Ordonnancement multiprocessurs et distribué temps réel

Dans cette thèse, nous considérons plusieurs problèmes d'ordonnancement par les calculs parallèles. Une application parallèle est représentée par un graphe de tâches acyclique (DAG). Les sommets représentent les tâches et les arcs les contraintes de précédance entre elles. Nos contributions s'inscrivent dans les trois volets suivants. Le premier problème étudié est l'ordonnancement des graphes de tâches dans les systèmes multiprocesseurs. Les graphes de tâches considérées sont quelconques, de graphes de grande taille et la durée des tâches/communications est arbitraire. Dans ce cadre, nous proposons deux algorithmes : 1-Un algorithme de regroupement(ordonnancement sur un nombre non borné de processeurs) efficace, basé sur la technique du chemin critique. Il est guidé par des règles d'ordonnancement qui permettent de réduire considérablement la consommation en processeurs. Dans le but de réduire la complexité temporelle de l'algorithme, la longueur du chemin critique est calculée d'une étape à une autre de façon incrémentale. 2-Un algorithme d'ordonnancement sur un nombre borné de processeurs. Cet algorithme a l'avantage, par rapport à ses compétiteurs, de réduire le choix, parmi les tâches candidates à l'ordonnancement de toutes à une seule et, sur l'ensemble des processeurs disponibles, de tous à deux. Cela nous permet d'avoir un algorithme à la fois rapide et performant comparé aux autres algorithmes connus dans ce domaine.Le deuxième problème traîté est l'ordonnancement dans les systèmes hétérogènes avec prise en compte de la fiabilité du système. Nous proposons une solution qui satisfait deux objectifs silmutanément. Le premier objectif consiste en la minimisation du makespan et le deuxième objectif consiste en la maximisation de la fiabilité du système. L'heuristique est validée par une série d'expérimentation et les résultats obtenus sont prometteurs. Enfin, nous nous sommes intéressés au problème d'ordonnancement en ligne des graphes de tâches dans les systèmes distribués temps-réel. Nous présentons un algorithme original sous des hypothèses réalistes (un réseau quelconque de taille arbitraire et des contraintes de dépendance entre tâches) où des graphes de tâches peuvent arriver concurrement et sporadiquement sur n'importe quel site et à n'importe quel moment. Cet algorithme est basé sur un nouveau concept : les sphères de calcul. Elles permettent de déterminer les voisins potentiels qui peuvent coopérer à l'exécution distribuée des graphes de tâches s'ils ne peuvent être garantis sur leurs sites d'origine. Cela permet une augmentation sensible du nombre de graphes garantis dans le système. Mots-clés : fiabilité, ordonnancement, regroupements, systèmes temps-réel, systèmes parallèles, systèmes distribués, graphes acycliques DAGs, ordonnancement bi-critères, systèmes hétérogènes.PARIS13-BU Sciences (930792102) / SudocSudocFranceF