摘要
利用Skylake架构处理器上的性能分析工具perf分析Ligra、Gemini和GraphBIG等3种图计算框架中的单源最短路径(Single Source Shortest Path,SSSP)及介数中心性(Betweenness Centrality,BC)算法的特性,评估了在3种框架下实现两种算法的性能指标,并使用皮尔逊相关系数方法分析了各指标与性能/能耗之间的关系。实验结果表明,当缓存每千条指令的平均未命中数较大且每一时钟周期内执行的指令数较小时,图计算的执行时间较长。若数据移动量较小,则图计算的执行时间和功耗均较小。随着系统处理任务的线程数增加,图数据边的执行时间明显减少,通过增加处理单元个数的方式可以提高硬件加速器的性能。当处理器内核数小于4时,应优先选择Gemini框架实现算法,而当内核数大于4时,选择图框架Ligra能够有效减少执行时间。数据移动量和功耗与性能/能耗表现出极强的相关性。将图数据全部加载到内存中计算能够有效减少数据移动的次数。在处理较稀疏的图数据时,选择Ligra框架实现算法计算量较小。
Perf,which is a performance analysis tool on the Skylake architecture processor,is used to analyze the characteristics of the Single Source Shortest Path(SSSP)algorithm and the Betweenness Centrality(BC)algorithm in three graph computing frameworks,namely Ligra,Gemini and GraphBIG.Performance indicators are adopted to analyze the relationship between each index and performance/energy consumption.The experiment result shows that when the average number of the cache misses in every thousand instructions is large,and the number of instructions executed in each clock cycle is small,the execution time of graph calculation is longer.If the amount of data movement is small,the execution time and power consumption of the graph calculation are both small.As the number of threads of system processing is increasing,the execution time of graph data edges is significantly reduced,and the performance of hardware accelerators can be improved by increasing the number of processing units.When the number of processor cores is less than 4,the Gemini framework is the priority selection to implement the algorithm,and when the number of cores is greater than 4,the Ligra framework can effectively reduced the execution time.The amount of data movement and power consumption have strong correlation with the performance/power consumption.Loading all the graph data into the memory for calculation can effectively reduce the number of data movement.When dealing with the sparse graph data,the Ligra framework is chosen to implement the algorithm with a smaller amount of calculation.
作者
邓军勇
赵一迪
DENG Junyong;ZHAO Yidi(School of Electronic Engineering,Xi'an University of Posts and Telecommunications,Xi'an 710121,China)
出处
《西安邮电大学学报》
2021年第2期35-41,共7页
Journal of Xi’an University of Posts and Telecommunications
基金
国家自然科学基金项目(61772417,61802304,61602377,61874087)。
