Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing
Exploiting in-Hub Temporal Locality in SpMV-based Graph Processing
复制标题
DOI：
10.1145/3472456.3472462
复制
发表时间：
2021-08
期刊：
影响因子：
--
通讯作者：
Mohsen Koohi Esfahani;Peter Kilpatrick;Hans Vandierendonck
中科院分区：
文献类型：
--
作者：
Mohsen Koohi Esfahani;Peter Kilpatrick;Hans Vandierendonck
真实世界图的倾斜度分布是遍历图的所有边时局部性差的主要来源，称为稀疏矩阵向量（SpMV）乘法。传统的图遍历方法，如推和拉，遍历所有顶点以相同的方式，我们显示应用一个统一的遍历方向的所有边缘导致次优的内存局部性，因此效率低下。本文认为幂律图的不同顶点具有不同的局部性，遍历方法应适应这些特性。为了解决这个问题，我们建议检查的目的地和源顶点的数量，在选择一个高速缓存兼容的遍历方向为每种类型的顶点。我们介绍了在集线器的时间局部性（iHTL），一个结构感知的SpMV，结合推和拉在一个图遍历，但不同的顶点类型。iHTL通过在推方向上将传入边缘遍历到入枢纽，同时在拉方向上处理其他边缘来利用时间局部性。测试结果显示，iHTL在GraphGrind、GraphIt和Galois等最先进的图形处理框架中，比pull快1.5 × - 2.4 ×，比push快4.8 × - 9.5 ×。更重要的是，iHTL比最先进的局部优化重排序算法（如SlashBurn，GOrder和Rabbit-Order）的pull遍历快1.3 - 1.5倍。
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 × faster than pull and 4.8 × - 9.5 × 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 × faster than pull traversal of state-of-the-art locality optimizing reordering algorithms such as SlashBurn, GOrder, and Rabbit-Order.