第5章存儲系統(tǒng)

第5章存儲系統(tǒng)張晨曦劉依www.A微信公眾號：arch3655.1 存儲系統(tǒng)的基本知識5.2 Cache基本知識5.3 降低Cache不命中率5.4 減少Cache不命中開銷5.5 減少命中時間5.6 并行主存系統(tǒng)5.7 虛擬存儲器5.8 實例：AMDOpteron的存儲器層次結構計算機系統(tǒng)結構設計中關鍵的問題之一

：如何以合理的價格，設計容量和速度都滿足計算機系統(tǒng)要求的存儲器系統(tǒng)？人們對這三個指標的要求

容量大、速度快、價格低三個要求是相互矛盾的速度越快，每位價格就越高；容量越大，每位價格就越低；容量越大，速度越慢。5.1存儲系統(tǒng)的基本知識5.1.1存儲系統(tǒng)的層次結構

5.1存儲系統(tǒng)的基本知識解決方法：采用多種存儲器技術，構成多級存儲層次結構。程序訪問的局部性原理：對于絕大多數(shù)程序來說，程序所訪問的指令和數(shù)據(jù)在地址上不是均勻分布的，而是相對簇聚的。(局部性原理)程序訪問的局部性包含兩個方面時間局部性：程序馬上將要用到的信息很可能就是現(xiàn)在正在使用的信息?？臻g局部性：程序馬上將要用到的信息很可能與現(xiàn)在正在使用的信息在存儲空間上是相鄰的。5.1存儲系統(tǒng)的基本知識存儲系統(tǒng)的多級層次結構

演示多級存儲層次5.1存儲系統(tǒng)的基本知識假設第i個存儲器Mi的訪問時間為Ti，容量為Si，平均每位價格為Ci，則訪問時間：T1<T2<…<Tn容量：S1<S2<…<Sn平均每位價格：C1>C2>…>Cn

整個存儲系統(tǒng)要達到的目標：從CPU來看，該存儲系統(tǒng)的速度接近于M1的，而容量和每位價格都接近于Mn的。存儲器越靠近CPU，則CPU對它的訪問頻度越高，而且最好大多數(shù)的訪問都能在M1完成。5.1存儲系統(tǒng)的基本知識下面僅考慮由M1和M2構成的兩級存儲層次：M1的參數(shù)：S1，T1，C1M2的參數(shù)：S2，T2，C25.1.2存儲層次的性能參數(shù)5.1存儲系統(tǒng)的基本知識存儲容量S一般來說，整個存儲系統(tǒng)的容量即是第二級存儲器M2的容量，即S=S2。每位價格C當S1<<S2時，C≈C2。

5.1存儲系統(tǒng)的基本知識命中率H和不命中率F命中率：CPU訪問存儲系統(tǒng)時，在M1中找到所需信息的概率。N1

──訪問M1的次數(shù)N2──訪問M2的次數(shù)

不命中率：F＝1－H5.1存儲系統(tǒng)的基本知識平均訪問時間TA

TA ＝HT1＋（1－H）（T1＋TM） ＝T1＋（1－H）TM

或TA ＝T1＋FTM分兩種情況來考慮CPU的一次訪存：當命中時，訪問時間即為T1（命中時間）當不命中時，情況比較復雜。不命中時的訪問時間為：T2＋TB＋T1＝T1＋TM

TM＝T2＋TB不命中開銷TM：從向M2發(fā)出訪問請求到把整個數(shù)據(jù)塊調(diào)入M1中所需的時間。傳送一個信息塊所需的時間為TB。5.1存儲系統(tǒng)的基本知識

三級存儲系統(tǒng)Cache（高速緩沖存儲器）主存儲器磁盤存儲器（輔存）可以看成是由“Cache—主存”層次和“主存—輔存”層次構成的系統(tǒng)。5.1.3三級存儲系統(tǒng)5.1存儲系統(tǒng)的基本知識

從主存的角度來看“Cache－主存”層次：彌補主存速度的不足“主存－輔存”層次：彌補主存容量的不足“Cache—主存”層次主存與CPU的速度差距“Cache-主存”層次

“主存－輔存”層次5.1存儲系統(tǒng)的基本知識1980年以來存儲器和CPU性能隨時間而提高的情況（以1980年時的性能作為基準）5.1存儲系統(tǒng)的基本知識兩種存儲層次5.1存儲系統(tǒng)的基本知識存儲層次CPU對第二級的

訪問方式比較項目目的存儲管理實現(xiàn)

訪問速度的比值

(第一級和第二級)典型的塊(頁)大小不命中時CPU是否切換“Cache－主存”層次“主存－輔存”層次為了彌補主存速度的不足為了彌補主存容量的不足主要由專用硬件實現(xiàn)主要由軟件實現(xiàn)幾比一幾萬比一幾十個字節(jié)幾百到幾千個字節(jié)可直接訪問均通過第一級不切換切換到其他進程“Cache－主存”與“主存－輔存”層次的區(qū)別5.1存儲系統(tǒng)的基本知識當把一個塊調(diào)入高一層(靠近CPU)存儲器時，

可以放在哪些位置上?

（映像規(guī)則）當所要訪問的塊在高一層存儲器中時，如何

找到該塊?（查找算法）當發(fā)生不命中時，應替換哪一塊？（替換算法）當進行寫訪問時，應進行哪些操作?

（寫策略）5.1.4存儲層次的四個問題存儲空間分割與地址計算Cache和主存分塊Cache是按塊進行管理的。Cache和主存均被分割成大小相同的塊。信息以塊為單位調(diào)入Cache。主存塊地址（塊號）用于查找該塊在Cache中的位置。塊內(nèi)位移用于確定所訪問的數(shù)據(jù)在該塊中的位置。5.2Cache基本知識

5.2.1

基本結構和原理

Cache的基本工作原理示意圖

5.2.2

映像規(guī)則

全相聯(lián)映像全相聯(lián)：主存中的任一塊可以被放置到Cache中的任意一個位置。舉例對比：閱覽室位置──隨便坐特點：空間利用率最高，沖突概率最低，實現(xiàn)最復雜。5.2Cache基本知識5.2Cache基本知識5.2Cache基本知識直接映像直接映像：主存中的每一塊只能被放置到Cache中唯一的一個位置。舉例（循環(huán)分配）對比：閱覽室位置──只有一個位置可以坐特點：空間利用率最低，沖突概率最高，實現(xiàn)最簡單。對于主存的第i

塊，若它映像到Cache的第j

塊，則:

j＝imod(M

)

（M為Cache的塊數(shù)）設M=2m，則當表示為二進制數(shù)時，j實際上就是i的低m位:

