Algorithmes parallèles à grain adaptatif et applications
Nous proposons un schéma algorithmique générique original pour contrôler la granularité du parallélisme en cours d’exécution. Ce schéma est basé sur le couplage de deux algorithmes, l’un séquentiel, l’autre parallèle à grain fin. La génération de parallélisme n’est effectuée qu’en cas d’inactivité d’un processeur. Lors de l’exécution sur un nombre restreint ou
variable de ressources, ce schéma permet de limiter le surcoût lié à la génération de parallélisme, sans limiter le degré de parallélisme potentiel. Il est adapté aux problèmes pour lesquels la parallélisation entraîne, malgré un gain de temps, une pénalité en nombre d’opérations ou en performance. Nous l’appliquons à la parallélisation de deux applications : gzip (Gailly, 2003)
qui implémente la méthode de compression de Lempel-Ziv, problème P-complet considéré difficilement parallélisable ; et PL (ProBayes, n.d.) un moteur d’inférence probabiliste.
To tune granularity of tasks at runtime, we introduce an original algorithmic scheme. It is based on the coupling of two algorithms, one sequential, the other one parallel and fine grain. However, parallelism is generated only in case of idleness of some processor. Then, when executing the program on a limited number of resources, the overhead related to parallelism management is bounded with no restriction of potential parallelism. It is especially suited to applications for which parallelization drastically increases the number of operations or induces a loss of performance, despite a decreasing execution time. This scheme is applied to parallelisation of two applications: gzip (Gailly, 2003) that implements Lempel-Ziv compression, a P -complete problem; and PL (ProBayes, n.d.) a probabilistic inference engine.
E.DAOUDI, T.GAUTIER, A.KERFALI, R.REVIRE, J.ROCH
algorithmique, parallélisme, ordonnancement glouton, vol de travail.
algorithmic, parallelism, greedy schedule, work stealing.
Français
|
