CHAP5-存儲層次.ppt

1、5.2Cache基本知識,5.3 降低Cache失效率的方法,5.4減少Cache失效開銷,5.1存儲器的層次結(jié)構(gòu),5.5減少命中時間,5.6主存,5.7虛擬存儲器,5.8進程保護和虛存實例,5.9Alpha AXP 21064存儲層次,第五章 存儲層次,5.1.1 從單級存儲器到多級存儲器,1. 從用戶的角度來看，存儲器的三個主要指標(biāo)是： 容量，速度，價格(每位價格) 2. 人們對這三個指標(biāo)的期望 3. 這三個指標(biāo)相互矛盾 4. 解決方法 采用多種存儲器技術(shù)，構(gòu)成存儲層次。 演示 演示 (局部性原理),5.1 存儲器的層次結(jié)構(gòu),第五章 存儲層次,5.1.2 存儲層次的性能參數(shù),C，H，TA

2、假設(shè)：S 容量 TA 訪問時間 C 每位價格 下面僅考慮由M1和M2構(gòu)成的兩級存儲層次： M1的參數(shù)：S1，TA1，C1 M2的參數(shù)：S2，TA2，C2,1. 每位價格C C ,C1S1C2S2,S1S2,5.1 存儲器的層次結(jié)構(gòu),2. 命中率 H 和失效率 F HN1/(N1N2) N1 訪問M1的次數(shù) N2 訪問M2的次數(shù) 失效率 F1H,5.1 存儲器的層次結(jié)構(gòu),3. 平均訪問時間 TA TATA1(1H )TM 或 TATA1F TM TA1 命中時間 TM 失效開銷,5.1.3 “Cache主存”和“主存輔存”層次,1. 從主存的角度來看 “Cache主存”層次：彌補主存速度的不足

3、“主存輔存”層次： 彌補主存容量的不足,2. “Cache主存”層次 主存與CPU的速度差距,5.1 存儲器的層次結(jié)構(gòu), “Cache - 主存”層次,3. “主存輔存”層次,存儲層次,CPU對第二級的訪問方式,比較項目,目的,存儲管理實現(xiàn),訪問速度的比值(第一級和第二級),典型的塊(頁)大小,失效時CPU是否切換,“Cache 主存”層次,“主存輔存”層次,為了彌補主存速度的不足,為了彌補主存容量的不足,主要由專用硬件實現(xiàn),主要由軟件實現(xiàn),幾比一,幾百比一,幾十個字節(jié),幾百到幾千個字節(jié),可直接訪問,均通過第一級,不切換,切換到其他進程,“Cache主存”與“主存輔存”層次的區(qū)別,5.1 存儲

4、器的層次結(jié)構(gòu),5.1.4 存儲層次的四個問題,當(dāng)把一個塊調(diào)入高一層(靠近CPU)存儲器時，可以放在哪些位置上? (映象規(guī)則),當(dāng)所要訪問的塊在高一層存儲器中時，如何找到該塊? (查找算法),3. 當(dāng)發(fā)生失效時，應(yīng)替換哪一塊？ (替換算法),4. 當(dāng)進行寫訪問時，應(yīng)進行哪些操作? (寫策略),1.,2.,5.1 存儲器的層次結(jié)構(gòu),5.2 Cache基本知識,1存儲空間分割與地址計算,5.2.1 映象規(guī)則,1. 全相聯(lián)映象 全相聯(lián)：主存中的任一塊可以被放置到 Cache中的任意一個位置。 舉例 對比： 閱覽室位置 隨便坐 特點： 空間利用率最高，沖突概率最低， 實現(xiàn)最復(fù)雜。,2Cache和主存分塊

5、,5.2 Cache 基本知識,2. 直接映象, 直接映象：主存中的每一塊只能被放置到 Cache中唯一的一個位置。 舉例 (循環(huán)分配) 對比：閱覽室位置 只有一個位置可 以坐 特點：空間利用率最低，沖突概率最高， 實現(xiàn)最簡單。 對于主存的第i 塊，若它映象到Cache的第 j 塊，則: ji mod (M ) （M為Cache的塊數(shù)）,5.2 Cache 基本知識, 組相聯(lián)：主存中的每一塊可以被放置到Cache 中唯一的一個組中的任何一個位置。 舉例 組相聯(lián)是直接映象和全相聯(lián)的一種折衷, 設(shè)M2m，則當(dāng)表示為二進制數(shù)時，j 實際 上就是i 的低m 位：,3. 組相聯(lián)映象,m位,j,i：,5.

6、2 Cache 基本知識, 上述的j 和k 通常稱為索引, 組的選擇常采用位選擇算法 若主存第i 塊映象到第k 組，則: ki mod（G） （G為Cache的組數(shù)） 設(shè)G2g，則當(dāng)表示為二進制數(shù)時，k 實 際上就是i 的低 g 位：,g 位,k,i：,5.2 Cache 基本知識, 絕大多數(shù)計算機的Cache: n 4 想一想：相聯(lián)度一定是越大越好？, n 路組相聯(lián)：每組中有n 個塊(nM/G ) n 稱為相聯(lián)度。 相聯(lián)度越高，Cache空間的利用率就越高， 塊沖突概率就越低，失效率也就越低。,全相聯(lián),直接映象,組相聯(lián),n (路數(shù)),G (組數(shù)),M,M,1,1,1nM,1GM,5.2 Ca

