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（ $32-\log _{2}(4096\div 16)-\log _{2}16=20$ ）。

此外，每個快取塊還可對應若干標誌位，包括有效位（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之間，均會命中。其餘地址則全部未命中。

而處理器執行資料寫入指令時，控制邏輯依如下流程：

用索引定位到相應的快取塊。
用標籤嘗試匹配該快取塊的對應標籤值。其結果為命中或未命中。
如命中，用塊內偏移定位此塊內的目標字。然後直接改寫這個字。
如未命中，依系統設計不同可有兩種處理策略，分別稱為按寫分配（Write allocate）和不按寫分配（No-write allocate）。如果是按寫分配，則先如處理讀未命中一樣，將未命中資料讀入快取，然後再將資料寫到被讀入的字單元。如果是不按寫分配，則直接將資料寫回記憶體。

組相聯

直接映射

為了便於資料查找，一般規定記憶體資料只能置於快取的特定區域。對於直接映射快取，每一個記憶體塊地址都可通過模運算對應到一個唯一快取塊上。注意這是一種多對一映射：多個記憶體塊地址須共享一個快取區域。

I=A_{mb}\mod N

其中I為快取索引，Amb為記憶體塊地址，N為快取塊總數。

使用記憶體塊地址而不是記憶體地址是因為快取塊通常包含一組連續的記憶體單元資料。以快取塊為32位元組的直接映射快取為例，記憶體地址Am到快取索引的計算為

I=\left(A_{m}\div 32\right)\mod N

由於快取位元數和快取塊數均為2的冪，上述運算可以由硬件通過移位極快地完成。

N路組相聯

直接匹配快取儘管在電路邏輯上十分簡單，但是存在顯著的衝突問題。由於多個不同的記憶體塊僅共享一個快取塊，一旦發生快取失效就必須將快取塊的當前內容清除出去。這種做法不但因為頻繁的更換快取內容造成了大量延遲，而且未能有效利用程式運行期所具有的時間局部性。

組相聯（Set Associativity）是解決這一問題的主要辦法。使用組相聯的快取把儲存空間組織成多個組，每個組有若干資料塊。通過建立記憶體資料和組索引的對應關係，一個記憶體塊可以被載入到對應組內的任一資料塊上。

以右圖為例，如使用2路組相聯，記憶體地址為0、8、16、24的資料均可被置於快取第0組中兩個資料塊的任意一個；如果使用4路組相聯，記憶體地址為0、8、16、24的資料均可被置於快取第0組中四個資料塊的任意一個。一般地，

I=\left(A_{m}\div N_{w}\div N_{a}\right)\mod N

其中，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）這一指標。在一個簡化模型中，該值可依下式求得：

AMAT=T_{hit} MR\times MP

式中三項的意義：

不同大小、不同組相聯快取運行SPEC CPU2000整數程式的失效率比較。注意每條曲線均呈三段式下降，這實際上分別體現了容量失效（容量過小時）、衝突失效和強制失效（容量逼近無限大時）。

$T_{hit}$ 為命中時間（Hit Time）：從定位快取塊、經標籤比較並選中，一直到傳回資料所需的時間。
$MR$ 為失效率（Miss Rate）：在特定次數的記憶體存取中，發生快取失效次數所佔的比重。
$MP$ 為失效代價（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）中。之後，當第二個記憶體存取指令到來時，會並行嘗試從快取和流緩衝器中讀取。如果該資料恰好在流緩衝器中，則取消快取存取指令，並將返回流緩衝器中的資料。同時，發出起一次新的預取。如果資料並不在流緩衝器中，則需要將緩衝器清空。

軟件控制則多由編譯器進行。指令集會提供預取指令供編譯器最佳化時使用。編譯器則負責分析代碼，並把預取指令適當地插入其中。這類指令直接把目標預取資料載入快取。

在使用預取技術時，必須妥善考慮進行時機和實施強度。如果過早地進行預取，則有可能在預取資料被用到之前就已經因為衝突置換被清除。如果預取得太多或太頻繁，則預取資料有可能將那些更加確實地會被用到的資料取代出快取。

減輕失效代價

多級快取

相對於單級快取，多級快取的性能模型可以下式表示：

AMAT=T_{L1.hit} MR_{L1}\times MP_{L1}

MP_{L1}=T_{L2.hit} MR_{L2}\times MP_{L2}

