Computer Science Colloquium

Rapid improvements in network technologies made computer grids an efficient solution for computationally intensive applications. The relatively coarse grain meta-applications and the heterogeneous nature of the grid require efficient scheduling algorithms. The shared nature of the network and computers of the grid creates hazards, which can lead the applications to miss their estimated time to completion.

In this talk we present research results related to scheduling meta applications on a heterogeneous computer grid. We introduce static scheduling algorithms and compare their relative performance for different levels of heterogeneity of the network. Scheduling algorithms based on the min-min heuristic, genetic algorithms and tabu search will be presented. We will show that carefully chosen, relatively simple heuristics can approach the performance of complex iterative search algorithms.Next, we move to the topic of scheduling meta applications in the presence of hazards. We introduce the concept of robustness of schedules and several mathematical results about the behavior of different schedules in the presence of hazards. We show that the entropy of a schedule is a good measure of the robustness.

In two practical scenarios, we show how the robustness analysis can be used to a) minimize the number of resource reservations needed for a particular meta-program and b) reduce the average execution time by enhancing aniterative scheduling algorithm to select the most robust schedule from a class of iso-schedules. We conclude by evaluating the impact of meta-program scheduling on computer grids and identifying goals for future research.

Ladislau Bölöni is infrastructure architect and designer of the MPLS traffic engineering product at CPlane Inc, Sunnyvale, CA. He received a PhD in Computer Science from Purdue University in May 2000, MSc degree from the Computer Sciences from Purdue University and BS degree with Honors in Computer Engineering from the Technical University of Cluj-Napoca, Romania. He was a visiting researcher at Neurological Computing Lab of the Hungarian Academy of Sciences for the 1994-95 academic year. He is a member of ACM, IEEE and the Upsilon Pi Epsilon honorary society. His research interests include distributed computing, autonomous agents and internet traffic optimization. He has authored over 25 research papers and book chapters, and a programming book.