高等計算機(jī)系統(tǒng)結(jié)構(gòu)-清華大學(xué)計算機(jī)系高性能所

1、高等計算機(jī)系統(tǒng)結(jié)構(gòu),清華大學(xué)計算機(jī)科學(xué)與技術(shù)系高性能計算研究所鄭緯民 教授2007年10月,計算機(jī)科學(xué)與技術(shù)系研究生課程,高等計算機(jī)系統(tǒng)結(jié)構(gòu),第一章 高等計算機(jī)的核心技術(shù)——并行處理第二章 加速比性能模型與可擴(kuò)展性分析第三章 互連與通信第四章 劃分與調(diào)度第五章 并行存儲器系統(tǒng)第六章 Cache Coherence第七章 Memory Consistency第八章 指令級并行處理,第五章 并行存儲器系統(tǒng)

2、,5.1 存儲器系統(tǒng)的層次結(jié)構(gòu)5.2 包含性、一致性和局部性5.3 存儲器容量的規(guī)劃5.4 虛擬存儲器技術(shù)5.5 交叉訪問的存儲器,5.1 存儲器系統(tǒng)的層次結(jié)構(gòu),存儲器系統(tǒng)的層次結(jié)構(gòu)如下圖所示：,CPU內(nèi)的寄存器,,,,高速緩存,主存儲器,磁盤存儲器,磁帶機(jī),,,,,層0：M0,層1：M1,層2：M2,層3：M3,層4：M4,,,,容量和存取時間增加,,,,每位成本增加,五個參數(shù)：存取時間ti：從CPU到第i

3、層存儲器的往返時間存儲器容量Si：第i層的字節(jié)或字的數(shù)量每字節(jié)成本Ci：第i層存儲器的成本為CiSi傳輸帶寬bi：相鄰層之間傳送信息的速率傳輸單位Xi：i和i+1層之間數(shù)據(jù)傳送的粒度 對存儲器系統(tǒng)中各層次存儲器的特性，1993年的統(tǒng)計數(shù)據(jù)如下表：,存儲器層次,特性,第0層,CPU寄存器,第1層,高速緩存,第2層,主存儲器,第3層,磁盤存儲器,第4層,磁帶存儲器,設(shè)備工藝,存取時間,容量(字節(jié)),成本(美分/KB

4、),帶寬(MB/S),傳送單位,分配管理,ECL,SRAM,DRAM,磁盤機(jī),磁帶機(jī),10ns,25-40ns,60-100ns,10-20ms,2-20min,512B,128KB,512MB,60-228GB,512G-2TB,18000,72,5.6,0.23,0.01,400-800,250-400,80-133,3-5,0.18-0.23,字:4-8B,塊:32B,頁:0.5-1KB,文件:5-512KB,后援存儲器,編譯器分

5、配,硬件控制,操作系統(tǒng),操作系統(tǒng)/用戶,操作系統(tǒng)/用戶,第五章 并行存儲器系統(tǒng),5.1 存儲器系統(tǒng)的層次結(jié)構(gòu)5.2 包含性、一致性和局部性5.2.1 包含性5.2.2 一致性5.2.3 局部性5.3 存儲器容量的規(guī)劃5.4 虛擬存儲器技術(shù)5.5 交叉訪問的存儲器,5.2 包含性、一致性和局部性,5.2.1 包含性（inclusion）1. 包含性的定義M0? M1? M2?

6、…… ? Mn 所有信息項最初存放在最外層Mn，在處理過程中，它的子集復(fù)制到Mn-1，同樣， Mn-1的子集復(fù)制到Mn-2，…… 如果在Mi中找到一個信息字，那么同一個字的復(fù)制品在所有的高層Mi+1，Mi+2，……，Mn中都一定可以找到。,2. 相鄰層之間的數(shù)據(jù)傳送單位CPU?高速緩存：字高速緩存?主存儲器：塊（每塊32個字節(jié)（8個字））主存?磁盤：頁面（比如每頁4K字節(jié)，包含128塊）磁盤?

7、磁帶：段包含性可以用下面的圖來說明：,CPU寄存器,,,,,……,b,,a,,……,,M1:高速緩存,a,b為高速緩存塊，32個字節(jié),,,,頁面A,a,M2:主存儲器,頁面B,b,,,,頁面A,a,M3:磁盤存儲器,頁面B,b,段F,段G,,頁面A,a,M4:磁帶機(jī)后援存儲器,頁面B,b,段F,段G,,,,,字單位,塊單位,頁單位,段單位,5.2.2 一致性（coherence）1.一致性定義同一個信息項與后繼存儲器

