計算機組成原理（4）-----Cache的原理及相關(guān)知識點

這篇具有很好參考價值的文章主要介紹了計算機組成原理（4）-----Cache的原理及相關(guān)知識點。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

1.Cache的原理

2.Cache的性能

3.Cache和主存的映射方式

?（1）全相聯(lián)映射

（2）直接映射

（3）組相聯(lián)映射

4.替換算法

(1)隨機算法(RAND)

(2)先進先出算法(FIFO)

(3)近期最少使用(LRU)

(4)最近不經(jīng)常使用(LFU)

5.Cache寫策略

(1)寫命中

?寫回法

?全寫法

(2)寫不命中

?寫分配法

?非寫分配法

補充:

1.Cache的原理

Cache被繼承在CPU內(nèi)部，用SRAM實現(xiàn)，速度快，集成度低（在芯片大小不能很大的情況下，Cache被允許的存儲空間非常小），成本高

基于局部性原理，不難想到，可以把CPU目前訪問的地址“周圍”的部分?jǐn)?shù)據(jù)復(fù)制到cache中，當(dāng)CPU想訪問這些數(shù)據(jù)時，直接到Cache中尋找即可，提高了CPU的運行速度。

對于局部性原理的說明：

如下圖所示，二維的數(shù)組會在內(nèi)存中被順序存放，若現(xiàn)在訪問的是a[0][0]數(shù)組，那么與其相鄰的數(shù)組可能很快會被訪問，這就是空間局部性

空間局部性：在最近的未來要用到的信息(指令和數(shù)據(jù))，很可能與現(xiàn)在正在使用的信息在存儲空間上是鄰近的

時間局部性：在最近的未來要用到的信息，很可能是現(xiàn)在正在使用的信息，例如循環(huán)結(jié)構(gòu)的指令代碼。

若把程序A改為程序B，即按列訪問，那么其訪問二維數(shù)組的順序為a[0][0],a[1][0],a[2][0]

可以發(fā)現(xiàn)，程序B空間局部性更差一些。

2.Cache的性能

CPU先訪問Cache，若Cache未命中再訪問主存，設(shè)為CPU訪問一次Cache所需時間，為CPU訪問一次主存所需時間。若CPU想要訪問的信息已在Cache中，那么稱為CPU命中，命中率為H，那么缺失(未命中)率M=1-H

那么系統(tǒng)的平均訪問時間t為：

$計算機組成原理（4）-----Cache的原理及相關(guān)知識點,計算機組成原理,學(xué)習(xí)日常（考研向）,緩存,Cache的原理,Cache和主存的映射方式,替換算法,Cache的寫策略,多級Cache,Cache的性能$

計算機組成原理（4）-----Cache的原理及相關(guān)知識點,計算機組成原理,學(xué)習(xí)日常（考研向）,緩存,Cache的原理,Cache和主存的映射方式,替換算法,Cache的寫策略,多級Cache,Cache的性能

若CPU同時到Cache和主存中找需要的數(shù)據(jù)，若在Cache中命中，若Cache命中，則立即停止訪問主存，那么訪問的時間為,若Cache未命中，由于是同時查找，那么訪問的時間為，那么總公式為：

$計算機組成原理（4）-----Cache的原理及相關(guān)知識點,計算機組成原理,學(xué)習(xí)日常（考研向）,緩存,Cache的原理,Cache和主存的映射方式,替換算法,Cache的寫策略,多級Cache,Cache的性能$

例如：

假設(shè)Cache的速度是主存的5倍，且Cache的命中率為95%)，則采用cache后，存儲器性能提高多少(設(shè)Cache和主存同時被訪問，若cache命中則中斷訪問主存)?

若Cache和主存同時訪問，命中時訪問時間為t，未命中時訪問時間為5t
平均訪問時間為 0.95xt + 0.05x5t = 1.2t

故性能為原來的 5t/1.2t??4.17倍

