Toward Efficient Scheduling of Evolving Computations on Rings of Processors
✍ Scribed by Li-Xin Gao; Arnold L. Rosenberg
- Publisher
- Elsevier Science
- Year
- 1996
- Tongue
- English
- Weight
- 320 KB
- Volume
- 38
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
We study a simple, low-overhead policy for scheduling dynamically evolving 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 large classes of these computations, but we have not yet been able to verify this. In the current paper, we adduce evidence that the policy works well on computations that end up being large and ''bushy,'' by showing (a) that it balances loads well as long as tasks keep spawning, and (b) that it yields asymptotically optimal parallel speedup when the evolving computations end up having the structure of complete binary trees or of two-dimensional pyramidal meshes. Specifically, we show that a p-processor ring can execute a computation that evolves into the height-n complete binary tree (which has 2 n ؊ 1 nodes) in time
Similarly, the ring can execute a computation that evolves into the side-n pyramidal mesh (which has ( n؉1 2 ) nodes) in time