mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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 accurate cost model for guiding data locality transformations
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
Universitat Politècnicade Catalunya-Barcelona, Spain.
Mälardalen University. Universitat Politècnicade Catalunya-Barcelona, Spain.
Mälardalen University. Universitat Politècnicade Catalunya-Barcelona, Spain.
2005 (English)In: ACM Transactions on Programming Languages and Systems, ISSN 0164-0925, E-ISSN 1558-4593, Vol. 27, no 5, 946-987 p.Article in journal (Refereed) Published
Resource type
Text
Abstract [en]

Caches have become increasingly important with the widening gap between main memory and processor speeds. Small and fast cache memories are designed to bridge this discrepancy. However, they are only effective when programs exhibit sufficient data locality. The performance of the memory hierarchy can be improved by means of data and loop transformations. Tiling is a loop transformation that aims at reducing capacity misses by shortening the reuse distance. Padding is a data layout transformation targeted to reduce conflict misses. This article presents an accurate cost model that describes misses across different hierarchy levels and considers the effects of other hardware components such as branch predictors. The cost model drives the application of tiling and padding transformations. We combine the cost model with a genetic algorithm to compute the tile and pad factors that enhance the program performance. To validate our strategy, we ran experiments for a set of benchmarks on a large set of modern architectures. Our results show that this scheme is useful to optimize programs' performance. When compared to previous approaches, we observe that with a reasonable compile-time overhead, our approach gives significant performance improvements for all studied kernels on all architectures.

Place, publisher, year, edition, pages
2005. Vol. 27, no 5, 946-987 p.
Keyword [en]
Cache memories, Genetic algorithms, Padding, Tiling, Cost model, Data locality, Cache memory, Costs, Data reduction, Hierarchical systems, Mathematical models, Program processors, Data transfer
Identifiers
URN: urn:nbn:se:mdh:diva-31914DOI: 10.1145/1086642.1086646Scopus ID: 2-s2.0-33745423635OAI: oai:DiVA.org:mdh-31914DiVA: diva2:937497
Available from: 2016-06-15 Created: 2016-06-14 Last updated: 2016-06-15Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus
By organisation
Embedded SystemsMälardalen University
In the same journal
ACM Transactions on Programming Languages and Systems

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 9 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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