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 latency 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 (Intel) 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 :
Rapport
[Research Report] RR-8763, Penn State University; ENS Lyon; INRIA. 2015
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-01183904
Contributeur : Equipe Roma <>
Soumis le : mardi 11 août 2015 - 20:48:49
Dernière modification le : samedi 17 septembre 2016 - 01:36:37
Document(s) archivé(s) le : jeudi 12 novembre 2015 - 10:41:13

Fichier

rr-8763.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01183904, version 1

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. [Research Report] RR-8763, Penn State University; ENS Lyon; INRIA. 2015. 〈hal-01183904〉

Partager

Métriques

Consultations de la notice

355

Téléchargements de fichiers

151