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