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

A redundancy-aware energy-efficient graph accelerator

作　　者：姚鹏程 廖小飞[1,2,3,4] 金海[1,2,3,4] 周宇航[1,2,3,4] 徐鹏 张伟 曾圳 潘晨高 朱冰 Pengcheng YAO;Xiaofei LIAO;Hai JIN;Yuhang ZHOU;Peng XU;Wei ZHANG;Zhen ZENG;Chengao PAN;Bing ZHU(National Engineering Research Center for Big Data Technology and System,Huazhong University of Science and Technology,Wuhan 430074,China;Service Computing Technology and System Lab,Huazhong University of Science and Technology,Wuhan 430074,China;Cluster and Grid Computing Lab,Huazhong University of Science and Technology,Wuhan 430074,China;School of Computer Science and Technology,Huazhong University of Science and Technology,Wuhan 430074,China;Zhejiang Lab,Hangzhou 311121,China)

机构地区：[1]华中科技大学大数据技术与系统国家地方联合工程研究中心,武汉430074 [2]华中科技大学服务计算技术与系统教育部重点实验室,武汉430074 [3]华中科技大学集群与网格计算湖北省重点实验室,武汉430074 [4]华中科技大学计算机科学与技术学院,武汉430074 [5]之江实验室,杭州311121

出　　处：《中国科学：信息科学》2024年第6期1369-1385,共17页Scientia Sinica(Informationis)

基　　金：国家重点研发计划(批准号:2023YFB4502300);中国博士后科学基金(批准号:BX20230333,2023M743257,2023TQ0328,2023TQ0327);浙江省自然科学基金(批准号:LY24F020014)资助项目。

摘　　要：图作为一种灵活表达对象之间关系的数据结构,广泛地应用于各类重要的现实场景.近年来,随着性能提升速度放缓,通用处理器逐渐无法满足图计算应用的需求,并成为限制图计算发展的主要瓶颈.因此,面向图计算的领域专用加速器成为近年来的研究热点.通过定制化的硬件设计,图计算加速器可以在图计算应用中取得通用处理器数十倍的性能.然而,现有的图计算加速器在运行宽度优先算法时会频繁地重复访问幂律顶点的相关数据,进而导致了严重的冗余访存问题.在特定场景下,现有的图计算加速器的性能甚至低于通用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.

关 键 词：图计算 加速器 宽度优先搜索 冗余访存 FPGA 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]