Semi-two-dimensional partitioning for parallel sparse matrix-vector multiplication

Abstract : We propose a novel sparse matrix partitioning scheme, called semi-two-dimensional (s2D), for efficient paral-lelization of sparse matrix-vector multiply (SpMV) operations on distributed memory systems. In s2D, matrix nonzeros are more flexibly distributed among processors than one dimensional (rowwise or columnwise) partitioning schemes. Yet, there is a constraint which renders s2D less flexible than two-dimensional (nonzero based) partitioning schemes. The constraint is enforced to confine all communication operations in a single phase, as in 1D partition, in a parallel SpMV operation. In a positive view, s2D thus can be seen as being close to 2D partitions in terms of flexibility, and being close 1D partitions in terms of computation/communication organization. We describe two methods that take partitions on the input and output vectors of SpMV and produce s2D partitions while reducing the total communication volume. The first method obtains optimal total communication volume, while the second one heuristically reduces this quantity and takes computational load balance into account. We demonstrate that the proposed partitioning method improves the performance of parallel SpMV operations both in theory and practice with respect to 1D and 2D partitionings.
Type de document :
Communication dans un congrès
PCO2015 (IPDPSW), May 2015, Hyderabad, India. IEEE CPS, pp.1125--1134
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger
Contributeur : Equipe Roma <>
Soumis le : mercredi 3 juin 2015 - 15:40:37
Dernière modification le : vendredi 20 avril 2018 - 15:44:27
Document(s) archivé(s) le : mardi 25 avril 2017 - 00:02:23


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01159692, version 1



Enver Kayaaslan, Bora Uçar, Cevdet Aykanat. Semi-two-dimensional partitioning for parallel sparse matrix-vector multiplication. PCO2015 (IPDPSW), May 2015, Hyderabad, India. IEEE CPS, pp.1125--1134. 〈hal-01159692〉



Consultations de la notice


Téléchargements de fichiers