Un algorithme adaptatif optimal pour le calcul parallèle des préfixes - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

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

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

Domaines

Autre [cs.OH]
Fichier non déposé

Dates et versions

hal-00694537 , version 1 (04-05-2012)

Identifiants

  • HAL Id : hal-00694537 , version 1

Citer

Jean-Louis Roch, Daouda A. K. 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. ⟨hal-00694537⟩
153 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More