一文喫透三種經典映射策略，從理論到項目實踐

在計算機的世界裏，有一個神祕的存在，它默默地工作，卻對計算機的性能起着至關重要的作用，它就是緩存（Cache）。Cache 就像是計算機的 “高速通道”，專門負責加速數據的讀取，讓計算機能夠快速響應各種指令，極大地提升了運行效率。想象一下，CPU 就像是一位忙碌的大廚，它需要各種食材（數據）來烹飪出美味的 “程序大餐”。而主存則像是一個巨大的食材倉庫，裏面存放着各種各樣的食材。但是，這個倉庫太大了，大廚每次去取食材都要花費很長時間，這就大大降低了烹飪的效率。

這時，Cache 就登場了，它就像是大廚身邊的一個小助手，會提前把一些常用的食材放在一個小籃子裏（緩存），這樣大廚需要的時候，就可以直接從小籃子裏拿，而不用每次都跑去大倉庫，大大節省了時間。Cache 之所以能夠如此高效地工作，離不開它獨特的映射方式。今天，我們就來深入探討一下 Cache 的三種映射方式，揭開它們神祕的面紗，看看它們是如何在幕後爲計算機的性能保駕護航的。

一、直接映射：簡單直接的 “定位器”

直接映射是三種映射方式中最爲簡單直接的一種。它的映射規則就像是給每個主存塊都分配了一個固定的 “座位”（緩存塊），這個 “座位” 的確定方式是通過主存塊號對緩存塊數取模運算。

假設主存中有很多個數據塊，編號從 0 開始依次遞增，而緩存也被劃分成了若干個緩存塊。對於主存中的第 n 個數據塊，它會被映射到緩存中的第（n % 緩存塊數）個緩存塊中。例如，如果緩存有 8 個緩存塊，主存中的第 0 塊、第 8 塊、第 16 塊…… 都會被映射到緩存的第 0 塊；主存中的第 1 塊、第 9 塊、第 17 塊…… 都會被映射到緩存的第 1 塊，以此類推 。這種映射關係是固定且唯一的，每個主存塊在緩存中都有且僅有一個對應的緩存塊。

直接映射是最簡單的地址映射方式，它的硬件簡單，成本低，地址變換速度快，而且不涉及替換算法問題。但是這種方式不夠靈活，Cache 的存儲空間得不到充分利用，每個主存塊只有一個固定位置可存放，容易產生衝突，使 Cache 效率下降，因此只適合大容量 Cache 採用。例如，如果一個程序需要重複引用主存中第 0 塊與第 16 塊，最好將主存第 0 塊與第 16 塊同時複製到 Cache 中，但由於它們都只能複製到 Cache 的第 0 塊中去，即使 Cache 中別的存儲空間空着也不能佔用，因此這兩個塊會不斷地交替裝入 Cache 中，導致命中率降低。

1.1 工作流程詳解

當 CPU 需要訪問某個數據時，它會首先根據數據的主存地址來判斷該數據是否在緩存中。它會將主存地址分成幾個部分，其中一部分用於確定緩存塊的索引（也就是前面提到的取模運算得到的結果），另一部分用於作爲標記（tag），還有一部分用於表示塊內偏移（因爲每個緩存塊中可以存儲多個數據）。

CPU 會根據索引找到對應的緩存塊，然後將主存地址中的標記與緩存塊中的標記進行比較。如果兩者相同，並且緩存塊中的有效位爲 1（表示該緩存塊中的數據是有效的），那麼就表示命中，CPU 可以直接從緩存塊中讀取數據；如果標記不同或者有效位爲 0，那就表示未命中，CPU 需要從主存中讀取數據，並且將該數據所在的主存塊調入緩存中，同時更新緩存塊的標記和有效位。

1.2 主存與 cache 地址格式

rWZbd4

1.3 優劣勢深度分析

直接映射的優點非常明顯，首先它的硬件實現非常簡單，因爲映射規則固定，不需要複雜的硬件電路來進行地址映射和查找。這就使得它的成本相對較低，而且地址變換的速度非常快，能夠快速地響應 CPU 的訪問請求。

