TY - GEN
T1 - Scheduling trees using FIFO queues
T2 - 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
AU - Bhatt, Sandeep
AU - Chung, Fan
AU - Leighton, Tom
AU - Rosenberg, Arnold
N1 - Publisher Copyright:
© 1994 ACM.
PY - 1994/8/1
Y1 - 1994/8/1
N2 - We study a combinatorial problem that is motivated by "client-server" schedulers for networks of workstations. Using a number of FIFO queues the scheduler is required to schedule iV-leaf binary (or any fixed degree) trees in such a way that each non- leaf node of the tree being scheduled is executed before its children. We establish a tradeoff 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. Let Qk(N) denote the minimax per-queue capacity for a Ac-queue algorithm that schedules all iV-leaf binary trees, and let Q∗ k(N) denote the analogous quantity for complete binary trees. We establish the following bounds. For all N, k ≤ log N, 1 (2N-1)1lk /k log N+1 ≤ Qk(N) ≤ 2N1/; + 1, 1/k N1k/(logN+1)1-1/k ≤ Q∗k (N) ≤ (4k)1-1/k N1/k/log 1-1/kN The bound for complete binary trees is tight, to within constant factors, for all fixed k.
AB - We study a combinatorial problem that is motivated by "client-server" schedulers for networks of workstations. Using a number of FIFO queues the scheduler is required to schedule iV-leaf binary (or any fixed degree) trees in such a way that each non- leaf node of the tree being scheduled is executed before its children. We establish a tradeoff 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. Let Qk(N) denote the minimax per-queue capacity for a Ac-queue algorithm that schedules all iV-leaf binary trees, and let Q∗ k(N) denote the analogous quantity for complete binary trees. We establish the following bounds. For all N, k ≤ log N, 1 (2N-1)1lk /k log N+1 ≤ Qk(N) ≤ 2N1/; + 1, 1/k N1k/(logN+1)1-1/k ≤ Q∗k (N) ≤ (4k)1-1/k N1/k/log 1-1/kN The bound for complete binary trees is tight, to within constant factors, for all fixed k.
UR - http://www.scopus.com/inward/record.url?scp=85032444497&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85032444497&partnerID=8YFLogxK
U2 - 10.1145/181014.181048
DO - 10.1145/181014.181048
M3 - Conference contribution
AN - SCOPUS:85032444497
T3 - Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
SP - 85
EP - 93
BT - Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
Y2 - 27 June 1994 through 29 June 1994
ER -