并行多核體系結(jié)構(gòu)基礎(chǔ)

譯者序
前言
縮寫詞表
第1章　多核體系結(jié)構(gòu)概述 1
1.1　多核體系結(jié)構(gòu)的由來 2
1.2　并行計(jì)算機(jī)概述 9
1.2.1　并行計(jì)算機(jī)的Flynn分類法 12
1.2.2　MIMD并行計(jì)算機(jī)分類 13
1.3　未來的多核體系結(jié)構(gòu) 14
1.4　習(xí)題 18
課堂習(xí)題 18
課后習(xí)題 18
第2章　并行編程概述 20
2.1　并行程序性能的限制因素 20
2.2　并行編程模型 23
2.2.1　共享存儲(chǔ)與消息傳遞模型的對比 25
2.2.2　一個(gè)簡單的例子 26
2.2.3　其他編程模型 29
2.3　習(xí)題 37
課后習(xí)題 37
第3章　共享存儲(chǔ)并行編程 39
3.1　并行編程的步驟 39
3.2　依賴分析 40
3.2.1　循環(huán)級依賴分析 42
3.2.2　迭代空間遍歷圖和循環(huán)傳遞依賴圖 42
3.3　識(shí)別循環(huán)結(jié)構(gòu)中的并行任務(wù) 45
3.3.1　循環(huán)迭代間的并行和DOALL并行 45
3.3.2　DOACROSS：循環(huán)迭代間的同步并行 46
3.3.3　循環(huán)中語句間的并行 48
3.3.4　DOPIPE：循環(huán)中語句間的流水線并行 50
3.4　識(shí)別其他層面的并行 51
3.5　通過算法知識(shí)識(shí)別并行 53
3.6　確定變量的范圍 55
3.6.1　私有化 56
3.6.2　歸約變量和操作 57
3.6.3　準(zhǔn)則 58
3.7　同步 59
3.8　任務(wù)到線程的映射 60
3.9　線程到處理器的映射 64
3.10　OpenMP概述 67
3.11　習(xí)題 72
課堂習(xí)題 72
課后習(xí)題 77
第4章　針對鏈?zhǔn)綌?shù)據(jù)結(jié)構(gòu)的并行編程 79
4.1　LDS并行化所面臨的挑戰(zhàn) 79
4.2　LDS并行化技術(shù) 80
4.2.1　計(jì)算并行化與遍歷 80
4.2.2　針對數(shù)據(jù)結(jié)構(gòu)的操作并行化 82
4.3　針對鏈表的并行化技術(shù) 89
4.3.1　讀操作之間的并行 89
4.3.2　LDS遍歷中的并行 91
4.3.3　細(xì)粒度鎖方法 94
4.4　事務(wù)內(nèi)存 98
4.5　習(xí)題 99
課堂習(xí)題 99
課后習(xí)題 101
第5章　存儲(chǔ)層次結(jié)構(gòu)概述 103
5.1　存儲(chǔ)層次的意義 103
5.2　高速緩存體系結(jié)構(gòu)基礎(chǔ) 104
5.2.1　數(shù)據(jù)放置策略 105
5.2.2　數(shù)據(jù)替換策略 109
5.2.3　數(shù)據(jù)寫策略 111
5.2.4　多級高速緩存中的包含策略 113
5.2.5　統(tǒng)一/分立/Banked高速緩存和高速緩存流水線 117
5.2.6　高速緩存尋址和旁路轉(zhuǎn)換緩沖 119
5.2.7　非阻塞式高速緩存 121
5.3　高速緩存性能 122
5.3.1　高速緩存缺失的冪次定律 124
5.3.2　棧距離特性 125
5.3.3　高速緩存性能指標(biāo) 126
5.4　預(yù)取 127
5.4.1　步長預(yù)取和順序預(yù)取 128
5.4.2　多處理器系統(tǒng)中的預(yù)取 130
5.5　多核體系結(jié)構(gòu)中的高速緩存設(shè)計(jì) 130
5.6　高速緩存的物理組成 131
5.6.1　集中式高速緩存 131
5.6.2　分布式高速緩存 133
5.6.3　混合式高速緩存 133
5.7　高速緩存的邏輯組成 135
5.7.1　散列函數(shù) 139
5.7.2　改善共享高速緩存的距離局部性 140
5.7.3　私有高速緩存結(jié)構(gòu)中的容量共享 141
5.8　案例分析 143
5.8.1　IBM Power7的存儲(chǔ)層次 143
5.8.2　AMD Shanghai和Intel Barcelona處理器存儲(chǔ)層次的比較 146
5.9　習(xí)題 148
課堂習(xí)題 148
課后習(xí)題 150
第6章　共享存儲(chǔ)多處理器簡介 152
6.1　緩存一致性問題 153
6.2　存儲(chǔ)一致性問題 155
6.3　同步問題 156
6.4　習(xí)題 160
課堂習(xí)題 160
課后習(xí)題 161
第7章　緩存一致性基礎(chǔ) 163
7.1　概述 164
7.2　基于總線的多處理器緩存一致性問題 168
7.2.1　“寫直達(dá)”緩存的一致性協(xié)議 168
7.2.2　“寫回”緩存的MSI協(xié)議 170
7.2.3　“寫回”緩存的MESI協(xié)議 175
7.2.4　“寫回”緩存的MOESI協(xié)議 178
7.2.5　“寫回”緩存基于更新的協(xié)議 183
7.3　緩存設(shè)計(jì)對緩存一致性性能的影響 186
7.4　性能及其他實(shí)際問題 187
7.4.1　預(yù)取和一致性缺失 187
7.4.2　多級緩存 187
7.4.3　偵聽過濾 189
7.5　點(diǎn)對點(diǎn)互連網(wǎng)絡(luò)上的廣播式協(xié)議 189
7.6　習(xí)題 203
課堂習(xí)題 203
課后習(xí)題 207
第8章　對同步的硬件支持 209
8.1　鎖的實(shí)現(xiàn) 209
8.1.1　對鎖實(shí)現(xiàn)性能的評估 209
8.1.2　對原子指令的需求 210
8.1.3　TS鎖 212
8.1.4　TTSL 214
8.1.5　LL/SC鎖 215
8.1.6　Ticket鎖 218
8.1.7　ABQL 219
8.1.8　各種鎖實(shí)現(xiàn)的量化比較 221
8.2　柵障的實(shí)現(xiàn) 222
8.2.1　翻轉(zhuǎn)感應(yīng)集中式柵障 223
8.2.2　組合樹柵障 225
8.2.3　硬件柵障實(shí)現(xiàn) 225
8.3　事務(wù)內(nèi)存 227
8.4　練習(xí) 232
課堂習(xí)題 232
課后習(xí)題 236
第9章　存儲(chǔ)一致性模型 238
9.1　程序員的直覺 238
9.2　保證順序一致性的體系結(jié)構(gòu)機(jī)制 242
9.2.1　在基于總線的多處理器中基本的SC實(shí)現(xiàn) 242
9.2.2　改善SC性能的技術(shù) 244
9.3　松弛的一致性模型 246
9.3.1　安全網(wǎng) 246
9.3.2　處理器一致性 246
9.3.3　弱序 248
9.3.4　釋放一致性 250
9.3.5　惰性釋放一致性 253
9.4　不同存儲(chǔ)一致性模型中的同步 254
9.5　習(xí)題 256
課堂習(xí)題 256
課后習(xí)題 260
第10章　高級緩存一致性設(shè)計(jì) 262
10.1　目錄式一致性協(xié)議 262
10.2　目錄式一致性協(xié)議概覽 262
10.3　目錄式緩存一致性協(xié)議基礎(chǔ) 268
10.4　實(shí)現(xiàn)正確性和性能 272
10.4.1　由目錄狀態(tài)不同步引起的競爭處理 272
10.4.2　由對請求非實(shí)時(shí)處理引起的競爭處