并行程序設(shè)計(jì)原理

出版者的話
推薦序
譯者序
前言
第一部分 基　礎(chǔ)
第1章 導(dǎo)論2
1.1 并行的威力和潛能2
1.1.1 并行，一個(gè)熟悉的概念2
1.1.2 計(jì)算機(jī)程序中的并行2
1.1.3 多核計(jì)算機(jī)，一個(gè)機(jī)遇3
1.1.4 使用并行硬件的更多機(jī)遇4
1.1.5 并行計(jì)算和分布式計(jì)算的比較4
1.1.6 系統(tǒng)級(jí)并行5
1.1.7 并行抽象的便利5
1.2 考察順序程序和并行程序6
1.2.1 并行化編譯器6
1.2.2 范例求解的變化7
1.2.3 并行前綴求和8
1.3 使用多指令流實(shí)現(xiàn)并行9
1.3.1 線程概念9
1.3.2 統(tǒng)計(jì)3的個(gè)數(shù)的多線程求解方法10
1.4 目標(biāo)：可擴(kuò)展性和性能可移植性17
1.4.1 可擴(kuò)展性17
1.4.2 性能可移植性18
1.4.3 原理第一18
1.5 小結(jié)19
歷史回顧19
習(xí)題19
第2章 認(rèn)識(shí)并行計(jì)算機(jī)21
2.1 用可移植性衡量機(jī)器特征21
2.2 6種并行機(jī)介紹21
2.2.1 芯片多處理器21
2.2.2 對(duì)稱多處理器體系結(jié)構(gòu)23
2.2.3 異構(gòu)芯片設(shè)計(jì)26
2.2.4 機(jī)群27
2.2.5 超級(jí)計(jì)算機(jī)27
2.2.6 對(duì)6種并行計(jì)算機(jī)的評(píng)論30
2.3 順序計(jì)算機(jī)的抽象30
2.3.1 應(yīng)用RAM模型31
2.3.2 評(píng)估RAM模型31
2.4 PRAM：一種并行計(jì)算機(jī)模型32
2.5 CTA：一種實(shí)際的并行計(jì)算機(jī)模型32
2.5.1 CTA模型33
2.5.2 通信時(shí)延36
2.5.3 CTA的性質(zhì)36
2.6 存儲(chǔ)器訪問機(jī)制37
2.6.1 共享存儲(chǔ)器37
2.6.2 單邊通信37
2.6.3 消息傳遞38
2.6.4 存儲(chǔ)器一致性模型38
2.6.5 程序設(shè)計(jì)模型39
2.7 進(jìn)一步研究通信40
2.8 CTA模型的應(yīng)用40
2.9 小結(jié)41
歷史回顧41
習(xí)題41
第3章 性能分析43
3.1 動(dòng)機(jī)和基本概念43
3.1.1 并行和性能43
3.1.2 線程和進(jìn)程43
3.1.3 時(shí)延和吞吐率44
3.2 性能損失的原因45
3.2.1 開銷45
3.2.2 不可并行代碼46
3.2.3 競爭47
3.2.4 空閑時(shí)間47
3.3 并行結(jié)構(gòu)48
3.3.1 相關(guān)性48
3.3.2 相關(guān)性限制并行性49
3.3.3 粒度50
3.3.4 局部性51
3.4 性能協(xié)調(diào)51
3.4.1 通信和計(jì)算52
3.4.2 存儲(chǔ)器和并行性52
3.4.3 開銷與并行52
3.5 性能度量53
3.5.1 執(zhí)行時(shí)間54
3.5.2 加速比54
3.5.3 超線性加速比55
3.5.4 效率55
3.5.5 加速比問題55
3.5.6 可擴(kuò)展加速比和固定加速比56
3.6 可擴(kuò)展性能56
3.6.1 難于達(dá)到的可擴(kuò)展性能57
3.6.2 硬件問題57
3.6.3 軟件問題58
3.6.4 問題規(guī)模的擴(kuò)展58
3.7 小結(jié)59
歷史回顧59
習(xí)題59
第二部分 并行抽象
第4章 并行程序設(shè)計(jì)起步62
4.1 數(shù)據(jù)和任務(wù)并行62
4.1.1 定義62
4.1.2 數(shù)據(jù)和任務(wù)并行的說明62
4.2 Peril-L記號(hào)63
4.2.1 擴(kuò)展C語言63
4.2.2 并行線程63
4.2.3 同步和協(xié)同64
4.2.4 存儲(chǔ)器模型64
4.2.5 同步存儲(chǔ)器66
4.2.6 歸約和掃描67
4.2.7 歸約的抽象68
4.3 統(tǒng)計(jì)3的個(gè)數(shù)程序?qū)嵗?8
4.4 并行性的表示68
4.4.1 固定并行性68
4.4.2 無限并行性69
4.4.3 可擴(kuò)展并行性70
4.5 按字母順序排序?qū)嵗?1
4.5.1 無限并行性71
4.5.2 固定并行性72
4.5.3 可擴(kuò)展并行性73
4.6 三種求解方法的比較77
4.7 小結(jié)78
歷史回顧78
習(xí)題78
第5章 可擴(kuò)展算法技術(shù)80
5.1 獨(dú)立計(jì)算塊80
5.2 Schwartz算法80
5.3 歸約和掃描抽象82
5.3.1 通用歸約和掃描舉例83
5.3.2 基本結(jié)構(gòu)84
5.3.3 通用歸約結(jié)構(gòu)86
5.3.4 通用掃描組件舉例87
5.3.5 應(yīng)用通用掃描88
5.3.6 通用向量操作89
5.4 靜態(tài)為進(jìn)程分配工作89
5.4.1 塊分配90
5.4.2 重疊區(qū)域91
5.4.3 循環(huán)分配和塊循環(huán)分配92
5.4.4 不規(guī)則分配94
5.5 動(dòng)態(tài)為進(jìn)程分配工作95
5.5.1 工作隊(duì)列95
5.5.2 工作隊(duì)列的變體97
5.5.3 案例研究：并發(fā)存儲(chǔ)器分配97
5.6 樹99
5.6.1 按子樹分配99
5.6.2 動(dòng)態(tài)分配100
5.7 小結(jié)100
歷史回顧100
習(xí)題101
第三部分 并行程序設(shè)計(jì)語言
第6章 線程程序設(shè)計(jì)104
6.1 POSIX Threads 104
6.1.1 線程的創(chuàng)建和銷毀104
6.1.2 互斥108
6.1.3 同步110
6.1.4 安全性問題117
6.1.5 性能問題120
6.1.6 案例研究1：連續(xù)過度松弛124
6.1.7 案例研究2：重疊同步與計(jì)算129
6.1.8 案例研究3：多核芯片上的流計(jì)算134
6.2 Java Threads 134
6.2.1 同步方法135
6.2.2 同步語句136
6.2.3 統(tǒng)計(jì)3的個(gè)數(shù)程序?qū)嵗?36
6.2.4 易變存儲(chǔ)器138
6.2.5 原子對(duì)象138
6.2.6 鎖對(duì)象138
6.2.7 執(zhí)行器138
6.2.8 并發(fā)集合138
6.3 OpenMP 138
6.3.1 統(tǒng)計(jì)3的個(gè)數(shù)程序?qū)嵗?39
6.3.2 parallel for的語義局限141
6.3.3 歸約141
6.3.4 線程的行為和交互142
6.3.5 段142
6.3.6 OpenMP總結(jié)143
6.4 小結(jié)143
歷史回顧143
習(xí)題143
第7章 MPI和其他局部視圖語言145
7.1 MPI：消息傳遞接口145
7.1.1 統(tǒng)計(jì)3的個(gè)數(shù)程序?qū)嵗?45
7.1.2 組和通信子152
7.1.3 點(diǎn)對(duì)點(diǎn)通信152
7.1.4 集合通信154
7.1.5 舉例：連續(xù)過度松弛157
7.1.6 性能問題159
7.1.7 安全性問題164
7.2 分區(qū)的全局地址空間語言164
7.2.1 Co-Array Fortran165
7.2.2 Unified Parallel C 166
7.2.3 Titanium 167
7.3 小結(jié)167
歷史回顧168
習(xí)題168
第8章 ZPL和其他全局視圖語言169
8.1 ZPL程序設(shè)計(jì)語言169
8.2 ZPL基本概念169
8.2.1 區(qū)域170
8.2.2 數(shù)組計(jì)算171
8.3 生命游戲?qū)嵗?73
8.3.1 問題173
8.3.2 解決方案173
8.3.3 如何實(shí)現(xiàn)174
8.3.4 生命游戲的哲學(xué)175
8.4 與眾不同的ZPL特征175
8.4.1 區(qū)域175
8.4.2 語句級(jí)索引175
8.4.3 區(qū)域的限制176
8.4.4 性能模型176
8.4.5 用減法實(shí)現(xiàn)加法177
8.5 操作不同秩的數(shù)組177
8.5.1 部分歸約177
8.5.2 擴(kuò)充178
8.5.3 擴(kuò)充的原理179
8.5.4 數(shù)據(jù)操作舉例179
8.5.5 擴(kuò)充區(qū)域180
8.5.6 矩陣乘181
8.6 用重映射操作重排數(shù)據(jù)182
8.6.1 索引數(shù)組183
8.6.2 重映射183
8.6.3 排序舉例185
8.7 ZPL程序的并行執(zhí)行186
8.7.1 編譯器的職責(zé)186
8.7.2 指定進(jìn)程數(shù)187
8.7.3 為進(jìn)程分配區(qū)域187
8.7.4 數(shù)組分配188
8.7.5 標(biāo)量分配188
8.7.6 工作分派188
8.8 性能模型189
8.8.1 應(yīng)用實(shí)例1：生命游戲190
8.8.2 應(yīng)用實(shí)例2：SUMMA算法190
8.8.3 性能模型總結(jié)191
8.9 NESL并行語言191
8.9.1 語言概念191
8.9.2 用嵌套并行實(shí)現(xiàn)矩陣乘192
8.9.3 NESL復(fù)雜性模型192
8.10 小結(jié)192
歷史回顧193
習(xí)題193
第9章 對(duì)并行程序設(shè)計(jì)現(xiàn)狀的評(píng)價(jià)194
9.1 并行語言的四個(gè)重要性質(zhì)194
9.1.1 正確性194
9.1.2 性能195
9.1.3 可擴(kuò)展性196
9.1.4 可移植性196
9.2 評(píng)估現(xiàn)有方法196
9.2.1 POSIX Threads 196
9.2.2 Java Threads 197
9.2.3 OpenMP 197
9.2.4 MPI 197
9.2.5 PGAS語言198
9.2.6 ZPL 198
9.2.7 NESL 199
9.3 可供將來借鑒的經(jīng)驗(yàn)199
9.3.1 隱藏并行199
9.3.2 透明化性能200
9.3.3 局部性200
9.3.4 約束并行200
9.3.5 隱式并行與顯式并行201
9.4 小結(jié)201
歷史回顧201
習(xí)題202
第四部分 展望
第10章 并行程序設(shè)計(jì)的未來方向204
10.1 附屬處理器204
10.1.1 圖形處理部件204
10.1.2 Cell處理器207
10.1.3 附屬處理器的總結(jié)207
10.2 網(wǎng)格計(jì)算208
10.3 事務(wù)存儲(chǔ)器209
10.3.1 與鎖的比較210
10.3.2 實(shí)現(xiàn)方法210
10.3.3 未解決的問題211
10.4 MapReduce 212
10.5 問題空間的提升214
10.6 新出現(xiàn)的語言214
10.6.1 Chapel215
10.6.2 Fortress 215
10.6.3 X10216
10.7 小結(jié)218
歷史回顧218
習(xí)題218
第11章 編寫并行程序219
11.1 起步219
11.1.1 訪問和軟件219
11.1.2 Hello, World 219
11.2 并行程序設(shè)計(jì)的建議220
11.2.1 增量式開發(fā)220
11.2.2 側(cè)重并行結(jié)構(gòu)220
11.2.3 并行結(jié)構(gòu)的測試221
11.2.4 順序程序設(shè)計(jì)221
11.2.5 樂意寫附加代碼222
11.2.6 測試時(shí)對(duì)參數(shù)的控制222
11.2.7 功能性調(diào)試223
11.3 對(duì)結(jié)課課程設(shè)計(jì)的設(shè)想223
11.3.1 實(shí)現(xiàn)現(xiàn)有的并行算法223
11.3.2 與標(biāo)準(zhǔn)的基準(zhǔn)測試程序媲美224
11.3.3 開發(fā)新的并行計(jì)算224
11.4 性能度量225
11.4.1 與順序求解方法比較226
11.4.2 維護(hù)一個(gè)公正的實(shí)驗(yàn)設(shè)置226
11.5 了解并行性能227
11.6 性能分析227
11.7 實(shí)驗(yàn)方法學(xué)228
11.8 可移植性和微調(diào)229
11.9 小結(jié)229
歷史回顧229
習(xí)題229
術(shù)語表230
參考文獻(xiàn)234