CPU快取
在計算機系統中，CPU高速緩存（英語：CPU Cache，在本文中簡稱緩存）是用於減少處理器訪問內存所需平均時間的部件。在金字塔式存儲體系中它位於自頂向下的第二層，僅次於CPU寄存器。其容量遠小於內存，但速度卻可以接近處理器的頻率。
當處理器發出內存訪問請求時，會先查看緩存內是否有請求數據。如果存在（命中），則不經訪問內存直接返回該數據；如果不存在（失效），則要先把內存中的相應數據載入緩存，再將其返回處理器。
緩存之所以有效，主要是因為程序運行時對內存的訪問呈現局部性（Locality）特徵。這種局部性既包括空間局部性（Spatial Locality），也包括時間局部性（Temporal Locality）。有效利用這種局部性，緩存可以達到極高的命中率。
在處理器看來，緩存是一個透明部件。因此，程序員通常無法直接干預對緩存的操作。但是，確實可以根據緩存的特點對程序代碼實施特定優化，從而更好地利用緩存。
基本描述 編輯
緩存的存儲結構 編輯
結構上，一個直接映射（Direct Mapped）緩存由若干緩存塊（Cache Block，或Cache Line）構成。每個緩存塊存儲具有連續內存地址的若干個存儲單元。在32位計算機上這通常是一個雙字（dword），即四個位元組。因此，每個雙字具有唯一的塊內偏移量。
每個緩存塊有一個索引（Index），它一般是內存地址的低端部分，但不含塊內偏移和字節偏移所占的最低若干位。一個數據總量為4KB、緩存塊大小為16B的直接映射緩存一共有256個緩存塊，其索引範圍為0到255。使用一個簡單的移位函數，就可以求得任意內存地址對應的緩存塊的索引。由於這是一種多對一映射，必須在存儲一段數據的同時標示出這些數據在內存中的確切位置。所以每個緩存塊都配有一個標籤（Tag）。拼接標籤值和此緩存塊的索引，即可求得緩存塊的內存地址。如果再加上塊內偏移，就能得出任意一塊數據的對應內存地址。
因此，在緩存大小不變的情況下，緩存塊大小和緩存塊總數成反比關係。下圖中所示的緩存塊來自一個數據總量為4KB、每個緩存塊大小為16B的直接映射緩存，其標籤長度為20bits（ ）。
此外，每個緩存塊還可對應若干標誌位，包括有效位（valid bit）、髒位（dirty bit）、使用位（use bit）等。這些位在保證正確性、排除衝突、優化性能等方面起着重要作用。
運作流程 編輯
下面簡要描述一個假想的直接映射緩存的工作流程。這個緩存共有四個緩存塊，每個塊16字節，即4個字，因此共有64字節存儲空間。使用寫回（Write back）策略以保證數據一致性。
系統啟動時，緩存內沒有任何數據。之後，數據逐漸被載入或換出緩存。假設在此後某一時間點，緩存和內存布局如右圖所示。此時，若處理器執行數據讀取指令，控制邏輯依如下流程：
- (將地址由高至低劃分為四個部分：標籤、索引、塊內偏移、字節偏移。其中塊內偏移和字節偏移各占兩位，後者在以下操作中不使用。)
- 用索引定位到相應的緩存塊。
- 用標籤嘗試匹配該緩存塊的對應標籤值。如果存在這樣的匹配，稱為命中（Hit）；否則稱為未命中（Miss）。
- 如命中，用塊內偏移將已定位緩存塊內的特定數據段取出，送回處理器。
- 如未命中，先用此塊地址（標籤+索引）從內存讀取數據並載入到當前緩存塊，再用塊內偏移將位於此塊內的特定數據單元取出，送回處理器。這裡要注意的是，（1）讀入的數據會衝掉之前的內容。為保證數據一致性，必須先將數據塊內的現有內容寫回內存。（2）儘管處理器請求的只是一個字，緩存仍必須在讀取的時候把整個數據塊都填充滿。（3）緩存的讀取是按緩存塊大小為邊界對齊的。對於大小為16字節的緩存塊，任何因為0x0000、或0x0001、或0x0002、或0x0003造成的未命中，都會導致位於內存0x0000—0x0003的全部四個字被讀入塊中。
在右圖中，如此時處理器請求的地址在0x0020到0x0023之間，或在0x0004到0x0007之間，或在0x0528到0x052B之間，或在0x05EC到0x05EF之間，均會命中。其餘地址則全部未命中。
而處理器執行數據寫入指令時，控制邏輯依如下流程：
組相聯 編輯
直接映射 編輯
為了便於數據查找，一般規定內存數據只能置於緩存的特定區域。對於直接映射緩存，每一個內存塊地址都可通過模運算對應到一個唯一緩存塊上。注意這是一種多對一映射：多個內存塊地址須共享一個緩存區域。
其中I為緩存索引，Amb為內存塊地址，N為緩存塊總數。
使用內存塊地址而不是內存地址是因為緩存塊通常包含一組連續的內存單元數據。以緩存塊為32字節的直接映射緩存為例，內存地址Am到緩存索引的計算為
由於緩存字節數和緩存塊數均為2的冪，上述運算可以由硬件通過移位極快地完成。
N路組相聯 編輯
直接匹配緩存儘管在電路邏輯上十分簡單，但是存在顯著的衝突問題。由於多個不同的內存塊僅共享一個緩存塊，一旦發生緩存失效就必須將緩存塊的當前內容清除出去。這種做法不但因為頻繁的更換緩存內容造成了大量延遲，而且未能有效利用程序運行期所具有的時間局部性。
組相聯（Set Associativity）是解決這一問題的主要辦法。使用組相聯的緩存把存儲空間組織成多個組，每個組有若干數據塊。通過建立內存數據和組索引的對應關係，一個內存塊可以被載入到對應組內的任一數據塊上。
以右圖為例， 如使用2路組相聯，內存地址為0、8、16、24的數據均可被置於緩存第0組中兩個數據塊的任意一個；如果使用4路組相聯，內存地址為0、8、16、24的數據均可被置於緩存第0組中四個數據塊的任意一個。一般地，
其中，I為緩存索引，Am為內存地址，Nw為緩存塊內字數， Na為相聯路數， N為組數。當使用組相聯時，在通過索引定位到對應組之後，必須進一步地與所有緩存塊的標籤值進行匹配，以確定查找是否命中。這在一定程度上增加了電路複雜性，因此會導致查找速度有所降低。
此外，在不增大緩存大小的前提下單純地增加組相聯的路數，將不會改變緩存和內存的對應比例。再以右圖為例，對於2路組相聯，儘管第0組內有兩個緩存塊，但是該組現在也是內存塊1、9、17、25的目標塊。
直接匹配可以被認為是單路組相聯。經驗規則表明，在緩存小於128KB時，欲達到相同失效率，一個雙路組相聯緩存僅需相當於直接匹配緩存一半的存儲空間[1]。
全相聯 編輯
組相聯的一個極端是全相聯。這種緩存意味着內存中的數據塊可以被放置到緩存的任意區域。這種相聯完全免去了索引的使用，而直接通過在整個緩存空間上匹配標籤進行查找。 由於這樣的查找造成的電路延遲最長，因此僅在特殊場合，如緩存極小時，才會使用。
置換策略 編輯
對於組相聯緩存，當一個組的全部緩存塊都被占滿後，如果再次發生緩存失效，就必須選擇一個緩存塊來替換掉。存在多種策略決定哪個塊被替換。
顯然，最理想的替換塊應當是距下一次被訪問最晚的那個。這種理想策略無法真正實現，但它為設計其他策略提供了方向。
先進先出算法（FIFO）替換掉進入組內時間最長的緩存塊。最久未使用算法（LRU）則跟蹤各個緩存塊的使用狀況，並根據統計比較出哪個塊已經最長時間未被訪問。對於2路以上相聯，這個算法的時間代價會非常高。
對最久未使用算法的一個近似是非最近使用（NMRU）。這個算法僅記錄哪一個緩存塊是最近被使用的。在替換時，會隨機替換掉任何一個其他的塊。故稱非最近使用。相比於LRU，這種算法僅需硬件為每一個緩存塊增加一個使用位（use bit）即可。
此外，也可使用純粹的隨機替換法。測試表明完全隨機替換的性能近似於LRU[2]。
寫操作 編輯
回寫策略 編輯
為了和下級存儲（如內存）保持數據一致性，就必須把數據更新適時傳播下去。這種傳播通過回寫來完成。一般有兩種回寫策略：寫回（Write back）和寫通（Write through）。
寫回是指，僅當一個緩存塊需要被替換回內存時，才將其內容寫入內存。如果快取命中，則總是不用更新內存。為了減少內存寫操作，緩存塊通常還設有一個髒位（dirty bit），用以標識該塊在被載入之後是否發生過更新。如果一個緩存塊在被置換回內存之前從未被寫入過，則可以免去回寫操作。
寫回的優點是節省了大量的寫操作。這主要是因為，對一個數據塊內不同單元的更新僅需一次寫操作即可完成。這種內存帶寬上的節省進一步降低了能耗，因此頗適用於嵌入式系統。
| 回寫策略 | 分配策略 | 當……時 | 寫到…… |
|---|---|---|---|
| 寫回 | 分配 | 命中 | 緩存 |
| 寫回 | 分配 | 失效 | 緩存 |
| 寫回 | 非分配 | 命中 | 緩存 |
| 寫回 | 非分配 | 失效 | 內存 |
| 寫通 | 分配 | 命中 | 快取和內存 |
| 寫通 | 分配 | 失效 | 快取和內存 |
| 寫通 | 非分配 | 命中 | 快取和內存 |
| 寫通 | 非分配 | 失效 | 內存 |
寫通是指，每當緩存接收到寫數據指令，都直接將數據寫回到內存。如果此數據地址也在緩存中，則必須同時更新緩存。由於這種設計會引發造成大量寫內存操作，有必要設置一個緩衝來減少硬件衝突。這個緩衝稱作寫緩衝器（Write buffer），通常不超過4個快取Block大小。不過，出於同樣的目的，寫緩衝器也可以用於寫回型緩存。
寫通較寫回易於實現，並且能更簡單地維持數據一致性。
按寫分配與不按寫分配 編輯
當發生寫失效時，緩存可有兩種處理策略，分別稱為按寫分配（Write allocate）和不按寫分配（No-write allocate）。
按寫分配是指，先如處理讀失效一樣，將所需數據讀入緩存，然後再將數據寫到被讀入的單元。不按寫分配則總是直接將數據寫回內存。
設計緩存時可以使用回寫策略和分配策略的任意組合。對於不同組合，發生數據寫操作時的行為也有所不同。如右表所示。
地址翻譯 編輯
由於計算機程序一般使用虛擬地址，一個必須決定的設計策略是緩存的地址標籤及索引是使用虛擬地址還是物理地址。
虛緩存 編輯
一個簡單的方案就是緩存的標籤和索引均使用虛擬地址。這種緩存稱為虛緩存（virtual cache）。這種緩存的優點是僅在緩存失效時才需要進行頁面翻譯。由於緩存命中率很高，需要翻譯的次數也相對較少。
但是這種技術也存在嚴重的問題。
第一，引入虛擬地址的一個重要原因是在軟件（操作系統）級進行頁面保護，以防止進程間相互侵犯地址空間。由於這種保護是通過頁表和翻譯旁視緩衝器（TLB）中的保護位（protection bit）實現的，直接使用虛擬地址來訪問數據等於繞過了頁面保護。一個解決辦法是在緩存失效時查看TLB對應表項的保護位以確定是否可以加載缺失的數據。
第二，由於不同進程使用相同的虛擬地址空間，在切換進程後會出現整個緩存都不再對應新進程的有效數據。如果前後兩個進程使用了相同的地址區間，就可能會造成緩存命中，卻訪問了錯誤的地址，導致程序錯誤。有兩個解決辦法：（1）進程切換後清空緩存。代價過高。（2）使用進程標識符（PID）作為緩存標籤的一部分，以區分不同進程的地址空間。
第三，別名問題（Alias）。由於操作系統可能允許頁面別名，即多個虛擬頁面映射至同一物理頁面，使用虛擬地址做標籤將可能導致一份數據在緩存中出現多份拷貝的情形。這種情況下如果對其中一份拷貝作出修改，而其他拷貝沒有同步更新，則數據喪失整合性，導致程序錯誤。有兩個解決辦法：（1）硬件級反別名。當緩存載入目標數據時，確認緩存內沒有緩存塊的標籤是此地址的別名。如果有則不載入，而直接返回別名緩存塊內的數據。（2）頁面着色（Page Coloring）。這種技術是由操作系統對頁面別名作出限制，使指向同一頁面的別名頁面具有相同的低端地址。這樣，只要緩存的索引範圍足夠小，就能保證在緩存中決不會出現來自不同別名頁面的數據。
第四，輸入輸出問題。由於輸入輸出系統通常只使用物理地址，虛緩存必須引入一種逆映射技術來實現虛擬地址到物理地址的轉換。
實緩存 編輯
實緩存（physical cache）完全使用物理地址做緩存塊的標籤和索引，故地址翻譯必須在訪問緩存之前進行。這種傳統方法所以可行的一個重要原因是TLB的訪問周期非常短（因為本質上TLB也是一個緩存），因而可以被納入流水線。
但是，由於地址翻譯發生在緩存訪問之前，會比虛緩存更加頻繁地造成TLB。（相比之下，虛緩存僅在本身失效的前提下才會訪問TLB，進而有可能引發TLB失效）實緩存在運行中存在這樣一種可能：首先觸發了一個TLB失效，然後從頁表中更換TLB表項（假定頁表中能找到）。然後再重新訪問TLB，翻譯地址，最後發現數據不在緩存中。[3]
虛索引、實標籤緩存 編輯
一個折中方案是同時使用虛索引和實標籤（virtually indexed, physically tagged）。這種緩存利用了頁面技術的一個特徵，即虛擬地址和物理地址享有相同的頁內偏移值（page offset）。這樣，可以使用頁內偏移作為緩存索引，同時使用物理頁面號作為標籤。這種混合方式的好處在於，其既能有效消除諸如別名引用等純虛緩存的固有問題，又可以通過對TLB和緩存的並行訪問來縮短流水線延遲。
這種技術的一個缺點是，在使用直接匹配緩存的前提下，緩存大小不能超過頁面大小，否則頁面偏移範圍就不足以覆蓋緩存索引範圍。這個弊端可以通過提高組相聯路數來改善。
多級緩存 編輯
引入動機 編輯
介於處理器和內存二者之間的緩存有兩個天然衝突的性能指標：速度和容積。如果只向處理器看齊而追求速度，則必然要靠減少容積來換取訪問時間；如果只向內存看齊而追求容積，則必然以增加處理器的訪問時間為犧牲。這種矛盾促使人們考慮使用多級緩存。
在一個兩級緩存體系中，一級緩存靠近處理器一側，二級緩存靠近內存一側。當一級緩存發生失效時，它向二級緩存發出請求。如果請求在二級緩存上命中，則數據交還給一級緩存；如失效，二級緩存進一步向內存發出請求。對於三級緩存可依此類推。
通常，更接近內存的緩存有着更大容積，但是速度也更慢。值得注意的是，無論如何，低級緩存的局部命中率總是低於高級緩存。這是因為數據的時空局部性在一級緩存上基本上已經利用殆盡。
設計考慮 編輯
雖然功能類似，但不同級別的緩存在設計和實現上也有不同之處。
儘管一般而言，在存儲體系結構中低級存儲總是包含高級存儲的全部數據，但對於多級緩存則未必。相反地，存在一種多級排他性（Multilevel exclusion）的設計。此種設計意指高級緩存中的內容和低級緩存的內容完全不相交。這樣，如果一個高級緩存請求失效，並在次級緩存中命中的話，次級緩存會將命中數據和高級緩存中的一項進行交換，以保證排他性。
多級排他性的好處是在存儲預算有限的前提下可以讓低級緩存更多地存儲數據。否則低級緩存的大量空間將不得不用於覆蓋高級緩存中的數據，這無益於提高低級緩存的命中率。
當然，也可以如內存對緩存般，使用多級包容性（Multilevel inclusion）設計。這種設計的優點是比較容易方便查看緩存和內存間的數據一致性，因為僅檢查最低一級緩存即可。對於多級排他性緩存這種檢查必須在各級上分別進行。這種設計的一個主要缺點是，一旦低級緩存由於失效而被更新，就必須相應更新在高級緩存上所有對應的數據。因此，通常令各級緩存的緩存塊大小一致，從而減少低級對高級的不必要更新。
此外，各級緩存的寫策略也不相同。對於一個兩級緩存系統，一級緩存可能會使用寫通來簡化實現，而二級緩存使用寫回確保數據一致性。
性能評估 編輯
性能評估模型 編輯
評估緩存的性能通常使用平均內存訪問時間（Average Memory Access Time, AMAT）這一指標。在一個簡化模型中，該值可依下式求得：
式中三項的意義：
- 為命中時間（Hit Time）：從定位緩存塊、經標籤比較並選中，一直到傳回數據所需的時間。
- 為失效率（Miss Rate）：在特定次數的內存訪問中，發生緩存失效次數所占的比重。
- 為失效代價（Miss Penalty）：從定位緩存塊、經標籤比較判定失效，然後再從內存中定位數據並載入緩存，最後直到把目標數據返回所需的時間。
失效分析 編輯
Mark Hill在對緩存失效的情形進行研究後給出了三種緩存失效的原因，稱為3C。
- 強制失效（Compulsory miss），又稱冷失效（Cold start miss），指地址第一次被引用時的失效。改變緩存大小或相聯度都不能影響這類失效。
- 容量失效（Capacity miss），是指某段數據由於緩存已滿而被逐出後，當緩存再一次企圖訪問此數據時造成的失效。改變緩存塊大小或相聯度都不能影響這類失效。
- 衝突失效（Conflict miss），是指內存中不同的塊被映射到緩存中相同的組或塊，導致訪問時產生衝突而失效。也叫Collision misses 或者 Interference misses。這類失效對於全相聯緩存並不存在。
此外，在多處理器系統中，還存在為保證各處理器緩存之間的數據一致性而進行數據清空/無效化所造成的失效。這類失效稱為一致失效（Coherency miss）。
優化技術 編輯
根據AMAT的計算式，可以看出優化緩存可從三個方面入手：一、減少命中時間；二、降低失效率；三、減輕失效代價。此外，增加緩存訪問帶寬也能有效降低AMAT。
存在多種優化技術來實現削減三個構成變量對AMAT造成的影響。應注意的是，由於緩存的內在性質，某些技術可能在減少一個因子的同時，增加了另一個因子。
減少命中時間 編輯
虛索引、實標籤緩存 編輯
理論上，完全使用虛擬地址可以獲得更快的緩存訪問速度，因為這樣僅在緩存失效時才會進行地址翻譯。但是，如前所述，這種純虛地址緩存由於繞開了操作系統對進程訪問地址的軟件控制，會存在不少問題。
為了能接近虛緩存的訪問速度，又能避開虛緩存帶來的種種問題，引入了所謂虛索引、實標籤緩存（virtually indexed, physically tagged）。這種結構的緩存可以令地址翻譯和緩存查詢並發進行，大大加快了緩存的訪問速度。詳見地址翻譯一節。
小而簡單的緩存 編輯
由於電路延遲很大程度上取決於存儲芯片的大小，所以可考慮使用較小容量的緩存以保證最短的訪問周期。這麼做的另一個好處是，由於一級緩存足夠小，可以把二級緩存的全部或部分也集成到CPU芯片上，從而減少了二級緩存的命中時間。
AMD從K6到Opteron連續三代CPU的一級緩存容量都沒有任何增長（均為64KB）正是基於這個原因[4]。
另一方面，考慮使用簡單的緩存，如直接匹配緩存，也可較組相聯緩存減少命中時間。
路預測 編輯
所謂路預測（Way prediction），是指在組相聯緩存中，跟蹤同一組內不同緩存塊的使用情況，然後在訪問到來時，不經比較直接返回預測的緩存塊。當然，標籤比較仍然會進行，並且如果發現比較結果不同於預測結果，就會重新送出正確的緩存塊。也就是說，錯誤預測會造成一個緩存塊長度的延遲。
模擬表明路預測的準確率超過85%[5]。這種技術非常適合於投機執行（Speculative Execution）處理器，因為這種處理器有完善的機制來保證在投機失敗之後取消已經派發的指令。
追蹤緩存 編輯
與一般的指令緩存存儲靜態連續地址不同，追蹤緩存（Trace Cache）存儲的是基於執行歷史的動態地址序列。這實際上是把分支預測的結果用在了緩存上。由於只存儲沿某一特定分支路徑才會遇到的指令，這種緩存可比傳統緩存更節省空間。
追蹤緩存的缺點是實現複雜，因為必須設法連續存儲的數據並不會按照2的冪次字長對齊。此外，對於不同執行路徑要分開存儲。如果這些執行路徑中存在相同地址的指令，這些指令就只好被分別存到兩個地方。這反而造成了低效的空間利用。
Intel的Pentium 4處理器使用了這一複雜技術。值得一提的是，Pentium 4追蹤緩存存儲的不是從內存抓取的原始指令，而是已經過解碼的微操作，從而進一步節省掉了指令解碼上要花的時間。
增加訪問帶寬 編輯
緩存流水線化 編輯
將一級緩存併入流水線是一般做法。這種做法可行性在於一級緩存的訪問時間通常都極短，可能只有一到數個CPU周期。此外，由於TLB也是一種高速緩存硬件，故也可以納入流水線。
非阻塞緩存 編輯
一般而言，當緩存發生失效時，處理器必須停滯（stall），等待緩存將數據從次級存儲中讀取出來。
當時，對於跨序執行（Out-of-order Execution）處理器，由於多條指令在不同處理單元中並發執行，某一條指令引發的緩存失效應該只造成其所在處理單元的停滯，而不影響其他處理單元和指令派發單元繼續流水。因此，有必要設計這樣一種緩存，使之能夠在處理緩存失效的同時，繼續接受來自處理器的訪問請求。這稱為非阻塞緩存（Non-blocking cache）。
降低失效率 編輯
使用更大的數據塊 編輯
使用大數據塊有助於利用空間局部性降低失效率，但其代價是更高的失效代價。這是因為，一旦失效，就必須把整個數據塊都重新填滿。
使用更大的緩存 編輯
單純增大緩存的容量也是降低失效率的一個辦法。不過顯然這也增大了命中時間。
高組相聯緩存 編輯
使用多路組相聯可以減少衝突失效。但其後果是緩存電路邏輯複雜化，故增大了命中時間。
編譯器優化 編輯
存在多種編譯器優化技術來間接影響緩存的使用模式。下面僅舉幾例，且均假定編譯器採用行主序（Row-major order）存儲數組：
1. 循環交換（Loop Interchange）
考慮一個對二維數組a[100][5000]的循環處理
a[100][5000] = ... //初始化
for (j = 0; j < 5000; j = j + 1) {
for (i = 0; i < 100; i = i + 1)
a[i][j] = 2 * a[i][j];
}
如果源代碼的外循環遍歷行，而內循環遍歷列，則總是會造成大量的緩存失效。這是因為當失效時，緩存從內存中抓取的整個數據塊幾乎都是同行不同列的數據，而這些數據在接下來的內循環中完全無法被重複利用。
通過循環交換改進如下
a[100][5000] = ... //初始化
for (i = 0; i < 100; i = i + 1) {
for (j = 0; j < 5000; j = j + 1)
a[i][j] = 2 * a[i][j];
}
這樣，緩存因為a[i][0]失效而從內存中抓取的數據塊實際上覆蓋了a[i][0]到a[i][7]的全部數據（假定使用32字節大小的緩存塊，每個整型值占四字節）。這樣後邊連續七次內循環均可告命中。
2. 循環合併（Loop fusion）
考慮下邊的代碼
a[1000] = ... //初始化
for (i = 0; i < 1000; i = i + 1)
a[i] = 2 * a[i];
for (i = 0; i < 1000; i = i + 1)
b[i] = a[i] + CONSTANT;
如果編譯器可以證明兩個循環體可以合併到一個基本塊而不影響程序結果，則應該進行合併。這是因為，通過合併，原來第二個循環的語句在訪問內存時必然會命中。
合併後的代碼
a[1000] = ... //初始化
for (i = 0; i < 1000; i = i + 1) {
a[i] = 2 * a[i];
b[i] = a[i] + CONSTANT;//对a[i]的访问必然命中缓存
}
3. 循環分塊（Blocking）
當循環遍歷的內存範圍很大（例如一個多維數組）時，由於緩存容積有限，可能會導致每次遍歷結束時留下的緩存布局完全無法被接下來的一次遍歷利用。這種情形下對循環進行分塊就十分有意義。
假設現在使用了一個非常小的全相聯緩存，只有四個緩存段，每個16字節。二維整型數組b和c的大小均為1024*1024，並被存儲上內存的連續地址上。由於每個整數占4個字節，故在這個緩存最多只能容納16個整數。假定該緩存使用LRU置換策略。首先考慮未經過優化的代碼。這個代碼段遍歷整個矩陣，每次遍歷過程中交替訪問由i和j分別指定的向量b[i][0]-b[i][1023]和c[0][j]-c[1023][j]。
b[1024] = ... //初始化
c[1024] = ... //初始化
for (i = 0; i < 1024; i = i + 1) {
for (j = 0; j < 1024; j = j + 1) {
for (k = 0; k < 1024; k = k + 1)
... = b[i][k] + c[k][j];
}
}
由於緩存極小，這段代碼效率十分低。考慮當i=0、j=0時，最內循環最後一次遍歷中，在訪問完b[i][k]（實際上是b[0][1023]）之後，但還沒有訪問c[k][j]（實際上是c[1023][0]）的情形，緩存內容如下圖所示。
之後，訪問c[1023][0]，緩存被刷新為
這樣一個結果無疑對於下一次遍歷（i=0、j=1）毫無價值。因為在k自增到4之前，所有數據都無法被重複利用，結果只能被換出。但如果改成
b[1024] = ... //初始化
c[1024] = ... //初始化
int B = 4;
for (jj = 0; jj < 1024; jj = jj + B) {
for (kk = 0; kk < 1024; kk = kk + B) {
for (i = 0; i < 1024; i = i + 1) {
for (j = jj; j < min(jj + B, 1024); j = j + 1) {
for (k = kk; k < min(kk + B, 1024); k = k + 1)
... = b[i][k] + c[k][j];
}
}
}
}
再次考慮當jj=0、kk=0、i=0、j=0時，最內循環最後一次遍歷中，在訪問完b[i][k]（實際上是b[0][3]）之後，但還沒有訪問c[k][j]（實際上是c[3][0]）的情形，緩存內容如下圖所示。
之後，訪問c[3][0]，緩存被刷新為
這樣的結果對於下一次遍歷（jj=0、kk=0、i=0、j=1）就十分有價值，因為所需數據的大部分，包括b[0][0]-b[0][3]和c[1][1]-c[3][1]，全都已在緩存中。
此外，還有數組合併（Array merge）、循環分解（Loop fission）、分支取直（Branch Straightening）等多種技術。
預取 編輯
為了利用空間局部性，同時也為了覆蓋傳輸延遲，可以隨機性地在數據被用到之前就將其取入緩存。這一技術稱為預取（Prefetch）。本質上講，加載整個緩存塊其實即是一種預取。
預取可以通過硬件或軟件控制。典型的硬件指令預取會在緩存因失效從內存載入一個塊的同時，把該塊之後緊鄰的一個塊也傳輸過來。第二個塊不會直接進入緩存，而是被排入指令流緩衝器（Instruction Stream Buffer）中。之後，當第二個內存訪問指令到來時，會並行嘗試從緩存和流緩衝器中讀取。如果該數據恰好在流緩衝器中，則取消緩存訪問指令，並將返回流緩衝器中的數據。同時，發出起一次新的預取。如果數據並不在流緩衝器中，則需要將緩衝器清空。
軟件控制則多由編譯器進行。指令集會提供預取指令供編譯器優化時使用。編譯器則負責分析代碼，並把預取指令適當地插入其中。這類指令直接把目標預取數據載入緩存。
在使用預取技術時，必須妥善考慮進行時機和實施強度。如果過早地進行預取，則有可能在預取數據被用到之前就已經因為衝突置換被清除。如果預取得太多或太頻繁，則預取數據有可能將那些更加確實地會被用到的數據取代出緩存。
減輕失效代價 編輯
多級緩存 編輯
相對於單級緩存，多級緩存的性能模型可以下式表示：
由於全局失效率等於兩個局部失效率 和 之積，故使用多級緩存降低了失效率。
讀失效優先策略 編輯
對於使用寫緩衝器的緩存，當出現讀失效時會遇到一個問題：所要讀取的數據已經被修改，但是還沒有更新到內存。也就是說，新數據還在寫緩衝器中。
解決方案有二：一、等待，直到寫緩衝器清空。這種方法顯然效率不高。二、在讀緩存的同時檢查寫緩衝器，確認最新數據是否在已在寫緩衝器中。如果有則直接從寫緩衝器返回。這種方法的本質是相比於回寫操作，賦予讀失效處理更高的優先級。
關鍵詞優先 編輯
如前述，緩存從內存讀取數據時需要把整個緩存塊都填滿，再返回偏移指定單元給處理器。但其實可以做這樣的優化，即令緩存從對應內存塊的相應偏移位置，也就是關鍵詞（Critical word），開始讀數據，然後一旦第一個數據單元被傳回，就立即將其交給處理器。
另有一個叫做早重啟（Early Restart）的類似技術。這種技術仍然從內存塊的起始位置按常序傳輸數據，但是一旦關鍵詞數據返回，就將其傳回處理器。可見，這種方法在減少處理器停滯上遜於關鍵詞優先法。
合併寫緩衝器 編輯
寫緩衝器通常可以令1到4個緩存塊排隊等待回寫。但事實上大部分寫操作都只是針對緩存塊的某一個單元進行的。同時，因為經常會出現對一塊連續內存按序進行寫操作（比如初始化一個數組），所以可以考慮將連續的寫操作合併為一個寫操作。
特殊的緩存結構 編輯
指令-數據分離緩存 編輯
由於流水線會在指令抓取和內存訪問兩個階段上訪問內存，如不增加緩存端口將會造成結構性冒險（Structural hazard）。一種辦法是使用兩片一級緩存，分別服務於指令抓取和內存訪問兩個階段。這樣，前一個一級緩存稱為指令緩存，後一個則為數據緩存。從處理器的觀點來看，這相當於採用了哈佛架構的存儲系統。
受害者緩存 編輯
所謂受害者緩存（Victim Cache），是一個與直接匹配或低相聯緩存並用的、容量很小的全相聯緩存。當一個數據塊被逐出緩存時，並不直接丟棄，而是暫先進入受害者緩存。如果受害者緩存已滿，就替換掉其中一項。當進行緩存標籤匹配時，在與索引指向標籤匹配的同時，並行查看受害者緩存，如果在受害者緩存發現匹配，就將其此數據塊與緩存中的不匹配數據塊做交換，同時返回給處理器。
受害者緩存的意圖是彌補因為低相聯度造成的頻繁替換所損失的時間局部性。
硬件實現 編輯
芯片技術 編輯
緩存芯片通常採用速度較快的SRAM。一級緩存一般與處理器同片封裝，二級緩存則不一定。一種實現是把標籤存儲集成到片內，而把數據存儲放到片外。
控制器 編輯
歷史和未來 編輯
緩存的發展史 編輯
在科研領域，C. J. Conti等人於1968年在描述360/85和360/91系統性能差異時最早引入了高速緩存（cache）一詞[7]。Alan Jay Smith於1982年的一篇論文中引入了空間局部性和時間局部性的概念。Mark Hill在1987年發明了3C（Compulsory, Capacity, Conflict）衝突分類。[8]
最早介紹非阻塞緩存的論文之一來自David Kroft（1981年）。1990年Norman Paul Jouppi在一篇論文中介紹了受害者緩存並研究了使用流緩衝器進行預取的性能。[8]
在工業領域，最早的有記載的緩存出現在IBM的360/85系統上[9]。
Intel的x86架構CPU從386開始引入使用SRAM技術的主板緩存，大小從16KB到64KB不等。486引入兩級緩存。其中8KBL1緩存和CPU同片，而L2緩存仍然位於主板上，大小可達268KB。將二級緩存置於主板上在此後十餘年間一直設計主流。但是由於SDRAM技術的引入，以及CPU主頻和主板總線頻率的差異不斷拉大，主板緩存在速度上的對內存優勢不斷縮水。因此，從Pentium Pro起，二級緩存開始和處理器一起封裝，頻率亦與CPU相同（稱為全速二級緩存）或為CPU主頻的一半（稱為半速二級緩存）。
AMD則從K6-III開始引入三級緩存。基於Socket 7接口的K6-III擁有64KB和256KB的同片封裝兩級緩存，以及可達2MB的三級主板緩存。
還有CPU將三級緩存全部集成到CPU芯片上。多核CPU通常為每個核配有獨享的一級和二級緩存，以及各核之間共享的三級緩存。
當今的研究方向 編輯
早期的緩存設計主要考慮的是存儲器成本和平均訪問速度。而許多最新的緩存設計同時關注了能耗、容錯等其它指標。
在進行緩存性能研究時，通常使用軟件模擬技術。有許多這樣的開源軟件，包括CACTI（Norm Paul Jouppi等人），以及SimpleScalar（Todd Austin， 威斯康星大學麥迪遜分校）等。
參見 編輯
注釋 編輯
- ^ Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第C-28頁
- ^ Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第C-10頁
- ^ Computer Organization And Design: The Hardware/Software Interface，第四版，Morgan Koffmann出版，第507頁
- ^ Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第294頁
- ^ Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第295頁
- ^ Computer Organization And Design: The Hardware/Software Interface，第四版，Morgan Koffmann出版，第529頁
- ^ Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第K-52頁
- ^ 8.0 8.1 Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第K-53頁
- ^ IBM System/360 Model 85 Functional Characteristics, 第二版 （頁面存檔備份，存於網際網路檔案館），IBM