若先訪問Cache再訪問主存，命中時訪問時間為t，未命中時訪問時間為t+5t

平均訪問時間為T=0.95xt + 0.05x6t = 1.25t

故性能為原來的5t/1.25t = 4倍

基于局部性原理，不難想到，可以把CPU目前訪問的地址“周圍”的部分?jǐn)?shù)據(jù)放到Cache中。如何界定“周圍”？

可以將主存的存儲空間“分塊”，如：每 1KB為一塊。主存與Cache之間以“塊”為單位進行數(shù)據(jù)交換

在CPU訪問某個內(nèi)存數(shù)據(jù)時，可以通過其地址信息判斷他屬于哪一個塊，并且把這一塊復(fù)制到Cache中

如圖所示，主存容量為4MB（2^22），每一塊為1K(2^10)，那么整個主存被分為2^12=4096塊

所以主存的地址共22位，結(jié)構(gòu)如下：

同理，我們將Cache分為大小相同的塊，那么主存與Cache就能進行以“塊”為單位的數(shù)據(jù)交換

注：操作系統(tǒng)中，通常將主存中的“一個塊”也稱為”一個頁/頁面/頁框”，Cache中的“塊”也稱為“行”

3.Cache和主存的映射方式

CPU如何區(qū)分Cache和主存的數(shù)據(jù)塊的對應(yīng)關(guān)系？

CPU先訪問Cache，再訪問內(nèi)存，并將內(nèi)存相應(yīng)的塊數(shù)據(jù)復(fù)制到Cache中（不是將其從內(nèi)存中刪除）?，即每次被訪問的主存塊一定會被立即調(diào)入Cache，那么如何記錄主存塊與Cache塊的映射關(guān)系呢？

?（1）全相聯(lián)映射

主存塊可以放在Cache的任意位置

（2）直接映射

每個主存塊只能放到一個特定的位置：Cache塊號=主存塊號%Cache總塊數(shù)

例如主存塊號為1，9的內(nèi)存塊都會被放到Cache塊號為1的位置。

（3）組相聯(lián)映射

將Cache的各個塊進行分組，每個分組的總塊數(shù)相同，每個主存塊可放到特定分組中的任意一個位置：組號=主存塊號%分組數(shù)

例如下圖中Cache被分為4個分組，那么對于內(nèi)存塊號為1的內(nèi)存塊就是1%4=1，那么1號內(nèi)存塊就會被放在Cache中第1組的任意空閑位置。

我們回到最初的問題：CPU如何區(qū)分Cache和主存的數(shù)據(jù)塊的對應(yīng)關(guān)系呢?

可以給每個cache塊增加一個“標(biāo)記”記錄對應(yīng)的主存塊號,例如0號Cache塊的標(biāo)記為9,則表示0號Cache塊的數(shù)據(jù)是9號內(nèi)存塊的副本

若2進制表示,初始都為0,沒有數(shù)據(jù)的則記為0,但是0也可以表示為是主存號為0的內(nèi)存塊的副本,所以光有標(biāo)記不行,還需要增加有效位

有效位的1表示有效,0表示無效,如下圖所示,只有7號Cache塊標(biāo)記為0,有效位為1,表示7號Cache塊存儲的是0號內(nèi)存塊的副本,其余標(biāo)記為0的Cache塊,則表示沒有數(shù)據(jù)

對于全相聯(lián)映射:

假設(shè)某個計算機的主存地址空間大小為256MB，按字節(jié)編址，其數(shù)據(jù)Cache有8個Cache行(即Cache塊,與主存快的大小相等)，行長為64B。

256M=2^28主存的地址,共28位,

按照如上結(jié)構(gòu),給定主存地址如下所示:

全相聯(lián)映射的過程,全相聯(lián)映射中,主存塊可以放到Cache中的任意一個位置,如下圖所示,主存塊映射到3號Cache塊,首先會將其有效位置1,接著標(biāo)記其映射的是主存的哪一位置,即標(biāo)記主存塊號(22位)

