并行程序設計原理

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