SCHEDULING TREE-DAGS USING FIFO QUEUES - A CONTROL-MEMORY TRADE-OFF

We study a combinatorial problem that is motivated by ''client-server' ' schedulers for parallel computations. Such schedulers are often used , for instance, when computations are being done by a cooperating netw ork of workstations. Our results expose and quantify a control-memory trade-off for such scheduler, when the computation being scheduled has the structure of a binary tree, with all arcs oriented either root-to ward-leaves or leaves-toward-root. The combinatorial problem for the r oot-toward-leaves case takes the following form. (The leaves-toward-ro ot case gives rise to a dual formulation, which yields the same trade- offs.) Consider, for integers k, N > 0, an algorithm that employs k FI FO queues in order to schedule an N-leaf binary tree in such a way tha t each nonleaf node of the tree is executed before its children. We es tablish a trade-off between the number of queues used by the algorithm -which we view as measuring the control complexity of the algorithm-an d the memory requirements of the algorithm, as embodied in the require d capacity of the largest-capacity queue. Specifically, for each integ er k is an element of {1, 2, ..., log(2) N}, let 2(k)(N) denote the mi nimax per-queue capacity for a k-queue algorithm that schedules all N- leaf binary trees; let 2(k)(N) denote the analogous quantity for comp lete binary trees. We establish the following bounds: For general N-le af binary trees, for all k, 1/k (2N - 1)(1/k)/log N + 1 less than or e qual to 2(k)(N) less than or equal to 2N(1/k) + 1. For complete binary trees, we derive tighter bounds. We prove that for all constant k, 2( k)(N) = Theta (N-1/k/log(1-1/k) N). For general k, we obtain the foll owing bounds: 1/k N-1/k/(log N + 1)(1-1k) less than or equal to 2(k)( N) less than or equal to (4k)(1-1/k) N-1/k/log(1-1/k) N. Similar trade -offs are readily established for trees of any fixed branching factor. (C) 1996 Academic Press, Inc.