8、層次的副本是一致的。如果在高速緩存中的一個字被修改過，那么在所有更高層上該字的副本也必須立即或最后加以修改 。,2.維護(hù)一致性的兩種策略（1）寫直達(dá)（write-through,WT），即如果在Mi（i=1，2，…，n-1）中修改了一個字，則在Mi+1中需要立即修改。 （2）寫回（write-back,WB），即如果在Mi+1 中的修改延遲到Mi中正在修改的字被替換時才進(jìn)行。,5.2.3 局部性（locality）

9、Hennessy和Patterson（1990年）提出了一條90-10規(guī)則：典型程序在10%的代碼上可能要耗費(fèi)其執(zhí)行時間的90%（例如嵌套循環(huán)操作的最內(nèi)層循環(huán)）。時間局部性（temporal locality）：最近的訪問項（指令或數(shù)據(jù)）很可能在不久的將來再次被訪問。即對最近使用區(qū)域的集中訪問。,空間局部性（spatial locality）：一個進(jìn)程訪問的各項的地址彼此很近，例如，表操作或數(shù)組操作含對地址空間中某一區(qū)域的集中

10、訪問。順序局部性（sequential locality）：在典型程序中，除非轉(zhuǎn)移指令產(chǎn)生不按次序的轉(zhuǎn)移外，指令都是順序執(zhí)行的。局部性原理指導(dǎo)我們?nèi)ピO(shè)計高速緩存、主存儲器以及虛擬存儲器組織。,第五章 并行存儲器系統(tǒng),5.1 存儲器系統(tǒng)的層次結(jié)構(gòu)5.2 包含性、一致性和局部性5.3 存儲器容量的規(guī)劃5.3.1 命中率5.3.2 有效存取時間5.4 虛擬存儲器技術(shù)5.5 交叉訪問的存儲器,

11、5.3 存儲器容量的規(guī)劃,存儲器層次結(jié)構(gòu)的性能是由層次結(jié)構(gòu)的有效存取時間Teff決定的，它依賴于相繼層次的命中率和訪問頻率。,5.3.1 命中率在Mi中找到一個信息項時，稱之為命中，反之稱為缺失。假定在層次結(jié)構(gòu)中的存儲器層次為Mi和Mi-1，其中i=1，2，…，n。在Mi層的命中率hi則是信息項可在Mi中找到的概率。它是表示兩個相鄰層Mi-1和Mi特性的函數(shù)。在Mi中的缺失率定義為1-hi。,相繼層的命中率是存儲器容量、管理

12、策略和程序行為的函數(shù)，它是獨(dú)立的隨機(jī)變量，其值在0到1之間。我們假設(shè)h0=0和hn=1，這意味著CPU總是先訪問M1，并且訪問到最外層Mn時總是命中的。對Mi的訪問頻率為：,是指在較低層次有i-1次缺失而在Mi有一次命中時訪問Mi成功的概率。,通常情況下，有：,這說明，訪問內(nèi)存比訪問外存要多。,5.3.2 有效存取時間每當(dāng)發(fā)生缺失時，就要付出代價去訪問較高層次的存儲器。這種缺失在Cache中稱為塊缺失。在主存儲器中稱為缺頁錯

13、（page fault），因?yàn)閴K和頁面是這些層次之間傳送信息的單位。缺頁錯付出的時間代價要比塊缺失付出的更大：,5.3.3 層次結(jié)構(gòu)的優(yōu)化目標(biāo)：使Teff接近于M1的t1， 總成本接近于Mn的Cn。優(yōu)化過程可以表達(dá)為：對一個線性規(guī)劃求最小值問題:,例子：存儲器層次結(jié)構(gòu)設(shè)計,存儲器層次,存取時間,容量,價格/K字節(jié),高速緩存主存儲器磁盤陣列,t1 = 25nst2 = 未知t3 = 4m

14、s,s1=512K字節(jié)s2=32M字節(jié)s3 = 未知,c1=1.25美元c2=0.2美元c3=0.0002美元,要達(dá)到有效存取時間Teff=10.04?s,高速緩存命中率為h1=0.98，主存儲器命中率h2=0.9，總成本上限為15000美元。,解：,如果在同樣的預(yù)算限制條件下，要吧主存儲器容量提高64M字節(jié)，那么只好以減少磁盤容量為代價，但是這一變化并不影響高速緩存的命中率。如果使用合適的頁面替換算法，可能會增加主存儲

