並行計算

目錄
前言
第1章 MPI 簡介I 1
1.1 矩陣向量乘法的順序實現 2
1.2 矩陣向量乘法的並行算法 4
1.3 矩陣向量乘法並行算法的程序實現 4
1.3.1 並行編程的模型和技術 4
1.3.2 MPI基礎——一個簡單的測試程序 5
1.3.3 從文件讀取輸入參數並分配至各個進程 6
1.3.4 進程間消息發送與接收的基本函數：Send和Recv 8
1.3.5 集體通信函數：Bcast.12
1.3.6 從文件讀取矩陣並分配至各個進程 13
1.3.7 從文件讀取向量並分配至各個進程 15
1.3.8 矩陣與向量的並行乘法 16
1.3.9 將不同進程中的數組片段匯集成完整數組 17
1.3.10 使用Probe函數優化信息收集 18
1.3.11 集體通信函數Gather和Scatter 21
1.4 適用於任意數量進程的推廣程序 23
1.5 優化程序實現的可能方法 28
1.5.1 一個優化程序的例子 28
1.5.2 消息傳遞函數：Bsend和Rsend 29
第2章 MPI簡介II 30
2.1 向量標量積計算的順序程序 30
2.2 計算向量標量積的並行算法 31
2.3 向量標量積並行算法的編程實現 32
2.3.1 基本代碼的實現 32
2.3.2 集體通信函數：Reduce和Allreduce 36
2.4 轉置矩陣與向量相乘的並行算法 37
2.5 轉置矩陣與向量相乘的並行算法的程序實現 38
2.5.1 其他集體通信函數 41
2.6 階段總結 42
第3章 求解線性代數方程組的共軛梯度法的並行算法實現 43
3.1 共軛梯度法的順序實現 44
3.2 共軛梯度法的並行實現 46
3.2.1 進程中計算數據的準備 46
3.2.2 計算部分 52
3.2.3 本章並行算法實現的優缺點分析 55
3.3 共軛梯度法的簡化並行實現 56
第4章 並行程序的效率和可擴展性 60
4.1 阿姆達爾定律 60
4.1.1 第3章中並行算法的理論分析 61
4.2 第3章中並行算法在程序實現中的實際加速 63
4.2.1 測量並行程序運行時間的方法 63
4.2.2 測試並行程序所用多處理器系統的特性 64
4.2.3 測試計算結果 65
4.3 並行程序的效率和擴展性分析 67
4.4 提高效率和擴展性的策略 69
第5章 使用進程組和通信器進行操作.71
5.1 基於二維塊劃分的矩陣與向量相乘的並行算法 71
5.2 基於二維塊劃分的轉置矩陣與向量相乘的並行算法 74
5.3 進程組和通信器 75
5.3.1 進程組操作 75
5.3.2 通信器操作 77
5.4 基於二維塊劃分的共軛梯度法的高級並行實現 81
5.4.1 進程中計算數據的準備 81
5.4.2 計算部分 94
5.5 並行程序的效率和可擴展性評估 98
5.6 本章並行程序實現的優缺點分析 100
第6章 虛擬拓撲 101
6.1 虛擬拓撲結構 101
6.1.1 基於笛卡兒拓撲的基本函數 101
6.1.2 進程間消息傳遞函數：Sendrecv和Sendrecv_replace 106
6.2 基於二維環形虛擬拓撲的共軛梯度法並行實現.109
6.2.1 進程中計算數據的準備 110
6.2.2 計算部分 116
6.3 並行程序的效率和可擴展性評估 121
6.4 本章並行程序實現的優缺點分析 123
第7章 求解三對角線性代數方程組的追趕法 124
7.1 追趕法的順序實現 124
7.2 追趕法的並行版本 126
7.2.1 並行算法的理論分析 131
7.3 追趕法的並行實現 132
7.3.1 進程中計算數據的準備 132
7.3.2 計算部分 135
第8章 求解偏微分方程的算法並行化方法：I 140
8.1 基於顯式格式的偏微分方程解的順序算法 140
8.2 順序算法的程序實現.142
8.3 基於顯式格式的並行算法 144
8.4 並行算法的代碼實現 146
8.5 並行程序的效率和可擴展性評估 152
8.6 改進方案的實施 154
第9章 求解偏微分方程的算法並行化方法：II 155
9.1 基於隱式格式的偏微分方程問題的順序算法 155
9.2 順序算法的程序實現 158
9.3 基於隱式格式的並行算法 162
9.4 並行算法的程序實現 165
9.5 並行程序的效率和可擴展性評估 173
第10章 求解偏微分方程的算法並行化方法：III 175
10.1 基於二維空間顯式格式的偏微分方程問題的順序算法 175
10.2 順序算法的程序實現 178
10.3 基於顯式格式的並行算法 181
10.4 並行算法的程序實現 184
10.5 並行程序的效率與可擴展性評估 194
10.6 關於程序實現的改進方法的討論 195
第11章 異步操作 197
11.1 死鎖問題與順序消息交換替代同步交換 197
11.2 進程間非阻塞消息傳遞函數：Isend和Irecv 201
11.3 在計算過程中進行消息傳遞 204
第12章 延遲的交互請求 209
12.1 結構相同的數據的多次轉移 209
12.2 延遲請求函數：Send_init和Recv_init 211
12.3 求解偏微分方程問題的程序實現的改進 214
12.4 優化共軛梯度法的一個程序實現 217
12.5 標準MPI-4的功能：集體延遲的交互請求 219
第13章 混合並行編程技術 220
13.1 現代計算系統的典型配置 220
13.2 測試示例 223
13.3 使用OpenMP技術修改示例 224
13.4 使用CUDA技術修改示例 225
13.5 本章程序實現的效率和可擴展性評估 227
第14章 對並行程序可擴展性差的分析與建議 230
14.1 並行程序可擴展性差的主要原因 230
14.1.1 接收數據的確切順序 231
14.1.2 大量數據的同時傳輸 233
14.1.3 計數和消息傳遞階段的分離 234
14.1.4 計算拓撲和網絡拓撲之間的不匹配 235
14.1.5 PCI帶寬不足，無法與GPU配合使用 236
14.1.6 運行混合程序時的錯誤系統設置 237
14.2 綜合建議 237
參考文獻 238