并行计算导论

第1部分  基础知识        1
第1章  预备知识        3
1.1  并行计算的主要研究目标和内容        3
1.1.1  什么是并行计算        4
1.1.2  并行计算的主要研究目标和内容        4
1.1.3  推动并行计算发展的主要动力        6
1.2  并行计算机发展历史        9
1.2.1  应用需求的推动作用        9
1.2.2  20世纪70年代        10
1.2.3  20世纪80年代早期        10
1.2.4  20世纪80年代中期        10
1.2.5  20世纪80年代后期        11
1.2.6  20世纪90年代早期        12
1.2.7  20世纪90年代中后期        13
1.2.8  2000年到当前        17
1.3  并行计算机体系结构        20
1.3.1  结点        21
1.3.2  并行计算机互联网络拓扑结构        22
1.3.3  多级存储体系结构        33
1.3.4  访存模型        40
1.3.5  并行计算机分类        41
1.4  操作系统与并行编程环境        46
1.4.1  进程、进程间通信与线程        47
1.4.2  并行编程环境        51
1.5  并行算法        56
1.5.1  并行算法的分类        56
1.5.2  并行算法的发展阶段        57
习题        59
第2章  Linux操作系统与程序开发环境        60
2.1  Linux安装与使用入门        60
2.1.1  Linux系统的安装        60
2.1.2  基本使用与管理        64
2.2  Linux基本命令和概念        74
2.2.1  一些基本命令        74
2.2.2  shell        94
2.2.3  文本文件处理        122
2.3  程序开发环境        131
2.3.1  第一个程序  (C程序)        131
2.3.2  FORTRAN程序的开发        141
2.3.3  软件开发        146
第3章  消息传递编程接口MPI        164
3.1  MPICH安装与程序编译、运行、调试        165
3.1.1  单机环境下MPICH的安装        165
3.1.2  机群环境下MPICH的安装        171
3.2  MPI编程        177
3.2.1  MPI编程的基本概念        177
3.2.2  程序基本结构        179
3.2.3  MPI的原始数据类型        181
3.2.4  点对点通信函数与通信模式        181
3.2.5  聚合通信与同步        187
3.2.6  自定义数据类型        189
3.2.7  进程组与通信器        194
3.2.8  进程拓扑结构        195
3.2.9  文件输入输出        196
3.3  MPI程序主要结构        203
习题        207
第4章  程序性能评价与优化        210
4.1  并行程序执行时间        210
4.2  并行加速比与效率        211
4.3  并行程序性能评价方法        212
4.3.1  浮点峰值性能与实际浮点性能        212
4.3.2  数值效率和并行效率        213
4.4  可扩展分析        216
4.5  程序性能优化        217
4.5.1  串行程序性能优化        217
4.5.2  并行程序性能优化        223
习题        225
第2部分  并行算法设计与实现实例        229
第5章  自适应数值积分        231
5.1  梯形积分公式        231
5.2  局部二分自适应区间加密        232
5.3  串行程序        235
5.4  基于简单区域分解的并行算法        239
5.5  基于主从模式的并行算法        243
5.5.1  基于非阻塞通信的并行程序        249
5.5.2  基于散发/收集通信的并行程序        252
5.6  基于动态负载调度的并行算法        256
习题        259
第6章  矩阵并行计算        261
6.1  并行矩阵乘法        263
6.1.1  串行矩阵乘法        263
6.1.2  行列划分算法        263
6.1.3  行行划分算法        264
6.1.4  列列划分算法        265
6.1.5  列行划分算法        266
6.1.6  Cannon算法        267
6.2  线性代数方程组并行求解方法        268
6.2.1  分布式系统的并行LU分解算法        269
6.2.2  三角方程组的并行解法        271
6.3  对称正定线性方程组的并行解法        273
6.3.1  Cholesky分解列格式的并行计算        273
6.3.2  双曲变换Cholesky分解        275
6.3.3  修正的双曲变换Cholesky分解        277
6.4  三对角方程组的并行解法        279
6.5  经典迭代算法的并行化        282
6.5.1  Jacobi迭代法        282
6.5.2  Causs-Seidel迭代法        283
6.6  异步并行迭代法        284
6.6.1  异步并行迭代法基础        284
6.6.2  线性迭代的一般收敛性结果        285
6.7  代数特征值问题的并行求解        286
6.7.1  对称三对角矩阵特征值问题        287
6.7.2  Householder变换        289
6.7.3  化对称矩阵为三对角矩阵        289
习题        290
第7章  FFT算法与应用        291
7.1  一维串行FFT 算法        292
7.2  二维串行FFT算法        297
7.3  并行FFT算法        298
7.4  FFT应用示例        305
7.4.1  多项式相乘        305
7.4.2  循环矩阵方程组的求解        306
第8章  二维Poisson方程        308
8.1  并行算法设计        310
8.2  MPI并行程序设计        312
8.3  并行效率分析        317
8.4  MPI并行程序的改进        319
习题        323
第9章  二维热传导方程        325
9.1  空间离散与区域划分        325
9.2  时间离散：显式格式        326
9.3  时间离散：隐式/半隐式格式        331
9.4  时间离散：ADI方法        332
9.5  分块流水线方法        334
9.5.1  模型问题        334
9.5.2  模型问题的并行效率分析        337
9.5.3  二维热传导方程的分块流水线算法程序实例        340
习题        351
第3部分  附    录        353
附录A  并行程序开发工具与高性能程序库        355
A.1  BLAS        355
A.1.1  Level 1 BLAS        357
A.1.2  Level 2 BLAS        357
A.1.3  Level 3 BLAS        359
A.2  LAPACK        360
A.2.1  LAPACK软件包组成        361
A.2.2  LAPACK程序文档        364
A.2.3  LAPACK参数设计        364
A.2.4  LAPACK使用示例        367
A.3  ScaLAPACK        376
A.3.1  ScaLAPACK体系结构        377
A.3.2  ScaLAPACK程序介绍        380
A.3.3  ScaLAPACK安装        384
A.3.4  ScaLAPACK编程指南        388
A.4  FFTW        392
A.4.1  复型变换        393
A.4.2  实型变换        396
A.4.3  并行FFTW        397
A.4.4  FFTW计算实例        397
A.5  PETSc        400
A.5.1  PETSc的系统结构        401
A.5.2  PETSc的基本特色        402
A.5.3  PETSc的基本功能        404
A.5.4  PETSc计算实例        406
A.5.5  PETSc小结        419
附录B  MPI参考手册        421
B.1  MPI函数、变量速查表        421
B.2  MPI预定义的变量及类型        426
B.2.1  C语言MPI原始数据类型        426
B.2.2  FORTRAN 77 语言MPI原始数据类型        427
B.2.3  预定义的通信器与进程组        428
B.2.4  用于归约函数的预定义的二目运算        428
B.2.5  C变量类型及预定义函数        429
B.2.6  空对象        430
B.2.7  MPI常量        430
B.2.8  进程拓扑结构        431
B.2.9  通信状态信息        431
B.2.10  错误码        432
B.2.11  MPI-2用于文件输入输出的常量与类型        432
B.3  初始化、退出与错误处理函数        434
B.4  点对点通信函数        436
B.4.1  阻塞型通信函数    436
B.4.2  非阻塞型通信函数        438
B.4.3  持久通信函数        442
B.5  数据类型与打包函数        444
B.6  同步与聚合通信函数        448
B.7  进程组与通信器操作        453
B.7.1  进程组操作        453
B.7.2  域内通信器操作        455
B.7.3  进程拓扑结构    457
B.7.4  域间通信器操作    462
B.8  时间函数    462
B.9  MPI-2文件输入输出函数    463
参考文献        475
MPI函数、变量索引        479
名词索引        483