Ch5 并行存儲器系統(tǒng)

1、高等計算機系統(tǒng)結構第一章 高等計算機的核心技術并行處理第二章 加速比性能模型與可擴展性分析第三章 互連與通信第四章 劃分與調度第五章 并行存儲器系統(tǒng)第六章 Cache Coherence第七章 Memory Consistency第八章 指令級并行處理第五章 并行存儲器系統(tǒng)5.1 存儲器系統(tǒng)的層次結構5.2 包含性、一致性和局部性5.3 存儲器容量的規(guī)劃5.4 虛擬存儲器技術5.5 交叉訪問的存儲器5.1 存儲器系統(tǒng)的層次結構存儲器系統(tǒng)的層次結構如下圖所示：CPU內的寄存器高速緩存主存儲器磁盤存儲器磁帶機層0：M0層1：M1層2：M2層3：M3層4：M4容量和存取時間增加每位成本增加五個參數：

2、存取時間ti：從CPU到第i層存儲器的往返時間存儲器容量Si：第i層的字節(jié)或字的數量每字節(jié)成本Ci：第i層存儲器的成本為CiSi傳輸帶寬bi：相鄰層之間傳送信息的速率傳輸單位Xi：i和i+1層之間數據傳送的粒度 對存儲器系統(tǒng)中各層次存儲器的特性，1993年的統(tǒng)計數據如下表：存儲器層次特性第0層CPU寄存器第1層高速緩存第2層主存儲器第3層磁盤存儲器第4層磁帶存儲器設備工藝存取時間容量(字節(jié))成本(美分/KB)帶寬(MB/S)傳送單位分配管理ECLSRAMDRAM磁盤機磁帶機10ns25-40ns60-100ns10-20ms2-20min512B128KB512MB60-228GB512G-2

3、TB18000725.60.230.01400-800250-40080-1333-50.18-0.23字:4-8B塊:32B頁:0.5-1KB文件:5-512KB后援存儲器編譯器分配 硬件控制 操作系統(tǒng)操作系統(tǒng)/用戶操作系統(tǒng)/用戶IntelAMDIBMSPARCMIPSP4P4 Xeon Itanium-2OpteronPower5Power6Ultra4T116000主頻3.83.41.62.42.34.71.21.20.8晶 體管數1.250.425.922.332.767.90.293.00-工藝90nm90180901306513090250字長3232128646464646464

4、核數221222281線 程數/核111122141一 級Cache96/64K96/1664/6464/6464/3216/832/6416/832/32二 級Cache10.25621.982*8316三 級Cache-9-3632-功 能部件7 個 整數 ， 1個浮點3/19/23/36/2簡單CPU3/31/18共享2/2主 要特征20級流水 ， 動態(tài)預測，SMT深流水靜態(tài)調度，動態(tài)預測動態(tài)預測動 態(tài) 預測，SMT雙 核 ，多線程單線程交叉多線程8 級 流水，動態(tài)預測功耗115W13513011080160707920第五章 并行存儲器系統(tǒng)5.1 存儲器系統(tǒng)的層次結構5.2 包含性、一

5、致性和局部性5.2.1 包含性5.2.2 一致性5.2.3 局部性5.3 存儲器容量的規(guī)劃5.4 虛擬存儲器技術5.5 交叉訪問的存儲器5.2 包含性、一致性和局部性5.2.1 包含性（inclusion）1. 包含性的定義M0 M1 M2 Mn 所有信息項最初存放在最外層Mn，在處理過程中，它的子集復制到Mn-1，同樣， Mn-1的子集復制到Mn-2， 如果在Mi中找到一個信息字，那么同一個字的復制品在所有的高層Mi+1，Mi+2，Mn中都一定可以找到。2. 相鄰層之間的數據傳送單位CPU高速緩存：字高速緩存主存儲器：塊（每塊32個字節(jié)（8個字）主存磁盤：頁面（比如每頁4K字節(jié)，包含128塊

