并行程序設計原理

出版者的話
推薦序
譯者序
前言
第一部分 基　礎
第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 小結(jié)19
歷史回顧19
習題19
第2章 認識并行計算機21
2.1 用可移植性衡量機器特征21
2.2 6種并行機介紹21
2.2.1 芯片多處理器21
2.2.2 對稱多處理器體系結(jié)構(gòu)23
2.2.3 異構(gòu)芯片設計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的性質(zhì)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 小結(jié)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 并行結(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 通信和計算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 小結(jié)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ù)程序?qū)嵗?8
4.4 并行性的表示68
4.4.1 固定并行性68
4.4.2 無限并行性69
4.4.3 可擴展并行性70
4.5 按字母順序排序?qū)嵗?1
4.5.1 無限并行性71
4.5.2 固定并行性72
4.5.3 可擴展并行性73
4.6 三種求解方法的比較77
4.7 小結(jié)78
歷史回顧78
習題78
第5章 可擴展算法技術(shù)80
5.1 獨立計算塊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 應用通用掃描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 小結(jié)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ù)程序?qū)嵗?36
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ù)程序?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
習題143
第7章 MPI和其他局部視圖語言145
7.1 MPI：消息傳遞接口145
7.1.1 統(tǒng)計3的個數(shù)程序?qū)嵗?45
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 小結(jié)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 生命游戲?qū)嵗?73
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 性能模型總結(jié)191
8.9 NESL并行語言191
8.9.1 語言概念191
8.9.2 用嵌套并行實現(xiàn)矩陣乘192
8.9.3 NESL復雜性模型192
8.10 小結(jié)192
歷史回顧193
習題193
第9章 對并行程序設計現(xiàn)狀的評價194
9.1 并行語言的四個重要性質(zhì)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 小結(jié)201
歷史回顧201
習題202
第四部分 展望
第10章 并行程序設計的未來方向204
10.1 附屬處理器204
10.1.1 圖形處理部件204
10.1.2 Cell處理器207
10.1.3 附屬處理器的總結(jié)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 小結(jié)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 側(cè)重并行結(jié)構(gòu)220
11.2.3 并行結(jié)構(gòu)的測試221
11.2.4 順序程序設計221
11.2.5 樂意寫附加代碼222
11.2.6 測試時對參數(shù)的控制222
11.2.7 功能性調(diào)試223
11.3 對結(jié)課課程設計的設想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 可移植性和微調(diào)229
11.9 小結(jié)229
歷史回顧229
習題229
術(shù)語表230
參考文獻234