高速緩沖存儲器Cache和虛擬存儲器TLB5.5高速緩沖存儲器CacheCache二五三四一Cache的基本原理主存與Cache的地址映射方式替換算法寫策略Cache的多層次設計一、Cache的基本原理Cache的工作原理Cache的特點Cache的命中率1231、Cache的特點Cache是指位于CPU和主存之間的一個高速小容量的存儲器，一般由SRAM構成。Cache功能：用于彌補CPU和主存之間的速度差異，提高CPU訪問主存的平均速度。設置Cache的理論基礎，是程序訪問的局部性原理。Cache的內容是主存部分內容的副本，Cache的功能均由硬件實現，對程序員是透明的。Cache存儲器工作原理（局部性工作原理）對大量典型程序的運行情況進行分析得到：在一個較短的時間間隔內，由程序產生的地址往往集中在地址空間的很小范圍內。原因：程序地址的分布一般是連續的，再加上循環程序、子程序等要重復執行多次。因此對程序地址的訪問自然具有相對集中的傾向。數據分布不如指令明顯，但對數組的存儲和訪問使存儲器地址相對集中。2、Cache的工作原理程序的簇聚性(局部性)指在每一小段時間內，程序所要用到的指令或數據的地址往往集中在一個局部區域內，因而對局部范圍內的存儲器地址頻繁訪問，而對此范圍外的地址則訪問甚少的現象。兩種局部性：時間局部性：最近被訪問的信息很可能還要被訪問。將最近被訪問的信息項裝入到Cache中?？臻g局部性：最近被訪問的信息臨近的信息也可能被訪問。將最近被訪問信息項附近的信息一起裝入到Cache中。如果能把正在執行的指令地址附近的一部分指令或數據從主存成批調入一個能高速訪問的小容量存儲器(Cache)

，供CPU在一段時間內隨時使用，從而大大減少CPU訪問主存的次數，加快程序的運行速度。Cache的速度比主存快5－10倍。Cache、主存與CPU的關系Cache的原理圖Cache的讀寫操作CPU在讀寫存儲器時，Cache控制邏輯首先要依據地址來判斷這個字是否在Cache中，若在Cache中，則稱為“命中”；若不在，則稱為“不命中”。針對命中/不命中、讀/寫操作，Cache的處理是不同的：讀命中：立即從Cache讀出送給CPU。讀不命中：通常有兩種解決方法：(1)將主存中該字所在的數據塊復制到Cache中，然后再把這個字傳送給CPU。(2)把此字從主存讀出送到CPU，同時，把包含這個字的數據塊從主存中讀出送到Cache中。Cache的讀寫操作寫不命中：直接將該字寫入主存中，且不再調入Cache；寫命中：通常也有兩種方法進行處理：寫貫穿方法：同時對Cache和主存進行寫操作；寫回：只寫Cache，僅當此Cache塊被替換時，才將該塊寫入主存3、Cache的命中率命中率指CPU訪問主存數據時，命中Cache的次數，占全部訪問次數的比率。失效率就指不命中Cache的次數，占全部訪問次數的比率。命中率h取決于程序的行為、Cache的容量、組織方式、塊大小。在一個程序執行期間，設Nc表示Cache完成存取的總次數，Nm表示主存完成存取的總次數，則命中率：若tc表示Cache的訪問時間，tm表示主存的訪問時間，則Cache/主存系統的平均訪問時間ta為：Cache/主存系統的訪問效率e:二、主存與Cache的地址映射方式討論前提：Cache的數據塊稱為行，主存的數據塊稱為塊，行與塊是等長的；主存容量為2m塊，Cache容量為2c行，每個字塊中含2b字。主存中只有一小部分塊的內容可放在Cache中。Cache存儲單元的組成部分:數據字段：保存從主存單元復制過來的數據。標志字段：保存相應主存單元的地址信息。有效位字段：標識數據字段和標志字段的是否有效。討論的問題：如何根據主存地址，判斷Cache有無命中并變換為Cache的地址，以便執行讀寫。有三種地址映射方式：直接映射全相聯映射組相聯映射1、直接映射直接映射是一種多對一的映射關系：主存的第i塊一定映射到Cache的第j行，且：

