目录
第 1章引言 .......................................................................................1
1.1大规模图计算 .........................................................................1
1.2图计算系统的分类 ...................................................................2
1.3图数据高效计算的挑战 ............................................................5
1.3.1图计算的特点 ...............................................................6
1.3.2现状和主要优化方向 .....................................................7
1.4主要贡献 ................................................................................9
1.5本书组织结构 ....................................................................... 11
第 2章相关工作 ............................................................................... 13
2.1基于分布式集群的图计算系统 ................................................ 13
2.1.1分布式图计算中的基本概念 ......................................... 13
2.1.2分布式图计算中任务的划分算法 .................................. 15
2.2基于外存的图计算系统 .......................................................... 18
2.2.1外存图计算系统的意义和挑战 ..................................... 18
2.2.2以点为中心的外存图计算系统 ..................................... 20
2.2.3以边为中心的外存图计算系统 ..................................... 21
2.3基于矩阵的图计算引擎 .......................................................... 23
2.4基于存算融合硬件的图计算系统 ............................................. 26
第 3章分布式图计算系统的三维任务划分 .......................................... 31
3.1概述 ..................................................................................... 31
3.2实例研究：协同过滤问题 ....................................................... 33
3.3三维划分的基本概念 ............................................................. 34
3.4三维划分下的编程模型 .......................................................... 37
3.4.1数据模型 ................................................................... 37
3.4.2 UPPS下的三维划分 ................................................... 39
3.4.3计算模型 ................................................................... 40
3.4.4二部图 ....................................................................... 41
3.4.5与 GAS模型的比较 .................................................... 41
3.4.6例程 .......................................................................... 42
3.5系统实现 .............................................................................. 47
3.5.1数据载入和划分 ......................................................... 47
3.5.2 Update操作的实现 .................................................... 48
3.5.3 Push，Pull和 Sink操作的实现 ................................... 49
3.5.4基于矩阵的数据结构 ................................................... 49
3.6实验结果 .............................................................................. 50
3.6.1测试环境 ................................................................... 51
3.6.2微型测试集 ................................................................ 52
3.6.3实际应用 ................................................................... 57
3.6.4其他讨论 ................................................................... 62
3.7小结 ..................................................................................... 66
第 4章外存图计算系统的分层数据组织 ............................................. 67
4.1概述 ..................................................................................... 67
4.2背景介绍 .............................................................................. 69
4.2.1外存图计算系统中的一维划分： GraphChi .................... 69
4.2.2外存图计算系统中的二维划分： GridGraph.................... 70
4.3 3DGridGraph ........................................................................ 72
4.3.1分层存储优势 ............................................................. 72
4.3.2编程模型 ................................................................... 74
4.3.3实例研究 ................................................................... 75
4.3.4实现 .......................................................................... 76
4.4测试结果 .............................................................................. 77
4.4.1定量分析 ................................................................... 77
目录 15
4.4.2实测结果 ................................................................... 78
4.5小结 ..................................................................................... 79
第 5章矩阵计算引擎的自动优化 ....................................................... 81
5.1概述 ..................................................................................... 81
5.1.1背景介绍 ................................................................... 81
5.1.2挑战 .......................................................................... 82
5.1.3我们的工作 ................................................................ 83
5.2设计思路与原理 .................................................................... 84
5.3 Kasen的编程模型 ................................................................ 86
5.3.1数据 .......................................................................... 86
5.3.2数据的操作 ................................................................ 87
5.3.3实例： PageRank ........................................................ 89
5.3.4应用范围 ................................................................... 90
5.4 Kasen模型的具体实现 ......................................................... 91
5.4.1三种数据存储状态 ...................................................... 91
5.4.2显式的存储状态转化 ................................................... 93
5.4.3约束条件 ................................................................... 94
5.5优化方法 .............................................................................. 96
5.5.1循环融合 ................................................................... 96
5.5.2内部操作 ................................................................... 98
5.5.3 DDAG...................................................................... 100
5.5.4优化算法 ................................................................. 101
5.5.5实例研究 ................................................................. 104
5.6估算公式 ............................................................................ 105
5.7实现细节 ............................................................................ 107
5.8性能测试 ............................................................................ 108
5.8.1定量分析 ................................................................. 108
5.8.2性能测试 ................................................................. 110
5.8.3与已有系统的性能对比 ............................................. 112
5.9小结 ................................................................................... 113
第 6章拓扑感知的存算融合图计算方法 ........................................... 115
6.1概述 ................................................................................... 115
6.2背景介绍 ............................................................................ 118
6.2.1互联拓扑结构 ........................................................... 118
6.2.2网络瓶颈 ................................................................. 120
6.2.3已有的 PIM图计算系统 ............................................ 121
6.3 PGIM系统 ........................................................................ 123
6.3.1两阶段点程序 ........................................................... 123
6.3.2广播 ........................................................................ 128
6.3.3计算和通讯的重合 .................................................... 129
6.4测试 ................................................................................... 129
6.4.1划分对通讯量的影响 ................................................. 130
6.4.2广播对瓶颈链路通讯量的影响 ................................... 131
6.5小结 ................................................................................... 131
第 7章总结与展望 ......................................................................... 133
7.1总结 ................................................................................... 133
7.2展望 ................................................................................... 134
参考文献 ........................................................................................... 137
在学期间发表的学术论文与研究成果 ................................................... 145
致谢 .................................................................................................. 147
