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

第1章 動(dòng)機(jī)和歷史
1.1 概述
1.2 現(xiàn)代科學(xué)方法
1.3 超級(jí)計(jì)算的進(jìn)化
1.4 現(xiàn)代并行計(jì)算機(jī)
1.4.1 Cosmic Cube并行計(jì)算機(jī)
1.4.2 商品化的并行計(jì)算機(jī)
1.4.3 Beowulf系統(tǒng)
1.4.4 先進(jìn)戰(zhàn)略計(jì)算計(jì)劃
1.5 尋找并行性
1.5.1 數(shù)據(jù)相關(guān)圖
1.5.2 數(shù)據(jù)并行性
1.5.3 功能并行性
1.5.4 流水線
1.5.5 計(jì)算規(guī)模的考慮因素
1.6 數(shù)據(jù)聚類
1.7 為并行計(jì)算機(jī)編程
1.7.1 擴(kuò)展編譯器
1.7.2 擴(kuò)展串行編程語(yǔ)言
1.7.3 增加并行編程層
1.7.4 創(chuàng)造一個(gè)并行語(yǔ)言
1.7.5 現(xiàn)狀
1.8 本章小結(jié)
1.9 主要術(shù)語(yǔ)
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 陣列處理機(jī)
2.3.1 體系結(jié)構(gòu)與數(shù)據(jù)并行
2.3.2 陣列處理機(jī)的性能
2.3.3 處理器互連網(wǎng)絡(luò)
2.3.4 處理器的啟動(dòng)與阻塞
2.3.5 其他體系結(jié)構(gòu)特點(diǎn)
2.3.6 陣列處理機(jī)的缺點(diǎn)
2.4 多處理器
2.4.1 集中式多處理器
2.4.2 分布式多處理器
2.5 多計(jì)算機(jī)
2.5.1 非對(duì)稱多計(jì)算機(jī)
2.5.2 對(duì)稱多計(jì)算機(jī)
2.5.3 怎樣的模型對(duì)商用集群來(lái)說(shuō)是最佳的
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ù)語(yǔ)
2.9 參考文獻(xiàn)
2.10 練習(xí)題
第3章 并行算法設(shè)計(jì)
3.1 概述
3.2 任務(wù)/通道模型
3.3 Foster的設(shè)計(jì)方法論
3.3.1 劃分
3.3.2 通信
3.3.3 聚集
3.3.4 映射
3.4 邊界值問(wèn)題
3.4.1 簡(jiǎn)介
3.4.2 劃分
3.4.3 通信
3.4.4 聚集與映射
3.4.5 分析
3.5 找出最大值
3.5.1 簡(jiǎn)介
3.5.2 劃分
3.5.3 通信
3.5.4 聚集與映射
3.5.5 分析
3.6 n-body問(wèn)題
3.6.1 簡(jiǎn)介
3.6.2 劃分
3.6.3 通信
3.6.4 聚集與映射
3.6.5 分析
3.7 增加數(shù)據(jù)輸入
3.7.1 簡(jiǎn)介
3.7.2 通信
3.7.3 分析
3.8 本章小結(jié)
3.9 主要術(shù)語(yǔ)
3.10 參考文獻(xiàn)
3.11 練習(xí)題
第4章 消息傳遞編程
4.1 概述
4.2 消息傳遞模型
4.3 MPI接口
4.4 電路可滿足性問(wèn)題
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 運(yùn)行MPI程序
4.5 聚合通信簡(jiǎn)介
MPI Reduce函數(shù)
4.6 檢測(cè)并行性能
4.6.1 MPI_Wtime和MPI_Wtick函數(shù)
4.6.2 MPI_Barrier函數(shù)
4.7 本章小結(jié)
4.8 主要術(shù)語(yǔ)
4.9 參考文獻(xiàn)
4.10 練習(xí)題
第5章 Eratosthenes篩法
5.1 概述
5.2 串行算法
5.3 并行性的來(lái)源
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 并行程序的說(shuō)明
5.8 測(cè)試
5.9 改進(jìn)
5.9.1 刪除偶數(shù)
5.9.2 消除廣播
5.9.3 循環(huán)的重新組織
5.9.4 測(cè)試
5.10 本章小結(jié)
5.11 主要術(shù)語(yǔ)
5.12 參考文獻(xiàn)
5.13 練習(xí)題
第6章 Floyd算法
6.1 概述
6.2 全點(diǎn)對(duì)最短路徑問(wèn)題
6.3 運(yùn)行時(shí)創(chuàng)建數(shù)組
6.4 設(shè)計(jì)并行算法
6.4.1 劃分
6.4.2 通信
6.4.3 聚合和映射
6.4.4 矩陣的輸入/輸出
6.5 點(diǎn)對(duì)點(diǎn)通信
6.5.1 函數(shù)MPI_Send
6.5.2 函數(shù)MPI_Recv
6.5.3 死鎖
6.6 并行程序的說(shuō)明
6.7 分析和測(cè)試
6.8 本章小結(jié)
6.9 主要術(shù)語(yǔ)
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ù)語(yǔ)
7.9 參考文獻(xiàn)
7.10 練習(xí)題
第8章 矩陣向量乘法
8.1 概述
8.2 串行算法
8.3 數(shù)據(jù)分解方式
8.4 矩陣按行分解
8.4.1 設(shè)計(jì)與分析
8.4.2 復(fù)制分塊的向量
8.4.3 函數(shù)MPI_Allgatherv
8.4.4 被復(fù)制向量的輸入/輸出
8.4.5 編寫并行程序
8.4.6 測(cè)試
8.5 矩陣按列分解
8.5.1 設(shè)計(jì)與分析
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 測(cè)試
8.6 棋盤式分解
8.6.1 設(shè)計(jì)與分析
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 測(cè)試
8.7 本章小結(jié)
8.8 主要術(shù)語(yǔ)
8.9 參考文獻(xiàn)
8.10 練習(xí)題
第9章 文檔分類
9.1 概述
9.2 并行算法設(shè)計(jì)
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 建立一個(gè)只有工人的通信域
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ù)語(yǔ)
9.8 參考文獻(xiàn)
9.9 練習(xí)題
第10章 蒙特卡洛法
10.1 概述
10.1.1 為什么蒙特卡洛法能奏效
10.1.2 蒙特卡洛法與并行計(jì)算
10.2 串行隨機(jī)數(shù)生成器
10.2.1 線性同余法
10.2.2 滯后形斐波那契生成器
10.3 并行隨機(jī)數(shù)產(chǎn)生器
10.3.1 管理者-工人方法
10.3.2 蛙跳方法
10.3.3 序列分割
10.3.4 參數(shù)化
10.4 其他的隨機(jī)數(shù)分布
10.4.1 逆分布累積分布函數(shù)變換
10.4.2 Box-Muller變換
10.4.3 拒絕法
10.5 應(yīng)用示例
10.5.1 中子輸運(yùn)
10.5.2 二維板上一個(gè)點(diǎn)的溫度
10.5.3 二維易辛模型
10.5.4 房間分配問(wèn)題
10.5.5 車庫(kù)停車問(wèn)題
10.5.6 交通環(huán)路
10.6 本章小結(jié)
10.7 主要術(shù)語(yǔ)
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ù)語(yǔ)
11.7 參考文獻(xiàn)
11.8 練習(xí)題
第12章 線性方程組求解
12.1 概述
12.2 基本術(shù)語(yǔ)
12.3 回代法
12.3.1 串行算法
12.3.2 面向行的并行算法
12.3.3 面向列的并行算法
12.3.4 對(duì)比
12.4 高斯消去法
12.4.1 串行算法
12.4.2 并行算法
12.4.3 面向行的算法
12.4.4 面向列的算法
12.4.5 對(duì)比
12.4.6 面向行的流水線算法
12.5 迭代法
12.6 共軛梯度法
12.6.1 串行算法
12.6.2 并行算法
12.7 本章小結(jié)
12.8 主要術(shù)語(yǔ)
12.9 參考文獻(xiàn)
12.10 練習(xí)題
第13章 有限差分方法
13.1 概述
13.2 偏微分等式
13.2.1 偏微分方程的分類
13.2.2 差分商
13.3 弦振蕩問(wèn)題
13.3.1 導(dǎo)出方程
13.3.2 串行程序
13.3.3 并行程序設(shè)計(jì)
13.3.4 等效分析
13.3.5 冗余計(jì)算
13.4 穩(wěn)定狀態(tài)熱量分布問(wèn)題
13.4.1 方程的導(dǎo)出
13.4.2 串行程序?qū)С?br />13.4.3 并行程序設(shè)計(jì)
13.4.4 等效分析
13.4.5 實(shí)現(xiàn)細(xì)節(jié)
13.5 本章小結(jié)
13.6 主要術(shù)語(yǔ)
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 超級(jí)快速排序
14.4.1 算法描述
14.4.2 等效分析
14.5 規(guī)則取樣并行排序
14.5.1 算法描述
14.5.2 等效分析
14.6 本章小結(jié)
14.7 主要術(shù)語(yǔ)
14.8 參考文獻(xiàn)
14.9 練習(xí)題
第15章 快速傅立葉變換
15.1 概述
15.2 傅立葉分析
15.3 離散傅立葉變換
15.3.1 離散傅立葉逆變換
15.3.2 應(yīng)用示例：多項(xiàng)式乘法
15.4 快速傅立葉變換
15.5 并行程序設(shè)計(jì)
15.5.1 分割與通信
15.5.2 聚合與映射
15.5.3 等效分析
15.6 本章小結(jié)
15.7 主要術(shù)語(yǔ)
15.8 參考文獻(xiàn)
15.9 練習(xí)題
第16章 組合搜索
16.1 概述
16.2 回溯搜索
16.2.1 示例
16.2.2 時(shí)間和空間復(fù)雜性
16.3 并行回溯算法
16.4 分布式終止檢測(cè)
16.5 分支定界法
16.5.1 示例
16.5.2 串行算法
16.5.3 分析
16.6 并行分支定界法
16.6.1 存儲(chǔ)和共享待解的子問(wèn)題
16.6.2 效率
16.6.3 停機(jī)條件
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ù)語(yǔ)
16.11 參考文獻(xiàn)
16.12 練習(xí)題
第17章 共享存儲(chǔ)編程
17.1 概述
17.2 共享存儲(chǔ)模型
17.3 對(duì)for循環(huán)的并行化
17.3.1 parallel for編譯指導(dǎo)語(yǔ)句
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)語(yǔ)句
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)語(yǔ)句
17.8.2 omp_get_thread num函數(shù)
17.8.3 omp_get_num_threads函數(shù)
17.8.4 編譯指導(dǎo)語(yǔ)句for
17.8.5 single編譯指導(dǎo)語(yǔ)句
17.8.6 nowait子句
17.9 功能并行
17.9.1 parallel sections編譯指導(dǎo)語(yǔ)句
17.9.2 section編譯指導(dǎo)語(yǔ)句
17.9.3 sections編譯指導(dǎo)語(yǔ)句
17.10 本章小結(jié)
17.1l 主要術(shù)語(yǔ)
17.12 參考文獻(xiàn)
17.13 練習(xí)題
第18章 融合OpenMP和MPI
18.1概述
18.2 共軛梯度算法
18.2.1 MPI程序
18.2.2 函數(shù)級(jí)程序輪廓刻畫
18.2.3 對(duì)函數(shù)matrix_vector_pmduct進(jìn)行并行化
18.2.4 測(cè)試程序
18.3 Jacobi方法
18.3.1 MPI程序輪廓刻畫
18.3.2 對(duì)函數(shù)find_steadv_state并行化
18.3.3 測(cè)試程序
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程序常見(jiàn)錯(cuò)誤
C.2.1 死鎖錯(cuò)誤
C.2.2 導(dǎo)致不準(zhǔn)確結(jié)果的錯(cuò)誤
C.2.3 組通信的優(yōu)點(diǎn)
C.3 實(shí)用調(diào)試策略
附錄D 復(fù)數(shù)回顧
附錄E OpenMP函數(shù)
參考文獻(xiàn)