An Efficient Semi-Hierarchical Array Layout
2001 (English)In: Interaction between Compilers and Computer Architectures / [ed] Gyungho Lee, Pen-Chung Yew, Kluwer Academic Publishers, 2001, 21-43 p.Conference paper (Refereed)
For high-level programming languages, linear array layout (e.g., column major and row major orders) have de facto been the sole form of mapping array elements to memory. The increasingly deep and complex memory hierarchies present in current computer systems expose several deficiencies of linear array layouts. One such deficiency is that linear array layouts strongly favor locality in one index dimension of multidimensional arrays. Secondly, the exact mapping of array elements to cache locations depend on the array’s size, which effectively renders linear array layouts non-analyzable with respect to cache behavior. We present and evaluate an alternative, semi-hierarchical, array layout which differs from linear array layouts by being neutral with respect to locality in different index dimensions and by enabling accurate and precise analysis of cache behaviors at compile-time. Simulation results indicate that the proposed layout may exhibit vastly improved TLB behavior, leading to clearly measurable improvements in execution time, despite a lack of suitable hardware support for address computations. Cache behavior is formalized in terms of conflict vectors, and it is shown how to compute such conflict vectors at compile-time.
Place, publisher, year, edition, pages
Kluwer Academic Publishers, 2001. 21-43 p.
IdentifiersURN: urn:nbn:se:kth:diva-72962ISBN: 0-7923-7370-7OAI: oai:DiVA.org:kth-72962DiVA: diva2:488457
Workshop on Interaction between Compilers and Computer Architectures (INTERACT-5)
FunderSwedish Research Council, 97-722
NR 201408052012-02-012012-02-012012-02-01Bibliographically approved