ji：m位5.2Cache基本知識5.2Cache基本知識組相聯(lián)映像組相聯(lián)：主存中的每一塊可以被放置到Cache中唯一的一個組中的任何一個位置。舉例組相聯(lián)是直接映像和全相聯(lián)的一種折中5.2Cache基本知識組的選擇常采用位選擇算法若主存第i

塊映像到第k

組，則:

k＝imod（G）（G為Cache的組數(shù)）設G＝2g，則當表示為二進制數(shù)時，k實際上就是i的低g位:低g位以及直接映像中的低m位通常稱為索引。

ki：g位5.2Cache基本知識n路組相聯(lián)：每組中有n個塊(n＝M/G)。

n稱為相聯(lián)度。相聯(lián)度越高，Cache空間的利用率就越高，塊沖突概率就越低，不命中率也就越低。絕大多數(shù)計算機的Cache:n≤4想一想：相聯(lián)度一定是越大越好？全相聯(lián)直接映像

組相聯(lián)n(路數(shù))G(組數(shù))MM111＜n＜M1＜G＜M5.2Cache基本知識當CPU訪問Cache時，如何確定Cache中是否有所要訪問的塊？若有的話，如何確定其位置？通過查找目錄表來實現(xiàn)目錄表的結構主存塊的塊地址的高位部分，稱為標識。每個主存塊能唯一地由其標識來確定5.2.3查找算法5.2Cache基本知識只需查找候選位置所對應的目錄表項并行查找與順序查找提高性能的重要思想：主候選位置(MRU塊)

（前瞻執(zhí)行）并行查找的實現(xiàn)方法相聯(lián)存儲器目錄由2g個相聯(lián)存儲區(qū)構成，每個相聯(lián)存儲區(qū)的大小為n×（h+log2n）位。根據(jù)所查找到的組內(nèi)塊地址，從Cache存儲體中讀出的多個信息字中選一個，發(fā)送給CPU。

5.2Cache基本知識5.2Cache基本知識單體多字存儲器＋比較器舉例：４路組相聯(lián)并行標識比較（比較器的個數(shù)及位數(shù)）４路組相聯(lián)Cache的查找過程直接映像Cache的查找過程優(yōu)缺點不必采用相聯(lián)存儲器，而是用按地址訪問的存儲器來實現(xiàn)。所需要的硬件為：大小為2g×n×h位的存儲器和n個h位的比較器。當相聯(lián)度n增加時，不僅比較器的個數(shù)會增加，而且比較器的位數(shù)也會增加。5.2Cache基本知識5.2Cache基本知識例子：DEC的AlphaAXP21064中的內(nèi)部數(shù)據(jù)Cache簡介容量：8KB塊大?。?2B塊數(shù)：256映像方法：直接映像寫緩沖器大小：4個塊5.2.4Cache的工作過程結構圖5.2Cache基本知識工作過程“讀”訪問命中（完成4步需要2個時鐘周期）Cache的容量與索引index、相聯(lián)度、塊大小之間的關系

Cache的容量=2index×相聯(lián)度×塊大小

把容量為8192、相聯(lián)度為1、塊大小為32（字節(jié)）代入：索引index：8位標識：29－8＝21位“寫”訪問命中5.2Cache基本知識設置了一個寫緩沖器（提高“寫”訪問的速度）按字尋址的，它含有4個塊，每塊大小為4個字。當要進行寫入操作時，如果寫緩沖器不滿，那么就把數(shù)據(jù)和完整的地址寫入緩沖器。對CPU而言，本次“寫”訪問已完成，CPU可以繼續(xù)往下執(zhí)行。由寫緩沖器負責把該數(shù)據(jù)寫入主存。在寫入緩沖器時，要進行寫合并檢查。即檢查本次寫入數(shù)據(jù)的地址是否與緩沖器內(nèi)某個有效塊的地址匹配。如果匹配，就把新數(shù)據(jù)與該塊合并。5.2Cache基本知識發(fā)生讀不命中與寫不命中時的操作讀不命中：向CPU發(fā)出一個暫停信號，通知它等待，并從下一級存儲器中新調(diào)入一個數(shù)據(jù)塊（32字節(jié)）。寫不命中：將使數(shù)據(jù)“繞過”Cache，直接寫入主存。對比：AlphaAXP21264的數(shù)據(jù)Cache結構容量：64KB

塊大?。?4字節(jié)

LRU替換策略主要區(qū)別采用2路組相聯(lián)采用寫回法沒有寫緩沖器5.2Cache基本知識替換算法所要解決的問題：當新調(diào)入一塊，而Cache又已被占滿時，替換哪一塊？直接映像Cache中的替換很簡單因為只有一個塊，別無選擇。在組相聯(lián)和全相聯(lián)Cache中，則有多個塊供選擇。主要的替換算法有三種隨機法優(yōu)點：實現(xiàn)簡單先進先出法FIFO5.2.5替換算法5.2Cache基本知識最近最少使用法LRU選擇近期最少被訪問的塊作為被替換的塊。

（實現(xiàn)比較困難）實際上：選擇最久沒有被訪問過的塊作為被替換的塊。

優(yōu)點：命中率較高LRU和隨機法分別因其不命中率低和實現(xiàn)簡單而被廣泛采用。模擬數(shù)據(jù)表明，對于容量很大的Cache，LRU和隨機法的命中率差別不大。5.2Cache基本知識LRU算法的硬件實現(xiàn)堆棧法用一個堆棧來記錄組相聯(lián)Cache的同一組中各塊被訪問的先后次序。用堆棧元素的物理位置來反映先后次序棧底記錄的是該組中最早被訪問過的塊，次棧底記錄的是該組中第二個被訪問過的塊，…，棧頂記錄的是剛訪問過的塊。當需要替換時，從棧底得到應該被替換的塊（塊地址）。5.2Cache基本知識5.2Cache基本知識堆棧中的內(nèi)容必須動態(tài)更新當Cache訪問命中時，通過用塊地址進行相聯(lián)查找，在堆棧中找到相應的元素，然后把該元素的上面的所有元素下壓一個位置，同時把本次訪問的塊地址抽出來，從最上面壓入棧頂。而該元素下面的所有元素則保持不動。如果Cache訪問不命中，則把本次訪問的塊地址從最上面壓入棧頂，堆棧中所有原來的元素都下移一個位置。如果Cache中該組已經(jīng)沒有空閑塊，就要替換一個塊。這時從棧底被擠出去的塊地址就是需要被替換的塊的塊地址。5.2Cache基本知識堆棧法所需要的硬件需要為每一組都設置一個項數(shù)與相聯(lián)度相同的小堆棧，每一項的位數(shù)為log2n位。硬件堆棧所需的功能相聯(lián)比較能全部下移、部分下移和從中間取出一項的功能速度較低，成本較高（只適用于相聯(lián)度較小的LRU算法）比較對法基本思路讓各塊兩兩組合，構成比較對。每一個比較對用一個觸發(fā)器的狀態(tài)來表示它所相關的兩個塊最近一次被訪問的遠近次序，再經(jīng)過門電路就可找到LRU塊。5.2Cache基本知識

例如：假設有A、B、C三個塊，可以組成3對：AB、AC、BC。每一對中塊的訪問次序分別用“對觸發(fā)器”TAB、TAC、TBC表示。TAB為“1”，表示A比B更近被訪問過；TAB為“0”，表示B比A更近被訪問過。TAC、TBC也是按這樣的規(guī)則定義。

顯然，當TAC＝1且TBC＝1時，C就是最久沒有被訪問過了。（A比C更近被訪問過、且B比C也是更近被訪問過）即：CLRU=TAC·TBC

同理可得：

用觸發(fā)器和與門實現(xiàn)上述邏輯的電路：5.2Cache基本知識用比較對法實現(xiàn)LRU算法

5.2Cache基本知識比較對法所需的硬件量與門有多少個塊，就要有多少個與門；每個與門的輸入端要連接所有與之相關的觸發(fā)器。對于一個具有P塊的組中的任何一個塊來說，由于它可以跟除了它自己以外的所有其他的塊兩兩組合，所以與該塊相關的比較對觸發(fā)器個數(shù)為P－1，因而其相應的與門的輸入端數(shù)是P－1。觸發(fā)器所需要的觸發(fā)器的個數(shù)與兩兩組合的比較對的數(shù)目相同。比較對觸發(fā)器個數(shù)、與門的個數(shù)、與門的輸入端數(shù)與塊數(shù)P的關系組內(nèi)塊數(shù)3481664256…P觸發(fā)器個數(shù)3628120201632640…與門個數(shù)3481664256…P與門輸入端個數(shù)2371563255…P-15.2Cache基本知識塊數(shù)少時，所需要的硬件較少，隨著組內(nèi)塊數(shù)P的增加，所需的觸發(fā)器的個數(shù)會以平方的關系迅速增加，門的輸入端數(shù)也線性增加。

（硬件實現(xiàn)的成本很高）當組內(nèi)塊數(shù)較多時，可以用多級狀態(tài)位技術減少所需的硬件量。例如：在IBM3033中組內(nèi)塊數(shù)為16，可分成群、對、行3級。先分成4群，每群兩對，每對兩行。選LRU群需6個觸發(fā)器；每群中選LRU對需要一個觸法器，4個群共需要4個觸發(fā)器；5.2Cache基本知識每行中選LRU塊需要一個觸發(fā)器，8個行共需要8個觸發(fā)器。所需的觸發(fā)器總個數(shù)為：

6（選群）＋4（選對）＋8（選行）=18（個）

以犧牲速度為代價的。5.2Cache基本知識“寫”在所有訪存操作中所占的比例統(tǒng)計結果表明，對于一組給定的程序：load指令：26％store指令：9％“寫”在所有訪存操作中所占的比例：

9％/(100％＋26％＋9％)≈7％“寫”在訪問Cache操作中所占的比例：

9％/(26％＋9％)≈25％5.2.6寫策略5.2Cache基本知識“寫”操作必須在確認是命中后才可進行“寫”訪問有可能導致Cache和主存內(nèi)容的不一致兩種寫策略寫策略是區(qū)分不同Cache設計方案的一個重要標志。寫直達法（也稱為存直達法）執(zhí)行“寫”操作時，不僅寫入Cache，而且也寫入下一級存儲器。寫回法（也稱為拷回法）執(zhí)行“寫”操作時，只寫入Cache。僅當Cache中相應的塊被替換時，才寫回主存。(設置“修改位”)

5.2Cache基本知識兩種寫策略的比較寫回法的優(yōu)點：速度快，所使用的存儲器

帶寬較低。寫直達法的優(yōu)點：易于實現(xiàn)，一致性好。采用寫直達法時，若在進行“寫”操作的過程中CPU必須等待，直到“寫”操作結束，則稱CPU寫停頓。減少寫停頓的一種常用的優(yōu)化技術：采用寫緩沖器5.2Cache基本知識“寫”操作時的調(diào)塊按寫分配(寫時取)寫不命中時，先把所寫單元所在的塊調(diào)入Cache，再行寫入。不按寫分配(繞寫法)寫不命中時，直接寫入下一級存儲器而不調(diào)塊。寫策略與調(diào)塊寫回法──按寫分配寫直達法──不按寫分配5.2Cache基本知識不命中率與硬件速度無關容易產(chǎn)生一些誤導平均訪存時間

平均訪存時間＝命中時間＋不命中率×不命中開銷5.2.7Cache的性能分析程序執(zhí)行時間CPU時間＝（CPU執(zhí)行周期數(shù)+存儲器停頓周期數(shù)）×時鐘周期時間其中：存儲器停頓時鐘周期數(shù)＝“讀”的次數(shù)×讀不命中率×讀不命中開銷＋“寫”的次數(shù)×寫不命中率×寫不命中開銷存儲器停頓時鐘周期數(shù)＝訪存次數(shù)×不命中率×不命中開銷

CPU時間＝（CPU執(zhí)行周期數(shù)+訪存次數(shù)×不命中率×不命中開銷）

×時鐘周期時間=IC×（CPIexecution＋每條指令的平均訪存次數(shù)×不命中率

×不命中開銷）×時鐘周期時間5.2Cache基本知識

例5.1

用一個和AlphaAXP類似的機器作為第一個例子。假設Cache不命中開銷為50個時鐘周期，當不考慮存儲器停頓時，所有指令的執(zhí)行時間都是2.0個時鐘周期，訪問Cache不命中率為2%，平均每條指令訪存1.33次。試分析Cache對性能的影響。

解

CPU時間有cache＝IC×（CPIexecution＋每條指令的平均訪存次數(shù)

×不命中率×不命中開銷）×時鐘周期時間＝IC×（2.0＋1.33×2%×50）×時鐘周期時間＝IC×3.33×時鐘周期時間5.2Cache基本知識

考慮Cache的不命中后，性能為：

CPU時間有cache＝IC×（2.0＋1.33×2%×50）×時鐘周期時間

＝IC×3.33×時鐘周期時間

實際CPI：3.33

3.33/2.0=1.67(倍)

CPU時間也增加為原來的1.67倍。但若不采用Cache,則：

CPI＝2.0＋50×1.33＝68.55.2Cache基本知識Cache不命中對于一個CPI較小而時鐘頻率較高的CPU來說，影響是雙重的：CPIexecution越低，固定周期數(shù)的Cache不命中開銷的相對影響就越大。在計算CPI時，不命中開銷的單位是時鐘周期數(shù)。因此，即使兩臺計算機的存儲層次完全相同，時鐘頻率較高的CPU的不命中開銷較大，其CPI中存儲器停頓這部分也就較大。因此Cache對于低CPI、高時鐘頻率的CPU來說更加重要。

例5.2

考慮兩種不同組織結構的Cache：直接映像Cache和兩路組相聯(lián)Cache，試問它們對CPU的性能有何影響？先求平均訪存時間，然后再計算CPU性能。分析時請用以下假設：

(1)理想Cache（命中率為100%）情況下的CPI為2.0，時鐘周期為2ns，平均每條指令訪存1.3次。

(2)兩種Cache容量均為64KB，塊大小都是32字節(jié)。

(3)在組相聯(lián)Cache中，由于多路選擇器的存在而使CPU的時鐘周期增加到原來的1.10倍。這是因為對Cache的訪問總是處于關鍵路徑上，對CPU的時鐘周期有直接的影響。

(4)這兩種結構Cache的不命中開銷都是70ns。（在實際應用中，應取整為整數(shù)個時鐘周期）

(5)命中時間為1個時鐘周期，64KB直接映像Cache的不命中率為1.4%，相同容量的兩路組相聯(lián)Cache的不命中率為1.0%。5.2Cache基本知識

解平均訪存時間為：平均訪存時間＝命中時間＋不命中率×不命中開銷因此，兩種結構的平均訪存時間分別是：

平均訪存時間1路＝2.0＋（0.014×70）＝2.98ns

平均訪存時間2路＝2.0×1.10＋（0.010×70）＝2.90ns

兩路組相聯(lián)Cache的平均訪存時間比較低。

CPU時間＝IC×（CPIexecution＋每條指令的平均訪存次數(shù)×

不命中率×不命中開銷）×時鐘周期時間＝IC×（CPIexecution×時鐘周期時間＋每條指令的平均訪存次數(shù)×不命中率×不命中開銷×時鐘周期時間）5.2Cache基本知識因此：CPU時間1路＝IC×(2.0×2＋(1.3×0.014×70))

＝5.27×ICCPU時間2路＝IC×(2.0×2×1.10＋(1.3×0.010×70))

＝5.31×IC直接映像Cache的平均性能好一些。5.2Cache基本知識平均訪存時間＝命中時間＋不命中率×不命中開銷可以從三個方面改進Cache的性能：降低不命中率減少不命中開銷減少Cache命中時間下面介紹17種Cache優(yōu)化技術8種用于降低不命中率5種用于減少不命中開銷4種用于減少命中時間5.2.8改進Cache的性能三種類型的不命中(3C)強制性不命中(Compulsorymiss)當?shù)谝淮卧L問一個塊時，該塊不在Cache中，需從下一級存儲器中調(diào)入Cache，這就是強制性不命中。(冷啟動不命中，首次訪問不命中）容量不命中(Capacitymiss)如果程序執(zhí)行時所需的塊不能全部調(diào)入Cache中，則當某些塊被替換后，若又重新被訪問，就會發(fā)生不命中。這種不命中稱為容量不命中。5.3降低Cache不命中率5.3.1三種類型的不命中5.3降低Cache不命中率沖突不命中(Conflictmiss)在組相聯(lián)或直接映像Cache中，若太多的塊映像到同一組(塊)中，則會出現(xiàn)該組中某個塊被別的塊替換(即使別的組或塊有空閑位置)，然后又被重新訪問的情況。這就是發(fā)生了沖突不命中。

(碰撞不命中，干擾不命中)三種不命中所占的比例圖示I(絕對值)圖示Ⅱ(相對值)5.3降低Cache不命中率5.3降低Cache不命中率5.3降低Cache不命中率可以看出：相聯(lián)度越高，沖突不命中就越少；強制性不命中和容量不命中不受相聯(lián)度的影響；強制性不命中不受Cache容量的影響，但容量不命中卻隨著容量的增加而減少。5.3降低Cache不命中率減少三種不命中的方法強制性不命中：增加塊大小，預?。ū旧砗苌伲┤萘坎幻校涸黾尤萘?/p>

（抖動現(xiàn)象）沖突不命中：提高相聯(lián)度（理想情況：全相聯(lián)）許多降低不命中率的方法會增加命中時間或不命中開銷5.3降低Cache不命中率不命中率與塊大小的關系對于給定的Cache容量，當塊大小增加時，不命中率開始是下降，后來反而上升了。原因：一方面它減少了強制性不命中；另一方面，由于增加塊大小會減少Cache中塊的數(shù)目，所以有可能會增加沖突不命中。

Cache容量越大，使不命中率達到最低的塊大小就越大。增加塊大小會增加不命中開銷5.3.2增加Cache塊大小5.3降低Cache不命中率不命中率隨塊大小變化的曲線

5.3降低Cache不命中率各種塊大小情況下Cache的不命中率

塊大?。ㄗ止?jié)）Cache容量（字節(jié)）1K4K16K64K256K1615.05%8.57%3.94%2.04%1.09%3213.34%

7.24%2.87%1.35%0.70%6413.76%7.00%

2.64%

1.06%0.51%12816.64%7.78%2.77%1.02%

0.49%

25622.01%9.51%3.29%1.15%0.49%5.3降低Cache不命中率最直接的方法是增加Cache的容量缺點:增加成本可能增加命中時間這種方法在片外Cache中用得比較多

5.3.3增加Cache的容量5.3降低Cache不命中率采用相聯(lián)度超過8的方案的實際意義不大。2:1Cache經(jīng)驗規(guī)則

容量為N的直接映像Cache的不命中率和容量為N/2的兩路組相聯(lián)Cache的不命中率差不多相同。提高相聯(lián)度是以增加命中時間為代價。5.3.4提高相聯(lián)度5.3降低Cache不命中率多路組相聯(lián)的低不命中率和直接映像的命中速度偽相聯(lián)Cache的優(yōu)點命中時間小不命中率低5.3.5偽相聯(lián)Cache(列相聯(lián)Cache)優(yōu)點缺點直接映像組相聯(lián)命中時間小命中時間大不命中率高不命中率低基本思想及工作原理（動畫演示）在邏輯上把直接映像Cache的空間上下平分為兩個區(qū)。對于任何一次訪問，偽相聯(lián)Cache先按直接映像Cache的方式去處理。若命中，則其訪問過程與直接映像Cache的情況一樣。若不命中，則再到另一區(qū)相應的位置去查找。若找到，則發(fā)生了偽命中，否則就只好訪問下一級存儲器。5.3降低Cache不命中率

缺點：多種命中時間快速命中與慢速命中要保證絕大多數(shù)命中都是快速命中。不命中開銷5.3降低Cache不命中率指令和數(shù)據(jù)都可以預取預取內(nèi)容既可放入Cache，也可放在外緩沖器中。例如：指令流緩沖器指令預取通常由Cache之外的硬件完成預取效果Joppi的研究結果指令預取(4KB，直接映像Cache，塊大?。?6字節(jié))1個塊的指令流緩沖器：捕獲15％～25％的不命中4個塊的指令流緩沖器：捕獲50％16個塊的指令流緩沖器：捕獲72％5.3.6硬件預取

5.3降低Cache不命中率數(shù)據(jù)預取(4KB,直接映像Cache)1個數(shù)據(jù)流緩沖器：捕獲25％的不命中還可以采用多個數(shù)據(jù)流緩沖器Palacharla和Kessler的研究結果流緩沖器：既能預取指令又能預取數(shù)據(jù)對于兩個64KB四路組相聯(lián)Cache來說：8個流緩沖器能捕獲50％～70％的不命中預取應利用存儲器的空閑帶寬，不能影響對正常不命中的處理，否則可能會降低性能。5.3降低Cache不命中率

在編譯時加入預取指令，在數(shù)據(jù)被用到之前發(fā)出預取請求。按照預取數(shù)據(jù)所放的位置，可把預取分為兩種類型：寄存器預取：把數(shù)據(jù)取到寄存器中。Cache預?。褐粚?shù)據(jù)取到Cache中。按照預取的處理方式不同，可把預取分為：故障性預?。涸陬A取時，若出現(xiàn)虛地址故障或違反保護權限，就會發(fā)生異常。5.3.7編譯器控制的預取

5.3降低Cache不命中率非故障性預?。涸谟龅竭@種情況時則不會發(fā)生異常，因為這時它會放棄預取，轉變?yōu)榭詹僮鳌１竟?jié)假定Cache預取都是非故障性的，也叫做非綁定預取。在預取數(shù)據(jù)的同時，處理器應能繼續(xù)執(zhí)行。只有這樣，預取才有意義。非阻塞Cache(非鎖定Cache)

編譯器控制預取的目的使執(zhí)行指令和讀取數(shù)據(jù)能重疊執(zhí)行。循環(huán)是預取優(yōu)化的主要對象5.3降低Cache不命中率不命中開銷小時：循環(huán)體展開1～2次不命中開銷大時：循環(huán)體展開許多次每次預取需要花費一條指令的開銷保證這種開銷不超過預取所帶來的收益編譯器可以通過把重點放在那些可能會導致不命中的訪問上，使程序避免不必要的預取，從而較大程度地減少平均訪存時間。5.3降低Cache不命中率基本思想：通過對軟件進行優(yōu)化來降低不命中率。

（特色：無需對硬件做任何改動）程序代碼和數(shù)據(jù)重組可以重新組織程序而不影響程序的正確性把一個程序中的過程重新排序，就可能會減少沖突不命中，從而降低指令不命中率。McFarling研究了如何使用配置文件（profile）來進行這種優(yōu)化。把基本塊對齊，使得程序的入口點與Cache塊的5.3.8編譯器優(yōu)化

5.3降低Cache不命中率

起始位置對齊，就可以減少順序代碼執(zhí)行時所發(fā)生的Cache不命中的可能性。

（提高大Cache塊的效率）如果編譯器知道一個分支指令很可能會成功轉移，那么它就可以通過以下兩步來改善空間局部性：將轉移目標處的基本塊和緊跟著該分支指令后的基本塊進行對調(diào)；把該分支指令換為操作語義相反的分支指令。數(shù)據(jù)對存儲位置的限制更少，更便于調(diào)整順序。5.3降低Cache不命中率編譯優(yōu)化技術包括數(shù)組合并將本來相互獨立的多個數(shù)組合并成為一個復合數(shù)組，以提高訪問它們的局部性。內(nèi)外循環(huán)交換循環(huán)融合將若干個獨立的循環(huán)融合為單個的循環(huán)。這些循環(huán)訪問同樣的數(shù)組，對相同的數(shù)據(jù)作不同的運算。這樣能使得讀入Cache的數(shù)據(jù)在被替換出去之前，能得到反復的使用。分塊5.3降低Cache不命中率內(nèi)外循環(huán)交換舉例：

/*修改前*/for（j=0;j<100;j=j+1）

for（i=0;i<5000;i=i+1）

x[i][j]=2*x[i][j];/*修改后*/for（i=0;i<5000;i=i+1）

for（j=0;j<100;j=j+1）

x[i][j]=2*x[i][j];5.3降低Cache不命中率分塊把對數(shù)組的整行或整列訪問改為按塊進行。

/*修改前*/for（i=0;i<N;i=i+1）

for（j=0;j<N;j=j+1）{r=0;for（k=0;k<N;k=k+1）{r=r+y[i][k]*z[k][j];}x[i][j]=r;}計算過程（不命中次數(shù)：2N3＋N2）5.3降低Cache不命中率5.3降低Cache不命中率/*修改后*/

for（jj=0;jj<N;jj=jj+B）

for（kk=0;kk<N;kk=kk+B）

for（i=0;i<N;i=i+1）

for（j=jj;j<min（jj+B-1,N）;j=j+1）{r=0;for（k=kk;k<min（kk+B-1,N）;k=k+1）{r=r+y[i][k]*z[k][j];}x[i][j]=x[i][j]+r;}計算過程(不命中次數(shù)：2N3/B＋N2)5.3降低Cache不命中率5.3降低Cache不命中率一種能減少沖突不命中次數(shù)而又不影響時鐘頻率的方法?；舅枷朐贑ache和它從下一級存儲器調(diào)數(shù)據(jù)的通路之間設置一個全相聯(lián)的小Cache，稱為“犧牲”Cache（VictimCache）。用于存放被替換出去的塊(稱為犧牲者)，以備重用。工作過程5.3.9“犧牲”

Cache

5.3降低Cache不命中率作用對于減小沖突不命中很有效，特別是對于小容量的直接映像數(shù)據(jù)Cache，作用尤其明顯。例如項數(shù)為4的VictimCache:

能使4KB

Cache的沖突不命中減少20%～90%應把Cache做得更快？還是更大？答案：二者兼顧，再增加一級Cache第一級Cache(L1)小而快第二級Cache(L2)容量大性能分析平均訪存時間＝命中時間L1＋不命中率L1×不命中開銷L1不命中開銷L1

＝命中時間L2＋不命中率L2×不命中開銷L25.4.1采用兩級Cache5.4減少Cache不命中開銷5.4減少Cache不命中開銷平均訪存時間＝命中時間L1＋不命中率L1×

（命中時間L2＋不命中率L2×不命中開銷L2）局部不命中率與全局不命中率局部不命中率＝該級Cache的不命中次數(shù)/到達該級Cache的訪問次數(shù)例如：上述式子中的不命中率L2全局不命中率＝該級Cache的不命中次數(shù)/CPU發(fā)出的訪存的總次數(shù)5.4減少Cache不命中開銷全局不命中率L2＝不命中率L1×不命中率L2

評價第二級Cache時，應使用全局不命中率這個指標。它指出了在CPU發(fā)出的訪存中，究竟有多大比例是穿過各級Cache，最終到達存儲器的。采用兩級Cache時，每條指令的平均訪存停頓時間：每條指令的平均訪存停頓時間＝每條指令的平均不命中次數(shù)L1×命中時間L2＋每條指令的平均不命中次數(shù)L2×不命中開銷L25.4減少Cache不命中開銷例5.3考慮某一兩級Cache：第一級Cache為L1，第二級Cache為L2。（1）假設在1000次訪存中，L1的不命中是40次，L2的不命中是20次。求各種局部不命中率和全局不命中率。（2）假設L2的命中時間是10個時鐘周期，L2的不命中開銷是100時鐘周期，L1的命中時間是1個時鐘周期，平均每條指令訪存1.5次，不考慮寫操作的影響。問：平均訪存時間是多少？每條指令的平均停頓時間是多少個時鐘周期？

解(1)

第一級Cache的不命中率（全局和局部）是40/1000，即4%；第二級Cache的局部不命中率是20/40，即50%；第二級Cache的全局不命中率是20/1000，即2%。5.4減少Cache不命中開銷（2）平均訪存時間＝命中時間L1＋不命中率L1×（命中時間L2＋不命中率L2×不命中開銷L2）＝1＋4%×（10＋50%×100）＝1＋4%×60＝3.4個時鐘周期由于平均每條指令訪存1.5次，且每次訪存的平均停頓時間為：

3.4－1.0＝2.4所以：每條指令的平均停頓時間＝2.4×1.5＝3.6個時鐘周期5.4減少Cache不命中開銷對于第二級Cache，我們有以下結論：在第二級Cache比第一級Cache大得多的情況下，兩級Cache的全局不命中率和容量與第二級Cache相同的單級Cache的不命中率非常接近。局部不命中率不是衡量第二級Cache的一個好指標，因此，在評價第二級Cache時，應用全局不命中率這個指標。第二級Cache不會影響CPU的時鐘頻率，因此其設計有更大的考慮空間。兩個問題：5.4減少Cache不命中開銷它能否降低CPI中的平均訪存時間部分？它的成本是多少？第二級Cache的參數(shù)容量第二級Cache的容量一般比第一級的大許多。大容量意味著第二級Cache可能實際上沒有容量不命中，只剩下一些強制性不命中和沖突不命中。相聯(lián)度第二級Cache可采用較高的相聯(lián)度或偽相聯(lián)方法。5.4減少Cache不命中開銷

例5.4

給出有關第二級Cache的以下數(shù)據(jù)：（1）對于直接映像，命中時間L2

＝10個時鐘周期

（2）兩路組相聯(lián)使命中時間增加0.1個時鐘周期，即為10.1個時鐘周期。（3）對于直接映像，局部不命中率L2

＝25%

（4）對于兩路組相聯(lián)，局部不命中率L2＝20%

（5）不命中開銷L2

＝50個時鐘周期試問第二級Cache的相聯(lián)度對不命中開銷的影響如何？5.4減少Cache不命中開銷

解對一個直接映像的第二級Cache來說，第一級Cache的不命中開銷為：

不命中開銷直接映像，L1

＝10＋25%×50＝22.5個時鐘周期對于兩路組相聯(lián)第二級Cache來說，命中時間增加了10%（0.1）個時鐘周期，故第一級Cache的不命中開銷為：

不命中開銷兩路組相聯(lián)，L1

＝10.1＋20%×50＝20.1個時鐘周期把第二級Cache的命中時間取整，得10或11，則：不命中開銷兩路組相聯(lián)，L1

＝10＋20%×50＝20.0個時鐘周期不命中開銷兩路組相聯(lián)，L1

＝11＋20%×50＝21.0個時鐘周期故對于第二級Cache來說，兩路組相聯(lián)優(yōu)于直接映像。5.4減少Cache不命中開銷塊大小第二級Cache可采用較大的塊如64、128、256字節(jié)為減少平均訪存時間，可以讓容量較小的第一級Cache采用較小的塊，而讓容量較大的第二級Cache采用較大的塊。多級包容性需要考慮的另一個問題：第一級Cache中的數(shù)據(jù)是否總是同時存在于第二級Cache中。

Cache中的寫緩沖器導致對存儲器訪問的復雜化在讀不命中時，所讀單元的最新值有可能還在寫緩沖器中，尚未寫入主存。5.4.2讓讀不命中優(yōu)先于寫5.4減少Cache不命中開銷解決問題的方法(讀不命中的處理)推遲對讀不命中的處理（缺點：讀不命中的開銷增加）檢查寫緩沖器中的內(nèi)容在寫回法Cache中，也可采用寫緩沖器。5.4減少Cache不命中開銷5.4.3寫緩沖合并提高寫緩沖器的效率寫直達Cache依靠寫緩沖來減少對下一級存儲器寫操作的時間。如果寫緩沖器為空，就把數(shù)據(jù)和相應地址寫入該緩沖器。從CPU的角度來看，該寫操作就算是完成了。如果寫緩沖器中已經(jīng)有了待寫入的數(shù)據(jù)，就要把這次的寫入地址與寫緩沖器中已有的所有地址進行比較，看是否有匹配的項。如果有地址匹配而5.4減少Cache不命中開銷

對應的位置又是空閑的，就把這次要寫入的數(shù)據(jù)與該項合并。這就叫寫緩沖合并。如果寫緩沖器滿且又沒有能進行寫合并的項，就必須等待。

提高了寫緩沖器的空間利用率，而且還能減少因寫緩沖器滿而要進行的等待時間。5.4減少Cache不命中開銷5.4減少Cache不命中開銷請求字

從下一級存儲器調(diào)入Cache的塊中，只有一個字是立即需要的。這個字稱為請求字。應盡早把請求字發(fā)送給CPU盡早重啟動：調(diào)塊時，從塊的起始位置開始讀起。一旦請求字到達，就立即發(fā)送給CPU，讓CPU繼續(xù)執(zhí)行。請求字優(yōu)先：調(diào)塊時，從請求字所在的位置讀起。這樣，第一個讀出的字便是請求字。將之立即發(fā)送給CPU。5.4.4請求字處理技術5.4減少Cache不命中開銷這種技術在以下情況下效果不大：Cache塊較小下一條指令正好訪問同一Cache塊的另一部分5.4減少Cache不命中開銷非阻塞Cache：Cache不命中時仍允許CPU進行其他的命中訪問。即允許“不命中下命中”。進一步提高性能：“多重不命中下命中”

