Data compiling for systems of affine recurrence equations

In order to get a parallel solution from a system of affine recurrence equations, a space-time transformation must first be determined. Such a transformation is characterized by a schedule and an allocation. In the context of data parallelism, efficient compilers require among other criteria appropriate data compiling techniques. These techniques should take into account the communication primitives of the target architecture (in particular broadcast primitives if any) and minimize the number of communications. The objective of this paper is to deal with these two questions (efficient use of broadcast capabilities and communication minimization) in order to determine efficient space-time transformations from systems of affine recurrence equations