圖書簡介
本書是美國Oregon州立大學的MichaelJ.Quinn教授在多年講授“並行程式設計”課程的基礎上編寫而成的，主要介紹用C語言，並結合使用MPI和OpenMP進行並行程式設計，內容包括並行體系結構、並行算法設計、訊息傳遞編程、Eratosthenes篩法、Floyd算法、性能分析、矩陣向量乘法、文檔分類、蒙特卡洛法、矩陣乘法、線性方程組求解、有限差分方法、排序、快速傅立葉變換、組合搜尋、共享存儲編程、融合OpenMP和MPI以及5個附錄。
本書按授課方式安排章節，通過劃分、通信、集聚和映射等四步的並行程式設計方法，來解決各種實際的並行性問題，使讀者掌握系統化的並行程式設計方法，開發出高效的並行程式。
本書不僅是一本優秀的並行程式設計教材，對廣大的相關專業人員也很有參考價值。
前言
本書是用C語言進行MPI和OpenMP並行編程的實用教程，適用於大學高年級本科生、研究生以及利用本書進行自學的計算機專業人員。讀者需要有很好的C語言編程經驗，並學習過基礎的算法分析課程。
對並行程式設計感興趣的Fortran程式設計師也可以從本書中受益。儘管本書中的例子都是用C寫的，但是使用MPI和OpenMP進行並行程式設計的基本概念對於C和Fortran來說是基本相同的。
在過去20年中，我為數以百計的本科生和研究生講授了並行程式設計。在這個過程中，我逐步了解了人們在開始"用並行方式思考"和編寫並行程式時所遇到的各種問題。逐步設計和實現的程式更容易讓學生們受益。因此我的哲學是僅在需要時才引入新的功能，儘可能地在解決設計、實現和分析中的具體問題時引入新概念。
本書的前兩章解釋了並行計算的起源並對並行體系結構進行了綜述。第3章介紹了Foster的並行算法設計方法論和幾個套用該方法的實例。第4、5、6、8和9章介紹了如何使用該設計方法，為一系列從易到難的問題開發MPI程式。這些章節中用到的27個MPI函式是MPI函式館的一個子集，但已經足夠為很多類型的實際套用設計並行程式。這些章節還介紹了能夠簡化矩陣和向量I/O的函式，附錄B中給出了該I/O庫的原始碼。
第4、5、6和8章的程式在一個集群系統上進行了性能測試，並在書中給出了測試結果。由於新的處理器比本書中所用到的要快得多，讀者可能會發現本書中用到的處理器已經落後了好幾代。但是在書中給出測試結果並不是要讓讀者對計算速度感到吃驚，而是為了表明將串列程式性能、互連網路的通信和延遲等信息集成起來，可以相當準確地預測並行程式的性能。
第7章主要介紹了分析和預測並行系統性能所用到的4種度量：Amdahl定律、Gustafson-Barsis定律、Karp-Flatt度量和等效度量。
第10~16章提供了更多的例子，表明如何分析問題並設計好的並行算法來解決問題。使用MPI來實現並行算法的任務則留給了讀者。我介紹了蒙特卡洛法和並行隨機數生成的相關問題。後面幾章介紹了若干關鍵算法：矩陣乘法、高斯消去法、共軛梯度法、有限元方法、排序、FFT、回溯搜尋、分支定界搜尋以及Alpha-Beta搜尋。
第17、18章介紹了新的共享記憶體編程標準OpenMP。介紹了將串列程式段轉化為並行程式段所需的OpenMP功能，並用兩個實例講解了如何將MPI程式轉化為MPI/OpenMP混合程式。在多處理器集群系統上，混合程式比MPI程式能夠得到更好的性能。
本書包含了超過一學期並行程式設計課程所需的內容。儘管並行程式設計比傳統程式設計要困難得多，但也會帶來更多的回報。即使在老師的指導與幫助下，大多數學生對於在多個處理器上執行單個任務仍然會覺得有些害怕。但是，當他們那看到調試過的程式比"普通"C程式要快得多的時候，這種害怕就轉換成了真正的成就感。因此，編程練習應該是本課程的中心內容。
幸運的是，並行計算機比以前更容易獲得了。如果無法使用商用並行計算機，使用幾台PC機、網路設備和自由軟體搭建一個小型的集群系統是一件很容易的事情。
圖前．1說明了本書章節的閱讀順序。圖中實線箭頭代表強依賴關係，虛線箭頭代表弱依賴關係。按照章節順序閱讀本書將滿足所有的章節依賴關係。但是，如果你希望讓學生儘快開始用C語言編寫MPI程式，那么你可能希望跳過第2章，或僅講授該章的1-2節內容。如果你希望集中講授數值算法，那么可以跳過第5章，並用其他方式介紹函式MPI Bcast。如果你希望學生從蒙特卡洛法開始，那么可以在第4章後直接跳到第10章。如果你希望在MPI之前就講授OpenMP，可以在第3章後直接跳到第17章。
感謝McGraw-Hill出版社的每位員工，他們幫助我創造了這本書，特別是BetsyJones，Michelle Flomenhoft和Kay Brimeyer。感謝他們的贊助、鼓勵和幫助。同樣感謝MaggieMurphy和Interactive Composition Corporation公司其他排版者所提供的幫助。
目錄
第1章動機和歷史
1.1概述
1.2現代科學方法
1.3超級計算的進化
1.4現代並行計算機
1.4.1CosmicCube並行計算機
1.4.2商品化的並行計算機
1.4.3Beowulf系統
1.4.4先進戰略計算計畫
1.5尋找並行性
1.5.1數據相關圖
1.5.2數據並行性
1.5.3功能並行性
1.5.4流水線
1.5.5計算規模的考慮因素
1.6數據聚類
1.7為並行計算機編程
1.7.1擴展編譯器
1.7.2擴展串列程式語言
1.7.3增加並行編程層
1.7.4創造一個並行語言
1.7.5現狀
1.8本章小結
1.9主要術語
1.10參考文獻
1.11練習題
第2章並行體系結構
2.1概述
2.2互連網路
2.2.1共享介質與開關介質
2.2.2開關網路的拓撲結構
2.2.3二維格線形網路
2.2.4二叉樹形網路
2.2.5超樹形網路
2.2.6蝶形網路
2.2.7超立方體網路
2.2.8混洗.交換網路
2.2.9小結
2.3陣列處理機
2.3.1體系結構與數據並行
2.3.2陣列處理機的性能
2.3.3處理器互連網路
2.3.4處理器的啟動與阻塞
2.3.5其他體系結構特點
2.3.6陣列處理機的缺點
2.4多處理器
2.4.1集中式多處理器
2.4.2分散式多處理器
2.5多計算機
2.5.1非對稱多計算機
2.5.2對稱多計算機
2.5.3怎樣的模型對商用集群來說是最佳的
2.5.4集群與工作站網路之間的差異
2.6弗林分類法
2.6.1SISD
2.6.2SIMD
2.6.3MISD
2.6.4MIMD
2.7本章小結
2.8主要術語
2.9參考文獻
2.10練習題
第3章並行算法設計
3.1概述
3.2任務/通道模型
3.3Foster的設計方法論
3.3.1劃分
3.3.2通信
3.3.3聚集
3.3.4映射
3.4邊界值問題
3.4.1簡介
3.4.2劃分
3.4.3通信
3.4.4聚集與映射
3.4.5分析
3.5找出最大值
3.5.1簡介
3.5.2劃分
3.5.3通信
3.5.4聚集與映射
3.5.5分析
3.6n-body問題
3.6.1簡介
3.6.2劃分
3.6.3通信
3.6.4聚集與映射
3.6.5分析
3.7增加數據輸入
3.7.1簡介
3.7.2通信
3.7.3分析
3.8本章小結
3.9主要術語
3.10參考文獻
3.11練習題
第4章訊息傳遞編程
4.1概述
4.2訊息傳遞模型
4.3MPI接口
4.4電路可滿足性問題
4.4.1MPI_Init函式
4.4.2MPI_Commrank和MPIComm_size函式
4.4.3MPIFimlize函式
4.4.4編譯MPI程式
4.4.5運行MPI程式
4.5聚合通信簡介
MPIReduce函式
4.6檢測並行性能
4.6.1MPI_Wtime和MPI_Wtick函式
4.6.2MPI_Barrier函式
4.7本章小結
4.8主要術語
4.9參考文獻
4.10練習題
第5章Eratosthenes篩法
5.1概述
5.2串列算法
5.3並行性的來源
5.4數據分解方法
5.4.1交叉數據分解
5.4.2按塊數據分解
5.4.3用於按塊分解的宏
5.4.4局部下標還是全局下標
5.4.5塊分解的結果
5.5開發並行算法
函式MPIBcast
5.6並行篩法算法的分析
5.7並行程式的說明
5.8測試
5.9改進
5.9.1刪除偶數
5.9.2消除廣播
5.9.3循環的重新組織
5.9.4測試
5.10本章小結
5.11主要術語
5.12參考文獻
5.13練習題
第6章Floyd算法
6.1概述
6.2全點對最短路徑問題
6.3運行時創建數組
6.4設計並行算法
6.4.1劃分
6.4.2通信
6.4.3聚合和映射
6.4.4矩陣的輸入/輸出
6.5點對點通信
6.5.1函式MPI_Send
6.5.2函式MPI_Recv
6.5.3死鎖
6.6並行程式的說明
6.7分析和測試
6.8本章小結
6.9主要術語
6.10參考文獻
6.11練習題
第7章性能分析
7.1概述
7.2加速比和效率
7.3Amdahl定律
7.3.1Amdahl定律的局限
7.3.2Amdahl效應
7.4Gustafson-Barsis定律
7.5Karp-Flatt量度
7.6等效指標
7.7本章小結
7.8主要術語
7.9參考文獻
7.10練習題
第8章矩陣向量乘法
8.1概述
8.2串列算法
8.3數據分解方式
8.4矩陣按行分解
8.4.1設計與分析
8.4.2複製分塊的向量
8.4.3函式MPI_Allgatherv
8.4.4被複製向量的輸入/輸出
8.4.5編寫並行程式
8.4.6測試
8.5矩陣按列分解
8.5.1設計與分析
8.5.2讀取按列分解的矩陣
8.5.3函式MPI_Scatterv
8.5.4列印輸出按列分塊矩陣
8.5.5函式MPI_Gatherv
8.5.6分發中間結果
8.5.7函式MPI_Alltoallv
8.5.8編寫並行程式
8.5.9測試
8.6棋盤式分解
8.6.1設計與分析
8.6.2創建通信域
8.6.3函式MPI_Dims_create
8.6.4函式MPI_Cart_create
8.6.5讀取棋盤式矩陣
8.6.6函式MPI_Cart_rank
8.6.7函式MPI_Cart_coords
8.6.8函式MPI_Comm_split
8.6.9測試
8.7本章小結
8.8主要術語
8.9參考文獻
8.10練習題
第9章文檔分類
9.1概述
9.2並行算法設計
9.2.1劃分與通信
9.2.2聚集和映射
9.2.3管理者/工人模式
9.2.4管理進程
9.2.5MPI_Abort函式
9.2.6工人進程
9.2.7建立一個只有工人的通信域
9.3非阻塞通信
9.3.1管理進程的通信
9.3.2MPI_Irecv函式
9.3.3MPI_Wait函式
9.3.4工人的通信
9.3.5MPI_Isend函式
9.3.6MPI_Probe函式
9.3.7MPI_Get_count函式
9.4文檔分類的並行程式
9.5算法改進
9.5.1按組分配文檔
9.5.2流水線處理
9.5.3MPI_Testsome函式
9.6本章小結
9.7主要術語
9.8參考文獻
9.9練習題
第10章蒙特卡洛法
10.1概述
10.1.1為什麼蒙特卡洛法能奏效
10.1.2蒙特卡洛法與並行計算
10.2串列隨機數生成器
10.2.1線性同餘法
10.2.2滯後形斐波那契生成器
10.3並行隨機數產生器
10.3.1管理者-工人方法
10.3.2蛙跳方法
10.3.3序列分割
10.3.4參數化
10.4其他的隨機數分布
10.4.1逆分布累積分布函式變換
10.4.2Box-Muller變換
10.4.3拒絕法
10.5套用示例
10.5.1中子輸運
10.5.2二維板上一個點的溫度
10.5.3二維易辛模型
10.5.4房間分配問題
10.5.5車庫停車問題
10.5.6交通環路
10.6本章小結
10.7主要術語
10.8參考文獻
10.9練習題
第11章矩陣乘法
11.1概述
11.2矩陣相乘的串列算法
11.2.1基於行的疊代算法
11.2.2基於塊的遞歸算法
11.3行塊分解並行算法
11.3.1確定原始任務
11.3.2聚合
11.3.3通信和進一步的聚合
11.3.4分析
11.4Cannon算法
11.4.1組合
11.4.2通信
11.4.3分析
11.5本章小結
11.6主要術語
11.7參考文獻
11.8練習題
第12章線性方程組求解
12.1概述
12.2基本術語
12.3回代法
12.3.1串列算法
12.3.2面向行的並行算法
12.3.3面向列的並行算法
12.3.4對比
12.4高斯消去法
12.4.1串列算法
12.4.2並行算法
12.4.3面向行的算法
12.4.4面向列的算法
12.4.5對比
12.4.6面向行的流水線算法
12.5疊代法
12.6共軛梯度法
12.6.1串列算法
12.6.2並行算法
12.7本章小結
12.8主要術語
12.9參考文獻
12.10練習題
第13章有限差分方法
13.1概述
13.2偏微分等式
13.2.1偏微分方程的分類
13.2.2差分商
13.3弦振盪問題
13.3.1導出方程
13.3.2串列程式
13.3.3並行程式設計
13.3.4等效分析
13.3.5冗餘計算
13.4穩定狀態熱量分布問題
13.4.1方程的導出
13.4.2串列程式導出
13.4.3並行程式設計
13.4.4等效分析
13.4.5實現細節
13.5本章小結
13.6主要術語
13.7參考文獻
13.8練習題
第14章排序
14.1概述
14.2快速排序
14.3並行快速排序算法
14.3.1排序完畢的定義
14.3.2算法開發
14.3.3分析
14.4超級快速排序
14.4.1算法描述
14.4.2等效分析
14.5規則取樣並行排序
14.5.1算法描述
14.5.2等效分析
14.6本章小結
14.7主要術語
14.8參考文獻
14.9練習題
第15章快速傅立葉變換
15.1概述
15.2傅立葉分析
15.3離散傅立葉變換
15.3.1離散傅立葉逆變換
15.3.2套用示例：多項式乘法
15.4快速傅立葉變換
15.5並行程式設計
15.5.1分割與通信
15.5.2聚合與映射
15.5.3等效分析
15.6本章小結
15.7主要術語
15.8參考文獻
15.9練習題
第16章組合搜尋
16.1概述
16.2回溯搜尋
16.2.1示例
16.2.2時間和空間複雜性
16.3並行回溯算法
16.4分散式終止檢測
16.5分支定界法
16.5.1示例
16.5.2串列算法
16.5.3分析
16.6並行分支定界法
16.6.1存儲和共享待解的子問題
16.6.2效率
16.6.3停機條件
16.7搜尋博弈樹
16.7.1最大最小算法
16.7.2Alpha-Beta剪枝
16.7.3Alpha-Beta剪枝法的改進
16.8並行Alpha-Beta搜尋
16.8.1並行渴望搜尋
16.8.2並行子樹估值
16.8.3分散式樹搜尋
16.9本章小結
16.10主要術語
16.11參考文獻
16.12練習題
第17章共享存儲編程
17.1概述
17.2共享存儲模型
17.3對for循環的並行化
17.3.1parallelfor編譯指導語句
17.3.2omp_get_num_procs函式
17.3.3omp_set_num_theads函式
17.4聲明私有變數
17.4.1private子句
17.4.2firstprivate子句
17.4.3lastprivate子句
17.5臨界區
critical編譯指導語句
17.6歸約操作
17.7性能改善
17.7.1循環轉化
17.7.2條件執行循環
17.7.3循環調度
17.8更普遍的數據並行
17.8.1parallel編譯指導語句
17.8.2omp_get_threadnum函式
17.8.3omp_get_num_threads函式
17.8.4編譯指導語句for
17.8.5single編譯指導語句
17.8.6nowait子句
17.9功能並行
17.9.1parallelsections編譯指導語句
17.9.2section編譯指導語句
17.9.3sections編譯指導語句
17.10本章小結
17.1l主要術語
17.12參考文獻
17.13練習題
第18章融合OpenMP和MPI
18.1概述
18.2共軛梯度算法
18.2.1MPI程式
18.2.2函式級程式輪廓刻畫
18.2.3對函式matrix_vector_pmduct進行並行化
18.2.4測試程式
18.3Jacobi方法
18.3.1MPI程式輪廓刻畫
18.3.2對函式find_steadv_state並行化
18.3.3測試程式
18.4本章小結
18.5練習題
附錄AMPI函式
附錄B工具函式
B.1MyMPI.h頭檔案
B.2MyMPI.c源檔案
附錄C調試MPI程式
C.1概述
C.2MPI程式常見錯誤
C.2.1死鎖錯誤
C.2.2導致不準確結果的錯誤
C.2.3組通信的優點
C.3實用調試策略
附錄D複數回顧
附錄EOpenMP函式
參考文獻
