Performance Analysis of List Scheduling in Heterogeneous Computing Systems

Authors: Keqin Li

Abstract:

Given a parallel program to be executed on a heterogeneous computing system, the overall execution time of the program is determined by a schedule. In this paper, we analyze the worst-case performance of the list scheduling algorithm for scheduling tasks of a parallel program in a mixed-machine heterogeneous computing system such that the total execution time of the program is minimized. We prove tight lower and upper bounds for the worst-case performance ratio of the list scheduling algorithm. We also examine the average-case performance of the list scheduling algorithm. Our experimental data reveal that the average-case performance of the list scheduling algorithm is much better than the worst-case performance and is very close to optimal, except for large systems with large heterogeneity. Thus, the list scheduling algorithm is very useful in real applications.

Keywords: Average-case performance, list scheduling algorithm, mixed-machine heterogeneous computing system, worst-case performance.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1077681

References:

[1] S. Ali, T. D. Braun, H. J. Siegel, and A. A. Maciejewski, "Heterogeneous computing," in Encyclopedia of Distributed Computing, J. Urbana and P. Dasgupta, eds., Kluwer Academic, Norwell, MA, 2001.
[2] T. D. Braun, H. J. Siegel, N. Beck, L. L. B¨ol¨oni, M. Maheswaran, A. I. Reuther, J. P. Robertson, M. D. Theys, B. Yao, D. Hensgen, and R. F. Freund, "A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous computing systems," Journal of Parallel and Distributed Computing, vol. 61, pp. 810-837, 2001.
[3] M. M. Eshaghian, ed., Heterogeneous Computing, Artech House, Norwood, MA, 1996.
[4] M. R. Garey and D. S. Johnson, Computers and Intractability - A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979.
[5] R. L. Graham, "Bounds on multiprocessing timing anomalies," SIAM J. Appl. Math., vol. 2, pp. 416-429, 1969.
[6] M. Kafil and I. Ahmad, "Optimal task assignment in heterogeneous distributed computing systems," IEEE Concurrency, vol. 6, no. 3, pp. 42-51, 1998.
[7] A. A. Khokhar, V. K. Prasanna, M. E. Shaaban, and C. L. Wang, "Heterogeneous computing: challenges and opportunities," Computer, vol. 26, no. 6, pp. 18-27, 1993.
[8] K. Li and J. E. Dorband, "A task scheduling algorithm for heterogeneous processing," Proceedings of the 5th High Performance Computing Symposium, pp. 183-188, 1997.
[9] M. Maheswaran, S. Ali, H. J. Siegel, D. Hensgen, and R. F. Freund, "Dynamic mapping of a class of independent tasks onto heterogeneous computing systems," Journal of Parallel and Distributed Computing, vol. 59, pp. 107-131, 1999.
[10] M. Maheswaran, T. D. Braun, and H. J. Siegel, "Heterogeneous distributed computing," in Encyclopedia of Electrical and Electronics Engineering, J. G. Webster, ed., Wiley, New York, pp. 679-690, 1999.
[11] H. J. Siegel and S. Ali, "Techniques for mapping tasks to machines in heterogeneous computing systems," Journal of Systems Architecture, vol. 46, pp. 627-639, 2000.
[12] H. J. Siegel, J. K. Antonio, R. C. Metzger, M. Tan, and Y. A. Li, "Heterogeneous computing," in Parallel and Distributed Computing Handbook, A. Y. Zomoya ed., McGraw-Hill, New York, pp. 725-761, 1996.
[13] H. J. Siegel, H. G. Dietz, and J. K. Antonio, "Software support for heterogeneous computing," in The Computer Science and Engineering Handbook, A. B. Tucker, Jr. ed., pp. 1886-1909, CRC Press, Boca Raton, FL, 1997.
[14] H. Topcuoglu, S. Hariri, and M.-Y. Wu, "Performance-effective and low-complexity task scheduling for heterogeneous computing," IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 3, pp. 260-274, 2002.