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

　　图计算研发能力的核心是掌握各类图算法的运行时特征和挑战，在系统掌握基本图计算优化技术原理的基础上，进一步实现图计算硬件器、图计算系统以及上层图应用。本书内容包括图计算概述、图计算编程与执行、图计算优化技术、图计算系统软件加速技术、图计算硬件加速技术、图计算性能评测，以及图计算发展趋势与展望7个部分，系统性地梳理图计算背景、图计算关键技术和发展趋势等知识。本书主要用于给计算机科学与技术、集成电路等学科研究生提供图计算技术的教学和学术资源，也可以作为 计算机系统结构、并行与分布式计算等研究生课程补充教材，还适合相关科研人员和产业界工程师阅读，推动我国在图计算基础理论、关键技术，以及行业应用方面的发展，取得 有影响力的科研和应用成果。

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

前言第1章 图计算背景 11.1图计算简介 11.1.1 图的基本概念 21.1.2 图遍历简介 21.1.3 图挖掘简介 51.1.4 图学习简介 81.2常见图算法 101.2.1 图遍历类算法 101.2.2 图挖掘类算法 171.2.3 图学习类算法 311.3图计算应用案例 471.3.1 图遍历应用案例 471.3.2 图挖掘应用案例 511.3.3 图学习应用案例 581.4本章小结 641.5习题1 65参考文献 65第2章 图计算编程与执行 692.1图数据存储和 新 692.1.1 静态图数据存储 692.1.2 动态图数据存储与 新 762.2图计算编程示例 1062.2.1 图遍历类算法编程示例 1062.2.2 图挖掘类算法编程示例 1112.2.3 图神经网络算法编程示例 1152.3图计算运行时特征和挑战 1202.3.1 图遍历运行时特征及挑战 1202.3.2 图挖掘运行时特征及挑战 1212.3.3 图学习训练和推理运行时特征及挑战 1222.4本章小结 1232.5习题2 123参考文献 124第3章 图计算优化技术 1273.1主流的并行编程模型 1273.1.1 图遍历并行编程模型 1273.1.2 图挖掘并行编程模型 1343.1.3 图学习并行编程模型 1363.2图预处理方法 1393.2.1 图划分策略 1393.2.2 图数据重排策略 1443.3图并行执行模型 1473.3.1 图并行执行基本概念 1473.3.2 主流的图并行执行模型 1483.4图顶点状态同步策略 1513.4.1 同步/异步状态传递机制 1513.4.2 Pull/Push状态同步机制 1523.4.3 通信优化策略 1543.4.4 图数据缓存策略 1553.5图计算负载均衡策略 1573.5.1 负载均衡简介 1573.5.2 单机负载均衡策略 1593.5.3 分布式负载均衡策略 1633.6图计算容错机制 1633.6.1 有状态的容错机制 1663.6.2 无状态的容错机制 1703.7本章小结 1763.8习题3 176参考文献 176第4章 图计算系统软件加速技术 1804.1图计算系统软件加速技术背景 1804.2单机图计算系统 1814.2.1 单机内存图计算系统 1814.2.2 单机外存图计算系统 1914.3分布式图计算系统 1994.3.1 分布式内存图处理系统 1994.3.2 分布式外存图处理系统 2144.4基于GPU的图计算系统加速技术 2154.4.1 GPU背景介绍 2154.4.2 GPU存内图计算系统 2194.4.3 单机CPU-GPU异构图计算系统 2364.4.4 单机多GPU图计算系统 2454.4.5 多机GPU图计算系统 2514.5 本章小结 2654.6 习题4 265参考文献 266第5章 图计算硬件加速技术 2705.1基于FPGA的图计算加速技术 2705.1.1 FPGA背景介绍 2705.1.2 主流FPGA图计算加速器 2745.2基于ASIC的图计算加速器 2995.2.1 ASIC背景介绍 2995.2.2 主流ASIC图计算加速器 2995.3基于PIM的图计算加速技术 3575.3.1 PIM背景介绍 3575.3.2 主流的基于PIM的图计算加速器 3585.4基于RERAM的图计算硬件加速技术 3685.4.1 ReRAM背景介绍 3685.4.2 主流的基于ReRAM的图计算加速器 3695.5本章小结 4145.6习题5 414参考文献 414第6章 图计算性能评测 4196.1 GRAPH 500 性能评测和优化 4196.1.1 Graph 500性能评测 4196.1.2 Graph 500的 BFS和SSSP算法优化 4216.2 GREEN GRAPH 500 性能功耗比评测与优化 4266.3 图学习OGB精度评测和优化 4296.3.1 OGB数据集简介 4296.3.2 OGB 依赖库与运行 4316.3.3 OGB顶点属性预测 4326.3.4 OGB链接属性预测 4346.3.5 OGB图属性预测 4366.3.6 OGB算法优化 4376.4本章小结 4396.5习题6 439参考文献 440第7章 图计算发展趋势与展望 4427.1图遍历发展趋势与展望 4427.2图挖掘发展趋势与展望 4437.3图学习发展趋势与展望 4457.4本章小结 446