Algorithmes parallegrave;les auto-adaptatifs et applications课件.ppt

Algorithme adaptatif du calcul parallèle des préfixes (6/7): validation expérimentale Taille des données : n= 104, temps d’une opération ≈ 2ms Temps [s] Nombre de processeurs 38/52 Dix Machines de fréquences différentes AMD Opteron processeur fréquence 1 1760 Mhz 2 550 Mhz 3 1100 Mhz 4 1650 Mhz 5 660 Mhz 6 440 Mhz 7 1320 Mhz 8 880 Mhz 9 550 Mhz 10 1760 Mhz [Simulateur CpuBurning /Cérin] Nombre de processeurs accélération 39/52 Algorithme adaptatif du calcul parallèle des préfixes (7/7): validation expérimentale Taille des données : n=5120000, temps d’une opération ≈ 1ms 8 Machines distribuées AMD Opteron [accès des données paginé via mmap] Algorithmes pour processeurs identiques: illustration sur le calcul parallèle des préfixes Ordonnancement par vol de travail Schéma générique adaptatif Algorithme adaptatif pour le calcul parallèle des Préfixes Application du schéma à la STL Conclusion et perspectives 40/52 Plan de la présentation Applications du schéma à la librairie standard C++ La librairie STL (Standard Template Library) : Fournit : conteneurs, algorithmes, itérateurs Avantage : généricité Parallélisation de la STL PSTL (Parallel Standard Template Library) [Johnson et al 97] STAPL (Standard Adaptive Parallel Libary) [Thomas et al 88 ] MPTL (Multi-Processing Template Library) [Baertschiger 06 ] MCSTL (Multi-Core Standard Template Library) [Singler et al 07 ] Intel TBB (Thread Building Blocks) [Reinders 07] PaSTeL [Saule Videau, RENPAR’08] KASTL (Kaapi Adaptive Standard Template Library) Implémenté sur le noyau exécutif kaapi Basé le schéma adaptatif 41/52 Applications du schéma à la librairie standard C++ Classe Algorithmes implémentés Algorithmes sans fusion de résultats copy, copy_bacward, fill, fill_n, for_each, generate, generate_n, replace, replace_if, replace_copy, replace_copy_if, swap_ranges, transform Algorithmes avec fusion