j=imod2c直接映像方式特點：主存的字塊只可以和固定的Cache字塊對應，映射方式直接、簡單，易實現，利用率低。標志位較短，比較電路的成本低。如果主存空間有2m塊，Cache中字塊有2c塊，則標志位只要有m-c位，且僅需要比較一次。機制不靈活，Cache命中率低。標記K：直接映像硬件實現舉例注意P358-359與這里講的區別。書上訪問Cache是訪問2個字(4字節/字)，這里是用W進行選擇，不需要在外面加一個2選擇1多路器來選擇。2、全相聯映射全相聯映射是多對多的映射關系：對于主存的任何一塊均可以映射到Cache的任何一行。特點：主存的字塊可以和Cache的任何字塊(行)對應，利用率高，方式靈活，命中率高。標志位較長，比較電路的成本太，高難于設計和實現。如果主存空間有2m塊，則標志位要有m位。如果Cache有n塊，則需要有n個比較電路。全相聯硬件實現舉例3、組相聯映射組相聯映像是將Cache的行分成c’=2c-r組，每組2r行。主存的字塊存放到Cache中的哪個組是固定的，至于映射到該組哪一行是靈活的，即有如下函數關系：

j＝(imod2c’)*2r+k其中0≤k≤2r-1組相聯映像方式特點：組間為直接映像，組內為全相聯映像。大大增加了映射的靈活性，主存中一塊可映射到Cache的2r塊，提高了命中率。每次比較只是進行2r路比較，r較小時，硬件開銷不是很大。集中了兩個方式的優點。成本也不太高。組相聯映像通常采用2路、4路和8路比較，即取r=1,r=2,r=3。組相聯硬件實現舉例三種映像方式比較全相聯映射主存中的一塊可以映射到Cache中任何一個位置直接映像主存中的一塊只能映射到Cache中唯一的一個位置定位時，不需要判斷，只需替換多路組相聯映射主存中的一塊可以選擇映射到Cache中多個位置全相聯映射和多路組相聯映射的失效處理從主存中取出新塊為了騰出Cache空間，需要替換出一個Cache塊不唯一，則需要判斷應替出哪塊三、替換算法1、隨機替換算法2、先進先出算法（FIFO）3、最近最少使用算法（LRU）該算法統計哪一個Cache行是近段時間使用次數最少的Cache行，需替換時就將它替換出去。LRU替換算法可以通過為每個Cache行設置一個計數器來實現LRU替換算法，Cache每命中一次，命中行的計數器被清零，其他行的計數器加1，需要替換的話，就將計數器值最大的行替換出去。LRU算法的平均命中率比FIFO要高，并且當分組容量加大時，能提高LRU替換算法的命中率。如下圖。圖LRU算法替換登記表（數字為塊號）例：假定cache是直接映射的，每塊4字。Cache的容量是16字，初始時cache為空。對于下述訪問主存地址序列(字地址)：

1,4,8,5,20,17,19,56,9,11,4,43,5,6,9,17。標出每次訪問的cache命中情況以及最后cache的內容，并計算命中率。如果Cache訪問時間為0.1μs，主存的訪問時間為1μs，問CPU訪問內存的平均時間是多少？解：cache的塊數=16/4=4塊。

根據Cache塊號=主存地址/4(mod4)

可得到下表：塊0塊1塊2塊3Cache中最后的內容如下：主存地址范圍塊號0—304—718—11212--15316—19020—23124--27228—31332-35036—39140--43244—47348—51052—55156--592序號12345678910111213141516地址14852017195691144356917塊號0121100222121120命中0001001001001100塊0塊1塊2塊3地址17地址6地址9空命中率=5/16=31.25%CPU訪問內存的平均時間Ta=H*Tc+(1-H)*Tm=0.3125*0.1+0.6875*1=0.71875四、寫策略常用的寫策略通常有寫貫穿和寫回兩種寫貫穿策略當CPU寫Cache命中時，所有寫操作既對Cache也對主存進行；當CPU寫Cache不命中時，直接寫主存，有兩種做法：不將該數據所在的塊拷貝到Cache行，稱為WTNWA法；將該數據所在塊拷貝到Cache的某行，稱為WTWA法。

