Equilibre de charge dynamique : étude et mise en œuvre dans le cadre des applications à nombre fini de tâches indépendantes et irrégulières
Institution:
MetzDisciplines:
Directors:
Abstract EN:
Parallelism allows the use of several processors simultaneously to solve a given problem more quickly. However, to increase the power of the machine by the number of processors is an ideal which is in general very difficult to reach, because if the task allocation is not optimized, the performances of the program will be reduced. The placement of these tasks is one of the principal problems of parallelism. In this work, we study a toolkit helping the parallelization of the FIIT applications (applications with a finite number of independent and irregular tasks). The result of this toolkit is a first parallel solution which dynamically solves the problem of load balancing. The FIIT toolkit proposes various tools to the user such as : five MIMD load balancing strategies, a mathematical model based on matrix to validate the algorithms theoretically and an environment of programming on a virtual parallel machine. To illustrate the FIIT toolkit, we consider the ray tracing as case study. We showed the irregular character of the ray tracing. In particular, we highlighted that the behaviour of the application is strongly dependent on the scene to visualize. Using the FIIT environment, we parallelized it and an experimental analysis on a CM-5 was carried out. The FIIT toolkit enabled us to parallelize the ray tracing application efficiently without worrying about the target machine nor the dynamic load balancing strategy applied.
Abstract FR:
Le parallélisme permet l'utilisation simultanée de plusieurs processeurs pour résoudre plus rapidement un problème. Cependant, multiplier la puissance de la machine par le nombre de processeurs est un idéal qui est en général très difficile à atteindre, car si la répartition des taches n'est pas optimisée, les performances du programme seront réduites. Le placement de ces tâches est un des problèmes principaux du parallélisme. Dans ce travail, nous étudions un environnement d'aide à la parallélisation pour les applications FTII (applications à nombre Fini de Tâches Indépendantes et Irrégulières). Cet environnement propose une première solution parallèle qui résout dynamiquement le problème d'équilibre de charge. L'environnement FTII met à la disposition de l'utilisateur différents outils dont : cinq algorithmes MIMD d'équilibre de charge dynamique, un modèle mathématique basé sur les matrices pour valider les algorithmes théoriquement et un environnement de programmation sur une machine parallèle virtuelle. Pour illustrer l'environnement FTII, nous considérons le lancer de rayons comme étude de cas. Nous avons montré le caractère irrégulier du lancer de rayons. En particulier, nous avons mis en évidence la dépendance existante entre le comportement de l'application et la scène à visualiser. A l'aide de l'environnement FTII, nous avons parallélisé le lancer de rayons et une analyse expérimentale sur CM-5 a été menée. L'environnement FTII, nous a permis de paralléliser efficacement le lancer de rayons sans se soucier de la machine cible ni de la stratégie d'équilibre de charge dynamique appliquée.