戴国浩：快速高能效大规模图计算架构设计方法研究

戴国浩：清华大学2019年度优秀博士学位论文获奖者

快速高能效大规模图计算架构设计方法研究

Key Technologies of Fast and Energy-efficient Large-scale Graph Processing Architectures

作 者：戴国浩

指导教师：汪玉

培养院系：电子工程系

学 科：电子科学与技术

读博感言：慢慢来，一切都来得及

研究背景/选题意义/研究价值

随着大数据时代的到来，图数据规模不断扩大，从而给图计算系统和架构的数据分析能力提出了巨大挑战。随着CMOS工艺尺寸下降速度逐步放缓，提升传统冯·诺依曼架构下系统与架构处理速度与能效的途径主要包括异构多核加速和新器件映射两条。然而大规模图计算问题具有非结构化、高传输计算比、负载不均衡、本地性差等特点。因此，本文将针对从应用算法到电路器件设计中每个层面的关键问题，沿着异构多核加速和新器件映射两条设计途径，研究快速高能效大规模图计算架构设计方法。

主要研究内容

大规模图计算系统性能提升核心是提升数据在计算与存储单元间的搬运效率。本文从电路系统设计中算法到器件各层面展开研究：

1. 从算法层到系统层，访存序列优化方法与异构高能效存储系统设计方法；

2. 从系统层到架构层，细粒度并行图加速器设计方法与划分方法；

3. 从架构层到器件层，新兴非冯·诺依曼器件大规模图计算映射方法。

论文主要研究内容的层次关系。为提升图数据在计算和存储单元间的搬运效率，本文从顶层算法到底层器件各个层面的具体研究内容。

主要创新点

1. 提出了一种FPGA片上细粒度并行图计算架构设计方法，基于节点索引重映射解决负载不均衡的问题，达到同时期最好FPGA方案吞吐率1.4至2.6倍。

2. 提出了一种多级异构图存储系统设计方法，根据点与边数据访存模式差异在异构存储器件上进行映射，相对于传统CPU+DRAM架构能效提升114倍。

3. 提出了一种基于多个混合立方存储的近存储图计算架构，采用点缓存和数据冲突调度等技术，相对传统CPU+DRAM架构速度提升2个数量级。

4. 提出了一种存算一体图计算架构和密度感知图划分方法，降低存储开销，提升忆阻器阵列图计算能效，达到同平台速度1.85倍，能效4.43倍。

代表性创新成果

1.[IEEE ToC] Guohao Dai, et al., HyVE: Hybrid Vertex-Edge Memory Hierarchy for Energy-Efficient Graph Processing, in IEEE Transactions on Computers, vol. 68, No. 8, pp. 1131-1146, 2019. （SCI收录，CCF-A类，影响因子3.131）

2.[IEEE TCAD] Guohao Dai, et al., “GraphH: A Processing-in-Memory Architecture for Large-scale Graph Processing”, in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, No. 4, pp. 640-653, 2019.（SCI收录， CCF-A类，影响因子2.402，谷歌学术引用16次）

3.[ASPDAC’ 19] Guohao Dai, et al., GraphSAR: A Sparsity-Aware Processing-in-Memory Architecture for Large-Scale Graph Processing on ReRAMs, in Asia and South Pacific Design Automation Conference

(ASP-DAC), 2019, pp.120-126. （大会最佳论文奖，2005年后清华首次获奖）

4.[FPGA’ 17] Guohao Dai, et al., ForeGraph: Exploring Large-scale Graph Processing on Multi-FPGA Architecture , in ACM International Symposium on FPGA (FPGA), 2017, pp.217-226. （FPGA领域顶级会议，谷歌学术引用34次）

5.[FPGA’ 16] Guohao Dai, et al., FPGP: Graph Processing Framework on FPGA, in ACM International Symposium on FPGA (FPGA), 2016, pp.105-110. (FPGA领域顶级会议，谷歌学术引用39次）

6.[DATE’ 18]Tianhao Huang,Guohao Dai, et al., HyVE: Hybrid Vertex-Edge Memory Hierarchy for Energy-Efficient Graph Processing, in Design, Automation & Test in Europe Conference & Exhibition (DATE), 2018, pp.973-978. （大会最佳论文奖提名，谷歌学术引用7次）

7.[ICDE’ 16]Yuze Chi,Guohao Dai, et al., NXgraph: An Efficient Graph Processing System on a Single Machine , in IEEE International Conference on Data Engineering (ICDE), 2016, pp.409-420. （CCF-A类，谷歌学术引用40次）

作者：戴国浩

供图：戴国浩

编辑：清华大学研究生院 吴佳瑛 李文

转载须经原作者同意授权