Loop Distribution with Arbitrary Control Flow

Loop distribution is an integral part of transforming a sequential program into a parallel one. It is used extensively in parallelization, vectorization, and memory management. For loops with control flow, previous methods for loop distribution have significant drawbacks. We present a new algorithm for loop distribution in the presence of control flow modeled by a control dependence graph. This algorithm is shown optimal in that it generates the minimum number of new arrays and tests possible. We also present a code generation algorithm that produces code for the resulting program without replicating statements or conditions. Although these algorithms are being developed for use in an interactive parallel programming environment for Fortran, they are very general and can be used in automatic parallelization and vectorization systems. Keywords: parallelization, vectorization, transformation, control dependence, data dependence, loop distribution 1 Introduction Loop distribution is a f..