Change search
ReferencesLink to record
Permanent link

Direct link
An Efficient Semi-Hierarchical Array Layout
KTH, Superseded Departments, Teleinformatics.
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS. KTH, Superseded Departments, Teleinformatics.
Mälardalen University.
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)
Abstract [en]

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.
National Category
Computer Systems
URN: urn:nbn:se:kth:diva-72962ISBN: 0-7923-7370-7OAI: diva2:488457
Workshop on Interaction between Compilers and Computer Architectures (INTERACT-5)
Swedish Research Council, 97-722
NR 20140805Available from: 2012-02-01 Created: 2012-02-01 Last updated: 2012-02-01Bibliographically approved

Open Access in DiVA

No full text

By organisation
TeleinformaticsSoftware and Computer Systems, SCS
Computer Systems

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 15 hits
ReferencesLink to record
Permanent link

Direct link