15、器的命中率，Teff有所降低。,層次化存儲器系統(tǒng)必須解決的問題：（1）數(shù)據(jù)塊在較高層存儲器中存放在哪個位置？即塊和頁的定位問題。如果一個塊存放在某一上層存儲器中，怎樣確定并找到該塊，即塊的尋址問題。（2）不命中的將從下層存儲器中訪問，并將該塊調(diào)入上層存儲器中，但是如果上層存儲器中已無空閑空間，則勢必將上層存儲器中的某一塊調(diào)出，但應(yīng)調(diào)出那一塊，即替換問題。（3）在寫訪問時，寫入上層存儲器中的數(shù)據(jù)必須在適當(dāng)?shù)臅r候?qū)懭胂聦?/p>

16、存儲器，何時寫？,第五章 并行存儲器系統(tǒng),5.1 存儲器系統(tǒng)的層次結(jié)構(gòu)5.2 包含性、一致性和局部性5.3 存儲器容量的規(guī)劃5.4 虛擬存儲器技術(shù)5.3.1 共享存儲和分布存儲5.3.2 DSM與SVM5.3.3 虛擬存儲器的主要技術(shù)5.5 交叉訪問的存儲器,5.4 虛擬存儲器技術(shù),提要：虛擬存儲器提供了幾乎沒有限制的存儲器工作空間。虛擬地址在編譯時產(chǎn)生。虛擬地址到物理

17、地址的轉(zhuǎn)換在運(yùn)行時進(jìn)行，需要使用轉(zhuǎn)換表和映象系統(tǒng)。替換策略。,5.4.1 共享存儲和分布存儲MIMD系統(tǒng)可以分為兩種：(1)tightly coupled shared-Memory multiprocessors(2)loosely coupled distributed-Memory multiprocessors它們可以用圖表示如下：,P1,P2,……,Pn,ICN,SM1,……,SMm,,,,,,s

18、hare-Memorymultiprocessors,P,……,ICN,,,,distribued-Memorymultiprocessors,LM,P,LM,P,LM,共享存儲和分布存儲的優(yōu)缺點(diǎn)：共享存儲器：易于編程，是單機(jī)的自然延伸；程序員無數(shù)據(jù)劃分的負(fù)擔(dān)；多進(jìn)程并發(fā)的開銷小，效率高，易于進(jìn)程遷移，任務(wù)動態(tài)分配簡單；由于每個處理器都通過總線訪問存儲器，因而限制了處理器的個數(shù)，可擴(kuò)展性差。,分

19、布存儲器：系統(tǒng)結(jié)構(gòu)靈活，可擴(kuò)展性好；處理機(jī)數(shù)目可達(dá)成百上千，處理速度有巨大的發(fā)展?jié)摿?；算法設(shè)計、編程以及任務(wù)動態(tài)分配比較困難；很難在處理機(jī)之間傳遞復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，難于進(jìn)程遷移；不能支持需要存儲空間的大規(guī)模數(shù)據(jù)處理要求。,分布存儲的兩種編程方法：（1）message-passing，用send，receive原語實(shí)現(xiàn)通信，要求程序員在進(jìn)程的整個運(yùn)行期間對數(shù)據(jù)的移動都很清楚；（2）romo

20、te procedure call，語言一級傳送控制與數(shù)據(jù)，可以看作是本地調(diào)用，但透明度有限。,缺點(diǎn)：這兩種方法都是用來解決不同地址空間的問題，在接點(diǎn)間傳遞復(fù)雜數(shù)據(jù)結(jié)構(gòu)時都比較困難，需要打包，傳遞指針也不可能實(shí)現(xiàn)。由于個處理機(jī)擁有不同的地址空間，使得進(jìn)程遷移時，該進(jìn)程所分配到的操作系統(tǒng)資源也得一起移動（打開得文件、文件存取控制塊等），這很費(fèi)時。,5.4.2 DSM與SVM1.DSM和SVM的提出 如何把共享和分布的優(yōu)

21、點(diǎn)結(jié)合起來，取長補(bǔ)短？共享分布存儲器（Distributed shared Memory，DSM）虛擬共享存儲器（Shared Virtual Memory，SVM）——基于分布存儲器的多處理機(jī)上，實(shí)現(xiàn)物理上分布但邏輯上共享的存儲器系統(tǒng)。,虛擬共享存儲器的邏輯結(jié)構(gòu)：,CPU1,……,虛擬共享存儲器,,,,LM1,CPU2,LM2,CPUn,LMn,地址映射部件,地址映射部件,……,地址映射部件,,,,,,,M