“不命中下不命中”（存儲器必須能夠處理多個不命中）可以同時處理的不命中次數(shù)越多，所能帶來的性能上的提高就越大。（不命中次數(shù)越多越好？）5.4.5非阻塞Cache技術5.4減少Cache不命中開銷模擬研究數(shù)據(jù)Cache的平均存儲器等待時間（以周期為單位）與阻塞Cache平均存儲器等待時間的比值測試條件：8K直接映像Cache，塊大小為32字節(jié)測試程序：SPEC92（14個浮點程序，4個整數(shù)程序）結果表明在重疊不命中個數(shù)為1、2和64的情況下浮點程序的平均比值分別為：76%、51%和39%整數(shù)程序的平均比值則分別為：81%、78%和78%對于整數(shù)程序來說，重疊次數(shù)對性能提高影響不大，簡單的“一次不命中下命中”就幾乎可以得到所有的好處。

命中時間直接影響到處理器的時鐘頻率。在當今的許多計算機中，往往是Cache的訪問時間限制了處理器的時鐘頻率。5.5減少命中時間5.5.1容量小、結構簡單的Cache硬件越簡單，速度就越快；應使Cache足夠小，以便可以與CPU一起放在同一塊芯片上。5.5減少命中時間

某些設計采用了一種折衷方案：

把Cache的標識放在片內(nèi)，而把Cache的數(shù)據(jù)存儲器放在片外。5.5.2虛擬Cache物理Cache使用物理地址進行訪問的傳統(tǒng)Cache。標識存儲器中存放的是物理地址，進行地址檢測也是用物理地址。5.5減少命中時間缺點：地址轉換和訪問Cache串行進行，訪問速度很慢。物理Cache存儲系統(tǒng)5.5減少命中時間虛擬Cache可以直接用虛擬地址進行訪問的Cache。標識存儲器中存放的是虛擬地址，進行地址檢測用的也是虛擬地址。優(yōu)點：在命中時不需要地址轉換，省去了地址轉換的時間。即使不命中，地址轉換和訪問Cache也是并行進行的，其速度比物理Cache快很多。

5.5減少命中時間并非都采用虛擬Cache(為什么?)虛擬Cache的清空問題解決方法：在地址標識中增加PID字段

(進程標識符)三種情況下不命中率的比較單進程，PIDs，清空PIDs與單進程相比：＋0.3％～＋0.6％PIDs與清空相比：－0.6％～－4.3%同義和別名解決方法：反別名法、頁著色5.5減少命中時間5.5減少命中時間虛擬索引＋物理標識優(yōu)點：兼得虛擬Cache和物理Cache的好處局限性：Cache容量受到限制

(頁內(nèi)位移)Cache容量≤頁大小×相聯(lián)度舉例：IBM3033的Cache頁大?。?KB相聯(lián)度＝16

頁地址

地址標識頁內(nèi)位移索引塊內(nèi)位移31121105.5減少命中時間Cache容量＝16×4KB＝64KB另一種方法：硬件散列變換5.5.3Cache訪問流水化對第一級Cache的訪問按流水方式組織訪問Cache需要多個時鐘周期才可以完成例如Pentium訪問指令Cache需要一個時鐘周期PentiumPro到PentiumⅢ需要兩個時鐘周期Pentium4則需要4個時鐘周期5.5減少命中時間開發(fā)指令級并行性所遇到的一個挑戰(zhàn)是：當要每個時鐘周期流出超過4條指令時，要提供足夠多條彼此互不相關的指令是很困難的。一個解決方法：采用蹤跡Cache存放CPU所執(zhí)行的動態(tài)指令序列包含了由分支預測展開的指令，該分支預測是否正確需要在取到該指令時進行確認。5.5.4蹤跡Cache5.5減少命中時間優(yōu)缺點地址映像機制復雜，相同的指令序列有可能被當作條件分支的不同選擇而重復存放,能夠提高指令Cache的空間利用率。5.5.5Cache優(yōu)化技術總結“＋”號：表示改進了相應指標?！埃碧枺罕硎舅乖撝笜俗儾??？崭駲冢罕硎舅鼘υ撝笜藷o影響。復雜性：0表示最容易，3表示最復雜。優(yōu)化技術不命中率不命中開銷命中時間硬件復雜度說明增加塊大小+

0實現(xiàn)容易；Pentium4的第二級Cache采用了128字節(jié)的塊增加Cache容量+1被廣泛采用，特別是第二級Cache提高相聯(lián)度+

1被廣泛采用犧牲Cache

+2AMDAthlon采用了8個項的VictimCache偽相聯(lián)Cache+2MIPSR10000的第二級Cache采用硬件預取指令和數(shù)據(jù)+2～3許多機器預取指令，UltraSPARCⅢ預取數(shù)據(jù)Cache優(yōu)化技術總結

優(yōu)化技術不命中率不命中開銷命中時間硬件復雜度說明編譯器控制的預取+

3需同時采用非阻塞Cache；有幾種微處理器提供了對這種預取的支持用編譯技術減少Cache不命中次數(shù)+0向軟件提出了新要求；有些機器提供了編譯器選項使讀不命中優(yōu)先于寫

+

1在單處理機上實現(xiàn)容易，被廣泛采用寫緩沖歸并+1與寫直達合用，廣泛應用，例如21164，UltraSPARCⅢ盡早重啟動和關鍵字優(yōu)先+2被廣泛采用非阻塞Cache

+3在支持亂序執(zhí)行的CPU中使用優(yōu)化技術不命中率不命中開銷命中時間硬件復雜度說明兩級Cache

+2硬件代價大；兩級Cache的塊大小不同時實現(xiàn)困難；被廣泛采用容量小且結構簡單的Cache

+0實現(xiàn)容易，被廣泛采用對Cache進行索引時不必進行地址變換

+2對于小容量Cache來說實現(xiàn)容易，已被Alpha21164和UltraSPARCⅢ采用流水化Cache訪問

+1被廣泛采用TraceCache+3Pentium4采用主存的主要性能指標：延遲和帶寬以往：Cache主要關心延遲，I/O主要關心帶寬?，F(xiàn)在：Cache關心兩者并行主存系統(tǒng)是在一個訪存周期內(nèi)能并行訪問多個存儲字的存儲器。能有效地提高存儲器的帶寬。5.6并行主存系統(tǒng)5.6并行主存系統(tǒng)一個單體單字寬的存儲器字長與CPU的字長相同。每一次只能訪問一個存儲字。假設該存儲器的訪問周期是TM，字長為W位，則其帶寬為：

普通存儲器5.6并行主存系統(tǒng)在相同的器件條件（即TM相同）下，可以采用兩種并行存儲器結構來提高主存的帶寬：單體多字存儲器多體交叉存儲器

