TOWARD EFFICIENT SCHEDULING OF EVOLVING COMPUTATIONS ON RINGS OF PROCESSORS

We study a simple, low-overhead policy for scheduling dynamically evol ving computations in which tasks that spawn produce precisely two offs pring, on rings of processors. Such computations include, for instance , tree-structured branching computations. We believe that our policy y ields good parallel speedup on large classes of these computations, bu t we have not yet been able to verify this. In the current paper, we a dduce 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 c omputation that evolves into the height-n complete binary tree (which has 2(n) - 1 nodes) in time T-tree(n;p) less than or equal to 1/2 (2(n ) - 1) + p + (2 cos(pi/p))(n) = (1 + o(1)) 1/p (2(n) - 1). Similarly, the ring can execute a computation that evolves into the side-n pyrami dal mesh (which has ((n+1)(2)) nodes) in time T-mesh(n'p) less than or equal to 1/p ((n + 1)(2)) + 3/2 n + 2 = (1 + o(1)) 1/p ((n + 1)(2)). (C) 1996 Academic Press, Inc.