张承龙^1,2,曹华伟¹,王国波^1,2,郝沁汾¹,张洋¹,叶笑春¹,范东睿^1,2

¹(计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190);²(中国科学院大学计算机与控制学院 北京 100049) (caohuawei@ict.ac.cn)

出版日期: 2020-06-01


基金资助:国家重点研发计划项目(2018YFB1003501)；国家自然科学基金项目(11904370，61732018，61672499)；计算机体系结构国家重点实验室创新项目(CARCH4509)

Efficient Optimization of Graph Computing on High-Throughput Computer

Zhang Chenglong^1,2, Cao Huawei¹, Wang Guobo^1,2, Hao Qinfen¹, Zhang Yang¹, Ye Xiaochun¹, Fan Dongrui^1,2

¹(State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190);²(School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049)

Online: 2020-06-01


Supported by:This work was supported by the National Key Research and Development Program of China (2018YFB1003501), the National Natural Science Foundation of China (11904370, 61732018, 61672499), and the Innovation Project of the State Key Laboratory of Computer Architecture (CARCH4509).

摘要/Abstract

摘要： 随着互联网技术的蓬勃发展，图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法，也是Graph500基准的核心测试程序之一.高通量计算机采用ARM架构的众核体系结构，具有高并发、强实时、低功耗等适于大数据计算的特点.在单节点上，BFS算法的优化已取得一系列进展，首先对现有的优化技术进行系统的介绍，并在此基础上提出2种面向高通量计算机的优化手段，通过减少冗余访存和提高缓存局部性，有效提高了算法的访存效率.通过这些优化手段，在高通量计算机上对BFS算法的性能进行了系统的评估.对于顶点规模为230的Kronecker图(顶点数为230，边数为234)，优化后的BFS算法在高通量计算机上的平均性能为24.26 GTEPS.与两路x86架构服务器相比，单节点具有1.18倍的性能优势.在性能功耗比方面，高通量计算机的结果为181.04 MTEPS/W.在2019年6月份的Green Graph500面向大数据集的排行榜上取得第2名的成绩.综上，高通量计算机的高并发和低功耗等特点非常适合处理大规模图计算等数据密集型应用.

参考文献

相关文章 6

[1]	甘新标, 谭雯, 刘杰. 基于双向位图的CSR大规模图存储优化[J]. 计算机研究与发展, 2021, 58(3): 458-466.
[2]	薛瑞,苗福涛,叶笑春,孙凝晖,徐文星. 面向处理器微体系结构评估的高通量MicroBenchmark研究[J]. 计算机研究与发展, 2018, 55(7): 1569-1583.
[3]	唐金辉,李泽超,刘少礼,秦磊. 高通量图像视频计算[J]. 计算机研究与发展, 2017, 54(6): 1225-1237.
[4]	李文明,叶笑春,王达,郑方,李宏亮,林晗,范东睿,孙凝晖. MACT：高通量众核处理器离散访存请求批量处理机制[J]. 计算机研究与发展, 2015, 52(6): 1254-1265.
[5]	汤文,张春明,谭光明,张佩珩,孙凝晖. 基于定制协处理器的基因重测序加速技术研究[J]. 计算机研究与发展, 2014, 51(9): 1980-1992.
[6]	王文迪, 汤 文, 段 勃, 张春明, 张佩珩, 孙凝晖,. 基于Hash索引的高通量基因序列比对并行加速技术研究[J]. , 2013, 50(11): 2463-2471.

PDF全文下载地址:

https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4192