面向高性能图计算:以硬件/软件协同设计的视角
Towards High-Performance Graph Processing: From a Hardware/Software Co-Design Perspective
-
摘要:背景 图在现代社会中扮演了至关重要的角色,它被普遍应用于构建和解析复杂的关系与实体网络。通过深入分析和算法设计,研究者能够从图中提取出重要且具启发性的信息。目前,图已在众多领域得到应用,涉及推荐系统、脑科学网络分析、电力网调度及网络安全等多个重要场景。动机 尽管如此,大规模图数据的高效处理仍是一项颇具挑战的任务。图结构具有稀疏性,即节点间的连接很少,且依附于同一节点的边的数量通常遵循幂律分布,这使得图计算表现出不规则的并行性和随机的内存访问模式。因此,使用传统的计算机体系结构(如CPU和GPU)来执行图计算任务往往效率不高,有时其表现甚至不如专用的单线程图算法。为了提高图计算的效率,采用针对特定领域设计的硬件加速器至关重要。然而,仅凭硬件优化还不足以实现性能的显著提升,与之配合的软件系统设计同样关键,这样才能将硬件潜力充分转化为实际的性能增益。解决方案 为应对上述挑战,我们提出了一个硬件与软件协同设计的图计算加速方案。正如图1中展示的那样,这一方案为图计算任务提供了一个全面的解决策略,涉及从硬件设计到软件系统的各个层面。该方案的目标在于打造一个具备高吞吐、低延迟、低能耗,并且能够灵活扩展的图计算架构,以此提升图计算任务的效率和可行性。具体设计 在硬件设计方面,我们专门针对不同存储架构研发了多样化的图计算加速器。例如,一个DRAM版本的加速器AccuGraph通过引入独特的冲突合并单元,针对图数据处理中的冲突问题提供了一种创新性解决方案。此外,本文基于高带宽内存设计了新型的加速器架构,如ScalaBFS2和ScalaGraph,这不仅提升了加速器对高带宽内存 (HBM) 的使用效率,还大幅增强了处理单元的可扩展性。在软件系统设计方面,我们注重优化图计算的效率,确保能够最大限度地利用硬件资源。我们开发了一系列软件库,如HotGraph/GraphFly/CGraph、DiGraph、GraSu、FBSGraph等,它们分别针对不同的硬件平台:CPU、GPU、FPGA以及分布式系统。这些软件库通过对数据结构和任务调度策略的优化,进一步增强了图计算系统的并行性和数据局部性。随着近年来图计算任务的不断演进和新型计算机体系结构的涌现,现有图计算体系结构面临了新的挑战。针对图的构建、超图计算和异构图计算等新兴任务,我们提出了多个硬件与软件协同设计的解决方案,如FNNG、XuLin、MetaNMP等。为了发挥新兴体系结构的优势,我们还设计了基于ReRAM和CMOS的图计算方案,包含Spara、ReFlip、HETRAPHE等,这些方案实现了更高的数据处理效率和并行能力,显著提升了图计算任务的整体性能。总结与展望 本文专注于图计算体系结构的高效实现,它包含硬件加速器和软件优化,提高了处理速度,降低了能耗。硬件上,我们有新设计来高效处理图数据;软件上,我们为不同计算平台提供了特别优化的程序库。同时,我们还准备了解决方案来应对新出现的图计算需求。总之,本文的解决方案让图计算更快、更节能。Abstract: Graph processing has been widely used in many scenarios, from scientific computing to artificial intelligence. Graph processing exhibits irregular computational parallelism and random memory accesses, unlike traditional workloads. Therefore, running graph processing workloads on conventional architectures (e.g., CPUs and GPUs) often shows a significantly low compute-memory ratio with few performance benefits, which can be, in many cases, even slower than a specialized single-thread graph algorithm. While domain-specific hardware designs are essential for graph processing, it is still challenging to transform the hardware capability to performance boost without coupled software codesigns. This article presents a graph processing ecosystem from hardware to software. We start by introducing a series of hardware accelerators as the foundation of this ecosystem. Subsequently, the codesigned parallel graph systems and their distributed techniques are presented to support graph applications. Finally, we introduce our efforts on novel graph applications and hardware architectures. Extensive results show that various graph applications can be efficiently accelerated in this graph processing ecosystem.