圖片來源：南京大學(xué)軟件學(xué)院COA課程PPT

?author:zzb

Github主頁 CSDN主頁

文章目錄

• 9 高速緩沖存儲器（Cache）
• Cache的設(shè)計要素
• • 一、cache容量
  • 二、映射功能
  • • 1.直接映射
    • 2.關(guān)聯(lián)映射
    • 3.組關(guān)聯(lián)映射（介于前面兩種方法之間）
  • 三、替換算法
  • • 1.最近最少使用算法（LRU）
    • 2.先進先出算法（FIFO）
    • 3.最不經(jīng)常使用算法（LFU）
    • 4.隨機替換算法（Random）
  • 四、寫策略
  • • 1.寫直達
    • 2.寫回法
  • 五、行大小
  • 六、cache數(shù)目
  • 總結(jié)
  • 總結(jié)

9 高速緩沖存儲器（Cache）

大部分是集成在CPU內(nèi)部的，存放的還是主存內(nèi)的信息，是主存內(nèi)部分信息的副本

如果不在cache中，那么會將包含這個字的固定大小的塊讀入cache，然后再從cache中把這個字傳給CPU

cache中除了要存內(nèi)容，還得存這個內(nèi)容的位置，因為CPU是通過位置來訪問主存中的內(nèi)容的，而不關(guān)心其中的內(nèi)容。

cache不是存放了完整的位置，而是通過tags標記來對應(yīng)內(nèi)容在內(nèi)存中的位置

如果大部分時間都是未命中，那么使用cache后反而時間會更慢，而事實上cache很好的處理了內(nèi)存墻問題，因此大部分情況應(yīng)當是命中的

這是由于程序訪問的局部性原理，即CPU總是會頻繁的訪問相同位置或者是相鄰位置的內(nèi)容：

• 時間局部性：在相對短時間內(nèi)，重復(fù)訪問相同位置的信息
• 空間局部性：在相對短時間內(nèi)，會訪問相鄰存儲位置的數(shù)據(jù)
  • 順序局部性：相鄰位置的按順序的，如訪問數(shù)組

注意這個塊是事先就在內(nèi)存中劃分好了（哪一部分屬于哪個塊都是確定的），要哪個字時，只要把這個字的所在塊搬過去，而不是臨時從這個字開始再劃分塊

所以只要想要訪問的字所屬的塊在cache中，那么這個字就在cache中，因此只要對每個塊做一個標記（塊號）就可以知道有沒有命中

cache中每一行是一個塊，記錄了塊的標記和塊中的K個字

T_A的兩個式子，是兩種不同的理解，第一行是分為命中和未命中來理解，第二行是分成check檢查階段和到主存取數(shù)據(jù)階段來理解的，一般第二行使用更多

Tc很快，Tm相對慢，因此Tc/Tm是比較小的值，所以p是相對很小時就能滿足條件。但事實上這個條件雖然小也很難滿足，因為cache容量遠小于主存容量，p實際上按概率來算應(yīng)該是cache的容量/主存容量，是非常小的，但之所以能滿足，就是因為前面提到的局部性原理

Cache的設(shè)計要素

一、cache容量

cache容量不是越大越好，也不是越小越好。

• 因為內(nèi)存是以地址來尋找的，所以直接解碼地址就能找到要的信息，而cache則是通過遍歷來找的（遍歷塊的標號），所以如果cache很大的話，會導(dǎo)致遍歷檢查的時間增加，增大了T_c。
• 如果cache很小的話，則可能出現(xiàn)從內(nèi)存中復(fù)制的新的塊把原來cache中的塊覆蓋后，又需要原來的塊中的內(nèi)容，因此又需要從內(nèi)存中復(fù)制到cache，浪費時間

二、映射功能

cache中記錄的是塊號，塊號要能反映地址

塊內(nèi)地址：如果一個塊內(nèi)有K個字節(jié)，那么地址的后log₂K位表示塊內(nèi)地址

而cache中分辨不同塊的標記可以直接使用塊號來作為標記，但這樣會造成一些浪費（塊號不是我們想要的信息），因此就要去想怎么盡可能縮短標記的長度

1.直接映射

比如0~7塊只能放到第一行，8~15塊只能放到第二行，因此如果加載了第2個塊，想再加載第3個塊，那么第3個塊會把第二個覆蓋

如上圖i=jmodCi=jmodCi=jmodC是間隔的把塊規(guī)定放到同一行，而不是上面的連續(xù)的幾個塊都只能在一個行中，顯然下面這種更合理，因為局部性原理，訪問相鄰塊的概率更大，因此間隔的放，可以把連續(xù)的塊都加載到cache中，而不會出現(xiàn)上面的覆蓋情況

映射到同一行的塊號（二進制表示）的后log2Clog_2Clog2?C位都是一樣的

因此只要比較塊號的前面log2M?log2Clog_2M-log_2Clog2?M?log2?C位即可（M是塊的數(shù)量，C是cache中行的數(shù)量）相當于把C個塊當作一個組，只要記錄這個組的地址即可

再看主存中一個具體的字節(jié)，它在主存的地址可以被分成三個部分：

• 塊內(nèi)地址（用于塊內(nèi)尋址）
• 塊映射到cache的行號
• 若干個塊分為一個組對應(yīng)的標號，用于區(qū)分映射到相同行的不同塊，記錄為cache標號

