SUPPLE: an Efficient Run-Time Support for Non-Uniform Parallel Loops

The efficient implementation of parallel loops on distributed--memory multicomputers is a hot topic of research. To this end, data parallel languages generally exploit static data layout and static scheduling of iterations. Unfortunately, when iteration execution costs vary considerably and are unpredictable, some processors may be assigned more work than others. Workload imbalance can be mitigated by cyclically distributing data and associated computations. Though this strategy often solves load balance issues, it may worsen data locality exploitation. This paper presents SUPPLE (SUPort for Parallel Loop Execution), an innovative run--time support for parallel loops with regular stencil data references and non--uniform iteration costs. SUPPLE relies upon a static block data distribution to exploit locality, and combines static and dynamic policies for scheduling non--uniform iterations. It adopts, as far as possible, a static scheduling policy derived from the owner computes rule, and..