高速緩沖存儲器的組成與運行原理

1、1第三單元 層次存儲器系統(tǒng)第三講 高速緩沖存儲器的組成與運行原理劉衛(wèi)東2內(nèi)容提要 Cache的目的 基本原理 Cache的三種映射方式 提高Cache性能3CPU與DRAM性能比較處理器性能每年處理器性能每年增長增長60%動態(tài)存儲器性能每年增長9%110100100019801981198319841985198619871988198919901991199219931994199519961997199819992000DRAMCPU1982CPU與主存儲器的性能差與主存儲器的性能差異，每年增長異，每年增長50%性能性能摩爾定律年份年份4Cache的提出一直以來，CPU和主存儲器的速度總是

2、有差距CPU的發(fā)展一直以速度為主，以提高速度為核心主存的發(fā)展一直以容量為主，以提高容量為核心如何解決這之間的矛盾？5這不是一個技術(shù)問題，而是一個經(jīng)濟問題。從技術(shù)上說，能制造出多高速度的CPU，就能制造出同樣速度的存儲器，只不過是我們是否愿意付出如此高的價格。有沒有更好的辦法？能否用廉價的高容量存儲器實現(xiàn)相對的高速度呢？6程序的局部性原理 程序在一定的時間段內(nèi)通常只訪問較小的地址空間 兩種局部性： 時間局部性 空間局部性地址空間訪問概率7層次存儲器系統(tǒng) 使用高速緩沖存儲器Cache來提高CPU對存儲器的平均訪問速度。 時間局部性：最近被訪問的信息很可能還要被訪問。 將最近被訪問的信息項裝入到Ca

3、che中。 空間局部性：最近被訪問的信息臨近的信息也可能被訪問。 將最近被訪問的信息項臨近的信息一起裝入到Cache中。8MEMORY CACHE CONTROLCACHE的基本運行原理的基本運行原理數(shù)據(jù)總線數(shù)據(jù)總線譯碼選一單元譯碼選一單元比較選一行比較選一行讀過程為例讀過程為例地址總線地址總線ADDR DATA CACHE CPU 9要解決的主要問題1. 地址之間的映射關(guān)系：如何從主存地址得到Cache地址？2. Cache中的內(nèi)容是否已經(jīng)是主存對應(yīng)地址的內(nèi)容？3. Cache內(nèi)容裝入策略如何提高Cache的命中率？10幾個參數(shù) 塊（Line）：數(shù)據(jù)交換的最小單位 命中（Hit）：在較高層次

4、中發(fā)現(xiàn)要訪問的內(nèi)容 命中率（Hit Rate）：命中次數(shù)/訪問次數(shù) 命中時間：訪問在較高層次中數(shù)據(jù)的時間 失效（Miss）：需要在較低層次中訪問塊 失效率（Miss Rate）：1-命中率 失效損失（Miss Penalty）：替換較高層次數(shù)據(jù)塊的時間+將該塊交付給處理器的時間 命中時間失效損失11參數(shù)典型數(shù)值 塊大?。?128Byte 命中時間：14周期 失效損失： 訪問時間：610個周期 傳輸時間：222個周期 命中率：80%99% Cache容量：1KB256KB12全相聯(lián)方式全相聯(lián)方式C P U數(shù)據(jù)數(shù)據(jù)地址地址有效位有效位主存儲器主存儲器CACHE比較比較譯碼譯碼標志標志數(shù)據(jù)數(shù)據(jù)塊號塊

