TY - JOUR
T1 - Scheduling tree-dags using FIFO queues
T2 - A control-memory trade-off
AU - Bhatt, Sandeep N.
AU - Chung, Fan R.K.
AU - Leighton, F. Thomas
AU - Rosenberg, Arnold L.
PY - 1996/2/25
Y1 - 1996/2/25
N2 - 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 network of workstations. Our results expose and quantify a control-memory trade-off for such schedulers, when the computation being scheduled has the structure of a binary tree, with all arcs oriented either root-toward-leaves or leaves-toward-root. The combinatorial problem for the root-toward-leaves case takes the following form. (The leaves-toward-root case gives rise to a dual formulation, which yields the same trade-offs.) Consider, for integers k, N > 0, an algorithm that employs k FIFO queues in order to schedule an N-leaf binary tree in such a way that each nonleaf node of the tree is executed before its children. We establish a trade-off between the number of queues used by the algorithm - which we view as measuring the control complexity of the algorithm - and the memory requirements of the algorithm, as embodied in the required capacity of the largest-capacity queue. Specifically, for each integer k ∈ {1, 2, ..., log2 N}, let ℒk(N) denote the minimax per-queue capacity for a k-queue algorithm that schedules all N-leaf binary trees; let ℒ*k(N) denote the analogous quantity for complete binary trees. We establish the following bounds: For general N-leaf binary trees, for all k, (formula presented) For complete binary trees, we derive tighter bounds. We prove that for all constant k, (formula presented) For general k, we obtain the following bounds: (formula presented) Similar trade-offs are readily established for trees of any fixed branching factor.
AB - 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 network of workstations. Our results expose and quantify a control-memory trade-off for such schedulers, when the computation being scheduled has the structure of a binary tree, with all arcs oriented either root-toward-leaves or leaves-toward-root. The combinatorial problem for the root-toward-leaves case takes the following form. (The leaves-toward-root case gives rise to a dual formulation, which yields the same trade-offs.) Consider, for integers k, N > 0, an algorithm that employs k FIFO queues in order to schedule an N-leaf binary tree in such a way that each nonleaf node of the tree is executed before its children. We establish a trade-off between the number of queues used by the algorithm - which we view as measuring the control complexity of the algorithm - and the memory requirements of the algorithm, as embodied in the required capacity of the largest-capacity queue. Specifically, for each integer k ∈ {1, 2, ..., log2 N}, let ℒk(N) denote the minimax per-queue capacity for a k-queue algorithm that schedules all N-leaf binary trees; let ℒ*k(N) denote the analogous quantity for complete binary trees. We establish the following bounds: For general N-leaf binary trees, for all k, (formula presented) For complete binary trees, we derive tighter bounds. We prove that for all constant k, (formula presented) For general k, we obtain the following bounds: (formula presented) Similar trade-offs are readily established for trees of any fixed branching factor.
UR - http://www.scopus.com/inward/record.url?scp=0030600713&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0030600713&partnerID=8YFLogxK
U2 - 10.1006/jpdc.1996.0024
DO - 10.1006/jpdc.1996.0024
M3 - Article
AN - SCOPUS:0030600713
SN - 0743-7315
VL - 33
SP - 55
EP - 68
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 1
ER -