A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. (English) Zbl 1243.68103

Daoud, Mohammad I.; Kharma, Nawwaf

J. Parallel Distrib. Comput. 68, No. 4, 399-409 (2008).

Summary: Effective task scheduling is essential for obtaining high performance in heterogeneous distributed computing systems (HeDCSs). However, finding an effective task schedule in HeDCSs requires the consideration of both the heterogeneity of processors and high interprocessor communication overhead, which results from non-trivial data movement between tasks scheduled on different processors. In this paper, we present a new high-performance scheduling algorithm, called the longest dynamic critical path (LDCP) algorithm, for HeDCSs with a bounded number of processors. The LDCP algorithm is a list-based scheduling algorithm that uses a new attribute to efficiently select tasks for scheduling in HeDCSs. The efficient selection of tasks enables the LDCP algorithm to generate high-quality task schedules in a heterogeneous computing environment. The performance of the LDCP algorithm is compared to two of the best existing scheduling algorithms for HeDCSs: the HEFT and DLS algorithms. The comparison study shows that the LDCP algorithm outperforms the HEFT and DLS algorithms in terms of schedule length and speedup. Moreover, the improvement in performance obtained by the LDCP algorithm over the HEFT and DLS algorithms increases as the inter-task communication cost increases. Therefore, the LDCP algorithm provides a practical solution for scheduling parallel applications with high communication costs in HeDCSs.

MSC:

68M20	Performance evaluation, queueing, and scheduling in the context of computer systems
68M14	Distributed systems

Keywords:

task scheduling; directed acyclic graph; heuristics; parallel processing; heterogeneous systems

References:

[1]	Ahmad, I.; Kwok, Y. K.: On exploiting task duplication in parallel program scheduling, IEEE trans. Parallel distributed systems 9, No. 9, 872-892 (1998)
[2]	Bajaj, R.; Agrawal, D. P.: Improving scheduling of tasks in a heterogeneous environment, IEEE trans. Parallel distributed systems 15, No. 2, 107-118 (2004)
[3]	Bansal, S.; Kumar, P.; Singh, K.: An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems, IEEE trans. Parallel distributed systems 14, No. 6, 533-544 (2003)
[4]	Bansal, S.; Kumar, P.; Singh, K.: Dealing with heterogeneity through limited duplication for scheduling precedence constrained task graphs, J. parallel distributed comput. 65, No. 4, 479-491 (2005) · Zbl 1101.68405
[5]	Baskiyar, S.; Dickinson, C.: Scheduling directed a-cyclic task graphs on a bounded set of heterogeneous processors using task duplication, J. parallel distributed comput. 65, No. 8, 911-921 (2005) · Zbl 1072.68511
[6]	Boyer, W. F.; Hura, G. S.: Non-evolutionary algorithm for scheduling dependent tasks in distributed heterogeneous computing environments, J. parallel distributed comput. 65, No. 9, 1035-1046 (2005) · Zbl 1077.68534
[7]	Y.C. Chung, S. Ranka, Application and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed-memory multiprocessors, in: Proceedings of the 1992 ACM/IEEE Conference on Supercomputing, Minneapolis, MN, USA, 1992, pp. 512 – 521.
[8]	Hamidzadeh, B.; Kit, L. Y.; Lilja, D. J.: Dynamic task scheduling using online optimization, IEEE trans. Parallel distributed systems 11, No. 11, 1151-1163 (2000)
[9]	E. Ilavarasan, P. Thambidurai, R. Mahilmannan, Performance effective task scheduling algorithm for heterogeneous computing system, in: Proceedings of the Fourth International Symposium on Parallel and Distributed Computing, France, 2005, pp. 28 – 38.
[10]	M. Iverson, F. Ozguner, G. Follen, Parallelizing existing applications in a distributed heterogeneous environment, in: Proceedings of the Fourth Heterogeneous Computing Workshop, 1995, pp. 93 – 100.
[11]	J. Kim, J. Rho, J.-O. Lee, M.-C. Ko, CPOC: effective static task scheduling for grid computing, in: Proceedings of the 2005 International Conference on High Performance Computing and Communications, Italy, 2005, pp. 477 – 486.
[12]	S.J. Kim, J.C. Browne, A general approach to mapping of parallel computation upon multiprocessor architectures, in: Proceedings of the International Conference on Parallel Processing, Pennsylvania State University, University Park, PA, USA, 1988, pp. 1 – 8.
[13]	Kwok, Y. K.; Ahmad, I.: Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessors, IEEE trans. Parallel distributed systems 7, No. 5, 506-521 (1996)
[14]	Kwok, Y. K.; Ahmad, I.: Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM comput. Surveys 31, No. 4, 406-471 (1999)
[15]	El-Rewini, H.; Lewis, T. G.: Scheduling parallel program tasks onto arbitrary target machines, J. parallel distributed comput. 9, No. 2, 138-153 (1990) · Zbl 0861.90072
[16]	Sih, G. C.; Lee, E. A.: A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architectures, IEEE trans. Parallel distributed systems 4, No. 2, 175-187 (1993)
[17]	Topcuoglu, H.; Hariri, S.; Wu, M. Y.: Performance-effective and low-complexity task scheduling for heterogeneous computing, IEEE trans. Parallel distributed systems 13, No. 3, 260-274 (2002)
[18]	Wu, M.; Dajski, D.: Hypertool: a programming aid for message passing systems, IEEE trans. Parallel distributed systems 1, No. 3, 330-343 (1990)
[19]	Yang, T.; Gerasoulis, A.: DSC: scheduling parallel tasks on an unbounded number of processors, IEEE trans. Parallel distributed systems 5, No. 9, 951-967 (1994)
[20]	Zomaya, A.; Ward, C.; Macey, B.: Genetic scheduling for parallel processor systems: comparative studies and performance issues, IEEE trans. Parallel distributed systems 10, No. 8, 795-812 (1999)