并行計(jì)算：結(jié)構(gòu)、算法、編程

第一篇  并行計(jì)算硬件基礎(chǔ)                  
 第一章  并行計(jì)算機(jī)系統(tǒng)及其結(jié)構(gòu)模型                  
 1. 1  并行計(jì)算與高端并行計(jì)算機(jī)                  
 1. 1. 1  并行計(jì)算與計(jì)算科學(xué)                  
 1. 1. 2  當(dāng)代科學(xué)與工程問(wèn)題的計(jì)算需求                  
 *1. 1. 3  萬(wàn)億次高端并行機(jī)                  
 1. 2  并行計(jì)算機(jī)系統(tǒng)互連                  
 1. 2. 1  系統(tǒng)互連                  
 1. 2. 2  靜態(tài)互連網(wǎng)絡(luò)                  
 1. 2. 3  動(dòng)態(tài)互連網(wǎng)絡(luò)                  
 1. 2. 4  寬帶互連網(wǎng)絡(luò)                  
 1. 3  并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)                  
 1. 3. 1  并行計(jì)算機(jī)結(jié)構(gòu)模型                  
 1. 3. 2  并行計(jì)算機(jī)訪存模型                  
 *1. 3. 3  并行計(jì)算機(jī)存儲(chǔ)組織                  
 1. 4  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第二章  當(dāng)代并行機(jī)系統(tǒng)：SMP. MPP和COW                  
 2. 1  對(duì)稱多處理機(jī)SMP                  
 2. 1. 1  SMP和CC-NUMA結(jié)構(gòu)特性                  
 *2. 1. 2  SGI／Cray Origin 2000超級(jí)服務(wù)器                  
 2. 2  大規(guī)模并行機(jī)MPP                  
 2. 2. 1  MPP結(jié)構(gòu)特性                  
 *2. 2. 2  機(jī)群型大規(guī)模并行機(jī)SP2                  
 2. 3  工作站機(jī)群COW                  
 2. 3. 1  COW的基本原理與技術(shù)                  
 *2. 3. 2  Berkeley的NOW計(jì)劃                  
 2. 4  國(guó)產(chǎn)曙光系列并行機(jī)系統(tǒng)                  
 2. 4. 1  全對(duì)稱共享存儲(chǔ)多處理機(jī)系統(tǒng)：曙光l號(hào)                  
 2. 4. 2  大規(guī)模并行處理系統(tǒng)：曙光-1000                  
 *2. 4. 3  超級(jí)并行計(jì)算機(jī)系統(tǒng)：曙光-2000                  
 2. 5  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第三章  并行計(jì)算性能評(píng)測(cè)                  
 3. 1  加速比性能定律                  
 3. 1. 1  Amdahl定律                  
 3. 1. 2  Gustafson定律                  
 3. 1. 3  Sun和Ni定律                  
 3. 1. 4  有關(guān)加速的討論                  
 3. 2  可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)                  
 3. 2. 1  并行計(jì)算的可擴(kuò)放性                  
 3. 2. 2  等效率度量標(biāo)準(zhǔn)                  
 3. 2. 3  等速度度量標(biāo)準(zhǔn)                  
 3. 2. 4  平均延遲度量標(biāo)準(zhǔn)                  
 3. 2. 5  有關(guān)可擴(kuò)放性標(biāo)準(zhǔn)的討論                  
 *3. 3  基準(zhǔn)測(cè)試程序                  
 3. 3. 1  基本測(cè)試程序                  
 3. 3. 2  數(shù)學(xué)庫(kù)測(cè)試程序                  
 3. 3. 3  并行測(cè)試程序                  
 3. 4  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第二篇  并行算法的設(shè)計(jì)                  
 第四章  并行算法的設(shè)計(jì)基礎(chǔ)                  
 *4. 1  并行算法的基礎(chǔ)知識(shí)                  
 4. 1. 1  并行算法的定義和分類                  
 4. 1. 2  并行算法的表達(dá)                  
 4. 1. 3  并行算法的復(fù)雜性度量                  
 4. 1. 4  并行算法中的同步與通信                  
 4. 2  并行計(jì)算模型                  
 4. 2. 1  PRAM模型                  
 4. 2. 2  異步PRAM模型                  
 4. 2. 3  BSP模型                  
 4. 2. 4  logP模型                  
 4. 2. 5  C3模型                  
 4. 2. 6  對(duì)BSP和logP的評(píng)注                  
 4. 3  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第五章  并行算法的一般設(shè)計(jì)方法                  
 5. 1  串行算法的直接并行化                  
 5. 1. 1  設(shè)計(jì)方法描述                  
 5. 1. 2  快排序算法的并行化                  
 5. 2  從問(wèn)題描述開(kāi)始設(shè)計(jì)并行算法                  
 5. 2. 1  串匹配算法                  
 *5. 2. 2  KMP串行串匹配算法                  
 5. 2. 3  并行串匹配算法的設(shè)計(jì)思路                  
 5. 3  借用已有算法求解新問(wèn)題                  
 5. 3. 1  設(shè)計(jì)方法描述                  
 5. 3. 2  利用矩陣乘法求所有點(diǎn)對(duì)間最短路徑                  
 5. 4  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第六章  并行算法的基本設(shè)計(jì)技術(shù)                  
 6. 1  劃分設(shè)計(jì)技術(shù)                  
 6. 1. 1  均勻劃分技術(shù)                  
 6. 1. 2  方根劃分技術(shù)                  
 6. 1. 3  對(duì)數(shù)劃分技術(shù)                  
 6. 1. 4  功能劃分技術(shù)                  
 6. 2  分治設(shè)計(jì)技術(shù)                  
 6. 2. 1  雙調(diào)歸并網(wǎng)絡(luò)                  
 6. 2. 2  凸殼問(wèn)題                  
 6. 3  平衡樹(shù)設(shè)計(jì)技術(shù)                  
 6. 3. 1  求取最大值                  
 6. 3. 2  計(jì)算前綴和                  
 6. 4  倍增設(shè)計(jì)技術(shù)                  
 6. 4. 1  表序問(wèn)題的計(jì)算                  
 6. 4. 2  求森林的根                  
 6. 5  流水線設(shè)計(jì)技術(shù)                  
 6. 5. 1  一維心動(dòng)陣列上的DFT計(jì)算                  
 6. 5. 2  一維心動(dòng)陣列上的卷積計(jì)算                  
 6. 6  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第七章  并行算法的一般設(shè)計(jì)過(guò)程                  
 7. 1  PCAM設(shè)計(jì)方法學(xué)                  
 7. 2  劃分                  
 7. 2. 1  域分解                  
 7. 2. 2  功能分解                  
 7. 2. 3  劃分判據(jù)                  
 7. 3  通信                  
 7. 3. 1  局部通信                  
 7. 3. 2  全局通信                  
 7. 3. 3  非結(jié)構(gòu)化. 動(dòng)態(tài)和異步通信                  
 7. 3. 4  通信判據(jù)                  
 7. 4  組合                  
 7. 4. 1  增加粒度                  
 7. 4. 2  保持靈活性和減少軟件工程成本                  
 7. 4. 3  組合判據(jù)                  
 7. 5  映射                  
 7. 5. 1  負(fù)載平衡算法                  
 7. 5. 2  任務(wù)調(diào)度算法                  
 7. 5. 3  映射判據(jù)                  
 7. 6  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第三篇  并行數(shù)值算法                  
 第八章  基本通信操作                  
 8. 1  選路方法與開(kāi)關(guān)技術(shù)                  
 8. 1. 1  選路方法                  
 8. 1. 2  開(kāi)關(guān)技術(shù)                  
 8. 2  單一信包一到一傳輸                  
 8. 3  一到多播送                  
 8. 3. 1  使用SF進(jìn)行一到多播送                  
 8. 3. 2  使用CT進(jìn)行一到多播送                  
 8. 4  多到多播送                  
 8. 4. 1  使用SF進(jìn)行多到多播送                  
 8. 4. 2  使用CT進(jìn)行多到多播送                  
 8. 5  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第九章  稠密矩陣運(yùn)算                  
 9. 1  矩陣的劃分                  
 9. 1. 1  帶狀劃分                  
 9. 1. 2  棋盤劃分                  
 9. 2  矩陣轉(zhuǎn)置                  
 9. 2. 1  棋盤劃分的矩陣轉(zhuǎn)置                  
 9. 2. 2  帶狀劃分的矩陣轉(zhuǎn)置                  
 9. 3  矩陣-向量乘法                  
 9. 3. 1  帶狀劃分的矩陣-向量乘法                  
 9. 3. 2  棋盤劃分的矩陣-向量乘法                  
 9. 4  矩陣乘法                  
 9. 4. 1  簡(jiǎn)單并行分塊乘法                  
 9. 4. 2  Cannon乘法                  
 9. 4. 3  Fox乘法                  
 9. 4. 4  DNS乘法                  
 9. 5  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第十章  線性方程組的求解                  
 10. 1  三角形方程組的求解                  
 10. 1. 1  基本術(shù)語(yǔ)                  
 10. 1. 2  上三角方程組的求解                  
 10. 2  三對(duì)角方程組的求解                  
 10. 2. 1  三對(duì)角方程組直接求解法                  
 10. 2. 2  三對(duì)角方程組奇偶?xì)w約求解法                  
 10. 3  稠密線性方程組的求解                  
 10. 3. 1  有回代的高斯消去法                  
 10. 3. 2  無(wú)回代的高斯-約旦法                  
 10. 3. 3  迭代求解的高斯-賽德?tīng)柗?nbsp;                 
 10. 4  稀疏線性方程組的求解                  
 10. 4. 1  稀疏矩陣的存儲(chǔ)方式                  
 10. 4. 2  雅可比迭代法                  
 10. 4. 3  高斯-賽德?tīng)柕?nbsp;                 
 10. 4. 4  超松弛迭代法                  
 10. 4. 5  多重網(wǎng)格法                  
 10. 4. 6  共扼梯度法                  
 10. 5  小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第十一章  快速傅里時(shí)變換                  
 11. 1  離散傅氏變換                  
 *11. 1. 1  預(yù)備知識(shí)                  
 11. 1. 2  離散傅里葉變換                  
 11. 1. 3  離散傅里葉逆變換                  
 11. 1. 4  離散傅氏變換的蝶式計(jì)算                  
 *11. 2  快速傅氏變換串行算法                  
 11. 2. 1  串行FFT迭代算法                  
 11. 2. 2  串行FFT遞歸算法                  
 11. 3  并行FFT算法                  
 11. 3. 1  SIMD一MC2上FFT算法                  
 11. 3. 2  SIMD-BF上FFT算法                  
 11. 3. 3　SIMD-CC上FFT算法                  
 11. 3. 4  MIMD-DM上FFT算法                  
 11. 4　小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第四篇  并行程序設(shè)計(jì)                  
 第十二章  并行程序設(shè)計(jì)基礎(chǔ)                  
 12. 1　并行程序設(shè)計(jì)概述                  
 12. 1. 1  串行程序設(shè)計(jì)與并行程序設(shè)計(jì)                  
 12. 1. 2　并行程序設(shè)計(jì)環(huán)境                  
 12. 1. 3　并行程序設(shè)計(jì)方法                  
 *12. 2  進(jìn)程                  
 12. 2. 1　進(jìn)程的基本概念                  
 12. 2. 2　進(jìn)程的并行執(zhí)行                  
 12. 2. 3　進(jìn)程的相互作用                  
 12. 3  線程                  
 12. 3. 1  線程的基本概念                  
 12. 3. 2　線程的管理                  
 12. 3. 3　線程的同步                  
 *12. 4  同步                  
 12. 4. 1　原子與互斥                  
 12. 4. 2　高級(jí)同步結(jié)構(gòu)                  
 12. 4. 3　低級(jí)同步原語(yǔ)                  
 12. 5  通信                  
 12. 5. 1  影響通信系統(tǒng)性能的因素                  
 12. 5. 2　低級(jí)通信支持                  
 12. 5. 3　TCP／IP通信協(xié)議組簡(jiǎn)介                  
 12. 6　小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第十三章  并行程序設(shè)計(jì)模型和共享存儲(chǔ)系統(tǒng)編程                  
 13. 1  并行編程風(fēng)范和樣本程序                  
 13. 1. 1  五種并行編程風(fēng)范                  
 13. 1. 2　計(jì)算∏樣本程序                  
 13. 2　并行程序設(shè)計(jì)模型                  
 13. 2. 1  隱式并行模型                  
 13. 2. 2　數(shù)據(jù)并行模型                  
 13. 2. 3　消息傳遞模型                  
 13. 2. 4　共享變量模型                  
 13. 2. 5　并行程序設(shè)計(jì)模型比較                  
 13. 3　共享存儲(chǔ)并行編程                  
 13. 3. 1　ANSIX3H5共享存儲(chǔ)模型                  
 13. 3. 2　POSIX線程模型                  
 13. 3. 3　OpenMP標(biāo)準(zhǔn)                  
 13. 4　小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 第十四章  分布存儲(chǔ)系統(tǒng)并行編程                  
 14. 1  基于消息傳遞的并行編程                  
 14. 1. 1　SPMD并行程序                  
 14. 1. 2　MPMD并行程序                  
 14. 2　MPI并行編程                  
 14. 2. 1  最基本的MPI                  
 14. 2. 2  群體通信                  
 14. 2. 3  通信體                  
 14. 2. 4　導(dǎo)出數(shù)據(jù)類型                  
 14. 2. 5　點(diǎn)到點(diǎn)通信                  
 *14. 3  PVM并行編程                  
 14. 3. 1　PVM概貌                  
 14. 3. 2　PVM消息傳遞庫(kù)                  
 14. 4　基于數(shù)據(jù)并行的并行編程                  
 14. 4. 1　數(shù)據(jù)并行模型的特點(diǎn)                  
 14. 4. 2　數(shù)據(jù)并行編程的基本問(wèn)題                  
 14. 5　HPF并行編程                  
 14. 5. 1　HPF的語(yǔ)言特點(diǎn)                  
 14. 5. 2　HPF的數(shù)據(jù)并行機(jī)制                  
 14. 5. 3　HPF使用中的若干問(wèn)題                  
 14. 6　小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 附錄一　MPI的函數(shù)的C語(yǔ)言說(shuō)明                  
 附錄二　MPI的函數(shù)的Fortran語(yǔ)言說(shuō)明                  
 第十五章  并行程序設(shè)計(jì)環(huán)境與工具                  
 *15. 1  軟件工具與環(huán)境                  
 15. 1. 1  編碼工具                  
 15. 1. 2　軟件工程工具                  
 15. 1. 3　集成工具                  
 15. 1. 4　將來(lái)的工具與環(huán)境                  
 15. 2　并行編譯器                  
 15. 2. 1　編譯及其并行化                  
 15. 2. 2  相關(guān)分析                  
 15. 2. 3  代碼優(yōu)化                  
 15. 2. 4  代碼生成                  
 15. 3　并行程序調(diào)試和性能分析                  
 15. 3. 1  并行程序的調(diào)試                  
 15. 3. 2　并行程序的性能分析                  
 15. 3. 3  并行程序的可視化設(shè)計(jì)環(huán)境與工具                  
 15. 4　小結(jié)和導(dǎo)讀                  
 習(xí)題                  
 算法索引                  
 表格索引                  
 示范程序索引                  
 參考文獻(xiàn)                  
 并行與分布計(jì)算Web網(wǎng)址                  
 術(shù)語(yǔ)中-英對(duì)照及索引