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

Patrice Quinton (1) , Tomofumi Yuki (2)

1 ENS Rennes - École normale supérieure - Rennes
2 TARAN - Architectures matérielles spécialisées pour l’ère post loi-de-Moore

Polyhedral 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.

Mots clés: Polyhedral model; Synthesis of parallel programs; Scheduling of parallel programs

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Patrice Quinton, Tomofumi Yuki. Representing Non-Affine Parallel Algorithms by means of Recursive Polyhedral Equations. IMPACT 2021 - International Microsystems, Packaging, Assembly and Circuits Technology conference, Hipeac 2021, Jan 2021, Budapest, Hungary. pp.1-11. ⟨hal-03518569⟩