并行多核體系結(jié)構(gòu)基礎(chǔ)
定 價(jià):99 元
叢書名:華章教育
- 作者:[美]湯孟巖(Yan Solihin)
- 出版時(shí)間:2018/11/1
- ISBN:9787111610410
- 出 版 社:機(jī)械工業(yè)出版社
- 中圖法分類:TP311.11
- 頁碼:
- 紙張:膠版紙
- 版次:
- 開本:16開
雖然多核現(xiàn)在是主流架構(gòu),但很少有教科書涵蓋并行多核體系結(jié)構(gòu)。本書填補(bǔ)了這一空白,為研究生或高級(jí)本科體系結(jié)構(gòu)課程提供了所有材料,重點(diǎn)是多核處理器的體系結(jié)構(gòu)。這本書也適合作為從事多核編程或多核芯片設(shè)計(jì)的專業(yè)人員的參考書。
從大概10年前開始,處理器的設(shè)計(jì)方式發(fā)生了巨大的變化。從表面上看,似乎沒有什么明顯的變化:晶體管密度依然按照摩爾定律每18~24個(gè)月翻一番。但如果仔細(xì)分析,會(huì)發(fā)現(xiàn)很多地方都發(fā)生了顯著的變化。曾經(jīng)按照摩爾定律增長(zhǎng)的處理器時(shí)鐘頻率開始變得停滯不前。處理器生產(chǎn)商開始從在管芯上設(shè)計(jì)單核處理器轉(zhuǎn)向設(shè)計(jì)多核處理器,通常也被簡(jiǎn)稱為多核(multicore)。這些多核芯片的發(fā)展標(biāo)志了處理器行業(yè)的一個(gè)重要轉(zhuǎn)變。從物理的角度來看,轉(zhuǎn)向多核設(shè)計(jì)的原因在于設(shè)計(jì)更高性能(更深或更寬的流水線)的單核處理器所帶來的功耗密度增長(zhǎng)無法接受。這也是處理器設(shè)計(jì)第二次遭遇功耗的物理限制,第一次遭遇導(dǎo)致處理器設(shè)計(jì)由雙極型晶體管全面轉(zhuǎn)向采用更高功效的互補(bǔ)金屬氧化物半導(dǎo)體(CMOS)晶體管。而這次沒有可以替代CMOS晶體管的功效更高的技術(shù),因此功耗限制需要通過體系結(jié)構(gòu)的改變來解決,即從單核處理器轉(zhuǎn)變?yōu)槎嗪颂幚砥鳌km然并行體系結(jié)構(gòu)已經(jīng)出現(xiàn)了很長(zhǎng)一段時(shí)間,但隨著向多核處理器的轉(zhuǎn)變,并行體系結(jié)構(gòu)將會(huì)成為當(dāng)代處理器的主流設(shè)計(jì)。
從處理器設(shè)計(jì)者的角度來看,理論上性能可以通過首先轉(zhuǎn)向多核,之后增加管芯上的核心數(shù)來保持很長(zhǎng)一段時(shí)間的增長(zhǎng)。然而從編程人員的角度來看,轉(zhuǎn)向多核會(huì)導(dǎo)致一個(gè)很重要的結(jié)果:性能的增長(zhǎng)依賴于程序員編寫并行代碼的能力,以及如何調(diào)優(yōu)并行代碼使其具有較好的可擴(kuò)展性。在多核處理器之前,程序員只需要關(guān)注增加可編程性或者編程抽象的層次,即便這樣做會(huì)導(dǎo)致代碼復(fù)雜度的增加以及執(zhí)行效率的降低,因?yàn)樗麄冎捞幚砥骱藭?huì)變得越來越快從而抵消這些不利影響。然而,現(xiàn)在程序員如果希望克服可編程性和抽象層次增加對(duì)性能的不利影響,需要考慮如何利用多核處理器所提供的并行優(yōu)勢(shì)來編寫程序。換句話說,并行編程和性能調(diào)優(yōu)對(duì)許多程序員而言已經(jīng)成為不可或缺的能力。
盡管多核已經(jīng)成為主流體系結(jié)構(gòu),但在寫作本書時(shí),市場(chǎng)上幾乎沒有任何教科書涵蓋了并行多核體系結(jié)構(gòu)。雖然有很多關(guān)于并行編程以及傳統(tǒng)并行體系結(jié)構(gòu)的教科書,也有一些與多核體系結(jié)構(gòu)相關(guān)的特定主題的短篇講義,但是筆者未找到完整的講解多核體系結(jié)構(gòu)的教科書。這方面的缺失促成了筆者完成本書。筆者希望本書關(guān)于多核體系結(jié)構(gòu)的內(nèi)容有助于當(dāng)前教授計(jì)算機(jī)體系結(jié)構(gòu)的教師講授相關(guān)內(nèi)容。筆者同時(shí)也希望本書能夠幫助還沒有教授多核體系結(jié)構(gòu)的教師開設(shè)該課程。最后,筆者希望本書能夠成為多核編程或者設(shè)計(jì)多核芯片的專家的工具書。
筆者在寫作本書時(shí)面臨一些重大的挑戰(zhàn)。首先,微處理器技術(shù)的變化節(jié)奏非?。本書涵蓋的一些主題仍然處于不斷變化中,導(dǎo)致筆者對(duì)相關(guān)內(nèi)容進(jìn)行了多次迭代。例如,在寫作之初,一個(gè)典型的多核處理器包含兩個(gè)處理器核并共享L2高速緩存,然而在完成本書寫作時(shí),管芯上的處理器核數(shù)量增加到了16個(gè),并且具有更深、更復(fù)雜的存儲(chǔ)層次。撰寫變化如此之快的相關(guān)技術(shù)非常具有挑戰(zhàn)性。此外,另一個(gè)重大的挑戰(zhàn)是關(guān)于多核體系結(jié)構(gòu)有太多的主題,單就一本教科書的厚度無法全部涵蓋。因此,筆者在寫作本書時(shí)需要做出決定:包含哪些主題和不包含哪些主題。因此非常遺憾,本書無法滿足所有讀者的需求,一些讀者可能會(huì)發(fā)現(xiàn)他們感興趣的主題并沒有包含在內(nèi)或者不夠深入。然而,筆者嘗試著涵蓋多核體系結(jié)構(gòu)中最基礎(chǔ)的內(nèi)容,并希望以此為跳板供讀者繼續(xù)閱讀其他資料。筆者相信本書可以為讀者提供預(yù)備知識(shí),進(jìn)而繼續(xù)閱讀多核體系結(jié)構(gòu)領(lǐng)域的研究論文。
本書基于筆者在2009年寫作并出版的《并行計(jì)算機(jī)體系結(jié)構(gòu)基礎(chǔ):多芯片和多核系統(tǒng)》(Fundamentals of Parallel Computer Architecture: Multichip and Multicore Systems)。與該書相比,本書不僅擴(kuò)展了所涵蓋的有關(guān)多核體系結(jié)構(gòu)的內(nèi)容,而且將多核體系結(jié)構(gòu)作為討論的中心。
本書在寫作過程中始終遵循以下理念。第一,本書的內(nèi)容適用于研究生、高年級(jí)本科生,以及受過計(jì)算機(jī)科學(xué)或工程訓(xùn)練的專業(yè)人士。一些涉及操作系統(tǒng)(進(jìn)程、線程、虛擬內(nèi)存)和計(jì)算機(jī)組成(指令集、寄存器)的基本概念在書中只是簡(jiǎn)單提及,筆者假設(shè)讀者已經(jīng)了解相關(guān)基本概念。
第二,當(dāng)介紹一個(gè)概念時(shí),筆者首先構(gòu)建一個(gè)場(chǎng)景并引導(dǎo)讀者理解該問題,之后再引入相關(guān)概念。因此,對(duì)于有些讀者來說本書的敘述可能有些煩瑣,但對(duì)另一些讀者來說這將有助于他們更清晰地理解相關(guān)問題和概念。
第三,除了一些特例之外,本書各章都設(shè)計(jì)得相對(duì)較短,因此讀者利用一個(gè)周末完成一章的閱讀并沒有太大難度。筆者希望學(xué)生可以完整閱讀本書,即使需要跳過本書的一些內(nèi)容,也希望是跳過整章而不是一章的部分內(nèi)容。為了縮短各章的長(zhǎng)度,筆者將本書的內(nèi)容分解為更多的章節(jié)(相對(duì)于本領(lǐng)域的典型教科書而言)。例如,關(guān)于高速緩存一致性(后文簡(jiǎn)稱緩存一致性)的內(nèi)容被劃分為3章:第6章引出問題,第7章介紹了廣播緩存一致性協(xié)議,第10章介紹了目錄式緩存一致性協(xié)議和更多高級(jí)主題。
第四,筆者致力于讓本書更具吸引力。一個(gè)獨(dú)特的地方就是分散在本書不同地方的“你知道嗎?”文本框,用于展示小的案例分析、不同的觀點(diǎn)、例子,或者有趣的事實(shí)和討論內(nèi)容。另一個(gè)獨(dú)特的地方就是在本書的最后包含了對(duì)并行多核體
湯孟巖(Yan Solihin) 北卡羅來納州立大學(xué)電子與計(jì)算機(jī)工程系教授,長(zhǎng)期從事計(jì)算機(jī)體系結(jié)構(gòu)方向的研究工作。研究興趣包括計(jì)算機(jī)體系結(jié)構(gòu)、計(jì)算機(jī)系統(tǒng)建模方法和圖像處理,在計(jì)算機(jī)體系結(jié)構(gòu)和性能建模領(lǐng)域發(fā)表過大量高水平論文,相關(guān)研究受到美國國家自然科學(xué)基金、Intel、IBM、Samsung、Tekelec、SunMicrosystems和HP的資助。他于2017年被選為IEEE會(huì)士,并入選了高性能計(jì)算機(jī)體系結(jié)構(gòu)國際會(huì)議(HPCA)名人堂(2015年)。此外,他還長(zhǎng)期從事計(jì)算機(jī)體系結(jié)構(gòu)的教學(xué)工作,具有豐富的教學(xué)經(jīng)驗(yàn)。創(chuàng)立和領(lǐng)導(dǎo)了針對(duì)性能、可靠性和安全的體系結(jié)構(gòu)研究小組,并且開源了大量針對(duì)多核體系結(jié)構(gòu)性能建模和性能優(yōu)化的軟件工具。
譯者序
前言
縮寫詞表
第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ǔ)與消息傳遞模型的對(duì)比 25
2.2.2 一個(gè)簡(jiǎn)單的例子 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)級(jí)依賴分析 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章 針對(duì)鏈?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 針對(duì)數(shù)據(jù)結(jié)構(gòu)的操作并行化 82
4.3 針對(duì)鏈表的并行化技術(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 多級(jí)高速緩存中的包含策略 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 步長(zhǎng)預(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ǔ)多處理器簡(jiǎn)介 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ì)對(duì)緩存一致性性能的影響 186
7.4 性能及其他實(shí)際問題 187
7.4.1 預(yù)取和一致性缺失 187
7.4.2 多級(jí)緩存 187
7.4.3 偵聽過濾 189
7.5 點(diǎn)對(duì)點(diǎn)互連網(wǎng)絡(luò)上的廣播式協(xié)議 189
7.6 習(xí)題 203
課堂習(xí)題 203
課后習(xí)題 207
第8章 對(duì)同步的硬件支持 209
8.1 鎖的實(shí)現(xiàn) 209
8.1.1 對(duì)鎖實(shí)現(xiàn)性能的評(píng)估 209
8.1.2 對(duì)原子指令的需求 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章 高級(jí)緩存一致性設(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)不同步引起的競(jìng)爭(zhēng)處理 272
10.4.2 由對(duì)請(qǐng)求非實(shí)時(shí)處理引起的競(jìng)爭(zhēng)處