7、che 基本知識,5.2.2 查找方法,1. 如何確定Cache中是否有所要訪問的塊？ 若有的話如何確定其位置？ 答案,5.2 Cache 基本知識, 目錄表的結(jié)構(gòu), 只需查找候選位置所對應(yīng)的目錄表項, 并行查找與順序查找, 提高性能的重要思想：主候選位置(MRU塊) 前瞻執(zhí)行, 并行查找的實現(xiàn)方法：,5.2 Cache 基本知識,舉例： 路組相聯(lián)并行標(biāo)識比較 （比較器的個數(shù)及位數(shù)）,相聯(lián)存儲器 單體多字存儲器比較器, 路組相聯(lián)Cache的查找過程, 直接映象Cache的查找過程,5.2.3 替換算法,所要解決的問題：當(dāng)新調(diào)入一塊，而Cache又已被占滿時，替換哪一塊？,2. FIFO 3.

8、LRU 優(yōu)點：失效率低 LRU和隨機法的失效率的比較,1. 隨機法 優(yōu)點：實現(xiàn)簡單,5.2 Cache 基本知識,5.2.4 寫策略,1. “寫”操作所占的比例 Load指令：26 Store指令：9 “寫”在所有訪存操作中所占的比例： 9/(100269)7 “寫”在訪問Cache操作中所占的比例： 9/(269)25,3“寫”訪問有可能導(dǎo)致Cache和主存內(nèi)容的不一致,2. “寫”操作必須在確認(rèn)是命中后才可進行,5.2 Cache 基本知識,4兩種寫策略 寫直達(dá)法 執(zhí)行“寫”操作時，不僅寫入Cache，而且 也寫入下一級存儲器。 寫回法 執(zhí)行“寫”操作時，只寫入Cache。僅當(dāng) Cache

9、中相應(yīng)的塊被替換時，才寫回主存。 (設(shè)置“污染位”),5.2 Cache 基本知識,5兩種寫策略的比較 寫回法的優(yōu)點：速度快，所使用的存儲器頻 帶較低； 寫直達(dá)法的優(yōu)點：易于實現(xiàn)，一致性好。,6. 寫緩沖器,8. 寫策略與調(diào)塊 寫回法 按寫分配 寫直達(dá)法 不按寫分配,7. “寫”操作時的調(diào)塊 按寫分配(寫時取) 寫失效時，先把所寫單元所在的塊調(diào)入 Cache，再行寫入。 不按寫分配(繞寫法) 寫失效時，直接寫入下一級存儲器而不調(diào)塊。,5.2 Cache 基本知識,5.2.5 Cache的結(jié)構(gòu),例子：DEC的Alpha AXP21064中的內(nèi)部數(shù)據(jù) Cache。,1. 簡介 容量：8KB 塊大小

10、：32B 塊數(shù)：256 采用不按寫分配 映象方法：直接映象 “寫”策略：寫直達(dá) 寫緩沖器大?。?個塊,5.2 Cache 基本知識,2. 結(jié)構(gòu)圖,3. 工作過程 “讀”訪問命中, “寫”訪問命中,5. 混合Cache與分離Cache (1) 優(yōu)缺點 (2) 失效率的比較,5.2 Cache 基本知識, 失效情況下的操作,16 KB,容量,1 KB,2 KB,4 KB,8 KB,32 KB,指令 Cache,3.06%,失 效 率 的 比 較,64 KB,128 KB,數(shù)據(jù) Cache,混合 Cache,2.26%,1.78%,1.10%,0.64%,0.39%,0.15%,0.02%,24.6

11、1%,20.57%,15.94%,10.19%,6.47%,4.82%,3.77%,2.88%,13.34%,9.78%,7.24%,4.57%,2.87%,1.99%,1.36%,0.95%,(3) 分離Cache平均失效率的計算：,訪問指令Cache的百分比指令Cache的失效率 訪問數(shù)據(jù)Cache的百分比數(shù)據(jù)Cache的失效率,5.2.6 Cache性能分析,2. 平均訪問時間 平均訪問時間命中時間失效率失效開銷,1. 失效率,例5.1 假設(shè)Cache的命中時間為1個時鐘周期，失效開銷為50 個時鐘周期，在混合Cache中一次load或store操作訪問Cache的命中時間都要增加一個時

12、鐘周期(因為混合Cache只有一個端口，無法同時滿足兩個請求。按照前一章中有關(guān)流水線的術(shù)語，混合Cache會導(dǎo)致結(jié)構(gòu)沖突)，根據(jù)表54所列的失效率，試問指令Cache和數(shù)據(jù)Cache容量均 為16KB的分離Cache和容量為32KB的混合Cache相,5.2 Cache 基本知識,解： 如前所述，約75%的訪存為取指令。因此，分離Cache的總體失效率為： (75%0.64%)(25%6.47%)2.10% 根據(jù)表54，容量為32KB的混合Cache的失效率略低一些，只有1.99%.,比，哪種Cache的失效率更低？又假設(shè)采用寫直達(dá)策略，且有一個寫緩沖器，并且忽略寫緩沖器引起的等待。請問上述兩

13、種情況下平均訪存時間各是多少？,5.2 Cache 基本知識,平均訪存時間公式可以分為指令訪問和數(shù)據(jù)訪問兩部分： 平均訪存時間指令所占的百分比 (指令命中時間指令失效率失效開銷) 數(shù)據(jù)所占的百分比 (數(shù)據(jù)命中時間數(shù)據(jù)失效率失效開銷) 所以，兩種結(jié)構(gòu)的平均訪存時間分別為： 平均訪存時間分離75%(10.64%50) 25%(16.47%50) (75%1.32)(25%4.325) 0.9901.0592.05,5.2 Cache 基本知識,平均訪存時間混合75%(11.99%50) 25%(111.99%50) (75%1.995)(25%2.995) 1.4960.7492.24,3. 程序

