第一篇 并行计算硬件平台：并行计算机 3
第一章 并行计算与并行计算机结构模型 3
1.1 计算与计算机科学 4
1.1.1 科学发现的第三支柱：计算科学 4
1.1.2 计算科学与计算机科学 5
1.2 单处理机与指令级并行 6
1.2.1 加快CPU执行速度 6
1.2.2 减少存储延迟 7
1.2.3 改善输入和输出以及网络性能 8
1.3 多核处理器与线程级并行 9
1.3.1 单核处理器结构设计 9
1.3.2 多核处理器结构设计 10
1.3.3 多核处理器实例 11
1.4 并行计算机体系结构 13
1.4.1 并行计算机结构模型 13
1.4.2 并行计算机访存模型 17
1.4.3 并行计算机存储组织 21
1.5 并行计算概述 25
1.5.1 关于并行计算 25
1.5.2 并行计算研究现状 28
1.6 小结和导读 32
习题 34
第二章 并行计算机系统互连与基本通信操作 36
2.1 并行计算机互连网络 37
2.1.1 系统互连 37
2.1.2 静态互连网络 38
2.1.3 动态互连网络 43
2.1.4 标准互连网络 46
2.2 选路方法与开关技术 52
2.2.1 选路方法 52
2.2.2 开关技术 54
2.3 单一信包一到一传输 56
2.4 一到多播送 56
2.4.1 使用SF进行一到多播送 57
2.4.2 使用CT进行一到多播送 58
2.5 多到多播送 59
2.5.1 使用SF进行多到多播送 59
2.5.2 使用CT进行多到多播送 62
2.6 小结和导读 62
习题 65
第三章 典型并行计算机系统介绍 72
3.1 共享存储多处理机系统 73
3.1.1 对称多处理机SMP结构特性 73
3.1.2 SGI Challenge系统 74
3.2 分布存储多计算机系统 77
3.2.1 大规模并行处理机MPP结构特性 77
3.2.2 ASCI Option Red MPP系统 82
3.3 分布共享存储计算机系统 86
3.3.1 分布共享存储计算机系统特性 87
3.3.2 SGI Origin 2000系统 90
3.4 机群系统 96
3.4.1 大规模并行处理系统MPP机群SP2 96
3.4.2 工作站机群COW 103
3.4.3 Berkeley的NOW计划 107
3.5 小结和导读 112
习题 114
第四章 并行计算性能评测 117
4.1 并行计算机的一些基本性能指标 118
4.1.1 CPU和存储器的某些基本性能指标 118
4.1.2 通信开销 120
4.1.3 机器的成本、价格与性能价格比 121
4.2 加速比性能定律 123
4.2.1 Amdahl定律 123
4.2.2 Gustafson定律 125
4.2.3 Sun和Ni定律 125
4.2.4 有关加速的讨论 127
4.3 可扩放性评测标准 128
4.3.1 并行计算的可扩放性 128
4.3.2 等效率度量标准 129
4.3.3 等速度度量标准 130
4.3.4 平均延迟度量标准 132
4.3.5 有关可扩放性标准的讨论 133
4.4 基准测试程序 134
4.4.1 基本的测试程序 135
4.4.2 数学库测试程序 136
4.4.3 并行测试程序 137
4.5 小结和导读 138
习题 139
第二篇 并行计算理论基础：并行算法（上）——并行算法设计 145
第五章 并行算法与并行计算模型 145
5.1 并行算法的基础知识 146
5.1.1 并行算法的定义和分类 146
5.1.2 并行算法的表达 147
5.1.3 并行算法的复杂性度量 147
5.1.4 并行算法中的同步与通信 149
5.2 并行计算模型 150
5.2.1 PRAM模型 151
5.2.2 异步PRAM模型 152
5.2.3 BSP模型 153
5.2.4 LogP模型 155
5.2.5 对BSP和LogP的评注 158
5.2.6 层次存储模型 160
5.2.7 分层并行计算模型 163
5.3 小结和导读 167
习题 168
第六章 并行算法基本设计策略 173
6.1 串行算法的直接并行化 174
6.1.1 设计策略描述 174
6.1.2 快排序算法的并行化 174
6.2 从问题描述开始设计并行算法 177
6.2.1 串匹配算法 177
6.2.2 KMP串行串匹配算法 178
6.2.3 并行串匹配算法的设计思路 180
6.3 借用已有算法求解新问题 181
6.3.1 设计策略描述 182
6.3.2 利用矩阵乘法求所有点对间最短路径 182
6.4 小结和导读 185
习题 186
第七章 并行算法常用设计技术 189
7.1 划分设计技术 190
7.1.1 均匀划分技术 190
7.1.2 方根划分技术 191
7.1.3 对数划分技术 192
7.1.4 功能划分技术 193
7.2 分治设计技术 194
7.2.1 双调归并网络 195
7.2.2 凸壳问题 196
7.3 平衡树设计技术 198
7.3.1 求取最大值 198
7.3.2 计算前缀和 199
7.4 倍增设计技术 200
7.4.1 表序问题的计算 200
7.4.2 求森林的根 201
7.5 流水线设计技术 203
7.5.1 一维脉动阵列上的DFT计算 203
7.5.2 一维脉动阵列上的卷积计算 204
7.6 小结和导读 205
习题 207
第八章 并行算法一般设计过程 209
8.1 PCAM设计方法学 210
8.2 划分 211
8.2.1 域分解 211
8.2.2 功能分解 212
8.2.3 划分判据 212
8.3 通信 213
8.3.1 局部通信 213
8.3.2 全局通信 214
8.3.3 非结构化、动态和异步通信 215
8.3.4 通信判据 216
8.4 组合 216
8.4.1 增加粒度 217
8.4.2 保持灵活性和减少软件工程成本 219
8.4.3 组合判据 219
8.5 映射 220
8.5.1 负载平衡算法 221
8.5.2 任务调度算法 222
8.5.3 映射判据 223
8.6 小结和导读 223
习题 224
第二篇 并行计算理论基础：并行算法（下）——并行数值算法 229
第九章 稠密矩阵运算 229
9.1 矩阵的划分 230
9.1.1 带状划分 230
9.1.2 棋盘划分 231
9.2 矩阵转置 231
9.2.1 棋盘划分的矩阵转置 232
9.2.2 带状划分的矩阵转置 235
9.3 矩阵-向量乘法 236
9.3.1 带状划分的矩阵-向量乘法 236
9.3.2 棋盘划分的矩阵-向量乘法 237
9.4 矩阵乘法 239
9.4.1 简单并行分块乘法 240
9.4.2 Cannon乘法 241
9.4.3 Fox乘法 244
9.4.4 DNS乘法 246
9.5 小结和导读 250
习题 251
第十章 线性方程组求解 254
10.1 三角形方程组的求解 255
10.1.1 基本术语 255
10.1.2 上三角方程组的求解 256
10.2 三对角方程组的求解 258
10.2.1 三对角方程组直接求解法 258
10.2.2 三对角方程组奇偶归约求解法 260
10.3 稠密线性方程组的求解 262
10.3.1 有回代的高斯消去法 262
10.3.2 无回代的高斯-约旦法 266
10.3.3 迭代求解的高斯-赛德尔法 268
10.4 稀疏线性方程组的求解 270
10.4.1 稀疏矩阵的存储方式 270
10.4.2 雅可比迭代法 272
10.4.3 高斯-赛德尔迭代法 278
10.4.4 超松弛迭代法 279
10.4.5 多重网格法 280
10.4.6 共轭梯度法 281
10.5 小结和导读 286
习题 287
第十一章 快速傅里叶变换 289
11.1 离散傅氏变换 290
11.1.1 预备知识 290
11.1.2 离散傅里叶变换 291
11.1.3 离散傅里叶逆变换 292
11.1.4 离散傅氏变换的蝶式计算 292
11.2 快速傅氏变换串行算法 295
11.2.1 串行FFT迭代算法 295
11.2.2 串行FFT递归算法 296
11.3 并行FFT算法 298
11.3.1 SIMD-MC2上FFT算法 299
11.3.2 SIMD-BF上FFT算法 301
11.3.3 SIMD-CC上FFT算法 303
11.3.4 MIMD-DM上FFT算法 304
11.4 小结和导读 308
习题 309
第十二章 数值计算的基本支撑技术 311
12.1 网格生成 312
12.1.1 网格生成过程与方法 312
12.1.2 并行网格生成 315
12.1.3 网格生成有关软件和网址 316
12.2 图的划分 317
12.2.1 负载平衡与图的划分 318
12.2.2 图划分算法 318
12.2.3 多约束图划分问题及算法 321
12.3 稀疏线性系统求解器 322
12.3.1 稀疏矩阵的来源和结构 322
12.3.2 稀疏线性系统直接方法 323
12.3.3 稀疏线性系统迭代方法 324
12.3.4 预条件子 326
12.3.5 稀疏线性代数库 328
12.4 算法和软件 329
12.4.1 算法和软件的可重用 329
12.4.2 算法和软件的可移植 331
12.4.3 算法和软件的可扩放 332
12.5 科学计算可视化 334
12.5.1 科学计算可视化的基本概念 334
12.5.2 并行科学计算可视化 336
12.6 小结和导读 338
习题 340
第三篇 并行计算软件支撑：并行编程 345
第十三章 并行程序设计基础 345
13.1 并行程序设计概述 346
13.1.1 串行程序设计与并行程序设计 346
13.1.2 并行程序设计环境与工具 348
13.1.3 并行程序设计方法 348
13.1.4 并行编程风范 350
13.2 进程和线程 351
13.2.1 进程和线程的基本概念 351
13.2.2 进程和线程的并行执行 353
13.3 同步和通信 355
13.3.1 同步 355
13.3.2 通信 358
13.4 单核多线程与多核多线程 359
13.4.1 单处理器核上并发程序设计 359
13.4.2 多执行核上并行程序设计 361
13.5 影响多线程性能的常见问题 362
13.5.1 线程过多 362
13.5.2 数据竞争 364
13.5.3 死锁 365
13.5.4 Cache伪共享 366
13.6 并行程序设计模型 367
13.6.1 计算π样本程序 367
13.6.2 隐式并行模型 369
13.6.3 数据并行模型 370
13.6.4 消息传递模型 371
13.6.5 共享变量模型 372
13.6.6 并行程序设计模型比较 374
13.7 小结和导读 375
习题 375
第十四章 共享存储系统并行编程 378
14.1 基于共享变量的共享存储并行编程 379
14.1.1 共享存储并行编程的基本问题 379
14.1.2 共享存储编程环境 380
14.2 POSIX线程 380
14.2.1 POSIX线程模型 381
14.2.2 使用Pthreads编写计算π的程序实例 382
14.3 OpenMP并行编程 384
14.3.1 OpenMP概述 384
14.3.2 OpenMP编程风格 385
14.3.3 共享任务结构 389
14.3.4 OpenMP其他编程要素 393
14.3.5 OpenMP计算实例 398
14.4 小结和导读 401
习题 401
附录 OpenMP运行库例程 404
第十五章 分布存储系统并行编程 406
15.1 基于消息传递的并行编程 407
15.1.1 SPMD并行程序 407
15.1.2 MPMD并行程序 408
15.2 MPI并行编程 409
15.2.1 MPI概述 410
15.2.2 最基本的MPI 411
15.2.3 MPI消息 413
15.2.4 点对点通信 418
15.2.5 群集通信 420
15.2.6 计算π的MPI程序 425
15.3 基于数据并行的并行编程 425
15.3.1 数据并行模型的特点 426
15.3.2 数据并行编程的基本问题 426
15.4 HPF并行编程 427
15.4.1 HPF概述 427
15.4.2 HPF编程简介 428
15.4.3 数据映射 432
15.4.4 数据并行结构 435
15.4.5 HPF语言的过程 438
15.4.6 高斯消去法的HPF程序 440
15.5 小结和导读 440
习题 441
附录一 MPI函数的C语言说明 447
附录二 MPI函数的FORTRAN语言说明 449
第十六章 并行程序设计环境与工具 452
16.1 软件工具与环境 453
16.1.1 编码工具与软件工程工具 453
16.1.2 集成工具与环境 454
16.2 并行编译器 456
16.2.1 编译及其并行化 457
16.2.2 相关分析 459
16.2.3 代码优化 461
16.2.4 代码生成 466
16.3 并行程序调试 467
16.3.1 并行程序调试的方法与步骤 467
16.3.2 并行程序的调试技术 469
16.4 并行程序性能分析 470
16.4.1 并行程序的性能预测 470
16.4.2 并行程序的性能监控 472
16.4.3 并行程序性能分析工具 474
16.4.4 并行程序的性能可视化 475
16.5 图形化并行程序集成开发环境 477
16.5.1 图形应用开发环境GRADE的组成 477
16.5.2 GRADE中开发并行程序过程 478
16.5.3 基于模式的可视化并行编程环境CO2P3S 479
16.6 小结和导读 480
习题 481
附录篇 并行计算发展动力：并行应用 487
附录A 并行应用相关知识 487
A.1 应用需求 487
A.2 应用领域 488
A.3 应用实例 489
A.4 应用须知 490
附录B 应用综合练习：大气模型的并行算法设计 492
B.1 背景知识 492
B.2 设计分析 493
附录C 数值计算软件包和工具 495
C.1 高性能程序库 495
C.1.1 BLAS库 495
C.1.2 LAPACK库 497
C.1.3 ScaLAPACK库 498
C.2 软件包和工具 500
C.2.1 PETSc 500
C.2.2 FFTW 501
C.2.3 HPSEPS 503
C.2.4 Hypre 504
C.2.5 MUMPS 505
C.2.6 ParMETIS 506
C.2.7 Trilions 507
C.2.8 TAO 509
C.2.9 SUNDIALS 511
C.2.10 SLEPC 512
附录D 应用实例一：机群系统上三维傅里叶变换 515
D.1 问题背景 515
D.2 机群系统 516
D.3 三维傅里叶变换一般并行算法 517
D.4 改进的三维傅里叶变换并行算法 519
D.5 应用实例 520
D.6 编程实现 521
D.7 实验比较 523
附录E 应用实例二：多核系统上并行图像特征提取 525
E.1 问题背景 525
E.2 多核平台 527
E.3 图像特征提取的并行算法 528
E.4 编程实现 530
E.5 实验比较 533
附录F 应用实例三：个人高性能计算机上水平井射孔渗流计算 535
F.1 问题背景 535
F.2 并行计算方法 536
F.3 并行编程概述 538
F.4 KD-50-I平台 540
F.5 应用结果 541
索引 544
算法索引 544
表格索引 546
示范程序索引 547
专业术语索引 548
参考文献 561