STS-k: A Multilevel Sparse Triangular Solution Scheme for NUMA Multicores

Abstract : We consider techniques to improve the performance of parallel sparse triangular solution on non-uniform memory architecture multicores by extending earlier coloring and level set schemes for single-core multiprocessors. We develop STS-k, where k represents a small number of transformations for la-tency reduction from increased spatial and temporal locality of data accesses. We propose a graph model of data reuse to inform the development of STS-k and to prove that computing an optimal cost schedule is NP-complete. We observe significant speed-ups with STS-3 on 32-core Intel Westmere-Ex and 24-core AMD 'MagnyCours' processors. Incremental gains solely from the 3-level transformations in STS-3 for a fixed ordering, correspond to reductions in execution times by factors of 1.4(Intel) and 1.5(AMD) for level sets and 2(In-tel) and 2.2(AMD) for coloring. On average, execution times are reduced by a factor of 6(Intel) and 4(AMD) for STS-3 with coloring compared to a reference implementation using level sets.
Type de document :
Communication dans un congrès
Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2015, Austin, TX, USA, November 15-20, 2015, Nov 2015, Austin, United States. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2015, Austin, TX, USA, November 15-20, 2015, pp.11, 2015, 〈10.1145/2807591.2807667〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01251937
Contributeur : Equipe Roma <>
Soumis le : lundi 11 janvier 2016 - 11:09:46
Dernière modification le : samedi 21 avril 2018 - 01:27:26
Document(s) archivé(s) le : mardi 12 avril 2016 - 10:59:38

Fichier

scHAL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Humayun Kabir, Joshua Booth, Guillaume Aupy, Anne Benoit, Yves Robert, et al.. STS-k: A Multilevel Sparse Triangular Solution Scheme for NUMA Multicores. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2015, Austin, TX, USA, November 15-20, 2015, Nov 2015, Austin, United States. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, 2015, Austin, TX, USA, November 15-20, 2015, pp.11, 2015, 〈10.1145/2807591.2807667〉. 〈hal-01251937〉

Partager

Métriques

Consultations de la notice

293

Téléchargements de fichiers

63