Abstract FR:

L'ordonnancement parallele est un probleme important dont la solution peut mener a ameliorer sensiblement l'utilisation des ordinateurs paralleles modernes. Il est defini comme : etant donne un ensemble de taches appartenant a plusieurs applications paralleles dans une machine parallele, trouver une allocation spatiale et temporelle pour executer toutes les taches efficacement. Une application parallele constituee de plusieurs taches peut apparaitre a un instant donne, attendre que les ressources demandees soient disponibles, puis etre executee. Les temps associes a la phase d'attente ainsi qu'a phase d'execution sont dependantes de l'algorithme d'ordonnancement et de la charge de travail. Quelques algorithmes d'ordonnancement exigent une attente dans une file d'attente jusqu'a ce que toutes les ressources necessaires deviennent disponibles (comme dans l'algorithme variable partitioning), alors que dans d'autres, comme les algorithmes bases sur le partage dans le temps, l'application parallele est executee presque immediatement. Dans la majeure partie de cette these, nous nous concentrons sur les algorithmes d'ordonnancement bases sur le gang scheduling, a savoir, un paradigme ou toutes les taches d'une meme application parallele sont regroupees et ordonnancees de maniere concurrente sur des processeurs distincts. Les raisons de considerer l'ordonnancement gang sont le partage efficace des ressources et la facilite de programmation. L'utilisation du partage de temps parmi les processeurs permet une degradation graduelle de la performance a mesure que la charge de travail augmente. Les performances des applications paralleles tres synchronisees sont fortement ameliorees par rapport a un ordonnancement non coordonne. Cette these est divisee en deux parties distinctes : dans la premiere partie, on presente l'algorithme d'ordonnancement gang, en identifiant ses avantages et ses faiblesses, puis on effectue une analyse theorique de l'algorithme gang et des strategies d'empaquetage. La deuxieme partie presente des nouvelles methodes d'ordonnancement dans une machine parallele, s'appuyant sur des mesures dynamiques effectuees au moment de l'execution. Dans cette partie, nous proposons un nouvel algorithme d'ordonnancement parallele nomme concurrent gang, qui utilise des informations dynamiques obtenues sur les taches au moment de l'execution, en vue d'ameliorer la performance de l'ordonnanceur parallele.