图计算中遍历类图框架的特性

摘要：

利用Skylake架构处理器上的性能分析工具perf分析Ligra、Gemini和GraphBIG等3种图计算框架中的单源最短路径(Single Source Shortest Path,SSSP)及介数中心性(Betweenness Centrality,BC)算法的特性,评估了在3种框架下实现两种算法的性能指标,并使用皮尔逊相关系数方法分析了各指标与性能/能耗之间的关系.实验结果表明,当缓存每千条指令的平均未命中数较大且每一时钟周期内执行的指令数较小时,图计算的执行时间较长.若数据移动量较小,则图计算的执行时间和功耗均较小.随着系统处理任务的线程数增加,图数据边的执行时间明显减少,通过增加处理单元个数的方式可以提高硬件加速器的性能.当处理器内核数小于4时,应优先选择Gemini框架实现算法,而当内核数大于4时,选择图框架Ligra能够有效减少执行时间.数据移动量和功耗与性能/能耗表现出极强的相关性.将图数据全部加载到内存中计算能够有效减少数据移动的次数.在处理较稀疏的图数据时,选择Ligra框架实现算法计算量较小.

关键词：Ligra、Gemini、GraphBIG、单源最短路径算法、介数中心性算法

所属期刊栏目：26

分类号：TP302.7(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;国家自然科学基金

在线出版日期：2021-06-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：35-41