若CPU需要訪問主存地址1.....1101001110:

①CPU會將主存地址的前22位，對比Cache中所有塊的標(biāo)記;

②若標(biāo)記匹配且有效位=1，則Cache命中，在Cache中訪問塊內(nèi)地址為001110的單元

③若未命中或有效位=0，則正常訪問主存

優(yōu)點:Cache存儲空間利用充分命中率高;

缺點:查找“標(biāo)記”最慢，有可能需要對比所有行的標(biāo)記

對于直接映射:

假設(shè)某個計算機的主存地址空間大小為256MB，按字節(jié)編址，其數(shù)據(jù)Cache有8個Cache行，行長為64B。
直接映射，主存塊在Cache中的位置=主存塊號%Cache總塊數(shù)

例如,對于0號內(nèi)存塊,只能放到0%8=0,即0號Cache塊,將有效位改為1,同時標(biāo)記為0...0000(22位)

若想將8號內(nèi)存塊調(diào)入Cache,8%8=0,則需要將之前存放的數(shù)據(jù)覆蓋,同時要把標(biāo)記改為8號主存塊的塊號0...01000

所以,如果采用直接映射的方式,雖然其他地方有空閑的Cache塊,但是8號主存塊不能使用

相比于全相聯(lián)映射,直接映射靈活性低,空間利用率也不充分

是否能優(yōu)化標(biāo)記呢?

對于上圖Cache塊數(shù)為8,主存塊號%2^3,相當(dāng)于留下主存塊號最后3位二進制數(shù),表示主存塊在Cache中的位置,也就是說某一主存塊能夠存放在0號 Cache,那么這個主存塊的塊號的末尾三位一定是000

我們已經(jīng)知道主存塊放在Cache中的位置,就沒必要記錄末尾3位了,將主存塊號的其余位作為標(biāo)記即可(標(biāo)記保留19位即可,即塊號的前19位)

總結(jié):

若Cache總塊數(shù)=2^n,則主存塊號末尾n位直接反映它在Cache中的位置,將主存塊號的其余位作為標(biāo)記即可

基于這種方式,CPU如何訪問主存地址:

若CPU訪問主存地址0...01000 001110:

①根據(jù)主存塊號的后3位確定Cache行

②若主存塊號的前19位與Cache標(biāo)記匹配且有效位=1，則Cache命中，在Cache塊中訪問塊內(nèi)地址為001110的單元。

③若未命中或有效位=0，則正常訪問主存

優(yōu)點:對于任意一個地址，只需對比一個“標(biāo)記”，速度最快;

缺點:由于某個主存塊只能放到Cache中的固定位置,Cache存儲空間利用不充分，命中率低

對于組相聯(lián)映射:

假設(shè)某個計算機的主存地址空間大小為256MB，按字節(jié)編址，其數(shù)據(jù)Cache有8個Cache行，行診為64B。
組相聯(lián)映射，所屬分組=主存塊號%分組數(shù)

假設(shè)Cache采用2路組相聯(lián)映射---2塊為1組,分四組

分為4組,所屬分組=主存塊號%分組數(shù)=主存塊號%2^2,相當(dāng)于只保留了主存塊號的末尾2位來表示所屬分組的組號,既然主存塊出現(xiàn)在Cache中的同一組,那么說明主存塊號末尾2位一定相同,所以標(biāo)記就沒有必要記錄這兩位了,所以對于這題的標(biāo)記,只需要取主存塊號前20位即可

總結(jié):

CPU訪問主存地址:1....1101001110

① 根據(jù)主存塊號的后2位確定所屬分組號

② 若主存塊號的前20位與分組內(nèi)的某個標(biāo)記匹配且有效位=1，則Cache命中，在Cache中訪問塊內(nèi)地址為 001110 的單元。

③若未命中或有效位=0，則正常訪問主存

優(yōu)點:另外兩種方式的折中，綜合效果較好

