高效能並行運行時系統:設計與實現 High Performance Parallel Runtimes: Design and Implementation

Contents　目　錄
譯者序
序
前言
術語表
第1章　緒論1
1.1　本書結構1
1.2　探索設計空間2
1.2.1　作為庫的並行3
1.2.2　作為語言的並行5
1.3　程式碼範例6
1.4　機器配置6
第2章　平行程式設計模型與概念9
2.1　多進程與多執行緒9
2.1.1　線程基礎11
2.1.2　線程親和性14
2.1.3　基於執行緒程式設計的OpenMP?API14
2.1.4　工作分享15
2.1.5　OpenMP線程親和性18
2.2　基於任務的平行程式設計19
2.3　同步構造22
2.3.1　鎖與互斥22
2.3.2　同步障、歸約和閉鎖24
2.3.3　任務同步障26
2.3.4　任務依賴28
2.4　阿姆達爾定律31
2.4.1　呈現性能結果32
2.4.2　對性能的影響34
2.4.3　將開銷映射到阿姆達爾定律中35
2.4.4　阿姆達爾定律變體35
2.5　總結37
第3章　眾核與多核心電腦架構39
3.1　執行機制39
3.1.1　馮·諾依曼架構與依序執行40
3.1.2　依序流水線執行42
3.1.3　亂序執行44
3.1.4　分支預測47
3.1.5　超標量執行48
3.1.6　同步多執行緒49
3.1.7　單指令多資料52
3.2　現代內存子系統54
3.2.1　記憶體層次結構54
3.2.2　記憶體模型與記憶體一致性58
3.2.3　緩存62
3.2.4　快取一致性：概述62
3.2.5　快取一致性：MESI協定62
3.2.6　性能影響66
3.2.7　非統一記憶體架構70
3.3　總結72
第4章　編譯器和運行時的交互73
4.1　編譯器基礎73
4.2　基於任務的平行模型的實現76
4.2.1　lambda函數和閉包77
4.2.2　TBB中的排隊任務79
4.3　並行程式語言的編譯器80
4.4　並行程式碼產生模式83
4.4.1　並行域的程式碼產生83
4.4.2　線程並行循環的程式碼產生85
4.4.3　SIMD並行循環的程式碼產生88
4.4.4　串行構造的程式碼生成91
4.4.5　靜態任務的程式碼生成93
4.4.6　動態任務的程式碼生成94
4.5　OpenMP實作範例97
4.5.1　GNU編譯器套件97
4.5.2　Intel編譯器和LLVM編譯器99
4.6　總結102
第5章　並行運行時基本機制103
5.1　管理並行性103
5.1.1　生成並行性103
5.1.2　等待104
5.2　並行性管理與硬體結構105
5.2.1　檢測硬體結構105
5.2.2　線程固定107
5.3　並行運行時系統中的記憶體管理108
5.3.1　記憶體效率及快取使用109
5.3.2　單線程記憶體分配器109
5.3.3　多執行緒記憶體分配器112
5.3.4　並行運行時系統的專用記憶體分配器113
5.3.5　線程本地存儲114
5.3.6　線程物件的資料佈局116
5.4　總結117
第6章　互斥和原子性118
6.1　互斥問題118
6.1.1　鎖的硬體支援：原子指令120
6.1.2　ABA問題122
6.2　我們應該寫鎖碼嗎123
6.3　鎖的類別124
6.4　鎖演算法的特性124
6.5　鎖演算法127
6.5.1　測試並設定鎖定128
6.5.2　測試及測試並設定鎖定129
6.5.3　票鎖130
6.5.4　排隊鎖131
6.6　實際程式碼效能133
6.6.1　無爭用鎖開銷133
6.6.2　爭用鎖的吞吐量134
6.6.3　性能總結136
6.7　如何等待138
6.8　事務同步143
6.8.1　事務語意144
6.8.2　MESI協定中的實作145
6.8.3　事務指令146
6.8.4　事務鎖146
6.8.5　互斥與預測的比較149
6.9　其他串列操作149
6.9.1　master和masked構造149
6.9.2　single構造150
6.10　原子操作151
6.10.1　原子指令映射151
6.10.2　最小值和大值的原子實現153
6.11　總結155
6.11.1　鎖總結155
6.11.2　原子操作總結155
第7章　同步障和歸約156
7.1　同步障基本原理157
7.2　同步障障礙性能測量158
7.2.1　同步障微基準程式159
7.2.2　同步障性能模型161
7.3　同步障組件161
7.3.1　計數器和標誌161
7.3.2　廣播163
7.4　同步障演算法分類166
7.5　同步障演算法166
7.5.1　計數同步障166
7.5.2　多對多重同步障169
7.5.3　蝶形/超立方體同步障170
7.5.4　傳播型同步障172
7.5.5　樹形簽入同步障174
7.6　歸約178
7.7　其他最佳化182
7.8　總結183
第8章　調度並行循環185
8.1　調度目標185
8.2　調度效率的理論極限186
8.3　基本調度方法188
8.3.1　靜態循環調度188
8.3.2　動態循環調度189
8.4　映射為規範形式189
8.5　編譯器循環轉換191
8.6　循環調度單調性193
8.7　靜態循環調度實現194
8.7.1　分塊式循環調度195
8.7.2　塊循環式循環調度195
8.8　動態循環調度實現196
8.8.1　指導式調度197
8.8.2　monotonic:dynamic199
8.8.3　nonmonotonic:dynamic201
8.9　循環調度評估203
8.10　其他循環調度方案207
8.10.1　使用歷史資訊208
8.10.2　用戶控制調度208
8.11　總結208
第9章　任務並行模型的運行時支援210
9.1　任務描述詞210
9.2　任務池實現211
9.2.1　單任務池212
9.2.2　多任務池217
9.3　任務同步223
9.3.1　等待任務子集完成224
9.3.2　等待直接子任務完成227
9.3.3　任務依賴231
9.4　任務調度234
9.4.1　任務調度點234
9.4.2　廣度優先調度和深度優先調度235
9.4.3　任務竊取236
9.5　任務調度限制239
9.5.1　棧調度239
9.5.2　循環調度240
9.6　其他任務主題241
9.6.1　任務優先級241
9.6.2　任務親和性243
9.7　總結245
第10章　總結與感想246
附錄　技術縮寫248
參考文獻251