Representing Non-Affine Parallel Algorithms by means of Recursive Polyhedral Equations

International audiencePolyhedral equations allow parallel program to be ex- pressed, analyzed, and compiled automatically, but they cannot express divide-and-conquer approaches. This li- mitation is basically due to the affine nature of the de- pendence functions imposed by the model. In this pa- per, we describe how this limitation can be overcome by extending a structured polyhedral equational language to recursive calls of polyhedral programs. Doing so, we preserve the affine property inside a given call, whereas the non-affine part is carried by the recursive expres- sion of subsystem calls. We describe the basic mech- anisms of this extension, show that the fundamental results of polyhedral equations hold, in particular, the schedule of such a system can be found automatically. We illustrate this approach on several well known algo- rithms, including the FFT