Hyperplane based approach for optimizing spatial locality in loop nests

M. Kandemir*, A. Choudhary, N. Shenoy, P. Banerjee, J. Ramanujam

*Corresponding author for this work

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

30 Scopus citations

Abstract

This paper presents a data layout optimization technique based on the theory of hyperplanes from linear algebra. Given a program, our framework automatically determines the optimal 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 specific conditions a loop nest can be optimized for perfect spatial locality by using data transformations. We divide the problem of optimizing data layout into two independent subproblems: (1) determining optimal layouts, and (2) determining data transformation matrices to implement 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. Our results on eight programs on SGI Origin 2000 distributed-shared-memory multiprocessor show that the layout optimizations are effective in optimizing spatial locality.

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Supercomputing
Editors Anon
PublisherACM
Pages69-76
Number of pages8
StatePublished - Jan 1 1998
EventProceedings of the 1998 International Conference on Supercomputing - Melbourne, Aust
Duration: Jul 13 1998Jul 17 1998

Other

OtherProceedings of the 1998 International Conference on Supercomputing
CityMelbourne, Aust
Period7/13/987/17/98

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Hyperplane based approach for optimizing spatial locality in loop nests'. Together they form a unique fingerprint.

Cite this