6、）磁盤磁帶：段包含性可以用下面的圖來說明：CPU寄存器baM1:高速緩存a,b為高速緩存塊，32個字節(jié)頁面AaM2:主存儲器頁面Bb頁面AaM3:磁盤存儲器頁面Bb段F段G頁面AaM4:磁帶機后援存儲器頁面Bb段F段G字單位塊單位頁單位段單位5.2.2 一致性（coherence）1.一致性定義 同一個信息項與后繼存儲器層次的副本是一致的。如果在高速緩存中的一個字被修改過，那么在所有更高層上該字的副本也必須立即或最后加以修改 。2.維護一致性的兩種策略1）寫直達（write-through,WT），即如果在Mi（i=1，2，n-1）中修改了一個字，則在Mi+1中需要立即修改。2）寫回（writ

7、e-back,WB），即如果在Mi+1 中的修改延遲到Mi中正在修改的字被替換時才進行。5.2.3 局部性（locality）Hennessy和Patterson（1990年）提出了一條90-10規(guī)則：典型程序在10%的代碼上可能要耗費其執(zhí)行時間的90%（例如嵌套循環(huán)操作的最內層循環(huán)）。時間局部性（temporal locality）：最近的訪問項（指令或數據）很可能在不久的將來再次被訪問。即對最近使用區(qū)域的集中訪問?？臻g局部性（spatial locality）：一個進程訪問的各項的地址彼此很近，例如，表操作或數組操作含對地址空間中某一區(qū)域的集中訪問。順序局部性（sequential loc

8、ality）：在典型程序中，除非轉移指令產生不按次序的轉移外，指令都是順序執(zhí)行的。局部性原理指導我們去設計高速緩存、主存儲器以及虛擬存儲器組織。第五章 并行存儲器系統(tǒng)5.1 存儲器系統(tǒng)的層次結構5.2 包含性、一致性和局部性5.3 存儲器容量的規(guī)劃5.3.1 命中率5.3.2 有效存取時間5.4 虛擬存儲器技術5.5 交叉訪問的存儲器5.3 存儲器容量的規(guī)劃存儲器層次結構的性能是由層次結構的有效存取時間Teff決定的，它依賴于相繼層次的命中率和訪問頻率。5.3.1 命中率在Mi中找到一個信息項時，稱之為命中，反之稱為缺失。假定在層次結構中的存儲器層次為Mi和 Mi-1，其中i=1，2，n。在M

