THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 /
156 pages - Décembre/December 2000 - French document.
Get it : 813 Ko /Kb
Contact : par mail / e-mail
Thème/Team: Architecture des Systèmes Intégrés et Micro-Électronique
Titre français : Modélisation et analyse d'une classe d'algorithmes d'ordonnancement pour Machines Parallèles
Titre anglais : Modeling and analysis of a class of scheduling algorithms for concurrent computing
Abstract : 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.
Key-words : Parallel Job Scheduling, Gang Scheduling, Parallel Computation, Coscheduling, Operating Systems
Publications internes LIP6 2001 / LIP6 research reports 2001
Responsable Éditorial / Editor :Francois.Dromard@lip6.fr