KIT | KIT-Bibliothek | Impressum | Datenschutz

Improving data layout through coloring-directed array merging

Genius, Daniela; Lelait, Sylvain

Abstract:
Scientific computing and image processing applications access
large
amounts of data in regular patterns. In order to relieve the
memory
bottleneck, caching tries to keep recently referenced data
available
in fast storage. This is increasingly important as the gap
between
processor and memory hierarchy speed has widened in recent
years.

There are two main difficulties that cannot be dealt with by
hardware
alone. Firstly, a cache line usually holds several values; often
only
one of them is actually used. Secondly, conflicting accesses to
one
cache line cause data to be evicted which is still required.
In the extreme case, data is replaced on every access, a
situation we
denote as cache thrashing. To overcome these problems, the
temporal/spatial structure of accesses has to be changed.

Compile-time cache optimizations exploit regular access
patterns.
Loop transformations as e.g. tiling are well-established.
For caches with limited associativity, it is often crucial to
additionally adjust the placement of data in memory.
We show that compiler techniques for register allocation, namely
graph coloring, support a systematic data placement.
... mehr


Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Forschungsbericht/Preprint
Publikationsjahr 1999
Sprache Englisch
Identifikator ISSN: 1432-7864
urn:nbn:de:swb:90-AAA22994
KITopen-ID: 2299
Verlag Universität Karlsruhe (TH)
Umfang 32 S.
Serie Interner Bericht. Universität Karlsruhe, Fakultät für Informatik ; 1999,3
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page