Graph based framework to detect optimal memory layouts for improving data locality

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

Research output: Contribution to journalConference articlepeer-review

8 Scopus citations


In order to extract high levels of performance from modern parallel architectures, the effective management of deep memory hierarchies is very important. While architectural advances in caches help in better utilization of the memory hierarchy, compiler-directed locality enhancement techniques are also important. In this paper we propose a locality improvement technique that uses data space (array layout) transformations in contrast to most of the previous work based on iteration space (loop) transformations. In other words, rather than changing the order of loop iterations, our technique modifies the memory layouts of multi-dimensional arrays. In comparison with previous work on data transformations it brings two novelties. First, we formulate the problem on a special graph structure called the layout graph (LG) and use integer linear programming (ILP) methods to determine optimal layouts. Second, in addition to static layout detection, our approach also enables the compiler to determine optimal dynamic layouts; that is, the layouts that can be changed across loop nest boundaries. We believe that this is the first attempt to determine optimal dynamic memory layouts. We also present preliminary experimental results on the SGI Origin 2000 distributed shared memory multiprocessor. Our results so far are encouraging and indicate that the additional compilation time taken by the solver is tolerable.

Original languageEnglish (US)
Pages (from-to)738-743
Number of pages6
JournalProceedings of the International Parallel Processing Symposium, IPPS
StatePublished - Jan 1 1999
EventProceedings of the 1999 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing - San Juan
Duration: Apr 12 1999Apr 16 1999

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture


Dive into the research topics of 'Graph based framework to detect optimal memory layouts for improving data locality'. Together they form a unique fingerprint.

Cite this