微處理器設計/快取

微處理器設計

快取

快取是一小部分記憶體，其執行速度快於主記憶體。資料從主記憶體移動到快取，以便可以更快地訪問它。現代晶片設計人員將多個快取放在與處理器相同的晶片上；設計人員通常分配給快取的芯片面積大於 CPU 本身。提高晶片效能通常是透過提高晶片快取的速度和效率來實現的。

快取記憶體效能是實現高處理器效能的最重要因素。

快取的工作原理是儲存外部記憶體內容的一個小子集，通常是按其原始順序儲存的。經常使用的資料和指令（例如資料陣列或小型指令迴圈）儲存在快取中，並且可以快速讀取，而無需訪問主記憶體。快取以與處理器其餘部分相同的速度執行，這通常比外部 RAM 的執行速度快得多。這意味著如果資料在快取中，則訪問它的速度比訪問記憶體快。

快取有助於加快處理器的速度，因為它基於區域性性原理。

在本章中，我們將討論幾種可能的快取安排，按複雜度遞增的順序

• 無快取，單 CPU，物理定址
• 單級快取，單 CPU，物理定址
• 快取層次結構：L1、L2、L3 等。
• 快取替換策略：關聯性、隨機替換、LRU 等。
• 分體快取：I 快取和 D 快取，位於統一快取層次結構之上
• 使用多個 CPU 進行快取
• 支援虛擬記憶體定址的快取硬體
• TLB 作為一種快取
• 單地址空間虛擬記憶體定址如何與快取硬體互動
• 每個程序的虛擬記憶體定址如何與快取硬體互動

無快取

如今的大多數處理器，例如標準鍵盤和滑鼠內部的處理器，都沒有任何快取。許多歷史上重要的計算機，例如 Cray 超級計算機，也沒有任何快取。絕大多數軟體既不知道也不關心快取的具體細節，或者是否存在快取。

沒有快取的處理器通常受主記憶體訪問時間的限制。如果沒有快取，處理器會一次從主記憶體中獲取每個指令，並且每個 LOAD 或 STORE 都會在執行下一條指令之前轉到主記憶體。

提高效能的一種方法是替換更快的主記憶體。唉，這通常具有財務限制：幾乎沒有人願意為 1GB 的真正快速的記憶體支付一分錢。

即使金錢不是問題，最終也會達到主記憶體訪問時間的物理限制。即使使用金錢可以買到的最快記憶體，統一 1GB 主記憶體的記憶體訪問時間也受到訊號從 CPU 傳播到記憶體最遠端並返回所需時間的限制。

單級快取

使用完全相同的技術，訊號遍歷一小塊記憶體所需的時間比遍歷一大塊記憶體所需的時間少。

帶有快取的處理器的效能不再受主記憶體訪問時間的限制。帶有快取的處理器的效能通常受（快得多的）快取記憶體訪問時間的限制：如果可以減少處理器的快取訪問時間，則處理器的效能會更高。但是，快取記憶體通常比主記憶體更容易加速：當我們只購買少量記憶體時，真正快速的記憶體要便宜得多。如果它會顯著提高系統的效能，那麼很多人願意為 1KB 的真正快速的快取記憶體支付一分錢。

區域性性原理

區域性性有兩種型別，空間和時間。現代計算機程式通常是基於迴圈的，因此我們有兩個關於區域性性的規則

空間區域性性

當訪問資料項時，很可能還會訪問順序記憶體位置中的資料項。考慮陣列的遍歷或在棧上儲存區域性變數的操作。在這些情況下，當訪問一個數據項時，最好同時將周圍的記憶體區域載入到快取中。

時間區域性性

當訪問資料項時，很可能再次訪問相同的資料項。例如，變數通常會快速連續地讀取和寫入。最好將最近使用過的專案保留在快取中，並且不要覆蓋最近使用過的資料。

命中或未命中

在談論快取時，命中是指處理器在快取中找到它正在查詢的資料。未命中是指處理器在快取中查詢資料，但資料不可用。如果發生未命中，快取控制器單元必須從主記憶體中收集資料，這可能會花費處理器更多時間。

