Locality Analysis of Graph Reordering Algorithms
Locality Analysis of Graph Reordering Algorithms
复制标题
DOI：
10.1109/iiswc53511.2021.00020
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Mohsen Koohi Esfahani;Peter Kilpatrick;Hans Vandierendonck
中科院分区：
文献类型：
--
作者：
Mohsen Koohi Esfahani;Peter Kilpatrick;Hans Vandierendonck
处理真实世界图的一个主要挑战源于内存访问的局部性差，已经提出了顶点重排序算法（RA）来通过改变内存访问的顺序来提高局部性。虽然SlashBurn、GOrder和Rabbit-Order等最先进的RA有效地加速了图算法，但它们的功能和缺点尚未完全了解，主要有三个原因：（1）数据集的大小，（2）缺乏合适的测量工具，以及（3）图的不同特征。缺乏分析也阻碍了更有效的监管机构的设计。本文通过引入一些工具来打开这个黑匣子，包括：（1）用于处理大型图的高速缓存模拟技术，（2）作为空间局部性度量的邻居到邻居平均ID距离（N2 N AID），（3）模拟的高速缓存未命中率和AID的度分布，以研究RA如何影响不同顶点的局部性，以及（4）“有效高速缓存大小”，以测量有多少高速缓存容量用于支持随机访问。我们引入（1）不对称度分布，（2）度范围分解，（3）推拉局部性，通过解释它们在面对RA时的对比行为，对不同类型的现实世界图进行结构分析。最后，我们提出了一些改进的RA使用本文提供的分析。
A major challenge in processing real-world graphs stems from poor locality of memory accesses and vertex reordering algorithms (RAs) have been proposed to improve locality by changing the order of memory accesses. While state-of-the-art RAs like SlashBurn, GOrder, and Rabbit-Order effectively speed up graph algorithms, their capabilities and disadvantages are not fully understood, mainly, for three reasons: (1) the large size of datasets, (2) the lack of suitable measurement tools, and (3) disparate characteristics of graphs. The paucity of analysis has also inhibited the design of more efficient RAs. This paper unlocks this black box by introducing a number of tools, including: (1) a cache simulation technique for processing large graphs, (2) the Neighbour to Neighbour Average ID Distance (N2N AID) as a spatial locality metric, (3) the degree distributions of simulated cache miss rate and AID to investigate how locality of different vertices is affected by RAs, and (4) “effective cache size” to measure how much of cache capacity is used to support random accesses. We introduce (1) asymmetricity degree distribution, (2) degree range decomposition, and (3) push and pull locality to present a structural analysis of different types of real-world graphs by explaining their contrasting behaviours in confronting RAs. Finally, we propose a number of improvements for RAs using the analysis provided in this paper.