Title :
Improving cache locality with blocked array layouts
Author :
Athanasaki, Evangelia ; Koziris, Nectarios
Author_Institution :
Sch. of Electr. & Comput. Eng., Nat. Tech. Univ. of Athens, Greece
Abstract :
Minimizing cache misses is one of the most important factors to reduce average latency for memory accesses. Tiled codes modify the instruction stream to exploit cache locality for array accesses. Here, we further reduce cache misses, restructuring the memory layout of multidimensional arrays, that are accessed by tiled instruction code. In our method, array elements are stored in a blocked way, exactly as they are swept by the tiled instruction stream. We present a straightforward way to easily translate multidimensional indexing of arrays into their blocked memory layout using simple binary-mask operations. Indices for such array layouts are easily calculated based on the algebra of dilated integers, similarly to morton-order indexing. Actual experimental results, using matrix multiplication and LU-decomposition on various size arrays, illustrate that execution time is greatly improved when combining tiled code with tiled array layouts and binary mask-based index translation functions. Simulations using the Simplescalar tool, verify that enhanced performance is due to the considerable reduction of total cache misses.
Keywords :
cache storage; parallel processing; program control structures; Simplescalar tool; array access; blocked array layout; cache locality; dilated integer algebra; memory access latency; morton-order indexing; multidimensional array indexing; tiled instruction code; Algebra; Delay; Indexing; Laboratories; Law; Legal factors; Multidimensional systems; Pipeline processing; Registers; Systems engineering and theory;
Conference_Titel :
Parallel, Distributed and Network-Based Processing, 2004. Proceedings. 12th Euromicro Conference on
Print_ISBN :
0-7695-2083-9
DOI :
10.1109/EMPDP.2004.1271460