“命中率”的測量通常是在基準應用程式上執行的。實際的命中率因應用程式而異。特別是，影片和音訊流應用程式的命中率通常接近於零，因為流中的每一位資料都會第一次讀取（強制未命中），使用，然後不再讀取或寫入。更糟糕的是，許多快取演算法（特別是 LRU）允許此流資料填充快取，從而將很快再次使用的資訊從快取中推出（快取汙染）。

快取效能

帶有快取的處理器首先會在快取中查詢資料（或指令）。如果未命中，處理器就會從主記憶體中獲取資料（或指令）。如果未命中，這個過程會比沒有快取的同等處理器花費 *更長* 的時間。

快取比沒有快取的處理器提供更好的淨效能，主要有三種方式。

• 命中（從快取讀取）的速度比沒有快取的處理器從主記憶體中獲取資料所需的時間快。關鍵在於設計快取，使其能夠經常命中，從而其效能提升能夠彌補偶爾未命中導致的效能下降。（這需要快取的速度快於主記憶體）。
• 具有共享主記憶體的多處理器計算機，在訪問主記憶體時經常會出現瓶頸。當本地快取成功地滿足記憶體操作而無需一直訪問主記憶體時，主記憶體頻寬就會釋放出來供其他處理器使用，並且本地處理器無需等待其他處理器完成其記憶體操作。
• 許多系統的設計使得處理器能夠經常同時從快取中讀取多個專案——無論是用於指令、資料和 TLB 的 3 個獨立快取；還是多埠快取；或兩者兼而有之——這比一次從主記憶體中讀取相同專案花費的時間少。

即使快取的速度不快於主記憶體，最後兩種方式也能提高整體效能。

沒有快取的處理器的記憶體引用時間 T 為常數

$T=T_{m}+E$

帶有快取的處理器的平均記憶體訪問時間為

$T=mT_{m}+T_{h}+E$

其中

• m 是未命中率
• T_m 是進行主記憶體引用的時間
• T_h 是在命中時進行快取引用的時間
• E 考慮各種次要因素（記憶體重新整理時間、多處理器爭用等）

重新整理快取

當處理器需要資料時，它會在快取中查詢。如果資料不在快取中，它就會去記憶體中查詢資料。來自記憶體的資料會被移動到快取中，然後由處理器使用。有時整個快取包含無用或舊資料，需要將其 **重新整理**。當快取控制器確定快取包含的潛在未命中次數多於命中次數時，就會發生重新整理。重新整理快取需要幾個處理器週期，因此很多研究都集中在開發用於保持快取更新的演算法上。

快取層次結構

快取通常劃分為多個級別。最常見的級別是 L1、L2 和 L3。L1 最小但最快。L3 最大但最慢。許多晶片沒有 L3 快取。一些確實具有 L3 快取的晶片實際上具有一個外部 L3 模組，該模組位於主機板上的微處理器和 RAM 之間。

包含、獨佔和其他快取層次結構

當存在多個快取級別，並且主記憶體中某個位置的資料已快取在 L1 快取中時，L2 快取中是否還有該資料的副本？

• 否。某些系統設計為具有嚴格的獨佔快取級別：主記憶體中的任何特定位置最多快取在一個快取級別中。

• 是。其他系統設計為具有嚴格的包含快取級別：只要主記憶體中的某個位置快取在任何一個級別中，該位置也會快取在所有更高級別中。L2 快取中的所有資料也都可以 found 在 L3 中（以及主記憶體中）。

L1 快取中的所有資料也可以在 L2 和 L3 中 found（以及主記憶體中）。

• 可能。在某些系統中，例如 Intel Pentium 4，L1 快取中的一些資料也在 L2 快取中，而 L1 快取中的其他資料則不在 L2 快取中。這種快取策略還沒有流行的名稱。

快取大小

奔騰 Pro 晶片是有史以來製造的最大微處理器之一。它之所以如此之大，是因為它包含當時任何晶片中最大的快取。

影響晶片上快取大小的因素有很多。

1. 摩爾定律使得每個晶片上的電晶體數量不斷增加。大約在 1989 年之後，每個晶片上可用的電晶體數量超過了設計人員用於製造 CPU 的數量。這些額外的電晶體很容易轉換為大型快取。
2. 隨著電晶體尺寸的減小，處理器元件的尺寸也隨之減小。這意味著晶片上有更多空間用於新增快取。
3. 更多的快取意味著訪問資料的延遲更少，因此效能更好。

由於這些因素，晶片快取的趨勢是每一代晶片都越來越大。

快取標記

快取可以包含沒有特定順序的非連續資料項。快取中的記憶體塊可能是空的，根本不包含任何資料。為了使硬體能夠檢查快取中條目的有效性，每個快取條目都需要維護以下資訊

1. 一個狀態位，用於確定塊是空還是滿
2. 塊中資料的記憶體地址
3. 指定記憶體地址中的資料（快取中的“塊”，也稱為快取中的“行”）

當處理器在快取中查詢資料時，它會將記憶體地址傳送到快取控制器。快取控制器會將該地址與快取中所有地址欄位進行比較。如果命中，快取控制器會返回資料。如果未命中，快取控制器必須將請求傳遞到下一級快取或主記憶體單元。

快取控制器將有效記憶體地址（MSB 到 LSB）拆分為標記、索引和塊偏移。 一些作者將塊偏移簡單地稱為“偏移” 或“位移”。

顯示非連續資料的快取示意圖

快取中資料的記憶體地址稱為 **標記**。

記憶體停頓週期

如果快取未命中，處理器將需要停頓當前指令，直到快取能夠從更高級別獲取正確的資料。停頓導致的時間損失取決於許多因素。特定程式中的記憶體訪問次數表示為 A_m；其中一些訪問將命中快取，其餘的將未命中快取。未命中率等於任何特定訪問未命中的機率，表示為 r_m。每次未命中導致的平均時間損失稱為未命中懲罰，表示為 P_m。我們可以計算因快取未命中停頓而浪費的時間為

${\mbox{停頓時間}}=A_{m}\times r_{m}\times P_{m}$

同樣地，如果我們知道程式中指令的總數 *N*，以及每條指令的平均缺失次數 *MPI*，我們可以計算出損失的時間為：

${\mbox{停頓時間}}=N\times MPI\times P_{m}$

如果我們用損失的週期數來衡量缺失懲罰，而不是損失的時間，那麼計算結果將是由於記憶體停頓而損失的週期數，而不是損失的時間。

讀取停頓時間

為了計算由於快取讀取缺失而損失的時間，我們可以執行與上面相同的基本計算。

${\mbox{讀取停頓時間}}=A_{r}\times r_{r}\times P_{r}$

*A_r* 是平均讀取訪問次數，*r_r* 是讀取操作的缺失率，*P_r* 是與讀取缺失相關的延遲時間或週期數。

寫入停頓時間

確定由於寫入停頓而損失的時間類似，但需要包含一個額外的加性項，表示寫入緩衝區的停頓。

${\mbox{寫入停頓時間}}=A_{w}\times r_{w}\times P_{w}+T_{wb}$

其中 *T_wb* 是由於寫入緩衝區停頓而損失的時間。當快取嘗試與主存同步時，寫入緩衝區可能會停頓。

層次結構停頓時間

在分層快取系統中，當資料在多個快取級別中缺失時，缺失懲罰可能會疊加。如果資料在 L1 快取中缺失，則將在 L2 快取中查詢。但是，如果它也在 L2 快取中缺失，則將產生雙重懲罰。L2 需要從主存（或 L3 快取，如果系統有 L3 快取）載入資料，然後將資料載入到 L1。請注意，在兩個快取級別中缺失然後訪問主存所需的時間比直接訪問記憶體所需的時間更長。

設計考慮因素

