并行計(jì)算導(dǎo)論

第1部分  基礎(chǔ)知識(shí)        1
第1章  預(yù)備知識(shí)        3
1.1  并行計(jì)算的主要研究目標(biāo)和內(nèi)容        3
1.1.1  什么是并行計(jì)算        4
1.1.2  并行計(jì)算的主要研究目標(biāo)和內(nèi)容        4
1.1.3  推動(dòng)并行計(jì)算發(fā)展的主要?jiǎng)恿?nbsp;       6
1.2  并行計(jì)算機(jī)發(fā)展歷史        9
1.2.1  應(yīng)用需求的推動(dò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ì)算機(jī)體系結(jié)構(gòu)        20
1.3.1  結(jié)點(diǎn)        21
1.3.2  并行計(jì)算機(jī)互聯(lián)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)        22
1.3.3  多級(jí)存儲(chǔ)體系結(jié)構(gòu)        33
1.3.4  訪(fǎng)存模型        40
1.3.5  并行計(jì)算機(jī)分類(lèi)        41
1.4  操作系統(tǒng)與并行編程環(huán)境        46
1.4.1  進(jìn)程、進(jìn)程間通信與線(xiàn)程        47
1.4.2  并行編程環(huán)境        51
1.5  并行算法        56
1.5.1  并行算法的分類(lèi)        56
1.5.2  并行算法的發(fā)展階段        57
習(xí)題        59
第2章  Linux操作系統(tǒng)與程序開(kāi)發(fā)環(huán)境        60
2.1  Linux安裝與使用入門(mén)        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  程序開(kāi)發(fā)環(huán)境        131
2.3.1  第一個(gè)程序  (C程序)        131
2.3.2  FORTRAN程序的開(kāi)發(fā)        141
2.3.3  軟件開(kāi)發(fā)        146
第3章  消息傳遞編程接口MPI        164
3.1  MPICH安裝與程序編譯、運(yùn)行、調(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ù)類(lèi)型        181
3.2.4  點(diǎn)對(duì)點(diǎn)通信函數(shù)與通信模式        181
3.2.5  聚合通信與同步        187
3.2.6  自定義數(shù)據(jù)類(lèi)型        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章  程序性能評(píng)價(jià)與優(yōu)化        210
4.1  并行程序執(zhí)行時(shí)間        210
4.2  并行加速比與效率        211
4.3  并行程序性能評(píng)價(jià)方法        212
4.3.1  浮點(diǎn)峰值性能與實(shí)際浮點(diǎn)性能        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è)計(jì)與實(shí)現(xiàn)實(shí)例        229
第5章  自適應(yīng)數(shù)值積分        231
5.1  梯形積分公式        231
5.2  局部二分自適應(yīng)區(qū)間加密        232
5.3  串行程序        235
5.4  基于簡(jiǎn)單區(qū)域分解的并行算法        239
5.5  基于主從模式的并行算法        243
5.5.1  基于非阻塞通信的并行程序        249
5.5.2  基于散發(fā)/收集通信的并行程序        252
5.6  基于動(dòng)態(tài)負(fù)載調(diào)度的并行算法        256
習(xí)題        259
第6章  矩陣并行計(jì)算        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  線(xiàn)性代數(shù)方程組并行求解方法        268
6.2.1  分布式系統(tǒng)的并行LU分解算法        269
6.2.2  三角方程組的并行解法        271
6.3  對(duì)稱(chēng)正定線(xiàn)性方程組的并行解法        273
6.3.1  Cholesky分解列格式的并行計(jì)算        273
6.3.2  雙曲變換Cholesky分解        275
6.3.3  修正的雙曲變換Cholesky分解        277
6.4  三對(duì)角方程組的并行解法        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  線(xiàn)性迭代的一般收斂性結(jié)果        285
6.7  代數(shù)特征值問(wèn)題的并行求解        286
6.7.1  對(duì)稱(chēng)三對(duì)角矩陣特征值問(wèn)題        287
6.7.2  Householder變換        289
6.7.3  化對(duì)稱(chēng)矩陣為三對(duì)角矩陣        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  多項(xiàng)式相乘        305
7.4.2  循環(huán)矩陣方程組的求解        306
第8章  二維Poisson方程        308
8.1  并行算法設(shè)計(jì)        310
8.2  MPI并行程序設(shè)計(jì)        312
8.3  并行效率分析        317
8.4  MPI并行程序的改進(jìn)        319
習(xí)題        323
第9章  二維熱傳導(dǎo)方程        325
9.1  空間離散與區(qū)域劃分        325
9.2  時(shí)間離散：顯式格式        326
9.3  時(shí)間離散：隱式/半隱式格式        331
9.4  時(shí)間離散：ADI方法        332
9.5  分塊流水線(xiàn)方法        334
9.5.1  模型問(wèn)題        334
9.5.2  模型問(wèn)題的并行效率分析        337
9.5.3  二維熱傳導(dǎo)方程的分塊流水線(xiàn)算法程序?qū)嵗?nbsp;       340
習(xí)題        351
第3部分  附    錄        353
附錄A  并行程序開(kāi)發(fā)工具與高性能程序庫(kù)        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è)計(jì)        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  實(shí)型變換        396
A.4.3  并行FFTW        397
A.4.4  FFTW計(jì)算實(shí)例        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計(jì)算實(shí)例        406
A.5.5  PETSc小結(jié)        419
附錄B  MPI參考手冊(cè)        421
B.1  MPI函數(shù)、變量速查表        421
B.2  MPI預(yù)定義的變量及類(lèi)型        426
B.2.1  C語(yǔ)言MPI原始數(shù)據(jù)類(lèi)型        426
B.2.2  FORTRAN 77 語(yǔ)言MPI原始數(shù)據(jù)類(lèi)型        427
B.2.3  預(yù)定義的通信器與進(jìn)程組        428
B.2.4  用于歸約函數(shù)的預(yù)定義的二目運(yùn)算        428
B.2.5  C變量類(lèi)型及預(yù)定義函數(shù)        429
B.2.6  空對(duì)象        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  錯(cuò)誤碼        432
B.2.11  MPI-2用于文件輸入輸出的常量與類(lèi)型        432
B.3  初始化、退出與錯(cuò)誤處理函數(shù)        434
B.4  點(diǎn)對(duì)點(diǎn)通信函數(shù)        436
B.4.1  阻塞型通信函數(shù)    436
B.4.2  非阻塞型通信函數(shù)        438
B.4.3  持久通信函數(shù)        442
B.5  數(shù)據(jù)類(lèi)型與打包函數(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í)間函數(shù)    462
B.9  MPI-2文件輸入輸出函數(shù)    463
參考文獻(xiàn)        475
MPI函數(shù)、變量索引        479
名詞索引        483