然而，它的缺點也同樣突出。由於每個主存塊只能映射到固定的緩存塊，這就導致了緩存的衝突率非常高。當多個主存塊都需要映射到同一個緩存塊時，就會發生衝突，後面的主存塊會覆蓋前面主存塊的數據，使得緩存的命中率降低。例如，如果程序頻繁地訪問主存中第 0 塊和第 8 塊的數據，而它們都映射到緩存的第 0 塊，那麼這兩個塊的數據就會不斷地在緩存中替換，導致每次訪問都可能需要從主存中讀取數據，大大降低了緩存的效率 。這種衝突問題也使得緩存的利用率很低，很多緩存空間無法得到充分利用，因爲即使其他緩存塊空閒，主存塊也不能隨意映射到這些空閒塊中。

1.4 案例分析

【例】設主存容量 1MB , cache 容量 16KB，塊的大小爲 512B，採用全相聯映射方式。

(1) 寫出 cache 的地址格式？

(2) 寫出主存的地址格式？

(3) 塊表的容量多大?

(4) 主存地址爲 CDE8FH 的單元，在 cache 中的什麼位置?

二、全相聯映射：自由靈活的 “數據收納盒”

全相聯映射與直接映射截然不同，它賦予了數據塊極高的自由度。在全相聯映射的規則下，主存中的任何一個數據塊都能夠隨心所欲地映射到緩存中的任意一個緩存塊位置 。這就好比一個大型圖書館，每本書（主存數據塊）可以被放置在圖書館的任意一個書架格子（緩存塊）裏，沒有固定的限制區域。這種映射方式徹底打破了直接映射的那種固定對應關係的束縛，極大地提高了緩存使用的靈活性。

全相聯映射方式比較靈活，主存的各塊可以映射到 Cache 的任一塊中，Cache 的利用率高，塊衝突概率低，只要淘汰 Cache 中的某一塊，即可調入主存的任一塊。但是，由於 Cache 比較電路的設計和實現比較困難，這種方式只適合於小容量 Cache 採用。

2.1 查找匹配過程

當 CPU 需要從緩存中讀取數據時，它會將主存地址拆分成標記（tag）和塊內偏移兩部分。接下來，CPU 會逐一比較緩存中每一個緩存塊的標記與主存地址中的標記。這個過程就像是在圖書館裏，工作人員需要拿着書籍編號（主存地址標記），在所有的書架格子（緩存塊）中尋找與之匹配的編號。如果找到了匹配的標記，並且該緩存塊的有效位爲 1，那就意味着命中了，CPU 可以直接從這個緩存塊中讀取數據；要是遍歷完所有緩存塊都沒有找到匹配的標記，那就表示未命中，CPU 不得不從主存中讀取數據，並且將該數據所在的主存塊調入緩存中，同時更新緩存塊的標記和有效位 。

2.2 主存地址格式

2.3 全面評價優缺點

全相聯映射的優點非常突出，由於它允許主存塊自由映射到緩存的任意位置，這使得緩存的命中率得到了顯著提高，緩存空間的利用率也達到了很高的水平。在實際應用中，當程序訪問的數據具有較強的隨機性和分散性時，全相聯映射能夠充分發揮其優勢，大大減少了緩存未命中的情況，從而提高了系統的性能 。

然而，全相聯映射也存在着明顯的缺點。由於查找數據時需要遍歷緩存中的所有塊來對比標記，這就使得查找過程變得非常複雜，需要耗費大量的時間，導致訪問速度較慢。而且，爲了實現這種自由映射和快速查找，需要配備複雜的硬件電路和大量的比較器，這無疑大大增加了硬件成本和實現難度 。

也正是因爲這些缺點，全相聯映射在實際應用中受到了一定的限制，通常只適用於對緩存容量要求較小的場景，比如一些對成本不太敏感但對緩存命中率要求極高的高端處理器緩存設計中 。

三、組相聯映射：取兩者之長的 “調和者”

組相聯映射就像是一個精心規劃的 “分組社區”，它巧妙地融合了直接映射和全相聯映射的優點 。在組相聯映射的規則下，緩存被細緻地劃分爲多個組（Set），每個組裏面又包含了若干個緩存塊（Block）。主存中的數據塊首先會依據特定的規則被映射到緩存中的某一個組，這個映射規則類似於直接映射，通過主存塊號對緩存組數取模運算來確定組號 。例如，如果緩存被分成 8 個組，主存中的第 0 塊、第 8 塊、第 16 塊…… 都會被映射到緩存的第 0 組。

