MPI與OpenMP并行程序設(shè)計（C語言版）

第1章 動機和歷史
1.1 概述
1.2 現(xiàn)代科學(xué)方法
1.3 超級計算的進(jìn)化
1.4 現(xiàn)代并行計算機
1.4.1 Cosmic Cube并行計算機
1.4.2 商品化的并行計算機
1.4.3 Beowulf系統(tǒng)
1.4.4 先進(jìn)戰(zhàn)略計算計劃
1.5 尋找并行性
1.5.1 數(shù)據(jù)相關(guān)圖
1.5.2 數(shù)據(jù)并行性
1.5.3 功能并行性
1.5.4 流水線
1.5.5 計算規(guī)模的考慮因素
1.6 數(shù)據(jù)聚類
1.7 為并行計算機編程
1.7.1 擴展編譯器
1.7.2 擴展串行編程語言
1.7.3 增加并行編程層
1.7.4 創(chuàng)造一個并行語言
1.7.5 現(xiàn)狀
1.8 本章小結(jié)
1.9 主要術(shù)語
1.10 參考文獻(xiàn)
1.11 練習(xí)題
第2章 并行體系結(jié)構(gòu)
2.1 概述
2.2 互連網(wǎng)絡(luò)
2.2.1 共享介質(zhì)與開關(guān)介質(zhì)
2.2.2 開關(guān)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)
2.2.3 二維網(wǎng)格形網(wǎng)絡(luò)
2.2.4 二叉樹形網(wǎng)絡(luò)
2.2.5 超樹形網(wǎng)絡(luò)
2.2.6 蝶形網(wǎng)絡(luò)
2.2.7 超立方體網(wǎng)絡(luò)
2.2.8 混洗.交換網(wǎng)絡(luò)
2.2.9 小結(jié)
2.3 陣列處理機
2.3.1 體系結(jié)構(gòu)與數(shù)據(jù)并行
2.3.2 陣列處理機的性能
2.3.3 處理器互連網(wǎng)絡(luò)
2.3.4 處理器的啟動與阻塞
2.3.5 其他體系結(jié)構(gòu)特點
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 集群與工作站網(wǎng)絡(luò)之間的差異
2.6 弗林分類法
2.6.1 SISD
2.6.2 SIMD
2.6.3 MISD
2.6.4 MIMD
2.7 本章小結(jié)
2.8 主要術(shù)語
2.9 參考文獻(xiàn)
2.10 練習(xí)題
第3章 并行算法設(shè)計
3.1 概述
3.2 任務(wù)/通道模型
3.3 Foster的設(shè)計方法論
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.6 n-body問題
3.6.1 簡介
3.6.2 劃分
3.6.3 通信
3.6.4 聚集與映射
3.6.5 分析
3.7 增加數(shù)據(jù)輸入
3.7.1 簡介
3.7.2 通信
3.7.3 分析
3.8 本章小結(jié)
3.9 主要術(shù)語
3.10 參考文獻(xiàn)
3.11 練習(xí)題
第4章 消息傳遞編程
4.1 概述
4.2 消息傳遞模型
4.3 MPI接口
4.4 電路可滿足性問題
4.4.1 MPI_Init函數(shù)
4.4.2 MPI_Comm rank和MPI Comm_size函數(shù)
4.4.3 MPI Fimlize函數(shù)
4.4.4 編譯MPI程序
4.4.5 運行MPI程序
4.5 聚合通信簡介
MPI Reduce函數(shù)
4.6 檢測并行性能
4.6.1 MPI_Wtime和MPI_Wtick函數(shù)
4.6.2 MPI_Barrier函數(shù)
4.7 本章小結(jié)
4.8 主要術(shù)語
4.9 參考文獻(xiàn)
4.10 練習(xí)題
第5章 Eratosthenes篩法
5.1 概述
5.2 串行算法
5.3 并行性的來源
5.4 數(shù)據(jù)分解方法
5.4.1 交叉數(shù)據(jù)分解
5.4.2 按塊數(shù)據(jù)分解
5.4.3 用于按塊分解的宏
5.4.4 局部下標(biāo)還是全局下標(biāo)
5.4.5 塊分解的結(jié)果
5.5 開發(fā)并行算法
函數(shù)MPI Bcast
5.6 并行篩法算法的分析
5.7 并行程序的說明
5.8 測試
5.9 改進(jìn)
5.9.1 刪除偶數(shù)
5.9.2 消除廣播
5.9.3 循環(huán)的重新組織
5.9.4 測試
5.10 本章小結(jié)
5.11 主要術(shù)語
5.12 參考文獻(xiàn)
5.13 練習(xí)題
第6章 Floyd算法
6.1 概述
6.2 全點對最短路徑問題
6.3 運行時創(chuàng)建數(shù)組
6.4 設(shè)計并行算法
6.4.1 劃分
6.4.2 通信
6.4.3 聚合和映射
6.4.4 矩陣的輸入/輸出
6.5 點對點通信
6.5.1 函數(shù)MPI_Send
6.5.2 函數(shù)MPI_Recv
6.5.3 死鎖
6.6 并行程序的說明
6.7 分析和測試
6.8 本章小結(jié)
6.9 主要術(shù)語
6.10 參考文獻(xiàn)
6.11 練習(xí)題
第7章 性能分析
7.1 概述
7.2 加速比和效率
7.3 Amdahl定律
7.3.1 Amdahl定律的局限
7.3.2 Amdahl效應(yīng)
7.4 Gustafson-Barsis定律
7.5 Karp-Flatt量度
7.6 等效指標(biāo)
7.7 本章小結(jié)
7.8 主要術(shù)語
7.9 參考文獻(xiàn)
7.10 練習(xí)題
第8章 矩陣向量乘法
8.1 概述
8.2 串行算法
8.3 數(shù)據(jù)分解方式
8.4 矩陣按行分解
8.4.1 設(shè)計與分析
8.4.2 復(fù)制分塊的向量
8.4.3 函數(shù)MPI_Allgatherv
8.4.4 被復(fù)制向量的輸入/輸出
8.4.5 編寫并行程序
8.4.6 測試
8.5 矩陣按列分解
8.5.1 設(shè)計與分析
8.5.2 讀取按列分解的矩陣
8.5.3 函數(shù)MPI_Scatterv
8.5.4 打印輸出按列分塊矩陣
8.5.5 函數(shù)MPI_Gatherv
8.5.6 分發(fā)中間結(jié)果
8.5.7 函數(shù)MPI_Alltoallv
8.5.8 編寫并行程序
8.5.9 測試
8.6 棋盤式分解
8.6.1 設(shè)計與分析
8.6.2 創(chuàng)建通信域
8.6.3 函數(shù)MPI_Dims_create
8.6.4 函數(shù)MPI_Cart_create
8.6.5 讀取棋盤式矩陣
8.6.6 函數(shù)MPI_Cart_rank
8.6.7 函數(shù)MPI_Cart_coords
8.6.8 函數(shù)MPI_Comm_split
8.6.9 測試
8.7 本章小結(jié)
8.8 主要術(shù)語
8.9 參考文獻(xiàn)
8.10 練習(xí)題
第9章 文檔分類
9.1 概述
9.2 并行算法設(shè)計
9.2.1 劃分與通信
9.2.2 聚集和映射
9.2.3 管理者/工人模式
9.2.4 管理進(jìn)程
9.2.5 MPI_Abort函數(shù)
9.2.6 工人進(jìn)程
9.2.7 建立一個只有工人的通信域
9.3 非阻塞通信
9.3.1 管理進(jìn)程的通信
9.3.2 MPI_Irecv函數(shù)
9.3.3 MPI_Wait函數(shù)
9.3.4 工人的通信
9.3.5 MPI_Isend函數(shù)
9.3.6 MPI_Probe函數(shù)
9.3.7 MPI_Get_count函數(shù)
9.4 文檔分類的并行程序
9.5 算法改進(jìn)
9.5.1 按組分配文檔
9.5.2 流水線處理
9.5.3 MPI_Testsome函數(shù)
9.6 本章小結(jié)
9.7 主要術(shù)語
9.8 參考文獻(xiàn)
9.9 練習(xí)題
第10章 蒙特卡洛法
10.1 概述
10.1.1 為什么蒙特卡洛法能奏效
10.1.2 蒙特卡洛法與并行計算
10.2 串行隨機數(shù)生成器
10.2.1 線性同余法
10.2.2 滯后形斐波那契生成器
10.3 并行隨機數(shù)產(chǎn)生器
10.3.1 管理者-工人方法
10.3.2 蛙跳方法
10.3.3 序列分割
10.3.4 參數(shù)化
10.4 其他的隨機數(shù)分布
10.4.1 逆分布累積分布函數(shù)變換
10.4.2 Box-Muller變換
10.4.3 拒絕法
10.5 應(yīng)用示例
10.5.1 中子輸運
10.5.2 二維板上一個點的溫度
10.5.3 二維易辛模型
10.5.4 房間分配問題
10.5.5 車庫停車問題
10.5.6 交通環(huán)路
10.6 本章小結(jié)
10.7 主要術(shù)語
10.8 參考文獻(xiàn)
10.9 練習(xí)題
第11章 矩陣乘法
11.1 概述
11.2 矩陣相乘的串行算法
11.2.1 基于行的迭代算法
11.2.2 基于塊的遞歸算法
11.3 行塊分解并行算法
11.3.1 確定原始任務(wù)
11.3.2 聚合
11.3.3 通信和進(jìn)一步的聚合
11.3.4 分析
11.4 Cannon算法
11.4.1 組合
11.4.2 通信
11.4.3 分析
11.5 本章小結(jié)
11.6 主要術(shù)語
11.7 參考文獻(xiàn)
11.8 練習(xí)題
第12章 線性方程組求解
12.1 概述
12.2 基本術(shù)語
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 本章小結(jié)
12.8 主要術(shù)語
12.9 參考文獻(xiàn)
12.10 練習(xí)題
第13章 有限差分方法
13.1 概述
13.2 偏微分等式
13.2.1 偏微分方程的分類
13.2.2 差分商
13.3 弦振蕩問題
13.3.1 導(dǎo)出方程
13.3.2 串行程序
13.3.3 并行程序設(shè)計
13.3.4 等效分析
13.3.5 冗余計算
13.4 穩(wěn)定狀態(tài)熱量分布問題
13.4.1 方程的導(dǎo)出
13.4.2 串行程序?qū)С?br />13.4.3 并行程序設(shè)計
13.4.4 等效分析
13.4.5 實現(xiàn)細(xì)節(jié)
13.5 本章小結(jié)
13.6 主要術(shù)語
13.7 參考文獻(xiàn)
13.8 練習(xí)題
第14章 排序
14.1 概述
14.2 快速排序
14.3 并行快速排序算法
14.3.1 排序完畢的定義
14.3.2 算法開發(fā)
14.3.3 分析
14.4 超級快速排序
14.4.1 算法描述
14.4.2 等效分析
14.5 規(guī)則取樣并行排序
14.5.1 算法描述
14.5.2 等效分析
14.6 本章小結(jié)
14.7 主要術(shù)語
14.8 參考文獻(xiàn)
14.9 練習(xí)題
第15章 快速傅立葉變換
15.1 概述
15.2 傅立葉分析
15.3 離散傅立葉變換
15.3.1 離散傅立葉逆變換
15.3.2 應(yīng)用示例：多項式乘法
15.4 快速傅立葉變換
15.5 并行程序設(shè)計
15.5.1 分割與通信
15.5.2 聚合與映射
15.5.3 等效分析
15.6 本章小結(jié)
15.7 主要術(shù)語
15.8 參考文獻(xiàn)
15.9 練習(xí)題
第16章 組合搜索
16.1 概述
16.2 回溯搜索
16.2.1 示例
16.2.2 時間和空間復(fù)雜性
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.2 Alpha-Beta剪枝
16.7.3 Alpha-Beta剪枝法的改進(jìn)
16.8 并行Alpha-Beta搜索
16.8.1 并行渴望搜索
16.8.2 并行子樹估值
16.8.3 分布式樹搜索
16.9 本章小結(jié)
16.10 主要術(shù)語
16.11 參考文獻(xiàn)
16.12 練習(xí)題
第17章 共享存儲編程
17.1 概述
17.2 共享存儲模型
17.3 對for循環(huán)的并行化
17.3.1 parallel for編譯指導(dǎo)語句
17.3.2 omp_get_num_procs函數(shù)
17.3.3 omp_set_num_theads函數(shù)
17.4 聲明私有變量
17.4.1 private子句
17.4.2 firstprivate子句
17.4.3 lastprivate子句
17.5 臨界區(qū)
critical編譯指導(dǎo)語句
17.6 歸約操作
17.7 性能改善
17.7.1 循環(huán)轉(zhuǎn)化
17.7.2 條件執(zhí)行循環(huán)
17.7.3 循環(huán)調(diào)度
17.8 更普遍的數(shù)據(jù)并行
17.8.1 parallel編譯指導(dǎo)語句
17.8.2 omp_get_thread num函數(shù)
17.8.3 omp_get_num_threads函數(shù)
17.8.4 編譯指導(dǎo)語句for
17.8.5 single編譯指導(dǎo)語句
17.8.6 nowait子句
17.9 功能并行
17.9.1 parallel sections編譯指導(dǎo)語句
17.9.2 section編譯指導(dǎo)語句
17.9.3 sections編譯指導(dǎo)語句
17.10 本章小結(jié)
17.1l 主要術(shù)語
17.12 參考文獻(xiàn)
17.13 練習(xí)題
第18章 融合OpenMP和MPI
18.1概述
18.2 共軛梯度算法
18.2.1 MPI程序
18.2.2 函數(shù)級程序輪廓刻畫
18.2.3 對函數(shù)matrix_vector_pmduct進(jìn)行并行化
18.2.4 測試程序
18.3 Jacobi方法
18.3.1 MPI程序輪廓刻畫
18.3.2 對函數(shù)find_steadv_state并行化
18.3.3 測試程序
18.4 本章小結(jié)
18.5 練習(xí)題
附錄A MPI函數(shù)
附錄B 工具函數(shù)
B.1 MyMPI.h頭文件
B.2 MyMPI.c源文件
附錄C 調(diào)試MPI程序
C.1 概述
C.2 MPI程序常見錯誤
C.2.1 死鎖錯誤
C.2.2 導(dǎo)致不準(zhǔn)確結(jié)果的錯誤
C.2.3 組通信的優(yōu)點
C.3 實用調(diào)試策略
附錄D 復(fù)數(shù)回顧
附錄E OpenMP函數(shù)
參考文獻(xiàn)