寫回策略（WriteBack）當CPU寫Cache命中時，寫操作只是對Cache進行，而不修改主存的相應內容，僅當此Cache行被換出時，相應的主存內容才被修改；當CPU寫Cache不命中時，先將該數據所在塊拷貝到Cache的某行，余下操作與Cache寫命中時相同。為了區別Cache行是否被改寫過，應為每個Cache行設置一個修改位，CPU修改Cache行時，標記其修改位，當此Cache行被換出時，判別此Cache行的修改位，從而決定是否將Cache行數據寫回主存相應單元。

3、兩種寫策略比較寫貫穿策略保證了主存數據總是有效，寫回策略可能導致Cache和主存數據不一致；寫回策略的效率高于寫貫穿策略；寫回策略的控制比寫貫穿策略的控制復雜。五、Cache的多層次設計設計Cache主要考慮五個問題：容量Cache中行的大小Cache的組織（地址映射方式）指令和數據共用同一個Cache還是分享不同CacheCache的層次統一Cache和分離Cache統一Cache：只有一個Cache，指令和數據混放。分離Cache：分為指令Cache和數據Cache。它消除了流水線中指令處理器和執行單元間的競爭，因此，特別適用于PentiumⅡ和PowerPC這樣的超標量流水線中；是Cache結構發展的趨勢。單級Cache與兩級Cache一級Cache（）和二級Cache采用兩級Cache結構可以提高性能Cache一致性問題

MESI協議的狀態圖RH——讀命中；RMS——讀不命中，共享；RME——讀不命中，專有；WH——寫命中；WM——寫不命中；SHR——讀監聽命中；SHW——寫監聽命中或讀是用于修改；+——無效處理；↑——Cache行填入；↓——無效行拷回；×——讀用于修改CACHE使用中的幾個問題CACHE的重要技術指標：命中率影響CACHE命中率的因素CACHE的容量，大一些好CACHE與主存儲器每次交換信息的單位量(CacheLineSize)適中CACHE不同的組織方式，多路組相聯更好CACHE的多級組織可提高命中率CACHE裝滿后的替換算法cache的容量與命中率的關系CacheSizeinKBHitRatecachelinesize與缺失率的關系多級的cache結構與命中率的關系

為增加cache容量，可以在已有的cache(第一級)存儲器系統之外，再增加一個容量更大的cache(第二級)。第二級cache的容量比第一級cache的容量要大得多，在第一級cache中保存的信息也一定保存在第二級cache中。當CPU訪問第一級cache出現缺失情況時，就去訪問第二級cache。若第一級、第二級cache的命中率為90%，則它們合起來后的命中率為1-(1-90%)×(1-90%)=99%，而不會是81%。5.6虛擬存儲器虛擬存儲器的實現方式有三種：段式、頁式或段頁式頁式虛擬存儲器

頁式虛擬存儲器中邏輯地址與物理地址的轉換關系5.6虛擬存儲器段式虛擬存儲器段式虛擬存儲器中邏輯地址與物理地址的轉換關系5.6虛擬存儲器段頁式虛擬存儲器段頁式虛擬存儲器中邏輯地址與物理地址的轉換關系5.9IA32架構的存儲系統舉例

P6微架構下的Cache

IntelNetBurst微架構下的Cache

IntelCore微架構的多核高效內存管理技術

一二三一、P6微架構下的CachePentiumⅡ處理器框圖一、P6微架構下的CacheL1級數據Cache的結構二、IntelNetBurst微架構下的CachePentium4的簡化圖三、IntelCore微架構的多核高效內存管理技術IntelCore的微架構的兩個核心IntelCore微架構在一個芯