而在組內，數據塊的映射方式則採用了全相聯映射，也就是說，主存中的數據塊可以自由地映射到它所對應的組內的任意一個緩存塊中 。這種獨特的映射方式既保留了直接映射簡單快速的特點，又具備了全相聯映射靈活高效的優勢，有效地降低了緩存衝突的概率，提高了緩存的利用率 。

3.1 實際工作機制

當 CPU 需要訪問數據時，組相聯映射的工作機制開始發揮作用。CPU 首先會根據主存地址中的組索引字段找到對應的緩存組，這個過程就像是在一個大型社區中找到對應的樓棟。然後，它會在這個組內逐一比較各個緩存塊的標記（tag）與主存地址中的標記 。這一步就像是在樓棟裏找到對應的房間，通過房間號（標記）來確認是否找對了地方。如果找到了匹配的標記，並且該緩存塊的有效位爲 1，那就意味着命中了，CPU 可以直接從這個緩存塊中讀取數據；如果沒有找到匹配的標記，那就表示未命中，CPU 需要從主存中讀取數據，並將該數據所在的主存塊調入緩存中，同時更新緩存塊的標記和有效位 。

3.2 性能綜合評估

組相聯映射在性能上有着出色的表現。它有效地降低了緩存衝突率，相比於直接映射，它允許更多的主存塊映射到緩存中，減少了因衝突導致的數據替換，從而提高了緩存的命中率 。在一個程序頻繁訪問多個主存塊，但這些主存塊不會都映射到同一個緩存組的情況下，組相聯映射能夠很好地滿足數據訪問需求，使得數據能夠更快速地被 CPU 獲取，提升了系統的整體性能 。

在緩存利用率方面，組相聯映射也表現得相當出色。由於組內採用全相聯映射，主存塊可以更靈活地放置在緩存中，避免了直接映射中因固定映射導致的緩存空間浪費問題，使得緩存空間得到了更充分的利用 。

當然，組相聯映射也並非完美無缺。由於在組內需要進行標記比較，這使得它的硬件複雜度要高於直接映射，需要更多的比較器和複雜的控制電路來實現 。查找數據的時間也會相對增加，因爲除了要找到對應的組，還需要在組內進行逐一比較 。但總體來說，它在衝突率、利用率和硬件複雜度之間取得了一個較好的平衡，在實際應用中得到了廣泛的使用 。

四、三種映射方式的應用場景與選擇策略

4.1 不同場景下的適用性分析

在實際應用中，不同的計算機系統和應用場景對 Cache 的性能有着不同的要求，因此需要根據具體情況選擇合適的映射方式。

對於一些簡單的小型系統或嵌入式系統，直接映射方式往往是一個不錯的選擇。這些系統通常對成本非常敏感，並且數據訪問模式相對簡單，數據的訪問具有一定的規律性。在這樣的系統中，直接映射的簡單性和低成本優勢就能夠得到充分體現 。一些簡單的微控制器系統，它們的任務相對單一，數據訪問主要集中在幾個固定的區域，使用直接映射 Cache 可以在保證一定性能的前提下，大大降低硬件成本，提高系統的性價比 。

而對於那些對性能要求極高，對成本不太敏感的高性能計算系統，全相聯映射則更能發揮其優勢。在高性能計算中，程序通常需要處理大量複雜的數據，數據訪問模式非常複雜且具有高度的隨機性。全相聯映射能夠提供極高的命中率，減少緩存未命中的情況，從而顯著提高系統的性能 。在一些超級計算機的緩存設計中，就可能會採用全相聯映射方式，以滿足其對高速數據訪問的嚴格要求 。

組相聯映射則在大多數現代計算機系統中得到了廣泛應用，因爲它在性能和成本之間取得了一個很好的平衡。無論是桌面計算機、服務器還是移動設備，這些系統既需要一定的性能來保證用戶的使用體驗，又需要控制成本以滿足市場需求 。組相聯映射既能有效降低緩存衝突率，提高命中率，又不會像全相聯映射那樣帶來過高的硬件成本和複雜度，非常適合這類系統的需求 。在常見的個人電腦中，CPU 的一級緩存（L1 Cache）和二級緩存（L2 Cache）通常會採用組相聯映射方式，以提供良好的性能和合理的成本 。

4.2 選擇時的關鍵考量因素

