1.1推动并行化 1
1.1.1计算能力因素——从晶体管到浮点运算速度 1
第1章 并行计算介绍 1
1.1.2内存及磁盘速度的因素 2
1.1.3数据通信因素 2
1.2并行计算适用范围 3
1.2.1在工程及设计中的应用 3
1.2.2科学计算中的应用 3
1.2.3商业应用 4
1.2.4计算机系统中的应用 4
1.3本书的组织及内容 4
1.4书目评注 6
习题 6
2.1隐式并行：微处理器体系结构的发展趋势 9
2.1.1流水线与超标量执行 9
第2章 并行编程平台 9
2.1.2超长指令字处理器 12
2.2内存系统性能的局限 12
2.2.1使用高速缓存改善有效内存延迟 13
2.2.2内存带宽的影响 14
2.2.3躲避内存延迟的其他方法 16
2.2.4多线程与预取间的权衡 17
2.3.1并行平台的控制结构 18
2.3并行计算平台剖析 18
2.3.2并行平台的通信模型 20
2.4并行平台的物理组织 22
2.4.1理想并行计算机的体系结构 22
2.4.2并行计算机互连网络 23
2.4.3网络拓扑结构 24
2.4.4静态互连网络评价 31
2.4.5动态互连网络评价 33
2.4.6多处理器系统中的高速缓存一致性 34
2.5.1并行计算机的消息传递成本 39
2.5并行计算机的通信成本 39
2.5.2共享地址空间计算机的通信成本 44
2.6互连网络的路由选择机制 46
2.7进程-处理器映射的影响和映射技术 47
2.7.1图的映射技术 48
2.7.2成本-性能平衡 53
2.8书目评注 54
习题 55
第3章 并行算法设计原则 63
3.1预备知识 63
3.1.1分解、任务与依赖图 63
3.1.2粒度、并发性与任务交互 65
3.1.3进程和映射 69
3.1.4进程与处理器 69
3.2分解技术 70
3.2.1递归分解 70
3.2.2数据分解 72
3.2.3探测性分解 77
3.2.4推测性分解 79
3.2.5混合分解 80
3.3任务和交互的特点 81
3.3.1任务特性 81
3.3.2任务间交互的特征 82
3.4负载平衡的映射技术 84
3.4.1静态映射方案 85
3.4.2动态映射方案 95
3.5包含交互开销的方法 96
3.5.1最大化数据本地性 97
3.5.2最小化争用与热点 98
3.5.3使计算与交互重叠 98
3.5.4复制数据或计算 99
3.5.5使用最优聚合交互操作 100
3.5.6一些交互与另一些交互的重叠 100
3.6.2任务图模型 101
3.6并行算法模型 101
3.6.1数据并行模型 101
3.6.3工作池模型 102
3.6.4主-从模型 102
3.6.5流水线模型或生产者-消费者模型 103
3.6.6混合模型 103
3.7书目评注 103
习题 103
第4章 基本通信操作 107
4.1一对多广播以及多对一归约 108
4.1.1环或线性阵列 108
4.1.2格网 110
4.1.3超立方体 111
4.1.4平衡二叉树 111
4.1.5算法细节 112
4.2多对多广播和归约 114
4.1.6成本分析 114
4.2.1线性阵列和环 115
4.2.2格网 117
4.2.3超立方体 117
4.2.4成本分析 120
4.3全归约与前缀和操作 121
4.4散发和收集 123
4.5多对多私自通信 125
4.5.1环 126
4.5.2格网 128
4.5.3超立方体 128
4.6循环移位 131
4.6.1格网 131
4.6.2超立方体 133
4.7提高某些通信操作的速度 135
4.7.1消息分裂和路由选择 135
4.7.2全端口通信 136
4.8小结 137
4.9书目评注 138
习题 139
第5章 并行程序的解析建模 143
5.1并行程序中的开销来源 143
5.2并行系统的性能度量 144
5.2.1执行时间 144
5.2.2总并行开销 144
5.2.3加速比 144
5.2.4效率 147
5.2.5成本 149
5.3粒度对性能的影响 149
5.4并行系统的可扩展性 152
5.4.1并行程序的扩展特性 153
5.4.2可扩展性的等效率度量 155
5.4.3成本最优性和等效率函数 158
5.5最小执行时间和最小成本最优执行时间 159
5.4.5并发度和等效率函数 159
5.4.4等效率函数的下界 159
5.6并行程序渐近分析 162
5.7其他可扩展性的度量 162
5.8书目评注 165
习题 166
第6章 使用消息传递模式编程 171
6.1消息传递编程的原理 171
6.2操作构件：发送和接收操作 172
6.2.1阻塞式消息传递操作 172
6.2.2无阻塞式消息传递操作 175
6.3MPI：消息传递接口 176
6.3.1启动和终止MPI库 177
6.3.2通信器 177
6.3.3获取信息 178
6.3.4发送和接收消息 178
6.3.5实例：奇偶排序 182
6.4.1创建和使用笛卡儿拓扑结构 184
6.4拓扑结构与嵌入 184
6.4.2实例：Cannon的矩阵与矩阵相乘 185
6.5计算与通信重叠 187
6.6聚合的通信和计算操作 191
6.6.1障碍 191
6.6.2广播 191
6.6.3归约 191
6.6.4前缀 193
6.6.5收集 193
6.6.6散发 194
6.6.7多对多 195
6.6.8实例：一维矩阵与向量相乘 195
6.6.9实例：单源最短路径 197
6.6.10实例：样本排序 199
6.7进程组和通信器 200
6.8书目评注 203
习题 204
7.1线程基础 205
第7章 共享地址空间平台的编程 205
7.2为什么要用线程 206
7.3POSIX线程API 207
7.4线程基础：创建和终止 207
7.5Pthreads中的同步原语 210
7.5.1共享变量的互斥 210
7.5.2用于同步的条件变量 216
7.6.1线程的属性对象 219
7.6控制线程及同步的属性 219
7.6.2互斥锁的属性对象 220
7.7线程注销 221
7.8复合同步结构 221
7.8.1读-写锁 222
7.8.2障碍 225
7.9设计异步程序的技巧 228
7.10.1OpenMP编程模型 229
7.10OpenMP：基于命令的并行编程标准 229
7.10.2在OpenMP中指定并发任务 232
7.10.3OpenMP中的同步结构 237
7.10.4OpenMP中的数据处理 240
7.10.5OpenMP库函数 241
7.10.6OpenMP中的环境变量 242
7.10.7显式线程与基于OpenMP编程的比较 243
7.11书目评注 243
习题 244
第8章 稠密矩阵算法 247
8.1矩阵向量乘法 247
8.1.1一维行划分 247
8.1.2二维划分 250
8.2矩阵与矩阵的乘法 253
8.2.1简单的并行算法 254
8.2.2Cannon算法 254
8.2.3DNS算法 256
8.3线性方程组求解 258
8.3.1简单高斯消元算法 259
8.3.2带部分主元选择的高斯消元算法 269
8.3.3求解三角系统：回代法 271
8.3.4求解线性方程组时的数值因素 272
8.4书目评注 272
习题 273
第9章 排序 279
9.1并行计算机中的排序问题 279
9.1.1输入输出序列的存放位置 279
9.1.2如何进行比较 280
9.2排序网络 281
9.2.1双调排序 282
9.2.2将双调排序映射到超立方体和格网 285
9.3冒泡排序及其变体 290
9.3.1奇偶转换 290
9.3.2希尔排序 293
9.4快速排序 294
9.4.1并行快速排序 295
9.4.2用于CRCWPRAM的并行形式 296
9.4.3用于实际体系结构的并行形式 298
9.4.4主元选择 302
9.5桶和样本排序 303
9.6其他排序算法 305
9.6.1枚举排序 305
9.6.2基数排序 306
9.7书目评注 307
习题 308
第10章 图算法 315
10.1定义和表示 315
10.2最小生成树：Prim算法 317
10.3单源最短路径：Dijkstra算法 321
10.4全部顶点对间的最短路径 321
10.4.1Dijkstra算法 322
10.4.2Floyd算法 323
10.4.3性能比较 327
10.5传递闭包 327
10.6连通分量 328
10.7稀疏图算法 331
10.7.1查找最大独立集 332
10.7.2单源最短路径 334
10.8书目评注 340
习题 341
第11章 离散优化问题的搜索算法 345
11.1定义与实例 345
11.2顺序搜索算法 349
11.2.1深度优先搜索算法 349
11.2.2最佳优先搜索算法 351
11.3搜索开销因子 353
11.4并行深度优先搜索 353
11.4.1并行DFS的重要参数 355
11.4.2并行DFS分析的一般框架 357
11.4.3负载平衡方案分析 359
11.4.4终止检测 360
11.4.5试验结果 362
11.4.6深度优先分支定界搜索的并行形式 364
11.4.7IDA＊的并行形式 365
11.5并行最佳优先搜索 365
11.6并行搜索算法的加速比异常 368
11.7书目评注 371
习题 374
第12章 动态规划 379
12.1动态规划概述 379
12.2串行一元DP形式 381
12.2.1最短路径问题 381
12.2.20/1背包问题 382
12.3非串行一元DP形式 384
12.5非串行多元DP形式 387
12.4串行多元DP形式 387
12.6综述与讨论 390
12.7书目评注 391
习题 391
第13章 快速傅里叶变换 395
13.1串行算法 395
13.2二进制交换算法 398
13.2.1全带宽网络 399
13.2.2有限带宽网络 404
13.2.3并行快速傅里叶变换中的额外计算 405
13.3转置算法 407
13.3.1二维转置算法 407
13.3.2转置算法的推广 410
13.4书目评注 413
习题 414
附录A 函数的复杂度与阶次分析 417
索引 419