Ordonnancement avec communications pour architectures multiprocesseurs dans divers modèles d'exécution
Institution:
Grenoble INPGDisciplines:
Directors:
Abstract EN:
In few years, parallel computers have been designed and have been widely developped. The main technical problems have been solved and today, the crucial goal is to provide a framework, a parallel programming environment, in order to program these machines. This thesis is part of the IMAG APACHE project which aims at building such an environment. The graphs are DAGs (Directed Acyclic Graphs). The process leading to the parallelization of an application consists of three main steps, with the scheduling and mapping as the central phase. Within this context, we focus our study on the designing of efficient and adaptable scheduling strategies, in the case of various granularity and within various execution models. From an algorithm that provided optimal schedules for the case of UECT intrees (unit execution and communication time tasks) on two processors, we have shown that it was possible to yield near-optimal schedules for intrees with a ration computation/communications lower or greater than one. Moreover, the same algorithm provides, for given families of intrees, optimal schedules within a totally different execution model. This study on two processors is extended for the case of m (greater than two) identical processors and for two uniform processors. Finally, part of this work is dedicated to the study of scheduling strategies for the special graphs generated by Athapascan (APACHE project) for which the determination of the granularity can be done during the scheduling phase
Abstract FR:
En quelques dizaines d'années, l'informatique a vu naître et se développer des machines fonctionnant avec plusieurs processeurs. Les difficultés techniques rencontrées pour la conception de ces ordinateurs ont été surmontées et l'un des défis majeur d'aujourd'hui est de fournir une plateforme pour la programmation parallèle. Ce travail de thèse s'inscrit dans le cadre du projet IMAG APACHE qui a pour but la conception d'un tel environnement. Le modèle de graphes que nous manipulons est un graphe de tâches orienté sans cycle. Le processus consistant à paralléliser une application est découpé en trois phases principales, avec l'ordonnancement et le placement des différentes parties de l'application comme étape centrale. Dans ce contexte, nous avons concentrés nos efforts sur la recherche de stratégies d'ordonnancement présentant de réelles qualités de robustesse et d'efficacité pour des graphes de différentes granularités, et pour des ensembles d'hypothèses d'exécution différents. A partir d'un algorithme produisant des ordonnancements optimaux dans le cas de graphes à structure arborescente formés de tàches de durées unitaires et de communications unitaires, nous avons montré qu'il était possible d'obtenir des ordonnancements, dont l'écart par rapport à l'optimal est borné, pour des arbres de granularité différente. Nous avons montré également que ce même algorithme permettait d'obtenir dans certains cas des ordonnancements optimaux pour un modèle d'exécution totalement différent de celui pour lequel il avait été originellement conçu. Cette étude sur deux processeurs a été mené pour un nombre supérieur de processeurs identiques et pour deux processeurs uniformes. Enfin, une partie de ce travail est dédiée à la recherche de stratégies d'ordonnancement pour des graphes générés par l'environnement Athapascan (projet APACHE) qui présentent la particularité de permettre l'adaptation de la granularité en fonction de la machine cible