[4] 并行存儲(chǔ)器系統(tǒng)

1、北京科技大學(xué)計(jì)算機(jī)系李建江參考課件：清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系高性能計(jì)算研究所 鄭緯民 教授第四章 并行存儲(chǔ)器系統(tǒng)4.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)4.2 包含性、一致性和局部性4.3 存儲(chǔ)器容量的規(guī)劃4.4 虛擬存儲(chǔ)器技術(shù)4.5 交叉訪問的存儲(chǔ)器4.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)如下圖所示：CPU內(nèi)的寄存器高速緩存主存儲(chǔ)器磁盤存儲(chǔ)器磁帶機(jī)層0：M0層1：M1層2：M2層3：M3層4：M4容量和存取時(shí)間增加每位成本增加五個(gè)參數(shù)：存取時(shí)間ti：從CPU到第i層存儲(chǔ)器的往返時(shí)間存儲(chǔ)器容量Si：第i層的字節(jié)的數(shù)量每字節(jié)成本Ci：第i層存儲(chǔ)器的成本為CiSi傳輸帶寬bi：相鄰層之間傳送信息的速

2、率傳輸單位Xi：i和i+1層之間數(shù)據(jù)傳送的粒度 對(duì)存儲(chǔ)器系統(tǒng)中各層次存儲(chǔ)器的特性，某統(tǒng)計(jì)數(shù)據(jù)如下表：存儲(chǔ)器層次特性第0層CPU寄存器第1層高速緩存第2層主存儲(chǔ)器第3層磁盤存儲(chǔ)器第4層磁帶存儲(chǔ)器設(shè)備工藝存取時(shí)間容量(字節(jié))成本(美分/KB)帶寬(MB/S)傳送單位分配管理ECLSRAMDRAM磁盤機(jī)磁帶機(jī)10ns25-40ns60-100ns10-20ms2-20min512B128KB512MB60-228GB512G-2TB18000725.60.230.01400-800250-40080-1333-50.18-0.23字:4-8B塊:32B頁:0.5-1KB文件:5-512KB后援存儲(chǔ)器

3、編譯器分配 硬件控制 操作系統(tǒng)操作系統(tǒng)/用戶操作系統(tǒng)/用戶第四章 并行存儲(chǔ)器系統(tǒng)4.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)4.2 包含性、一致性和局部性4.2.1 包含性4.2.2 一致性4.2.3 局部性4.3 存儲(chǔ)器容量的規(guī)劃4.4 虛擬存儲(chǔ)器技術(shù)4.5 交叉訪問的存儲(chǔ)器4.2 包含性、一致性和局部性4.2.1 包含性（inclusion）1. 包含性的定義M0 M1 M2 Mn 所有信息項(xiàng)最初存放在最外層Mn，在處理過程中，它的子集復(fù)制到Mn-1，同樣， Mn-1的子集復(fù)制到Mn-2， 如果在Mi中找到一個(gè)信息字，那么同一個(gè)字的復(fù)制品在所有的高層Mi+1，Mi+2，Mn中都一定可以找到。2. 相鄰層之

4、間的數(shù)據(jù)傳送單位CPU高速緩存：字字高速緩存主存儲(chǔ)器：塊塊（每塊32個(gè)字節(jié)（8個(gè)字）主存磁盤：頁面頁面（比如每頁4K字節(jié)，包含128塊）磁盤磁帶：段段包含性可以用下面的圖來說明：CPU寄存器baM1:高速緩存a,b為高速緩存塊，32個(gè)字節(jié)頁面AaM2:主存儲(chǔ)器頁面Bb頁面AaM3:磁盤存儲(chǔ)器頁面Bb段F段G頁面AaM4:磁帶機(jī)后援存儲(chǔ)器頁面Bb段F段G字單位塊單位頁單位段單位4.2.2 一致性（coherence）1.一致性定義同一個(gè)信息項(xiàng)與后繼存儲(chǔ)器層次的副本是一致的。如果在高速緩存中的一個(gè)字被修改過，那么在所有更高層上該字的副本也必須立即或最后加以修改 。2.維護(hù)一致性的兩種策略（1）寫直

5、達(dá)（write-through,WT），即如果在Mi（i=1，2，n-1）中修改了一個(gè)字，則在Mi+1中需要立即修改。 （2）寫回（write-back,WB），即如果在Mi+1 中的修改延遲到Mi中正在修改的字被替換時(shí)才進(jìn)行。4.2.3 局部性（locality）Hennessy和Patterson（1990年）提出了一條90-10規(guī)則：典型程序在10%的代碼上可能要耗費(fèi)其執(zhí)行時(shí)間的90%（例如嵌套循環(huán)操作的最內(nèi)層循環(huán)）。時(shí)間局部性（temporal locality）：最近的訪問項(xiàng)（指令或數(shù)據(jù)）很可能在不久的將來再次被訪問。即對(duì)最近使用區(qū)域的集中訪問?？臻g局部性（spatial local

6、ity）：一個(gè)進(jìn)程訪問的各項(xiàng)的地址彼此很近，例如，表操作或數(shù)組操作含對(duì)地址空間中某一區(qū)域的集中訪問。順序局部性（sequential locality）：在典型程序中，除非轉(zhuǎn)移指令產(chǎn)生不按次序的轉(zhuǎn)移外，指令都是順序執(zhí)行的。局部性原理指導(dǎo)我們?nèi)ピO(shè)計(jì)高速緩存、主存儲(chǔ)器以及虛擬存儲(chǔ)器組織。第四章 并行存儲(chǔ)器系統(tǒng)4.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)4.2 包含性、一致性和局部性4.3 存儲(chǔ)器容量的規(guī)劃5.3.1 命中率5.3.2 有效存取時(shí)間4.4 虛擬存儲(chǔ)器技術(shù)4.5 交叉訪問的存儲(chǔ)器4.3 存儲(chǔ)器容量的規(guī)劃存儲(chǔ)器層次結(jié)構(gòu)的性能是由層次結(jié)構(gòu)的有效存取時(shí)間Teff決定的，它依賴于相繼層次的命中率和訪問頻率。4

7、.3.1 命中率在Mi中找到一個(gè)信息項(xiàng)時(shí)，稱之為命中，反之稱為缺失。假定在層次結(jié)構(gòu)中的存儲(chǔ)器層次為Mi和Mi-1，其中i=1，2，n。 在Mi層的命中率hi則是信息項(xiàng)可在Mi中找到的概率。它是表示兩個(gè)相鄰層Mi-1和Mi特性的函數(shù)。 在Mi中的缺失率定義為1-hi。相繼層的命中率是存儲(chǔ)器容量、管理策略和程序行為的函數(shù)，它是獨(dú)立的隨機(jī)變量，其值在0到1之間。我們，這意味著CPU總是先訪問M1，并且訪問到最外層Mn時(shí)總是命中的。對(duì)Mi的訪問頻率為：iiihhhhf)1()1)(1(121是指在較低層次有i-1次缺失而在Mi有一次命中時(shí)訪問Mi成功的概率。111,1hffniiiiihhhhf)1(

8、)1)(1(121niif11111111)1()1(njjnijijihfhhfhfCPU總是先訪問M1訪問到最外層Mn時(shí)總是命中的nfff21通常情況下，有：這說明，訪問內(nèi)存比訪問外存要多。4.3.2 有效存取時(shí)間每當(dāng)發(fā)生缺失時(shí)，就要付出代價(jià)付出代價(jià)去訪問較高層次的存儲(chǔ)器。這種缺失在Cache中稱為塊缺失。在主存儲(chǔ)器中稱為缺頁錯(cuò)（page fault），因?yàn)閴K和頁面是這些層次之間傳送信息的單位。nnnniiieffthhhhthhthtfT)1()1)(1()1(121122111訪問到最外層Mn時(shí)總是命中的4.3.3 層次結(jié)構(gòu)的優(yōu)化目標(biāo)： 使Teff接近于M1的t1， 總成本接近于Mn的

9、CnSn 。優(yōu)化過程可以表達(dá)為：對(duì)一個(gè)線性規(guī)劃求最小值問題:減到最小值。要將有效存取時(shí)間總價(jià)格的上限）時(shí)，對(duì)于niiieffniiitotaliitfTCSCCSnitS101(,2, 1,0,0例子：存儲(chǔ)器層次結(jié)構(gòu)設(shè)計(jì)存儲(chǔ)器層次存取時(shí)間容量價(jià)格/K字節(jié)高速緩存主存儲(chǔ)器磁盤陣列t1 = 25nst2 = 未知t3 = 4mss1=512K字節(jié)s2=32M字節(jié)s3 = 未知c1=1.25美元c2=0.2美元c3=0.0002美元要達(dá)到有效存取時(shí)間Teff=10.04s,高速緩存命中率為h1=0.98，主存儲(chǔ)器命中率h2=0.9，總成本上限為15000美元。解：ustthhhthhthTGByte

10、SSCSCSCCSeff972.11104.10)1)(1()1(8.391500023321221113332211代入可得代入有：如果在同樣的預(yù)算限制條件下，要把主存儲(chǔ)器容量提高64M字節(jié)，那么只好以減少磁盤容量為代價(jià)，但是這一變化并不影響高速緩存的命中率。如果使用合適的頁面替換算法(主存與磁盤)，可能會(huì)增加主存儲(chǔ)器的命中率，Teff有所降低。層次化存儲(chǔ)器系統(tǒng)必須解決的問題：（1）數(shù)據(jù)塊在較高層存儲(chǔ)器中存放在哪個(gè)位置？即塊和頁的。如果一個(gè)塊存放在某一上層存儲(chǔ)器中，怎樣確定并找到該塊，即塊的。（2）不命中的將從下層存儲(chǔ)器中訪問，并將該塊調(diào)入上層存儲(chǔ)器中，但是如果上層存儲(chǔ)器中已無空閑空間，則勢

11、必將上層存儲(chǔ)器中的某一塊調(diào)出，但應(yīng)調(diào)出那一塊，即。（3）在寫訪問時(shí)，寫入上層存儲(chǔ)器中的數(shù)據(jù)必須在適當(dāng)?shù)臅r(shí)候?qū)懭胂聦哟鎯?chǔ)器，何時(shí)寫？即第四章 并行存儲(chǔ)器系統(tǒng)4.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)4.2 包含性、一致性和局部性4.3 存儲(chǔ)器容量的規(guī)劃4.4 虛擬存儲(chǔ)器技術(shù)4.3.1 共享存儲(chǔ)和分布存儲(chǔ)4.3.2 DSM與SVM4.3.3 虛擬存儲(chǔ)器的主要技術(shù)4.5 交叉訪問的存儲(chǔ)器4.4 虛擬存儲(chǔ)器技術(shù)提要：虛擬存儲(chǔ)器提供了的存儲(chǔ)器工作空間。虛擬地址在編譯時(shí)產(chǎn)生。虛擬地址到物理地址的轉(zhuǎn)換在運(yùn)行時(shí)進(jìn)行，需要使用轉(zhuǎn)換表和映象系統(tǒng)。4.4.1 共享存儲(chǔ)和分布存儲(chǔ)MIMD系統(tǒng)可以分為兩種：(1)tightly co

12、upled shared-Memory multiprocessors(2)loosely coupled distributed-Memory multiprocessors它們可以用圖表示如下：P1P2PnICN (Interconnection Network)SM1SMmshare-MemorymultiprocessorsPICNdistribued-MemorymultiprocessorsLMPLMPLM共享存儲(chǔ)和分布存儲(chǔ)的優(yōu)缺點(diǎn)：共享存儲(chǔ)器：易于編程，是單機(jī)的自然延伸；程序員沒有數(shù)據(jù)劃分的負(fù)擔(dān)；多進(jìn)程并發(fā)的開銷小，效率高，易于進(jìn)程遷移，任務(wù)動(dòng)態(tài)分配簡單；由于每個(gè)處理器都通過總線

13、通過總線訪問存儲(chǔ)器，因而限制了處理器的個(gè)數(shù)，可擴(kuò)展性差。分布存儲(chǔ)器：系統(tǒng)結(jié)構(gòu)靈活，可擴(kuò)展性好；處理機(jī)數(shù)目可達(dá)成百上千，處理速度有巨大的發(fā)展?jié)摿?；算法設(shè)計(jì)、編程以及任務(wù)動(dòng)態(tài)分配比較困難；很難在處理機(jī)之間傳遞復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，難于進(jìn)程遷移；不能支持需要存儲(chǔ)空間的大規(guī)模數(shù)據(jù)處理要求。分布存儲(chǔ)的兩種編程方法：（1）message-passing，用send，receive原語實(shí)現(xiàn)通信，要求程序員在進(jìn)程的整個(gè)運(yùn)行期間對(duì)數(shù)據(jù)的移動(dòng)都很清楚；（2）romote procedure call，語言一級(jí)傳送控制與數(shù)據(jù)，可以看作是本地調(diào)用，但透明度有限。缺點(diǎn)：這兩種方法都是用來解決不同地址空間的問題，在結(jié)點(diǎn)間傳遞復(fù)

14、雜數(shù)據(jù)結(jié)構(gòu)時(shí)都比較困難，需要打包。由于每個(gè)處理機(jī)擁有不同的地址空間，使得進(jìn)程遷移時(shí)，該進(jìn)程所分配到的操作系統(tǒng)資源也得一起移動(dòng)（打開的文件、文件存取控制塊等），這很費(fèi)時(shí)。4.4.2 DSM與SVM1.DSM和SVM的提出 如何把共享和分布的優(yōu)點(diǎn)結(jié)合起來，取長補(bǔ)短？共享分布存儲(chǔ)器（Distributed shared Memory，DSM）虛擬共享存儲(chǔ)器（Shared Virtual Memory，SVM）基于分布存儲(chǔ)器的多處理機(jī)上，實(shí)現(xiàn)物理上分布但邏輯上共享的存儲(chǔ)器系統(tǒng)。虛擬共享存儲(chǔ)器的邏輯結(jié)構(gòu)：CPU1虛擬共享存儲(chǔ)器LM1CPU2LM2CPUnLMn地址映射部件地址映射部件地址映射部件MIMD

15、機(jī)器存儲(chǔ)系統(tǒng)的發(fā)展方向：共享存儲(chǔ)器分布存儲(chǔ)器共享分布存儲(chǔ)器2.DSM系統(tǒng)的特點(diǎn) 在DSM系統(tǒng)中，每一臺(tái)處理機(jī)都可以訪問全局存儲(chǔ)器的任一位置，用戶可以把它當(dāng)成全局共享存儲(chǔ)器系統(tǒng)。 優(yōu)點(diǎn)：編程容易系統(tǒng)結(jié)構(gòu)靈活可擴(kuò)展性好系統(tǒng)價(jià)格低有較好的軟件移植性 DSM系統(tǒng)編制的程序比用消息傳遞方式編制的程序效率高：（1）在DSM系統(tǒng)中，數(shù)據(jù)都是以塊的方式進(jìn)行傳送，如果一個(gè)程序具有較高的，則當(dāng)把一個(gè)數(shù)據(jù)塊傳送到一個(gè)結(jié)點(diǎn)后，該結(jié)點(diǎn)對(duì)它的訪問就成為本地訪問，而消息傳遞方式的每次訪問都需要。（2）許多并行應(yīng)用程序都是分階段執(zhí)行的，每次執(zhí)行前，都有一個(gè)數(shù)據(jù)交換階段，其時(shí)間受通信限制。在DSM系統(tǒng)中，數(shù)據(jù)只有用到的時(shí)候才傳

16、送，取消了數(shù)據(jù)交換階段，把通信時(shí)間加以分散，提高了并行性。（3）DSM提供的虛存空間比單個(gè)結(jié)點(diǎn)的存儲(chǔ)空間大得多，減少了換頁操作。3.實(shí)現(xiàn)DSM的途徑 主要有三種：（1）硬件實(shí)現(xiàn)：將傳統(tǒng)的cache技術(shù)擴(kuò)展應(yīng)用到松耦合分布式存儲(chǔ)多處理機(jī)。要增加專用部件以取得高效的實(shí)現(xiàn)。（2）操作系統(tǒng)和庫實(shí)現(xiàn)：利用虛擬存儲(chǔ)管理機(jī)制取得共享（sharing）和一致（coherence）。（3）編譯實(shí)現(xiàn)：自動(dòng)將共享訪問轉(zhuǎn)換成同步和一致原語。用戶需要顯式控制全局?jǐn)?shù)據(jù)，當(dāng)傳遞大量數(shù)據(jù)時(shí)或試圖進(jìn)行進(jìn)程遷移時(shí)極其復(fù)雜。4.主要技術(shù)結(jié)構(gòu)（structure）粒度（granularity）數(shù)據(jù)訪問與一致性（access and

17、cosistency）一致性語義（coherence semantics）可擴(kuò)展性（scalability）異構(gòu)性（heterogeneity）結(jié)構(gòu)指共享數(shù)據(jù)在存儲(chǔ)器中的框架（如對(duì)象和語言的類型）；粒度指基本共享單位長度（如字節(jié)、字、頁或復(fù)雜數(shù)據(jù)結(jié)構(gòu)）。第四章 并行存儲(chǔ)器系統(tǒng)4.1 存儲(chǔ)器系統(tǒng)的層次結(jié)構(gòu)4.2 包含性、一致性和局部性4.3 存儲(chǔ)器容量的規(guī)劃4.4 虛擬存儲(chǔ)器技術(shù)4.5 交叉訪問的存儲(chǔ)器4.5.1 兩種組織方式4.5.2 兩種方式的比較4.3.3 容錯(cuò)4.5 交叉訪問的存儲(chǔ)器主存儲(chǔ)器。假設(shè)主存儲(chǔ)器包含m=2a個(gè)存儲(chǔ)器模塊，每個(gè)模塊包含w=2b個(gè)存儲(chǔ)單元（字），則總存儲(chǔ)容量為個(gè)字b

18、awm24.5.1 兩種組織方式交叉訪問的存儲(chǔ)器可以分為兩種：(1)低位交叉方式(2)高位交叉方式1.低位交叉方式存儲(chǔ)器地址的低a位用來指明存儲(chǔ)器模塊，高b位是每個(gè)模塊內(nèi)的字地址。低位m路交叉存取如下圖：MAB0mm(w-1)MDBM0MAB1m+1mw-m+1MDBM1MABm-12m-1mw-1MDBMm-1MDB字模塊地址ab數(shù)據(jù)總線存儲(chǔ)器數(shù)據(jù)緩沖器模塊地址緩沖器字地址緩沖器每個(gè)模塊每個(gè)模塊包含包含w=2w=2b b個(gè)存儲(chǔ)單個(gè)存儲(chǔ)單元（字）元（字）包含包含m=2m=2a a個(gè)個(gè)存儲(chǔ)器模塊存儲(chǔ)器模塊行優(yōu)先！行優(yōu)先！2.高位交叉方式存儲(chǔ)器地址的高a位作為存儲(chǔ)器模塊地址，鄰接的存儲(chǔ)器單元被分配在同一個(gè)存儲(chǔ)器模塊中，在每個(gè)存儲(chǔ)器周期內(nèi)，只能對(duì)各模塊存取一個(gè)字。所以不支持鄰接單元的成塊存取。高位m路交叉存取如下圖：MAB01w-1MDBM0MABww+12w-1MDBM1MAB(m-1)wmw-w-1mw-1MDBMm-1MDB字模塊地址ab數(shù)據(jù)總線存儲(chǔ)器數(shù)據(jù)緩沖器模塊地址緩沖器字地址緩沖器列優(yōu)先！列優(yōu)先！4.5.2 兩種方式的比較 （1）低位交叉以流水線方式支持成塊存取行優(yōu)先！行優(yōu)先！0856存儲(chǔ)器地址寄存器(6位)M01957M121058M231159M3412