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

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

圖 1

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

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

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

圖 2

映射算法是指把內(nèi)存地址空間映射到Cache地址空間。具體來說，就是把存放在內(nèi)存中的內(nèi)容按照某種規(guī)則裝入到 Cache 中，并建立內(nèi)存地址與 Cache 地址之間的對(duì)應(yīng)關(guān)系。當(dāng)處理器需要訪問這個(gè)數(shù)據(jù)塊內(nèi)容時(shí)，則需要把內(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時(shí)，可根據(jù)當(dāng)時(shí)Cache的塊占用或分配情況，選擇一個(gè)塊給主存塊存儲(chǔ)，所選的Cache塊可以是Cache中的任意一塊。例如，設(shè)Cache共有m塊，主存共有n塊，當(dāng)主存的某一塊j需調(diào)進(jìn)Cache中時(shí)，它可以存入Cache的塊0、塊1、…、塊i、… 或塊m的任意一塊上,如圖3所示，區(qū)別在于cache和主存塊的對(duì)應(yīng)關(guān)系不一樣。

圖3

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

圖 4

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

圖 5

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

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

圖 6