• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

面向高通量计算机的图算法优化技术

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

张承龙, 曹华伟, 王国波, 郝沁汾, 张洋, 叶笑春, 范东睿. 面向高通量计算机的图算法优化技术[J]. 计算机研究与发展, 2020, 57(6): 1152-1163. DOI: 10.7544/issn1000-1239.2020.20200115
引用本文: 张承龙, 曹华伟, 王国波, 郝沁汾, 张洋, 叶笑春, 范东睿. 面向高通量计算机的图算法优化技术[J]. 计算机研究与发展, 2020, 57(6): 1152-1163. DOI: 10.7544/issn1000-1239.2020.20200115
shu
Zhang Chenglong, Cao Huawei, Wang Guobo, Hao Qinfen, Zhang Yang, Ye Xiaochun, Fan Dongrui. Efficient Optimization of Graph Computing on High-Throughput Computer[J]. Journal of Computer Research and Development, 2020, 57(6): 1152-1163. DOI: 10.7544/issn1000-1239.2020.20200115
Citation: Zhang Chenglong, Cao Huawei, Wang Guobo, Hao Qinfen, Zhang Yang, Ye Xiaochun, Fan Dongrui. Efficient Optimization of Graph Computing on High-Throughput Computer[J]. Journal of Computer Research and Development, 2020, 57(6): 1152-1163. DOI: 10.7544/issn1000-1239.2020.20200115
shu
张承龙, 曹华伟, 王国波, 郝沁汾, 张洋, 叶笑春, 范东睿. 面向高通量计算机的图算法优化技术[J]. 计算机研究与发展, 2020, 57(6): 1152-1163. CSTR: 32373.14.issn1000-1239.2020.20200115
引用本文: 张承龙, 曹华伟, 王国波, 郝沁汾, 张洋, 叶笑春, 范东睿. 面向高通量计算机的图算法优化技术[J]. 计算机研究与发展, 2020, 57(6): 1152-1163. CSTR: 32373.14.issn1000-1239.2020.20200115
shu
Zhang Chenglong, Cao Huawei, Wang Guobo, Hao Qinfen, Zhang Yang, Ye Xiaochun, Fan Dongrui. Efficient Optimization of Graph Computing on High-Throughput Computer[J]. Journal of Computer Research and Development, 2020, 57(6): 1152-1163. CSTR: 32373.14.issn1000-1239.2020.20200115
Citation: Zhang Chenglong, Cao Huawei, Wang Guobo, Hao Qinfen, Zhang Yang, Ye Xiaochun, Fan Dongrui. Efficient Optimization of Graph Computing on High-Throughput Computer[J]. Journal of Computer Research and Development, 2020, 57(6): 1152-1163. CSTR: 32373.14.issn1000-1239.2020.20200115
shu

面向高通量计算机的图算法优化技术

  • 1(计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190)

  • 2(中国科学院大学计算机与控制学院 北京 100049) (caohuawei@ict.ac.cn)

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

  • 中图分类号: TP301

Efficient Optimization of Graph Computing on High-Throughput Computer

  • 1(State Key Laboratory of Computer Architecture (Institute of Computing Technology, Chinese Academy of Sciences), Beijing 100190)

  • 2(School of Computer and Control Engineering, University of Chinese Academy of Sciences, Beijing 100049)

Funds: 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).

