@article{(Open Science Index):https://publications.waset.org/pdf/11646, title = {Performance Analysis of List Scheduling in Heterogeneous Computing Systems}, author = {Keqin Li}, country = {}, institution = {}, 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.}, journal = {International Journal of Computer and Information Engineering}, volume = {4}, number = {3}, year = {2010}, pages = {484 - 491}, ee = {https://publications.waset.org/pdf/11646}, url = {https://publications.waset.org/vol/39}, bibsource = {https://publications.waset.org/}, issn = {eISSN: 1307-6892}, publisher = {World Academy of Science, Engineering and Technology}, index = {Open Science Index 39, 2010}, }