LIP6 2001/003
- Soutenance de thèse
Modélisation et analyse d'une classe d'algorithmes d'ordonnancement pour Machines Parallèles - F. Alves Barbosa da Silva
- 156 pages - 01/12/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
- Mots clés : Ordonnancement Parallèle, Ordonnancement Gang, Parallélisme, Coscheduling, Système d'exploitation
- Directeur de la publication : Francois.Dromard (at) nulllip6.fr
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.