图计算技术:深入理解图计算架构、系统和应用

张宇

华中科技大学副教授，2016年6月博士毕业于华中科技大学，入选2022年国家重大人才工程青年学者和2022年湖北省青年拔尖人オ培养计划，长期从事高性能图计算研究，主持国家自然科学基金、湖北省重点研发、华为项目等10余项，研制的高性能图计算引擎性能指标屡次打破国际图计算权威榜单世界纪录，应用于华为等多家龙头企业，曾获2022年CCF高性能计算“卓越青年”、2022年中国智能计算科技创新人物、2022年ACM中国新星奖（全国奖）等荣誉，指导学生获第七届中国国际“互联网+”大学生创新创业大赛全国金奖、第十三届“挑战杯”中国大学生创业计划竞赛全国金奖、国际顶级图学习OGB榜单全球冠军等。

前言

第1章 图计算背景

1.1 图计算简介

1.1.1 图的基本概念

1.1.2 图遍历简介

1.1.3 图挖掘简介

1.1.4 图学习简介

1.2 常见图算法

1.2.1 图遍历类算法

1.2.2 图挖掘类算法

1.2.3 图学习类算法

1.3 图计算应用案例

1.3.1 图遍历应用案例

1.3.2 图挖掘应用案例

1.3.3 图学习应用案例

1.4 本章小结

1.5 习题

参考文献

第2章 图计算编程与执行

2.1 图数据存储和更新

2.1.1 静态图数据存储

2.1.2 动态图数据存储与更新

2.2 图计算编程示例

2.2.1 图遍历类算法编程示例

2.2.2 图挖掘类算法编程示例

2.2.3 图神经网络算法编程示例

2.3 图计算运行时征和挑战

2.3.1 图遍历运行时征及挑战

2.3.2 图挖掘运行时征及挑战

2.3.3 图学习和推理运行时征及挑战

2.4 本章小结

2.5 习题

参考文献

第3章 图计算优化技术

3.1 主流的并行编程模型

3.1.1 图遍历并行编程模型

3.1.2 图挖掘并行编程模型

3.1.3 图学习并行编程模型

3.2 图预处理方法

3.2.1 图划分策略

3.2.2 图数据重排策略

3.3 图并行执行模型

3.3.1 图并行执行基本概念

3.3.2 主流的图并行执行模型

3.4 图顶点状态同步策略

3.4.1 同步/异步状态传递机制

3.4.2 Pull/Push状态同步机制

3.4.3 通信优化策略

3.4.4 图数据缓存策略

3.5 图计算负载均衡策略

3.5.1 负载均衡简介

3.5.2 单机负载均衡策略

3.5.3 分布式负载均衡策略

3.6 图计算容错机制

3.6.1 有状态的容错机制

3.6.2 无状态的容错机制

3.7 本章小结

3.8 习题

参考文献

第4章 图计算系统软件加速技术

4.1 图计算系统软件加速技术背景

4.2 单机图计算系统

4.2.1 单机内存图计算系统

4.2.2 单机外存图计算系统

4.3 分布式图计算系统

4.3.1 分布式内存图处理系统

4.3.2 分布式外存图处理系统

4.4 基于GPU的图计算系统加速技术

4.4.1 GPU背景介绍

4.4.2 GPU存内图计算系统

4.4.3 单机CPU-GPU异构图计算系统

4.4.4 单机多GPU图计算系统

4.4.5 多机GPU图计算系统

4.5 本章小结

4.6 习题

参考文献

第5章 图计算硬件加速技术

5.1 基于FPGA的图计算加速技术

5.1.1 FPGA背景介绍

5.1.2 主流FPGA图计算加速器

5.2 基于ASIC的图计算加速器

5.2.1 ASIC背景介绍

5.2.2 主流ASIC图计算加速器

5.3 基于PIM的图计算加速技术

5.3.1 PIM背景介绍

5.3.2 主流的基于PIM的图计算加速器

5.4 基于RERAM的图计算硬件加速技术

5.4.1 ReRAM背景介绍

5.4.2 主流的基于ReRAM的图计算加速器

5.5 本章小结

5.6 习题

参考文献

第6章 图计算性能评测

6.1 GRAPH500性能评测和优化

6.1.1 Graph500性能评测

6.1.2 Graph500的BFS和SSSP算法优化

6.2 GREENGRAPH500性能功耗比评测与优化

6.3 图学习OGB精度评测和优化

6.3.1 OGB数据集简介

6.3.2 OGB依赖库与运行

6.3.3 OGB顶点属性预测

6.3.4 OGB链接属性预测

6.3.5 OGB图属性预测

6.3.6 OGB算法优化

6.4 本章小结

6.5 习题

参考文献

第7章 图计算发展趋势与展望

7.1 图遍历发展趋势与展望

7.2 图挖掘发展趋势与展望

7.3 图学习发展趋势与展望

7.4 本章小结

图计算研发能力的核心是掌握各类图算法的运行时特征和挑战，在系统掌握基本图计算优化技术原理的基础上，进一步实现图计算硬件器、图计算系统以及上层图应用。本书内容包括图计算概述、图计算编程与执行、图计算优化技术、图计算系统软件加速技术、图计算硬件加速技术、图计算性能评测，以及图计算发展趋势与展望7个部分，系统性地梳理图计算背景、图计算关键技术和发展趋势等知识。

本书主要用于给计算机科学与技术、集成电路等学科研究生提供图计算技术的教学和学术资源，也可以作为高级计算机系统结构、并行与分布式计算等研究生课程补充教材，还适合相关科研人员和产业界工程师阅读，推动我国在图计算基础理论、关键技术，以及行业应用方面的发展，取得更有影响力的科研和应用成果。