A Matrix-Based Approach to Global Locality Optimization

Mahmut Kandemir, Alok Choudhary, J. Ramanujam, Prith Banerjee*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


Global locality optimization is a technique for improving the cache performance of a sequence of loop nests through a combination of loop and data layout transformations. Pure loop transformations are restricted by data dependencies and may not be very successful in optimizing imperfectly nested loops and explicitly parallelized programs. Although pure data transformations are not constrained by data dependencies, the impact of a data transformation on an array might be program-wide; that is, it can affect all the references to that array in all the loop nests. Therefore, in this paper we argue for an integrated approach that employs both loop and data transformations. The method enjoys the advantages of most of the previous techniques for enhancing locality and is efficient. In our approach, the loop nests in a program are processed one by one and the data layout constraints obtained from one nest are propagated for optimizing the remaining loop nests. We show a simple and effective matrix-based framework to implement this process. The search space that we consider for possible loop transformations can be represented by general nonsingular linear transformation matrices and the data layouts that we consider are those that can be expressed using hyperplanes. Experiments with several floating-point programs on an 8-processor SGI Origin 2000 distributed-shared-memory machine demonstrate the efficacy of our approach.

Original languageEnglish (US)
Pages (from-to)190-235
Number of pages46
JournalJournal of Parallel and Distributed Computing
Issue number2
StatePublished - Aug 1999


  • Array restructuring
  • Data reuse
  • Data transformations
  • Locality
  • Loop tranformations
  • Memory hierarchy
  • Parallelism

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'A Matrix-Based Approach to Global Locality Optimization'. Together they form a unique fingerprint.

Cite this