Download or read book Algorithmes d'approximation garantie pour l'ordonnancement de tâches written by Christophe Rapine and published by . This book was released on 1999 with total page 125 pages. Available in PDF, EPUB and Kindle. Book excerpt: Cette thèse est consacrée à l'étude des problèmes d'ordonnancement d'une application parallèle décrite par un graphe de précédence avec délais de communication. Les problèmes d'ordonnancement étant dans leur grande majorité NP-difficiles, nous présentons une approche par algorithmes d'approximation dont nous déterminons les garanties de performance par rapport à une solution optimale. L'objectif de l'ordonnancement est la minimisation du temps d'exécution de l'application. Afin de réduire l'impact des communications dans les performances des heuristiques, nous envisageons deux approches, par un regroupement préliminaire des tâches et par l'utilisation de la duplication. Pour le problème du regroupement nous proposons une extension de l'algorithme DSC construisant des suites itérées de regroupements linéaires, convergeant pour des structures simples de graphes vers la solution optimale. Nous proposons également un algorithme d'ordonnancement avec duplication de garantie 2 pour les problème à petits temps de communication sur un nombre limité de processeurs, basé sur un algorithme de liste. Pour les problèmes à grands temps de communication nous établissons le gain, mais aussi les limitations, de cette approche, en montrant que tout algorithme de liste avec duplication possède une garantie en Θ(√ρ), ρ désignant la granularité du graphe. Nous étudions finalement une généralisation du modèle d'exécution dans lequel chaque tâche, dite malléable, peut s'exécuter sur un nombre quelconque de processeurs. Un algorithme de garantie √3 est proposé pour l'ordonnancement de tâches malléables indépendantes. Nous concluons cette thèse par quelques perspectives sur l'ordonnancement dynamique dans ce modèle