MPI與Open MP並行程式設計：C語言版

《MPI與Open MP並行程式設計：C語言版》是2004年清華大學出版社出版的圖書，作者是Michael J. Qiunn。

基本介紹

• 書名：MPI與Open MP並行程式設計：C語言版
• ISBN：9787302095552
• 定價：51元
• 出版時間：2004-10-26
• 裝幀：平裝

圖書簡介

本書是美國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函式

參考文獻