Le contexte général de ce travail est l'étude du comportement d'applications parallèles, représentées par un graphe de précédence. La programmation de telles applications dépend fortement des supports d'exécution. Nous présentons et discutons les principaux modèles d'exécution et leur influence sur les problèmes d'ordonnancement des tâches du programme parallèle. Nous étudions en détail quatre problèmes d'ordonnancement sur des modèles d'exécution où le coût de communication est pris en compte. Nous proposons une solution pour un problème à grain très fin, le problème du sac à dos, sur hypercube dans un modèle d'exécution synchrone où le coût de communication est implicite. Nous étudions l'ordonnancement de chaînes sur un modèle à gros grain de communication, le modèle BSP. Nous démontrons qu'ici la recherche d'un ordonnancement optimal est un problème NP-difficile. Nous proposons des solutions avec un compromis entre le nombre de phases de communication/synchronisation et le temps d'inactivité dans chaque processeur. Les deux derniers problèmes étudiés concernent des techniques qui permettent de réduire l'impact du coût des communications inter processeurs. La première technique considère la duplication des tâches. Nous proposons un algorithme de liste avec garantie de performance 2 pour les problèmes à petit temps de communication sur un nombre limité de processeurs. Le deuxième méthode consiste à optimiser les phases de communication en ordonnançant les transmissions de messages. La recherche de la solution optimale étant NP-difficile, nous proposons plusieurs heuristiques.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00004839 |
| Date | 17 November 1999 |
| Creators | Goldman, Alfredo |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0018 seconds