14、執(zhí)行時間 CPU時間(CPU執(zhí)行周期數(shù)存儲器停頓周期數(shù)) 時鐘周期時間 其中， 存儲器停頓周期數(shù)訪存次數(shù)失效率 失效開銷,5.2 Cache 基本知識,CPU時間ICCPIexe每條指令的平均存儲 器停頓周期數(shù)時鐘周期時間,CPU時間ICCPIexe訪存次數(shù)/指令數(shù) 失效率失效開銷時鐘周期時間,5.2 Cache 基本知識,例5.2 我們用一個和Alpha AXP類似的機器作為第一個例子。假設(shè)Cache失效開銷為50個時鐘周期，當(dāng)不考慮存儲器停頓時，所有指令的執(zhí)行時間都是2.0個時鐘周期， Cache的失效率為2%，平均每條指令訪存1.33次。試分析Cache對性能的影響。,考慮Cache的失

15、效后，性能為： CPU 時間有cacheIC(2.0(1.332%50) 時鐘周期時間 IC3.33時鐘周期時間,CPU 時間IC(CPIexe ) 時鐘周期時間,存儲器停頓周期數(shù),指令數(shù),解：,5.2 Cache 基本知識,實際CPI ：3.33 3.33/2.0 = 1.67(倍),CPU時間也增加為原來的1.67倍。但若不采用Cache,則： CPI2.0+501.3368.5,5.2 Cache 基本知識,考慮兩種不同組織結(jié)構(gòu)的Cache：直接映象Cache和兩路組相聯(lián)Cache，試問它們對CPU的性能有何影響？先求平均訪存時間，然后再計算CPU性能。分析時請用以下假設(shè)： 理想Cach

16、e(命中率為100)情況下的CPI 為2.0，時鐘周期為2ns，平均每條指令 訪存1.3次。 兩種Cache容量均為64KB，塊大小都是32 字節(jié)。,例5.3,5.2 Cache 基本知識, 圖5.10說明，在組相聯(lián)Cache中，我們必須增 加一個多路選擇器，用于根據(jù)標(biāo)識匹配結(jié)果 從相應(yīng)組的塊中選擇所需的數(shù)據(jù)。因為CPU 的速度直接與Cache命中的速度緊密相關(guān),所 以對于組相聯(lián)Cache，由于多路選擇器的存 在而使CPU的時鐘周期增加到原來的1.10倍。 這兩種結(jié)構(gòu)Cache的失效開銷都是70ns。在 實際應(yīng)用中，應(yīng)取整為整數(shù)個時鐘周期。 命中時間為1個時鐘周期，64KB直接映象 Cache

17、的失效率為1.4%，相同容量的兩路組 相聯(lián)Cache的失效率為1.0%。,5.2 Cache 基本知識,由:平均訪存時間命中時間失效率失效開銷 得:平均訪存時間1路2.0(0.01470)2.98ns平均訪存時間2路2.01.10(0.01070)2.90ns,由:CPU 時間IC(CPIexe每條指令的平均存儲器 停頓周期數(shù))時鐘周期時間 IC (CPIexe時鐘周期時間 每條指令的平均存儲器停頓時間),解：,5.2 Cache 基本知識,CPU時間1路IC(2.02(1.30.01470) 5.27IC CPU時間2路IC(2.021.10 (1.30.01070) 5.31IC,得：,5

18、.31IC,CPU時間1路, 1.01,5.27IC,CPU時間2路,5.2 Cache 基本知識,平均訪存時間命中時間失效率失效開銷 可以從三個方面改進Cache的性能： (1) 降低失效率 (2) 減少失效開銷(3) 減少Cache命中時間 下面介紹15種Cache優(yōu)化技術(shù),5.2.7 改進Cache性能,5.2 Cache 基本知識,(1) 強制性失效(Compulsory miss) 當(dāng)?shù)谝淮卧L問一個塊時，該塊不在 Cache中，需從下一級存儲器中調(diào)入Cache， 這就是強制性失效。 (冷啟動失效，首次訪問失效。) (2) 容量失效(Capacity miss ) 如果程序執(zhí)行時所需的

19、塊不能全部調(diào) 入Cache中，則當(dāng)某些塊被替換后，若又,5.3 降低Cache失效率的方法,1. 三種失效(3C),第五章 存儲層次,重新被訪問，就會發(fā)生失效。這種失效稱 為容量失效。,(3) 沖突失效(Conflict miss) 在組相聯(lián)或直接映象Cache中，若太多 的塊映象到同一組(塊)中，則會出現(xiàn)該組 中某個塊被別的塊替換(即使別的組或塊有 空閑位置)，然后又被重新訪問的情況。這 就是發(fā)生了沖突失效。 (碰撞失效，干擾失效),5.3 降低Cache 失效率的方法,2. 三種失效所占的比例,(SPEC92)表5.5,5.3 降低Cache 失效率的方法,圖示I(絕對值),圖示(相對值)

20、,可以看出： (1) 相聯(lián)度越高，沖突失效就越少； (2) 強制性失效和容量失效不受相聯(lián)度的影響； (3) 強制性失效不受Cache容量的影響，但容 量失效卻隨著容量的增加而減少； (4) 表中的數(shù)據(jù)符合2:1的Cache經(jīng)驗規(guī)則，即 大小為N 的直接映象Cache的失效率約等于 大小為N/2 的兩路組相聯(lián)Cache的失效率。,強制性失效：增加塊大小，預(yù)取 (本身很少) 容量失效：增加容量 (抖動現(xiàn)象) 沖突失效：提高相聯(lián)度 (理想情況：全相聯(lián)),3. 減少三種失效的方法,4. 許多降低失效率的方法會增加命中時間或 失效開銷,5.3 降低Cache 失效率的方法,5.3.1 增加Cache塊大

21、小,1. 失效率與塊大小的關(guān)系 (1) 對于給定的Cache容量，當(dāng)塊大小增加 失效率開始是下降，后來反而上升了； (2) Cache容量越大，使失效率達(dá)到最低的 塊大小就越大。,5.3 降低Cache 失效率的方法,2. 增加塊大小會增加失效開銷,3. 例題,例 5.4,假定存儲系統(tǒng)在延遲40個時鐘周期后，每2個時鐘周期能送出16個字節(jié)。即:經(jīng)過42個時鐘周期，它可提供16個字節(jié)；經(jīng)過44個時鐘周期，可提供32個字節(jié)；依此類推。試問對于表5-6中列出的各種容量的Cache，在塊大小分別為多少時，平均訪存時間最小？,解： 解題過程 1KB、4KB、16KB Cache: 塊大小32字節(jié) 64K

22、B、256KB Cache: 塊大小64字節(jié),5.3 降低Cache 失效率的方法,5.3.2 提高相聯(lián)度,1. 采用相聯(lián)度超過8的方法實際意義不大,2. 2:1 Cache經(jīng)驗規(guī)則 容量為N 的直接映象Cache 容量為N/2的兩路組相聯(lián)Cache,3. 提高相聯(lián)度是以增加命中時間為代價 例如： TTL或ECL板級Cache，兩路組相聯(lián)： 增加10 定制的CMOS Cache, 兩路組相聯(lián)： 增加2,5.3 降低Cache 失效率的方法,4. 例題,假定提高相聯(lián)度會按下列比例增大處理器時鐘周期： 時鐘周期2路 1.10時鐘周期1路 時鐘周期4路 1.12時鐘周期1路 時鐘周期8路 1.14時

23、鐘周期1路 假定命中時間為1個時鐘，直接映象情況下失效開銷為50個時鐘周期，而且假設(shè)不必將失效開銷取整。使用表55中的失效率，試問當(dāng)Cache為多大時，以下不等式成立？,例 5.5,5.3 降低Cache 失效率的方法,平均訪存時間8路 平均訪存時間4路 平均訪存時間4路 平均訪存時間2路 平均訪存時間2路 平均訪存時間1路,解：,在各種相聯(lián)度的情況下，平均訪存時間分別為： 平均訪存時間8路 = 命中時間8路 + 失效率8路 失效開銷8路 = 1.14失效率8路50 平均訪存時間4路 = 1.12 失效率4路50 平均訪存時間2路 = 1.10 失效率2路50 平均訪存時間1路 = 1.00

24、失效率1路50,5.3 降低Cache 失效率的方法,在每種情況下的失效開銷相同，都是50個時鐘周期。把相應(yīng)的失效率代入上式， 即可得平均訪存時間。 例如，1KB的直接映象Cache的平均訪存時間為： 平均訪存時間1路 1.00(0.13350) 7.65 容量為128KB的8路組相聯(lián)Cache的平均訪存時間為： 平均訪存時間8路 1.14(0.00650) 1.44,表5-8,5.3 降低Cache 失效率的方法,1. 基本思想 在Cache和它從下一級存儲器調(diào)數(shù)據(jù) 的通路之間設(shè)置一個全相聯(lián)的小Cache， 用于存放被替換出去的塊(稱為Victim)， 以備重用。 工作過程,5.3.3 Vi

25、ctim Cache,5.3 降低Cache 失效率的方法,對于減小沖突失效很有效，特別是對于小容量的直接映象數(shù)據(jù)Cache，作用尤其明顯。 例如，項數(shù)為4的Victim Cache: 使4KB Cache的沖突失效減少20%90%,2. 作用,5.3 降低Cache 失效率的方法,1. 直接映象 vs組相聯(lián),5.3.4 偽相聯(lián)Cache,2. 偽相聯(lián)Cache,優(yōu)點,缺點,直接映象,組相聯(lián),命中時間小,命中時間大,失效率高,失效率低,取直接映象及組相聯(lián)兩者的優(yōu)點： 命中時間小，失效率低,5.3 降低Cache 失效率的方法,(1) 基本思想及工作原理 (動畫演示) 在邏輯上把直接映象Cach

26、e的空間上下 平分為兩個區(qū)。對于任何一次訪問，偽相聯(lián) Cache先按直接映象Cache的方式去處理。若 命中，則其訪問過程與直接映象Cache的情 況一樣。若不命中，則再到另一區(qū)相應(yīng)的位 置去查找。若找到，則發(fā)生了偽命中，否則 就只好訪問下一級存儲器。,(2) 快速命中與慢速命中 要保證絕大多數(shù)命中都是快速命中。,5.3 降低Cache 失效率的方法,3. 例題,例5.6 假設(shè)當(dāng)在按直接映象找到的位置處沒有發(fā)現(xiàn)匹配、而在另一個位置才找到數(shù)據(jù)(偽命中)需要2個額外的周期。仍用上個例子中的數(shù)據(jù)，問：當(dāng)Cache容量分別為2KB和128KB時，直接映象、兩路組相聯(lián)和偽相聯(lián)這三種組織結(jié)構(gòu)中，哪一種速度

27、最快？,5.3 降低Cache 失效率的方法,首先考慮標(biāo)準(zhǔn)的平均訪存時間公式： 平均訪存時間偽相聯(lián) 命中時間偽相聯(lián)失效率偽相聯(lián)失效開銷偽相聯(lián) 由于： 失效率偽相聯(lián)失效率2路 命中時間偽相聯(lián)命中時間1路偽命中率偽相聯(lián)2； 偽命中率偽相聯(lián)命中率2路命中率1路 (1失效率2路)(1失效率1路) 失效率1路失效率2路,解：,5.3 降低Cache 失效率的方法,故： 平均訪存時間偽相聯(lián) 命中時間1路(失效率1路失效率2路)2 失效率2路失效開銷1路,將表55中的數(shù)據(jù)代入上面的公式，得： 平均訪存時間偽相聯(lián)，2KB 1(0.0980.076)2(0.07650) 4.844 平均訪存時間偽相聯(lián)，128K

28、B 1(0.0100.007)2(0.00750) 1.356,5.3 降低Cache 失效率的方法,根據(jù)上一個例子中的表58，對于2KB Cache，可得： 平均訪存時間1路 5.90 個時鐘 平均訪存時間2路 4.90 個時鐘 對于128KB的Cache有，可得： 平均訪存時間1路 1.50 個時鐘 平均訪存時間2路 1.45 個時鐘 可見，對于這兩種Cache容量，偽相聯(lián)Cache都是速度最快的。,缺點：多種命中時間,5.3 降低Cache 失效率的方法,5.3.5 硬件預(yù)取技術(shù),1. 指令和數(shù)據(jù)都可以預(yù)取,2. 預(yù)取內(nèi)容既可放入Cache，也可放在 外緩沖器中 例如：指令流緩沖器,3.

29、 預(yù)取效果 (1) Joppi的研究結(jié)果 指令預(yù)?。?4KB，直接映象Cache, 塊大小16字節(jié)),5.3 降低Cache 失效率的方法,1個塊的指令流緩沖器： 捕獲1525 的失效 4個塊的指令流緩沖器： 捕獲50 16個塊的指令流緩沖器：捕獲72, 數(shù)據(jù)預(yù)?。?4KB,直接映象Cache) 1個數(shù)據(jù)流緩沖器：捕獲25的失效 還可以采用多個數(shù)據(jù)流緩沖器,(2) Palacharla和Kessler的研究結(jié)果 流緩沖器：既能預(yù)取指令又能預(yù)取數(shù)據(jù) 對于兩個64KB四路組相聯(lián)Cache來說： 8個流緩沖器能捕獲5070的失效。,5.3 降低Cache 失效率的方法,4. 例題,例5.7 Alph

