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

International audienceDans 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)