注:n路組相聯(lián)映射----每n個Cache行為一組

4.替換算法

Cache很小，主存很大，而每次被訪問的主存塊,一定會被立即調(diào)入Cache,如果Cache滿了怎么辦？?

(1)對于全相聯(lián)映射

對于這種方式,每一個主存塊,可能被放到Cache中的任何塊中,所以只有Cache完全滿了才需要替換需要在全局選擇替換哪一塊

(2)對于直接映射

對于這種方式,某一主存塊會被放到Cache中的指定位置,所以如果對應(yīng)位置非空，則毫無選擇地直接替換

計算機組成原理（4）-----Cache的原理及相關(guān)知識點,計算機組成原理,學(xué)習(xí)日常（考研向）,緩存,Cache的原理,Cache和主存的映射方式,替換算法,Cache的寫策略,多級Cache,Cache的性能

(3)對于組相聯(lián)映射

對于這一方式,某一主存塊會被放到固定分組中的任意位置,分組內(nèi)滿了才需要替換,需要在分組內(nèi)選擇替換哪一塊

所以替換算法只會被應(yīng)用到全相聯(lián)映射與組相聯(lián)映射中,對于直接映射,無需考慮替換算法,這里以全相聯(lián)映射為例,講解以下替換算法:

(1)隨機算法(RAND)

隨機算法(RAND,Random)----若Cache已滿，則隨機選擇一塊替換

設(shè)總共有4個Cache塊，初始整個Cache為空。采用全相聯(lián)映射，依次訪問主存塊{1,2,3,4,1,2,5,1, 2,3,4,5}??

如圖所示,每訪問一個主存塊,都需要將其從主存調(diào)入Cache,由于前4次訪問,Cache都未被裝滿,所以不需要進行Cache替換

由于1,2號主存塊已經(jīng)在Cache中,所以Cache命中

現(xiàn)在訪問5號主存塊,就需要立即將5號主存塊調(diào)入Cache,根據(jù)隨機算法的規(guī)則,則隨機選擇一個Cache塊替換,其他同理:

隨機算法----實現(xiàn)簡單，但完全沒考慮局部性原理，命中率低，實際效果很不穩(wěn)定

(2)先進先出算法(FIFO)

先進先出算法(FIFO,First In First Out)--若Cache已滿，則替換最先被調(diào)入Cache 的塊

設(shè)總共有4個Cache塊，初始整個Cache為空。采用全相聯(lián)映射，依次訪問主存塊{1,2,3,4,1,2,5, 1, 2, 3, 4, 5}

前面與隨機算法同理:

接下來訪問5號主存塊,由于5號主存塊沒有在Cache中,所以5號主存塊會被調(diào)入Cache,根據(jù)先進先出的規(guī)則,由于最先被調(diào)入的是1號主存塊,所以1號主存塊先被淘汰,將5號主存塊放入1號主存塊原來放的Cache中:

現(xiàn)在在Cache中,最先調(diào)入Cache的是2號主存塊,所以淘汰2號主存塊,將1號主存塊放入到2號主存塊原來放的Cache中,其他以此類推:

先進先出算法----實現(xiàn)簡單，最開始按#0#1#2#3(Cache行號遞增的方式)放入Cache，之后輪流替換#0#1#2#3

FIFO依然沒考慮局部性原理，最先被調(diào)入Cache的塊也有可能是被頻繁訪問的,同時先進先出算法會出現(xiàn)抖動現(xiàn)象:頻繁的換入換出現(xiàn)象(剛被替換的塊很快又被調(diào)入)

(3)近期最少使用(LRU)

近期最少使用算法(LRU,Least Recently Used)----為每一個Cache塊設(shè)置一個"計數(shù)器"，用于記錄每個Cache塊已經(jīng)有多久沒被訪問了。當(dāng)Cache滿后替換“計數(shù)器”最大的

