Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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
Identifiers
URN: urn:nbn:se:kth:diva-72962ISBN: 0-7923-7370-7 (print)OAI: oai:DiVA.org:kth-72962DiVA: diva2:488457
Conference
Workshop on Interaction between Compilers and Computer Architectures (INTERACT-5)
Funder
Swedish Research Council, 97-722
Note
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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 89 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf