本節書摘來自華章出版社《深入淺出dpdk》一書中的第2章，第2.3節cache位址映射和變換，作者朱河清，梁存銘，胡雪焜，曹水 等，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。
2.3 cache位址映射和變換
cache的容量一般都很小，即使是最大的三級cache（l3）也隻有20mb～30mb。而當今記憶體的容量都是以gb作為機關，在一些伺服器平台上，則都是以tb（1tb=1024gb）作為機關。在這種情況下，如何把記憶體中的内容存放到cache中去呢？這就需要一個映射算法和一個分塊機制。
分塊機制就是說，cache和記憶體以塊為機關進行資料交換，塊的大小通常以在記憶體的一個存儲周期中能夠通路到的資料長度為限。當今主流塊的大小都是64位元組，是以一個cache line就是指64個位元組大小的資料塊。
而映射算法是指把記憶體位址空間映射到cache位址空間。具體來說，就是把存放在記憶體中的内容按照某種規則裝入到cache中，并建立記憶體位址與cache位址之間的對應關系。當内容已經裝入到cache之後，在實際運作過程中，當處理器需要通路這個資料塊内容時，則需要把記憶體位址轉換成cache位址，進而在cache中找到該資料塊，最終傳回給處理器。
根據cache和記憶體之間的映射關系的不同，cache可以分為三類：第一類是全關聯型cache（full associative cache），第二類是直接關聯型cache（direct mapped cache），第三類是組關聯型cache（n-ways associative cache）。
2.3.1 全關聯型cache
全關聯型cache是指主存中的任何一塊記憶體都可以映射到cache中的任意一塊位置上。在cache中，需要建立一個目錄表，目錄表的每個表項都有三部分組成：記憶體位址、cache塊号和一個有效位。當處理器需要通路某個記憶體位址時，首先通過該目錄表查詢是否該内容緩存在cache中，具體過程如圖2-5所示。
首先，用記憶體的塊位址a在cache的目錄表中進行查詢，如果找到等值的記憶體塊位址，檢查有效位是否有效，隻有有效的情況下，才能通過cache塊号在cache中找到緩存的記憶體，并且加上塊内位址b，找到相應資料，這時則稱為cache命中，處理器拿到資料傳回；否則稱為不命中，處理器則需要在記憶體中讀取相應的資料。
可以看出，使用全關聯型cache，塊的沖突最小（沒有沖突），cache的使用率也高，但是需要一個通路速度很快的相聯存儲器。随着cache容量的增加，其電路設計變得十分複雜，是以隻有容量很小的cache才會設計成全關聯型的（如一些英特爾處理器中的tlb cache）。
2.3.2 直接關聯型cache
直接關聯型cache是指主存中的一塊記憶體隻能映射到cache的一個特定的塊中。假設一個cache中總共存在n個cache line，那麼記憶體被分成n等分，其中每一等分對應一個cache line。舉個簡單的例子，假設cache的大小是2k，而一個cache line的大小是64b，那麼就一共有2k/64b=32個cache line，那麼對應我們的記憶體，第1塊（位址0～63），第33塊（位址6432～6433-1），以及第（n32+1）塊（位址64（n-1）～64n-1）都被映射到cache第一塊中；同理，第2塊，第34塊，以及第（n32+2）塊都被映射到cache第二塊中；可以依次類推其他記憶體塊。
直接關聯型cache的目錄表隻有兩部分組成：區号和有效位。其查找過程如圖2-6所示。首先，記憶體位址被分成三部分：區号a、塊号b和塊内位址c。根據區号a在目錄表中找到完全相等的區号，并且在有效位有效的情況下，說明該資料在cache中，然後通過記憶體位址的塊号b獲得在cache中的塊位址，加上塊内位址c，最終找到資料。如果在目錄表中找不到相等的區号，或者有效位無效的情況下，則說明該内容不在cache中，需要到記憶體中讀取。
可以看出，直接關聯是一種很“死”的映射方法，當映射到同一個cache塊的多個記憶體塊同時需要緩存在cache中時，隻有一個記憶體塊能夠緩存，其他塊需要被“淘汰”掉。是以，直接關聯型命中率是最低的，但是其實作方式最為簡單，比對速度也最快。
2.3.3 組關聯型cache
組關聯型cache是目前cache中用的比較廣泛的一種方式，是前兩種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中去。
圖2-7以4路組關聯型cache為例介紹其在cache中的查找過程。目錄表由三部分組成，分别是“區号+塊号”、cache塊号和有效位。當收到一個記憶體位址時，該位址被分成四部分：區号a、組号b、塊号c和塊内位址d。首先，根據組号b按位址查找到一組目錄表項，在4路組關聯中，則有四個表項，每個表項都有可能存放該記憶體塊；然後，根據區号a和塊号c在該組表項中進行關聯查找（即并行查找，為了提高效率），如果比對且有效位有效，則表明該資料塊緩存在cache中，得到cache塊号，加上塊内位址d，可以得到該記憶體位址在cache中映射的位址，得到資料；如果沒有找到比對項或者有效位無效，則表示該記憶體塊不在cache中，需要處理器到記憶體中讀取。
實際上，直接關聯型cache和全關聯型cache隻是組關聯型cache的特殊情況，當組内cache line數目為1時，即為直接關聯型cache。而當組内cache line數目和cache大小相等時，即整個cache隻有一個組，這成為全關聯型cache。