一种冗余感知的高能效图计算加速器

A redundancy-aware energy-efficient graph accelerator

图作为一种灵活表达对象之间关系的数据结构,广泛地应用于各类重要的现实场景.近年来,随着性能提升速度放缓,通用处理器逐渐无法满足图计算应用的需求,并成为限制图计算发展的主要瓶颈.因此,面向图计算的领域专用加速器成为近年来的研究热点.通过定制化的硬件设计,图计算加速器可以在图计算应用中取得通用处理器数十倍的性能.然而,现有的图计算加速器在运行宽度优先算法时会频繁地重复访问幂律顶点的相关数据,进而导致了严重的冗余访存问题.在特定场景下,现有的图计算加速器的性能甚至低于通用CPU.为了解决该问题,本文提出一种冗余感知的高能效图计算加速器JiFeng.当幂律顶点完成迭代计算时,JiFeng通过跳过剩余的相邻边大幅减少其被重复访问的次数.JiFeng实现了一系列软硬件协同设计,在保证负载均衡的同时提升硬件的执行效率.为了验证JiFeng的有效性,本文采用FPGA原型系统对相关设计进行性能评估.JiFeng在典型的生成图和现实图上实现最高每秒遍历4612亿条边的性能和每秒每瓦特遍历125亿条边的能效比,并在2023年11月的图计算超算排行榜GreenGraph500的小数据集榜单上取得第2名的成绩.

Graph plays an essential role in a wide range of real-world applications.Due to graph irregularity,general-purpose processors are not an ideal platform for graph processing.Therefore,there has been a significant interest in developing domain-specific accelerators for graph processing in the past few years.With dedicated hardware specialization,graph accelerators can deliver considerable performance speedups compared to CPUs and GPUs.However,existing graph accelerators perform unnecessary accesses on high-degree vertices when running BFS on power-law graphs,resulting in severe off-chip memory overheads.To solve the problem,we architect JiFeng,a redundancy-aware graph accelerator.When a high-degree vertex finishes execution,JiFeng aggressively skips all its edges to avoid redundant memory accesses.Several software/hardware co-designs are proposed to improve memory efficiency and load-balance.We have implemented JiFeng in RTL and evaluated it on a Xilinx Alveo U55C accelerator card.JiFeng achieves at most 461.2 GTEPS throughput and 12.5 GTEPS/W energy efficiency,and ranks 2nd in the SMALL DATA list of GreenGraph500.