30、a AXP 21064采用指令預(yù)取技術(shù)，其實際失效率是多少？若不采用指令預(yù)取技術(shù)，AlphaAPX 21064的指令Cache必須為多大才能保持平均訪存時間不變？,解： 假設(shè)從預(yù)取緩沖器中找到所需指令需多花1個時鐘周期。 平均訪存時間預(yù)取 命中時間失效率預(yù)取命中率1 失效率(1預(yù)取命中率)失效開銷,5.3 降低Cache 失效率的方法,假設(shè)： 預(yù)取命中率25 命中時間1個時鐘周期 失效開銷50個時鐘周期 由表5.4可知，8KB指令Cache的失效率1.10 故平均訪存時間預(yù)取 1(1.10 %25 %1) (1.10 %(125 %)50) 10.002750.4125 1.415 由公式：

31、平均訪問時間命中時間失效率失效開銷,5.3 降低Cache 失效率的方法,可得相應(yīng)的失效率為： 失效率(平均訪問時間命中時間)/失效開銷 (1.4511)/500.83,8KB Cache,帶預(yù)取的8kB Cache,失效率,1.10,0.83,16KB Cache,0.64,5.3 降低Cache 失效率的方法,5.3.6 由編譯器控制的預(yù)取,1. 預(yù)取的類型 寄存器預(yù)取：把數(shù)據(jù)取到寄存器中 Cache預(yù)?。?只將數(shù)據(jù)取到Cache中 故障性預(yù)?。侯A(yù)取時，若出現(xiàn)虛地址故障 或違反訪問權(quán)限，就會發(fā)生異常。 非故障性預(yù)?。侯A(yù)取時，若出現(xiàn)虛地址故 障或違反訪問權(quán)限，并不會導(dǎo)致異常，只 是轉(zhuǎn)變?yōu)椤安?/p>