5、內(nèi)地址主存地址13全相連映射硬件實現(xiàn)舉例14全相聯(lián)方式的地址映射特點1. 主存的字塊可以和Cache的任何字塊對應(yīng)，利用率高，方式靈活。2. 標志位較長，比較電路的成本太高。如果主存空間有2m塊，則標志位要有m位。同時，如果Cache有n塊，則需要有n個比較電路。使用成本太高15直接映射方式直接映射方式C P U數(shù)據(jù)數(shù)據(jù)地址地址有效位有效位主存儲器主存儲器CACHE比較比較譯碼譯碼譯碼譯碼塊塊內(nèi)內(nèi)地地址址塊塊號號標志標志數(shù)據(jù)數(shù)據(jù)塊號塊內(nèi)地址主存地址16Cache 舉例 8 塊 cache 每塊16 字節(jié) “直接映射”: 內(nèi)存中的每個單元在Cache中只會有一個唯一的位置和它對應(yīng)。 0-1532

6、-4716-31128-143160-175144-15917直接映射Cache 舉例 假定有如下訪問操作: Read location 0 Read location 16 Read location 32 Read location 4 Read location 8 Read location 36 Read location 32 Read location 128 Read location 148 cache中命中和缺失各有多少次?0-1532-4716-31128-143160-175144-1590-1516-3132-47XXX 128-143XXX 144-15918Cac

7、he 舉例：續(xù) Cache中命中和缺失次數(shù)? Read location 0: Miss Read location 16: Miss Read location 32: Miss Read location 4: Hit Read location 8: Hit Read location 36: Hit Read location 32: Hit Read location 128: Miss Read location 148: Miss 命中率 = 4/9 = 45% 注意:失效的原因 啟動失效 沖突失效0-1532-4716-31128-143160-175144-1590-1516

8、-3132-47XXX 128-143XXX 144-15919直接映射 Cache:硬件實現(xiàn)Address (showing bit positions)2010ByteoffsetValid TagDataIndex012102110221023TagIndexHitData203231 30 13 12 11 2 1 020 增加塊大小可以更好地利用空間局部性直接映射 Cache: 硬件實現(xiàn) Address (showing bit positions)1612ByteoffsetVTagDataHitData16324Kentries16 bits128 bitsMux32323223

9、2Block offsetIndexTag31 16 15 4 32 1 021直接映射方式的地址映射特點1. 主存的字塊只可以和固定的Cache字塊對應(yīng)，方式直接，利用率低。2. 標志位較短，比較電路的成本低。如果主存空間有2m塊，Cache中字塊有2c塊，則標志位只要有m-c位。且僅需要比較一次。利用率低，命中率低，效率較低22兩路組相聯(lián)方式兩路組相聯(lián)方式C P U數(shù)據(jù)數(shù)據(jù)地址地址有效位有效位主存儲器主存儲器CACHE譯碼譯碼比較比較比較比較譯碼譯碼譯碼譯碼標志標志數(shù)據(jù)數(shù)據(jù)塊號塊內(nèi)地址主存地址23兩路組組相聯(lián)方式的地址映射特點1. 前兩種方式的折衷方案。組間為全相連，組內(nèi)為直接映射。2.

10、集中了兩個方式的優(yōu)點。成本也不太高。是常用的方式24組相連Cache訪問舉例z 假設(shè)有下列訪問主存順序:yRead location 0: MissyRead location 16: MissyRead location 32: MissyRead location 4: HityRead location 8: HityRead location 36: HityRead location 32: HityRead location 128: MissyRead location 148: MissyRead location 0: HityRead location 128: HityR

11、ead location 4: HityRead location 132: Hit0-1564-790-1516-3132-47128-143144-15925四路組相連Cache實現(xiàn)Address228VTagIndex012253254255DataVTagDataVTagDataVTagData32224-to-1 multiplexorHitData123891011123031026三種映射方式比較 直接映射 主存中的一塊只能映射到Cache中唯一的一個位置 定位時，不需要判斷，只需替換 全相連映射 主存中的一塊可以映射到Cache中任何一個位置 N路組相連映射 主存中的一塊可以選

12、擇映射到Cache中N個位置 全相連映射和N路組相連映射的失效處理 從主存中取出新塊 為了騰出Cache空間，需要替換出一個Cache塊 不唯一，則需要判斷應(yīng)替出哪塊27提高Cache的性能1. 提高命中率 2. 縮短缺失后的處理時間3. 提高訪問cache的速度28Cache缺失的原因 必然缺失 （開機或進程切換）：首次訪問數(shù)據(jù)塊 世事總是有缺憾 注意：如果我們運行幾百萬條指令，有點必然缺失又何妨？ 沖突缺失 多個 memory塊映射到同一 cache塊 解決辦法 1：增大 cache 容量 解決辦法 2：增加相連組數(shù) 容量沖突 Cache無法裝入程序需要訪問的所有塊 方案：增大 cache

13、 容量 無效缺失：其它進程（如I/O）修改了主存29影響影響 CACHE 命中率的因素命中率的因素 從從 CACHE 本身諸因素看，可能：本身諸因素看，可能：1. CACHE 的容量，大一些好的容量，大一些好2. CACHE 與主存儲器每次交換與主存儲器每次交換 信息的單位量信息的單位量(Cache Line Size)適中適中3. CACHE 不同的組織方式，多路組相聯(lián)更好不同的組織方式，多路組相聯(lián)更好4. CACHE 的多級組織可提高命中率的多級組織可提高命中率5. CACHE 裝滿后的換字算法裝滿后的換字算法30Cache命中率0%20%40%60%80%100%181632641282

14、56512Cache Size in KBHit Rate31塊大小和缺失率的關(guān)系1 K B8 K B1 6 K B6 4 K B2 56 K B25 64 0%3 5%3 0%2 5%2 0%1 5%1 0%5 %0 %Miss rate641 64B lock size (byte s)32塊大小的權(quán)衡 一般來說，數(shù)據(jù)塊較大可以更好地利用空間局部性，但是： 數(shù)據(jù)塊大意味著缺失損失的增大： 需要花費更長的時間來裝入數(shù)據(jù)塊 若塊大小相對Cache總?cè)萘縼碚f太大的話，命中率將降低 Cache塊數(shù)太少一般來說，平均訪問時間 = 命中時間 x 命中率 + 失效損失 x 缺失率缺失損失缺失損失塊大小塊

15、大小缺失率缺失率利用空間局部性較少的數(shù)據(jù)塊：彌補時間局部性平均訪平均訪問時間問時間增加了缺失損失和缺失率塊大小塊大小塊大小塊大小33Cache的替換算法1. 先進先出算法（FIFO）將最早調(diào)入Cache的字塊替換出去。容易實現(xiàn)，開銷小。2. 最近最少使用算法（LRU）需要計算字塊的使用次數(shù)，開銷大，但平均命中率比FIFO要高。3. 隨機替換（RAND）34多級Cache 采用兩級或更多級cache來提高命中率 將Cache分解為指令Cache和數(shù)據(jù)Cache35CACHE 接入系統(tǒng)的體系結(jié)構(gòu)接入系統(tǒng)的體系結(jié)構(gòu)1. 側(cè)接法：像入出設(shè)備似的連接到側(cè)接法：像入出設(shè)備似的連接到 總線上，優(yōu)點是結(jié)構(gòu)簡單

16、，成本低，總線上，優(yōu)點是結(jié)構(gòu)簡單，成本低， 缺點是不利于降低總線占用率缺點是不利于降低總線占用率。CPUMEMORYCACHEBus Master 1Bus Master 2總線總線36CACHE 接入系統(tǒng)的體系結(jié)構(gòu)接入系統(tǒng)的體系結(jié)構(gòu)2. 隔斷法：把原來的總線打斷為兩段，隔斷法：把原來的總線打斷為兩段， 使使 CACHE 處在兩段之間，優(yōu)點是有利處在兩段之間，優(yōu)點是有利于提高總線利用率，支持總線并發(fā)操作，于提高總線利用率，支持總線并發(fā)操作，缺點是結(jié)構(gòu)復雜，成本較高。缺點是結(jié)構(gòu)復雜，成本較高。CPUMEMORYCACHEBus Master 1Bus Master 2總線總線37改寫主存儲器的策

