Accelerating Graph Analytics by Utilising the Memory Locality of Graph Partitioning
Accelerating Graph Analytics by Utilising the Memory Locality of Graph Partitioning
复制标题
DOI：
10.1109/icpp.2017.27
复制
发表时间：
2017-09
期刊：
影响因子：
--
通讯作者：
Jiawen Sun;Hans Vandierendonck;Dimitrios S. Nikolopoulos
中科院分区：
文献类型：
--
作者：
Jiawen Sun;Hans Vandierendonck;Dimitrios S. Nikolopoulos
本文研究了如何在大规模共享内存系统上提高图结构分析的内存局部性。我们证明了一个图分区，其中一个顶点的所有在边缘放置在同一分区提高内存的局部性。然而，通过这种图划分实现性能改进带来了一些挑战，需要重新思考图算法和首选数据结构的分类。我们引入了中等密度边界的概念，这是一种对于位图表示足够密集的边界，但受益于索引图布局。使用三种类型的边界，和三个图形布局方案优化到每个边界类型，我们设计了一个边遍历算法，自主决定使用哪种类型。我们已经在一个基于Ligra的NUMA感知图分析框架中实现了我们的技术，并展示了比Ligra高达4.34×，比Polymer高达2.93×的加速比。
This paper investigates how to improve the memory locality of graph-structured analytics on large-scale shared memory systems. We demonstrate that a graph partitioning where all in-edges for a vertex are placed in the same partition improves memory locality. However, realising performance improvement through such graph partitioning poses several challenges and requires rethinking the classification of graph algorithms and preferred data structures. We introduce the notion of medium dense frontiers, a type of frontier that is sufficiently dense for a bitmap representation, yet benefits from an indexed graph layout. Using three types of frontiers, and three graph layout schemes optimized to each frontier type, we design an edge traversal algorithm that autonomously decides which type to use. The distinction of forward vs. backward graph traversal folds into this decision and need no longer be specified by the programmer.We have implemented our techniques in a NUMA-aware graph analytics framework derived from Ligra and demonstrate a speedup of up to 4.34× over Ligra and up to 2.93× over Polymer.