Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing
| Autor: | Hans Vandierendonck, Mohsen Koohi Esfahani, Peter Kilpatrick |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Sparse Matrix-Vector Multiplication
Computer science Locality High Performance Computing Sparse matrix-vector multiplication Graph Algorithms Degree distribution Vertex (geometry) Tree traversal Graph traversal Locality of reference Multiplication Graph Traversal Memory Locality Algorithm MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Koohi Esfahani, M, Kilpatrick, P & Vandierendonck, H 2021, Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing . in 50th International Conference on Parallel Processing (ICPP 2021): Proceedings ., 42, Association for Computing Machinery, New York, NY, USA . https://doi.org/10.1145/3472456.3472462 ICPP |
| Popis: | 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/ |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|