Binary Trees and Parallel Scheduling Algorithms
- 1 March 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-32 (3), 307-315
- https://doi.org/10.1109/tc.1983.1676223
Abstract
This paper examines the use of binary trees in the design of efficient parallel algorithms. Using binary trees, we develop efficient algorithms for several scheduling problems. The shared memory model for parallel computation is used. Our success in using binary trees for parallel computations, indicates that the binary tree is an important and useful design tool for parallel algorithms.Keywords
This publication has 25 references indexed in Scilit:
- Parallel permutation and sorting algorithms and a new generalized connection networkJournal of the ACM, 1982
- An optimal routing algorithm for mesh-connected Parallel computersJournal of the ACM, 1980
- Fast parallel sorting algorithmsCommunications of the ACM, 1978
- Simple algorithms for multiprocessor scheduling to meet deadlinesInformation Processing Letters, 1977
- Sorting on a mesh-connected parallel computerCommunications of the ACM, 1977
- Bounds to Complexities of Networks for Sorting and for SwitchingJournal of the ACM, 1975
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974
- Some simple scheduling algorithmsNaval Research Logistics Quarterly, 1974
- Sequencing with due‐dates and early start times to minimize maximum tardinessNaval Research Logistics Quarterly, 1974
- Various optimizers for single‐stage productionNaval Research Logistics Quarterly, 1956