现阶段, 随着数据规模扩大化和结构多样化的趋势日益凸现, 如何利用现代链路内链的异构多协处理器为大规模数据处理提供实时、可靠的并行运行时环境, 已经成为高性能以及数据库领域的研究热点. 利用多协处理器(GPU)设备的现代服务器(multi-GPU server)硬件架构环境, 已经成为分析大规模、非规则性图数据的首选高性能平台. 现有研究工作基于Multi-GPU服务器架构设计的图计算系统和算法(如广度优先遍历和最短路径算法), 整体性能已显著优于多核CPU计算环境. 然而, 这类图计算系统中, 多GPU协处理器间的图分块数据传输性能受限于PCI-E总线带宽和局部延迟, 导致通过增加GPU设备数量无法达到整体系统性能的类线性增长趋势, 甚至会出现严重的时延抖动, 进而已无法满足大规模图并行计算系统的高可扩展性要求. 经过一系列基准实验验证发现, 现有系统存在如下两类缺陷: (1) 现代GPU设备间数据通路的硬件架构发展日益更新(如NVLink-V1, NVLink-V2), 其链路带宽和延迟得到大幅改进, 然而现有系统受限于PCI-E总线进行数据分块通信, 无法充分利用现代GPU链路资源(包括链路拓扑、连通性和路由); (2) 在应对不规则图数据集时, 这类系统常采用过于单一的设备间数据组织和移动策略, 带来大量不必要GPU设备间经PCI-E总线的数据同步开销, 导致本地性计算同步等待时延开销过大.因此, 充分地利用各类现代Multi-GPU服务器通信链路架构来设计可扩展性强的图数据高性能计算系统亟待解决.为了达到Multi-GPU下图计算系统的高可扩展性, 提出一种基于混合感知的细粒度通信来增强Multi-GPU图计算系统的可伸缩性, 即采用架构链路预感知技术对图结构化数据采用模块化数据链路和通信策略, 为大规模图数据(结构型数据、应用型数据)最优化选择数据交换方法. 综合上述优化策略, 提出并设计了一种面向Multi-GPU图并行计算系统ChattyGraph. 通过对GPU图数据缓冲区优化, 基于OPENMP与NCCL优化多核GPU协同计算, ChattyGraph能在Multi-GPU HPC平台上自适应、高效地支持各类图并行计算应用和算法. 在8-GPU NVIDIA DGX服务器上, 对各种真实世界图数据的若干实验评估表明: ChattyGraph显著实现了图计算效率和可扩展性的提升, 并优于其他最先进的竞争对手性能, 计算效率平均提升了1.2×-1.5×, 加速比平均提升了2×-3×, 包括WS-VR和Groute.
Recently, with the increasing trend of data scale expansion and structure diversification, how to use the heterogeneous multi accelerators in modern link to provide a real-time and reliable parallel runtime environment for large-scale data processing has become a research hotspot in the field of high performance and database. Modern servers equipped with multi accelerators (GPU) has become the preferred high-performance platform for analyzing large-scale and irregular graph data. The overall performance of existing research designing graph computing systems and algorithms based on multi-GPU server architecture (such as breadth first traversal and shortest path algorithm) has been significantly better than that of multi-core CPU computing environment. However, the data transmission performance between multi-GPU of existing graph computing system is limited by PCI-E bandwidth and local delay, leading to being unable to achieve a linear growth trend of performance by increasing the number of GPU devices, and even serious delay jitter which cannot satisfy the high scalability requirements of large-scale graph parallel computing systems. After a series of benchmark experiments, it is found that the existing system has the following two types of defects. (1) The hardware architecture of the data link between modern GPU devices is rapidly updated (such as NVLink-V1 and NVLink-V2), and its link bandwidth and delay have been greatly improved. However, the existing systems are still limited by PCI-E for data communication, and cannot make full use of modern GPU link resources (including link topology, connectivity, and routing); (2) When dealing with irregular graph data, such systems often adopt single data movement strategy between devices, bringing a lot of unnecessary data synchronization overhead between GPU devices via PCI-E bus, resulting in excessive time-wait overhead of local computing. Therefore, it is urgent to make full use of various communication links between modern multi-GPU to design a highly scalable graph computing system. In order to achieve the high scalability of the multi-GPU graph computing system, a fine-grained communication based on hybrid perception is proposed to enhance the scalability of the multi-GPU graph computing system. It pre-awares the architecture link, uses the modular data link and communication strategy for different graph structured data, and finally selects the optimal data exchange method for large-scale graph data (structural data and application data). Based on above optimization strategies, this study proposes and designs a graph oriented parallel computing system via multi-GPU named ChattyGraph. By optimizing data buffer and multi-GPU collaborative computing with OpenMP and NCCL, ChattyGraph can adaptively and efficiently support various graph parallel computing applications and algorithms on multi-GPU HPC platform. Several experiments of various real-world graph data on 8-GPU NVIDIA DGX server show that ChattyGraph significantly improves graph computing efficiency and scalability, and outperforms other advanced competitors. The average computing efficiency is increased by 1.2×-1.5× and the average acceleration ratio is increased by 2×-3×, including WS-VR and Groute.
随着硬件不断发展的趋势, 搭载多块通用图形处理单元(general graphic procssor units, GPU)的服务器已成为现代高性能计算(high performance computing, HPC)的主流运算平台[
在当前GPU高性能图计算系统研究工作中, Multi-GPU图数据并行系统设计逻辑围绕以顶点(vertex)为中心的思想进行图数据切分、图分块迭代计算和整体同步[
1) 同步模型(synchronization model): 遵循整体同步并行计算模型, 即在每个迭代计算轮加载和处理本地子图分块之后, 所有设备之间均需全局通信同步[
2) 异步模型(asynchronization model): 基于流水线工作列表(worklist)的任务队列实现设备间计算和异步通信, 这使得自定义代码中不需要制定显式同步条件, 只设置细粒度(非批量)同步点来更新本地子图数据[
然而, 经过调研和验证, 现有GPU服务器图并行计算系统在扩展到Multi-GPU服务器环境时, 其可扩展性和性能仍存在问题和挑战[
进一步, 在NVIDIA DGX服务器上, 对当前最先进的GPU图并行计算系统WSVR[
Groute和WS-VR的扩展性实验
1) 仍依赖于主处理器总线PCI-E通信模型. 这类系统忽略了利用现代GPU设备间链路和机制进行协同优化, 包括NVLink技术和集合通信模型等;
2) 缺乏有效的策略以应对各类不同数据粒度间的非规则性图数据集的数据交换, 从而导致了大量的设备间同步开销, 使这类系统难以权衡GPU设备本地性计算和设备间远程通信的开销平衡.
本文对Multi-GPU图数据计算系统(WSVR, Groute)进行了深度并行机理性分析, 深入研究了P2P和UVA两种通信模式(见第1.2节). 本文研究发现: 对于不同大小的图计算数据集, 并非所有情况均适用于选择同一类模式. 因此, 构建一套自适应的通信方法会有效提升通信和资源利用率. 该策略不仅能为不同的图应用基准提供高效的并行计算性能, 而且会在图算法的不同执行阶段设置最优化的缓存通信性能. 例如: GPU的UVA(unified virtual addressing space)模式提供了易于实现的设备访存读写方式, 更适用于小粒度数据集读写; 而NCCL方法可以将设备内的消息细粒度化传输, 降低对等通信开销, 更适用于大粒度的数据移动算法(例如PageRank). 此外, NCCL方法在遍历算法中具有良好的通信性能, 但同时也会在多轮迭代过程中引入大量初始化操作开销, 反而会影响图迭代算法的性能. 基于这些观测结果, 本文设计了一种高效、可扩展的大规模图数据并行计算方法. 重点研究了最优通信模式选择.
本文的主要贡献总结如下:
(1) 本文量化了NVLink, PCI-E等通信链路技术, 在不同的图基准、数据集、执行阶段和GPU规模上, 对当前先进Multi-GPU服务器的数据链路特性进行了综合分析;
(2) 基于硬件通信链路特性, 对比分析了3类通信模式的通信效率, 设计并实现了一种基于混合感知的细粒度通信模型, 优化了多GPU间图数据通信效率, 针对不同的图数据结构采用协同通信模式. 结果表明, 混合图数据感知的通信模式降低了GPU间的通信时间1.2×−1.5×;
(3) 实现了新的高可扩展Multi-GPU图并行计算系统ChattyGraph, 优化了多GPU设备内图数据缓冲区以及实现了基于OPENMP与NCCL的多核CPU和多GPU设备协同计算, 并提出了3类用户友好的API接口, 实现了各类标准图并行计算算法(广度优先遍历、PageRank、最短路径遍历等);
(4) 实验结果表明: ChattyGraph与GPU图数据并行计算系统(WS-VR, Groute)相比, 达到了1.5×−3×的性能提升; 同时, 在8GPU下, 平均加速比普遍能达到3×−4×左右, 比WS-VR和Groute性能加速比提升2倍. 另外, 实验也从多角度验证了所提方案的性能优势, 在图数据量和GPU数量不断扩大的情况下, ChattyGraph的图数据处理效率提升越发明显.
本文第1节介绍GPU高性能图计算系统的相关工作背景, 并给出现代GPU设备间的通信链路技术和数据移动策略. 第2节给出Multi-GPU下高扩展图并行计算系统的架构动机, 并分析高可扩展性的图计算瓶颈和应对策略. 进一步地, 第3节详细介绍高扩展图计算系统ChattyGraph新的细粒度通信策略. 第4节具体描述高扩展图计算系统ChattyGraph的实现细节, 包括GPU设备内图数据表征及缓冲区优化、在多核CPU和多块GPU设备间图数据协同计算优化. 第5节描述具体的实验平台、实验设计以及实验结果和分析. 最后是本文的总结和未来展望.
利用GPU协处理器的高并行计算能力构建高性能、可扩展性图计算应用和算法优化的工作一直是高性能、数据库以及系统领域的研究热点. 随着图数据量的规模不断增大、应用需求的日益增多, 各类基于GPU的图计算系统层出不穷, 例如, Medusa[
在本节中, 本文首先简要讨论Multi-GPU图数据并行处理系统的相关研究工作; 然后, 从软件系统的角度深入分析当前3种现代GPU设备间数据交换链路架构和通信方式; 最后, 本文具体分析了当前Multi-GPU图数据并行计算系统的若干缺陷.
分布式或共享内存的高性能图数据计算研究一直是高性能、数据库以及系统领域的研究热点, 并且催生了诸多面向GPU处理器的图计算系统[
随着数据规模的不断增加, 近年来, 在搭载多块互通互联GPU设备的Multi-GPU服务器上开展高性能大规模图数据处理已开始受到各类研究的关注[
具体地, 以下分别介绍两类当前最先进的Multi-GPU图数据并行计算系统架构, WSVR和Groute.
WSVR[
两种先进的多GPU图数据处理系统
Groute[
近年来, GPU通常被作为协处理器来弥补CPU在大规模数据并行计算上的缺陷, 而CPU处理器主要负责数据的预处理和后处理、内存分配、进程管理以及调度和管理GPU核操作和GPU间数据通信. CPU与GPU之间通过前端总线(FSB, 例如QPI和HyperTransport)相互连接. 前端总线与北桥连接, 并由北桥通过PCI-E, NVLink-V1和NVLink-V2链路连接到GPU显卡.
具有8个NVIDIA V100 GPU的NVIDIA DGX服务器的内部链接拓扑
GPU间链路互联特性
设备链路 | 带宽(MB/s) | 0-hop (ms) | 1-hop (ms) | 2-hop (ms) |
PCI-E | 2 872.111 | 0.348 176 | 0.686 045 | 0.732 432 |
NVLink-V1 | 17 196.9 | 0.058 15 | 0.117 411 | 0.176 563 |
NVLink-V2 | 27 228.67 | 0.036 726 | 0.078 07 | 0.113 05 |
在本节中, 下面以PCI-E, NVLink-V1和NVLink-V2为例, 重点讨论GPU设备间数据通信的互联技术.
PCI-E: 高速串行计算机扩展总线标准, 即外围组件互联快速总线. 在高性能GPU服务器内, 设备间的数据链路通过PCI-E总线构架. 一个或多个GPU设备通过PCI-E总线连接到CPU主机端. 与CPU和DRAM之间数据带宽速度相比, 由于大量待处理数据需要从源设备(磁盘或源GPU设备访存)加载至DRAM之后, 再经PCI-E加载至目的GPU访存空间, 局限的PCI-E总线带宽限制了多块GPU协处理器和CPU之间的数据传输效率. 因此, 局限的PCI-E总线带宽和延迟使其成为GPU高性能算法设计的主要性能瓶颈[
NVLink-V1: 基于高速信号互联(NVHS)总线[
UVA和NCCL在传输不同大小数据时的通信带宽对比
不同大小的数据包在各链路技术之间通信性能的情况
NVLink-V2: 基于NVLink-V1优化的桥接器. 相对比NVLink-V1, NVLink-V2使用硬件地址转换, 提供了Unified Memory机制支持GPU设备直接访问CPU地址, 大幅提高了设备间的链路带宽, 并为NVIDIA Tesla GPU设备提供了更多的链路插槽[
基于底层互联链路, 在多GPU集群中设计了多种通信方式, 包括点对点通信和集合通信. 点对点通信直接依附于通信链路, 通过CUDA中的通信API: cudaMemcpy和cudaMemcpyPeer实现CPU-GPU和GPU-GPU之间的通信. 集合通信通常会涉及多个发送者和接收者, 其操作包括广播(broadcast)、分散(scatter)、聚集(gather)等. 有效第实现集合通信, 要综合考虑集群中的所有设备状态, 因此需要从底层的硬件拓扑结构出发, 选择合适的通信路径, 以解决通信过程中的冗余、同步和死锁问题. 在本节中, 下面介绍UVA和NCCL两种通信方式, 优化传统通信过程中的通信延迟.
UVA: 统一虚拟寻址(unified virtual addressing)是CUDA v4.0版本起支持的新特性. UVA本质上没有缓解PCI-E的低带宽和高延迟, 其通过零拷贝(zero-copy)内存为所有内存提供一个虚拟地址空间, 允许GPU中的访存指针直接内存访问, 而不需要显式的数据拷贝; 通过固定内存(pinned memory)锁定主存存储页, 避免因分页引起的页面缺失. Dipanjan Sengupta等人[
NCCL: NVIDIA开发的GPU集合通信库NCCL (NVIDIA collective communication library)高效地实现了多设备间的高性能通信, 现已集成到多个深度学习平台上. 目前, NCCL库有两个版本: NCCL-V1(开源)和NCCL-V2(闭源). 为了最大化传输带宽, NCCL通信库可以自动识别节点内的NVLink, PCI-E和QPI链路, 在硬件拓扑结构中构建环状通信路径. 将大数据集细粒度切分成小块, 沿环状网络以流水线形式传输. 据分析: 当数据切分份数远大于设备数时, 集合通信所需要的时间趋于点对点通信时间, 即集合通信时间不会随着设备数量的增加而增加, 为集合通信的扩展性能提供了可能.
如
点对点通信在传输不同大小数据时的通信延迟
设备间数据传输大小 |
设备间零拷贝 |
同步式设备间内存访问 |
异步式设备间内存拷贝 |
4 | 0.017 | 0.040 | 0.025 |
16 | 0.037 | 0.061 | 0.050 |
64 | 0.118 | 0.136 | 0.124 |
256 | 0.621 | 0.405 | 0.372 |
1 024 | 3.317 | 1.497 | 1.419 |
4 096 | 25.272 | 5.391 | 5.307 |
16 384 | 174.579 | 27.144 | 28.302 |
从表中可以看出: 对于小数据传输时, 选择Zero-Copy的通信延迟都要优于其他两种; 而在传输大数据, Zero-Copy性能不佳. 结合
● 现有系统扩展到Multi-GPU链路技术时存在的可扩展性缺陷
综上所述, 当前最先进的面向Multi-GPU服务器的大规模图数据并行计算系统[
随着GPU设备间链路通信技术的持续更新, 设备间数据移动的性能得到显著改进. 然而, 现有相关研究工作在设计Multi-GPU图并行计算系统时, 在一定程度上忽视了对这类先进设备间链路技术优势的使用, GPU设备间高效的链路带宽资源并未得到充分利用.
在本节中, 基于对服务器可伸缩性评估的研究, 本文总结了不同节点间互连技术在不同粒度图数据、通信模式以及负载均衡的影响(带宽、延迟等). 之后, 给出了在扩展到多GPU平台上架构和设计大规模图并行计算系统所面临挑战和应对策略选择.
● 体系结构感知的连通性预判
在Multi-GPU服务器中, 各GPU设备均配置若干链路桥接器(
因此, 在进行大规模大粒度数据移动操作之前, 通过预先检测服务器体系结构下多GPU设备间的连通性, 从而预判数据路由流的最优选择, 避免设备之间单一的数据传输路径.
● 设备间同步数据的粒度选择
从
因此, 在应对不规则的、稀疏的图数据集时, Multi-GPU图并行计算系统的可扩展性不仅需要考虑根据数据粒度来选择最优的设备间链路, 更为重要的是, 决策传输数据包的大小和选择更为合理的数据传输操作(P2P/UVA/显式/集合通信等), 以达到最优传输性能.
为了使当前基于GPU的图数据并行计算系统能够更好地扩展到Multi-GPU平台上, 本文拟构建优化的通信模型来识别各GPU设备的连通性和工作负载调度情况. 第3节将介绍我们的Multi-GPU图计算系统的全新基于混合感知的细粒度图计算通信模型. 为了解决不同结构数据通信模式选择和计算与通信平衡性的权衡挑战, 本文设计并实现了一个通用的GPU图并行计算框架, 并对所提策略(GPU缓存优化、多核CPU和多GPU设备协同)进行集成化实现, 形成面向Multi-GPU图计算并行系统ChattyGraph, 第4节将详细描述其实现部分.
通过数据感知通信[
如第2节讨论所述, 现有Multi-GPU图数据并行计算系统在迭代计算执行过程中选择了单一特定的通信模型. WSVR图数据计算框架采用统一内存管理技术(UVA)在主机内存端进行数据同步, Groute图数据计算框架也采用主机内存端进行数据同步, 并配合传输路由, 优化了WSVR中完全的UVA形式, 属于不完全的主机内存端同步.
相比之下, ChattyGraph使用细粒度和粗粒度的GPU间通信操作, 这是一种混合的数据结构感知的内部通信运行时. 这是因为在不规则图数据处理的并行迭代过程中, 不同的处理数据集有不同大小的值需要同步, 并要求不同类型的并行. ChattyGraph旨在为不同粒度的结构数据和应用数据、状态数据提供不同的GPU间通信操作以及不同的GPU内内存访问. 为了降低PCI-E的带宽、延迟等资源局限性, ChattyGraph充分利用NVLink构建GPU之间的路径, 大大排除了CPU参与的计算. 如下所示, ChattyGraph在我们的混合运行时中主要选择了两个优化的通信操作.
● 通过集合操作的结构数据路径
统一虚拟寻址主要用于存储在CPU主机缓冲区中的整个结构图数据集, 在初始化阶段, 经由CSR图数据压缩后分割和分配给多GPU, 各GPU访存内设置切分后, 部分图数据大小的空间与该缓冲区对等, 包括顶点偏移量和边, 底层GPU设备通过寄存器操作以保障缓存的一致性. 然而, 底层有限的PCI-E带宽使得CUDAMemcpyAsync操作无法扩展到从多个设备访问海量图数据结构, 成为扩展到多GPU系统时的主要瓶颈. 与传统的结构数据同步机制不同, ChattyGraph通过预先分配全局顶点值数组的缓冲区来部署广播操作, 因为所有互连GPU设备中都存在大量对更新值的访问. 更具体地, ChattyGraph消除了CPU内存缓冲区作为路由器的参与. 整个同步阶段完全在GPU之间执行, 如
混合通信模型
多线程更新
由算法1的ChattyGraph主控流程伪代码所示: 当设备完成本轮计算任务(第10行)后, 需要通信的顶点值会保存在发送缓冲区, 并由NCCL的广播函数进行广播(第15行), 广播的目的地址是每个设备的接收缓冲区.在下一轮迭代开始时, 所有设备都需从上轮迭代的接收缓冲区中更新顶点值(第6行), 通过多线程管理接收缓冲区数组的每一位, 更新对应关键词的
● 通过P2P操作的状态数据路径
图计算迭代过程中的状态数据主要包括GPU设备状态、需要传输的定量数据计数和迭代间控制的标志位等. 状态数据集是迭代式图计算应用所必需的. 通过度量, 状态数据量的粒度相对结构数据量较小, 然而对在Multi-GPU处理中的系统扩展性能具有不可忽视的影响, 因为GPU设备的状态控制需要在每一轮迭代后根据不断更新的状态值判断是否需要同步, 进而影响迭代轮收敛结果. 这类状态数据如
方法:
(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)
(13)
(14)
(15)
(16)
(17)
(18) /* Does iteration finish? */
(19)
(20) Iteration finish
(21)
(22)
(23) Iteration not finish
(24)
(25)
其中, 设备信息通过设备ID(包括源设备
●
●
●
●
本节对上述的细粒度图数据通信模型进行了集成实现, 设计了面向Multi-GPU高可扩展图并行计算系统ChattyGraph.
ChattyGraph系统架构图
通信引擎主要负责CPU-GPU与GPU-GPU间的数据读写和同步, 对顶点数据在全局GPU间同步采用ncclBroadcast广播, 而对于状态数据采用在主存中开辟UVA空间, 以显式cudaMemcpyAsync提供传输策略.在通信模块中, 由于各GPU全局访存空间有限, 缓冲区的预分配和初始化对设备间数据传输和同步、GPU缓存空间的优化尤为重要.
在Multi-GPU的数据初始化阶段, ChattyGraph对各GPU设备一个发送缓冲区和两个接收缓冲区. 此外, 考虑到顶点值数据的持续读写更新, ChattyGraph采用全局顶点值数组, 用以记录每一轮迭代顶点的计算值. 在每一轮GPU计算迭代轮开始之前, 各GPU设备都会从接收缓冲区中将上一轮迭代从其他设备中接收到的顶点值更新进全局顶点值数组, 并从全局顶点值数组中取出所需要的顶点进行计算过程. 最终迭代轮的计算结果仍保存于全局顶点值数组中, 同时将更新后边界顶点填充进发送缓冲区中, 等待同步通信.
为了实现多任务的并行执行, ChattyGraph通过设置发送和接收缓冲区可以提升GPU设备间的数据移动性能. 双接收缓冲区保证GPU在更新时不会因读写冲突而写入脏值. 因为多设备异步计算的原因, 多设备间执行步骤相同, 但执行速度不同. 假设当设备
在CPU和GPU协同计算方面, 现有Multi-GPU图并行计算系统常采用单核控制多设备的编程模式. 然而, 我们发现: 现有并行计算系统中常会出现阻塞点, 限制多GPU高性能并行. 以指令顺序为基础, 在顶点的计算指令中, 不仅要得到每个顶点的计算更新值, 还需要统计通信量大小. 而不管是显式的P2P传输CUDAMemcpyPeerAsync还是NCCL通信库中的ncclBroadcast, 其API接口
为了解决阻塞点问题, ChattyGraph摈弃了传统单核控制多设备的编程模式, 提出了多核控制多设备机制.具体地, ChattyGraph采用OpenMP多核编程框架以控制多线程计算, 每一个线程控制对应GPU的核函数调度(第3行), 最终实现多GPU与CPU多核处理器间的协同并行处理(如
单核与多核控制多设备时CPU指令流顺序对比
计算引擎主要负责顶点在GPU中的计算过程. 在计算过程中, 为了尽可能地减少GPU间通信量, 采用仅通信更新的边界顶点. 如何确定系统中更新的边界顶点分为以下两步.
● 在图划分过程中, 首先标记边界顶点, 边界顶点的定义是: 一条边的两端顶点不在同一个分区中, 则两点属于边界顶点. 遍历所有边集, 判断具体边的源顶点和目的顶点是否跨GPU设备, 即边的源顶点和目的顶点不在同一个分区(GPU设备), 则标记为边界顶点;
● 在计算过程中, 对更新顶点进行标记. 以CUDA Warp-Level原语支持的集体操作为基础, 通过线程来计算每一个顶点的值, 32个线程为一个warp, 并以一个warp作为一个单元. ChattyGraph中涉及的原语如下:
首先, __any_sync确定32个线程中更新了哪几个线程, __ballot_sync将其转换为32位01序列. 在序列化的支持下, __popc可以统计一个warp中更新顶点的数量并记录其位置, 最终将标记了更新位和边界位的顶点的位置与其值填充进输出缓冲区中.
● 实验平台
在配置8块互联互通的NVIDIA V100 GPU协处理器的NVIDIA DGX服务器上进行验证实验. 每个GPU有5 120个流式多处理器、32 GB全局内存和768 KB二级缓存. 该系统还包括两个64核Intel(R) Xeon(R) CPU Platinum 8163(2.5 Hz)和256 GB DDR4主内存, 运行Ubuntu 16.04(内核4.15.0)和CUDA 10.0. 整体实验平台NVIDIA DGX服务器的连接性如
● 图数据集
数据集特征
数据集 | 顶点数 | 边数 | 大小(GB) |
soc-LiveJournal1[ |
4 847 584 | 68 993 773 | 1 |
USA-road[ |
23 947 360 | 58 333 344 | 1.2 |
osm-eur[ |
173 789 216 | 347 997 111 | 7.08 |
Twitter[ |
61 578 432 | 1 468 365 182 | 24.37 |
● 基准测试集
为了进行更为全面和公平的比较, 本文选择了3种标准的图计算和遍历算法进行系统评估, 包括单源最短路径(SSSP)、广度优先搜索(BFS)和PageRank(PR). 我们在性能、可扩展性等指标中展示了这3种算法的运行时间(每类算法运行10次取平均值).
● 对比系统
本文的对比系统选用当前最先进的GPU图数据并行计算系统(WS-VR, Groute)来进行评估, 并分别报告各自系统的整体执行性能、分阶段执行性能、系统可扩展性、运行时间、冗余工作负载减少以及延迟度量. 上述两种系统与ChattyGraph都使用相同的平台(NVIDIA DGX)进行评估, 并提供对比数据.
首先, 我们对ChattyGraph和当前Multi-GPU图数据并行计算系统(Groute和WS-VR)进行性能比较. 通过对比遍历和计算应用(SSSP和PageRank)的性能结果, 从
先进图计算系统对比
数据集 | 算法 | GPU数量 | WSVR | Groute | ChattyG |
USA-road | SSSP | 1 | 10 415.3 | 33 261.37 | 10 406.8 |
2 | 5 814.39 | 22 565.26 | 5 478.73 | ||
3 | 5 952.88 | 18 749.16 | 4 359.85 | ||
4 | 6 234.02 | 18 158.48 | 3 820.02 | ||
5 | 8 829.48 | 16 751.32 | 9 012.92 | ||
6 | 10 406.9 | 18 212.56 | 4 566.57 | ||
7 | 13 029.6 | 16 384.66 | 4 418.74 | ||
8 | 14 711.8 | 15 825.89 | 4 045.44 | ||
USA-road | PageRank | 1 | 39.693 | 428.875 | 39.684 |
2 | 20.016 | 214.366 | 24.08 | ||
3 | 20.515 | 138.486 | 23.662 | ||
4 | 23.178 | 106.844 | 23.872 | ||
5 | 34.765 | 86.882 | 27.226 | ||
6 | 32.348 | 78.635 | 27.135 | ||
7 | 35.576 | 72.392 | 28.691 | ||
8 | 42.68 | 70.535 | 31.554 | ||
PageRank | 1 | 19 751.5 | 13 762.296 | 18 051.7 | |
2 | 18 804.2 | 9 772.269 | 17 507.7 | ||
3 | 8 632.92 | 8 104.444 | 8 615.4 | ||
4 | 8 596.6 | 7 970.716 | 8 488.03 | ||
5 | 7 864.87 | 8 954.205 | 7 766.54 | ||
6 | 7 800.82 | 8 021.378 | 7 488.87 | ||
7 | 7 830.87 | 6 999.526 | 7 669.34 | ||
8 | 6 470.85 | 7 705.487 | 5 954.21 | ||
LiveJournal | PageRank | 1 | 781.653 | 230.665 | 781.328 |
2 | 402.4 | 242.332 | 417.014 | ||
3 | 259.677 | 258.378 | 229.693 | ||
4 | 306.863 | 281.903 | 270.467 | ||
5 | 308.234 | 598.843 | 276.369 | ||
6 | 273.666 | 1 068.281 | 230.799 | ||
7 | 256.483 | 1 478.873 | 225.335 | ||
8 | 251.955 | 2 144.472 | 198.01 |
ChattyGraph与先进图计算系统扩展性对比
此外, 需要额外注意的是: 随着GPU设备数量的增加, ChattyGraph实现了比其他两个系统更高的加速比(在8GPU下平均3.8×). 从SSSP应用程序上的这些结果可以看出: ChattyGraph在该图遍历算法中实现了更好的性能和更高的可扩展性, 执行加速比分别对比Groute和WSVR达到了4.48×和1.8×的提升.
从对这3个数据集的PageRank标准测试来看, ChattyGraph也表现出良好的性能和可扩展性. 尽管ChattyGraph对Twitter图数据的效率不如Groute和WS-VR, 但在扩展到多个GPU设备时, ChattyGraph仍然实现了更好的可扩展性. 例如,
为了进一步评估ChattyGraph的可伸缩性, 我们评估了其他算法和数据集上的可伸缩性, 即BFS在USA- road图和SSSP在osm-eur图(如
进一步, 考虑到具体的策略针对Multi-GPU下的设备间通信展开, 本文对ChattyGraph的通信量优化进行了深入的分析. 从通信量优化的实验结果(
更新顶点与通信顶点数量对比
从
为了比较单核与多核控制多设备对系统可扩展性的影响, 我们分别比较了Peer-to-Peer Broadcast, UVA Broadcast(WS-VR)和NCCL Broadcast在有无OpenMP下的图计算时间, 以下实验都以USA-road为例运行SSSP基准测试.
OpenMP对扩展性分析
为了观察将系统ChattyGraph的图数据处理过程从一个GPU扩展到多个GPU的效果, 通过比较UVA, NCCL和p2pBroadcast这3种通信技术, 对USA-road, eur-osm和LiveJournal这3种图数据在ChattyGraph中进行评估, 并说明从1GPU扩展到8GPU时的性能.
从
多种通信方式对扩展性分析
在这项工作中, 本文提出了ChattyGraph, 一种新型的面向多协处理器高性能环境的大规模图数据并行计算系统, 用于在当前HPC节点上实现与现代总线链路互联互通的GPU设备集成的高可扩展图数据计算. 从目前最先进的Multi-GPU图并行计算技术来看, 当前的系统仍然存在以下缺陷: (1) 无法充分利用GPU的高通量连接性; (2) 通常采用过于单一的设备间数据组织和移动策略. ChattyGraph采用混合通信运行时技术, 以结合最小化通信开销, 从而为Multi-GPU图计算并行系统提供了高可扩展性支持, 充分利用现代GPU链路技术的高带宽和低时延特性. 在大规模真实图数据和标准测试集上的结果表明: ChattyGraph相比WSVR和Groute在性能和可扩展性上均实现了显著改进, 并且随着GPU数量的增加和图数据规模的扩大, ChattyGraph可以更为高效地扩展. 未来的工作将围绕分布式多协处理器的高性能环境展开, 拟充分利用现代网络链路技术, 以进一步提升ChattyGraph的计算性能和应用范围.
Ben-Nun T, Sutton M, Pai S,
Fu ZS, Personick M, Thompson B. Mapgraph: A high level API for fast development of high performance graph analytics on GPUs. In: Proc. of the Workshop on GRAph Data Management Experiences and Systems. ACM, 2014. 1-6.
Pan YC, Wang YZH, Wu YD,
Khorasani F, Vora K, Gupta R,
Wu YD, Wang YZH, Pan YC,
Ben-Nun T, Levy E, Barak A,
Adar E, Re C. Managing uncertainty in social networks. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2007, 30(2): 15-22.
Kwak H, Lee C, Park H,
Shirahata K, Sato H, Matsuoka S. Out-of-Core GPU memory management for MapReduce-based large-scale graph processing. In: Proc. of the 2014 IEEE Int'l Conf. on Cluster Computing (CLUSTER). 2014. 221-229.
Sengupta D, Song SL, Agarwal K,
Zhong JL, He BS. Medusa: Simplified graph processing on GPUs. IEEE Trans. on Parallel and Distributed Systems, 2014, 25(6): 1543-1552.
Khorasani F, Gupta R, Bhuyan LN. Scalable SIMD-efficient graph processing on GPUs. In: Proc. of the 2015 Int'l Conf. on Parallel Architecture and Compilation (PACT). 2015. 39-50. [
Kyrola A, Blelloch G, Guestrin C. GraphChi: Large-scale graph computation on just a PC. In: Proc. of the 10th USENIX Symp. on Operating Systems Design and Implementation (OSDI 2012). 2012. 31-46.
Hong S, Kim SK, Oguntebi T,
Naumov M, Vrielink A, Garland M. Parallel depth-first search for directed acyclic graphs. In: Proc. of the 7th Workshop on Irregular Applications: Architectures and Algorithms. 2017. 1-8.
Liu H, Huang HH. Enterprise: Breadth-first graph traversal on GPUs. In: Proc. of the Int'l Conf. for High Performance Computing, Networking, Storage and Analysis. 2015. 1-12.
Wang TT, Rong CT, Lu W,
王童童, 荣垂田, 卢卫, 等. 分布式图处理系统技术综述. 软件学报, 2018, 29(3): 569-586. http://www.jos.org.cn/1000-9825/5450.htm[doi:10.13328/j.cnki.jos.005450]
Zhang CB, Li Y, Jia T. Survey of state-of-the-art fault tolerance for distributed graph processing jobs. Ruan Jian Xue Bao/Journal of Software, 2021, 32(7): 2078-2102(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/6269.htm[doi:10. 13328/j.cnki.jos.006269]
张程博, 李影, 贾统. 面向分布式图计算作业的容错技术研究综述. 软件学报, 2021, 32(7): 2078-2102. http://www.jos.org.cn/1000-9825/6269.htm[doi:10.13328/j.cnki.jos.006269]
Wang YZH, Davidson A, Pan YC,
Li A, Song SL, Chen JY,
Tran HN, Kim JJ, He BS. Fast subgraph matching on large graphs using graphics processors. In: Proc. of the Int'l Conf. on Database Systems for Advanced Applications. Springer, 2015. 299-315.
Busato F, Bombieri N. BFS-4K: An efficient implementation of BFS for kepler GPU architectures. IEEE Trans. on Parallel and Distributed Systems, 2015, 26(7): 1826-1838.
Merrill D, Garland M, Grimshaw A. High-performance and scalable GPU graph traversal. ACM Trans. on Parallel Computing, 2015, 1(2): 14.
Djidjev H, Chapuis G, Andonov R,
Martinasso M, Kwasniewski G, Alam SR,
Merrill D, Garland M, Grimshaw A. Scalable GPU graph traversal. In: Proc. of the ACM SIGPLAN Notices, Vol. 47. ACM, 2012. 117-128.
Narayanan D, Harlap A, Phanishayee A,
Wang GH, Venkataraman S, Phanishayee A,
Wang J, Zhang L, Wang PY,
王靖, 张路, 王鹏宇, 等. 面向图计算的内存系统优化技术综述. 中国科学: 信息科学, 2019, 49(3): 295-313. [doi:10.1360/N112018-00281]
Wang P, Wang J, Li C,
Stanford large network dataset collection.
9th DIMACS implementation challenge.
Karlsruhe Institute of Technology.
Cha M, Haddadi H, Benevenuto F,