HTML全文

    摘要
  • 摘要: 随着互联网技术的蓬勃发展，图数据的规模呈爆炸式增长.如何高效地处理大规模图数据逐渐成为工业界和学术界关注的焦点.宽度优先搜索算法是解决图遍历问题的经典算法，也是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名的成绩.综上，高通量计算机的高并发和低功耗等特点非常适合处理大规模图计算等数据密集型应用.
    Abstract: With the rapid development of computing technology, the scale of graph increases explosively and large-scale graph computing has been the focus in recent years. Breadth first search (BFS) is a classic algorithm to solve graph traverse problem. It is the main kernel of Graph500 benchmark that evaluates the performance of supercomputers and servers in terms of data-intensive applications. High-throughput computer (HTC) adopts ARM-based many-core architecture, which has the characteristics of high concurrency, strong real-time, low-power consumption. The optimization of BFS algorithm has made a series of progress on single-node systems. In this paper, we first introduce parallel BFS algorithm and existing optimizations. Then we propose two optimization techniques for HTC to improve the efficiency of data access and data locality. We systematically evaluate the performance of BFS algorithm on HTC. For the Kronecker graph with 2scale=230whose vertices are 230 and edges are 234, the average performance on HTC is 24.26 GTEPS and 1.18 times faster than the two-way x86 server. In terms of energy efficiency, the result on HTC is 181.04 MTEPS/W and rank 2nd place on the June 2019 Green Graph500 big data list. To our best knowledge, this is the first work that evaluates BFS performance on HTC platform. HTC is suitable for data intensive applications such as large-scale graph computing.
    • HTML全文
    • 参考文献(0)
    • 相关文章
    • 施引文献(92)

  • 期刊类型引用(27)

    1. 顾敏，徐雅男，王辛迪，花敏，周雯. 多用户MIMO-MEC网络中基于APSO的任务卸载研究. 无线电工程. 2024(03): 711-718 . 百度学术
    2. 王斐然，郭昕阳，张峰. 基于边缘计算的输电线路巡检设备协同调配研究. 自动化仪表. 2024(05): 123-126 . 百度学术
    3. 史晓蒙，吕晓鹏，魏健康，王凌. 基于算法组合的端边云任务处理方法. 价值工程. 2024(36): 108-112 . 百度学术
    4. 向朝参，程文辉，张昭，焦贤龙，屈毓锛，陈超，戴海鹏. 基于边缘智能计算的城市交通感知数据自适应恢复. 计算机研究与发展. 2023(03): 619-634 . 本站查看
    5. 邵梁，何星舟，尚俊娜. 边缘计算中利用改进型遗传算法的任务卸载策略. 计算机应用与软件. 2023(11): 48-57 . 百度学术
    6. 高仕斌，刘帝洋，韦晓广，康高强，罗嘉明，雷杰宇. 基于数字孪生网络的牵引供电智能运维体系与应用架构. 铁道学报. 2023(12): 1-15 . 百度学术
    7. 张彦虎，鄢丽娟，马志愤，张彦军. 一种适用于多任务多资源移动边缘计算环境下的改进粒子群算力卸载算法. 计算机与现代化. 2022(05): 54-60+67 . 百度学术
    8. 刘春林，秦进. 面向5G网络的移动边缘计算节点部署算法设计. 计算机仿真. 2022(12): 436-439+473 . 百度学术
    9. 张开强，蒋从锋，程小兰，贾刚勇，张纪林，万健. 多分辨率下资源感知的图像目标自适应缩放检测. 计算机科学. 2021(04): 180-186 . 百度学术
    10. 乐光学，陈光鲁，卢敏，杨晓慧，刘建华，黄淳岚，杨忠明. 一种基于K-shell影响力最大化的路径择优计算迁移算法. 计算机研究与发展. 2021(09): 2025-2039 . 本站查看
    11. 苏命峰，王国军，李仁发. 边云协同计算中基于预测的资源部署与任务调度优化. 计算机研究与发展. 2021(11): 2558-2570 . 本站查看
    12. 贾觐，暴占彪. 改进GA的边缘计算任务卸载与资源分配策略. 计算机工程与设计. 2021(11): 3009-3017 . 百度学术
    13. 汪小威，林宁，胡玉平. 移动边缘计算中利用BPSO的任务卸载策略. 计算机工程与设计. 2021(12): 3333-3341 . 百度学术
    14. 尹高，石远明. 移动边缘网络中深度学习任务卸载方案. 重庆邮电大学学报(自然科学版). 2020(01): 38-46 . 百度学术
    15. 丁雪乾，薛建彬. 边缘计算下基于Lyapunov优化的系统资源分配策略. 微电子学与计算机. 2020(02): 63-68 . 百度学术
    16. 白昱阳，黄彦浩，陈思远，张俊，李柏青，王飞跃. 云边智能:电力系统运行控制的边缘计算方法及其应用现状与展望. 自动化学报. 2020(03): 397-410 . 百度学术
    17. 乐光学，戴亚盛，杨晓慧，刘建华，游真旭，朱友康. 边缘计算可信协同服务策略建模. 计算机研究与发展. 2020(05): 1080-1102 . 本站查看
    18. 盛津芳，滕潇雨，李伟民，王斌. 移动边缘计算中基于改进拍卖模型的计算卸载策略. 计算机应用研究. 2020(06): 1688-1692 . 百度学术
    19. 胡锦天，王高才，徐晓桐. 移动边缘计算中具有能耗优化的任务迁移策略. 计算机科学. 2020(06): 260-265 . 百度学术
    20. 周振宇，陈亚鹏，潘超，赵雄文，张磊，汪中原. 面向智能电力巡检的高可靠低时延移动边缘计算技术. 高电压技术. 2020(06): 1895-1902 . 百度学术
    21. 吕洁娜，张家波，张祖凡，甘臣权. 移动边缘计算卸载策略综述. 小型微型计算机系统. 2020(09): 1866-1877 . 百度学术
    22. 张伟. 边缘计算的任务迁移机制研究. 软件导刊. 2020(09): 48-53 . 百度学术
    23. 路亚. MEC多服务器启发式联合任务卸载和资源分配策略. 计算机应用与软件. 2020(10): 77-84 . 百度学术
    24. 方加娟，李凯. 基于边缘云和移动辅助设备的计算卸载优化方案. 计算机应用与软件. 2020(12): 6-12 . 百度学术
    25. 危泽华，曾玲玲. 基于Stackelberg博弈论的边缘计算卸载决策方法. 数学的实践与认识. 2019(11): 91-100 . 百度学术
    26. 居晓琴. 移动边缘计算的QoE视频缓存方法. 电脑与信息技术. 2019(05): 44-47 . 百度学术
    27. 乐光学，戴亚盛，杨晓慧，朱友康，游真旭，刘建生. 边缘计算多约束可信协同任务迁移策略. 电信科学. 2019(11): 36-50 . 百度学术

    其他类型引用(65)

    • 资源附件(0)
计量
  • 文章访问数:  1509
  • HTML全文浏览量:  3
  • PDF下载量:  693
  • 被引次数: 92
出版历程
  • 发布日期:  2020-05-31

目录

摘要
HTML全文
    参考文献(0)
    相关文章
    施引文献(92)
    资源附件(0)

    /

    返回文章
    返回
    邮件订阅 RSS
    微信订阅号<br/>（实时资讯）

    微信订阅号
    （实时资讯）

    微信服务号<br/>（同步网站）

    微信服务号
    （同步网站）

    微信视频号<br/>（视频分享）

    微信视频号
    （视频分享）

    CCF<br/>（扫码入会）

    CCF
    （扫码入会）

    版权所有 © 《计算机研究与发展》编辑部

    本系统由北京仁和汇智信息技术有限公司开发  百度统计