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
