Cache-Friendly Data Layout for Massive Graph
Cache-Friendly Data Layout for Massive Graph
复制标题
DOI：
10.1109/nas.2018.8515737
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
Yuxiang Shan;Zhan Shi;D. Feng;Ouyang Mengyun;F. Wang
中科院分区：
文献类型：
--
作者：
Yuxiang Shan;Zhan Shi;D. Feng;Ouyang Mengyun;F. Wang
存储层次结构被广泛用于经济地缓解不同存储组件之间的巨大性能差距，而该高速缓存在提高存储访问效率方面起着重要作用。然而，传统的图计算框架的内存中的数据组织并没有很好地优化各种缓存，特别是CPU缓存，因为经典的缓存是无效的不规则的访问模式的图应用程序。本文提出了一种缓存友好的图形数据布局策略，以提高图形处理的效率.在不改变图形处理工具代码的前提下，综合考虑缓存线参数和对相邻链表的访问模式，对边进行排序，生成顺序布局，并采用广度优先搜索（BFS）算法对顶点进行重新排序，提高局部性，从而提高CPU缓存效率。排序布局的效率提高范围从11%到78.76%的BGL和SNAP与CC（连接组件[1]）。BFS布局可以使GraphChi上的3种经典算法受益：CC，TC（Triangle Counting）和PageRank [2]，比例为15%-20%。
Storage hierarchy is widely used to mitigate the vast performance gap between different storage components economically, and the cache plays an important role in increasing the efficiency of memory access. However, the in-memory data organization of traditional graph computing framework is not well-optimized for various caches, especially the CPU cache, since classical caches are effectiveless towards irregular access pattern of graph applications. This work presents a cache- friendly graph data layout strategy to improve the efficiency of graph processing. By both considering the parameters of cache line and the pattern of access to adjacent list, we sort the edges to generate a sequential layout, and use BFS (Breadth First Search) algorithm to reorder the vertices for improving locality, thus benefit the CPU cache, without altering the code of graph processing toolkits. The efficiency improvement of Sort layout ranges from 11% up to 78.76% on BGL and SNAP with CC (Connected Components [1]). The BFS layout can benefit 3 classical algorithms on GraphChi: CC, TC (Triangle Counting) and PageRank [2], with the ratios of 15%–20%.