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

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