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

AUTOR(ES)
DATA DE PUBLICAÇÃO

2000

RESUMO

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 distincts. 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.

ASSUNTO(S)

operating systems gang scheduling ordonnancement parallèle ordonnancement gang parallel computation arquitetura de sistemas de computacao système d exploitation parallélisme parallel job scheduling coscheduling

ACESSO AO ARTIGO

Documentos Relacionados