Hybrid static/dynamic scheduling for already optimized dense matrix factorization

Résumé : Nous présentons une nouvelle stratégie d'ordonnancement hybride statique/dynamique du graphe de dépendance de tâches pour les méthodes directes utilisées en algèbre linéaire numérique dense. Cette stratégie offre un équilibre entre la localité de données, l'équilibrage de la charge des processors et la réduction de la charge de l'ordonnanceur de taches. Nous montrons que l'utilisation de cette technique d'ordonnancement appliquée aux algorithmes de réduction de communications pour la factorisation des matrices denses conduit à des gains de performance significatifs. Sur une machine NUMA AMD opteron disposant de 48 cores, nos expériences montrent que nous pouvons atteindre des gains de performance de 64% par rapport à la version de CALU qui utilise un ordonnancement statique, et jusqu'à 30% par rapport à un ordonnancement dynamique. Sur une machine Intel Xeon disposant de 16 cores, notre approche est jusqu'à 8% plus rapide que la version de CALU qui utilise un ordonnancement statique ou dynamique. Notre algorithme montre des améliorations importantes par rapport aux fonctions correspondantes à factorisation LU dans les libraires bien connus. Sur la machine AMD ayant 48 cores, la meilleur implémentation est jusqu'à 110% plus rapide que MKL, tandis que sur la machine Intel xeon ayant 16 cores, elle est jusqu'à 82% plus rapide que MKL. Notre approche montre aussi des accélérations significatives par rapport à PLASMA sur les deux machines.
Type de document :
Rapport
[Research Report] RR-7775, INRIA. 2011, pp.29
Liste complète des métadonnées

https://hal.inria.fr/inria-00631348
Contributeur : Simplice Donfack <>
Soumis le : jeudi 20 octobre 2011 - 14:09:48
Dernière modification le : mardi 24 avril 2018 - 13:51:42
Document(s) archivé(s) le : samedi 21 janvier 2012 - 02:26:56

Fichier

RR-7775.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00631348, version 2

Collections

Citation

Simplice Donfack, Laura Grigori, William D. Gropp, Vivek Kale. Hybrid static/dynamic scheduling for already optimized dense matrix factorization. [Research Report] RR-7775, INRIA. 2011, pp.29. 〈inria-00631348v2〉

Partager

Métriques

Consultations de la notice

592

Téléchargements de fichiers

598