高速緩沖存儲器(CACHE)-吳學涯第一頁，共30頁。計算機系統中，CPU的運行速度與主存的訪問速度極不匹配800MHzPentiumIIICPU一條指令的執行時間約為1.25ns，而133MHzSDRAM的存取時間為7.5ns在83%的時間內CPU都處于等待狀態，運行效率極低為提高CPU利用率，現代計算機體系結構中廣泛采用高速緩沖存儲器（Cache）技術第二頁，共30頁。3.4.1Cache基本原理程序訪問的局部性程序員通常采用模塊化的程序設計方法，某一模塊的程序往往集中在存儲器邏輯地址空間中很小的一塊范圍內，且程序地址分布是連續的CPU在一段較短的時間內，是對連續地址的一段很小的主存空間頻繁地進行訪問，而對此范圍以外地址的訪問甚少第三頁，共30頁。高速緩沖存儲器（Cache）技術利用程序訪問的局部性原理，把程序中正在使用的部分（活躍塊）存放在一個小容量的高速Cache中，使CPU的訪存操作大多針對Cache進行解決高速CPU和低速主存之間速度不匹配的問題，使程序的執行速度大大提高第四頁，共30頁。1.Cache的功能Cache是介于CPU和主存之間的小容量存儲器存取速度比主存快，接近CPU能高速地向CPU提供指令和數據，提高程序的執行速度Cache是主存的緩沖存儲器由高速的SRAM組成所有控制邏輯全部由硬件實現，對程序員而言是透明的有些CPU內置Cache，出現了兩級以上的多級Cache系統第五頁，共30頁。Cache系統與CPU和主存的關系FLASH演示第六頁，共30頁。2.Cache的基本原理CPU與Cache之間的數據交換以字為單位Cache與主存之間的數據交換以塊為單位一個塊由若干個定長字組成第七頁，共30頁。當CPU讀取主存中的一個字時，該字的主存地址被發給Cache和主存Cache控制邏輯依據地址判斷該字當前是否存在于Cache中若在，該字立即被從Cache傳送給CPU；若不在，則用主存讀周期把該字從主存讀出送到CPU同時把含有這個字的整個數據塊從主存讀出送到Cache中并采用一定的替換策略將Cache中的某一塊替換掉（替換算法由Cache管理邏輯電路來實現）第八頁，共30頁。Cache原理圖FLASH演示

按內容尋址的相聯存儲器（表）用于存放與Cache中數據相對應的主存地址可以快速檢索、判斷CPU讀取的某個字當前是否存在于Cache中第九頁，共30頁。3.Cache的命中率基于程序訪問的局部性原理，增加Cache使要訪問的數據絕大多數都可在Cache中找到這樣才能在性能上使主存的平均讀出時間盡可能接近Cache的讀出時間Cache的工作效率通常用“命中率”來表示第十頁，共30頁。命中率：CPU要訪問的信息在Cache中的概率Cache的命中率越高，CPU訪問主存的速度就越接近訪問Cache的速度通常Cache的容量越大，存儲的塊也越多，CPU的命中率就越高但是，當Cache的容量達到一定值時，命中率并不會隨著容量的增大而增加，而成本卻相應增加所以，Cache的容量一般是命中率與成本價格的折中第十一頁，共30頁。在一個程序執行期間，設Nc表示Cache完成存取的總次數，Nm表示主存完成存取的總次數，h定義為命中率，則有若tc表示命中時的Cache訪問時間，tm表示未命中時的主存訪問時間，1-h表示未命中率，則Cache－主存系統的平均訪問時間ta為：設e表示訪問效率，則有為提高訪問效率e，命中率h越接近1越好第十二頁，共30頁。【例3-1】CPU執行一段程序時，Cache完成存取的次數為1900次，主存完成存取的次數為100次，已知Cache存取周期為50ns，主存存取周期為250ns，求Cache－主存系統的效率和平均訪問時間。【解】Nc=1900，Nm=100，tc=50ns，tm=250ns∴ 命中率h=Nc/(Nc+Nm)=1900/(1900+100)=0.95

平均訪問時間ta =htc+(1-h)tm

=0.95×50+(1-0.95)×250=60ns

