并行計算導論

第1部分  基礎知識        1
第1章  預備知識        3
1.1  并行計算的主要研究目標和內容        3
1.1.1  什么是并行計算        4
1.1.2  并行計算的主要研究目標和內容        4
1.1.3  推動并行計算發(fā)展的主要動力        6
1.2  并行計算機發(fā)展歷史        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  并行計算機互聯(lián)網(wǎng)絡拓撲結構        22
1.3.3  多級存儲體系結構        33
1.3.4  訪存模型        40
1.3.5  并行計算機分類        41
1.4  操作系統(tǒng)與并行編程環(huán)境        46
1.4.1  進程、進程間通信與線程        47
1.4.2  并行編程環(huán)境        51
1.5  并行算法        56
1.5.1  并行算法的分類        56
1.5.2  并行算法的發(fā)展階段        57
習題        59
第2章  Linux操作系統(tǒng)與程序開發(fā)環(huán)境        60
2.1  Linux安裝與使用入門        60
2.1.1  Linux系統(tǒng)的安裝        60
2.1.2  基本使用與管理        64
2.2  Linux基本命令和概念        74
2.2.1  一些基本命令        74
2.2.2  shell        94
2.2.3  文本文件處理        122
2.3  程序開發(fā)環(huán)境        131
2.3.1  第一個程序  (C程序)        131
2.3.2  FORTRAN程序的開發(fā)        141
2.3.3  軟件開發(fā)        146
第3章  消息傳遞編程接口MPI        164
3.1  MPICH安裝與程序編譯、運行、調試        165
3.1.1  單機環(huán)境下MPICH的安裝        165
3.1.2  機群環(huán)境下MPICH的安裝        171
3.2  MPI編程        177
3.2.1  MPI編程的基本概念        177
3.2.2  程序基本結構        179
3.2.3  MPI的原始數(shù)據(jù)類型        181
3.2.4  點對點通信函數(shù)與通信模式        181
3.2.5  聚合通信與同步        187
3.2.6  自定義數(shù)據(jù)類型        189
3.2.7  進程組與通信器        194
3.2.8  進程拓撲結構        195
3.2.9  文件輸入輸出        196
3.3  MPI程序主要結構        203
習題        207
第4章  程序性能評價與優(yōu)化        210
4.1  并行程序執(zhí)行時間        210
4.2  并行加速比與效率        211
4.3  并行程序性能評價方法        212
4.3.1  浮點峰值性能與實際浮點性能        212
4.3.2  數(shù)值效率和并行效率        213
4.4  可擴展分析        216
4.5  程序性能優(yōu)化        217
4.5.1  串行程序性能優(yōu)化        217
4.5.2  并行程序性能優(yōu)化        223
習題        225
第2部分  并行算法設計與實現(xiàn)實例        229
第5章  自適應數(shù)值積分        231
5.1  梯形積分公式        231
5.2  局部二分自適應區(qū)間加密        232
5.3  串行程序        235
5.4  基于簡單區(qū)域分解的并行算法        239
5.5  基于主從模式的并行算法        243
5.5.1  基于非阻塞通信的并行程序        249
5.5.2  基于散發(fā)/收集通信的并行程序        252
5.6  基于動態(tài)負載調度的并行算法        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  線性代數(shù)方程組并行求解方法        268
6.2.1  分布式系統(tǒng)的并行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  經(jīng)典迭代算法的并行化        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  代數(shù)特征值問題的并行求解        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  循環(huán)矩陣方程組的求解        306
第8章  二維Poisson方程        308
8.1  并行算法設計        310
8.2  MPI并行程序設計        312
8.3  并行效率分析        317
8.4  MPI并行程序的改進        319
習題        323
第9章  二維熱傳導方程        325
9.1  空間離散與區(qū)域劃分        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  并行程序開發(fā)工具與高性能程序庫        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參數(shù)設計        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的系統(tǒng)結構        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函數(shù)、變量速查表        421
B.2  MPI預定義的變量及類型        426
B.2.1  C語言MPI原始數(shù)據(jù)類型        426
B.2.2  FORTRAN 77 語言MPI原始數(shù)據(jù)類型        427
B.2.3  預定義的通信器與進程組        428
B.2.4  用于歸約函數(shù)的預定義的二目運算        428
B.2.5  C變量類型及預定義函數(shù)        429
B.2.6  空對象        430
B.2.7  MPI常量        430
B.2.8  進程拓撲結構        431
B.2.9  通信狀態(tài)信息        431
B.2.10  錯誤碼        432
B.2.11  MPI-2用于文件輸入輸出的常量與類型        432
B.3  初始化、退出與錯誤處理函數(shù)        434
B.4  點對點通信函數(shù)        436
B.4.1  阻塞型通信函數(shù)    436
B.4.2  非阻塞型通信函數(shù)        438
B.4.3  持久通信函數(shù)        442
B.5  數(shù)據(jù)類型與打包函數(shù)        444
B.6  同步與聚合通信函數(shù)        448
B.7  進程組與通信器操作        453
B.7.1  進程組操作        453
B.7.2  域內通信器操作        455
B.7.3  進程拓撲結構    457
B.7.4  域間通信器操作    462
B.8  時間函數(shù)    462
B.9  MPI-2文件輸入輸出函數(shù)    463
參考文獻        475
MPI函數(shù)、變量索引        479
名詞索引        483