并行程序設(shè)計

專家指導(dǎo)委員會
譯者序
譯者簡介
前言
作者簡介
第一部分   基本技術(shù)
第1章   并行計算機(jī) 2
1.1   對計算速度的需求 2
1.2   并行計算機(jī)的類型 4
1.2.1   共享存儲器多處理機(jī)系統(tǒng) 4
1.2.2   消息傳遞多計算機(jī)系統(tǒng) 5
1.2.3   分布式共享存儲器系統(tǒng) 6
1.2.4   MIMD和SIMD分類法 7
1.3   消息傳遞多計算機(jī)的體系結(jié)構(gòu)特征 8
1.3.1   靜態(tài)網(wǎng)絡(luò)消息傳遞多計算機(jī) 8
1.3.2   嵌入 12
1.3.3   通信方法 15
1.3.4   輸入/輸出 17
1.4   用連網(wǎng)計算機(jī)作為多計算機(jī)平臺 18
1.5   提高計算速度的潛力 21
1.6   小結(jié) 26
推薦讀物 26
參考文獻(xiàn) 27
習(xí)題 29
第2章   消息傳遞計算 31
2.1   消息傳遞編程基礎(chǔ) 31
2.1.1   編程的選擇 31
2.1.2   進(jìn)程的創(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   偽代碼構(gòu)造 49
2.3   并行程序的評估 50
2.3.1   并行執(zhí)行時間 50
2.3.2   時間復(fù)雜性 52
2.3.3   對漸近分析的評注 55
2.3.4   廣播/匯集的時間復(fù)雜性 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   小結(jié) 63
推薦讀物 63
參考文獻(xiàn) 63
習(xí)題 65
第3章   易并行計算 67
3.1   理想的并行計算 67
3.2   易并行計算舉例 68
3.2.1   圖像的幾何變換 68
3.2.2   曼德勃羅特集 72
3.2.3   蒙特卡羅法 78
3.3   小結(jié) 82
推薦讀物 82
參考文獻(xiàn) 82
習(xí)題 83
第4章   劃分和分治策略 88
4.1   劃分 88
4.1.1   劃分策略 88
4.1.2   分治 91
4.1.3   M路分治 95
4.2   分治技術(shù)舉例 97
4.2.1   使用桶排序法排序 97
4.2.2   數(shù)值積分 100
4.2.3   N體問題 103
4.3   小結(jié) 107
推薦讀物 107
參考文獻(xiàn) 108
習(xí)題 109
第5章   流水線計算 114
5.1   流水線技術(shù) 114
5.2   流水線應(yīng)用的計算平臺 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   小結(jié) 127
推薦讀物 128
參考文獻(xiàn) 128
習(xí)題 128
第6章   同步計算 132
6.1   同步 132
6.1.1   路障 132
6.1.2   計數(shù)器實(shí)現(xiàn) 133
6.1.3   樹實(shí)現(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   細(xì)胞自動機(jī) 152
6.4   小結(jié) 153
推薦讀物 153
參考文獻(xiàn) 154
習(xí)題 154
第7章   負(fù)載平衡與終止檢測 160
7.1   負(fù)載平衡 160
7.2   動態(tài)負(fù)載平衡 161
7.2.1   集中式動態(tài)負(fù)載平衡 162
7.2.2   分散式動態(tài)負(fù)載平衡 163
7.2.3   使用線形結(jié)構(gòu)的負(fù)載平衡 165
7.3   分布式終止檢測算法 167
7.3.1   終止條件 167
7.3.2   使用應(yīng)答消息實(shí)現(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   小結(jié) 177
推薦讀物 177
參考文獻(xiàn) 178
習(xí)題 179
第8章   共享存儲器編程 184
8.1   共享存儲器多處理機(jī) 184
8.2   說明并行性的結(jié)構(gòu) 186
8.2.1   創(chuàng)建并發(fā)進(jìn)程 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   并行性的語言結(jié)構(gòu) 198
8.3.4   相關(guān)性分析 199
8.3.5   具有高速緩存的系統(tǒng)中
的共享數(shù)據(jù) 201
8.4   程序舉例 203
8.4.1   UNIX進(jìn)程 204
8.4.2   Pthreads的例子 206
8.4.3   Java的例子 208
8.5   小結(jié) 209
推薦讀物 210
參考文獻(xiàn) 210
習(xí)題 211
第二部分   算法和應(yīng)用
第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   奇偶?xì)w并排序 234
9.2.8   雙調(diào)諧歸并排序 235
9.3   小結(jié) 238
推薦讀物 239
參考文獻(xiàn) 239
習(xí)題 240
第10章   數(shù)值算法 243
10.1   矩陣—回顧 243
10.1.1   矩陣相加 243
10.1.2   矩陣相乘 243
10.1.3   矩陣－向量相乘 244
10.1.4   矩陣與線性方程組的關(guān)系 244
10.2   矩陣乘法的實(shí)現(xiàn) 244
10.2.1   算法 244
10.2.2   直接實(shí)現(xiàn) 246
10.2.3   遞歸實(shí)現(xiàn) 248
10.2.4   網(wǎng)格實(shí)現(xiàn) 249
10.2.5   其他矩陣相乘方法 252
10.3   求解線性方程組 253
10.3.1   線性方程組 253
10.3.2   高斯消去法 253
10.3.3   并行實(shí)現(xiàn) 254
10.4   迭代方法 256
10.4.1   雅可比迭代 256
10.4.2   快速收斂方法 260
10.5   小結(jié) 263
推薦讀物 263
參考文獻(xiàn) 264
習(xí)題 265
第11章   圖像處理 268
11.1   低層圖像處理 268
11.2   點(diǎn)處理 269
11.3   直方圖 270
11.4   平滑. 銳化和噪聲消減 270
11.4.1   平均值 271
11.4.2   中值 272
11.4.3   加權(quán)掩碼 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   小結(jié) 293
推薦讀物 293
參考文獻(xiàn) 293
習(xí)題 295
第12章   搜索和優(yōu)化 298
12.1   應(yīng)用和技術(shù) 298
12.2   分枝限界搜索 299
12.2.1   順序分枝限界 299
12.2.2   并行分枝限界 300
12.3   遺傳算法 301
12.3.1   進(jìn)化算法和遺傳算法 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è)務(wù)應(yīng)用問題 312
12.5.2   爬山法在銀行業(yè)務(wù)中的應(yīng)用 314
12.5.3   并行化 315
12.6   小結(jié) 315
推薦讀物 315
參考文獻(xiàn) 315
習(xí)題 317
附      錄
附錄A   基本的PVM例程 323
附錄B   基本的MPI例程 328
附錄C   基本的Pthread例程 333
附錄D   并行計算模型 337
索引 346