32、預(yù)取”。,由編譯器加入預(yù)取指令，在數(shù)據(jù)被用到之前發(fā)出預(yù)取請求。,5.3 降低Cache 失效率的方法,4. 例題,2. 在預(yù)取數(shù)據(jù)的同時，處理器應(yīng)能繼續(xù)執(zhí)行 只有這樣，預(yù)取才有意義。 非阻塞Cache (非鎖定Cache),3. 循環(huán)是預(yù)取優(yōu)化的主要對象 失效開銷小時：循環(huán)體展開12次 失效開銷大時：循環(huán)體展開許多次,5.3 降低Cache 失效率的方法,例 5.8 對于下面的程序，判斷哪些訪問可能會導(dǎo)致數(shù)據(jù)Cache失效。然后，加入預(yù)取指令以減少失效。最后，計算所執(zhí)行的預(yù)取指令的條數(shù)以及通過預(yù)取避免的失效次數(shù)。假定： (1) 我們用的是一個容量為8KB、塊大小為 16B的直接映象Cache，

33、它采用寫回法并 且按寫分配。 (2) a、b分別為3100(3行100列)和1013 的雙精度浮點數(shù)組，每個元素都是8個 字節(jié)。當(dāng)程序開始執(zhí)行時，這些數(shù)據(jù)都 不在Cache內(nèi)。,5.3 降低Cache 失效率的方法,for (i0 ; i 3 ; ii1 ) for (j0 ; j 100 ; jj1 ) aijbj0bj10;,解： (1) 計算過程 (2) 失效情況 總的失效次數(shù)251次 (3) 改進后的程序,5.3 降低Cache 失效率的方法,for (j0，j100；jj1) prefetch (bj70); /* 預(yù)取7次循環(huán)后所需的b(j ,0 ) */ prefetch (a0

34、j7); /* 預(yù)取7次循環(huán)后所需的a(0,j ) */ a0jbj 0 * b j10 for (i1; i 3; ii1) for (j0; j 100; jj1) prefetch(aij7); /* 預(yù)取7次循環(huán)后所需的a(i , j ) */ aijbj0 * bj10; ,5.3 降低Cache 失效率的方法,例 59 在以下條件下，計算例5.8中所節(jié)約的時間： (1) 忽略指令Cache失效，并假設(shè)數(shù)據(jù)Cache 無沖突失效和容量失效。 (2) 假設(shè)預(yù)取可以被重疊或與Cache失效重 疊執(zhí)行，從而能以最大的存儲帶寬傳送 數(shù)據(jù)。 (3) 不考慮Cache失效時，修改前的循環(huán)每7 個