如下圖所示,接下來需要將5號內(nèi)存塊調(diào)入Cache,那么從5這個位置往前看,依次為2,1,4,3,所以最久未被訪問的是3號內(nèi)存塊,替換3號內(nèi)存塊,調(diào)入5號內(nèi)存塊

所以若需要將某一內(nèi)存塊調(diào)入Cache,就從這一內(nèi)存塊往前看,替換最久未被訪問的內(nèi)存塊

若使用近期最少使用算法,每個Cache行不僅需要記錄標(biāo)記和有效位,還必須記錄"計數(shù)器"

①命中時，所命中的行的計數(shù)器清零，比其低的計數(shù)器加1，其余不變;

②未命中且還有空閑行時，新裝入的行的計數(shù)器置0，其余非空閑行全加1;

③未命中且無空閑行時,計數(shù)值最大的行的信息塊被淘汰，新裝行的塊的計數(shù)器置0，其余全加1。

例如,剛開始1號主存塊被調(diào)入Cache中,沒有命中,并且依然有空閑行,所以1號主存塊被調(diào)入0號Cache中,那么將0號Cache行的計數(shù)器置0,因為其他行也空閑,所以不需要加1;

同理,2號主存塊調(diào)入到1號Cache中,那么將2號Cache的計數(shù)器置0,并且將0號Cache加1,依次類推:

接下來訪問1號內(nèi)存塊,由于Cache命中,那么會把命中的行計數(shù)器清零,比其更低的計數(shù)器加1,其余不變

2號內(nèi)存塊同理:

接下來5號內(nèi)存塊會替換"計數(shù)值最大"的行,新裝入行的塊計數(shù)器置0,其余全部加1

接下來訪問1號內(nèi)存塊,Cache命中,所以把命中的行的計數(shù)器清零,比其低的計數(shù)器加1,其余不變

在這里我們同樣可以把3+1=4,但是這是沒有必要的,因為設(shè)置計數(shù)器是想通過判斷值的大小,選擇要替換的內(nèi)存塊,要替換"計數(shù)器"最大的,所以就算不加+1,3也是最大的

注:由于Cache填滿前計數(shù)的起點是不同步的,接下來填滿后,若要替換,也是一次替換一個內(nèi)存塊,所以一定不會有相同的計數(shù)

計數(shù)器比2大的數(shù)值不變的好處有以下兩個:

①當(dāng)只有4個Cache行時,計數(shù)器的值只可能出現(xiàn)0,1,2,3,Cache塊的總數(shù)=2^n，則計數(shù)器只需n位。且Cache裝滿后所有計數(shù)器的值一定不重復(fù)

②若以下圖中,CPU一直訪問內(nèi)存塊1,如果不設(shè)置這一機制,則計數(shù)器一直+1,可能導(dǎo)致計數(shù)器溢出

其他同理,最終得到:

LRU算法----基于"局部性原理",近期被訪問過的主存塊，在不久的將來也很有可能被再次訪問，因此淘汰最久沒被訪問過的塊是合理的。LRU算法的實際運行效果優(yōu)秀，Cache命中率高。

但若被頻繁訪問的主存塊數(shù)量>Cache行的數(shù)量，則有可能發(fā)生“抖動”，如:{1,2,3,4,5,1,2,3,4,5,1,2...}

(4)最近不經(jīng)常使用(LFU)

最不經(jīng)常使用算法(LFU,Least Frequently Used )----為每一個Cache塊設(shè)置一個“計數(shù)器”，用于記
錄每個Cache塊被訪問過幾次。當(dāng)Cache滿后替換“計數(shù)器”最小的

① 新調(diào)入的塊計數(shù)器=0，之后每被訪問一次計數(shù)器+1。需要替換時，選擇計數(shù)器最小的一行計算機組成原理（4）-----Cache的原理及相關(guān)知識點,計算機組成原理,學(xué)習(xí)日常（考研向）,緩存,Cache的原理,Cache和主存的映射方式,替換算法,Cache的寫策略,多級Cache,Cache的性能

