§7·5高速緩沖存儲器一、高速緩沖存儲器和工作原理1、高速緩沖存儲器

CACHE是一個高速度、小容量的緩沖存儲器，存儲CPU最經常訪問的指令或數據，一般用SRAM芯片構成，其全部功能由硬件實現，對程序員是透明的。CACHE用于解決CPU與主存間的速度匹配問題，其理論依據是程序訪問的局部性原理。在一個較短的時間內，CPU對局部范圍的存儲器地址頻繁訪問，而對此址范圍外的地址訪問很少。程序訪問的局部性原理2、工作原理

為了使主存與cache之間映射，將主存與緩存都分在若干個塊，每個塊包含若干個字，并使塊的大小相等。將主存n位地址分為高m位和低b位，緩存地址也分成高c位和低b位。主存的塊數M=2m遠大于緩存的塊數C=2c塊。由于緩存的塊數遠小于主存的塊數，一個緩存塊不能唯一、永久地對應一個主存塊，每個緩存塊需設一個標記，用來表示當前存放的是哪一個主存塊，該標記的內容相當于主存塊的編號（即主存地址的高m位）。CPU讀信息時根據主存地址的低位部分，將主存地址的高位部分與緩存塊的標記進行比較，以判斷所讀信息是否在緩存中。

~~~~~~~~主存儲器Cache

主存塊號0122m-1：：：：：：：：：：：：：：：：：：：：字塊0字塊1字塊2字塊M-1字塊0字塊1字塊C-1012c-1標記（1）CACAHE命中：CPU訪問的數據或指令已存在于CACHE中。（2）命中時間：在CACHE命中時的訪存時間，它等于CACHE的訪問時間。（3）失效時間：CACHE不命中時因訪存而增加的訪問時間，它等于對主存的訪問時間和將主存中的數據調入CACHE的時間。M=2mC=2c3、高速緩沖存儲器設計中要考慮的問題（1）地址映象：主存中的塊放入CACHE中的什么地方。（2）塊的替換策略：CACHE放滿時將哪塊數據移去再調入要訪問的塊。（3）塊的更新策略：解決CACHE數據寫操作與主存寫操作的關系。（4）CACHE容量16KB~256K和塊的容量4B~128B。二、地址映象根據主存的地址來構成CACHE的地址，即主存地址與CACHE地址之間的邏輯關系。

地址映象關系是用地址映象表來表示的，這張表反映了主存單元和CACHE單元間的對應關系，這張表是用硬件實現的。

塊號塊內地址地址映象表塊號塊內地址CACHE主存地址在訪問存儲器時，根據主存地址的低位部分在地址映象表中查找標志并與主存地址的高位部分進行比較，相同命中，將高速CACHE中數據送CPU，不相同從主存調入數據，再送入CPU。地址變換和替換算法均用硬件實現，CACHE對程序員是透明的。主存命中？調入？替換機構CPU訪問主存替換CacheNNYY訪問主存裝入Cache數據直接通路Cache地址數據總線、1、直接映象：一個主存塊只能映象到CACHE中的唯一一個指定塊的地址映象方式。

第1塊第2塊第3塊第4塊第1塊第2塊第3塊第4塊第5塊第6塊第7塊第8塊第9塊第10塊第11塊第12塊第13塊第14塊第15塊第16塊一個塊由若干個字節組成，由于主存容量比CACHE大得多，所以主存有許多塊會映射到CACHE的同一個塊上，將主存塊地址對CACHE的塊數取模即得到CACHE中的塊地址。主存地址：區號、塊號、塊內地址區號：作為標志存放在地址映象表中，用于判斷命中與否。塊號：用于查找地址映象表和在CACHE中的塊尋址。塊內地址：用于塊內尋址。

