Spatiotemporal Graph and Hypergraph Partitioning Models for Sparse Matrix-Vector Multiplication on Many-Core Architectures

Nabil Abubaker, Kadir Akbudak, Cevdet Aykanat*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


There exist graph/hypergraph partitioning-based row/column reordering methods for encoding either spatial or temporal locality 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.

Original languageEnglish (US)
Article number8432126
Pages (from-to)445-458
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number2
StatePublished - Feb 1 2019

Bibliographical note

Publisher Copyright:
© 2018 IEEE.


  • Intel Xeon Phi
  • Intel many integrated core architecture
  • Sparse matrix
  • bipartite graph model
  • data locality
  • graph model
  • graph partitioning
  • hypergraph model
  • hypergraph partitioning
  • sparse matrix-vector multiplication
  • spatial locality
  • temporal locality

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Spatiotemporal Graph and Hypergraph Partitioning Models for Sparse Matrix-Vector Multiplication on Many-Core Architectures'. Together they form a unique fingerprint.

Cite this