Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing

Research output: Chapter in Book/Report/Conference proceedingConference contribution

108 Downloads (Pure)

Abstract

The skewed degree distribution of real-world graphs is the main source of poor locality in traversing all edges of the graph, known as Sparse Matrix-Vector (SpMV) Multiplication. Conventional graph traversal methods, such as push and pull, traverse all vertices in the same manner, and we show applying a uniform traversal direction for all edges leads to sub-optimal memory locality, hence poor efficiency. This paper argues that different vertices in power-law graphs have different locality characteristics and the traversal method should be adapted to these characteristics.

To solve this problem, we propose to inspect the number of destination and source vertices in selecting a cache-compatible traversal direction for each type of vertex. We introduce in-Hub Temporal Locality (iHTL), a structure-aware SpMV that combines push and pull in one graph traversal, but for different vertex types. iHTL exploits temporal locality by traversing incoming edges to in-hubs in push direction, while processing other edges in pull direction.

The evaluation shows iHTL is 1.5-2.4 times faster than pull and 4.8-9.5 times faster than push in state-of-the-art graph processing frameworks such as GraphGrind, GraphIt and Galois. More importantly, iHTL is 1.3-1.5 times faster than pull traversal of state-of-the-art locality optimizing reordering algorithms such as SlashBurn, GOrder, and Rabbit-Order.

https://blogs.qub.ac.uk/GraphProcessing/exploiting-in-hub-temporal-locality-in-spmv-based-graph-processing/
Original languageEnglish
Title of host publication50th International Conference on Parallel Processing (ICPP 2021): Proceedings
Place of PublicationNew York, NY, USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages10
ISBN (Electronic)9781450390682
ISBN (Print)9781450390682
DOIs
Publication statusPublished - 09 Aug 2021

Keywords

  • High Performance Computing
  • Graph Traversal
  • Memory Locality
  • Graph Algorithms
  • Sparse Matrix-Vector Multiplication

Cite this