Exploiting Locality in Sparse Matrix-Matrix Multiplication on Many-Core Architectures

Exploiting spatial and temporal localities is investigated for efficient row-by-row parallelization of general sparse matrix-matrix multiplication (SpGEMM) operation of the form C=AB on many-core architectures. Hypergraph and bipartite graph models are proposed for 1D rowwise partitioning of matrix...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on parallel and distributed systems 2017-08, Vol.28 (8), p.2258-2271
Main Authors: Akbudak, Kadir, Aykanat, Cevdet
Format: Article
Language:English
Subjects:
Bipartite graph
bipartite graph model
Central processing units
computational hypergraph model
Computational modeling
Computer architecture
CPUs
Data locality
Data models
graph clustering
graph model
graph partitioning
hypergraph clustering
hypergraph partitioning
Instruction sets
Intel Xeon Phi
many-core architecture
Matrices (mathematics)
Microprocessors
Multiplication
Parallel processing
Reuse
Similarity
Sparse matrices
sparse matrix
sparse matrix-matrix multiplication
Sparsity
SpGEMM
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Exploiting spatial and temporal localities is investigated for efficient row-by-row parallelization of general sparse matrix-matrix multiplication (SpGEMM) operation of the form C=AB on many-core architectures. Hypergraph and bipartite graph models are proposed for 1D rowwise partitioning of matrix A to evenly partition the work across threads with the objective of reducing the number of B-matrix words to be transferred from the memory and between different caches. A hypergraph model is proposed for B-matrix column reordering to exploit spatial locality in accessing entries of thread-private temporary arrays, which are used to accumulate results for C-matrix rows. A similarity graph model is proposed for B-matrix row reordering to increase temporal reuse of these accumulation array entries. The proposed models and methods are tested on a wide range of sparse matrices from real applications and the experiments were carried on a 60-core Intel Xeon Phi processor, as well as a two-socket Xeon processor. Results show the validity of the models and methods proposed for enhancing the locality in parallel SpGEMM operations.
ISSN:1045-9219
1558-2183
DOI:10.1109/TPDS.2017.2656893