35、時鐘周期循環(huán)一次。修改后的程序中，,失效情況 總的失效次數(shù)19次,5.3 降低Cache 失效率的方法,解： 修改前： 循環(huán)時間3007 2100 失效開銷2515012550/14650 21001255014650,第一個預(yù)取循環(huán)每9個時鐘周期循環(huán)一次， 而第二個預(yù)取循環(huán)每8個時鐘周期循環(huán)一 次(包括外層for循環(huán)的開銷)。(4) 一次失效需50個時鐘周期。,5.3 降低Cache 失效率的方法,修改后： 循環(huán)時間100920082500 失效時間1950950 25009503450 加速比14650/34504.2,5.3 降低Cache 失效率的方法,5.3.7 編譯器優(yōu)化,2KB

36、Cache: 降低50 8KB Cache：降低75%,1. 基本思想,在編譯時，對程序中的指令和數(shù)據(jù)進行重新組織，以降低Cache失效率。,2. McFaring 發(fā)現(xiàn)：通過對指令進行重新排序， 可有效地降低指令Cache的失效率。,5.3 降低Cache 失效率的方法,3. 數(shù)據(jù)對存儲位置的限制比指令的少，因此 更便于優(yōu)化。 通過把數(shù)據(jù)重新組織，使得在一塊數(shù) 據(jù)被從Cache替換出去之前，能最大限度 利用其中的數(shù)據(jù)(訪問次數(shù)最多) (1) 數(shù)組合并 舉例： /* 修改前 */ int val SIZE; int key SIZE;,5.3 降低Cache 失效率的方法,(2) 內(nèi)外循環(huán)交換

37、 舉例： /* 修改前 */ for (j0 ;j100 ;jj1) for (i0 ;i5000 ;ii1) xij2*xij;,/* 修改后 */ struct merge int val ; int key ; ; struct merge merged_arraysize;,5.3 降低Cache 失效率的方法,(3) 循環(huán)融合 舉例： /* 修改前 */ for (i0 ; iN ;ii1) for (j0 ; jN ; jj1) aij1/bij*cij;,/* 修改后 */ for (i0 ;i100 ;ii1) for (j0 ;j 000 ;jj1) xij2*xij;,5.

38、3 降低Cache 失效率的方法,/* 修改后 */ for (i0 ;i N ;ii1) for (j0 ;j N ;jj1) aij1/bij*cij; dijaijcij; ,for (i0 ;iN ;ii1) for (j0 ; jN ;jj1) dijaijcij;,(4)分塊 把對數(shù)組的整行或整列訪問改為按塊進行。,5.3 降低Cache 失效率的方法,舉例： /* 修改前 */ for (i0; i N; ii1) for (j0; j N; jj1) r0; for (k0; k N; kk1) rryik*zkj; xijr; ,計算過程 失效次數(shù)：2N3N2,5.3 降低C

39、ache 失效率的方法,/* 修改后 */ for (jj0; jj N; jjjj1) for (kk0; kk N; kkkk1) for (i0; i N; ii1) for (jjj; j min(jjB1,N); jj1) r0; for (kkk; k min(kkB1,N); kk1) rryik*zkj; xijxijr; ,計算過程 失效次數(shù)：2N3 /B N2,5.3 降低Cache 失效率的方法,5.4.1 讓讀失效優(yōu)先于寫,5.4 減少Cache失效開銷,1. Cache中的寫緩沖器導(dǎo)致對存儲器訪問的 復(fù)雜化,2. 解決問題的方法(讀失效的處理) 推遲對讀失效的處理 (

40、缺點：讀失效的開銷增加，如50) 檢查寫緩沖器中的內(nèi)容,3. 在寫回法Cache中，也可采用寫緩沖器,第五章 存儲層次,5.4.2 子塊放置技術(shù),1. 為減少標(biāo)識的位數(shù)，可采用增加塊大小的 方法，但這會增加失效開銷，故應(yīng)采用子 塊放置技術(shù)。,2. 子塊放置技術(shù)：把Cache塊進一步劃分為更 小的塊(子塊)，并給每個子塊賦予一位有 效位，用于指明該子塊中的數(shù)據(jù)是否有效。 Cache與下一級存儲器之間以子塊為單位傳 送數(shù)據(jù)。但標(biāo)識仍以塊為單位。,3. 舉例 (動畫演示),5.4 減少Cache 失效開銷,5.4.3 請求字處理技術(shù),1. 請求字 從下一級存儲器調(diào)入Cache的塊中，只有 一個字是立

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

