Quantitative Analysis of Graph Algorithms: Models and Optimization Methods
Quantitative Analysis of Graph Algorithms: Models and Optimization Methods
复制标题
图算法的定量分析：模型和优化方法
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yufeng Chen
中科院分区：
文献类型：
--
作者：
Xu Wang;Yongxin Zhu;Yufeng Chen
随着图形数据在现实世界中的广泛应用及其规模的不断增大，近年来已经开发了许多图形计算系统来扩展对海量图形的处理和分析。然而，很少有研究集中在建模的图算法和系统的性能，以确定现有的机器下的大规模图的工作负载的瓶颈。在本文中，我们提出了一个分析性能模型，考虑计算能力，通信带宽和通信延迟量化的图形算法的性能。基于该模型，我们发现大部分的图处理时间都花在了对相邻顶点的随机访问上，造成了很高的缓存丢失率，这使得性能受到通信延迟的限制。进一步从硬件和软件两个方面提出了性能优化方法，以缓解瓶颈。综合图和实际图的实验结果表明，这些优化方法可以产生高达4倍的性能提高各种图算法。
With the prevalence of graph data in real-world applications and their ever-increasing size, many graph computing systems have been developed in recent years to scale the processing and analyzing of massive graphs. However, few study focuses on modeling the performance of graph algorithms and systems to identify the bottleneck of existing machines under the workload of large-scale graphs. In this paper, we propose an analytical performance model considering computation capacity, communication bandwidth and communication latency to quantify the performance of graph algorithms. Based on this model, we find the majority of graph processing runtime is spent on random access of neighbouring vertices, causing a high cache missrate, which makes the performance bounded by communication latency. We further present performance optimization methods from perspectives of both hardware and software to alleviate the bottlenecks. Experiment results from both synthesis graphs andreal graphs show that these optimization methods can produce up to 4X performance improvement in a variety of graph algorithms.