Adaptive Guided Self-Scheduling

Adaptive Guided Self-Scheduling

Abstract

Loops are an important source of parallelism in application programs.
The iterations of such loops may be scheduled statically
(at compile time) or dynamically (at run-time) onto the processors
of a parallel machine.
Dynamic scheduling methods, although offering increased robustness
and flexibility relative to static approaches,
must be carefully designed if they are to simultaneously
achieve low overhead and good load balance.

In this paper we propose Adaptive Guided Self-Scheduling, an
enhancement of the Guided Self-Scheduling (GSS) approach to the
dynamic scheduling of loops with independent iterations.  Adaptive
Guided Self-Scheduling addresses the two principal weaknesses of GSS:
excessive overhead caused by fine grained scheduling of the final few
loop iterations when iteration execution times are small, and load
imbalance resulting from consecutive iteration execution times that
vary widely but in a correlated way.  We address the first weakness by
adaptively adjusting the scheduling granularity if, at run time, loop
iterations are determined to be so short that overhead would otherwise
be excessive.  We address the second weakness by providing the option
of wrapped assignment of loop iterations, assigning processors groups
of iterations sampled uniformly throughout the iteration space rather
than blocks of consecutive iterations.

Performance measurements are presented for an implementation of Adaptive
Guided Self-Scheduling on a Sequent Symmetry multiprocessor.