高性能并行運行時系統(tǒng)：設計與實現(xiàn)

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　呈現(xiàn)性能結果32
2.4.2　對性能的影響34
2.4.3　將開銷映射到阿姆達爾定律中35
2.4.4　阿姆達爾定律變體35
2.5　總結37
第3章　眾核與多核計算機架構39
3.1　執(zhí)行機制39
3.1.1　馮·諾依曼架構與按序執(zhí)行40
3.1.2　按序流水線執(zhí)行42
3.1.3　亂序執(zhí)行44
3.1.4　分支預測47
3.1.5　超標量執(zhí)行48
3.1.6　同步多線程49
3.1.7　單指令多數(shù)據(jù)52
3.2　現(xiàn)代內(nèi)存子系統(tǒng)54
3.2.1　內(nèi)存層次結構54
3.2.2　內(nèi)存模型與內(nèi)存一致性58
3.2.3　緩存62
3.2.4　緩存一致性：概述62
3.2.5　緩存一致性：MESI協(xié)議62
3.2.6　性能影響66
3.2.7　非統(tǒng)一內(nèi)存架構70
3.3　總結72
第4章　編譯器和運行時的交互73
4.1　編譯器基礎73
4.2　基于任務的并行模型的實現(xiàn)76
4.2.1　lambda函數(shù)和閉包77
4.2.2　TBB中的排隊任務79
4.3　并行編程語言的編譯器80
4.4　并行代碼生成模式83
4.4.1　并行域的代碼生成83
4.4.2　線程并行循環(huán)的代碼生成85
4.4.3　SIMD并行循環(huán)的代碼生成88
4.4.4　串行構造的代碼生成91
4.4.5　靜態(tài)任務的代碼生成93
4.4.6　動態(tài)任務的代碼生成94
4.5　OpenMP實現(xiàn)示例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　并行運行時系統(tǒng)中的內(nèi)存管理108
5.3.1　內(nèi)存效率及緩存使用109
5.3.2　單線程內(nèi)存分配器109
5.3.3　多線程內(nèi)存分配器112
5.3.4　并行運行時系統(tǒng)的專用內(nèi)存
　　　分配器113
5.3.5　線程本地存儲114
5.3.6　線程對象的數(shù)據(jù)布局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協(xié)議中的實現(xiàn)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　最小值和最大值的原子實現(xiàn)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　計數(shù)器和標志161
7.3.2　廣播163
7.4　同步障算法分類166
7.5　同步障算法166
7.5.1　計數(shù)同步障166
7.5.2　多對多同步障169
7.5.3　蝶形/超立方體同步障170
7.5.4　傳播型同步障172
7.5.5　樹形簽入同步障174
7.6　歸約178
7.7　其他優(yōu)化182
7.8　總結183
第8章　調(diào)度并行循環(huán)185
8.1　調(diào)度目標185
8.2　調(diào)度效率的理論極限186
8.3　基本調(diào)度方法188
8.3.1　靜態(tài)循環(huán)調(diào)度188
8.3.2　動態(tài)循環(huán)調(diào)度189
8.4　映射為規(guī)范形式189
8.5　編譯器循環(huán)轉換191
8.6　循環(huán)調(diào)度單調(diào)性193
8.7　靜態(tài)循環(huán)調(diào)度實現(xiàn)194
8.7.1　分塊式循環(huán)調(diào)度195
8.7.2　塊循環(huán)式循環(huán)調(diào)度195
8.8　動態(tài)循環(huán)調(diào)度實現(xiàn)196
8.8.1　指導式調(diào)度197
8.8.2　monotonic:dynamic199
8.8.3　nonmonotonic:dynamic201
8.9　循環(huán)調(diào)度評估203
8.10　其他循環(huán)調(diào)度方案207
8.10.1　使用歷史信息208
8.10.2　用戶控制調(diào)度208
8.11　總結208
第9章　任務并行模型的運行時
　　　　支持210
9.1　任務描述符210
9.2　任務池實現(xiàn)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　任務調(diào)度234
9.4.1　任務調(diào)度點234
9.4.2　廣度優(yōu)先調(diào)度和深度優(yōu)先
　　　調(diào)度235
9.4.3　任務竊取236
9.5　任務調(diào)度約束239
9.5.1　棧調(diào)度239
9.5.2　循環(huán)調(diào)度240
9.6　其他任務主題241
9.6.1　任務優(yōu)先級241
9.6.2　任務親和性243
9.7　總結245
第10章　總結和感想246
附錄　技術縮略語248
參考文獻251