Modélisation et analyse d'une classe d'algorithmes d'ordonnancement pour Machines Parallèles
- F. Alves Barbosa da Silva
- 156 pages - 12/01/2000- document en - http://www.lip6.fr/lip6/reports/2001/lip6.2001.003.pdf - 832 Ko
- Contact : fsilva (at) nullics.uci.edu
- Ancien Thème : ASIM
- Keywords : Parallel Job Scheduling, Gang Scheduling, Parallel Computation, Coscheduling, Operating Systems
- Publisher : Francois.Dromard (at) nulllip6.fr
Parallel job scheduling is an important problem whose solution may lead to better utilization of modern parallel computers. It is defined as: "Given the aggregate of all tasks of multiple jobs in a parallel system, find a spatial and temporal allocation to execute all tasks efficiently". For the purposes of scheduling, we view a computer as a queueing system. An arriving job may wait for some time, receive the required service, and depart. The time associated with the waiting and service phases is a function of the scheduling algorithm and the workload. Some scheduling algorithms may require that a job wait in a queue until all of its required resources become available (as in variable partitioning), while in others, like time slicing, the arriving job receives service immediately through a processor sharing discipline. In most of this thesis, we focus on scheduling based on Gang service, namely, a paradigm where all tasks of a job in the service stage are grouped into a Gang and concurrently scheduled in distinct processors. Reasons to consider Gang service are responsiveness, efficient sharing of resources and ease of programming. In Gang service the tasks of a job are supplied with an environment that is very similar to a dedicated machine. It is useful to any model of computation and any programming style. The use of time slicing allows performance to degrade gradually as load increases. Applications with fine-grain interactions benefit of large performance improvements over uncoordinated scheduling. This thesis is divided into two distinct parts: in the first part, we present the algorithm Gang scheduling, we identify its advantages and weaknesses, and we carry out a theoretical analysis of the Gang scheduling algorithm. The second part presents new methods to improve scheduling in a parallel machine based on runtime measurements at execution time. In this second part we propose a new parallel job scheduling algorithm named Concurrent Gang which uses the runtime information obtained on tasks at execution time in order to improve the performance of the parallel scheduler.