Hybrid static/dynamic scheduling for already optimized dense matrix factorization
Résumé
We present the use of a hybrid static/dynamic scheduling strategy of the task dependency graph for direct methods used in dense numerical linear algebra. This strategy provides a balance of data locality, load balance, and low dequeue overhead. We show that the usage of this scheduling in communication avoiding dense factorization leads to significant performance gains. On a 48 core AMD Opteron NUMA machine, our experiments show that we can achieve up to 64% improvement over a version of CALU that uses fully dynamic scheduling, and up to 30% improvement over the version of CALU that uses fully static scheduling. On a 16-core Intel Xeon machine, our hybrid static/dynamic scheduling approach is up to 8% faster than the version of CALU that uses a fully static scheduling or fully dynamic scheduling. Our algorithm leads to speedups over the corresponding routines for computing LU factorization in well known libraries. On the 48 core AMD NUMA machine, our best implementation is up to 110% faster than MKL, while on the 16 core Intel Xeon machine, it is up to 82% faster than MKL. Our approach also shows significant speedups compared with PLASMA on both of these systems.
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.
Origine : Fichiers produits par l'(les) auteur(s)