基于块坐标下降法的外存异步图计算系统  

Block coordinate descent based asynchronous out-of-core graph computing system

作　　者：赵程 张志斌[1,2] 郭嘉丰 刘丁玮[1,2] ZHAO Cheng;ZHANG Zhibin;GUO Jiafeng;LIU Dingwei(Key Lab of Network Data Science and Technology,Institute of Computing Technology,Chinese Academy of Sciences,Beijing 100190;University of Chinese Academy of Sciences,Beijing 100049)

机构地区：[1]中国科学院计算技术研究所网络数据科学与技术重点实验室,北京100190 [2]中国科学院大学,北京100049

出　　处：《高技术通讯》2022年第8期825-835,共11页Chinese High Technology Letters

基　　金：中国科学院战略性先导科技专项(XDA19020400);中国科学院青年创新促进会(20144310);联想-中科院联合实验室青年科学家项目(E051350);重庆市基础科学与前沿技术研究专项(cstc2017jcjyBX0059)资助项目。

摘　　要：现有外存图计算系统中,外存I/O带宽不足成为性能瓶颈。使用整体并行模型将导致冗余计算,使用异步并行模型则将引入额外的优先级计算开销和负载不均衡。本文提出了基于块坐标下降法(BCD)的外存异步图计算系统(BCDG),设计了一次选择多轮优先的调度策略,降低了优先级计算的平均开销;设计了基于优先级的块预取策略,解决了优先选择会破坏顺序执行流水线的问题;设计了计算调度分离的划分策略,实现了均衡地按边计算和按点调度。实验结果表明,相较于目前最先进的外存图计算系统GridGraph和Lumos,所提系统平均性能分别提升10.30倍与8.72倍。整体计算过程中,中央处理器(CPU)等待外存I/O的时间仅占10%~30%。For existing out-of-core graph computing systems, insufficient external memory I/O bandwidth is a performance bottleneck. Using a bulk synchronous parallel model will lead to redundant computation, while using an asynchronous parallel mode introduces additional priority computation overhead and load imbalance. In this paper, a block coordinate descent(BCD) based asynchronous out-of-core graph computing system(BCDG) is proposed. A scheduling strategy named one-selection multi-round priority is designed to reduce the average overhead of priority computation;a priority-based block prefetching strategy is designed to solve the problem that priority selection destroys the sequential execution pipeline;a partitioning strategy to separate computation and scheduling is designed to achieve balanced edge-by-edge computation and ensure vertex-by-vertex scheduling. The experimental results show that compared with two state-of-the-art out-of-core graph computing systems, GridGraph and Lumos, the proposed system outperforms them by 10. 30 times and 8. 72 times on average respectively. During the overall computation, the central processing unit(CPU) spends only 10%-30% of its time waiting for disk I/O.

关 键 词：图计算系统 外存 异步并行计算 块坐标下降(BCD) 图划分 

分 类 号：O157.5[理学—数学]