Automatic mapping of system of N-dimensional affine recurrence equations (SARE) onto distributed memory parallel systems

The automatic extraction of parallelism from algorithms, and the consequent parallel code generation, is a challenging problem. We present a procedure for automatic parallel code generation in the case of algorithms described through a SARE (Set of Affine Recurrence Equations). Starting from the original SARE description in an N-dimensional iteration space, the algorithm is converted into a parallel code for an (eventually virtual) m-dimensional distributed memory parallel machine (m<N). We demonstrate some theorems which are the mathematical basis for the proposed parallel generation tool. The projection technique used in the tool is based on the polytope model. Some affine transformations are introduced to project the polytope from the original iteration space onto another polytope, preserving the SARE semantic, in the time-processor (t,p) space. Points in (t,p) are individuated through the m-dimensional p coordinate and the n-dimensional t coordinate, resulting in N=n+m. Along with polytope transformation, a methodology to generate the code within processors is given. Finally, a cost function, used to guide the heuristic search for the polytope transformation and derived from the actual implementation of the method on an MPP SIMD machine, is introduced