并行計算導(dǎo)論

第1部分  基礎(chǔ)知識        1
第1章  預(yù)備知識        3
1.1  并行計算的主要研究目標(biāo)和內(nèi)容        3
1.1.1  什么是并行計算        4
1.1.2  并行計算的主要研究目標(biāo)和內(nèi)容        4
1.1.3  推動并行計算發(fā)展的主要動力        6
1.2  并行計算機(jī)發(fā)展歷史        9
1.2.1  應(yīng)用需求的推動作用        9
1.2.2  20世紀(jì)70年代        10
1.2.3  20世紀(jì)80年代早期        10
1.2.4  20世紀(jì)80年代中期        10
1.2.5  20世紀(jì)80年代后期        11
1.2.6  20世紀(jì)90年代早期        12
1.2.7  20世紀(jì)90年代中后期        13
1.2.8  2000年到當(dāng)前        17
1.3  并行計算機(jī)體系結(jié)構(gòu)        20
1.3.1  結(jié)點        21
1.3.2  并行計算機(jī)互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)        22
1.3.3  多級存儲體系結(jié)構(gòu)        33
1.3.4  訪存模型        40
1.3.5  并行計算機(jī)分類        41
1.4  操作系統(tǒng)與并行編程環(huán)境        46
1.4.1  進(jìn)程、進(jìn)程間通信與線程        47
1.4.2  并行編程環(huán)境        51
1.5  并行算法        56
1.5.1  并行算法的分類        56
1.5.2  并行算法的發(fā)展階段        57
習(xí)題        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安裝與程序編譯、運行、調(diào)試        165
3.1.1  單機(jī)環(huán)境下MPICH的安裝        165
3.1.2  機(jī)群環(huán)境下MPICH的安裝        171
3.2  MPI編程        177
3.2.1  MPI編程的基本概念        177
3.2.2  程序基本結(jié)構(gòu)        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  進(jìn)程組與通信器        194
3.2.8  進(jìn)程拓?fù)浣Y(jié)構(gòu)        195
3.2.9  文件輸入輸出        196
3.3  MPI程序主要結(jié)構(gòu)        203
習(xí)題        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  可擴(kuò)展分析        216
4.5  程序性能優(yōu)化        217
4.5.1  串行程序性能優(yōu)化        217
4.5.2  并行程序性能優(yōu)化        223
習(xí)題        225
第2部分  并行算法設(shè)計與實現(xiàn)實例        229
第5章  自適應(yīng)數(shù)值積分        231
5.1  梯形積分公式        231
5.2  局部二分自適應(yīng)區(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)負(fù)載調(diào)度的并行算法        256
習(xí)題        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  異步并行迭代法基礎(chǔ)        284
6.6.2  線性迭代的一般收斂性結(jié)果        285
6.7  代數(shù)特征值問題的并行求解        286
6.7.1  對稱三對角矩陣特征值問題        287
6.7.2  Householder變換        289
6.7.3  化對稱矩陣為三對角矩陣        289
習(xí)題        290
第7章  FFT算法與應(yīng)用        291
7.1  一維串行FFT 算法        292
7.2  二維串行FFT算法        297
7.3  并行FFT算法        298
7.4  FFT應(yīng)用示例        305
7.4.1  多項式相乘        305
7.4.2  循環(huán)矩陣方程組的求解        306
第8章  二維Poisson方程        308
8.1  并行算法設(shè)計        310
8.2  MPI并行程序設(shè)計        312
8.3  并行效率分析        317
8.4  MPI并行程序的改進(jìn)        319
習(xí)題        323
第9章  二維熱傳導(dǎo)方程        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  二維熱傳導(dǎo)方程的分塊流水線算法程序?qū)嵗?nbsp;       340
習(xí)題        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ù)設(shè)計        364
A.2.4  LAPACK使用示例        367
A.3  ScaLAPACK        376
A.3.1  ScaLAPACK體系結(jié)構(gòu)        377
A.3.2  ScaLAPACK程序介紹        380
A.3.3  ScaLAPACK安裝        384
A.3.4  ScaLAPACK編程指南        388
A.4  FFTW        392
A.4.1  復(fù)型變換        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)結(jié)構(gòu)        401
A.5.2  PETSc的基本特色        402
A.5.3  PETSc的基本功能        404
A.5.4  PETSc計算實例        406
A.5.5  PETSc小結(jié)        419
附錄B  MPI參考手冊        421
B.1  MPI函數(shù)、變量速查表        421
B.2  MPI預(yù)定義的變量及類型        426
B.2.1  C語言MPI原始數(shù)據(jù)類型        426
B.2.2  FORTRAN 77 語言MPI原始數(shù)據(jù)類型        427
B.2.3  預(yù)定義的通信器與進(jìn)程組        428
B.2.4  用于歸約函數(shù)的預(yù)定義的二目運算        428
B.2.5  C變量類型及預(yù)定義函數(shù)        429
B.2.6  空對象        430
B.2.7  MPI常量        430
B.2.8  進(jìn)程拓?fù)浣Y(jié)構(gòu)        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  進(jìn)程組與通信器操作        453
B.7.1  進(jìn)程組操作        453
B.7.2  域內(nèi)通信器操作        455
B.7.3  進(jìn)程拓?fù)浣Y(jié)構(gòu)    457
B.7.4  域間通信器操作    462
B.8  時間函數(shù)    462
B.9  MPI-2文件輸入輸出函數(shù)    463
參考文獻(xiàn)        475
MPI函數(shù)、變量索引        479
名詞索引        483