由於全局失效率等於兩個局部失效率 $MR_{L1}$ 和 $MR_{L2}$ 之積，故使用多級快取降低了失效率。

讀失效優先策略

合併寫緩衝器。注意每個字前都有一個有效位，用於標識跟在此位置後的字是否需要寫入記憶體。

對於使用寫緩衝器的快取，當出現讀失效時會遇到一個問題：所要讀取的資料已經被修改，但是還沒有更新到記憶體。也就是說，新資料還在寫緩衝器中。

解決方案有二：一、等待，直到寫緩衝器清空。這種方法顯然效率不高。二、在讀快取的同時檢查寫緩衝器，確認最新資料是否在已在寫緩衝器中。如果有則直接從寫緩衝器返回。這種方法的本質是相比於回寫操作，賦予讀失效處理更高的優先級。

關鍵詞優先

如前述，快取從記憶體讀取資料時需要把整個快取塊都填滿，再返回偏移指定單元給處理器。但其實可以做這樣的最佳化，即令快取從對應記憶體塊的相應偏移位置，也就是關鍵詞（Critical word），開始讀資料，然後一旦第一個資料單元被傳回，就立即將其交給處理器。

另有一個叫做早重啟（Early Restart）的類似技術。這種技術仍然從記憶體塊的起始位置按常序傳輸資料，但是一旦關鍵詞資料返回，就將其傳回處理器。可見，這種方法在減少處理器停滯上遜於關鍵詞優先法。

合併寫緩衝器

寫緩衝器通常可以令1到4個快取塊排隊等待回寫。但事實上大部分寫操作都只是針對快取塊的某一個單元進行的。同時，因為經常會出現對一塊連續記憶體按序進行寫操作（比如初始化一個數組），所以可以考慮將連續的寫操作合併為一個寫操作。

特殊的快取結構

指令-資料分離快取

由於管線會在指令抓取和記憶體存取兩個階段上存取記憶體，如不增加快取端口將會造成結構性冒險（Structural hazard）。一種辦法是使用兩片一級快取，分別服務於指令抓取和記憶體存取兩個階段。這樣，前一個一級快取稱為指令快取，後一個則為資料快取。從處理器的觀點來看，這相當於採用了哈佛架構的儲存系統。

受害者快取

所謂受害者快取（Victim Cache），是一個與直接匹配或低相聯快取並用的、容量很小的全相聯快取。當一個資料塊被逐出快取時，並不直接丟棄，而是暫先進入受害者快取。如果受害者快取已滿，就替換掉其中一項。當進行快取標籤匹配時，在與索引指向標籤匹配的同時，並行查看受害者快取，如果在受害者快取發現匹配，就將其此資料塊與快取中的不匹配資料塊做交換，同時返回給處理器。

受害者快取的意圖是彌補因為低相聯度造成的頻繁替換所損失的時間局部性。

硬件實作

晶片技術

快取晶片通常採用速度較快的SRAM。一級快取一般與處理器同片封裝，二級快取則不一定。一種實作是把標籤儲存集成到片內，而把資料儲存放到片外。

控制器

可以使用有限狀態機實作簡易的快取控制器。^[6]

歷史和未來

快取的發展史

在科研領域，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，威斯康星大學麥迪遜分校）等。

參見

分支預測器
快取
快取文件置換機制
快取一致性
快取控制指令
快取層次結構（英語：Cache hierarchy）
快取放置策略（英語：Cache placement policies）
快取預取（英語：Cache prefetching）
Dinero（英語：Dinero (cache simulator)）（威斯康星大學開發的快取模擬器）
指令單元（英語：Instruction unit）
存取局部性
記憶化
記憶體階層
微操作
Scratchpad RAM（英語：Scratchpad RAM）
和尋址譯碼器（英語：Sum-addressed decoder）
寫緩衝區（英語：Write buffer）

註釋

^ 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

[1] Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第C-28頁

[2] Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第C-10頁

[3] Computer Organization And Design: The Hardware/Software Interface，第四版，Morgan Koffmann出版，第507頁

[4] Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第294頁

[5] Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第295頁

[6] Computer Organization And Design: The Hardware/Software Interface，第四版，Morgan Koffmann出版，第529頁

[7] Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第K-52頁

[#1-8] 8.0 ^8.1 Computer Architecture: A Quantitative Approach，第四版，Morgan Koffmann出版，第K-53頁

[9] IBM System/360 Model 85 Functional Characteristics, 第二版（頁面存檔備份，存於互聯網檔案館），IBM

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]