22、IMD機(jī)器存儲系統(tǒng)的發(fā)展方向：,共享存儲器,分布存儲器,共享分布存儲器,,,2.DSM系統(tǒng)的特點(diǎn) 在DSM系統(tǒng)中，每一臺處理機(jī)都可以訪問全局存儲器的任一位置，用戶可以把它當(dāng)成全局共享存儲器系統(tǒng)。 優(yōu)點(diǎn)：編程容易系統(tǒng)結(jié)構(gòu)靈活可擴(kuò)展性好系統(tǒng)價格低有較好的軟件移植性,DSM系統(tǒng)編制的程序比用消息傳遞方式編制的程序效率高：（1）在DSM系統(tǒng)中，數(shù)據(jù)都是以塊的方式進(jìn)行傳送，如果一個程序具有較

23、高的局部性，則當(dāng)把一個數(shù)據(jù)塊傳送到一個結(jié)點(diǎn)后，該結(jié)點(diǎn)對它的訪問就成為本地訪問，而消息傳遞方式的每次訪問都需要通訊。,（2）許多并行應(yīng)用程序都是分階段執(zhí)行的，每次執(zhí)行前，都有一個數(shù)據(jù)交換階段，其時間受通訊限制。在DSM系統(tǒng)中，數(shù)據(jù)只有用到的時候才傳送，取消了數(shù)據(jù)交換階段，把通訊時間加以分散，提高了并行性。（3）DSM提供的虛存空間比單個結(jié)點(diǎn)的存儲空間大得多，減少了換頁操作。,3.實(shí)現(xiàn)DSM的途徑 主要有三種：（1）硬件實(shí)現(xiàn)

24、：將傳統(tǒng)的cache技術(shù)擴(kuò)展應(yīng)用到松耦合分布式存儲多處理機(jī)。要增加專用部件以取得高效的實(shí)現(xiàn)。（2）操作系統(tǒng)和庫實(shí)現(xiàn)：利用虛擬存儲管理機(jī)制取得共享（sharing）和一致（coherence）。（3）編譯實(shí)現(xiàn)：自動將共享訪問轉(zhuǎn)換成同步和一致原語。用戶需要顯式控制全局?jǐn)?shù)據(jù)，當(dāng)傳遞大量數(shù)據(jù)時或試圖進(jìn)行進(jìn)程遷移時極其復(fù)雜。,4.主要技術(shù)結(jié)構(gòu)（structure）粒度（granularity）數(shù)據(jù)訪問與一致性（acc

25、ess and cosistency）一致性語義（coherence semantics）可擴(kuò)展性（scalability）異構(gòu)性（heterogeneity）結(jié)構(gòu)——指共享數(shù)據(jù)在存儲器中的框架（如對象和語言的類型）；粒度——指基本共享單位長度（如字節(jié)、字、頁或復(fù)雜數(shù)據(jù)結(jié)構(gòu)）。,第五章 并行存儲器系統(tǒng),5.1 存儲器系統(tǒng)的層次結(jié)構(gòu)5.2 包含性、一致性和局部性5.3 存儲器容量的規(guī)劃5.4

26、虛擬存儲器技術(shù)5.5 交叉訪問的存儲器5.5.1 兩種組織方式5.5.2 兩種方式的比較5.3.3 帶寬和容錯,5.5 交叉訪問的存儲器,主存儲器由多個模塊構(gòu)成。假設(shè)主存儲器包含m=2a個存儲器模塊，每個模塊包含w=2b個存儲單元（字），則總存儲容量為,5.5.1 兩種組織方式交叉訪問的存儲器可以分為兩種：(1)低位交叉方式(2)高位交叉方式,1.低位交叉方式存儲器地址的低a位

27、用來指明存儲器模塊，高b位是每個模塊內(nèi)的字地址。低位m路交叉存取如下圖：,地址譯碼器,MAB,,0,m,……,m(w-1),,MDB,,M0,MAB,,1,m+1,……,mw-m+1,,MDB,,M1,……,MAB,,m-1,2m-1,……,mw-1,,MDB,,Mm-1,,,,,,,,MDB,字,模塊,,,,,,,,……,,,,,,,地址,a,b,數(shù)據(jù)總線,存儲器數(shù)據(jù)緩沖器,,,模塊地址緩沖器,,,字地址緩沖器,,,2.高位