17、略改寫主存儲器的策略若 CPU 改寫了 CACHE 一單元內(nèi)容后且尚未改變主存相應(yīng)單元內(nèi)容，則出現(xiàn)數(shù)據(jù)不一致性。有兩種解決辦法：1.接下來直接改寫主存單元內(nèi)容（Write Through） 簡便易行, 但可能帶來系統(tǒng)運行效率不高的問題。需要寫入緩沖存儲器。2.拖后改寫主存單元內(nèi)容（Write Back）一直拖到有另外的設(shè)備要讀該內(nèi)容過時的主存單元時,則首先停止這一讀操作，接下來改寫主存內(nèi)容，之后再起動已停下來的讀操作。 矛盾是如何檢查是否是讀無效內(nèi)存單元的操作，這是通過 監(jiān)視地址總線完成的，記下無效單元地址用于比較。 控制復雜些，但可以提供更高的系統(tǒng)運行效率。38Pentium上的Cache

18、Intel的80386及更早的處理器芯片上并沒有片上的高速緩沖存儲器。 80486：引入一個8K字節(jié)的片上Cache，其塊大小為16字節(jié)，采用的是四路組相連映象方式。 Pentium：芯片上已經(jīng)有了兩個8K字節(jié)的片上cache，一個用作指令緩存，另一個用作數(shù)據(jù)緩存。它們的塊大小都為32字節(jié)，采用兩路組相連的組織方式。3964位總線接口指令緩存（8 KB）指令分支預測預取緩沖器整型寄存器組數(shù)據(jù)緩存（8 KB）浮點算邏部件浮點寄存器組整型ALU整型ALU乘法器加法器除法器32位64位32位32位U流水線V流水線32位32位256位64位 Pentium結(jié)構(gòu)簡圖40Pentium的數(shù)據(jù)緩存 數(shù)據(jù)緩存

19、由128組，每組兩個cache塊組成，從邏輯上可以看成是大小為4K字節(jié)的兩“路”。 每個cache塊都有20位的標記位和兩位的狀態(tài)位與其對應(yīng)，標記位即存放在該cache塊中的主存塊的地址的高20位，兩位狀態(tài)位可以標記出4個不同的塊狀態(tài)。 替換算法采用的是最近最少使用法（LRU），所以對每組cache塊還需要有1位的LRU位來表示CPU最近訪問的是該組中的哪一塊。 采用拖后寫策略。 支持兩級Cache。41Pentium Cache塊的狀態(tài) 修改態(tài)（M）：處于這個狀態(tài)的cache塊中的數(shù)據(jù)已經(jīng)被修改過，和主存中對應(yīng)的數(shù)據(jù)已不同，只能從cache中讀到正確的數(shù)據(jù)。 獨占態(tài)（E）：處于本狀態(tài)的cache塊的數(shù)據(jù)和主存中對應(yīng)的數(shù)據(jù)塊內(nèi)容相同，而且在其它cache中沒有副本。 共享態(tài)（S）：處于本狀態(tài)的cache塊的數(shù)據(jù)和主存中對應(yīng)的數(shù)據(jù)塊內(nèi)容相同，而且可能在其它cache中有該塊的副本。 非法態(tài)（I）：處于本狀態(tài)的cache塊中尚未裝入數(shù)據(jù)。42兩級Cache塊的狀態(tài)轉(zhuǎn)換IL1:L2:SIEEMM讀入數(shù)據(jù)讀入數(shù)據(jù)第一次修改第二次修改多次修改訪問主存第一次修改訪問主存替換策略：S、E狀態(tài)不需改寫L243寫主存順序 L2監(jiān)聽到其它總線主設(shè)備寫請求，