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

Contents　目　錄
譯者序
序
前言
術(shù)語表
第1章　緒論1
1.1　本書結(jié)構(gòu)1
1.2　探索設(shè)計空間2
1.2.1　作為庫的并行3
1.2.2　作為語言的并行5
1.3　代碼示例6
1.4　機器配置6
第2章　并行編程模型與概念9
2.1　多進(jìn)程與多線程9
2.1.1　線程基礎(chǔ)11
2.1.2　線程親和性14
2.1.3　基于線程編程的OpenMP API14
2.1.4　工作分享15
2.1.5　OpenMP線程親和性18
2.2　基于任務(wù)的并行編程19
2.3　同步構(gòu)造22
2.3.1　鎖與互斥22
2.3.2　同步障、歸約和閉鎖24
2.3.3　任務(wù)同步障26
2.3.4　任務(wù)依賴28
2.4　阿姆達(dá)爾定律31
2.4.1　呈現(xiàn)性能結(jié)果32
2.4.2　對性能的影響34
2.4.3　將開銷映射到阿姆達(dá)爾定律中35
2.4.4　阿姆達(dá)爾定律變體35
2.5　總結(jié)37
第3章　眾核與多核計算機架構(gòu)39
3.1　執(zhí)行機制39
3.1.1　馮·諾依曼架構(gòu)與按序執(zhí)行40
3.1.2　按序流水線執(zhí)行42
3.1.3　亂序執(zhí)行44
3.1.4　分支預(yù)測47
3.1.5　超標(biāo)量執(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)存層次結(jié)構(gòu)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)存架構(gòu)70
3.3　總結(jié)72
第4章　編譯器和運行時的交互73
4.1　編譯器基礎(chǔ)73
4.2　基于任務(wù)的并行模型的實現(xiàn)76
4.2.1　lambda函數(shù)和閉包77
4.2.2　TBB中的排隊任務(wù)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　串行構(gòu)造的代碼生成91
4.4.5　靜態(tài)任務(wù)的代碼生成93
4.4.6　動態(tài)任務(wù)的代碼生成94
4.5　OpenMP實現(xiàn)示例97
4.5.1　GNU編譯器套件97
4.5.2　Intel編譯器和LLVM編譯器99
4.6　總結(jié)102
第5章　并行運行時基本機制103
5.1　管理并行性103
5.1.1　生成并行性103
5.1.2　等待104
5.2　并行性管理與硬件結(jié)構(gòu)105
5.2.1　檢測硬件結(jié)構(gòu)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　總結(jié)117
第6章　互斥和原子性118
6.1　互斥問題118
6.1.1　鎖的硬件支持：原子指令120
6.1.2　ABA問題122
6.2　我們應(yīng)該寫鎖代碼嗎123
6.3　鎖的類別124
6.4　鎖算法的特性124
6.5　鎖算法127
6.5.1　測試并設(shè)置鎖128
6.5.2　測試及測試并設(shè)置鎖129
6.5.3　票鎖130
6.5.4　排隊鎖131
6.6　實際代碼性能133
6.6.1　無爭用鎖開銷133
6.6.2　爭用鎖的吞吐量134
6.6.3　性能總結(jié)136
6.7　如何等待138
6.8　事務(wù)同步143
6.8.1　事務(wù)語義144
6.8.2　MESI協(xié)議中的實現(xiàn)145
6.8.3　事務(wù)指令146
6.8.4　事務(wù)鎖146
6.8.5　互斥和預(yù)測的比較149
6.9　其他串行操作149
6.9.1　master和masked構(gòu)造149
6.9.2　single構(gòu)造150
6.10　原子操作151
6.10.1　原子指令映射151
6.10.2　最小值和最大值的原子實現(xiàn)153
6.11　總結(jié)155
6.11.1　鎖總結(jié)155
6.11.2　原子操作總結(jié)155
第7章　同步障和歸約156
7.1　同步障基本原理157
7.2　同步障性能測量158
7.2.1　同步障微基準(zhǔn)程序159
7.2.2　同步障性能模型161
7.3　同步障組件161
7.3.1　計數(shù)器和標(biāo)志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　總結(jié)183
第8章　調(diào)度并行循環(huán)185
8.1　調(diào)度目標(biā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)轉(zhuǎ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　指導(dǎo)式調(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　總結(jié)208
第9章　任務(wù)并行模型的運行時
　　　　支持210
9.1　任務(wù)描述符210
9.2　任務(wù)池實現(xiàn)211
9.2.1　單任務(wù)池212
9.2.2　多任務(wù)池217
9.3　任務(wù)同步223
9.3.1　等待任務(wù)子集完成224
9.3.2　等待直接子任務(wù)完成227
9.3.3　任務(wù)依賴231
9.4　任務(wù)調(diào)度234
9.4.1　任務(wù)調(diào)度點234
9.4.2　廣度優(yōu)先調(diào)度和深度優(yōu)先
　　　調(diào)度235
9.4.3　任務(wù)竊取236
9.5　任務(wù)調(diào)度約束239
9.5.1　棧調(diào)度239
9.5.2　循環(huán)調(diào)度240
9.6　其他任務(wù)主題241
9.6.1　任務(wù)優(yōu)先級241
9.6.2　任務(wù)親和性243
9.7　總結(jié)245
第10章　總結(jié)和感想246
附錄　技術(shù)縮略語248
參考文獻(xiàn)251