ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 24/5 - 2005  - pp.505-524  - doi:10.3166/tsi.24.505-524
TITRE
Algorithmes parallèles à grain adaptatif et applications

RÉSUMÉ
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.


ABSTRACT
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.


AUTEUR(S)
El Mostafa DAOUDI, Thierry GAUTIER, Aicha KERFALI, Rémi REVIRE, Jean-Louis ROCH

MOTS-CLÉS
algorithmique, parallélisme, ordonnancement glouton, vol de travail.

KEYWORDS
algorithmic, parallelism, greedy schedule, work stealing.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (162 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier