并行存储器系统课件

並行記憶體系統5.1記憶體系統的層次結構

記憶體系統的層次結構如下圖所示：CPU內的寄存器高速緩存主記憶體磁片記憶體磁帶機層0：M0層1：M1層2：M2層3：M3層4：M4容量和存取時間增加每位成本增加五個參數：

存取時間ti：從CPU到第i層記憶體的往返時間

記憶體容量Si：第i層的位元組或字的數量

每位元組成本Ci：第i層記憶體的成本為CiSi

傳輸帶寬bi：相鄰層之間傳送資訊的速率

傳輸單位Xi：i和i+1層之間數據傳送的粒度 對記憶體系統中各層次記憶體的特性，1993年的統計數據如下表：記憶體層次特性第0層CPU寄存器第1層高速緩存第2層主記憶體第3層磁片記憶體第4層磁帶記憶體設備工藝存取時間容量(位元組)成本(美分/KB)帶寬(MB/S)傳送單位分配管理ECLSRAMDRAM磁片機磁帶機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後援記憶體編譯器分配硬體控制操作系統操作系統/用戶操作系統/用戶第五章並行記憶體系統

5.1記憶體系統的層次結構

5.2包含性、一致性和局部性

5.2.1包含性

5.2.2一致性

5.2.3局部性

5.3記憶體容量的規劃

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個位元組（8個字））

主存

磁片：頁面（比如每頁4K位元組，包含128塊）

磁片

磁帶：段包含性可以用下麵的圖來說明：CPU寄存器……ba……M1:高速緩存a,b為高速緩存塊，32個位元組頁面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）寫回（write-back,WB），即如果在Mi+1

中的修改延遲到Mi中正在修改的字被替換時才進行。

5.2.3局部性（locality）

Hennessy和Patterson（1990年）提出了一條90-10規則：典型程式在10%的代碼上可能要耗費其執行時間的90%（例如嵌套迴圈操作的最內層迴圈）。

時間局部性（temporallocality）：最近的訪問項（指令或數據）很可能在不久的將來再次被訪問。即對最近使用區域的集中訪問。

空間局部性（spatiallocality）：一個進程訪問的各項的地址彼此很近，例如，表操作或數組操作含對地址空間中某一區域的集中訪問。 順序局部性（sequentiallocality）：在典型程式中，除非轉移指令產生不按次序的轉移外，指令都是順序執行的。局部性原理指導我們去設計高速緩存、主記憶體以及虛擬記憶體組織。第五章並行記憶體系統

5.1記憶體系統的層次結構

5.2包含性、一致性和局部性

5.3記憶體容量的規劃

5.3.1命中率

5.3.2有效存取時間

5.4虛擬記憶體技術

5.5交叉訪問的記憶體5.3記憶體容量的規劃

記憶體層次結構的性能是由層次結構的有效存取時間Teff決定的，它依賴於相繼層次的命中率和訪問頻率。

5.3.1命中率

在Mi中找到一個資訊項時，稱之為命中，反之稱為缺失。 假定在層次結構中的記憶體層次為Mi和Mi-1，其中i=1，2，…，n。在Mi層的命中率hi則是資訊項可在Mi中找到的概率。它是表示兩個相鄰層Mi-1和Mi特性的函數。在Mi中的缺失率定義為1-hi。

相繼層的命中率是記憶體容量、管理策略和程式行為的函數，它是獨立的隨機變數，其值在0到1之間。我們假設h0=0和hn=1，這意味著CPU總是先訪問M1，並且訪問到最外層Mn時總是命中的。 對Mi的訪問頻率為：

是指在較低層次有i-1次缺失而在Mi有一次命中時訪問Mi成功的概率。

通常情況下，有：

這說明，訪問記憶體比訪問外存要多。

5.3.2有效存取時間

每當發生缺失時，就要付出代價去訪問較高層次的記憶體。這種缺失在Cache中稱為塊缺失。在主記憶體中稱為缺頁錯（pagefault），因為塊和頁面是這些層次之間傳送資訊的單位。 缺頁錯付出的時間代價要比塊缺失付出的更大：

5.3.3層次結構的優化

目標： 使Teff接近於M1的t1， 總成本接近於Mn的Cn。 優化過程可以表達為：對一個線性規劃求最小值問題:

例子：記憶體層次結構設計記憶體層次存取時間容量價格/K位元組高速緩存主記憶體磁片陣列t1=25nst2=未知t3=4mss1=512K位元組s2=32M位元組s3=未知c1=1.25美元c2=0.2美元c3=0.0002美元

要達到有效存取時間Teff=10.04s,高速緩存命中率為h1=0.98，主記憶體命中率h2=0.9，總成本上限為15000美元。

解：

如果在同樣的預算限制條件下，要吧主記憶體容量提高64M位元組，那麼只好以減少磁片容量為代價，但是這一變化並不影響高速緩存的命中率。如果使用合適的頁面替換演算法，可能會增加主記憶體的命中率，Teff有所降低。

層次化記憶體系統必須解決的問題：

（1）數據塊在較高層記憶體中存放在哪個位置？即塊和頁的定位問題。如果一個塊存放在某一上層記憶體中，怎樣確定並找到該塊，即塊的尋址問題。 （2）不命中的將從下層記憶體中訪問，並將該塊調入上層記憶體中，但是如果上層記憶體中已無空閒空間，則勢必將上層記憶體中的某一塊調出，但應調出那一塊，即替換問題。 （3）在寫訪問時，寫入上層記憶體中的數據必須在適當的時候寫入下層記憶體，何時寫？第五章並行記憶體系統

5.1記憶體系統的層次結構

5.2包含性、一致性和局部性

5.3記憶體容量的規劃

5.4虛擬記憶體技術

5.3.1共用存儲和分佈存儲

5.3.2DSM與SVM 5.3.3虛擬記憶體的主要技術

5.5交叉訪問的記憶體5.4虛擬記憶體技術

提要： 虛擬記憶體提供了幾乎沒有限制的記憶體工作空間。 虛擬地址在編譯時產生。 虛擬地址到物理地址的轉換在運行時進行，需要使用轉換表和映象系統。 替換策略。

5.4.1共用存儲和分佈存儲

MIMD系統可以分為兩種：

(1)tightlycoupledshared-Memorymultiprocessors

(2)looselycoupleddistributed-Memorymultiprocessors

它們可以用圖表示如下：P1P2……PnICNSM1……SMmshare-MemorymultiprocessorsP……ICNdistribued-MemorymultiprocessorsLMPLMPLM

共用存儲和分佈存儲的優缺點：

共用記憶體： 易於編程，是單機的自然延伸； 程式員無數據劃分的負擔； 多進程併發的開銷小，效率高，易於進程遷移，任務動態分配簡單； 由於每個處理器都通過匯流排訪問記憶體，因而限制了處理器的個數，可擴展性差。

分佈記憶體： 系統結構靈活，可擴展性好； 處理機數目可達成百上千，處理速度有巨大的發展潛力； 演算法設計、編程以及任務動態分配比較困難； 很難在處理機之間傳遞複雜的數據結構，難於進程遷移； 不能支持需要存儲空間的大規模數據處理要求。

分佈存儲的兩種編程方法： （1）message-passing，用send，receive原語實現通信，要求程式員在進程的整個運行期間對數據的移動都很清楚； （2）romoteprocedurecall，語言一級傳送控制與數據，可以看作是本地調用，但透明度有限。

缺點： 這兩種方法都是用來解決不同地址空間的問題，在接點間傳遞複雜數據結構時都比較困難，需要打包，傳遞指針也不可能實現。由於個處理機擁有不同的地址空間，使得進程遷移時，該進程所分配到的操作系統資源也得一起移動（打開得檔、檔存取控制塊等），這很費時。

5.4.2DSM與SVM

1.DSM和SVM的提出

如何把共用和分佈的優點結合起來，取長補短？

共用分佈記憶體（DistributedsharedMemory，DSM）

虛擬共用記憶體（SharedVirtualMemory，SVM）

——基於分佈記憶體的多處理機上，實現物理上分佈但邏輯上共用的記憶體系統。

虛擬共用記憶體的邏輯結構：CPU1……虛擬共用記憶體LM1CPU2LM2CPUnLMn地址映射部件地址映射部件……地址映射部件

MIMD機器存儲系統的發展方向：共用記憶體分佈記憶體共用分佈記憶體

2.DSM系統的特點

在DSM系統中，每一臺處理機都可以訪問全局記憶體的任一位置，用戶可以把它當成全局共用記憶體系統。

優點：

編程容易 系統結構靈活 可擴展性好 系統價格低 有較好的軟體移植性

DSM系統編制的程式比用消息傳遞方式編制的程式效率高：

（1）在DSM系統中，數據都是以塊的方式進行傳送，如果一個程式具有較高的局部性，則當把一個數據塊傳送到一個結點後，該結點對它的訪問就成為本地訪問，而消息傳遞方式的每次訪問都需要通訊。

（2）許多並行應用程式都是分階段執行的，每次執行前，都有一個數據交換階段，其時間受通訊限制。在DSM系統中，數據只有用到的時候才傳送，取消了數據交換階段，把通訊時間加以分散，提高了並行性。

（3）DSM提供的虛存空間比單個結點的存儲空間大得多，減少了換頁操作。

3.實現DSM的途徑

主要有三種：

（1）硬體實現：將傳統的cache技術擴展應用到松耦合分佈式存儲多處理機。要增加專用部件以取得高效的實現。

（2）操作系統和庫實現：利用虛擬存儲管理機制取得共用（sharing）和一致（coherence）。

（3）編譯實現：自動將共用訪問轉換成同步和一致原語。用戶需要顯式控制全局數據，當傳遞大量數據時或試圖進行進程遷移時極其複雜。

4.主要技術

結構（structure）

粒度（granularity） 數據訪問與一致性（accessandcosistency）

一致性語義（coherencesemantics）

可擴展性（scalability）

異構性（heterogeneity） 結構——指共用數據在記憶體中的框架（如對象和語言的類型）； 粒度——指基本共用單位長度（如位元組、字、頁或複雜數據結構）。第五章並行記憶體系統

5.1記憶體系統的層次結構

5.2包含性、一致性和局部性

5.3記憶體容量的規劃

5.4虛擬記憶體技術

5.5交叉訪問的記憶體

5.5.1兩種組織方式

5.5.2兩種方式的比較

5.3.3帶寬和容錯5.5交叉訪問的記憶體

主記憶體由多個模組構成。 假設主記憶體包含m=2a個記憶體模組，每個模組包含w=2b個存儲單元（字），則總存儲容量為

5.5.1兩種組織方式

交叉訪問的記憶體可以分為兩種：

(1)低位交叉方式

(2)高位交叉方式

1.低位交叉方式

記憶體地址的低a位用來指明記憶體模組，高b位是每個模組內的字地址。 低位m路交叉存取如下圖：地址解碼器MAB0m……m(w-1)MDBM0MAB1m+1……mw-m+1MDBM1……MABm-12m-1……mw-1MDBMm-1MDB字模組……地址ab數據匯流排記憶體數據緩衝器模組地址緩衝器字地址緩衝器

2.高位交叉方式

記憶體地址的高a位作為記憶體模組地址，鄰接的記憶體單元被分配在同一個記憶體模組中，在每個記憶體週期內，只能對各模組存取一個字。所以不支持鄰接單元的成塊存取。 高位m路交叉存取如下圖：地址解碼器MAB01……w-1MDBM0MABww+1……2w-1MDBM1……MAB(m-1)wmw-w-1……mw-1MDBMm-1MDB字模組……地址ab數據匯流排記憶體數據緩衝器模組地址緩衝器字地址緩衝器

5.5.2兩種方式的比較

（1）低位交叉以流水線方式支持成塊存取

將記憶體週期稱為主週期，細分為m個小週期（m稱為交叉存取度），如8路交叉，m=8，w=8，a=b=3，設

為主週期，

為小週期，則

8路低位交叉存取如下圖：08…56記憶體地址寄存器(6位)M019…57M1210…58M2311…59M3412…60M4513…61M5614…62M6715…63M7數據

低位交叉流水線方式示意圖：W0W7W6W5W4W3W2W1

時間

為主週期，=/m為小週期，m為交叉存取度

（2）如果應用問題很少共用地址空間，把一個進程的幾頁集中在高位交叉記憶體的某個給定的記憶體模組種，能有效的減少記憶體干擾，即每個記憶體模組只和一臺處理機有關，可以減少記憶體衝突。

5.5.3帶寬和容錯

1.帶寬

討論低位交叉情況。 帶寬B的上限為m，下限為1。Hellerman（1967年）推導出來的公式為：

如果使用16個記憶體模組，則有效記憶體帶寬大約是單個記憶體的4倍。產生這一悲觀估算的原因是：不同長度的塊存取與單字存取在用戶程式中是隨機混合的。

另外一種估算公式：Cragon（1992年） 假設n個分量存放在m路交叉存取記憶體系統鄰接的存儲單元中，存取向量的一個分量所需的平均時間t1可估算為：

所以，交叉存取適合於長向量的流水線存取。

2.容錯

將高位