Algorithmes parallèles auto-adaptatifs et applications
Institution:
Grenoble INPGDisciplines:
Directors:
Abstract EN:
This thesis focuses on the building of algorithms and parallel programs that obliviously adapts the execution platform (number of processors, speeds of processors,. . . ). The building that we propose is based on the technology developed in the Moais team; it consists on the recursive and dynamic coupling of two algorithms: one sequential that minimizes the work (the number of operations), but not the parallel time; one parallel that minimizes the depth (parallel time) on an unbounded number of resources, but not the work. The two algorithms are interleaved on-line based on a work-stealing schedule. The contribution of this thesis consists in a theoretical analysis of coupling (lower bound, asymptotic optimality in some cases), and a "generic" implementation of the coupling scheme witch is applied to several examples (new on-line adaptive parallel prefix computation, adaptive merging and sorting, adaptive parallelization of several STL algorithms). In this thesis, we also propose a new strict optimal parallel static algorithm for prefix computation.
Abstract FR:
Cette thèse porte sur la construction d'algorithmes et de programmes parallèles qui s'adapte automatiquement à la plate-forme d'exécution (nombre de processeurs, vitesses des processeurs,. . . ) et ce, de manière dynamique inconsciente (en anglais oblivious). La construction que nous proposons est basée sur la technologie développée au sein de l'équipe Moais consistant au couplage récursif et dynamique : d'un algorithme séquentiel (qui minimise le nombre d'opérations, mais pas le temps parallèle) ; et d'un algorithme parallèle à grain fin (qui minimise le temps parallèle sur un nombre non borné de ressources, mais pas le nombre d'opérations). Les deux algorithmes sont entrelacés à la volée par un ordonnancement à grain fin de type vol de travail. Outre une analyse théorique du couplage (borne inférieure, optimalité asymptotique), nous proposons une implantation " générique " que nous instancions sur différents exemples (un nouvel algorithme parallèle adaptatif de calcul des préfixes, algorithmes adaptatifs de fusion, de partition et tris, plusieurs algorithmes adaptatifs de la librairie standard C++). Dans cette thèse, nous proposons aussi un nouvel algorithme parallèle statique optimal du calcul des préfixes.