Un algorithme adaptatif optimal pour le calcul parallèle des préfixes

Jean-Louis Roch 1 Daouda Traoré 1
1 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes, UJF - Université Joseph Fourier - Grenoble 1
Résumé : Dans cet article, nous proposons un nouvel algorithme parallèle de calcul des préfixes pour des processeurs dont la vitesse ou le nombre peut varier en cours d'exécution. Basé sur le couplage récursif d'un algorithme séquentiel optimal et d'un algorithme parallèle non optimal mais récursif à grain fin, il exploite un ordonnancement dynamique de type vol de travail (Cilk, Kaapi). Sa performance théorique est analysée sur p processeurs à vitesses variables, de vitesse moyenne ¦ave. Bien que cet algorithme adaptatif est indépendant du nombre de processeurs, son temps d'exécution est équivalent à 2n ¦ave.(p+1) , ce qui est optimal si les processeurs sont identiques (i.e. ¦ave = 1). Expérimentalement, cet algorithme adaptatif est comparé à un algorithme optimal pour un nombre fixé p de processeurs identiques avec ordonnancement statique optimal sur une machine SMP octoprocesseurs. Même pour des petites valeurs de n (100) et de p (de 1 à 8), ses performances sont analogues dans le cas où les processeurs sont dédiées au calcul, et il est beaucoup plus rapide dans le cas général où la machine exécute concuremment d'autres processus (cas multi-utilisateurs).
Type de document :
Communication dans un congrès
8ème colloque Africain sur la recherche en Informatique, Nov 2006, Cotonou, Bénin. 2006, 〈http://www.cari-info.org/arch_actes_cari2006.htm〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00694537
Contributeur : Ist Rennes <>
Soumis le : vendredi 4 mai 2012 - 15:55:04
Dernière modification le : mercredi 11 avril 2018 - 01:55:02

Identifiants

  • HAL Id : hal-00694537, version 1

Collections

Citation

Jean-Louis Roch, Daouda Traoré. Un algorithme adaptatif optimal pour le calcul parallèle des préfixes. 8ème colloque Africain sur la recherche en Informatique, Nov 2006, Cotonou, Bénin. 2006, 〈http://www.cari-info.org/arch_actes_cari2006.htm〉. 〈hal-00694537〉

Partager

Métriques

Consultations de la notice

196