Automatic Generation of Modular Time-Space Mappings and Data Alignments

Time-space transformations and data alignments that can lead to efficient execution of parallel programs have been extensively studied. Recently, modular time-space transformations have been proposed to generate a class of algorithm mappings that cannot be described by linear time-space transformations. This paper proposes a new class of data alignments, called expanded modular data alignments (EMDAs), for programs that result from modular time-space transformations. An EMDA subsumes multiple modular data alignments, which are described by affine functions modulo a constant vector. Conditions of a modular time-space mapping and an EMDA for perfect alignment are described. However, these conditions together with other conditions for validity and optimality of a modular mapping introduce nonlinear constraints in the problem of generating modular mappings. A method of O(n ²) complexity is provided to choose some entries of a transformation matrix so that nonlinear constraints are transformed into linear ones, where n is the dimension of the computation domain (e.g., the number of nested loops). Although the solution space of the problem is reduced by assigning fixed values to some entries, the proposed heuristic attempts to minimize the number of the fixed entries and consequently to exclude as few solutions as possible.