L1 快取通常旨在最大程度地減少命中所需的時間。如果命中時間足夠快，則可以接受相當大的缺失率。L1 中的缺失將重定向到 L2，這仍然比訪問主存快得多。L1 快取往往具有較小的塊大小，但在相同空間內可以受益於更多可用的塊。為了使 L1 命中時間最小化，L1 通常採用直接對映或甚至狹義的 2 路組相聯方式。

另一方面，L2 快取需要具有較低的缺失率以幫助避免訪問主存。訪問 L2 快取的速度比訪問記憶體快得多，因此我們應該盡一切努力確保最大化命中率。出於這個原因，L2 快取往往採用全相聯方式並具有較大的塊大小。這是因為記憶體通常按順序記憶體單元讀取和寫入，因此較大的塊大小可以利用這種順序性。

L3 快取進一步延續了這一趨勢，具有更大的塊大小和更低的缺失率。

塊大小

非常小的快取塊大小會增加缺失率，因為缺失將每次獲取較少的資料。非常大的快取塊大小也會增加缺失率，因為它會導致系統獲取大量額外資訊，而這些資訊的使用頻率低於它在快取中取代的資料。

相聯性

為了提高快取的讀取速度，許多快取設計人員實現了一定程度的**相聯性**。相聯快取在原始記憶體位置和儲存該資料的快取位置之間建立了一種關係。主存地址與資料儲存位置之間的關係稱為快取的**對映**。這樣，如果資料確實存在於快取中，則快取控制器知道它只能位於滿足對映的特定位置。

直接對映

直接對映系統使用雜湊演算法為記憶體地址分配識別符號。此目的的常用雜湊演算法是模運算。模運算將地址除以某個數 *p*，並將餘數 *r* 作為結果。如果 *a* 是主存地址，*n* 是任意非負整數，則雜湊演算法必須滿足以下等式

$a=p\times n+r$

如果設計人員正確選擇了 *p*，則資料將均勻分佈在整個快取中。

在直接對映系統中，每個記憶體地址僅對應一個快取位置，但單個快取位置可以對應多個記憶體位置。上圖顯示了一個簡單的快取圖，其中包含 8 個塊。因此，所有記憶體地址都計算為 *n mod 8*，其中 *n* 是要讀入快取的記憶體地址。記憶體地址 0、8 和 16 都將對映到快取中的塊 0。當具有相同雜湊值的多個數據項被讀取時，快取效能最差，而當資料項在記憶體中彼此靠近時（例如程式指令的順序塊或順序陣列），快取效能最佳。

大多數外部快取（位於主機板上，但位於 CPU 外部）採用直接對映或偶爾採用 2 路組相聯方式，因為用標準組件構建更高相聯性的快取很複雜。 如果存在這樣的快取，則通常主機板上只有一個外部快取，由所有 CPU 共享。

直接對映快取的替換策略是最簡單的替換策略：新資料必須進入它對應的一個且僅一個快取位置。（如果快取中該位置的舊資料的髒位已設定，則必須首先將其寫入主存）。

2 路組相聯

在2路組相聯快取系統中，資料值會被雜湊，但每個雜湊值對應一組快取塊。每個塊包含多個數據單元，分配給該塊的資料值可以插入到塊中的任何位置。讀取速度很快，因為快取控制器可以立即將搜尋範圍縮小到與地址雜湊值匹配的塊。

2路組相聯快取的LRU替換策略是最簡單的替換策略之一：新資料必須放在2個可能位置之一。這兩個位置共享一個LRU位，每當讀取或寫入其中一個時都會更新該位，指示該組中的兩個條目中哪個是最近最少使用的。新資料將放入*另一個*位置（最近最少使用的位置）。（如果快取中該LRU位置的舊資料其髒位被設定，則必須先將其寫入主記憶體）。

2路傾斜關聯

2路傾斜關聯快取是“對於……大小在4K-8K位元組範圍內的快取的最佳折衷方案”——André SeznecAndré Seznec. “支援雙向傾斜關聯快取的案例”. 檢索於 2007-12-13.

