Cache映射是硬件層面物理塊與物理塊之間建立的聯(lián)系

理解Cache地址映射之前補充一些基礎(chǔ)知識，Cache的地址映射和MMU（內(nèi)存管理單元）和TLB Cache（轉(zhuǎn)譯查找緩存）中的映射是有區(qū)別的。Cache、TLB Cache、MMU在CPU中結(jié)構(gòu)如圖1所示，圖1展現(xiàn)的是Cortex A9 Processor內(nèi)部結(jié)構(gòu)，采用的指令和數(shù)據(jù)總線分開的哈佛結(jié)構(gòu)。

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

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

圖 1

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

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

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

圖 2

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

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

圖3

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

圖 4

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

圖 5

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

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

圖 6