【正文】 08 注意 ? LFU也不是理想的方法，它僅僅是根據(jù)過去訪存的頻率估計未來的訪存情況，因而只是推測的方法； ? 塊命中率與地址流、塊的大小和塊的數(shù)量有關(guān)，應(yīng)具體問題具體分析，選擇適當?shù)乃惴ǎ? ? 存儲單元替換時應(yīng)注意防止出現(xiàn)顛簸現(xiàn)象，即調(diào)入一塊時將另一塊調(diào)出，緊接著又需要訪問剛剛調(diào)出塊的數(shù)據(jù)，而將該塊調(diào)入時又將上一塊調(diào)出，即顛簸。 109 Cache的寫操作 ? 寫操作在訪存指令中占有一定的比率。 ? 對 Cache的讀操作，查表命中檢查可以和讀數(shù)同時進行，而寫操作，必須先進行命中檢查， 命中后，方可進行寫操作 。 ? 有三種方法： 110 Cache的寫操作 一、全寫法，亦稱寫直達法 (WT法 ——Writethrough)： 在對 Cache進行寫操作的同時，也對主存該內(nèi)容進行寫入 。 二、寫回法 (WB法 ——Write back)： 在 CPU執(zhí)行寫操作時，只寫入 Cache，不寫入主存；需要替換時，把修改過的塊寫回主存。 按寫分配法 不按寫 分配法 問題： 1. 全寫法的寫入時間問題。 2. 某些塊被替換時沒有被修改過。解決方法：加一個污染位，記錄是否被寫過。 111 Cache的寫操作 三、寫不命中（寫失效 ) ： 不按寫分配法 按寫分配法 直接將數(shù)據(jù)寫入主存 ，不調(diào)入緩存 數(shù)據(jù)寫入 Cache,再寫入 主存 。 或?qū)懭胫鞔?， 再調(diào)入 Cache 問題：寫入時間長 措施： 1. 設(shè)寫隊列，寫入隊列后不管，由寫隊列完成寫入主存 2. 進入寫隊列的數(shù)據(jù)可以自動按字重組合寫入。 112 Cache的性能分析 1. Ta=Tc*H+(1H)Tm 2. Ta=Tc*H+(1H)(Tc+Tm) =Tc+(1H)Tm 平均訪存時間＝命中時間＋失效率 失效開銷 注： Tm—— 主存訪問時間 Ta—— 平均訪存時間 113 Cache系統(tǒng)的加速比 等效的訪問周期為 T a mccca THTHT )1( ???Cache系統(tǒng)的加速比 Sp )1(1)1(cmccmcccmampHTTHTHTHTTTS???????命中率越高，加速比越大。當 Hc→ 1時， cmp TTS ?Tc ： Cache的訪問周期； Tm：主存儲器的訪問周期； Hc： Cache的命中率 114 ? 加速比 Sp： mccmpTHTHTS)1(* ???mcmpTHTTS)1( ???115 加速比與命中率的關(guān)系 存儲系統(tǒng)的訪問效率： cmccacTTHHTTe)1(1????Sp的期望值 Spmax=Tm/Tc Sp 1 0 2 4 6 8 命中率 H 116 改進 Cache性能 可以從三個方面著手： 一、降低失效率（提高 Cache命中率） 二、減少命中時間（訪問 Cache 的時間） 三、減少失效開銷 117 改進 Cache性能（ 1） ——降低失效率 ? 產(chǎn)生失效的原因： ? 開機時訪問 Cache產(chǎn)生的失效 ? 反復(fù)替換同一數(shù)據(jù)塊產(chǎn)生的失效（直接映象中多主存數(shù)據(jù)塊映象一個 Cache數(shù)據(jù)塊） ? Cache容量太小產(chǎn)生的失效 ? 改進措施： ? 降低失效率的基本措施： ? 提高相聯(lián)度，減少同一數(shù)據(jù)塊多次被替換現(xiàn)象。 ? 增加 Cache容量，提高裝入的數(shù)據(jù)塊數(shù)量 以上兩項措施均以 增加成本 為代價 在同等條件下有無其他改進措施？ 118 降低失效率措施之一 ? 降低失效率的措施： （一）改變數(shù)據(jù)塊大小 (1) 一般情況下，增加塊大小，可降低失效率。 (2) 增加塊大小 ,失效開銷增加。 (3) 但當 Cache容量小時，增加塊大小，可能提高失效率。（ Cache的塊數(shù)少） 塊 失效率 119 命中率 H 塊大小 初始 最佳 Cache命中率 H與塊大小的關(guān)系 120 塊大小 （字節(jié) ） Cache容量 1KB 4KB 16KB 64KB 256KB 16 % % % % % 32 % % % % % 64 % % % % % 128 % % % % % 256 % % % % % 各種塊大小情況下 Cache的失效率 121 例： 例：假設(shè)存儲系統(tǒng)在延遲 40個時鐘周期后，每 2個時鐘周期能讀出 16個字節(jié)，即：經(jīng)過 42個時鐘周期可提供 16個字節(jié)；經(jīng)過 44個時鐘周期，可以提供 32個字節(jié)；依次類推。請按上表計算，塊大小為多少時，平均訪存時間最??？ 解： 設(shè)命中時間與塊大小無關(guān)，為 1個時鐘周期 平均訪存時間 =命中時間 +失效率 *失效開銷 122 1) 塊大小 16字節(jié)， Cache容量 1KB 平均訪存時間 =1+(%*42) = 2）塊大小 256字節(jié)， Cache容量 256KB 平均訪存時間 =1+(%*72) = 注意： Cache容量增加，命中率提高 塊大小增大，命中率不一定增加 123 塊大小 （字節(jié)） 失效開銷 （時鐘周期） Cache容量 1KB 4KB 16KB 64KB 256KB 16 42 32 44 64 48 128 56 256 72 各種塊大小情況下 Cache的平均訪問時間 124 降低失效率措施之二 ? 降低失效率的措施： （二） 提高相聯(lián)度 （ 1）提高相聯(lián)度，降低失效率，增加命中時間。 （ 2）相聯(lián)度和空間局部性相關(guān)聯(lián)，相聯(lián)度超過（ 8組相聯(lián)）失效率接近全相聯(lián)映象。 注：提高 Cache相聯(lián)度和增加塊大小都會產(chǎn)成副作用。 ? 能否尋求其他不增加命中時間和失效開銷的方法？ 125 降低失效率措施之三 ? 降低失效率的措施： （三）采用 Victim Cache ? 在 Cache和主存之間設(shè)一個小的全相聯(lián) Cache，存放 Cache中被替換的數(shù)據(jù)塊。 ? 當發(fā)生失效時，先檢查 Victim Cache，若找到，作數(shù)據(jù)塊交換。 126 標志 數(shù)據(jù) Victim cache 寫緩沖器 下一級存儲器 CPU 地址 數(shù)據(jù) 輸入 數(shù)據(jù) 輸出 =？ =？ Cache 127 降低失效率措施之四 ? 降低失效率的措施： （四） 偽相聯(lián) ? 以直接映象在 Cache查找。命中時，直接訪問存??；失效時，先轉(zhuǎn)到檢查 Cache中的另一個位置，若仍不命中，再訪問主存。 ? 以一種簡單的方式映射到第二個位置，例如，地址高位取反。 128 降低失效率措施之五 ? 降低失效率的措施： （五） 硬件預(yù)取技術(shù) ?設(shè)一個高速緩沖器，存放提前預(yù)取的指令和數(shù)據(jù)塊。 ?訪問 Cache之前先訪問緩沖器，直接讀取。 ?在緩沖器中被訪問的指令數(shù)據(jù)塊返回時存入 Cache。 129 降低失效率措施之六 ? 降低失效率的措施： （六） 編譯器優(yōu)化 ? 編譯時優(yōu)化軟件，提高數(shù)據(jù)的空間局部 性和時間局部性。（把近期常用的數(shù)據(jù)集中在一起） ? 前提條件 ： 重新組織的程序不影響源程序的正確性。 130 數(shù)據(jù)合并 — 多個獨立數(shù)組整合為一個數(shù)組。 Int val[size] Int key[size] 改為： Struct merge{ Int val Int key }。 Struct merge merged_array[size] 131 互換循環(huán) — 內(nèi)外循環(huán)互換，最大限度利用一個塊的數(shù)據(jù) 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 ] 132 循環(huán)融合和分塊： 對多個數(shù)組的訪問改為對子矩陣的訪問，子陣的數(shù)據(jù)存放在一個數(shù)據(jù)塊中 133 改進 Cache性能（ 2） ——減少命中時間 減少命中時間的方法： 1. 使用小 Cache。 *小 Cache直接做在 CPU芯片內(nèi)。 2. 目錄表做在 CPU芯片內(nèi)。 3. 直接映象查表和讀取數(shù)據(jù)同時進行。 4. 分指令 Cache和數(shù)據(jù) Cache。原因見下一頁。 134 劃分數(shù)據(jù)體 Cache與指令體 Cache的原因 ? 數(shù)據(jù)與指令不在一體可以減少多個訪問源訪問存儲器的沖突 ； ? 兩個體的訪問操作不完全相同，數(shù)據(jù)體有讀操作和寫操作，而指令體只有讀操作。因此在替換時，只有數(shù)據(jù)體有寫回的問題。在 Cache容量相等的情況下，指令與數(shù)據(jù)分體的 Cache比一體化的 Cache命中率要高； ? 每個單體 Cache容量小，簡單而訪問速度提高。 135 改進 Cache性能（ 3） ——減少失效損失 ? 減少失效損失的途徑： 1。加快失效時的寫操作 設(shè)寫緩沖器，寫操作時送入寫緩沖器， CPU繼續(xù)執(zhí)行，由寫緩沖器完成寫入。 2。加快失效時的讀操作 基本思路：在數(shù)據(jù)塊讀入 Cache之前，盡快把所讀數(shù)據(jù)送往CPU。 21）盡早重啟動策略 當整個數(shù)據(jù)塊調(diào)入 Cache時，一旦發(fā)現(xiàn)所需數(shù)據(jù)，立即送至 CPU執(zhí)行。其余接著傳送。 22）亂序取策略 先從主存讀取所需數(shù)據(jù)，使 CPU繼續(xù)執(zhí)行。再將整個數(shù)據(jù)塊調(diào)入 Cache。 136 兩級 Cache ? 一級設(shè)在 CPU芯片內(nèi)，二級在芯片外。 ? 用 L1和 L2分別表示第一級和第二級 Cache。 ? 平均訪存時間 =命中時間 L1+失效率 L1*失效開銷 L1 ? 失效開銷 L1 =命中時間 L2+失效率 L2*失效開銷 L2 》》》 ? 平均訪存時間 =命中時間 L1+失效率 L1*（命中時間L2+失效率 L2*失效開銷 L2） 137 多級 Cache 局部失效率 ： (對應(yīng)某級的 Cache) 的訪問次數(shù)該級的失效次數(shù)該級局部失效率C a c h eC a c h e?全局失效率： 發(fā)出的訪存次數(shù)的失效次數(shù)該級全局失效率C PUC a c h e?全局失效率 L2 = 失效率 L1 * 失效率 L2 全局失效率會變小。 138 三級存儲系統(tǒng) ? 三級存儲系統(tǒng)： Cache、主存、磁盤三個存儲器構(gòu)成。實現(xiàn)方法有以下幾種： ? 兩個存儲系統(tǒng)組織方式：兩個獨立的存儲系統(tǒng)，“ Cache主存 ” 、 “ 主存 磁盤 ” 。 ? 一個存儲系統(tǒng)組織方式：構(gòu)成一個 “ Cache主存 磁盤 ” 存儲系統(tǒng)。 ? 全 Cache系統(tǒng)：沒有主存，只有 Cache和磁盤。 139 小結(jié)與作業(yè) ? 小結(jié) ? 作業(yè)： P202207 ? 、 、 ? 、 、 ? 、