Lower and upper bounds on time for multiprocessor optimal schedules
- 1 January 1994
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 5 (8) , 879-886
- https://doi.org/10.1109/71.298216
Abstract
The lower and upper bounds on the minimum time needed to process a given directedacyclic task graph for a given number of processors are derived. It is proved that theproposed lower bound on time is not only sharper than the previously known values butalso easier to calculate. The upper bound on time, which is useful in determining theworst case behavior of a given task graph, is presented. The lower and upper bounds onthe minimum number of processors required to process a given task graph in the minimum possible time are also derived. It is seen with a number of randomly generated dense task graphs that the lower and upper bounds we derive are equal, thus giving the optimal time for scheduling directed acyclic task graphs on a given set of processors.Keywords
This publication has 17 references indexed in Scilit:
- Parallelism measures of task graphs for multiprocessorsMicroprocessing and Microprogramming, 1994
- Measuring parallelism in algorithmsMicroprocessing and Microprogramming, 1992
- Task assignment in a multiprocessor systemMicroprocessing and Microprogramming, 1989
- Two Processor Scheduling is in $\mathcal{NC}$SIAM Journal on Computing, 1987
- Scheduling precedence graphs of bounded heightJournal of Algorithms, 1984
- An Almost-Linear Algorithm for Two-Processor SchedulingJournal of the ACM, 1982
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975
- Measurements of parallelism in ordinary FORTRAN programsComputer, 1974
- Bounds on the Number of Processors and Time for Multiprocessor Optimal SchedulesIEEE Transactions on Computers, 1973
- Bounds on Multiprocessing Timing AnomaliesSIAM Journal on Applied Mathematics, 1969