第一部分 基本技術
第1章 並行計算機 2
1.1 對計算速度的需求 2
1.2 提高計算速度的潛力 4
1.2.1 加速係數 4
1.2.2 什麼是最大的加速比 5
1.2.3 消息傳遞計算 9
1.3 並行計算機的類型 9
1.3.1 共享存儲器多處理機係統 10
1.3.2 消息傳遞多計算機 11
1.3.3 分布式共享存儲器 17
1.3.4 MIMD和SIMD的分類 17
1.4 機群計算 18
1.4.1 以互聯計算機作為計算平颱 18
1.4.2 機群的配置 23
1.4.3 打造“Beowulf風格”的專用機群 26
1.5 小結 27
推薦讀物 27
參考文獻 28
習題 30
第2章 消息傳遞計算 31
2.1 消息傳遞程序設計基礎 31
2.1.1 編程的選擇 31
2.1.2 進程的創建 31
2.1.3 消息傳遞例程 33
2.2 使用計算機機群 37
2.2.1 軟件工具 37
2.2.2 MPI 37
2.2.3 僞代碼構造 44
2.3 並行程序的評估 45
2.3.1 並行執行時間方程式 45
2.3.2 時間復雜性 48
2.3.3 對漸近分析的評注 50
2.3.4 廣播/集中的通信時間 50
2.4 用經驗方法進行並行程序的調試和評估 51
2.4.1 低層調試 52
2.4.2 可視化工具 52
2.4.3 調試策略 53
2.4.4 評估程序 53
2.4.5 對優化並行代碼的評注 55
2.5 小結 55
推薦讀物 55
參考文獻 56
習題 57
第3章 易並行計算 59
3.1 理想的並行計算 59
3.2 易並行計算舉例 60
3.2.1 圖像的幾何轉換 60
3.2.2 曼德勃羅特集 64
3.2.3 濛特卡羅法 69
3.3 小結 73
推薦讀物 73
參考文獻 73
習題 74
第4章 劃分和分治策略 79
4.1 劃分 79
4.1.1 劃分策略 79
4.1.2 分治 82
4.1.3 M路分治 86
4.2 分治技術舉例 87
4.2.1 使用桶排序法排序 87
4.2.2 數值積分 91
4.2.3 N體問題 93
4.3 小結 96
推薦讀物 97
參考文獻 97
習題 98
第5章 流水綫計算 104
5.1 流水綫技術 104
5.2 流水綫應用的計算平颱 107
5.3 流水綫程序舉例 107
5.3.1 數字相加 108
5.3.2 數的排序 110
5.3.3 生成質數 112
5.3.4 綫性方程組求解—特殊個例 114
5.4 小結 117
推薦讀物 117
參考文獻 117
習題 117
第6章 同步計算 122
6.1 同步 122
6.1.1 障柵 122
6.1.2 計數器實現 123
6.1.3 樹實現 124
6.1.4 蝶形障柵 125
6.1.5 局部同步 126
6.1.6 死鎖 126
6.2 同步計算 127
6.2.1 數據並行計算 127
6.2.2 同步迭代 129
6.3 同步迭代程序舉例 130
6.3.1 用迭代法解綫性方程組 130
6.3.2 熱分布問題 135
6.3.3 細胞自動機 142
6.4 部分同步方法 143
6.5 小結 144
推薦讀物 144
參考文獻 144
習題 145
第7章 負載平衡與終止檢測 151
7.1 負載平衡 151
7.2 動態負載平衡 152
7.2.1 集中式動態負載平衡 152
7.2.2 分散式動態負載平衡 153
7.2.3 使用綫形結構的負載平衡 155
7.3 分布式終止檢測算法 157
7.3.1 終止條件 157
7.3.2 使用確認消息實現終止 158
7.3.3 環形終止算法 158
7.3.4 固定能量分布式終止算法 160
7.4 程序舉例 160
7.4.1 最短路徑問題 160
7.4.2 圖的錶示 161
7.4.3 圖的搜索 162
7.5 小結 166
推薦讀物 166
參考文獻 167
習題 168
第8章 共享存儲器程序設計 172
8.1 共享存儲器多處理機 172
8.2 說明並行性的構造 173
8.2.1 創建並發進程 173
8.2.2 綫程 175
8.3 共享數據 178
8.3.1 創建共享數據 179
8.3.2 訪問共享數據 179
8.4 並行程序設計語言和構造 185
8.4.1 並行語言 185
8.4.2 並行語言構造 186
8.4.3 相關性分析 187
8.5 OpenMP 189
8.6 性能問題 193
8.6.1 共享數據的訪問 193
8.6.2 共享存儲器的同步 195
8.6.3 順序一緻性 196
8.7 程序舉例 199
8.7.1 使用UNIX進程的舉例 199
8.7.2 使用Pthread的舉例 201
8.7.3 使用Java的舉例 203
8.8 小結 204
推薦讀物 205
參考文獻 205
習題 206
第9章 分布式共享存儲器係統及其程序設計 211
9.1 分布式共享存儲器 211
9.2 分布式共享存儲器的實現 212
9.2.1 軟件DSM係統 212
9.2.2 DSM係統的硬件實現 213
9.2.3 對共享數據的管理 214
9.2.4 基於頁麵係統的多閱讀器/單寫入器策略 214
9.3 在DSM係統中實現一緻性存儲器 214
9.4 分布式共享存儲器的程序設計原語 216
9.4.1 進程的創建 216
9.4.2 共享數據的創建 216
9.4.3 共享數據的訪問 217
9.4.4 同步訪問 217
9.4.5 改進性能的要點 217
9.5 分布式共享存儲器的程序設計 219
9.6 實現一個簡易的DSM係統 219
9.6.1 使用類和方法作為用戶接口 220
9.6.2 基本的共享變量實現 220
9.6.3 數據組的重疊 222
9.7 小結 224
推薦讀物 224
參考文獻 224
習題 225
第二部分 算法和應用
第10章 排序算法 230
10.1 概述 230
10.1.1 排序 230
10.1.2 可能的加速比 230
10.2 比較和交換排序算法 231
10.2.1 比較和交換 231
10.2.2 冒泡排序與奇偶互換排序 233
10.2.3 歸並排序 236
10.2.4 快速排序 237
10.2.5 奇偶歸並排序 239
10.2.6 雙調諧歸並排序 240
10.3 在專用網絡上排序 243
10.3.1 二維排序 243
10.3.2 在超立方體上進行快速排序 244
10.4 其他排序算法 247
10.4.1 秩排序 248
10.4.2 計數排序 249
10.4.3 基數排序 250
10.4.4 采樣排序 252
10.4.5 在機群上實現排序算法 253
10.5 小結 253
推薦讀物 254
參考文獻 254
習題 255
第11章 數值算法 258
11.1 矩陣迴顧 258
11.1.1 矩陣相加 258
11.1.2 矩陣相乘 258
11.1.3 矩陣-嚮量相乘 259
11.1.4 矩陣與綫性方程組的關係 259
11.2 矩陣乘法的實現 259
11.2.1 算法 259
11.2.2 直接實現 260
11.2.3 遞歸實現 262
11.2.4 網格實現 263
11.2.5 其他矩陣相乘方法 266
11.3 求解綫性方程組 266
11.3.1 綫性方程組 266
11.3.2 高斯消去法 266
11.3.3 並行實現 267
11.4 迭代方法 269
11.4.1 雅可比迭代 269
11.4.2 快速收斂方法 272
11.5 小結 274
推薦讀物 275
參考文獻 275
習題 276
第12章 圖像處理 279
12.1 低層圖像處理 279
12.2 點處理 280
12.3 直方圖 281
12.4 平滑、銳化和噪聲消減 281
12.4.1 平均值 281
12.4.2 中值 283
12.4.3 加權掩碼 284
12.5 邊緣檢測 285
12.5.1 梯度和幅度 285
12.5.2 邊緣檢測掩碼 286
12.6 霍夫變換 288
12.7 嚮頻域的變換 290
12.7.1 傅裏葉級數 291
12.7.2 傅裏葉變換 291
12.7.3 圖像處理中的傅裏葉變換 292
12.7.4 離散傅裏葉變換算法的並行化 294
12.7.5 快速傅裏葉變換 296
12.8 小結 300
推薦讀物 300
參考文獻 300
習題 302
第13章 搜索和優化 305
13.1 應用和技術 305
13.2 分支限界搜索 306
13.2.1 順序分支限界 306
13.2.2 並行分支限界 307
13.3 遺傳算法 308
13.3.1 進化算法和遺傳算法 308
13.3.2 順序遺傳算法 310
13.3.3 初始種群 310
13.3.4 選擇過程 312
13.3.5 後代的生成 312
13.3.6 變異 314
13.3.7 終止條件 314
13.3.8 並行遺傳算法 314
13.4 連續求精 317
13.5 爬山法（hill climbing） 318
13.5.1 銀行業務應用問題 319
13.5.2 爬山法在金融業務中的應用 320
13.5.3 並行化 321
13.6 小結 321
推薦讀物 321
參考文獻 322
習題 323
附錄A 基本的MPI例程 329
附錄B 基本的Pthread例程 335
附錄C OpenMP命令、庫函數以及
環境變量 339
索引 347
· · · · · · (
收起)
