On balancing computational load on rings of processors
Lixin Gao, Arnold L. Rosenberg · 2002
We consider a simple, deterministic policy for scheduling certain genres of dynamically evolving computations-specifically, computations in which tasks that spawn produce precisely two offspring-on rings of processors. Such computations include, for instance, tree-structured branching computations. We believe that our policy yields good parallel speedup on most computations of the genre, but we have not yet been able to verify this. In the current paper, we show that when the evolving computations end up having the structure of complete binary trees or of two-dimensional pyramidal grids, our strategy yields almost optimal parallel speedup.>