基于mpi的奇偶排序_并行程序设计(第2版)pdf
并行程序設(shè)計(jì)(第2版) 內(nèi)容簡介
本書系統(tǒng)介紹并行程序設(shè)計(jì)原理及應(yīng)用。除介紹常用的一些算法范例，包括分治、流水、同步計(jì)算、主從及工作池，還介紹了一些常用的經(jīng)典數(shù)值和非數(shù)值算法，如排序、矩陣相乘、線性方程組求解、圖像處理中的預(yù)處理和相應(yīng)的變換、搜索和優(yōu)化等。第2版新增了機(jī)群計(jì)算等使用機(jī)群的內(nèi)容，對(duì)如何打造專用和通用的機(jī)群以及設(shè)置相應(yīng)的程序設(shè)計(jì)環(huán)境做了較為詳盡的介紹。章后包含大量習(xí)題，其中現(xiàn)實(shí)生活習(xí)題非常實(shí)用，既可增強(qiáng)學(xué)習(xí)興趣，又可提高并行程序設(shè)計(jì)技巧。
本書可作為高等院校計(jì)算機(jī)專業(yè)高年級(jí)本科生或研究生的教材，對(duì)從事高性能計(jì)算的科技工作者也是一本很有價(jià)值的參考書。
并行程序設(shè)計(jì)(第2版) 目錄
前言
作者簡介
第一部分 基本技術(shù)
第1章 并行計(jì)算機(jī) 2
1.1 對(duì)計(jì)算速度的需求 2
1.2 提高計(jì)算速度的潛力 4
1.2.1 加速系數(shù) 4
1.2.2 什么是最大的加速比 5
1.2.3 消息傳遞計(jì)算 9
1.3 并行計(jì)算機(jī)的類型 9
1.3.1 共享存儲(chǔ)器多處理機(jī)系統(tǒng) 10
1.3.2 消息傳遞多計(jì)算機(jī) 11
1.3.3 分布式共享存儲(chǔ)器 17
1.3.4 MIMD和SIMD的分類 17
1.4 機(jī)群計(jì)算 18
1.4.1 以互聯(lián)計(jì)算機(jī)作為計(jì)算平臺(tái) 18
1.4.2 機(jī)群的配置 23
1.4.3 打造“Beowulf風(fēng)格”的專用機(jī)群 26
1.5 小結(jié) 27
推薦讀物 27
參考文獻(xiàn) 28
習(xí)題 30
第2章 消息傳遞計(jì)算 31
2.1 消息傳遞程序設(shè)計(jì)基礎(chǔ) 31
2.1.1 編程的選擇 31
2.1.2 進(jìn)程的創(chuàng)建 31
2.1.3 消息傳遞例程 33
2.2 使用計(jì)算機(jī)機(jī)群 37
2.2.1 軟件工具 37
2.2.2 MPI 37
2.2.3 偽代碼構(gòu)造 44
2.3 并行程序的評(píng)估 45
2.3.1 并行執(zhí)行時(shí)間方程式 45
2.3.2 時(shí)間復(fù)雜性 48
2.3.3 對(duì)漸近分析的評(píng)注 50
2.3.4 廣播/集中的通信時(shí)間 50
2.4 用經(jīng)驗(yàn)方法進(jìn)行并行程序的調(diào)試和評(píng)估 51
2.4.1 低層調(diào)試 52
2.4.2 可視化工具 52
2.4.3 調(diào)試策略 53
2.4.4 評(píng)估程序 53
2.4.5 對(duì)優(yōu)化并行代碼的評(píng)注 55
2.5 小結(jié) 55
推薦讀物 55
參考文獻(xiàn) 56
習(xí)題 57
第3章 易并行計(jì)算 59
3.1 理想的并行計(jì)算 59
3.2 易并行計(jì)算舉例 60
3.2.1 圖像的幾何轉(zhuǎn)換 60
3.2.2 曼德勃羅特集 64
3.2.3 蒙特卡羅法 69
3.3 小結(jié) 73
推薦讀物 73
參考文獻(xiàn) 73
習(xí)題 74
第4章 劃分和分治策略 79
4.1 劃分 79
4.1.1 劃分策略 79
4.1.2 分治 82
4.1.3 M路分治 86
4.2 分治技術(shù)舉例 87
4.2.1 使用桶排序法排序 87
4.2.2 數(shù)值積分 91
4.2.3 N體問題 93
4.3 小結(jié) 96
推薦讀物 97
參考文獻(xiàn) 97
習(xí)題 98
第5章 流水線計(jì)算 104
5.1 流水線技術(shù) 104
5.2 流水線應(yīng)用的計(jì)算平臺(tái) 107
5.3 流水線程序舉例 107
5.3.1 數(shù)字相加 108
5.3.2 數(shù)的排序 110
5.3.3 生成質(zhì)數(shù) 112
5.3.4 線性方程組求解—特殊個(gè)例 114
5.4 小結(jié) 117
推薦讀物 117
參考文獻(xiàn) 117
習(xí)題 117
第6章 同步計(jì)算 122
6.1 同步 122
6.1.1 障柵 122
6.1.2 計(jì)數(shù)器實(shí)現(xiàn) 123
6.1.3 樹實(shí)現(xiàn) 124
6.1.4 蝶形障柵 125
6.1.5 局部同步 126
6.1.6 死鎖 126
6.2 同步計(jì)算 127
6.2.1 數(shù)據(jù)并行計(jì)算 127
6.2.2 同步迭代 129
6.3 同步迭代程序舉例 130
6.3.1 用迭代法解線性方程組 130
6.3.2 熱分布問題 135
6.3.3 細(xì)胞自動(dòng)機(jī) 142
6.4 部分同步方法 143
6.5 小結(jié) 144
推薦讀物 144
參考文獻(xiàn) 144
習(xí)題 145
第7章 負(fù)載平衡與終止檢測 151
7.1 負(fù)載平衡 151
7.2 動(dòng)態(tài)負(fù)載平衡 152
7.2.1 集中式動(dòng)態(tài)負(fù)載平衡 152
7.2.2 分散式動(dòng)態(tài)負(fù)載平衡 153
7.2.3 使用線形結(jié)構(gòu)的負(fù)載平衡 155
7.3 分布式終止檢測算法 157
7.3.1 終止條件 157
7.3.2 使用確認(rèn)消息實(shí)現(xiàn)終止 158
7.3.3 環(huán)形終止算法 158
7.3.4 固定能量分布式終止算法 160
7.4 程序舉例 160
7.4.1 最短路徑問題 160
7.4.2 圖的表示 161
7.4.3 圖的搜索 162
7.5 小結(jié) 166
推薦讀物 166
參考文獻(xiàn) 167
習(xí)題 168
第8章 共享存儲(chǔ)器程序設(shè)計(jì) 172
8.1 共享存儲(chǔ)器多處理機(jī) 172
8.2 說明并行性的構(gòu)造 173
8.2.1 創(chuàng)建并發(fā)進(jìn)程 173
8.2.2 線程 175
8.3 共享數(shù)據(jù) 178
8.3.1 創(chuàng)建共享數(shù)據(jù) 179
8.3.2 訪問共享數(shù)據(jù) 179
8.4 并行程序設(shè)計(jì)語言和構(gòu)造 185
8.4.1 并行語言 185
8.4.2 并行語言構(gòu)造 186
8.4.3 相關(guān)性分析 187
8.5 OpenMP 189
8.6 性能問題 193
8.6.1 共享數(shù)據(jù)的訪問 193
8.6.2 共享存儲(chǔ)器的同步 195
8.6.3 順序一致性 196
8.7 程序舉例 199
8.7.1 使用UNIX進(jìn)程的舉例 199
8.7.2 使用Pthread的舉例 201
8.7.3 使用Java的舉例 203
8.8 小結(jié) 204
推薦讀物 205
參考文獻(xiàn) 205
習(xí)題 206
第9章 分布式共享存儲(chǔ)器系統(tǒng)及其程序設(shè)計(jì) 211
9.1 分布式共享存儲(chǔ)器 211
9.2 分布式共享存儲(chǔ)器的實(shí)現(xiàn) 212
9.2.1 軟件DSM系統(tǒng) 212
9.2.2 DSM系統(tǒng)的硬件實(shí)現(xiàn) 213
9.2.3 對(duì)共享數(shù)據(jù)的管理 214
9.2.4 基于頁面系統(tǒng)的多閱讀器/單寫入器策略 214
9.3 在DSM系統(tǒng)中實(shí)現(xiàn)一致性存儲(chǔ)器 214
9.4 分布式共享存儲(chǔ)器的程序設(shè)計(jì)原語 216
9.4.1 進(jìn)程的創(chuàng)建 216
9.4.2 共享數(shù)據(jù)的創(chuàng)建 216
9.4.3 共享數(shù)據(jù)的訪問 217
9.4.4 同步訪問 217
9.4.5 改進(jìn)性能的要點(diǎn) 217
9.5 分布式共享存儲(chǔ)器的程序設(shè)計(jì) 219
9.6 實(shí)現(xiàn)一個(gè)簡易的DSM系統(tǒng) 219
9.6.1 使用類和方法作為用戶接口 220
9.6.2 基本的共享變量實(shí)現(xiàn) 220
9.6.3 數(shù)據(jù)組的重疊 222
9.7 小結(jié) 224
推薦讀物 224
參考文獻(xiàn) 224
習(xí)題 225
第二部分 算法和應(yīng)用
第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 奇偶?xì)w并排序 239
10.2.6 雙調(diào)諧歸并排序 240
10.3 在專用網(wǎng)絡(luò)上排序 243
10.3.1 二維排序 243
10.3.2 在超立方體上進(jìn)行快速排序 244
10.4 其他排序算法 247
10.4.1 秩排序 248
10.4.2 計(jì)數(shù)排序 249
10.4.3 基數(shù)排序 250
10.4.4 采樣排序 252
10.4.5 在機(jī)群上實(shí)現(xiàn)排序算法 253
10.5 小結(jié) 253
推薦讀物 254
參考文獻(xiàn) 254
習(xí)題 255
第11章 數(shù)值算法 258
11.1 矩陣回顧 258
11.1.1 矩陣相加 258
11.1.2 矩陣相乘 258
11.1.3 矩陣-向量相乘 259
11.1.4 矩陣與線性方程組的關(guān)系 259
11.2 矩陣乘法的實(shí)現(xiàn) 259
11.2.1 算法 259
11.2.2 直接實(shí)現(xiàn) 260
11.2.3 遞歸實(shí)現(xiàn) 262
11.2.4 網(wǎng)格實(shí)現(xiàn) 263
11.2.5 其他矩陣相乘方法 266
11.3 求解線性方程組 266
11.3.1 線性方程組 266
11.3.2 高斯消去法 266
11.3.3 并行實(shí)現(xiàn) 267
11.4 迭代方法 269
11.4.1 雅可比迭代 269
11.4.2 快速收斂方法 272
11.5 小結(jié) 274
推薦讀物 275
參考文獻(xiàn) 275
習(xí)題 276
第12章 圖像處理 279
12.1 低層圖像處理 279
12.2 點(diǎn)處理 280
12.3 直方圖 281
12.4 平滑、銳化和噪聲消減 281
12.4.1 平均值 281
12.4.2 中值 283
12.4.3 加權(quán)掩碼 284
12.5 邊緣檢測 285
12.5.1 梯度和幅度 285
12.5.2 邊緣檢測掩碼 286
12.6 霍夫變換 288
12.7 向頻域的變換 290
12.7.1 傅里葉級(jí)數(shù) 291
12.7.2 傅里葉變換 291
12.7.3 圖像處理中的傅里葉變換 292
12.7.4 離散傅里葉變換算法的并行化 294
12.7.5 快速傅里葉變換 296
12.8 小結(jié) 300
推薦讀物 300
參考文獻(xiàn) 300
習(xí)題 302
第13章 搜索和優(yōu)化 305
13.1 應(yīng)用和技術(shù) 305
13.2 分支限界搜索 306
13.2.1 順序分支限界 306
13.2.2 并行分支限界 307
13.3 遺傳算法 308
13.3.1 進(jìn)化算法和遺傳算法 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 連續(xù)求精 317
13.5 爬山法(hill climbing) 318
13.5.1 銀行業(yè)務(wù)應(yīng)用問題 319
13.5.2 爬山法在金融業(yè)務(wù)中的應(yīng)用 320
13.5.3 并行化 321
13.6 小結(jié) 321
推薦讀物 321
參考文獻(xiàn) 322
習(xí)題 323
附錄A 基本的MPI例程 329
附錄B 基本的Pthread例程 335
附錄C OpenMP命令、庫函數(shù)以及
環(huán)境變量 339
索引 347
總結(jié)
以上是生活随笔為你收集整理的基于mpi的奇偶排序_并行程序设计(第2版)pdf的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： π是无理数证明定积分_证明圆周率是无理数
- 下一篇： 为什么那么多人黑baby.在节目里的表现