Modélisation et analyse d'une classe d'algorithmes d'ordonnancement pour Machines Parallèles

F. Alves Barbosa da Silva

LIP6 2001/003: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 LIP6 / LIP6 research reports
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

Résumé : L'ordonnancement parallèle est un problème important dont la solution peut mener à améliorer sensiblement l'utilisation des ordinateurs parallèles modernes. Il est défini comme: "Etant donné un ensemble de tâches appartenant à plusieurs applications parallèles dans une machine parallèle, trouver une allocation spatiale et temporelle pour exécuter toutes les tâches efficacement". Une application parallèle constituée de plusieurs tâches peut apparaître à un instant donné, attendre que les ressources demandées soient disponibles, puis être exécutée. Les temps associés à la phase d'attente ainsi qu'a phase d'exécution sont dépendantes de l'algorithme d'ordonnancement et de la charge de travail. Dans la majeure partie de cette thèse, nous nous concentrons sur les algorithmes d'ordonnancement basés sur le "Gang scheduling", à savoir, un paradigme où toutes les tâches d'une même application parallèle sont regroupées et ordonnancées de manière concurrente sur des processeurs distints. Les raisons de considérer l'ordonnancement Gang sont le partage efficace des ressources et la facilité de programmation. L'utilisation du partage de temps parmi les processeurs permet une dégradation graduelle de la performance à mesure que la charge de travail augmente. Les performances des applications parallèles très synchronisées sont fortement améliorées par rapport à un ordonnancement non coordonné. Cette thèse est divisée en deux parties distinctes : dans la première partie, on présente l'algorithme d'ordonnancement Gang, en identifiant ses avantages et ses faiblesses, puis on effectue une analyse théorique de l'algorithme Gang et des stratégies d'empaquetage. La deuxième partie présente des nouvelles méthodes d'ordonnancement dans une machine parallèle, s'appuyant sur des mesures dynamiques effectuées au moment de l'exécution. Dans cette partie, nous proposons un nouvel algorithme d'ordonnancement parallèle nommé _Concurrent Gang_, qui utilise des informations dynamiques obtenues sur les tâches au moment de l'exécution, en vue d'améliorer la performance de l'ordonnanceur parallèle.

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.

Mots-clés : Ordonnancement Parallèle, Ordonnancement Gang, Parallélisme, Coscheduling, Système d'exploitation

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