在選擇 Cache 映射方式時，有幾個關鍵因素需要仔細考量。首先是成本因素，硬件成本在系統設計中是一個重要的制約因素。直接映射方式由於硬件實現簡單，所需的硬件資源最少，因此成本最低；全相聯映射則需要複雜的硬件電路和大量的比較器，成本最高；組相聯映射的成本介於兩者之間 。如果系統對成本控制較爲嚴格，那麼直接映射可能是首選；而對於那些追求極致性能且對成本不敏感的高端系統，則可以考慮全相聯映射 。

性能是另一個至關重要的考量因素。性能主要體現在緩存命中率和訪問速度上。全相聯映射的命中率最高，因爲它可以將主存塊自由地映射到緩存的任意位置，最大限度地減少了衝突，對於那些數據訪問模式複雜且隨機的應用，能夠提供最佳的性能 。直接映射的訪問速度最快，因爲它的映射規則簡單，每次訪問只需檢查一個固定的緩存塊位置，但由於衝突率高，命中率相對較低 。組相聯映射在命中率和訪問速度之間取得了平衡，它通過合理的分組和組內全相聯映射，降低了衝突率，提高了命中率，同時訪問速度也不會太慢 。

緩存大小也會對映射方式的選擇產生影響。對於較小的緩存，全相聯映射可能更適用，因爲小緩存中的緩存塊數量有限，全相聯映射可以更充分地利用這些緩存塊，提高緩存的利用率和命中率 。而對於較大的緩存，直接映射可能會導致嚴重的衝突問題，降低緩存的性能，此時組相聯映射則是更好的選擇，它可以通過分組來減少衝突，提高緩存的整體性能 。

五、Cache 映射案例分析

5.1 實際例子

下面展示了現代 Intel 處理器的 CPU cache 是如何組織的。有關 cache 的討論往往缺乏具體的實例，使得一些簡單的概念變得撲朔迷離。也許是我可愛的小腦瓜有點遲鈍吧，但不管怎樣，至少下面講述了故事的前一半，即 Core 2 的 L1 cache 是如何被訪問的：

5.2 由索引揀選緩存組（行）

在 cache 中的數據是以緩存線（line）爲單位組織的，一條緩存線對應於內存中一個連續的字節塊。這個 cache 使用了 64 字節的緩存線。這些線被保存在 cache bank 中，也叫路（way）。每一路都有一個專門的目錄（directory）用來保存一些登記信息。你可以把每一路連同它的目錄想象成電子表格中的一列，而表的一行構成了 cache 的一組（set）。列中的每一個單元（cell）都含有一條緩存線，由與之對應的目錄單元跟蹤管理。圖中的 cache 有 64 組、每組 8 路，因此有 512 個含有緩存線的單元，合計 32KB 的存儲空間。

在 cache 眼中，物理內存被分割成了許多 4KB 大小的物理內存頁（page）。每一頁都含有 4KB / 64 bytes == 64 條緩存線。在一個 4KB 的頁中，第 0 到 63 字節是第一條緩存線，第 64 到 127 字節是第二條緩存線，以此類推。每一頁都重複着這種劃分，所以第 0 頁第 3 條緩存線與第 1 頁第 3 條緩存線是不同的。

在全相聯緩存（fully associative cache）中，內存中的任意一條緩存線都可以被存儲到任意的緩存單元中。這種存儲方式十分靈活，但也使得要訪問它們時，檢索緩存單元的工作變得複雜、昂貴。由於 L1 和 L2 cache 工作在很強的約束之下，包括功耗，芯片物理空間，存取速度等，所以在多數情況下，使用全相聯緩存並不是一個很好的折中。

取而代之的是圖中的組相聯緩存（set associative cache）。意思是，內存中一條給定的緩存線只能被保存在一個特定的組（或行）中。所以，任意物理內存頁的第 0 條緩存線（頁內第 0 到 63 字節）必須存儲到第 0 組，第 1 條緩存線存儲到第 1 組，以此類推。每一組有 8 個單元可用於存儲它所關聯的緩存線，從而形成一個 8 路關聯的組（8-way associative set）。當訪問一個內存地址時，地址的第 6 到 11 位（譯註：組索引）指出了在 4KB 內存頁中緩存線的編號，從而決定了即將使用的緩存組。舉例來說，物理地址 0x800010a0 的組索引是 000010，所以此地址的內容一定是在第 2 組中緩存的。

