并行程序設計

專家指導委員會
譯者序
譯者簡介
前言
作者簡介
第一部分   基本技術
第1章   并行計算機 2
1.1   對計算速度的需求 2
1.2   并行計算機的類型 4
1.2.1   共享存儲器多處理機系統(tǒng) 4
1.2.2   消息傳遞多計算機系統(tǒng) 5
1.2.3   分布式共享存儲器系統(tǒng) 6
1.2.4   MIMD和SIMD分類法 7
1.3   消息傳遞多計算機的體系結構特征 8
1.3.1   靜態(tài)網(wǎng)絡消息傳遞多計算機 8
1.3.2   嵌入 12
1.3.3   通信方法 15
1.3.4   輸入/輸出 17
1.4   用連網(wǎng)計算機作為多計算機平臺 18
1.5   提高計算速度的潛力 21
1.6   小結 26
推薦讀物 26
參考文獻 27
習題 29
第2章   消息傳遞計算 31
2.1   消息傳遞編程基礎 31
2.1.1   編程的選擇 31
2.1.2   進程的創(chuàng)建 31
2.1.3   消息傳遞例程 33
2.2   使用工作站集群 38
2.2.1   軟件工具 38
2.2.2   PVM 38
2.2.3   MPI 43
2.2.4   偽代碼構造 49
2.3   并行程序的評估 50
2.3.1   并行執(zhí)行時間 50
2.3.2   時間復雜性 52
2.3.3   對漸近分析的評注 55
2.3.4   廣播/匯集的時間復雜性 55
2.4   并行程序的調(diào)試和評估 58
2.4.1   低層次調(diào)試 58
2.4.2   可視化工具 59
2.4.3   調(diào)試策略 60
2.4.4   用經(jīng)驗方法評估程序 60
2.4.5   對優(yōu)化并行代碼的評注 62
2.5   小結 63
推薦讀物 63
參考文獻 63
習題 65
第3章   易并行計算 67
3.1   理想的并行計算 67
3.2   易并行計算舉例 68
3.2.1   圖像的幾何變換 68
3.2.2   曼德勃羅特集 72
3.2.3   蒙特卡羅法 78
3.3   小結 82
推薦讀物 82
參考文獻 82
習題 83
第4章   劃分和分治策略 88
4.1   劃分 88
4.1.1   劃分策略 88
4.1.2   分治 91
4.1.3   M路分治 95
4.2   分治技術舉例 97
4.2.1   使用桶排序法排序 97
4.2.2   數(shù)值積分 100
4.2.3   N體問題 103
4.3   小結 107
推薦讀物 107
參考文獻 108
習題 109
第5章   流水線計算 114
5.1   流水線技術 114
5.2   流水線應用的計算平臺 117
5.3   流水線程序舉例 118
5.3.1   數(shù)字相加 118
5.3.2   數(shù)的排序 120
5.3.3   生成質(zhì)數(shù) 123
5.3.4   線性方程組求解—特殊案例 125
5.4   小結 127
推薦讀物 128
參考文獻 128
習題 128
第6章   同步計算 132
6.1   同步 132
6.1.1   路障 132
6.1.2   計數(shù)器實現(xiàn) 133
6.1.3   樹實現(xiàn) 135
6.1.4   蝶形路障 136
6.1.5   局部同步 136
6.1.6   死鎖 137
6.2   同步計算 137
6.2.1   數(shù)據(jù)并行計算 137
6.2.2   同步迭代 140
6.3   同步迭代程序舉例 140
6.3.1   用迭代法解線性方程組 140
6.3.2   熱分布問題 145
6.3.3   細胞自動機 152
6.4   小結 153
推薦讀物 153
參考文獻 154
習題 154
第7章   負載平衡與終止檢測 160
7.1   負載平衡 160
7.2   動態(tài)負載平衡 161
7.2.1   集中式動態(tài)負載平衡 162
7.2.2   分散式動態(tài)負載平衡 163
7.2.3   使用線形結構的負載平衡 165
7.3   分布式終止檢測算法 167
7.3.1   終止條件 167
7.3.2   使用應答消息實現(xiàn)終止 167
7.3.3   環(huán)形終止算法 168
7.3.4   固定能量分布式終止算法 170
7.4   程序舉例 170
7.4.1   最短路徑問題 170
7.4.2   圖表示 171
7.4.3   圖的搜索 172
7.5   小結 177
推薦讀物 177
參考文獻 178
習題 179
第8章   共享存儲器編程 184
8.1   共享存儲器多處理機 184
8.2   說明并行性的結構 186
8.2.1   創(chuàng)建并發(fā)進程 186
8.2.2   線程 187
8.3   共享數(shù)據(jù) 191
8.3.1   創(chuàng)建共享數(shù)據(jù) 191
8.3.2   訪問共享數(shù)據(jù) 192
8.3.3   并行性的語言結構 198
8.3.4   相關性分析 199
8.3.5   具有高速緩存的系統(tǒng)中
的共享數(shù)據(jù) 201
8.4   程序舉例 203
8.4.1   UNIX進程 204
8.4.2   Pthreads的例子 206
8.4.3   Java的例子 208
8.5   小結 209
推薦讀物 210
參考文獻 210
習題 211
第二部分   算法和應用
第9章   排序算法 216
9.1   概述 216
9.1.1   排序 216
9.1.2   可能的加速 216
9.1.3   秩排序 217
9.2   比較和交換排序算法 219
9.2.1   比較和交換 219
9.2.2   冒泡排序與奇偶互換排序 221
9.2.3   二維排序 224
9.2.4   歸并排序 226
9.2.5   快速排序 228
9.2.6   超立方體上的快速排序 230
9.2.7   奇偶歸并排序 234
9.2.8   雙調(diào)諧歸并排序 235
9.3   小結 238
推薦讀物 239
參考文獻 239
習題 240
第10章   數(shù)值算法 243
10.1   矩陣—回顧 243
10.1.1   矩陣相加 243
10.1.2   矩陣相乘 243
10.1.3   矩陣－向量相乘 244
10.1.4   矩陣與線性方程組的關系 244
10.2   矩陣乘法的實現(xiàn) 244
10.2.1   算法 244
10.2.2   直接實現(xiàn) 246
10.2.3   遞歸實現(xiàn) 248
10.2.4   網(wǎng)格實現(xiàn) 249
10.2.5   其他矩陣相乘方法 252
10.3   求解線性方程組 253
10.3.1   線性方程組 253
10.3.2   高斯消去法 253
10.3.3   并行實現(xiàn) 254
10.4   迭代方法 256
10.4.1   雅可比迭代 256
10.4.2   快速收斂方法 260
10.5   小結 263
推薦讀物 263
參考文獻 264
習題 265
第11章   圖像處理 268
11.1   低層圖像處理 268
11.2   點處理 269
11.3   直方圖 270
11.4   平滑. 銳化和噪聲消減 270
11.4.1   平均值 271
11.4.2   中值 272
11.4.3   加權掩碼 274
11.5   邊緣檢測 275
11.5.1   梯度和幅度 275
11.5.2   邊緣檢測掩碼 276
11.6   霍夫變換 279
11.7   向頻域的變換 282
11.7.1   傅里葉級數(shù) 282
11.7.2   傅里葉變換 282
11.7.3   圖像處理中的傅里葉變換 283
11.7.4   離散傅里葉變換算法的并行化 285
11.7.5   快速傅里葉變換 287
11.8   小結 293
推薦讀物 293
參考文獻 293
習題 295
第12章   搜索和優(yōu)化 298
12.1   應用和技術 298
12.2   分枝限界搜索 299
12.2.1   順序分枝限界 299
12.2.2   并行分枝限界 300
12.3   遺傳算法 301
12.3.1   進化算法和遺傳算法 301
12.3.2   順序遺傳算法 303
12.3.3   初始種群 303
12.3.4   選擇過程 305
12.3.5   后代的生成 306
12.3.6   變異 307
12.3.7   終止條件 307
12.3.8   并行遺傳算法 308
12.4   連續(xù)求精 311
12.5   爬山法 311
12.5.1   銀行業(yè)務應用問題 312
12.5.2   爬山法在銀行業(yè)務中的應用 314
12.5.3   并行化 315
12.6   小結 315
推薦讀物 315
參考文獻 315
習題 317
附      錄
附錄A   基本的PVM例程 323
附錄B   基本的MPI例程 328
附錄C   基本的Pthread例程 333
附錄D   并行計算模型 337
索引 346