Scheduling Parallel Tasks: Approximation Algorithms

Pierre-Francois Dutot (1, 2) , Grégory Mounié (1, 2) , Denis Trystram (1, 2)

1 ID-IMAG - Informatique et Distribution
2 APACHE - Parallel algorithms and load sharing

Scheduling is a crucial problem in parallel and distributed processing. It consists of determining where and when the tasks of parallel programs will be executed. The design of parallel algorithms has to be reconsidered by the influence of new execution supports (namely, clusters of workstations, grid computing and global computing) which are characterized by a larger number of heterogeneous processors, often organized by hierarchical sub-systems. Parallel Tasks model (tasks that require more than one processor for their execution) has been introduced about 15 years ago as a promising alternative for scheduling parallel applications, especially in the case of slow communication media. The basic idea is to consider the application at a rough level of granularity (larger tasks in order to decrease the relative weight of communications). As the main difficulty for scheduling in actual systems comes from handling efficiently the communications, this new view of the problem allows us to consider them implicitly, thus leading to more tractable problems. We kindly invite the reader to look at the chapter of Maciej Drozdowski (in this book) for a detailed presentation of various kinds of Parallel Tasks in a general context and the survey paper from Feitelson et al. \\cite{Feitelsonsurvey} for a discussion in the field of parallel processing. Even if the basic problem of scheduling Parallel Tasks remains NP-hard, some approximation algorithms can be designed. A lot of results have been derived recently for scheduling the different types of Parallel Tasks, namely, Rigid, Moldable or Malleable ones. We will distinguish Parallel Tasks inside the same application or between applications in a multi-user context. Various optimization criteria will be discussed. This chapter aims to present several approximation algorithms for scheduling moldable and malleable tasks with a special emphasis on new execution supports.

Mots clés: Parallel Computing; Scheduling; Malleable Tasks; Moldable Tasks; Algorithms

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Pierre-Francois Dutot, Grégory Mounié, Denis Trystram. Scheduling Parallel Tasks: Approximation Algorithms. Joseph T. Leung. Handbook of Scheduling: Algorithms, Models, and Performance Analysis, CRC Press, pp.26-1 - 26-24, 2004, chapter 26. ⟨hal-00003126⟩