• 優(yōu)點：因為塊映射到cache中的行的位置是固定的，因此檢查時，只要去找這一行中有沒有要的數(shù)據(jù)即可，而不必全部搜索一遍，所以T_c是固定的，不會因cache容量增大而使得T_c變大
• 缺點：抖動現(xiàn)象：如果要重復(fù)訪問的兩個塊剛好映射到同一行，就會降低命中率，當兩個塊比較相鄰（才可能被重復(fù)訪問）時并被映射到同一行，說明cache比較小，即行數(shù)比較少時會出現(xiàn)這種情況。
• 因此直接映射適合大容量cache使用

1. 根據(jù)內(nèi)存地址的塊地址去找cache對應(yīng)行
2. 再比較cache標記和主存地址的塊標記是否相等
3. 相等就命中，命中就再根據(jù)主存地址的塊內(nèi)地址到cache取對應(yīng)字節(jié)

2.關(guān)聯(lián)映射

關(guān)聯(lián)映射中的標記必須是塊號，所以長度只能是log2Mlog_2Mlog2?M，不像直接映射中有規(guī)律，可以縮短。關(guān)聯(lián)映射是可以按一定規(guī)則放的，只要有空位就能放

• 優(yōu)點：在cache比較小時不會出現(xiàn)抖動，想加載哪些塊都可，不會出現(xiàn)反復(fù)加載，除非cache行數(shù)不夠了
• 缺點：怎么規(guī)定放塊實現(xiàn)比較復(fù)雜，同時檢查時要平均檢查12\frac{1}{2}21?的cache，在cache很大時開銷太大
• 因此關(guān)聯(lián)映射適合容量小的cache

3.組關(guān)聯(lián)映射（介于前面兩種方法之間）

K是指每組里面包含的行數(shù)，S是組數(shù)

即將cache分成不同的組，一個塊只能映射到對應(yīng)的組中，但在這個組中可以放在任意一行

標記中不需要存全部塊號，因為組號是固定的，只要log2M?log2Slog_2M-log_2Slog2?M?log2?S位即可

**關(guān)聯(lián)度：**一個塊映射到cache中可能存放的位置個數(shù)

關(guān)聯(lián)度越低，命中率越低，檢查是否命中的時間越短，標記所占的額外空間開銷越小

三、替換算法

目的：將最不可能被使用的行替換掉，盡可能增大命中率

替換算法使用硬件來實現(xiàn)，因為替換需要非常快的速度

1.最近最少使用算法（LRU）

假設(shè)前提相當于看文件被修改過到現(xiàn)在的時間

需要限定路的數(shù)目，多路會很復(fù)雜，在模擬中可以通過設(shè)置時間戳的方式來記錄最近使用的時間，要替換時最早的那個就是最近最少使用的

2.先進先出算法（FIFO）

假設(shè)前提相當于看文件被創(chuàng)建到現(xiàn)在的時間

無需限定路的數(shù)目，只要循環(huán)輪下來即可

最開始初始化是應(yīng)該把每一行的use位設(shè)為0，因為相當于替換哪行都可以。

替換時把被替換的行設(shè)為1，把它的下一行設(shè)為0（如果是最開始，那么它的下一行本來就是0），如果被替換的是最后一行，那么把第一行設(shè)為0，這樣循環(huán)，可以保證一個組中至少存在一個use位為0的行，從而用新數(shù)據(jù)去替換這一行

3.最不經(jīng)常使用算法（LFU）

4.隨機替換算法（Random）

能到cache中的的塊都是使用率較高的，否則不會進到cache中，所以不再去區(qū)分cache中塊的使用率

性能只比其他區(qū)分cache中塊優(yōu)先級的差一點點，但實現(xiàn)起來相對簡單很多

四、寫策略

寫數(shù)據(jù)時，CPU同樣會優(yōu)先修改cache中的數(shù)據(jù)

對cache的修改不需要直接同步到內(nèi)存中，因為之后CPU讀的還是cache中的內(nèi)容，因此只要存在cache中即可；只有在cache中這個塊要被替換時，才要把修改同步到內(nèi)存，否則這個修改就丟失了

1.寫直達

對于多CPU共享一個內(nèi)存的情況，實時同步數(shù)據(jù)是必要的

2.寫回法

缺點就是如果這個塊被修改但沒有被替換，那么它不會寫回主存同步修改，而I/O模塊對主存如打印時就得不到最新的數(shù)據(jù)了，只能增加設(shè)計：在打印時把所有cache中臟位為1的都同步到主存

五、行大小

六、cache數(shù)目

L2容量比L1更大，L2從內(nèi)存中取了數(shù)據(jù)，L1從L2中取了數(shù)據(jù)，同樣找數(shù)據(jù)時也是先在L1中找，如果未命中，再去L2中找

為什么不只使用大容量的L2，而是加入了L1?

分立：對指令和數(shù)據(jù)分別用不同的cache

總結(jié)

)]

L2容量比L1更大，L2從內(nèi)存中取了數(shù)據(jù)，L1從L2中取了數(shù)據(jù)，同樣找數(shù)據(jù)時也是先在L1中找，如果未命中，再去L2中找

為什么不只使用大容量的L2，而是加入了L1?

[外鏈圖片轉(zhuǎn)存中…(img-Pa7XGQ10-1656554789633)]

分立：對指令和數(shù)據(jù)分別用不同的cache

總結(jié)

[外鏈圖片轉(zhuǎn)存中…(img-5w3yeJG8-1656554789635)]

總結(jié)

以上是生活随笔為你收集整理的计算机组织与结构【9 高速缓冲存储器（Cache）】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。