42、多重失效下命中” “失效下失效” (存儲器必須能夠處理多個失效),3. 重疊失效個數(shù)對平均訪問時間的影響,5.4 減少Cache 失效開銷,非阻塞Cache平均存儲器等待時間 與阻塞Cache的比值,1,2,浮點程序,76,51,64,39,整數(shù)程序,81,78,78,重疊失效個數(shù),5.4 減少Cache 失效開銷,對于圖5.18所描述的Cache，在兩路組相聯(lián)和“一次失效下命中”這兩種措施中，哪一種對浮點程序更重要？對整數(shù)程序的情況如何？ 假設(shè)8KB數(shù)據(jù)Cache的平均失效率為： 對于浮點程序，直接映象Cache為11.4%，兩路組相聯(lián)Cache為10.7%； 對于整數(shù)程序，直接映象Cach

43、e為7.4%，兩路組相聯(lián)Cache為6.0%。并且假設(shè)平均存儲器等待時間是失效率和失效開銷的積，失效開銷為16個時鐘周期。,例 5.11,5.4 減少Cache 失效開銷,對于浮點程序，平均存儲器等待時間為： 失效率直接映象失效開銷11.4%161.82 失效率兩路組相聯(lián)失效開銷10.7%161.71 1.71/1.820.94,對于整數(shù)程序： 失效率直接映象失效開銷7.4 %161.18 失效率兩路組相聯(lián)失效開銷6.0 %16 0.96 0.96/1.18=0.81,解：,5.4 減少Cache 失效開銷,5.4.5 采用兩級Cache,1. 應(yīng)把Cache做得更快？還是更大？ 答案：二者兼

44、顧，再增加一級Cache 第一級Cache(L1)小而快 第二級Cache(L2)容量大,2. 性能分析 平均訪問時間 命中時間L1失效率L1失效開銷L1 命中時間L1失效率L1 (命中時間L2失效率L2失效開銷L2),5.4 減少Cache 失效開銷,3. 局部失效率與全局失效率 局部失效率該級Cache的失效次數(shù)/到達(dá) 該級Cache的訪問次數(shù) 例如：上述式子中的失效率L2 全局失效率該級Cache的失效次數(shù)/CPU 發(fā)出的訪存的總次數(shù) 全局失效率L2失效率L1失效率L2 評價第二級Cache時，應(yīng)使用全局失效率 這個指標(biāo)。,5.4 減少Cache 失效開銷,例5.12 假設(shè)在1000次訪

45、存中，第一級Cache失效40次， 第二級Cache失效20次。試問：在這種情況下，該 Cache系統(tǒng)的局部失效率和全局失效率各是多少？ 解 第一級Cache的失效率（全局和局部）是40/1000， 即4%；第二級Cache的局部失效率是20/40，即50%， 第二級Cache的全局失效率是20/1000，即2%。,5.4 減少Cache 失效開銷,4. 當(dāng)?shù)诙塁ache比第一級Cache大得多時，兩 級Cache的全局失效率與容量和第二級Cache 相同的單級Cache的失效率非常接近。,5. 第二級Cache的參數(shù) 第二級Cache不會影響CPU的時鐘頻率， 因此其設(shè)計有更大的考慮空間。

46、 兩個問題： 能否降低CPI中的平均訪存時間部分？ 成本是多少？ (1) 容量 第二級Cache的容量一般比第一級的 大許多，如512KB。,5.4 減少Cache 失效開銷,(2) 相聯(lián)度 第二級Cache可采用較高的相聯(lián)度或偽 相聯(lián)方法,例5.13 給出有關(guān)第二級Cache的以下數(shù)據(jù)： 兩路組相聯(lián)使命中時間增加10%CPU時鐘周期 對于直接映象，命中時間L210個時鐘周期 對于直接映象，局部失效率L225% 對于兩路組相聯(lián)，局部失效率L220% 失效開銷L250個時鐘周期 試問第二級Cache的相聯(lián)度對失效開銷的影響如何？,5.4 減少Cache 失效開銷,解： 對于一個直接映象的第二級C

47、ache來說， 第一級Cache的失效開銷為： 失效開銷直接映象，L1 1025%5022.5個時鐘周期 對于兩路組相聯(lián)第二級Cache來說，命中 時間增加了10%(0.1)個時鐘周期，故第一級 Cache的失效開銷為： 失效開銷兩路組相聯(lián)，L1 10.120%5020.1個時鐘周期 把第二級Cache的命中時間取整，得10或11， 則：,5.4 減少Cache 失效開銷,失效開銷兩路組相聯(lián)，L1 1020%5020.0個時鐘周期 失效開銷兩路組相聯(lián)，L1 1120%5021.0個時鐘周期 故對于第二級Cache來說，兩路組相聯(lián)優(yōu)于 直接映象。,(3) 塊大小 第二級Cache可采用較大的塊，

48、 如 64、128、256字節(jié)。 圖 5.19 為減少平均訪存時間，可以讓容量較小 的第一級Cache采用較小的塊，而讓容量較大 的第二級Cache采用較大的塊。,5.4 減少Cache 失效開銷,5.5 減少命中時間,2. 應(yīng)使Cache足夠小，以便可以與CPU一起放 在同一塊芯片上。,命中時間直接影響到處理器的時鐘頻率。在當(dāng)今的許多計算機中，往往是Cache的訪問時間限制了處理器的時鐘頻率。,1. 硬件越簡單，速度就越快；,5.5.1 容量小、結(jié)構(gòu)簡單的Cache,第五章 存儲層次,1. 虛擬Cache 訪問Cache的索引以及Cache中的標(biāo)識都 是虛擬地址(一部分)。 2. 并非都采用