② 接下來訪問5號主存塊,需要替換"計數(shù)器"最小的內(nèi)存塊,若有多個計數(shù)器最小的行，可按行號遞增或FIFO策略進行選擇,例如可以優(yōu)先淘汰行號較小的塊或淘汰先進的內(nèi)存塊,所以這里替換2號Cache行中的內(nèi)存塊

這里按照優(yōu)先淘汰行號較小的塊的規(guī)則,最終得到:

采用這種算法的話,計數(shù)器的取值范圍:0~很大的值,那么每個Cache行所對應(yīng)的計數(shù)器,就需要使用較長的位數(shù)表示

同時,對于LFU算法---曾經(jīng)被經(jīng)常訪問的主存塊在未來不一定會用到(例如某段時間頻繁使用微信視頻聊天相關(guān)的塊,此時相關(guān)計數(shù)器會增加到很大,若之后不再需要視頻聊天,但相關(guān)Cache塊的計數(shù)器已經(jīng)很大了,所以相關(guān)內(nèi)存塊在Cache中的數(shù)據(jù)副本在短時間內(nèi)不會被淘汰),并沒有很好地遵循局部性原理(最不經(jīng)常使用算法可能會記錄下全局的訪問頻率)，因此實際運行效果不如LRU

5.Cache寫策略

CPU修改了Cache中的數(shù)據(jù)副本，如何確保主存中數(shù)據(jù)母本的一致性?

(1)寫命中

?寫回法

寫回法(write-back)----當(dāng)CPU對Cache寫命中時，只修改Cache的內(nèi)容，而不立即寫入主存，只有當(dāng)此塊被換出(淘汰)時才寫回主存

為了讓硬件能夠區(qū)分哪個Cache塊被修改過,哪個沒有被修改過,需要為每個Cache行增加一個臟位,當(dāng)一個Cache行的數(shù)據(jù)塊被修改,需要將這一Cache行對應(yīng)的臟位置1 ,這樣當(dāng)我們淘汰某一Cache行時,就可以判斷這一Cache行是否需要被寫入主存,而寫回主存的什么位置,則可以通過標(biāo)記判斷

這種方式減少了訪存次數(shù)，但存在數(shù)據(jù)不一致的隱患。

?全寫法

全寫法(寫直通法，write-through)----當(dāng)CPU對Cache寫命中時，必須把數(shù)據(jù)同時寫入Cache和主存，一般使用寫緩沖(write buffer)

當(dāng)Cache行中的數(shù)據(jù)被淘汰時,也不需要寫回主存中,因為數(shù)據(jù)隨時都是保持一致的

采用這種方法,CPU每次進行寫操作時,除了訪問Cache,也需要訪問主存,訪存次數(shù)增加，速度變慢,通常增加寫緩存(write buffer),寫緩存是用SRAM制造的,對寫緩沖的讀寫會比較快

當(dāng)CPU對某一地址的數(shù)據(jù)進行寫操作,并且這一地址命中時,CPU首先會向Cache中寫入這些數(shù)據(jù),另外CPU也會向?qū)懢彌_中寫入相應(yīng)的數(shù)據(jù),由于寫緩存是由SRAM實現(xiàn)的,所以寫入寫緩沖要比寫入主存更快

接下來CPU就可以做其他事了,在這期間,寫緩沖會在專門的控制電路控制下逐一寫回

使用寫緩沖，CPU寫的速度很快，若操作不頻繁,則效果很好。若寫操作很頻繁，可能會因為寫緩沖飽和而發(fā)生阻塞

(2)寫不命中

?寫分配法

寫分配法(write-allocate)---當(dāng)CPU對Cache寫不命中時，把主存中的塊調(diào)入Cache，在Cache中修改。(也就是主存的數(shù)據(jù)不動,CPU只是修改了Cache中的副本) 通常搭配寫回法(也就是Cache塊被淘汰后,才把一整塊的數(shù)據(jù)同步回主存)使用。