Optimizing inter-nest data locality

M. Kandemir*, I. Kadayif, Alok Nidhi Choudhary, J. A. Zambreno

*Corresponding author for this work

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

12 Scopus citations

Abstract

By examining data reuse patterns of four array-intensive embedded applications, we found that these codes exhibit a significant amount of inter-nest reuse (i. e., the data reuse that occurs between different nests). While traditional compiler techniques that target array-intensive applications can exploit intra-nest data reuse, there has not been much success in the past in taking advantage of internest data reuse. In this paper, we present a compiler strategy that optimizes inter-nest reuse using loop (iteration space) transformations. Our approach captures the impact of execution of a nest on cache contents using an abstraction called footprint vector. Then, it transforms a given nest such that the new (transformed) access pattern reuses the data left in cache by the previous nest in the code. In optimizing inter-nest locality, our approach also tries to achieve good intra-nest locality. Our simulation results indicate large performance improvements. In particular, inter-nest loop optimization generates competitive results with intra-nest loop and data optimizations.

Original languageEnglish (US)
Title of host publicationProceedings of the 2002 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES '02
Pages127-135
Number of pages9
DOIs
StatePublished - Dec 1 2002
Event2002 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES '02 - Grenoble, France
Duration: Oct 8 2002Oct 11 2002

Publication series

NameProceedings of the 2002 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES '02

Other

Other2002 International Conference on Compilers, Architecture, and Synthesis for Embedded Systems, CASES '02
CountryFrance
CityGrenoble
Period10/8/0210/11/02

Keywords

  • Array-intensive codes
  • Cache locality
  • Data reuse
  • Embedded applications
  • Inter-nest optimization

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering

Cite this