新型体系结构上的图计算技术与方法研究

In the context of new computing device, traditional large-scale graph computing is facing new opportunities and challenges. Graph algorithms often exhibit poor locality, and low cache hit rate feature. The traditional computing architecture are computing-centric, focusing on memory sharing and message communications, which is unable to deal graph data processing, especially large-scale graph data. In this project, we focus on the key technologies and methods of new computing architecture for large scale graph data processing, this project focused on: (1) Semantic model for large scale graph data processing under new computing architecture, which include semantic rule base and graph data interpretation method; (2) an architecture-driven programming model, which include parallel computing method, load balance and so on; (3) data-aware and topology-aware graph data partition and data layout scheme, which will analyze the data structure and process features to make the best data mapping to the new computing architecture. The successful research of this subject will help to promote the development of large data analysis technology and broaden the application of new architecture in large data analysis.

图数据的蓬勃发展使得图计算技术与系统的研究变得越来越重要，但由于图处理的时空局部性差、访存密集、迭代计算等处理特点，以局部性原理为指导的传统体系结构设计在图处理中效率低下。针对这一问题，本课题拟开展新型体系结构上的图数据处理关键技术与方法研究。围绕新型体系结构上的图计算表达、编程以及数据划分与放置，本项目从三方面开展研究：1）针对新型体系结构的并行特征与图计算迭代特征，研究新型体系结构下的图计算语义模型，包括语义规则库、DSL解释器等；（2）针对新型体系结构的异构并行性与图处理扩展性需求，研究多体系结构支持的图处理编程模型，包括图计算并行处理抽象与体系结构运行时支撑等；（3）针对体系结构局部内存访存高、容量小特征与大图处理需求，研究兼顾图处理计算负载均衡与通信开销、访存效率与冗余开销的图数据划分与放置策略，包括图数据存储格式、数据划分策略等。

课题以新型体系结构上的图算法语义模型、图计算编程模型以及数据划分与放置策略为核心开展研究。研究了以颜色为中心的两阶段图着色算法Feluca、参数级的并行优化算法 plpSGD等算法，显著提高了图算法在异构计算设备上的并行性与扩展性。同时还提出了基于GPU的富元数据属性图管理系统GRAM，用以支持大规模属性图在GPU上的高速访问及查询，相关成果发表在NPC上。在显存与内存优化方面，本课题提出了基于张量的GPU内存管理框架Capuchin以及基于对象生命周期的内存管理机制Deca，其中Deca可以提升图计算应用 PageRank和CC 6.4倍的性能，两项成果分别发表ASPLOS会议和TOCS期刊上。在数据存储方面，本项目组开发了高性能的内存时序数据库ByteSeries、基于机器学习的重复查询缓存系统Maxon、基于负载感知的BurstBuffer优化系统SSDUP、基于对象级协调的负载均衡系统LoomIO，基于Deadline的服务质量保障系统DDL-QoS以及基于软件定义的服务质量保障系统SDQoS，相关工作分别发表在ICDE会议、SoCC会议、TACO期刊、TPDS期刊、CCPE期刊及THPC期刊上。