49、虛擬Cache(為什么?) 3. 虛擬Cache的清空問題,5.5.2 虛擬Cache,解決方法：在地址標(biāo)識中增加PID字段 (進程標(biāo)識符) 三種情況下失效率的比較 單進程，PIDs，清空 PIDs與單進程相比：0.30.6 PIDs與清空相比： 0.64.3%,5.5 減少命中時間,4. 同義和別名 解決方法：反別名法,頁著色 5. 虛擬索引物理標(biāo)識 優(yōu)點：兼得虛擬Cache和物理Cache的好處 局限性：Cache容量受到限制 (頁內(nèi)位移) Cache容量頁大小相聯(lián)度 6. 舉例：IBM3033的Cache 頁大小4KB 相聯(lián)度16,5.5 減少命中時間,5.5.3 寫操作流水化 (圖 5

50、.22),Cache容量164KB64KB 7. 另一種方法：硬件散列變換,頁地址地址標(biāo)識,頁內(nèi)位移,索 引,塊內(nèi)位移,31,12 11,0,5.5.4 Cache優(yōu)化技術(shù)總結(jié) (表 5-9),5.5 減少命中時間,1. 主存的主要性能指標(biāo)：延遲和帶寬 2. 以往： Cache主要關(guān)心延遲，I/O主要關(guān)心帶寬 現(xiàn)在：Cache關(guān)心兩者 下面討論幾種能提高主存性能的存儲器組織技術(shù) 在下面的討論中，我們以處理Cache失效為例來說明各種存儲器組織結(jié)構(gòu)的好處。,5.6 主 存,第五章 存儲層次, 增加Cache塊大小能利用主存帶寬增加所帶 來的好處 在以下的討論中，我們假設(shè)基本存儲 器結(jié)構(gòu)的性能為：

51、,5.6 主 存,送地址需4個時鐘周期 每個字的訪問時間為24個時鐘周期 傳送一個字的數(shù)據(jù)需4個時鐘周期, 為了減少失效開銷TM，應(yīng)該：,減少主存延遲 提高主存帶寬,如果Cache大小為4個字，則： 失效開銷4(4244) 432128(時鐘周期) 帶寬16/1280.0125(字節(jié)/時鐘周期),1. 增加存儲器的寬度 性能舉例(參照前面的假設(shè)) 當(dāng)寬度為4個字時： 失效開銷132(周期) 帶寬0.5(字節(jié)/周期),5.6 主 存, 缺點：,5.6 主 存,增加CPU和存儲器之間的連接通路的寬度 CUP和Cache之間有一個多路選擇器 擴充主存的最小增量增加了相應(yīng)的倍數(shù) 寫入有可能變得復(fù)雜,

52、舉例： DEC的Alpha Axp21064：256位寬 2. 采用簡單的多體交叉存儲器 在存儲系統(tǒng)中采用多個DRAM，并利用它們 潛在的并行性。, 存儲器的各個體一般是按字交叉的 交叉存儲器（interleaved memory） 通常是指存儲器的各個體是按字交叉的。 字交叉存儲器非常適合于處理： Cache讀失效，寫回法Cache中的寫回,性能舉例：(參照前面的假設(shè)) 失效開銷4244444(周期) 帶寬0.4(字節(jié)/周期),5.6 主 存,假設(shè)四個存儲體的地址是在字一級交叉的，即 存儲體0中每個字的地址對4取模都是0，體1中每個 字的地址對4取模都是1，依此類推。,0 4 8 12,地址

53、 體0,1 5 9 13,地址 體1,2 6 10 14,地址 體2,3 7 11 15,地址 體3,假設(shè)某臺機器的特性及其Cache的性能為： 塊大小為1個字 存儲器總線寬度為1個字 Cache失效率為3 % 平均每條指令訪存1.2次 Cache失效開銷為32個時鐘周期(和上面相同) 平均CPI(忽略Cache失效)為2 試問多體交叉和增加存儲器寬度對提高性能各 有何作用？ 如果當(dāng)把Cache塊大小變?yōu)?個字時，失效率,例 5.14,5.6 主 存,降為2%；塊大小變?yōu)?個字時，失效率降為1%。 根據(jù)5.6.2小節(jié)中給出的訪問時間，求在采用 2路、4路多體交叉存取以及將存儲器和總線寬 度增加

54、一倍時，性能分別提高多少？,解：,在改變前的機器中，Cache塊大小為一個字，其CPI為 2(1.23%32)3.15 當(dāng)將塊大小增加為2個字時，在下面三種情況下的CPI分別為：,5.6 主 存,32位總線和存儲器，不采用多體交叉： 2(1.22%232)3.54 32位總線和存儲器，采用多體交叉： 2(1.22%(4248)2.86 性能提高了10% 64位總線和存儲器，不采用多體交叉： 2(1.22%132)2.77 性能提高了14% 如果將塊大小增加到4個字節(jié)，則： 32位總線和存儲器，不采用多體交叉： 2(1.21%432)3.54,5.6 主 存, 存儲體的數(shù)目 體的數(shù)目訪問體中一個

55、字所需的時鐘周期,32位總線和存儲器，采用多體交叉： 2(1.21%(42416) 2.53 性能提高了25% 64位總線和存儲器，不采用多體交叉： 2(1.21%232) 2.77 性能提高了14%,3. 獨立存儲體 設(shè)置多個存儲控制器，使多個體能獨立操 作，以便能同時進行多個獨立的訪存。,5.6 主 存, 每個體有獨立的地址線 (動畫演示) 非阻塞Cache與多體結(jié)構(gòu) 體和超體 將存儲器分為若干個獨立的存儲體，而每個獨 立存儲體內(nèi)又劃分為若干個按字交叉方式工作的體。,5.6 主 存,4. 避免存儲體沖突 體沖突： 兩個請求要訪問同一個體 減少沖突：采用許多體 例如：NEC SX/3最多128個體 這種方法存在問題。,5.6 主 存,假如我們有128個存儲體，按字交叉方式工作，并執(zhí)行以下程序： int x 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 主 存, 解決體沖突的方法, 舉例