【正文】 139 小結(jié)與作業(yè) ? 小結(jié) ? 作業(yè)： P202207 ? 、 、 ? 、 、 ? 、 。 ? 一個存儲系統(tǒng)組織方式：構(gòu)成一個 “ Cache主存 磁盤 ” 存儲系統(tǒng)。 138 三級存儲系統(tǒng) ? 三級存儲系統(tǒng)： Cache、主存、磁盤三個存儲器構(gòu)成。 ? 用 L1和 L2分別表示第一級和第二級 Cache。再將整個數(shù)據(jù)塊調(diào)入 Cache。其余接著傳送。加快失效時的讀操作 基本思路：在數(shù)據(jù)塊讀入 Cache之前，盡快把所讀數(shù)據(jù)送往CPU。加快失效時的寫操作 設(shè)寫緩沖器，寫操作時送入寫緩沖器， CPU繼續(xù)執(zhí)行，由寫緩沖器完成寫入。在 Cache容量相等的情況下，指令與數(shù)據(jù)分體的 Cache比一體化的 Cache命中率要高； ? 每個單體 Cache容量小，簡單而訪問速度提高。 134 劃分數(shù)據(jù)體 Cache與指令體 Cache的原因 ? 數(shù)據(jù)與指令不在一體可以減少多個訪問源訪問存儲器的沖突 ； ? 兩個體的訪問操作不完全相同，數(shù)據(jù)體有讀操作和寫操作，而指令體只有讀操作。 4. 分指令 Cache和數(shù)據(jù) Cache。 2. 目錄表做在 CPU芯片內(nèi)。 j=j+1) x[ i ][ j ]=2 * x[ i ][ j ] 132 循環(huán)融合和分塊： 對多個數(shù)組的訪問改為對子矩陣的訪問，子陣的數(shù)據(jù)存放在一個數(shù)據(jù)塊中 133 改進 Cache性能（ 2） ——減少命中時間 減少命中時間的方法： 1. 使用小 Cache。 i=i+1 ) for( j = 0。 i=i+1) x[ i ][ j ]=2 * x[ i ][ j ] 改為： For( i =0。 j=j+1 ) for(i = 0。 Struct merge merged_array[size] 131 互換循環(huán) — 內(nèi)外循環(huán)互換，最大限度利用一個塊的數(shù)據(jù) For( j=0。 130 數(shù)據(jù)合并 — 多個獨立數(shù)組整合為一個數(shù)組。 129 降低失效率措施之六 ? 降低失效率的措施： （六） 編譯器優(yōu)化 ? 編譯時優(yōu)化軟件，提高數(shù)據(jù)的空間局部 性和時間局部性。 ?訪問 Cache之前先訪問緩沖器，直接讀取。 ? 以一種簡單的方式映射到第二個位置，例如，地址高位取反。 126 標志 數(shù)據(jù) Victim cache 寫緩沖器 下一級存儲器 CPU 地址 數(shù)據(jù) 輸入 數(shù)據(jù) 輸出 =？ =？ Cache 127 降低失效率措施之四 ? 降低失效率的措施： （四） 偽相聯(lián) ? 以直接映象在 Cache查找。 ? 能否尋求其他不增加命中時間和失效開銷的方法？ 125 降低失效率措施之三 ? 降低失效率的措施： （三）采用 Victim Cache ? 在 Cache和主存之間設(shè)一個小的全相聯(lián) Cache，存放 Cache中被替換的數(shù)據(jù)塊。 （ 2）相聯(lián)度和空間局部性相關(guān)聯(lián)，相聯(lián)度超過（ 8組相聯(lián)）失效率接近全相聯(lián)映象。（ 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é)；依次類推。 (2) 增加塊大小 ,失效開銷增加。當 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)象。 或?qū)懭胫鞔?， 再調(diào)入 Cache 問題：寫入時間長 措施： 1. 設(shè)寫隊列，寫入隊列后不管，由寫隊列完成寫入主存 2. 進入寫隊列的數(shù)據(jù)可以自動按字重組合寫入。解決方法：加一個污染位，記錄是否被寫過。 按寫分配法 不按寫 分配法 問題： 1. 全寫法的寫入時間問題。 ? 有三種方法： 110 Cache的寫操作 一、全寫法，亦稱寫直達法 (WT法 ——Writethrough)： 在對 Cache進行寫操作的同時，也對主存該內(nèi)容進行寫入 。 109 Cache的寫操作 ? 寫操作在訪存指令中占有一定的比率。 說明： （ 1）隨機算法：用隨機數(shù)確定要替換的塊； （ 2） FIFO算法：替換最早裝入主存的塊； （ 3） LFU算法：依據(jù)各塊使用的情況，選擇最近最少使用的塊替換。 105 Cache替換算法（ 3） ? 最久沒有使用法： 很久沒有被訪問的塊被替換 ? 實現(xiàn)： 每個數(shù)據(jù)塊設(shè)計數(shù)器；被訪問塊計數(shù)器清 0，其他數(shù)據(jù)塊加 1。 ? 優(yōu)點： 簡單，容易實現(xiàn)。 104 Cache替換算法（ 2） ? 先進先出法： 最早進入 Cache的數(shù)據(jù)塊被替換。 ? Cache的三種常用替換算法： ? 隨機法 (Random， RAND法 ) ? 先進先出法 (FirstIn FirstOut， FIFO法 ) ? 最久沒有使用法（ Least Frequently Used， LFU） 103 Cache替換算法（ 1） ? 隨機法： 隨機地選擇被替換地塊 需要隨機發(fā)生器 ? 優(yōu)點： 簡單，容易實現(xiàn) ? 缺點： 沒有考慮 Cache中數(shù)據(jù)塊使用情況。 ? Cache中，由于其速度高， 替換算法 必須用 硬件實現(xiàn) 。 內(nèi)存第 i個數(shù)據(jù)塊映象到 Cache的第 k組。 99 000001000011001000011000011101100101110010111010100111111110110110011111010100001101000100組 01組 10組 11組 16塊 8塊 主存 CACHE 2路組相聯(lián) 100 組相聯(lián)映象公式： k= i mod (G) 其中 G為 Cache組數(shù)。 3. 內(nèi)存塊和 Cache的組直接映象，對應(yīng)組內(nèi)的塊為全相聯(lián)映象。 請寫出： （ 1）主存與 Cache的格式； （ 2）相關(guān)存儲器的格式與容量 解： 主存地址： 區(qū)號 組號 塊號 塊內(nèi)地址 19 15 14 8 7 6 5 0 緩存地址： 組號 塊號 塊內(nèi)地址 14 8 7 6 5 0 區(qū)號 Ei 塊號 Bi 緩存塊號 bi 裝入位 9 5 4 3 2 1 0 相關(guān)存儲器的格式： 相關(guān)存儲器的容量，應(yīng)與緩存的塊數(shù)相同，即 : 組數(shù) 組內(nèi)塊數(shù) =128 4=512 98 組相聯(lián) ? 映象規(guī)則（ 2） ： 1. Cache被劃分為若干組，每組由若干塊構(gòu)成 。 3. 組間直接映象；組內(nèi)全相聯(lián)映象。 94 （三）組相聯(lián)映象 ? 映象規(guī)則（ 1） ： 1. 主存與緩存分成大小相同的組 。 直接映象 Cache利用率低， 全相聯(lián)映象 Cache利用率高。結(jié)構(gòu)復(fù)雜，實現(xiàn)難。 （ 1）主存地址多少位？如何分配？ （ 2） Cache地址多少位？如何分配？ （ 3）目錄表的格式和容量？ 93 直接映象與全相聯(lián)映象 直接映象 按地址一次讀出。 B：每塊大小 C： Cache容量 M：主存容量 塊 0 塊 1 ： 塊 i ： 塊 M/B1 塊 0 塊 1 ： 塊 C/B1 Cache 主存儲器 91 全相聯(lián)地址變換 塊號 塊內(nèi)地址 主存地址 塊號 塊內(nèi)地址 Cache地址 Bi bi 1 主存塊號 B Cache塊號 b 有效位 優(yōu)點：命中率較高， Cache的存儲空間利用率高； 缺點：線路復(fù)雜，成本高，速度低。設(shè) CPU訪存的地址順序為 0000（塊）、 1100、 0000、 0100、 1000、 1100，請分析執(zhí)行過程和 Cache的使用狀況。 87 直接映象 ——訪問過程 區(qū)號 塊 號B 塊 內(nèi)地址W 塊 號B 塊內(nèi) 地址W相等比較 1/W主存地址Cach e地址CPU相等主存不相等有效位 區(qū)號 數(shù)據(jù) 1 數(shù)據(jù) 2 數(shù)據(jù) n 1 E D1 D2 Dn 直接映象快速訪問 Cache 88 例： 例 1 假設(shè)在某個計算機系統(tǒng)中 Cache容量為 64K字節(jié)，數(shù)據(jù)塊大小是16個字節(jié)，主存容量是 4M，地址映象為直接相聯(lián)方式。 82 直接映象 ——公式 直接映象公式： j=i mod (M) 其中 M 為 Cache塊數(shù) 設(shè) M = 2m, j 是 I 的低 m 位。解決： ? 從內(nèi)存讀取的數(shù)據(jù)塊放入到 Cache什么位置？ ? 怎樣在 Cache中獲得所需數(shù)據(jù)？ ? 三種地址映象 ? 直接相聯(lián)方式 ? 全相聯(lián)方式 ? 組相聯(lián)方式 81 （一）直接映象