9、i層的命中率hi則是信息項可在Mi中找到的概率。它是表示兩個相鄰層Mi-1和Mi特性的函數。在Mi中的缺失率定義為1-hi。相繼層的命中率是存儲器容量、管理策略和程序行為的函數，它是獨立的隨機變量，其值在0到1之間。假設h0=0和hn=1，這意味著CPU總是先訪問M1，并且訪問到最外層Mn時總是命中的。對Mi的訪問頻率為：iiihhhhf)1()1)(1(121是指在較低層次有i-1次缺失而在Mi有一次命中時訪問Mi成功的概率。111,1hffniinfff21通常情況下，有：訪問內存比訪問外存要多。5.3.2 有效存取時間每當發(fā)生缺失時，就要付出代價去訪問較高層次的存儲器。這種缺失在Cach

10、e中稱為塊缺失。在主存儲器中稱為缺頁錯（page fault），因為塊和頁面是這些層次之間傳送信息的單位。缺頁錯付出的時間代價要比塊缺失付出的更大：nnnniiieffthhhhthhthtfT)1()1)(1()1(1211221115.3.3 層次結構的優(yōu)化目標：使Teff接近于M1的t1， 總成本接近于Mn的Cn。優(yōu)化過程可以表達為：對一個線性規(guī)劃求最小值問題:減到最小值。要將有效存取時間總價格的上限）時，對于niiieffniiitotaliitfTCSCCnitS101(, 2 , 1, 0, 0例子：存儲器層次結構設計存儲器層次存取時間容量價格/K字節(jié)高速緩存主存儲器磁盤陣列t1

11、= 25nst2 = 未知t3 = 4mss1=512K字節(jié)s2=32M字節(jié)s3 = 未知c1=1.25美元c2=0.2美元c3=0.0002美元要達到有效存取時間Teff=10.04s,高速緩存命中率為h1=0.98，主存儲器命中率h2=0.9，總成本上限為15000美元。解：nstthhhthhthTGByteSSCSCSCCeff90304.10)1)(1 ()1 (8 .391500023321221113332211代入可得代入有： 如果在同樣的預算限制條件下，要把主存儲器容量提高64M字節(jié)，那么只好以減少磁盤容量為代價，但是這一變化并不影響高速緩存的命中率。如果使用合適的頁面替換算

12、法，可能會增加主存儲器的命中率，Teff有所降低。層次化存儲器系統(tǒng)必須解決的問題：（1）數據塊在較高層存儲器中存放在哪個位置？即塊和頁的定位問題。（2）如果一個塊存放在某一上層存儲器中，怎樣確定并找到該塊，即塊的尋址問題。（3）不命中的將從下層存儲器中訪問，并將該塊調入上層存儲器中，但是如果上層存儲器中已無空閑空間，則勢必將上層存儲器中的某一塊調出，但應調出那一塊，即替換問題。（4）在寫訪問時，寫入上層存儲器中的數據必須在適當的時候寫入下層存儲器，寫一致性。第五章 并行存儲器系統(tǒng)5.1 存儲器系統(tǒng)的層次結構5.2 包含性、一致性和局部性5.3 存儲器容量的規(guī)劃5.4 虛擬存儲器技術5.3.1

13、共享存儲和分布存儲5.3.2 DSM與SVM5.3.3 虛擬存儲器的主要技術5.5 交叉訪問的存儲器5.4 虛擬存儲器技術提要：虛擬存儲器提供了幾乎沒有限制的存儲器工作空間。虛擬地址在編譯時產生。虛擬地址到物理地址的轉換在運行時進行，需要使用轉換表和映象系統(tǒng)。替換策略。5.4.1 共享存儲和分布存儲MIMD系統(tǒng)可以分為兩種：(1)tightly coupled shared-Memory multiprocessors(2)loosely coupled distributed-Memory multiprocessors它們可以用圖表示如下：P1P2PnICNSM1SMmshare-Memo

14、rymultiprocessorsPICNdistribued-MemorymultiprocessorsLMPLMPLM共享存儲和分布存儲的優(yōu)缺點：共享存儲器：易于編程，是單機的自然延伸；程序員無數據劃分的負擔；多進程并發(fā)的開銷小，效率高，易于進程遷移，任務動態(tài)分配簡單；由于每個處理器都通過總線訪問存儲器，因而限制了處理器的個數，可擴展性差。分布存儲器：系統(tǒng)結構靈活，可擴展性好；處理機數目可達成百上千，處理速度有巨大的發(fā)展?jié)摿?；算法設計、編程以及任務動態(tài)分配比較困難； 很難在處理機之間傳遞復雜的數據結構，難于進程遷移；不能支持需要存儲空間的大規(guī)模數據處理要求。分布存儲的兩種編程方法：（1）m

15、essage-passing，用send，receive原語實現通信，要求程序員在進程的整個運行期間對數據的移動都很清楚；（2）romote procedure call，語言一級傳送控制與數據，可以看作是本地調用，但透明度有限。缺點：這兩種方法都是用來解決不同地址空間的問題，在接點間傳遞復雜數據結構時都比較困難，需要打包，傳遞指針也不可能實現。由于每個處理機擁有不同的地址空間，使得進程遷移時，該進程所分配到的操作系統(tǒng)資源也得一起移動（打開的文件、文件存取控制塊等），這很費時。5.4.2 DSM與SVM1.DSM和SVM的提出 如何把共享和分布的優(yōu)點結合起來，取長補短？ 共享分布存儲器（Dis

16、tributed shared Memory，DSM）虛擬共享存儲器（Shared Virtual Memory，SVM）基于分布存儲器的多處理機上，實現物理上分布但邏輯上共享的存儲器系統(tǒng)。虛擬共享存儲器的邏輯結構：CPU1虛擬共享存儲器LM1CPU2LM2CPUnLMn地址映射部件地址映射部件地址映射部件MIMD機器存儲系統(tǒng)的發(fā)展方向：共享存儲器分布存儲器共享分布存儲器2.DSM系統(tǒng)的特點 在DSM系統(tǒng)中，每一臺處理機都可以訪問全局存儲器的任一位置，用戶可以把它當成全局共享存儲器系統(tǒng)。優(yōu)點：編程容易系統(tǒng)結構靈活可擴展性好系統(tǒng)價格低有較好的軟件移植性DSM系統(tǒng)編制的程序比用消息傳遞方式編制的程

17、序效率高：（1）在DSM系統(tǒng)中，數據都是以塊的方式進行傳送，如果一個程序具有較高的局部性，則當把一個數據塊傳送到一個結點后，該結點對它的訪問就成為本地訪問，而消息傳遞方式的每次訪問都需要通訊。（2）許多并行應用程序都是分階段執(zhí)行的，每次執(zhí)行前，都有一個數據交換階段，其時間受通訊限制。在DSM系統(tǒng)中，數據只有用到的時候才傳送，取消了數據交換階段，把通訊時間加以分散，提高了并行性。（3）DSM提供的虛存空間比單個結點的存儲空間大得多，減少了換頁操作。3.實現DSM的途徑 主要有三種：（1）硬件實現：將傳統(tǒng)的cache技術擴展應用到松耦合分布式存儲多處理機。要增加專用部件以取得高效的實現。（2）操作

18、系統(tǒng)和庫實現：利用虛擬存儲管理機制取得共享（sharing）和一致（coherence）。（3）編譯實現：自動將共享訪問轉換成同步和一致原語。用戶需要顯式控制全局數據，當傳遞大量數據時或試圖進行進程遷移時極其復雜。4.主要技術結構（structure）粒度（granularity）數據訪問與一致性（access and cosistency）一致性語義（coherence semantics）可擴展性（scalability）異構性（heterogeneity） 結構指共享數據在存儲器中的框架（如 對象和語言的類型）；粒度指基本共享單位長度（如字節(jié)、字、頁或復雜數據結構）。第五章 并行存儲器系

19、統(tǒng)5.1 存儲器系統(tǒng)的層次結構5.2 包含性、一致性和局部性5.3 存儲器容量的規(guī)劃5.4 虛擬存儲器技術5.5 交叉訪問的存儲器5.5.1 兩種組織方式5.5.2 兩種方式的比較5.3.3 帶寬和容錯5.5 交叉訪問的存儲器主存儲器由多個模塊構成。假設主存儲器包含m=2a個存儲器模塊，每個模塊包含w=2b個存儲單元（字），則總存儲容量為個字bawm25.5.1 兩種組織方式交叉訪問的存儲器可以分為兩種：(1)低位交叉方式(2)高位交叉方式1.低位交叉方式存儲器地址的低a位用來指明存儲器模塊，高b位是每個模塊內的字地址。低位m路交叉存取如下圖：地址譯碼器MAB0mm(w-1)MDBM0MAB1

20、m+1mw-m+1MDBM1MABm-12m-1mw-1MDBMm-1MDB字模塊地址ab數據總線存儲器數據緩沖器模塊地址緩沖器字地址緩沖器2.高位交叉方式 存儲器地址的高a位作為存儲器模塊地址，鄰接的存儲器單元被分配在同一個存儲器模塊中，在每個存儲器周期內，只能對各模塊存取一個字。所以不支持鄰接單元的成塊存取。高位m路交叉存取如下圖：地址譯碼器MAB01w-1MDBM0MABww+12w-1MDBM1MAB(m-1)wmw-w-1mw-1MDBMm-1MDB字模塊地址ab數據總線存儲器數據緩沖器模塊地址緩沖器字地址緩沖器5.5.2 兩種方式的比較（1）低位交叉以流水線方式支持成塊存取 將存儲

21、器周期稱為主周期，細分為m個小周期（m稱為交叉存取度），如8路交叉，m=8，w=8，a=b=3，設為主周期，為小周期，則m8路低位交叉存取如下圖：0856存儲器地址寄存器(6位)M01957M121058M231159M341260M451361M561462M671563M7數據低位交叉流水線方式示意圖：W0W7W6W5W4W3W2W1時間為主周期，= /m為小周期，m為交叉存取度 （2）如果應用問題很少共享地址空間，把一個進程的幾頁集中在高位交叉存儲器的某個給定的存儲器模塊，能有效的減少存儲器干擾，即每個存儲器模塊只和一臺處理機有關，可以減少存儲器沖突。5.5.3 帶寬和容錯 1.帶寬討論低位交叉情況。帶寬B的上限為m，下限為1。Hellerman（1967年）推導出來的公式為：mmB56.0如果使用16個存儲器模塊，則有效存儲器帶寬大約是單個存儲器的4倍。產生這一悲觀估算的原因是：不同長度的塊存取與單字存取在用戶程序中是隨機混