Dynamic Critical Path Scheduling Parallel Programs onto Multiprocessors
Mourad Hakem, Franck Butelle · Proceedings - IEEE International Parallel and Distributed Processing Symposium · 2005
In this paper we present an efficient algorithm for compile-time scheduling and clustering of parallel programs onto parallel processing systems with distributed memory, which is called the dynamic critical path scheduling DCPS. The DCPS is superior to several other algorithms from the literature in terms of computational complexity, processors consumption and solution quality. DCPS has a time complexity of O(e+vlogv), as opposed to DSC algorithm O((e+v) logv) which is the best known algorithm.
Cited by 25 works. doi:10.1109/ipdps.2005.175
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- DSC: scheduling parallel tasks on an unbounded number of processors
- Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors
- Partitioning and Scheduling Parallel Programs for Multiprocessing
- Scheduling parallel program tasks onto arbitrary target machines
- Partitioning and scheduling parallel programs for execution on multiprocessors
- On the granularity and clustering of directed acyclic task graphs
- Scheduling with sufficient loosely coupled processors
- List scheduling with and without communication delays