Perfectly nested loops : communication and memory reuse for do-across loops

The expression of problem solutions in a serial form has distinct advantages over parallel implementations from the programmer's point of view: 1. The thought process involved in constructing a program solution is more intuitive. 2. The language itself, (eg FORTRAN), can be standard across a large range of platforms. Although often under one paradigm one of the above may be true, both are seldom true simultaneously. Frequently programs which are used to solve scientific or engineering problems display a high degree of repetitiveness. This regular and repetitive nature has a high degree of inherent parallelism. The extraction and exploitation of parallelism from program structures such as loop nests has been extensively studied. A set of fundamental transforms form a basis for extracting parallelism. Some of these techniques are: data space transforms such as array expansion and scalar expansion, loop transformations such as skewing, reversal, interchange and tiling. Other methods such as ChainBased Scheduling rely on these techniques. In this thesis we examine a perfectly nested set of loops, in which some or all of those loops are Do-ACROSS loops. The loop nest is partitioned by tiling and the resulting subsets of iterations are not independent. This gives rise to several issues: 1. Communication:- what messages must be sent and what they actually contain. 2. Data Distribution:- what data is needed by which processor and what data must be shared. 3. Memory Reuse:- can memory be reused during execution, if so under what conditions. These issues are covered and answered by techniques presented in this thesis