理解Cache地址映射之前補充一些基礎知識，Cache的地址映射和MMU（內存管理單元）和TLB Cache（轉譯查找緩存）中的映射是有區別的。Cache、TLB Cache、MMU在CPU中結構如圖1所示，圖1展現的是Cortex A9 Processor內部結構，采用的指令和數據總線分開的哈佛結構。

CPU訪問內部存儲和外部存儲，以及各種外設空間在硬件層面上看都是物理地址（硬件總線），然后為了滿足多進程脆弱的軟件系統提出了虛擬地址，虛擬地址是針對應用程序所提出的概念，MMU負責虛擬地址到物理地址的映射工作，從虛擬地址到物理地址的轉換過程可知：頁表存儲在內存中，使用一級頁表進行地址轉換時，每次讀/寫數據需要訪問兩次內存，第一次訪問一級頁表獲得物理地址，第二次才是真正的讀/寫數據；使用兩級頁表時，每次讀/寫數據需要訪問三次內存，訪問兩次頁表（一級頁表和二級頁表）獲得物理地址，第三次才是真正的讀/寫數據,由于這種機制速率很慢，才提出TLB Cache用于存儲近期用到的頁表條目（段/大頁/小頁/極小頁描述符。

TLB Cache是一個內存管理單元用于改進虛擬地址到物理地址轉換速度的高速緩存，位于MMU中，本文章不深入分析MMU和TLB。Cache映射是硬件層面物理塊與物理塊之間建立的聯系。

圖 1

Cache的容量一般都很小，即使是最大的三級Cache（L3）也只有20MB～30MB。而當今內存的容量都是以GB作為單位，CPU對存儲器的訪問，通常是一次讀寫一個字單元。當CPU訪Cache不命中時，需將存儲在主存中的字單元連同其后若干個字一同調入Cache中，之所以這樣做（write-back策略才會有這種機制），是為了使其后的訪存能在Cache中命中。因此，主存和Cache之間一次交換的數據單位應該是一個數據塊（以前文章中提到的cache line，一般大小為64 Byte）。數據塊的大小是固定的，由若干個字組成，且主存和Cache的數據塊大小是相同的。

從Cache-主存模型來看，一方面既要使CPU的訪存速度接近于訪Cache的速度，另一方面為用戶程序提供的運行空間應保持為主存容量大小的存儲空間。在采Cache-主存層次的系統中，Cache對用戶程序而言是透明的，也就是說，用戶程序可以不需要知道Cache的存在。因此，CPU每次訪存時，依然和未使用Cache的情況一樣，給出的是一個主存地址。但在Cache-主存層次中，CPU首先訪問的是Cache，并不是主存。為此，需要一種機制將CPU的訪主存地址轉換成訪Cache地址。而主存地址與Cache地址之間的轉換是與主存塊與Cache塊之間的映射關系緊密聯系的。如何把內存中的內容存放到Cache中去，這就需要一個映射算法和一個分塊機制。

分塊機制就是說，Cache和內存以塊為單位進行數據交換，塊的大小通常以在內存的一個存儲周期中能夠訪問到的數據長度為限。當今主流塊的大小都是64字節，因此一個Cache line就是指 64 個字節大小的數據塊。Cache容量模型如圖 2所示，圖中展現了data cache: 32-KB, 8-way set associative（每個組里有8行）,64-byte line size的cache容量模型。

圖 2

映射算法是指把內存地址空間映射到Cache地址空間。具體來說，就是把存放在內存中的內容按照某種規則裝入到 Cache 中，并建立內存地址與 Cache 地址之間的對應關系。當處理器需要訪問這個數據塊內容時，則需要把內存地址轉換成 Cache 地址，從而在Cache 中找到該數據塊，最終返回給處理器。Cache 和內存之間的映射關系可以分為三類：全關聯型Cache（full associative cache），直接關聯型 Cache（direct mapped cache），組關聯型 Cache（N-ways associative cache）。

