Spatiotemporal Graph and Hypergraph Partitioning Models for Sparse Matrix-Vector Multiplication on Many-Core Architectures
- 10 August 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 30 (2) , 445-458
Abstract
There exist graph/hypergraph partitioning-based row/column reordering methods for encoding either spatial or temporal locality separately for sparse matrix-vector multiplication (SpMV) operations. Spatial and temporal hypergraph models in these methods are extended to encapsulate both spatial and temporal localities based on cut/uncut net categorization obtained from vertex partitioning. These extensions of spatial and temporal hypergraph models encode the spatial locality primarily and the temporal locality secondarily, and vice-versa, respectively. However, the literature lacks models that simultaneously encode both spatial and temporal localities utilizing only vertex partitioning for further improving the performance of SpMV on shared-memory architectures. In order to fill this gap, we propose a novel spatiotemporal hypergraph model that leads to a one-phase spatiotemporal reordering method which encodes both types of locality simultaneously. We also propose a framework for spatiotemporal methods which encodes both types of locality in two dependent phases and two separate phases. The validity of the proposed spatiotemporal models and methods are tested on a wide range of sparse matrices and the experiments are performed on both a 60-core Intel Xeon Phi processor and a Xeon processor. Results show the validity of the methods via almost doubling the Gflop/s performance through enhancing data locality in parallel SpMV operations.Keywords
Funding Information
- The Scientific and Technological Research Council of Turkey TUBITAK (EEEAG-115E212)
This publication has 29 references indexed in Scilit:
- Hypergraph Partitioning Based Models and Methods for Exploiting Cache Locality in Sparse Matrix-Vector MultiplicationSIAM Journal on Scientific Computing, 2013
- Two-dimensional cache-oblivious sparse matrix–vector multiplicationParallel Computing, 2011
- Optimization of sparse matrix–vector multiplication on emerging multicore platformsParallel Computing, 2009
- Cache-Oblivious Sparse Matrix–Vector Multiplication by Using Sparse Matrix Partitioning MethodsSIAM Journal on Scientific Computing, 2009
- Efficient parallel Text Retrieval techniques on Bulk Synchronous Parallel (BSP)/Coarse Grained Multicomputers (CGM)The Journal of Supercomputing, 2008
- Benchmarking optimization software with performance profilesMathematical Programming, 2002
- Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplicationIEEE Transactions on Parallel and Distributed Systems, 1999
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular GraphsSIAM Journal on Scientific Computing, 1998
- Partitioning similarity graphs: A framework for declustering problemsInformation Systems, 1996
- QMR: a quasi-minimal residual method for non-Hermitian linear systemsNumerische Mathematik, 1991