La répartition des calculs et des données est le problème majeur à résoudre pour réaliser une application parallèle, son efficacité dépendant de la date et du lieu d'exécution des calculs sur l'ensemble des ressources, processeurs et mémoire, de la machine. Nous nous attachons à résoudre ce "problème d'ordonnancement". Nous utilisons pour cela un modèle proposé récemment : les tâches malléables. Après une introduction au domaine du parallélisme, nous présentons les principaux défauts d'autres modèles d'exécution, notamment leur modélisation fine du comportement des échanges de données, ce qui rend leur manipulation complexe. Les problèmes d'ordonnancement qui en résultent nous semblent difficiles à résoudre efficacement. Le modèle des tâches malléables considère une application comme un ensemble de tâches parallèles, chacune étant exécutée simultanément par plusieurs processeurs. La modélisation d'une application reste classique, en graphe de tâches, mais les communications ne sont prises en compte que de manière implicite, dans le temps d'exécution de chaque tâche malléable. Nous pensons que cette approche simplifie le problème d'ordonnancement à la fois théorique et pratique. Dans ce mémoire, nous abordons d'abord l'ordonnancement de tâches malléables indépendantes. Nous présentons quelques travaux déjà connus dont nous analysons les déficiences. Nous proposons un algorithme en deux étagères avec une meilleure garantie de performance de 3/2. Une comparaison en moyenne des différents algorithmes est également présentée. Pour les problèmes incluant des contraintes de précédences, nous présentons d'abord les résultats existants dans des modèles proches avant de proposer une première étude du problème des chaînes de tâches malléables. Enfin, après une introduction au domaine de la simulation adaptative de courants océaniques, l'utilisation pratique du modèle pour l'ordonnancement d'une simulation est également présentée.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00006094 |
| Date | 26 June 2000 |
| Creators | Mounié, Grégory |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0076 seconds