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）等。這些位在保證正確性、排除衝突、最佳化性能等方面起著重要作用。

全相聯

組相聯的一個極端是全相聯。這種快取意味著記憶體中的資料塊可以被放置到快取的任意區域。這種相聯完全免去了索引的使用，而直接通過在整個快取空間上匹配標籤進行查找。
由於這樣的查找造成的電路延遲最長，因此僅在特殊場合，如快取極小時，才會使用。

置換策略

對於組相聯快取，當一個組的全部快取塊都被占滿後，如果再次發生快取失效，就必須選擇一個快取塊來替換掉。存在多種策略決定哪個塊被替換。
顯然，最理想的替換塊應當是距下一次被存取最晚的那個。這種理想策略無法真正實作，但它為設計其他策略提供了方向。
先進先出算法（FIFO）替換掉進入組內時間最長的快取塊。最久未使用算法（LRU）則跟蹤各個快取塊的使用狀況，並根據統計比較出哪個塊已經最長時間未被存取。對於2路以上相聯，這個算法的時間代價會非常高。
對最久未使用算法的一個近似是非最近使用（NMRU）。這個算法僅記錄哪一個快取塊是最近被使用的。在替換時，會隨機替換掉任何一個其他的塊。故稱非最近使用。相比於LRU，這種算法僅需硬體為每一個快取塊增加一個使用位（use bit）即可。
此外，也可使用純粹的隨機替換法。測試表明完全隨機替換的性能近似於LRU。

按寫分配與不按寫分配

當發生寫失效時，快取可有兩種處理策略，分別稱為按寫分配（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，翻譯地址，最後發現資料不在快取中。

虛索引、實標籤快取

一個折中方案是同時使用虛索引和實標籤（virtually indexed, physically tagged）。這種快取利用了頁面技術的一個特徵，即虛擬地址和物理地址享有相同的頁內偏移值（page offset）。這樣，可以使用頁內偏移作為快取索引，同時使用物理頁面號作為標籤。這種混合方式的好處在於，其既能有效消除諸如別名引用等純虛快取的固有問題，又可以通過對TLB和快取的並行存取來縮短管線延遲。
這種技術的一個缺點是，在使用直接匹配快取的前提下，快取大小不能超過頁面大小，否則頁面偏移範圍就不足以覆蓋快取索引範圍。這個弊端可以通過提高組相聯路數來改善。

設計考慮

雖然功能類似，但不同級別的快取在設計和實作上也有不同之處。
儘管一般而言，在記憶體階層結構中低級儲存總是包含高級儲存的全部資料，但對於多級快取則未必。相反地，存在一種多級排他性（Multilevel exclusion）的設計。此種設計意指高級快取中的內容和低級快取的內容完全不相交。這樣，如果一個高級快取請求失效，並在次級快取中命中的話，次級快取會將命中資料和高級快取中的一項進行交換，以保證排他性。
多級排他性的好處是在儲存預算有限的前提下可以讓低級快取更多地儲存資料。否則低級快取的大量空間將不得不用於覆蓋高級快取中的資料，這無益於提高低級快取的命中率。
當然，也可以如記憶體對快取般，使用多級包容性（Multilevel inclusion）設計。這種設計的優點是比較容易方便查看快取和記憶體間的資料一致性，因為僅檢查最低一級快取即可。對於多級排他性快取這種檢查必須在各級上分別進行。這種設計的一個主要缺點是，一旦低級快取由於失效而被更新，就必須相應更新在高級快取上所有對應的資料。因此，通常令各級快取的快取塊大小一致，從而減少低級對高級的不必要更新。
此外，各級快取的寫策略也不相同。對於一個兩級快取系統，一級快取可能會使用寫通來簡化實作，而二級快取使用寫回確保資料一致性。

最佳化技術

根據AMAT的計算式，可以看出最佳化快取可從三個方面入手：一、減少命中時間；二、降低失效率；三、減輕失效代價。此外，增加快取存取頻寬也能有效較低AMAT。
存在多種最佳化技術來實作削減三個構成變量對AMAT造成的影響。應注意的是，由於快取的內在性質，某些技術可能在減少一個因子的同時，增加了另一個因子。

虛索引、實標籤快取

理論上，完全使用虛擬地址可以獲得更快的快取存取速度，因為這樣僅在快取失效時才會進行地址翻譯。但是，如前所述，這種純虛地址快取由於繞開了作業系統對行程存取地址的軟體控制，會存在不少問題。
為了能接近虛快取的存取速度，又能避開虛快取帶來的種種問題，引入了所謂虛索引、實標籤快取（virtually indexed, physically tagged）。這種結構的快取可以令地址翻譯和快取查詢並發進行，大大加快了快取的存取速度。詳見地址翻譯一節。

小而簡單的快取

由於電路延遲很大程度上取決於儲存晶片的大小，所以可考慮使用較小容量的快取以保證最短的存取周期。這麼做的另一個好處是，由於一級快取足夠小，可以把二級快取的全部或部分也集成到CPU晶片上，從而減少了二級快取的命中時間。
AMD從K6到Opteron連續三代CPU的一級快取容量都沒有任何增長（均為64KB）正是基於這個原因。
另一方面，考慮使用簡單的快取，如直接匹配快取，也可較組相聯快取減少命中時間。

路預測

所謂路預測（Way prediction），是指在組相聯快取中，跟蹤同一組內不同快取塊的使用情況，然後在存取到來時，不經比較直接返回預測的快取塊。當然，標籤比較仍然會進行，並且如果發現比較結果不同於預測結果，就會重新送出正確的快取塊。也就是說，錯誤預測會造成一個快取塊長度的延遲。
模擬表明路預測的準確率超過85%。這種技術非常適合於投機執行（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）一詞。Alan Jay Smith於1982年的一篇論文中引入了空間局部性和時間局部性的概念。Mark Hill在1987年發明了3C（Compulsory, Capacity, Conflict）衝突分類。
最早介紹非阻塞快取的論文之一來自David Kroft（1981年）。1990年Norman Paul Jouppi在一篇論文中介紹了受害者快取並研究了使用流緩衝器進行預取的性能。
在工業領域，最早的有記載的快取出現在IBM的360/85系統上。
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， 威斯康星大學麥迪遜分校）等。