Scheduling Algorithms for new Emerging Applications

May, 29th - June, 2nd 2006, CIRM, Marseille, France

Scheduling applications with uncertainties on new computing platforms

SpeakerDenis Trystram

Co-authorsJonathan Pecero-Sanchez and Denis Trystram

The recent development of new parallel and distributed platforms based on the interconnection of a large number of standard components highly changed the landscape of the parallel processing field. The most important point for a more effective use of such systems is the management and optimization of the resources, particularly scheduling. It consists in allocating the tasks of a parallel program to the processors on the patform and to determine at what time they will start their execution. These new systems are characterized by many new features that should be taken into account for optimizing the performances. More than ever, the handled data are subject to uncertainties and-or disturbances. It is mostly impossible to have a precise prediction of the parameters of the scheduling problem.

In this talk, we propose to investigate several ways for dealing with uncertainties in scheduling algorithms. We first survey the different existing approaches and see how they can be interpreted and used in the context of cluster and grid computing. Then, we focus on partially on-line approaches which start from an initial solution computed with estimated data and correct it on-line depending on the value of actual data. We describe the principle of stabilization and we analyze a scheduling algorithm that is intrinsically stable (i.e. it is able absorb the bad effects of disturbances). Finally, it is compared experimentally to pure on-line algorithms.