ABSTRACT
E´cole normale supe´rieure de Lyon, Institut Universitaire de France, and Universite´ de Lyon
Fre´de´ric Vivien
INRIA and Universite´ de Lyon
In this chapter, we focus on the problem of scheduling a large and computeintensive application on parallel resources, typically organized as a masterworker platform. We assume that we can arbitrarily split the total work, or load, into chunks of arbitrary sizes, and that we can distribute these chunks to an arbitrary number of workers. The job has to be perfectly parallel, without any dependence between sub-tasks. In practice, this model is a reasonable relaxation of an application made up of a large number of identical, fine-grain parallel computations. Such applications are found in many scientific areas, like processing satellite pictures [14], broadcasting multimedia contents [2, 3], searching large databases [11, 10], or studying seismic events [12]. This model is known as the Divisible Load model and has been widespread by Bharadwaj et al. in [9]. Steady-State Scheduling, detailed in Chapter 7, is another relaxation, more sophisticated but well-suited to complex applications. In [15], Robertazzi shows that the Divisible Load model is a tractable approach, which applies to a great number of scheduling problems and to a large variety of platforms, such as bus-shaped, star-shaped, and even tree-shaped platforms.
