Code Generation for General Loops using Methods from Computational Geometry

T. Andronikos, F.M. Ciorba, D. Kamenopoulos, P. Theodoropoulos, and G. Papakonstantinou (Greece)


General loops, dynamic scheduling, automatic SPMD code generation, message passing architectures.


This paper deals with general nested loops and proposes a novel dynamic scheduling technique. General loops con tain complex loop bodies (consisting of arbitrary program statements, such as assignments, conditionals and rep etitions) that exhibit uniform loop-carried dependencies. Therefore it is now possible to achieve efficient paralleliza tion for a vast class of loops, mostly found in DSP, PDEs, signal and video coding. At the core of this technique lies a simple and efficient dynamic rule (SDS - Successive Dy namic Scheduling) for determining the next ready-to-be executed iteration at runtime. The central idea is to sched ule the iterations on-the-fly using SDS, along the optimal hyperplane (determined using the QuickHull algorithm). Furthermore, a tool (CRONUS/1) that implements this the ory and automatically produces the SPMD parallel code for message passing architectures is presented. As a testing case study, the FSBM motion estimation algorithm (used in video coding standards, e.g., MPEG-2, H.261) was used. The experimental results validate the presented theory and corroborate the efficiency of the generated parallel code.

Important Links:

Go Back