在訪存操作時，根據地址中的塊號讀出塊表中的區號并與當前地址的區號進行比較，比較結果相同表示CACHE命中，訪問可對CACHE進行，比較不相同則表示不命中，訪問需要對主存進行。特點：不需采用相聯存儲器，判斷命中的方法簡單，也不要替換算法，速度快，可實現大容量的CACHE。但數據塊的沖突率高。區號主存塊號塊內地址塊號塊內地址比較主存區號標志主存地址Cach地址不相等塊失效相等塊表按塊號查找例：有一個CACHE的容量為2K字，每個塊16個字，求（1）該CACHE可容納多少個塊？（2）如果主存的容量是256K字，則有多少個塊？（3）主存的地址有多少位？CACHE地址有多少位？（4）在直接映象方式下，主存中的第i塊映象到CACHE中哪一個塊中？（5）進行地址映象時，存儲器的地址分成哪幾段？各段分別有多少位？（1）CACHE塊數：2K/16=128塊（2）主存塊數：256K/16=16K（3）主存的地址位數：log2256K=18位CACHE地址位數：log22K=11位（4）在直接映象方式下，主存中的第i塊映象到CACHE中的imod128個塊中（5）存儲器的地址分成區號、主存塊號和塊內地址三段區號：主存地址位數與CACHE地址位數之差：18-11=7主存塊號：塊地址長度與CACHE的塊數有關，CACHE是128塊，所以主存塊號有log2128=7位塊內地址：每個塊由16個字組成，所以塊內地址的位數：log216=4位。

2、全相聯映象：每個主存塊可映象到任何CACHE塊的地址映象。

在訪問操作時，根據地址中的塊號在塊表中查找是否有相同的主存塊號。如果有，則表示CACHE命中，將對應的CACHE塊號取出并對CACHE進行訪問，如果沒有，則CACHE沒有命中，需對主存訪問，在將主存中的塊調入CACHE中的同時將主存塊號寫入塊表中，以改變地址映象關系。特點：是最靈活的地址映象方式，地址是映象算法復雜，需要采用

相聯存儲器，適合小容量的CACHE，速度慢。第0塊第1塊…….第N-1塊第0塊第1塊第M(N-1)主存塊號塊內地址塊號塊內地址比較主存塊號標志CACHE塊號不相等塊失效相等塊表相聯查找0123、組相聯映象：是將存儲空間分成若干組，各組之間是直接映象，而組內各塊之間則采用全相聯映象。此方式是上述兩種方式的折衷。CACHE0組第0區0組1組1組

0組第M-1區1組第0塊………..第N-1塊第0塊…….…..第N-1塊…….第（M-1）N….第MN-1

在訪存操作時，根據地址中的組號和塊號在塊表中的該組對應的若干項中查找是否有相同的主存區號和組內塊號。如果有相同的，CACHE命中，將對應的CACHE組內塊號取出以對CACHE訪問，沒有相同的表示不命中，在對主存進行訪問并將主存中的塊調入CACHE中的同時將主存區號和組內塊號和CACHE的組內塊號寫入塊表中，以改變地址映象關系。特點：適合于容量小，速度較低的場合。區號組號主存塊號塊內地址塊內地址塊號組號比較主存地址不相等塊失效CACHE相等塊表區號標志主存塊號標志CACHE塊號組內相聯查找三、替換策略及更新策略（一）替換策略在全相聯和組相聯映象方式下，主存中的數據塊寫入CACH中若干位置，這就有一個選擇替換掉哪一個CACHE存儲塊的問題。1、隨機法（RAND）：隨機地確定替換存儲單元，沒有根據訪存局部性原理，不能提高系統的命中率。2、先進先出法（FIFO）：替換最早調入的存儲單元。3、近期最少使用法（LRU）：替換出近期用得最少的存儲塊，利用了訪存局部性的原理，但實現復雜。例：設一個容量為4個塊的全相聯CACHE，采用FIFO替換算法，若主存的地址塊號序列為2、11、2、9、7、6、4、3畫出每次訪問后CACHE中的內容訪問順序12345678地址塊號211297643塊分配情況22112112119211976119764976437（二）更新策略（寫操作策略）由于Cache的內容只是主存部分內容的復制，它應當和主存內容保持一致。當程序運行時需對某個單元進行寫操作，則會出現Cache和主存中的內容不一致。1、寫操作CACHE命中時（1）寫直達法：寫CACHE又寫主存。（2）寫回法：寫CACHE不寫主存，當CACHE中數據被替換出去時才寫主存。2、寫操作CACHE不命中時（1）按寫分配法：從主存將塊調入CACHE。（2）不按寫分配法：當CACHE寫不命中時該地址所對應