效率e=tc/ta=50/60=83.3%第十三頁，共30頁。3.4.2地址映射Cache的容量很小，保存的只是主存內容的一個子集，且Cache與主存的數據交換是以塊為單位的為了把信息放到Cache中，必須應用某種函數把主存地址定位到Cache中，這稱為地址映射CPU執行程序時，會將程序中的主存地址變換成Cache地址，這個變換過程叫做地址變換假設某臺計算機主存容量為1MB，被分為2048塊，每塊512BCache容量為8KB，被分為16塊，每塊也是512B第十四頁，共30頁。1.直接映射直接映射的Cache組織主存中的一個塊只能映射到Cache的某一特定塊中去主存的第0塊、第16塊、……、第2032塊，只能映射到Cache的第0塊主存的第1塊、第17塊、……、第2033塊，只能映射到Cache的第1塊……第十五頁，共30頁。直接映射是最簡單的地址映射方式硬件簡單，成本低，地址變換速度快，不涉及替換算法不夠靈活，Cache的存儲空間得不到充分利用每個主存塊只有一個固定存放位置，容易產生沖突，使Cache效率下降，因此只適合大容量Cache采用如果一個程序需要重復引用主存中第0塊與第16塊，最好將主存第0塊與第16塊同時復制到Cache中但由于它們都只能復制到Cache的第0塊中去，即使Cache中別的存儲空間空著也不能占用因此這兩個塊會不斷交替裝入Cache，導致命中率降低第十六頁，共30頁。2.全相聯映射全相聯映射的Cache組織主存中任何一塊都可以映射到Cache中的任何一塊位置上第十七頁，共30頁。全相聯映射方式比較靈活，主存的各塊可以映射到Cache的任一塊中，Cache的利用率高塊沖突概率低只要淘汰Cache中的某一塊，即可調入主存的任一塊由于Cache比較電路的設計和實現比較困難，這種方式只適合于小容量Cache采用第十八頁，共30頁。3.組相聯映射組相聯映射是直接映射和全相聯映射的折中方案主存和Cache都分組主存中一個組內的塊數與Cache

中的分組數相同組間直接映射，組內全相聯映射將Cache分成u組，每組v塊主存塊存放到哪個組是固定的至于存到該組哪一塊則是靈活的主存分為256組，每組8塊；Cache分為8組，每組2塊第十九頁，共30頁。組相聯映射方式主存中的各塊與Cache的組號之間有固定的映射關系但可自由映射到對應Cache組中的任何一塊主存中的第0塊、第8塊……均映射于Cache的第0組，但可映射到Cache第0組中的第0塊或第1塊；主存的第1塊、第9塊……均映射于Cache的第1組，但可映射到Cache第1組中的第2塊或第3塊第二十頁，共30頁。常采用的組相聯結構Cache每組內有2、4、8、16塊，稱為2路、4路、8路、16路組相聯Cache組相聯結構Cache是前兩種方法的折中方案適度兼顧二者的優點盡量避免二者的缺點得到普遍采用第二十一頁，共30頁。3.4.3替換策略Cache工作原理要求它盡量保存最新數據當從主存向Cache傳送一個新塊，而Cache中可用位置已被占滿時，就會產生Cache替換的問題替換問題與Cache的組織方式緊密相關：對直接映射Cache來說，只要把此可用位置上的主存塊換出Cache即可對全相聯和組相聯Cache來說，從若干可用位置中選取一個，把主存塊換出Cache第二十二頁，共30頁。1.最不經常使用（LFU）算法LFU（LeastFrequentlyUsed，最不經常使用）算法將一段時間內被訪問次數最少的那個塊替換出去每塊設置一個計數器，從0開始計數，每訪問一次，被訪塊的計數器就增1當需要替換時，將計數值最小的塊換出，同時將所有塊的計數器都清零將計數周期限定在對這些特定塊兩次替換的間隔時間內不能嚴格反映近期訪問情況新調入的塊很容易被替換出去第二十三頁，共30頁。2.近期最少使用（LRU）算法LRU（LeastRecentlyUsed，近期最少使用）算法把CPU近期最少使用的塊替換出去需要隨時記錄Cache中各塊的使用情況，以便確定哪個塊是近期最少使用的塊每塊設置一個計數器，Cache每命中一次，命中塊計數器清零，其他各塊計數器增1當需要替換時，將計數值最大的塊換出第二十四頁，共30頁。LRU算法相對合理，但實現起來比較復雜，系統開銷較大保護了剛調入Cache的新數據塊，具有較高的命中率不能肯定調出去的塊近期不會再被使用，所以不能算作最合理、最優秀的算法研究表明，采用這種算法可使Cache命中率達到90%左右第二十五頁，共30頁。3.隨機替換最簡單的替換算法是隨機替換完全不管Cache的情況，簡單地根據一個隨機數選擇一塊替換出去在硬件上容易實現，且速度也比前兩種算法快缺點是降低了命中率和Cache工作效率第二十六頁，共30頁。3.4.4寫操作策略由于Cache的內容只是主存內容的一個子集，應當與主存內容保持一致，而CPU對Cache的寫入更改了Cache的內容為此，可選用寫操作策略使Cache內容與主存內容保持一致第二十七頁，共30頁。1、寫回法（Write-Back）當CPU寫Cache命中時，只修改Cache的內容，而不立即寫入主存只有當此塊被換出時才寫回主存寫Cache和寫主存異步進行，顯著減少訪問主存的次數但存在數據不一致的隱患實現這種方法時，每個Cache塊必須配置一個修改位