摘要
图计算作为分析与挖掘关联关系的一种关键技术,已在智慧医疗、社交网络分析、金融反欺诈、地图道路规划、计算科学等领域广泛应用.当前,通用CPU与GPU架构的并行结构、访存结构、互连结构及同步机制的不断发展,使得多核CPU与GPU成为图处理加速的常用平台.但由于图处理具有处理数据规模大、数据依赖复杂、访存计算比高等特性,加之现实应用场景下的图数据分布不规则且图中的顶点与边呈现动态变化,给图处理的性能提升和高可扩展性带来严峻挑战.为应对上述挑战,大量基于多核CPU与GPU平台的图处理系统被提出,并在该领域取得显著成果.为了让读者了解多核CPU与GPU平台上图处理优化相关技术的演化,首先剖析了图数据、图算法、图应用特性,并阐明图处理所面临的挑战.然后分类梳理了当前已有的基于多核CPU与GPU平台的图处理系统,并从加速图处理设计的角度,详细、系统地总结了关键优化技术,包括图数据预处理、访存优化、计算加速和数据通信优化等.最后对已有先进图处理系统的性能、可扩展性等进行分析,并从不同角度对图处理未来发展趋势进行展望,希望对从事图处理系统研究的学者有一定的启发.
As a key technique for analyzing and mining relationships,graph computing has been widely used in smart healthcare,social network analysis,financial anti-fraud,road navigation,computational sciences,and others.In recent years,with the development of parallel structures,memory access methods,interconnection structures,and synchronization mechanisms of general-purpose CPU and GPU architecture,multi-core CPU and GPU have become common platforms for accelerating graph processing.However,there are significant challenges to graph processing in terms of improving performance and achieving high scalability,such as the large scale and irregular distribution of data,complex data dependence,high communication-to-computation ratio,and dynamic changes of vertices and edges.To address the above challenges,a large number of graph processing systems based on multi-core CPU and GPU platforms are proposed and achieve good results.To provide readers with a comprehensive understanding of graph processing optimizations on multi-core CPU and GPU platforms,we first present the basic concepts,including the graph data structures,the typical graph algorithms,and the characteristics of graph application.Then the challenges of graph processing are clarified.After that,we present the existing graph processing systems based on multi-core CPU and GPU platforms.From the perspective of accelerated graph processing design,we summarize the key technology optimizations in detail and systematically,including pre-processing,memory access optimization,computing acceleration,and overhead reduction of data communication.Finally,we analyze the performance and scalability of state-of-art graph processing and conclude the future development trend of graph processing based on different perspectives,which expects to bring certain inspiration to relevant researchers to explore high-performance graph processing system.
作者
张园
曹华伟
张婕
申玥
孙一鸣
敦明
安学军
叶笑春
Zhang Yuan;Cao Huawei;Zhang Jie;Shen Yue;Sun Yiming;Dun Ming;An Xuejun;Ye Xiaochun(State Key Lab of Processors(Institute of Computing Technology,Chinese Academy of Sciences),Beijing 100190;University of Chinese Academy of Sciences,Beijing 100049;University of Chinese Academy of Sciences,Nanjing 211135)
出处
《计算机研究与发展》
EI
CSCD
北大核心
2024年第6期1401-1428,共28页
Journal of Computer Research and Development
基金
国家重点研发计划项目(2023YFB4502305)
北京市自然科学基金项目(4232036)
CAS青年创新促进会项目。
关键词
多核CPU与GPU平台
图处理系统
图数据表示
负载均衡
不规则访存
动态图处理
multi-core CPU and GPU platform
graph processing systems
graph data representation
load balancing
irregular memory access
dynamic graph processing