LCS Publication Details
Publication Title: AUTOMATIC PARTITIONING OF PARALLEL LOOPS FOR CACHE-COHERENT MULTIPROCESSORS
Publication Author: Agarwal, Anant
Additional Authors: Kranz, David and Natarajan, Venkat
LCS Document Number: MIT-LCS-TM-481
Publication Date: 12-1-1992
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
This paper presents a theoretical framework for automatically partitioning parallel loops to minimize cache coherency traffic on shared-memory multiprocessors. The framework introduces the notion of uniformly intersecting references to capture temporal locality in array references, and the idea of data footprints to estimate the communication traffic between processors. The framework uses lattice theory to compute the size of data footprints. We demonstrate that algorithms based on our framework discover optimal partitions in many cases, such as non-communication-free parallelogram partitions of affine loop index functions, which were not handled by previous algorithms. We also show that our framework correctly reproduces results from previous loop partitioning algorithms proposed by Abraham and Hudak and by Sadayappan and Ramanujam. Because they deal only with index expressions, the algorithms are computationally efficient as well. We have implemented a subset of this framework for rectangular partitioning in a compiler for the cache-coherent Alewife machine.
To obtain this publication:

To purchase a printed copy of this publication please contact MIT Document Services.