但是還有一個問題，就是要找出一組中_哪個_單元包含了想要的信息，如果有的話。這就到了緩存目錄登場的時刻。每一個緩存線都被其對應的目錄單元做了_標記_（tag）；這個標記就是一個簡單的內存頁編號，指出緩存線來自於哪一頁。由於處理器可以尋址 64GB 的物理 RAM，所以總共有 64GB / 4KB == 224 個內存頁，需要 24 位來保存標記。前例中的物理地址 0x800010a0 對應的頁號爲 524,289。下面是故事的後一半：

5.3 在組中搜索匹配標記

由於我們只需要去查看某一組中的 8 路，所以查找匹配標記是非常迅速的；事實上，從電學角度講，所有的標記是同時進行比對的，我用箭頭來表示這一點。如果此時正好有一條具有匹配標籤的有效緩存線，我們就獲得一次緩存命中（cache hit）。否則，這個請求就會被轉發的 L2 cache，如果還沒匹配上就再轉發給主系統內存。通過應用各種調節尺寸和容量的技術，Intel 給 CPU 配置了較大的 L2 cache，但其基本的設計都是相同的。

比如，你可以將原先的緩存增加 8 路而獲得一個 64KB 的緩存；再將組數增加到 4096，每路可以存儲 256KB。經過這兩次修改，就得到了一個 4MB 的 L2 cache。在此情況下，需要 18 位來保存標記，12 位保存組索引；緩存所使用的物理內存頁的大小與其一路的大小相等。（譯註：有 4096 組，就需要 lg (4096)==12 位的組索引，緩存線依然是 64 字節，所以一路有 4096*64B==256KB 字節；在 L2 cache 眼中，內存被分割爲許多 256KB 的塊，所以需要 lg (64GB/256KB)==18 位來保存標記。）

如果有一組已經被放滿了，那麼在另一條緩存線被存儲進來之前，已有的某一條則必須被騰空（evict）。爲了避免這種情況，對運算速度要求較高的程序就要嘗試仔細組織它的數據，使得內存訪問均勻的分佈在已有的緩存線上。舉例來說，假設程序中有一個數組，元素的大小是 512 字節，其中一些對象在內存中相距 4KB。這些對象的各個字段都落在同一緩存線上，並競爭同一緩存組。如果程序頻繁的訪問一個給定的字段（比如，通過虛函數表 vtable 調用虛函數），那麼這個組看起來就好像一直是被填滿的，緩存開始變得毫無意義，因爲緩存線一直在重複着騰空與重新載入的步驟。

在我們的例子中，由於組數的限制，L1 cache 僅能保存 8 個這類對象的虛函數表。這就是組相聯策略的折中所付出的代價：即使在整體緩存的使用率並不高的情況下，由於組衝突，我們還是會遇到緩存缺失的情況。然而，鑑於計算機中各個存儲層次的相對速度，不管怎麼說，大部分的應用程序並不必爲此而擔心。

一個內存訪問經常由一個線性（或虛擬）地址發起，所以 L1 cache 需要依賴分頁單元（paging unit）來求出物理內存頁的地址，以便用於緩存標記。與此相反，組索引來自於線性地址的低位，所以不需要轉換就可以使用了（在我們的例子中爲第 6 到 11 位）。因此 L1 cache 是物理標記但虛擬索引的（physically tagged but virtually indexed），從而幫助 CPU 進行並行的查找操作。因爲 L1 cache 的一路絕不會比 MMU 的一頁還大，所以可以保證一個給定的物理地址位置總是關聯到同一組，即使組索引是虛擬的。在另一方面 L2 cache 必須是物理標記和物理索引的，因爲它的一路比 MMU 的一頁要大。但是，當一個請求到達 L2 cache 時，物理地址已經被 L1 cache 準備（resolved）完畢了，所以 L2 cache 會工作得很好。

最後，目錄單元還存儲了對應緩存線的狀態（state）。在 L1 代碼緩存中的一條緩存線要麼是無效的（invalid）要麼是共享的（shared，意思是有效的，真的 J）。在 L1 數據緩存和 L2 緩存中，一條緩存線可以爲 4 個 MESI 狀態之一：被修改的（modified），獨佔的（exclusive），共享的（shared），無效的（invalid）。Intel 緩存是包容式的（inclusive）：L1 緩存的內容會被複制到 L2 緩存中。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/qW8kLP0ycJBOooKKcFV1jw

猜你喜歡