全相聯

在全相聯快取中，不使用雜湊演算法，資料可以插入到快取中任何可用位置。一個典型的演算法會將新的資料值覆蓋快取中最早未使用的值。然而，此方案需要儲存載入或訪問項的時間，這可能需要大量的額外儲存空間。

快取未命中

快取中主要有三種類型的未命中

1. 衝突未命中
2. 強制未命中
3. 容量未命中

衝突未命中

當兩個資料項對映到同一個快取位置時，在直接對映和2路組相聯快取中會發生衝突未命中。在資料未命中時，最近使用的資料項會被新資料項覆蓋。

強制未命中

上圖顯示了衝突未命中和強制未命中之間的區別。強制未命中是指快取必須未命中因為它不包含任何資料的情況。例如，當處理器第一次通電時，快取中沒有有效資料，前幾次讀取總是會未命中。

強制未命中演示了快取需要區分空閒空間和已用空間的必要性。考慮當我們開啟處理器並重置所有地址值到零時，嘗試讀取雜湊值為零的記憶體位置將命中。如果塊為空，我們不希望快取命中。

容量未命中

當快取塊不足以容納資料項時，會發生容量未命中。

快取寫策略

資料寫入需要與資料讀取相同的時間延遲。出於這個原因，快取系統通常也會將資料寫入快取。但是，寫入快取時，務必確保資料也寫入主記憶體，以免被下一次快取讀取覆蓋。如果快取中的資料在未儲存到主記憶體的情況下被覆蓋，則資料將丟失。

快取必須將資料寫入主記憶體，但何時將資料寫入主記憶體稱為寫策略。有兩種寫策略：寫通和寫回。

寫入操作在主記憶體中執行的時間與讀取操作一樣長。因此，許多帶快取的處理器除了執行讀取操作外，還會執行寫入快取的操作。

寫通

當資料寫入記憶體時，寫入請求會同時傳送到主記憶體和快取。這樣，結果資料可以在寫入（然後從主記憶體再次讀取）之前在快取中可用。寫入快取時，務必確保主記憶體和快取同步，並且它們包含相同的資料。

在寫通系統中，寫入快取的資料也會立即寫入主記憶體。如果許多寫入需要按順序指令發生，寫緩衝區可能會積壓並導致停頓。

寫回

在寫回系統中，快取控制器會跟蹤哪些資料項已與主記憶體同步。未同步的資料項稱為“髒資料”，快取控制器會防止髒資料被覆蓋。

快取控制器將在處理器週期中同步資料，在這些週期中沒有其他資料被寫入快取。

寫旁路

某些處理器會將寫入直接傳送到主記憶體，繞過快取。如果該位置*尚未*被快取，則無需執行任何其他操作。如果該位置*已*被快取，則快取中的舊資料需要標記為“無效”（“陳舊”），因此如果CPU讀取該位置，CPU將讀取主記憶體中的最新值，而不是快取中的某些早期值。

陳舊資料

主記憶體中的資料可能會被微控制器之外的元件更改。例如，許多計算機系統具有記憶體對映I/O或可以更改資料的DMA控制器。某些計算機系統具有連線到公共主記憶體的多個CPU。快取控制器必須檢查快取中的資料是否正確。快取中舊且可能不正確的資料稱為“陳舊資料”。

處理陳舊資料（“快取一致性協議”）的三種最流行方法是

• 使用忽略其他CPU正在做什麼的簡單快取硬體。
• 將所有快取設定為寫通所有儲存（寫通策略）。使用額外的快取硬體在其他裝置寫入主記憶體時偵聽（“嗅探”），並在其他裝置寫入主記憶體中相應快取位置時使本地快取行無效。

• 設計快取以使用MESI協議。

對於忽略其他CPU正在做什麼的簡單快取硬體，快取一致性由作業系統軟體維護。作業系統將記憶體中的每個頁面設定為（a）僅供一個特定CPU獨佔使用（該CPU被允許讀取、寫入和快取它）；所有其他CPU都不允許讀取、寫入或快取該頁面；（b）在CPU之間共享讀取/寫入，並設定為“不可快取”，與記憶體對映I/O裝置設定為不可快取的方式相同；或（c）共享只讀；所有CPU都被允許快取但不能寫入該頁面。

