Colloquia / Seminars / Industry Talks

We analyze the average-case performance of an online non-clairvoyant scheduling algorithm called SIMPLE for independent parallel tasks. The algorithm schedules tasks without prior knowledge of the future tasks and the execution times of the tasks that are not yet completed. By using reasonable assumptions, we find an asymptotic average-case performance bound and develop a method to calculate the bound for arbitrary probability distribution of task sizes. In particular, we show that when task sizes are uniformly distributed in the range [1..C], an asymptotic average-case performance bound of M/(M-(3-(1+1/C)C+1)C-1) can be achieved, where M is the number of processors. We present extensive numerical and simulation data to demonstrate the accuracy of our analytical bound. We also evaluate the average-case performance of three approximation algorithms for online non-clairvoyant scheduling of parallel tasks with precedence constraints. We show that for a class of wide task graphs, when task sizes are uniformly distributed in the range [1..C], the online non-clairvoyant scheduling algorithm LL-SIMPLE has an asymptotic average-case performance bound of M/(M - (3 - (1 + 1/C)C+1)C - 1), where M is the number of processors. We report extensive experimental results on the average-case performance of online non-clairvoyant scheduling algorithms LL-GREEDY and LS. Algorithm LL-GREEDY has better performance than LL-SIMPLE by using an improved algorithm to schedule independent tasks in the same level. Algorithm LS produces even better schedules due to break of boundaries among levels.

Keqin Li received B.S. degree in computer science from Tsinghua University, China,in 1985, and Ph.D. degree in computer science from the University of Houston in 1990. He is currently a full professor of computer science in State University of New York at New Paltz and the chair of SUNY New Paltz’s Central Committee on Promotion and Salary Increase. Professor Li’s research interests are mainly in the areas of design and analysis of algorithms, parallel and distributed computing, and computer networking, with particular interests in approximation algorithms, parallel algorithms, job scheduling, task dispatching, load balancing, performance evaluation, scalability analysis, dynamic tree embedding, parallel computing using optical interconnects, optical networks, and wireless networks. He has over 200 research publications in various books, journals, and refereed international conference proceedings. He has received several Best Paper Awards for his highest quality work. His research has been supported by US National Science Foundation, US National Aeronautics and Space Admin istration, SUNY Research Foundation, and State of New York/United University Professions. Professor Li has served in various capacities for numerous international conferences as general chair, program chair, workshop chair, track chair, and steering/advisory/award/program committee member.