| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Improving Scheduling of Tasks in a Heterogeneous Environment
February 2004 (vol. 15 no. 2)
pp. 107-118
Abstract—Optimal scheduling of parallel tasks with some precedence relationship, onto a parallel machine is known to be NP-complete. The complexity of the problem increases when task scheduling is to be done in a heterogeneous environment, where the processors in the network may not be identical and take different amounts of time to execute the same task. This paper introduces a Task duplication-based scheduling Algorithm for Network of Heterogeneous systems (TANH), with complexity $\rm O(V^2)$, which provides optimal results for applications represented by Directed Acyclic Graphs (DAGs), provided a simple set of conditions on task computation and network communication time could be satisfied. The performance of the algorithm is illustrated by comparing the scheduling time with an existing “Best Imaginary Level scheduling (BIL)” scheme for heterogeneous systems. The scalability for a higher or lower number of processors, as per their availability is also discussed. This work is shown to provide substantial improvement over existing work on the Task Duplication-Based Scheduling Algorithm (TDS).
[1] 107 R.L. Graham, L.E. Lawler, J.K. Lenstra, and A.H. Kan, Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey Annals of Discrete Math., pp. 287-326, 1979.[2] T.L. Casavant and J.G. Kuhl,“A taxonomy of scheduling in general-purpose distributed computing systems,” IEEE Trans. on Software Engineering, vol. 14, no. 2. Feb. 1988.[3] S. Darbha and D.P. Agrawal, Optimal Scheduling Algorithm for Distributed-Memory Machines IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 1, pp. 87-95, Jan. 1998.[4] G.C. Sih and E.A. Lee, “A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures,” IEEE Trans. Parallel and Distributed Systems, vol. 4, no. 2, pp. 175-186, Feb. 1993.[5] A. Gerasoulis and T. Yang, A Comparison of Clustering Heuristics for Scheduling Directed Acyclic Graphs onto Multiprocessors J. Parallel and Distributed Computing, vol. 16, no. 4, pp. 276-291, Dec. 1992.[6] J.J. Hwang, Y.C. Chow, F.D. Anger, and C.Y. Lee, Scheduling Precedence Graphs in Systems with Inter Processor Communication Times SIAM J. Computing, vol. 18, no. 2, pp. 244-257, Apr. 1989.[7] S.J. Kim and J.C. Brown, A General Approach to Mapping of Parallel Computations upon Multiprocessor Architectures Proc. Int'l Conf. Parallel Processing, vol. 3, pp. 1-8, Aug. 1988.[8] S.S. Pande, D.P. Agrawal, and J. Mauney, A New Threshold Scheduling Strategy for Sisal Programs on Distributed Memory Systems J. Parallel and Distributed Computing, vol. 21, no. 2, pp. 223-236, May 1994.[9] S.S. Pande, D.P. Agrawal, and J. Mauney, "A Scalable Scheduling Method for Functional Parallelism on Distributed Memory MultiProcessors," IEEE Trans. Parallel and Distributed Systems, vol. 6, no. 4, pp. 388-399, Apr. 1995.[10] V. Sarkar, Partitioning and Scheduling Programs for Execution on Multiprocessors. MIT Press, 1989.[11] H.B. Chen, B. Shirazi, K. Kavi, and A.R. Hurson, Static Scheduling Using Linear Clustering and Task Duplication Proc. ISCA Int'l Conf. Parallel and Distributed Computing and Systems, pp. 285-290, 1993.[12] J.Y. Colin and P. Chretienne, C.P.M. Scheduling with Small Computation Delays and Task Duplication Operations Research, pp. 680-684, 1991.[13] I. Ahmad and Y. Kwok, On Exploiting Task Duplication in Parallel Program Scheduling IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 9, pp. 872-892, Sept. 1998.[14] E. Hodzic and W. Shang, On Supernode Transformation with Minimized Total Running Time IEEE Trans. Parallel and Distributed Systems, vol. 9, no. 5, pp. 417-428, May 1998.[15] K. Yu-Kwong and I. Ahmad, Benchmarking and Comparison of the Task Graph Scheduling Algorithms J. Parallel and Distributed Computing, vol. 59, no. 2, pp. 381-422, Dec. 1999.[16] C.I. Park and T.Y. Choe, An Optimal Scheduling Algorithm Based on Task Duplication IEEE Trans. Computers, vol. 51, no. 4, pp. 444-448, Apr. 2002.[17] K. Yu-Kwong and I. Ahmad, Link-Constrained Scheduling and Mapping of Tasks and Messages to a Network of Heterogeneous Processors Cluster Computing, vol. 3, no. 2, pp. 113-124, Sept. 2000.[18] O. Beaumont, V. Boudet, A. Legrand, F. Rastello, and Y. Robert, Heterogeneity Considered Harmful to Algorithm Designers Research Report No. 2000-24, Ecole Normale Superieure de Lyon, France, 2000.[19] O. Beaumont, A. Legrand, F. Rastello, and Y. Robert, Static LU Decomposition on Heterogeneous Platforms Research Report No. 2000-44, Ecole Normale Superieure de Lyon, France, 2000.[20] A. Ranaweera and D.P. Agrawal, Task Duplication Based Scheduling Algorithm for Heterogeneous Systems Proc. Int'l Parallel Processing Symp., pp. 445-450, 2000.[21] A. Ranaweera and D.P. Agrawal, A Scalable Task Duplication Based Scheduling Algorithm for Heterogeneous Systems Proc. Int'l Conf. Parallel Processing, pp. 383-390, Aug. 2000.[22] A. Ranaweera, Task Scheduling Algorithms for Heterogeneous Systems masters thesis, Univ. of Cincinnati, Ohio, 2000.[23] H. Oh and S. Ha, A Static Heuristic for Heterogeneous Processors Proc. European Conf. Parallel Processing (Euro-Par '96), vol. 2, pp. 573-577, Aug. 1996.[24] A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.[25] C.C. Hui and S.T. Chanson, Allocating Task Interaction Graphs to Processors in Heterogeneous Networks IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 9, pp. 908-926, Sept. 1997.[26] M. Kafeel and I. Ahmad, “Optimal Task Assignment in Heterogeneous Distributed Computing Systems,” IEEE Concurrency, vol. 6, no. 3, pp. 42-51, July 1998.[27] H. Topcuoglu, S. Hariri, and M.-Y. Wu, Task Scheduling Algorithms for Heterogeneous Processors Proc. Eighth Heterogeneous Computing Workshop, 1999.[28] M. Cosnard and E. Jeannot, Compact DAG Representation and Its Dynamic Scheduling J. Parallel and Distributed Computing, vol. 58, no. 3, pp. 487-514, Sept. 1999.[29] S. Darbha and D.P. Agrawal, A Task Duplication Based Scalable Scheduling Algorithm for Distributed Memory Systems J. Parallel and Distributed Computing, vol. 46, no. 1, pp. 15-27, Oct. 1997.
Index Terms:
Communication cost, computational cost, directed acyclic graph, heterogeneous environment, network of processors, optimal scheduling, task duplication.
Citation:
Rashmi Bajaj, Dharma P. Agrawal, "Improving Scheduling of Tasks in a Heterogeneous Environment," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 2, pp. 107-118, Feb. 2004, doi:10.1109/TPDS.2004.1264795