分離快取

高效能處理器總是具有2個獨立的L1快取，即指令快取和資料快取（I快取和D快取）。這種“分離快取”與統一快取相比具有幾個優點：

• 佈線簡單：解碼器和排程器僅連線到I快取；暫存器和ALU以及FPU僅連線到D快取。
• 速度：CPU可以從D快取讀取資料，同時從I快取載入下一條指令。

多CPU系統通常為每個CPU配備單獨的L1指令快取（L1 I-cache）和L1資料快取（L1 D-cache），每個快取都採用直接對映方式以提高速度。

開放性問題：為了加速JVM中Java應用程式的執行（以及類似的直譯器和CPU模擬器），是否可以透過使用3個獨立的快取來提高效能——一個由程式計數器PC索引的機器指令快取、一個由虛擬機器指令指標IP索引的位元組碼快取，以及一個數據快取？

另一方面，在高效能處理器中，其他級別的快取（如果有）——L2、L3等——以及主記憶體——通常是統一的，儘管也有一些例外（例如Itanium 2 Montecito）。統一快取（以及統一主記憶體）的優勢有：

• 一些程式大部分時間都在程式的一小部分中處理大量資料。其他程式則對少量資料執行大量不同的子程式。統一快取會自動平衡用於指令和用於資料的快取比例——要獲得與分離快取相同的效能，需要更大的快取。
• 當指令被寫入記憶體時——例如作業系統從儲存器載入可執行檔案，或即時編譯器將位元組碼轉換為可執行程式碼——分離快取需要CPU重新整理並重新載入指令快取；而統一快取則不需要這樣做。

錯誤檢測

每個快取行條目可能都有錯誤檢測位。由於快取僅儲存主記憶體中資訊的副本（寫回佇列除外），因此當檢測到錯誤時，可以從主記憶體中重新獲取所需的資料——視為一種無效缺失——並且系統可以繼續執行，就像沒有發生錯誤一樣。一些計算機系統使用漢明糾錯來糾正快取“資料”欄位中的單位元錯誤，而無需返回到主記憶體。

專用快取特性

許多CPU對指令快取和資料快取使用完全相同的硬體。（當然，在統一快取中，指令和資料也使用相同的硬體。馮諾依曼體系結構的革命性思想是在主記憶體本身中對指令和資料使用相同的硬體）。例如，Fairchild CLIPPER使用了2個相同的CAMMU晶片，一個用於指令快取，另一個用於資料快取。

由於各種快取的使用方式略有不同，因此一些CPU設計人員會以不同的方式定製每個快取。

• 一些CPU設計人員將用於分支預測的“分支歷史位”放在指令快取中。將此類資訊新增到僅用於資料的快取中沒有任何意義。
• 許多指令快取的設計方式使得處理陳舊指令的唯一方法是使整個快取失效並重新載入。資料快取通常設計有更細粒度的響應，並配備額外的硬體，可以僅使已過時的特定快取行失效並重新載入。
• 虛擬到物理地址轉換過程通常具有許多與其相關的專用硬體以加快速度——TLB快取、硬體頁面漫遊器等。我們將在下一章虛擬記憶體中更詳細地討論這一點。

進一步閱讀

• 平行計算和計算機叢集/記憶體
• 可在馬里蘭大學：記憶體系統研究：“計算工件”下載的模擬器可用於衡量微處理器設計的快取效能和功耗，而無需實際構建它。這使得探索快取設計中涉及的各種權衡變得更加快捷和經濟。（“在晶片尺寸固定的情況下，如果我犧牲一些L2快取以使L1快取更大，這會使整體效能更好還是更差？”“使用具有低關聯性的極快週期時間快取更好，還是使用具有較高關聯性並提供更好命中率的稍慢週期時間快取更好？”）