Data relocation and prefetching for programs with large data sets

Yoji Yamada, John Gyllenhall, Grant Haab, Wen-Mei W Hwu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Numerical applications frequently contain nested loop structures that process large arrays of data. The execution of these loop structures often produces memory reference patterns that poorly utilize data caches. Limited associativity and cache capacity result in cache conflict misses. Also, nonunit stride access patterns can cause low utilization of cache lines. Data copying has been proposed and investigated in order to reduce cache conflict misses [1][2], but this technique has a high execution overhead since it performs the copy operations entirely in software. We propose a combined hardware and software technique called data relocation and prefetching which eliminates much of the overhead of data copying through the use of special hardware. Furthermore, by relocating the data while performing software prefetching, the overhead of copying the data can be reduced further. Experimental results for data relocation and prefetching are encouraging and show a large improvement in cache performance.

Original languageEnglish (US)
Title of host publicationProceedings of the 27th Annual International Symposium on Microarchitecture, MICRO 1994
PublisherIEEE Computer Society
Pages118-127
Number of pages10
ISBN (Electronic)0897917073
DOIs
StatePublished - Nov 30 1994
Event27th Annual International Symposium on Microarchitecture, MICRO 1994 - San Jose, United States
Duration: Nov 30 1994Dec 2 1994

Publication series

NameProceedings of the Annual International Symposium on Microarchitecture, MICRO
VolumePart F129425
ISSN (Print)1072-4451

Other

Other27th Annual International Symposium on Microarchitecture, MICRO 1994
CountryUnited States
CitySan Jose
Period11/30/9412/2/94

Fingerprint

Copying
Relocation
Hardware
Data storage equipment

Keywords

  • Cache conflicts
  • Data copying
  • Data relocation
  • Program optimization
  • Software prefetching

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this

Yamada, Y., Gyllenhall, J., Haab, G., & Hwu, W-M. W. (1994). Data relocation and prefetching for programs with large data sets. In Proceedings of the 27th Annual International Symposium on Microarchitecture, MICRO 1994 (pp. 118-127). (Proceedings of the Annual International Symposium on Microarchitecture, MICRO; Vol. Part F129425). IEEE Computer Society. https://doi.org/10.1145/192724.192740

Data relocation and prefetching for programs with large data sets. / Yamada, Yoji; Gyllenhall, John; Haab, Grant; Hwu, Wen-Mei W.

Proceedings of the 27th Annual International Symposium on Microarchitecture, MICRO 1994. IEEE Computer Society, 1994. p. 118-127 (Proceedings of the Annual International Symposium on Microarchitecture, MICRO; Vol. Part F129425).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Yamada, Y, Gyllenhall, J, Haab, G & Hwu, W-MW 1994, Data relocation and prefetching for programs with large data sets. in Proceedings of the 27th Annual International Symposium on Microarchitecture, MICRO 1994. Proceedings of the Annual International Symposium on Microarchitecture, MICRO, vol. Part F129425, IEEE Computer Society, pp. 118-127, 27th Annual International Symposium on Microarchitecture, MICRO 1994, San Jose, United States, 11/30/94. https://doi.org/10.1145/192724.192740
Yamada Y, Gyllenhall J, Haab G, Hwu W-MW. Data relocation and prefetching for programs with large data sets. In Proceedings of the 27th Annual International Symposium on Microarchitecture, MICRO 1994. IEEE Computer Society. 1994. p. 118-127. (Proceedings of the Annual International Symposium on Microarchitecture, MICRO). https://doi.org/10.1145/192724.192740
Yamada, Yoji ; Gyllenhall, John ; Haab, Grant ; Hwu, Wen-Mei W. / Data relocation and prefetching for programs with large data sets. Proceedings of the 27th Annual International Symposium on Microarchitecture, MICRO 1994. IEEE Computer Society, 1994. pp. 118-127 (Proceedings of the Annual International Symposium on Microarchitecture, MICRO).
@inproceedings{890d99ec5dbe46b09fb40cb12c34d977,
title = "Data relocation and prefetching for programs with large data sets",
abstract = "Numerical applications frequently contain nested loop structures that process large arrays of data. The execution of these loop structures often produces memory reference patterns that poorly utilize data caches. Limited associativity and cache capacity result in cache conflict misses. Also, nonunit stride access patterns can cause low utilization of cache lines. Data copying has been proposed and investigated in order to reduce cache conflict misses [1][2], but this technique has a high execution overhead since it performs the copy operations entirely in software. We propose a combined hardware and software technique called data relocation and prefetching which eliminates much of the overhead of data copying through the use of special hardware. Furthermore, by relocating the data while performing software prefetching, the overhead of copying the data can be reduced further. Experimental results for data relocation and prefetching are encouraging and show a large improvement in cache performance.",
keywords = "Cache conflicts, Data copying, Data relocation, Program optimization, Software prefetching",
author = "Yoji Yamada and John Gyllenhall and Grant Haab and Hwu, {Wen-Mei W}",
year = "1994",
month = "11",
day = "30",
doi = "10.1145/192724.192740",
language = "English (US)",
series = "Proceedings of the Annual International Symposium on Microarchitecture, MICRO",
publisher = "IEEE Computer Society",
pages = "118--127",
booktitle = "Proceedings of the 27th Annual International Symposium on Microarchitecture, MICRO 1994",

}

TY - GEN

T1 - Data relocation and prefetching for programs with large data sets

AU - Yamada, Yoji

AU - Gyllenhall, John

AU - Haab, Grant

AU - Hwu, Wen-Mei W

PY - 1994/11/30

Y1 - 1994/11/30

N2 - Numerical applications frequently contain nested loop structures that process large arrays of data. The execution of these loop structures often produces memory reference patterns that poorly utilize data caches. Limited associativity and cache capacity result in cache conflict misses. Also, nonunit stride access patterns can cause low utilization of cache lines. Data copying has been proposed and investigated in order to reduce cache conflict misses [1][2], but this technique has a high execution overhead since it performs the copy operations entirely in software. We propose a combined hardware and software technique called data relocation and prefetching which eliminates much of the overhead of data copying through the use of special hardware. Furthermore, by relocating the data while performing software prefetching, the overhead of copying the data can be reduced further. Experimental results for data relocation and prefetching are encouraging and show a large improvement in cache performance.

AB - Numerical applications frequently contain nested loop structures that process large arrays of data. The execution of these loop structures often produces memory reference patterns that poorly utilize data caches. Limited associativity and cache capacity result in cache conflict misses. Also, nonunit stride access patterns can cause low utilization of cache lines. Data copying has been proposed and investigated in order to reduce cache conflict misses [1][2], but this technique has a high execution overhead since it performs the copy operations entirely in software. We propose a combined hardware and software technique called data relocation and prefetching which eliminates much of the overhead of data copying through the use of special hardware. Furthermore, by relocating the data while performing software prefetching, the overhead of copying the data can be reduced further. Experimental results for data relocation and prefetching are encouraging and show a large improvement in cache performance.

KW - Cache conflicts

KW - Data copying

KW - Data relocation

KW - Program optimization

KW - Software prefetching

UR - http://www.scopus.com/inward/record.url?scp=0006424869&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0006424869&partnerID=8YFLogxK

U2 - 10.1145/192724.192740

DO - 10.1145/192724.192740

M3 - Conference contribution

AN - SCOPUS:0006424869

T3 - Proceedings of the Annual International Symposium on Microarchitecture, MICRO

SP - 118

EP - 127

BT - Proceedings of the 27th Annual International Symposium on Microarchitecture, MICRO 1994

PB - IEEE Computer Society

ER -