V-Combiner: speeding-up iterative graph processing on a shared-memory platform with vertex merging
V-Combiner: speeding-up iterative graph processing on a shared-memory platform with vertex merging
复制标题
DOI：
10.1145/3392717.3392739
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Azin Heidarshenas;Serif Yesil;Dimitrios Skarlatos;Sasa Misailovic;Adam Morrison;J. Torrellas
中科院分区：
文献类型：
--
作者：
Azin Heidarshenas;Serif Yesil;Dimitrios Skarlatos;Sasa Misailovic;Adam Morrison;J. Torrellas
迭代图算法在每次迭代中对图中的所有顶点应用顶点更新操作。对于大图，这种计算成本很高。然而，在实践中，并非所有更新都对最终结果有同等的贡献，事实上，可能不需要确切的结果。在这项工作中，我们利用这些见解来加速迭代图算法。我们提出了一种机制来识别不太重要的顶点并省略对它们的计算。我们的方案称为 V-Combiner，是一种确定性、快速且对应用程序透明的技术，用于构建近似图以实现更快的执行。 V-Combiner 背后的主要思想是将某些顶点合并到集线器中，这些顶点具有许多连接并对算法的最终结果做出很大贡献。我们还提出了一种廉价的校正步骤来恢复合并顶点的贡献以获得更高的精度。我们在 4 个不同的应用程序和 5 个数据集上评估 V-Combiner。对于 44 线程运行，V-Combiner 的平均端到端加速比传统系统提高了 1.25 倍，准确率达到 91.8%。与现有的稀疏化和 k 核技术相比，它还显示出更好的性能与准确性权衡。
An iterative graph algorithm applies a vertex update operation to all vertices in a graph in every iteration. For large graphs, this computation is costly. However, in practice, not all the updates contribute equally to the end result and, in fact, an exact result may not be needed. In this work, we leverage these insights to speed-up iterative graph algorithms. We propose a mechanism to identify the less important vertices and omit computations for them. Our scheme, called V-Combiner, is a deterministic, fast, and application-transparent technique to construct an approximate graph to enable faster execution. The main idea behind V-Combiner is to merge certain vertices into hubs, which are vertices that have many connections and contribute heavily to the end result of the algorithm. We also propose an inexpensive correction step to recover the contribution of the merged vertices to get higher accuracy. We evaluate V-Combiner on 4 different applications and 5 datasets. For 44-threaded runs, V-Combiner achieves an average end-to-end speedup of 1.25X over the conventional system, with an accuracy of 91.8%. It also shows a better performance-accuracy trade-off than the existing sparsification and k-core techniques.