Finding optimum wavefront of parallel computation

The problem of finding the optimum wavefront that minimizes total computation time is discussed for iterative computations over two-dimensional arrays executed on linear or two-dimensional processor arrays. Assuming a continuum of data elements in two-dimensional arrays computed on a linear array of processors, efficient algorithms are presented to determine the optimum wavefront of the computation and the optimum partitioning of the wavefront into sections assigned to individual processors. An O(n²) time algorithm, where n is the number of data dependence vectors, for finding the optimum wavefront for one-dimensional processor arrays is described. In addition, a method for finding a good wavefront for two-dimensional single-instruction, multiple-data (SIMD) machines is presented