全相聯映射是指主存中任一塊都可以映射到Cache中任一塊的方式，也就是說，當主存中的一塊需調入Cache時，可根據當時Cache的塊占用或分配情況，選擇一個塊給主存塊存儲，所選的Cache塊可以是Cache中的任意一塊。例如，設Cache共有m塊，主存共有n塊，當主存的某一塊j需調進Cache中時，它可以存入Cache的塊0、塊1、…、塊i、… 或塊m的任意一塊上,如圖3所示，區別在于cache和主存塊的對應關系不一樣。

圖3

在Cache中，需要建立一個目錄表，目錄表的每個表項都有三部分組成：內存地址、Cache塊號和一個有效位。當處理器需要訪問某個內存地址時，首先通過該目錄表查詢是否該內容緩存在Cache中，具體過程如圖4所示。當一個主存塊調入Cache中時，會同時在一個存儲主存塊號和Cache塊號映射表的相聯存儲器中進行登記。CPU訪存時，主存的塊地址A在Cache的相聯存儲器目錄表中進行查詢，如果找到等值的內存塊地址，檢查有效位是否有效，只有有效的情況下，才能通過Cache塊號在Cache中找到緩存的內存，并且加上塊內地址 B，找到相應數據，這時則稱為Cache命中，處理器拿到數據返回；否則稱為不命中，處理器則需要在內存中讀取相應的數據。使用全關聯型 Cache，塊的沖突最小，Cache的利用率也高，但是需要一個訪問速度很快的相聯存儲器。隨著Cache容量的增加，其電路設計變得十分復雜，因此只有容量很小的Cache才會設計成全關聯型。

圖 4

直接關聯型Cache是指主存中的一塊內存只能映射到Cache的一個特定的塊中，Cache的目錄表只有兩部分組成：區號和有效位。其查找過程如圖5所示。首先，內存地址被分成三部分：區號A、塊號B和塊內地址C，在這里區號A和區號B其實是全關聯型中主存地址A。根據區號A在目錄表中找到完全相等的區號，并且在有效位有效的情況下，說明該數據在Cache中，然后通過內存地址的塊號B獲得在Cache中的塊地址，加上塊內地址C，最終找到數據。如果在目錄表中找不到相等的區號，或者有效位無效的情況下，則說明該內容不在Cache中，需要到內存中讀取。直接相聯映射方式的優點 是比較電路最簡單，但缺點是Cache塊沖突率較高，從而降低了Cache的利用率。

圖 5

以上兩種方式各有優缺點，而且非常有趣的是，它們的優缺點正好相反，所以組關聯型映射就出現了，組關聯型映射是目前用的最多的映射方式。組關聯型Cache內存被分為很多組，一個組的大小為多個Cache line的大小，一個組映射到對應的多個連續的Cache line，也就是一個Cache組，并且該組內的任意一塊可以映射到對應Cache組的任意一個?？梢钥闯?，在組外，其采用直接關聯型 Cache 的映射方式，而在組內，則采用全關聯型Cache 的映射方式。

假設有一個4路組關聯型Cache，其大小為1M，一個Cache line的大小為64B，那么總共有16K個 Cache line，但是在4路組關聯的情況下，我們并不是簡簡單單擁有16K個Cache line，而是擁有了4K 個組，每個組有4個Cache line。一個內存單元可以緩存到它所對應的組中的任意一個Cache line中去。圖 6以4路組關聯型 Cache 為例介紹其在Cache中的查找過程。目錄表由三部分組成，分別是“區號+塊號”、Cache塊號和有效位。當收到一個內存地址時，該地址被分成四部分：區號A、組號B、塊號C和塊內地址D。首先，根據組號 B 按地址查找到一組目錄表項，在4 路組關聯中，則有四個表項，每個表項都有可能存放該內存塊；然后，根據區號A和塊號C在該組表項中進行關聯查找（即并行查找，為了提高效率），如果匹配且有效位有效，則表明該數據塊緩存在 Cache 中，得到Cache塊號，加上塊內地址D，可以得到該內存地址在Cache中映射的地址，得到數據；如果沒有找到匹配項或者有效位無效，則表示該內存塊不在Cache中，需要處理器到內存中讀取。

圖 6