5.6并行主存系統(tǒng)一個單體m字（這里m=4）存儲器

動畫5.6.1單體多字存儲器5.6并行主存系統(tǒng)存儲器能夠每個存儲周期讀出m個CPU字。因此其最大帶寬提高到原來的m倍。單體多字存儲器的實際帶寬比最大帶寬小優(yōu)缺點優(yōu)點：實現(xiàn)簡單缺點：訪存效率不高

5.6并行主存系統(tǒng)原因：如果一次讀取的m個指令字中有分支指令，而且分支成功，那么該分支指令之后的指令是無用的。一次取出的m個數(shù)據(jù)不一定都是有用的。另一方面，當前執(zhí)行指令所需要的多個操作數(shù)也不一定正好都存放在同一個長存儲字中。寫入有可能變得復雜。當要讀出的數(shù)據(jù)字和要寫入的數(shù)據(jù)字處于同一個長存儲字內(nèi)時，讀和寫的操作就無法在同一個存儲周期內(nèi)完成。5.6并行主存系統(tǒng)多體交叉存儲器：由多個單字存儲體構成，每個體都有自己的地址寄存器以及地址譯碼和讀/寫驅動等電路。問題：對多體存儲器如何進行編址？存儲器是按順序線性編址的。如何在二維矩陣和線性地址之間建立對應關系？兩種編址方法高位交叉編址低位交叉編址（有效地解決訪問沖突問題）5.6.2多體交叉存儲器5.6并行主存系統(tǒng)多體（m=4）交叉存儲器5.6并行主存系統(tǒng)高位交叉編址對存儲單元矩陣按列優(yōu)先的方式進行編址特點：同一個體中的高log2m位都是相同的（體號）

處于第i行第j列的單元，即體號為j、體內(nèi)地址為i的單元，其線性地址為：

A＝j×n＋i其中：j＝０，1，2，…，m－1i＝０，1，2，…，n－1一個單元的線性地址為A，則其體號j和體內(nèi)地址i為：

i＝Amodn5.6并行主存系統(tǒng)5.6并行主存系統(tǒng)把A表示為二進制數(shù)，則其高log2m位就是體號，而剩下的部分就是體內(nèi)地址。

低位交叉編址

對存儲單元矩陣按行優(yōu)先進行編址特點：同一個體中的低log2m位都是相同的（體號）5.6并行主存系統(tǒng)處于第i行第j列的單元，即體號為j、體內(nèi)地址為i的單元，其線性地址為：

A＝i×m＋j

其中：i＝０，1，2，…，n－1j＝０，1，2，…，m－15.6并行主存系統(tǒng)一個單元的線性地址為A，則其體號j和體內(nèi)地址i為：

j＝Amodm把A表示為二進制數(shù)，則其低log2m位就是體號，而剩下的部分就是體內(nèi)地址。

例：采用低位交叉編址的存儲器由8個存儲體構成、總容量為64。格子中的編號為線性地址。

5.6并行主存系統(tǒng)為了提高主存的帶寬，需要多個或所有存儲體能并行工作。

在每一個存儲周期內(nèi)，分時啟動m個存儲體。如果每個存儲體的訪問周期是TM，則各存儲體的啟動間隔為：

t=TM/m。5.6并行主存系統(tǒng)增加m的值就能夠提高主存儲器的帶寬。但是，由于存在訪問沖突，實際加速比小于m。通過一個模型分析并行主存系統(tǒng)的實際帶寬一個由m個獨立分體組成的主存系統(tǒng)CPU發(fā)出的一串地址為A1，A2，…，Aq的訪存申請隊列存儲控制器掃描這個隊列，并截取從頭起的A1，A2，…，Ak序列作為申請序列。申請序列是滿足以下條件的最長序列：k個地址所訪問的存儲器單元都處在不同的分體中。5.6并行主存系統(tǒng)A1～Ak不一定是順序地址，只要它們之間不出現(xiàn)分體沖突。k越接近于m，系統(tǒng)的效率就越高。設P(k)表示申請序列長度為k的概率，用B表示k的平均值，則其中：k=1，2，…，m

每個主存周期所能訪問到的字數(shù)的平均值，正比于主存實際帶寬。5.6并行主存系統(tǒng)P(k)與具體程序的運行狀況密切相關。如果訪存申請隊列都是指令的話，那么影響最大的是轉移概率λ。轉移概率λ：給定指令的下條指令地址為非順序地址的概率。當k＝1時，所表示的情況是：第一條就是轉移指令且轉移成功。

P（1）＝λ＝（1－λ）0·λ當k＝2時，所表示的情況是：第一條指令沒有轉移（其概率為1－λ），第二條是轉移指令且轉移成功。所以有：

P（2）＝（1－λ）1·λ5.6并行主存系統(tǒng)同理，P（3）＝（1－λ）2·λ依此類推，P（k）＝（1－λ）k－1·λ

其中：1≤k＜m如果前m－1條指令均不轉移，則不管第m條指令是否轉移，k都等于m，因此有：

P（m）＝（1－λ）m－1

5.6并行主存系統(tǒng)m等于4、8、16時，B與λ的關系曲線

5.6并行主存系統(tǒng)對于數(shù)據(jù)來說，由于其順序性差，m值的增大給B帶來的好處就更差一些。若機器主要是運行標量運算的程序，一般取m≤8。如果是向量處理機，其m值可以取大些。單純靠增大m來提高并行主存系統(tǒng)的帶寬是有限的，而且性能價格比還會隨m的增大而下降。原因：程序的轉移概率不會很低數(shù)據(jù)分布的離散性較大5.6并行主存系統(tǒng)5.6.3避免存儲體沖突體沖突：兩個請求要訪問同一個體。減少體沖突次數(shù)的一種方法：采用許多體例如，NECSX/3最多可使用128個體

5.6并行主存系統(tǒng)

這種方法存在問題：假如我們有128個存儲體，按字交叉方式工作，并執(zhí)行以下程序：

intx[256][512]；

for（j=0；j<512；j=j+1）

for（i=0；i<256；i=i+1）

x[i][j]=2*x[i][j]；

因為512是128的整數(shù)倍，同一列中的所有元素都在同一個體內(nèi)，無論CPU或存儲系統(tǒng)多么高級，該程序都會在數(shù)據(jù)Cache不命中時暫停。5.6并行主存系統(tǒng)解決體沖突的方法軟件方法(編譯器)循環(huán)交換優(yōu)化擴展數(shù)組的大小，使之不是2的冪。硬件方法使體數(shù)為素數(shù)體內(nèi)地址＝地址Amod(存儲體中的字數(shù))

可以直接截取舉例體內(nèi)地址存儲體順序交叉取模交叉012345順序交叉和取模交叉的地址映像舉例670120120120168345678910111213142122231516171819209