28、交叉方式存儲器地址的高a位作為存儲器模塊地址，鄰接的存儲器單元被分配在同一個存儲器模塊中，在每個存儲器周期內(nèi)，只能對各模塊存取一個字。所以不支持鄰接單元的成塊存取。高位m路交叉存取如下圖：,地址譯碼器,MAB,,0,1,……,w-1,,MDB,,M0,MAB,,w,w+1,……,2w-1,,MDB,,M1,……,MAB,,(m-1)w,mw-w-1,……,mw-1,,MDB,,Mm-1,,,,,,,,MDB,字,模塊,,

29、,,,,,……,,,,,,,地址,a,b,數(shù)據(jù)總線,存儲器數(shù)據(jù)緩沖器,,,模塊地址緩沖器,,,字地址緩沖器,,,,,5.5.2 兩種方式的比較 （1）低位交叉以流水線方式支持成塊存取 將存儲器周期稱為主周期，細(xì)分為m個小周期（m稱為交叉存取度），如8路交叉，m=8，w=8，a=b=3，設(shè)?為主周期，?為小周期，則,8路低位交叉存取如下圖：,,,,,,,0,8,…,56,存儲器地址寄存器(6位),M0,1,9,…,57,M1,

30、2,10,…,58,M2,3,11,…,59,M3,4,12,…,60,M4,5,13,…,61,M5,6,14,…,62,M6,7,15,…,63,M7,數(shù)據(jù),,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,低位交叉流水線方式示意圖：,,,W0,W7,W6,W5,W4,W3,W2,W1,,,,,,,,,,,?,,,,,?,,,,,時間,?為主周期，?= ?/m為小周期，m為交叉存取度,（2）如果應(yīng)用問題很少共享地址空

31、間，把一個進(jìn)程的幾頁集中在高位交叉存儲器的某個給定的存儲器模塊種，能有效的減少存儲器干擾，即每個存儲器模塊只和一臺處理機(jī)有關(guān)，可以減少存儲器沖突。,5.5.3 帶寬和容錯 1.帶寬討論低位交叉情況。帶寬B的上限為m，下限為1。Hellerman（1967年）推導(dǎo)出來的公式為：,如果使用16個存儲器模塊，則有效存儲器帶寬大約是單個存儲器的4倍。產(chǎn)生這一悲觀估算的原因是：不同長度的塊存取與單字存取在用戶程序中是隨機(jī)混合的。

32、,另外一種估算公式：Cragon（1992年）假設(shè)n個分量存放在m路交叉存取存儲器系統(tǒng)鄰接的存儲單元中，存取向量的一個分量所需的平均時間t1可估算為：,所以，交叉存取適合于長向量的流水線存取。,2.容錯將高位與低位交叉存取加以組合。高位交叉時，各存儲器模塊內(nèi)的地址是按順序編排的。對8個存儲模塊，將它們分為2個存儲器，體內(nèi)采用4路低位交叉存取。示意圖如下：,,,,,,,0,4,…,28,存儲器地址寄存器(6位),M

33、0,1,5,…,29,M1,2,6,…,30,M2,3,7,…,31,M3,32,36,…,60,M4,33,37,…,61,M5,34,38,…,62,M6,35,39,…,63,M7,,,,,,,,,,,,,,,,,,,,體0,,,,,,,體1,,,體地址,字地址,模塊地址,對8個存儲模塊，將它們分為4個存儲器，體內(nèi)采用2路低位交叉存取。示意圖如下：,,,,,,,0,2,…,14,存儲器地址寄存器(6位),M0,1,3,…,15,M

34、1,16,18,…,30,M2,17,19,…,31,M3,32,34,…,46,M4,33,35,…,47,M5,48,50,…,62,M6,49,51,…,63,M7,,,,,,,,,,,,,,,,,,,體0,,,,,,,體2,,,,體地址,字地址,模塊地址,體1,體3,,,,,在一個模塊發(fā)生故障的情況下：8路交叉存取存儲器的最大存儲器帶寬減少到零；4路2體交叉存儲器的最大帶寬減少到每周期4個字（只有一個體被廢棄）；

35、2路4體交叉存儲器中，仍有3個體工作，所以最大帶寬為6個字。,習(xí)題：假定一個由16個存儲器模塊構(gòu)成的主存儲器系統(tǒng)有下列三種交叉存儲器設(shè)計方案。每個模塊的容量為1M字節(jié)，機(jī)器按字節(jié)尋址。設(shè)計1：用1個存儲體16路交叉。設(shè)計2：用2個存儲體8路交叉。設(shè)計3：用4個存儲體4路交叉。（a）確定上述存儲器組織的地址構(gòu)成。（b）在上述每種存儲器組織中，假定只有一個存儲器模塊失效，確定能獲得的最大存儲器帶寬。（c