並行多核體系結構基礎

湯孟岩（Yan Solihin） 北卡羅來納州立大學電子與計算機工程系教授，長期從事計算機體系結構方向的研究工作。研究興趣包括計算機體系結構、計算機系統建模方法和圖像處理，在計算機體系結構和性能建模領域發表過大量高水平論文，相關研究受到美國國家自然科學基金、Intel、IBM、Samsung、Tekelec、SunMicrosystems和HP的資助。他於2017年被選為IEEE會士，併入選了高性能計算機體系結構國際會議（HPCA）名人堂（2015年）。此外，他還長期從事計算機體系結構的教學工作，具有豐富的教學經驗。創立和領導了針對性能、可靠性和安全的體系結構研究小組，並且開源了大量針對多核體系結構性能建模和性能優化的軟件工具。

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