流式处理的异步图处理框架

作     者：李金吉 张岩峰 巩树凤 于戈 高立新 LI Jin-Ji;ZHANG Yan-Feng;GONG Shu-Feng;YU Ge;GAO Li-Xin

作者机构：东北大学计算机科学与工程学院辽宁沈阳110819 Department of Electrical and Computer Engineering University of Massachusetts Amherst 

基　　金：国家自然科学基金(61672141 61528203) 计算机体系结构国家重点实验室开放课题(CARCH201610) 中央高校基本科研业务费专项资金(N161604008)~~ 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2018年第29卷第3期

页      码：528-544页

摘      要：分布式图计算是目前处理大图数据的主流技术,但是存在诸多无法避免的问题,比如分布式计算的负载均衡和分布式实现的调试和优化仍然非常困难.另一方面,近几年的研究结果表明:通过设计合理的数据结构和处理模型,在单个PC上基于大容量磁盘的大图计算往往可以获得与分布式图计算相当的处理性能.例如,Graph Chi在单机上的处理性能与Spark在50台节点上的处理性能相差无几.结合累加迭代计算和单机并行处理技术,提出流式处理的异步计算模型ASP.它实现了对磁盘的完全顺序访问,允许流式的顺序载入结构数据的同时进行异步更新计算.基于ASP模型,提出了一种流式处理的异步图处理框架S-Maiter,实现了高效率的基于外存的单机大图处理,通过I/O线程优化、内存资源监控、shard级优先级调度等优化技术,提高了系统处理大图数据的性能.实验结果表明:在处理大图数据(1 300万顶点,5亿连边)时,仅仅需要1台PC机计算资源的S-Maiter与在16台PC上运行的分布式Maiter的性能几乎相当.并且,S-Maiter比另外一个流行的单机大图处理系统Graph Chi要快1.5倍.

主 题 词：外存 异步累加模型 I/O 流式处理 

学科分类：07[理学] 08[工学] 070104[070104] 0835[0835] 0811[工学-水利类] 0701[理学-数学类] 081201[081201] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13328/j.cnki.jos.005441

馆 藏 号：203284963...