Global Partitioning of Parallel Loops and Data Arrays for Caches and Distributed Memory in Multiprocessors

this paper we will present a solution to the problem of determining loop and data partitions automatically for programs with multiple loops and data arrays. We assume that parallelism in the source program is specified using parallel do loops. This can either be done by a programmer, or by a previous dependence analysis and parallelization. The full version of this work is in [2]. We have applied our algorithm to cache-coherent multiprocessors with physically distributed memory. We introduce a cost model that will estimate the cost of executing a loop given the loop partitions and the partitions of data arrays accessed by the loop. This cost model is based on architectural parameters such as the cost of local and remote cache misses. The cost model is used to drive an iterative solution to the global problem. We note that the demands of cache and data locality often conflict. The algorithm itself uses an iterative improvement method to arrive at a solution. We initially begin with a cache optimized solution as demanded in [1], and the heuristic method then determines the best data partitions given the loop partitions. Then the loop partitions are re-evaluated given the new data partitions. These forward and back phases of the algorithm are run until some threshold number of iterations, and the best solution found until then, as determined by the cost model, is used. 2 Loop Partitioning Overview This section gives a brief summary of the method for loop partitioning to increase cache reuse given in [1]. We use this method a