A linear algebra framework for automatic determination of optimal data layouts

Mahmut Kandemir, Alok Choudhary, Nagaraj Shenoy, Prithviraj Banerjee, J. Ramanujam

Research output: Contribution to journalArticlepeer-review

45 Scopus citations

Abstract

This paper presents a data layout optimization technique for sequential and parallel programs based on the theory of hyperplanes from linear algebra. Given a program, our framework automatically determines suitable memory layouts that can be expressed by hyperplanes for each array that is referenced. We discuss the cases where data transformations are preferable to loop transformations and show that under certain conditions a loop nest can be optimized for perfect spatial locality by using data transformations. We argue that data transformations can also optimize spatial locality for some arrays without distorting temporal/spatial locality exhibited by others. We divide the problem of optimizing data layout into two independent subproblems: 1) determining optimal static data layouts, and 2) determining data transformation matrices to implement the optimal layouts. By postponing the determination of the transformation matrix to the last stage, our method can be adapted to compilers with different default layouts. We then present an algorithm that considers optimizing parallelism and spatial locality simultaneously. Our results on eight programs on two distributed shared-memory multiprocessors, the Convex Exemplar SPP-2000 and the SGI Origin 2000, show that the layout optimizations are effective in optimizing spatial locality and parallelism.

Original languageEnglish (US)
Pages (from-to)115-135
Number of pages21
JournalIEEE Transactions on Parallel and Distributed Systems
Volume10
Issue number2
DOIs
StatePublished - 1999

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'A linear algebra framework for automatic determination of optimal data layouts'. Together they form a unique fingerprint.

Cite this