塊映射策略

塊映射策略是指當需要將來自記憶體的新數據塊裝入高速快取時，由塊映射策略決定它的存放位置。根據塊在高速快取內的位置，塊映射策略可分成直接映射、全相聯映射和組相聯映射。

基本介紹

• 中文名：塊映射策略
• 外文名：Block mapping strategy
• 領域：計算機

背景

在主存和CPU之間可設定一個速度很快而容量相對較小的存儲器，在其中存放CPU當前正在使用以及一個較短的時間內將要使用的程式和數據，這樣，可大大加快CPU訪問存儲器的速度，提高機器的運行效率。

Cache的功能是用來存放那些近期需要運行的指令與數據，目的是提高CPU對存儲器的訪問速度，為此需要解決2個技術問題：

一是主存地址與快取地址的映射及轉換，就是塊映射策略。

二是按一定原則對Cache的內容進行替換，就是塊替換策略。

詳細介紹

全相聯映射方式

全相聯映射是指主存中任意一個塊都可以映射到Cache中任意一個塊的方式，也就是說，當主存中的某一塊需調入Cache時，可根據當時Cache的塊占用或分配情況，選擇一個塊給主存塊存儲，所選的Cache塊可以是Cache中的任意一個塊。例如，設Cache共有2塊，主存共有2塊，當主存的某一塊j需調進Cache中時，它可以存入Cache的塊0、塊1、…、塊i、…或塊2-1的任意一塊上。如圖一所示。

（圖一）全相聯映射方式

在全相聯映射方式下，CPU的訪主存地址為如圖二形式：

圖二

其中，M為主存的塊號，W為塊內的字號。而CPU訪Cache的地址形式為，如圖三所示：

圖三

其中，C為Cache的塊號，W為塊內的字號。

主存地址到Cache地址的轉換是通過查找一個由相聯存儲器實現的塊表來完成的，其形成過程如圖四所示。

（圖四）全相聯映射的地址轉換

當一個主存塊調入Cache中時，會同時在一個存儲主存塊號和Cache塊號映射表的相聯存儲器中進行登記。CPU訪存時，首先，根據主存地址中的主存塊號M在相聯存儲器中查找Cache塊號C，若找到，則本次訪Cache命中，於是將對應的Cache塊號取出，並送訪Cache地址的塊號C欄位，緊接著將主存地址的塊內字號W直接送Cache地址的塊內字號W欄位，從而形成一個訪Cache的地址，最後根據該地址完成對Cache單元的訪問。

優點：命中率比較高，Cache存儲空間利用率高。

缺點：相聯存儲器龐大，比較電路複雜，訪問相關存儲器時，每次都要與全部內容比較，速度低，成本高，因而只適合於小容量的Cache之用，套用少。

直接相聯映射

地址映象規則：主存儲器中一塊只能映象到Cache的一個特定的塊中。

(1)主存與快取分成相同大小的數據塊。

(2)主存容量應是快取容量的整數倍，將主存空間按快取的容量分成區，主存中每一區的塊數與快取的總塊數相等。

(3)主存中某區的一塊存入快取時只能存入快取中塊號相同的位置。

圖五表示出了直接相聯映象規則。可見，主存中各區內相同塊號的數據塊都可以分別調入快取中塊號相同的地址中，但同時只能有一個區的塊存入快取。由於主、快取塊號相同，因此，目錄登記時，只記錄調入塊的區號即可。

（圖五）直接相聯映射

圖六表示出了主、緩衝地址格式、目錄表的格式及地址變換規則。主、快取塊號及塊內地址兩個欄位完全相同。目錄表存放在高速小容量存儲器中，其中包括二部分：數據塊在主存的區號和有效位。目錄表的容量與快取的塊數相同。

（圖六）直接相聯地址轉換

地址變換過程：用主存地址中的塊號B去訪問目錄存儲器，把讀出來的區號與主存地址中的區號E進行比較，比較結果相等，有效位為1，則Cache命中，可以直接用塊號及塊內地址組成的緩衝地址到快取中取數；比較結果不相等，有效位為1，可以進行替換，如果有效位為0，可以直接調入所需塊。

優點：地址映象方式簡單，數據訪問時，只需檢查區號是否相等即可，因而可以得到比較快的訪問速度，硬體設備簡單。

缺點：替換操作頻繁，命中率比較低。

舉例：上例中，主存容量為1M，Cache的容量為32KB，每塊的大小為16個字（或位元組）。劃出主、快取的地址格式、目錄表格式及其容量。

容量：與緩衝塊數量相同即211=2048（或32K/16=2048）。

組相聯映射方式

組相聯映射實際上是直接映射和全相聯映射的折中方案，其組織結構如圖七所示。主存和Cache都分組，主存中一個組內的塊數與Cache中的分組數相同，組間採用直接映射，組內採用全相聯映射。也就是說，將Cache分成u組，每組v塊，主存塊存放到哪個組是固定的，至於存到該組哪一塊則是靈活的。例如，主存分為256組，每組8塊，Cache分為8組，每組2塊。

（圖七）組相聯映射

主存中的各塊與Cache的組號之間有固定的映射關係，但可自由映射到對應Cache組中的任何一塊。例如，主存中的第0塊、第8塊……均映射於Cache的第0組，但可映射到Cache第0組中的第0塊或第1塊；主存的第1塊、第9塊……均映射於Cache的第1組，但可映射到Cache第1組中的第2塊或第3塊。

優點：塊的衝突機率比較低，塊的利用率大幅度提高，塊失效率明顯降低。

缺點：實現難度和造價要比直接映象方式高。

常採用的組相聯結構Cache，每組內有2、4、8、16塊，稱為2路、4路、8路、16路組相聯Cache。組相聯結構Cache是前兩種方法的折中方案，適度兼顧二者的優點，儘量避免二者的缺點，因而得到普遍採用。