[科普中國]-塊映射策略

塊映射策略是指當(dāng)需要將來自內(nèi)存的新數(shù)據(jù)塊裝入高速緩存時，由塊映射策略決定它的存放位置。根據(jù)塊在高速緩存內(nèi)的位置，塊映射策略可分成直接映射、全相聯(lián)映射和組相聯(lián)映射。

背景在主存和CPU之間可設(shè)置一個速度很快而容量相對較小的存儲器，在其中存放CPU當(dāng)前正在使用以及一個較短的時間內(nèi)將要使用的程序和數(shù)據(jù)，這樣，可大大加快CPU訪問存儲器的速度，提高機器的運行效率。

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

一是主存地址與緩存地址的映射及轉(zhuǎn)換，就是塊映射策略。1

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

詳細介紹全相聯(lián)映射方式全相聯(lián)映射是指主存中任意一個塊都可以映射到Cache中任意一個塊的方式，也就是說，當(dāng)主存中的某一塊需調(diào)入Cache時，可根據(jù)當(dāng)時Cache的塊占用或分配情況，選擇一個塊給主存塊存儲，所選的Cache塊可以是Cache中的任意一個塊。例如，設(shè)Cache共有2塊，主存共有2塊，當(dāng)主存的某一塊j需調(diào)進Cache中時，它可以存入Cache的塊0、塊1、…、塊i、…或塊2-1的任意一塊上。如圖一所示。

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

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

其中，C為Cache的塊號，W為塊內(nèi)的字號。

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

當(dāng)一個主存塊調(diào)入Cache中時，會同時在一個存儲主存塊號和Cache塊號映射表的相聯(lián)存儲器中進行登記。CPU訪存時，首先，根據(jù)主存地址中的主存塊號M在相聯(lián)存儲器中查找Cache塊號C，若找到，則本次訪Cache命中，于是將對應(yīng)的Cache塊號取出，并送訪Cache地址的塊號C字段，緊接著將主存地址的塊內(nèi)字號W直接送Cache地址的塊內(nèi)字號W字段，從而形成一個訪Cache的地址，最后根據(jù)該地址完成對Cache單元的訪問。

優(yōu)點：命中率比較高，Cache存儲空間利用率高。

缺點：相聯(lián)存儲器龐大，比較電路復(fù)雜，訪問相關(guān)存儲器時，每次都要與全部內(nèi)容比較，速度低，成本高，因而只適合于小容量的Cache之用，應(yīng)用少。

直接相聯(lián)映射地址映象規(guī)則：主存儲器中一塊只能映象到Cache的一個特定的塊中。

(1)主存與緩存分成相同大小的數(shù)據(jù)塊。

(2)主存容量應(yīng)是緩存容量的整數(shù)倍，將主存空間按緩存的容量分成區(qū)，主存中每一區(qū)的塊數(shù)與緩存的總塊數(shù)相等。

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

圖五表示出了直接相聯(lián)映象規(guī)則。可見，主存中各區(qū)內(nèi)相同塊號的數(shù)據(jù)塊都可以分別調(diào)入緩存中塊號相同的地址中，但同時只能有一個區(qū)的塊存入緩存。由于主、緩存塊號相同，因此，目錄登記時，只記錄調(diào)入塊的區(qū)號即可。

圖六表示出了主、緩沖地址格式、目錄表的格式及地址變換規(guī)則。主、緩存塊號及塊內(nèi)地址兩個字段完全相同。目錄表存放在高速小容量存儲器中，其中包括二部分：數(shù)據(jù)塊在主存的區(qū)號和有效位。目錄表的容量與緩存的塊數(shù)相同。

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

優(yōu)點：地址映象方式簡單，數(shù)據(jù)訪問時，只需檢查區(qū)號是否相等即可，因而可以得到比較快的訪問速度，硬件設(shè)備簡單。

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

舉例：上例中，主存容量為1M，Cache的容量為32KB，每塊的大小為16個字（或字節(jié)）。劃出主、緩存的地址格式、目錄表格式及其容量。

容量：與緩沖塊數(shù)量相同即211=2048（或32K/16=2048）。

組相聯(lián)映射方式組相聯(lián)映射實際上是直接映射和全相聯(lián)映射的折中方案，其組織結(jié)構(gòu)如圖七所示。主存和Cache都分組，主存中一個組內(nèi)的塊數(shù)與Cache中的分組數(shù)相同，組間采用直接映射，組內(nèi)采用全相聯(lián)映射。也就是說，將Cache分成u組，每組v塊，主存塊存放到哪個組是固定的，至于存到該組哪一塊則是靈活的。例如，主存分為256組，每組8塊，Cache分為8組，每組2塊。

主存中的各塊與Cache的組號之間有固定的映射關(guān)系，但可自由映射到對應(yīng)Cache組中的任何一塊。例如，主存中的第0塊、第8塊……均映射于Cache的第0組，但可映射到Cache第0組中的第0塊或第1塊；主存的第1塊、第9塊……均映射于Cache的第1組，但可映射到Cache第1組中的第2塊或第3塊。

優(yōu)點：塊的沖突概率比較低，塊的利用率大幅度提高，塊失效率明顯降低。

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

常采用的組相聯(lián)結(jié)構(gòu)Cache，每組內(nèi)有2、4、8、16塊，稱為2路、4路、8路、16路組相聯(lián)Cache。組相聯(lián)結(jié)構(gòu)Cache是前兩種方法的折中方案，適度兼顧二者的優(yōu)點，盡量避免二者的缺點，因而得到普遍采用。

本詞條內(nèi)容貢獻者為:

王慧維 - 副研究員 - 西南大學(xué)