KIT | KIT-Bibliothek | Impressum | Datenschutz

Improving data layout through coloring-directed array merging

Genius, Daniela; Lelait, Sylvain


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

There are two main difficulties that cannot be dealt with by
alone. Firstly, a cache line usually holds several values; often
one of them is actually used. Secondly, conflicting accesses to
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
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
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