Scheduling trees using FIFO queues: A control-memory tradeoff

Sandeep Bhatt, Fan Chung, Tom Leighton, Arnold Rosenberg

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationProceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
Pages85-93
Number of pages9
ISBN (Electronic)0897916719, 9780897916714
DOIs
StatePublished - 1 Aug 1994
Event6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994 - Cape May, United States
Duration: 27 Jun 199429 Jun 1994

Publication series

NameProceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994

Conference

Conference6th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 1994
Country/TerritoryUnited States
CityCape May
Period27/06/9429/06/94

Fingerprint

Dive into the research topics of 'Scheduling trees using FIFO queues: A control-memory tradeoff'. Together they form a unique fingerprint.

Cite this