Is reuse distance applicable to data locality analysis on chip multiprocessors?

Yunlian Jiang, Eddy Z. Zhang, Kai Tian, Xipeng Shen

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

55 Scopus citations

Abstract

On Chip Multiprocessors (CMP), it is common that multiple cores share certain levels of cache. The sharing increases the contention in cache and memory-to-chip bandwidth, further highlighting the importance of data locality analysis. As a rigorous and hardware-independent locality metric, reuse distance has served for a variety of locality analysis, program transformations, and performance prediction. However, previous studies have concentrated on sequential programs running on unicore processors. On CMP, accesses by different threads (or jobs) interact in the shared cache. How reuse distance applies to the new architecture remains an open question-particularly, how the interactions in shared cache affect the collection and application of reuse distance, and how reuse-distance-based locality analysis should adapt to such architecture changes. This paper presents our explorations towards answering those questions. It first introduces the concept of concurrent reuse distance, a direct extension of the traditional concept of reuse distance with data references by all co-running threads (or jobs) considered. It then discusses the properties of concurrent reuse distance, revealing the special challenges facing the collection and application of concurrent reuse distance on CMP platforms. Finally, it presents the solutions to those challenges for a class of multithreading applications. The solutions center on a probabilistic model that connects concurrent reuse distance with the data locality of each individual thread. Experiments demonstrate the effectiveness of the proposed techniques in facilitating the uses of concurrent reuse distance for CMP computing.

Original languageEnglish (US)
Title of host publicationCompiler Construction - 19th International Conference, CC 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Proceedings
Pages264-282
Number of pages19
DOIs
StatePublished - 2010
Externally publishedYes
Event19th International Conference on Compiler Construction, CC 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010 - Paphos, Cyprus
Duration: Mar 20 2010Mar 28 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6011 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other19th International Conference on Compiler Construction, CC 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010
Country/TerritoryCyprus
CityPaphos
Period3/20/103/28/10

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Is reuse distance applicable to data locality analysis on chip multiprocessors?'. Together they form a unique fingerprint.

Cite this