目錄
- 1. 什么是快取
- 2. 快取的定義
- 3. 計算機中的高速快取
- 3.1 高速快取相關名詞
- 3.2 計算機中的高速快取存盤器模型
- 3.3 計算機中有哪些快取
- 3.4 硬體讀取高速快取的程序
- 4. 直接映射高速快取
- 4.1 組選擇
- 4.2 行匹配
- 4.3 字選擇
- 4.4 模擬直接映射快取
- 4.5 直接映射高速快取的缺陷
- 5. 兩路相聯高速快取
- 5.1 組選擇
- 5.2 行匹配
- 5.3 字選擇
- 5.4 模擬兩路相聯高速快取
- 6. 全相聯高速快取
- 7. 真實計算機系統中的快取
- 8. 快取的評價指標
- 8.1 不命中率
- 8.2 命中率
- 8.3 命中時間
- 8.4 未命中懲罰
- 9. 總結
1. 什么是快取
??快取又叫高速快取，是計算機存盤器中的一種，本質上和硬碟是一樣的，都是用來存盤資料和指令的 ，它們最大的區別在于讀取速度的不同，程式一般是放在記憶體中的，當CPU執行程式的時候，執行完一條指令需要從記憶體中讀取下一條指令，讀取記憶體中的指令要花費100000個時鐘周期（快取讀取速度為200個時鐘周期，相差500倍），如果每次都從記憶體中取指令，CPU運行時將花費大量的時間在讀取指令上，這顯然是一種資源浪費，
??如何解決這個問題呢？有人肯定會問，直接把程式存盤在快取中不行嗎？
??答案是可以的，但是，快取的造價太貴了，具體如下圖所示，以2015年的售價為例，1GB SRAM的價格大約為327680美元，而1GB 普通硬碟的價格僅僅為0.03美元，用快取來存盤程式成本太高了，得不償失，
??于是，有人就提出了這樣一種方法，在CPU和記憶體之間添加一個高速記憶體， 這個高速記憶體容量小，只用來存盤CPU執行時常用的指令，既保證了硬體成本，又提高了CPU的訪問速度，這個高速記憶體就是快取（高速快取），
2. 快取的定義
??高速快取是一個小而快速的存盤設備 ，它作為存盤在更大更慢的設 備中的資料物件的緩沖區域，使用高速快取的程序稱為快取 ，
??具體如下圖所示，主存可以作為一個存盤設備，L3是主存的緩沖區域，從L3存取資料的程序就叫做快取，
3. 計算機中的高速快取
3.1 高速快取相關名詞
??如下圖所示，資料總是以塊為單位 在高速快取和主存之間來回復制，
??如果我們的程式請求一個資料字，這個資料字存盤在編號為10的塊中，將分以下幾種情況考慮：
??1. 高速快取行中為空，這叫做冷不命中 ，
??2.高速快取中有資料塊，但沒有資料塊10，這叫做快取不命中 ，接下來快取請求主存將該塊復制到高速快取，高速快取接收到之后將替換一個現有的資料塊，從而存盤新的資料塊在高速快取中，最后，高速快取將資料塊10回傳給CPU，
??3. 高速快取中有資料，將記憶體中的資料塊放置到高速快取中時，發生了沖突，這叫做沖突不命中 ，
放置策略中最常用的是：第k+1層的塊i必須放在第k層的塊（i mod 4）中，比如，第k+1層的0,4,8,12會映射到第k層的塊0，塊1,5,9,13會映射到塊1，
??4. 快取中有資料塊10，則直接回傳給CPU，這叫做快取命中 ，
3.2 計算機中的高速快取存盤器模型
??高速快取完全由硬體管理，硬體邏輯必須要知道，如何查找快取中的塊，并確定是否包含特定塊，因此，必須以非常嚴格且簡單的方式去構建高速快取，在計算機中，高速快取模型如下圖所示，
??我們可以將高速快取存盤器視為有\(S = {2^s}\)個高速快取組的陣列 ，每個組包含\(E = {2^e}\)個高速快取行 ，每個行是由一個\(B = {2^b}\)位元組的資料塊組成的，
??一般而言，高速快取的結構可以用元組（S,E,B,m）來描述，高速快取的大小（或容量）C指的是所有塊的大小的和，標記位和有效位不包括在內 ，因此，C=S×E×B，
??每個高速快取存盤器有m位，可以組成\(M = {2^m}\)個不同的地址，\(m = t + s + b\)，每個資料塊由以下三部分構成，
??有效位：有效位為t位，t一般為1，指明這個行是否包含有效資訊，
??標記位：標記位為s位，唯一的標識了存盤在高速快取中的塊（陣列索引），
??塊偏移：資料塊為\(B = {2^b}\)位元組，指明CPU請求的內容在資料塊中的偏移，
??下面對以上內容出現的引數做個總結：
| 引數 | 描述 |
|---|---|
| \(S = {2^s}\) | 組數 |
| \(E\) | 每個組的行數 |
| \(B = {2^b}\) | 塊大小（位元組） |
| \(m = {\log _2}(M)\) | 物理地址位數 |
| \(M = {2^m}\) | 記憶體地址的最大數量 |
| \(s = {\log _2}(S)\) | 組索引位數量 |
| \(b = {\log _2}(B)\) | 塊偏移位數量 |
| \(t = m - (s + b)\) | 標記位數量 |
| \(C = B \times E \times S\) | 不包括像有效位和標記位這樣開銷的高速快取大小（位元組） |
3.3 計算機中有哪些快取
?下表為現代計算機中用到的各種快取，
| 型別 | 快取什么 | 被快取在何處 | 延遲（周期數） | 由誰管理 |
|---|---|---|---|---|
| CPU暫存器 | 4位元組或8位元組 | 芯片上的CPU暫存器 | 0 | 編譯器 |
| TLB | 地址翻譯 | 芯片上的TLB | 0 | 硬體MMU |
| L1高速快取 | 64位元組塊 | 芯片上的L1高速快取 | 4 | 硬體 |
| L2高速快取 | 64位元組塊 | 芯片上的L2高速快取 | 10 | 硬體 |
| L3高速快取 | 64位元組塊 | 芯片上的L3高速快取 | 50 | 硬體 |
| 虛擬記憶體 | 4KB頁 | 主存 | 200 | 硬體 |
| 緩沖區快取 | 部分檔案 | 主存 | 200 | OS |
| 磁盤快取 | 磁盤扇區 | 磁盤控制器 | 100000 | 控制器韌體 |
| 網路快取 | 部分檔案 | 本地磁盤 | 10000000 | NFS客戶 |
| 瀏覽器快取 | Web頁 | 本地磁盤 | 10000000 | Web瀏覽器 |
| Web快取 | Web頁 | 遠程服務器磁盤 | 1000000000 | Web代理服務器 |
3.4 硬體讀取高速快取的程序
??當一條加載指令指示CPU從主存地址A中讀取一個字w時，會將該主存地址A發送到高速快取中，則高速快取會根據以下步驟判斷地址A是否命中：
??組選擇：根據地址劃分，將中間的s位表示為無符號數作為組的索引 ，可得到該地址對應的組，
??行匹配：根據地址劃分，可得到t位的標志位，由于組內的任意一行都可以包含任意映射到該組的資料塊，所以就要線性搜索組中的每一行，判斷是否有和標志位匹配且設定了有效位的行 ，如果存在，則快取命中，否則緩沖不命中，
??字抽取：如果找到了對應的高速快取行，則可以將b位表示為無符號數作為塊偏移量 ，得到對應位置的字，
??當高速快取命中時，會很快抽取出字w，并將其回傳給CPU，如果快取不命中，CPU會進行等待，高速快取會向主存請求包含字w的資料塊，當請求的塊從主存到達時，高速快取會將這個塊保存到它的一個高速快取行中，然后從被存盤的塊中抽取出字w，將其回傳給CPU，
4. 直接映射高速快取
??上面我們介紹了計算機中的高速快取模型，我們可以根據每個組的高速快取行數E，將高速快取分成不同的型別，下面我們看下直接映射高速快取（E=1）的具體例子，
4.1 組選擇
??組選擇示意圖如下所示，假設有 S 組，每組由一行組成，快取塊為8位元組，CPU發出地址要取資料字，高速快取將該地址分解為三部分，對于圖中的地址來說，塊偏移量為4，組索引是 1 ，粉紅色的為t位標記位， 因此，高速快取提取的組索引為 1，即圖中第二行，
4.2 行匹配
??然后，檢查地址中的標記位與快取行中的標記位是否匹配，如果匹配，將進行下一步字選擇，如果不匹配，則表示未命中，在未命中時，高速快取必須從記憶體中重新取資料塊， 在行中覆寫此塊，
4.3 字選擇
??當標記位匹配時，表示命中，接著檢查地址中的塊偏移為4，即要從快取行資料塊的第5位開始取值，并回傳給CPU，
4.4 模擬直接映射快取
??下面，我們模擬下直接映射高速快取的程序，以便加深理解高速快取是如何作業的，假設，記憶體地址為4位元組，S=4組，E=1行/組，B=2位元組/塊， 其結構圖如下所示，
??我們模擬CPU要從高速快取中讀取地址為0,1,7,8,0的資料，下面是具體的程序，
| 地址 | 二進制 | 是否命中 |
|---|---|---|
| 0 | [\({0000_2}\)]（t=0,s=00,b=0） | |
| 1 | [\({0001_2}\)]（t=0,s=00,b=1） | |
| 7 | [\({0111_2}\)]（t=0,s=11,b=1） | |
| 8 | [\({1000_2}\)]（t=1,s=00,b=0） | |
| 0 | [\({0000_2}\)]（t=00,s=0,b=0） |
??1. 讀地址0的資料，標記位為0，索引位為00，偏移位為0，塊號為0，快取行中沒有資料，組0的有效位為0，地址的標記位和組0的標記位不匹配，因此，未命中，然后，高速快取從記憶體中取出塊0，塊1， 共2位元組，并存盤在組0中，具體如下圖所示，
??2. 讀地址1的資料，標記位為0，索引位為00，偏移位為1，塊號1， 快取行中已有資料資料，組0的有效位為1，地址1的標記位和組0的標記位匹配，因此，命中，具體如下圖所示，
??3. 讀地址7的資料，標記位為0，索引位為11（3），偏移位為1，塊號為3， 快取行中有資料，組3的有效位為0，地址的標記位和組0的標記位不匹配，因此，未命中，然后，高速快取從記憶體中取出塊6，塊7， 共2位元組，并存盤在組3中，具體如下圖所示，
?? 4. 讀地址8的資料，標記位為1，索引位為00，偏移位為0，塊號為4， 快取行中有資料，組0的有效位為1，地址的標記位和組0的標記位不匹配，因此，未命中，然后，高速快取從記憶體中取出塊8，塊9， 共2位元組，并存盤在組0中，具體如下圖所示，
?? 5. 讀地址0的資料，標記位為0，索引位為00，偏移位為0，塊號為0，快取行中有資料，組0的有效位為1，地址的標記位和組0的標記位不匹配，因此，未命中，然后，高速快取從記憶體中取出塊0，塊1， 共2位元組，并存盤在組0中，具體如下圖所示，
??最終結果如下：快取命中率為20%，
| 地址 | 二進制 | 是否命中 |
|---|---|---|
| 0 | [\({0000_2}\)]（t=0,s=00,b=0） | 否 |
| 1 | [\({0001_2}\)]（t=0,s=00,b=1） | 是 |
| 7 | [\({0111_2}\)]（t=0,s=11,b=1） | 否 |
| 8 | [\({1000_2}\)]（t=1,s=00,b=0） | 否 |
| 0 | [\({0000_2}\)]（t=00,s=0,b=0） | 否 |
注意：塊大小為2位元組，所以從記憶體中取資料總是以偶數倍開始的，所以會看到M[8-9],而不是M[7-8]，
??如果你看懂了上述高速快取的整個程序，考慮下如何編程來模擬高速快取呢？ 后面的文章我會詳細講解如何用C語言模擬高速快取，歡迎關注我的公眾號【嵌入式與Linux那些事】，第一時間獲取更新，
4.5 直接映射高速快取的缺陷
??觀察以上程序其實可以發現，在第5步，讀地址0的資料的時候，我們又得重新從記憶體中取資料到快取行中， 在讀地址8的資料的時候，M[8-9]替換了快取行中的M[0-1]，
??最主要的原因是每一個組中只允許存放一行快取， 假設，E = 2，每組中有2個快取行，M[8-9]和M[0-1]就有很大可能同時存在于組0中，我們在第5步訪問時，就不需要重新從記憶體中取資料了，因此，就有了E = 2的兩路相聯高速快取，
5. 兩路相聯高速快取
??直接映射高速快取中沖突不命中造成的問題源于每個組只有一行這個限制，組相聯高速存放松了這條限制，所以每個組都保存有多于一個的高速快取行，如下圖所示為兩路相聯的高速快取，
5.1 組選擇
??它的組選擇與直接映射高速快取的組選擇一樣，組索引位標識組，具體如下圖所示，這里不再贅述，
5.2 行匹配
??組相聯高速快取中的行匹配比直接映射高速快取中的更復雜，因為它必須每次檢查多個行 的標記位和有效位，以確定所請求的字是否在集合中，具體如下圖所示，
5.3 字選擇
??字選擇的程序和直接映射高速快取中的方式一樣，這里就不再贅述，
5.4 模擬兩路相聯高速快取
??下面，我們模擬下兩路相聯高速快取的程序，以便加深理解高速快取是如何作業的，假設，記憶體地址為4位元組，S=2組，E=2行/組，B=2位元組/塊，其結構圖如下所示，
??我們模擬CPU要從高速快取中讀取地址為0,1,7,8,0的資料，下面是具體的程序，
| 地址 | 二進制 | 是否命中 |
|---|---|---|
| 0 | [\({0000_2}\)] （t=00,s=0,b=0） | |
| 1 | [\({0001_2}\)]（t=00,s=0,b=1） | |
| 7 | [\({0111_2}\)]（t=01,s=1,b=1） | |
| 8 | [\({1000_2}\)]（t=10,s=0,b=0） | |
| 0 | [\({0000_2}\)]（t=00,s=0,b=0） |
??1. 讀地址0的資料，標記位為00，索引位為0，偏移位為0，塊號為0，快取行中沒有資料，組0的有效位為0，地址的標記位和組0的第一行和第二行的標記位都不匹配，因此，未命中，然后，高速快取從記憶體中取出塊0，塊1， 共2位元組，并存盤在組0第一行中，具體如下圖所示，
??2. 讀地址1的資料，標記位為00，索引位為0，偏移位為1，塊號為1，快取行中已有資料資料，組0的第一行有效位為1，地址1的標記位和組0的第一行標記位匹配，因此，命中，具體如下圖所示，
??3. 讀地址7的資料，標記位為01，索引位為1，偏移位為1，塊號為1，快取行中有資料，組1的有效位為0，地址的標記位和組1中的第一行和第二行的標記位不匹配，因此，未命中，然后，高速快取從記憶體中取出塊6，塊7， 共2位元組，并存盤在組1中，具體如下圖所示，
?? 4. 讀地址8的資料，標記位為10，索引位為0，偏移位為0，塊號為0，快取行中有資料，組0的第一行有效位為1，第二行有效位為0，地址的標記位和組0的第一行和第二行的標記位不匹配，因此，未命中，然后，高速快取從記憶體中取出塊8，塊9， 共2位元組，并存盤在組0的第二行中，具體如下圖所示，
?? 5. 讀地址0的資料，標記位為00，索引位為0，偏移位為0，塊號為0，快取行中有資料，組0的第一行有效位為1，地址的標記位和組0的第一行的標記位匹配，因此，命中，具體如下圖所示，
| 地址 | 二進制 | 是否命中 |
|---|---|---|
| 0 | [\({0000_2}\)] （t=00,s=0,b=0） | 否 |
| 1 | [\({0001_2}\)]（t=00,s=0,b=1） | 是 |
| 7 | [\({0111_2}\)]（t=01,s=1,b=1） | 否 |
| 8 | [\({1000_2}\)]（t=10,s=0,b=0） | 否 |
| 0 | [\({0000_2}\)]（t=00,s=0,b=0） | 是 |
??兩路相聯高速快取與直接映射高速快取相比，在每組中增加了一行，快取命中率提升了15%，避免了快取頻繁從記憶體中存取資料的情況，提高了程式運行速度，
6. 全相聯高速快取
??全相聯高速快取中的行匹配和字選擇與組相聯高速快取中的是一樣的，程序就不再贅述，其結構圖如下所示，
相聯度越高越好嗎？
答案是否定的，較高的相聯度會造成較高的成本，實作難度大，價格昂貴，而且很難使之速度變快，較高的相聯度會增加命中時間，因為復雜性增加了，另外，還會增加不命中處罰，因為選擇犧牲行的復雜性也增加了，
相聯度的選擇最終變成了命中時間和不命中處罰之問的折中，一般來講，高性能系統會為L1高速快取選擇較低的相聯度（這里的不命中處罰只是幾個周期），而在不命中處罰比較高的較低層上使用比較小的相聯度，例如， Intel Core i7系統中，L和L2高速快取是8路組相聯的，而L3高速快取是16路組相聯的，
7. 真實計算機系統中的快取
??在此之前，我們一直假設高速快取只保存資料，不過，實際上，高速快取既保存資料，也保存指令，只保存指令的高速快取稱為 i-cache ，只保存程式資料的高速快取稱為 d-cache ，既保存指令又包括資料的高速快取稱為 統一的高速快取 ，
??如下圖所示為 Intel Core i7處理器的高速快取層次結構，每個CPU芯片有四個核，每個核有自己的L1 i-cache， L1 d-cache和L2統一的高速快取，所有的核共享片上L3統一的高速快取，其具體引數如下表所示，
| 快取 | 大小 | 內部結構 | 訪問時間 |
|---|---|---|---|
| L1 | 32KB | 8路相聯 | 4時鐘 |
| L2 | 256KB | 8路相聯 | 10時鐘 |
| L3 | 8M | 16路相聯 | 40-75時鐘 |
8. 快取的評價指標
??最后介紹下衡量高速快取性能的一些指標：
8.1 不命中率
??在一個程式執行或程式的一部分執行期間，記憶體參考不命中的比率，它等于： 不命中數量/參考數量，
8.2 命中率
??命中的記憶體參考比率，它等于：
8.3 命中時間
??從高速快取傳送一個字到CPU所需的時間，包括組選擇、行確認和字選擇的時間，一般來講，L1快取的命中時間為：4個時鐘，L2快取的命中時間為：10個時鐘，
8.4 未命中懲罰
??未命中需要的額外時間，對于主存來說，一般為 50 ~ 200個時鐘周期，
舉個例子：
假設快取命中時間為1個時鐘周期，快取未命中懲罰為100個時鐘周期，
下面計算下97%快取命中率和99%的快取命中率的平均訪問時間為多少？計算公式為命中時間加上未命中處罰乘以百分系數，
97%的命中率：\(1 + 0.03 \times 100 = 4\)時鐘，
99%的命中率：\(1 + 0.01 \times 100 = 2\)時鐘，
結論：命中率增加2%，平均訪問時間減少了50%，
9. 總結
??計算機中存在著各種各樣的快取，比如， 檔案快取 把一些需要高速存取的變數快取在記憶體中，每次訪問直接讀出即可， 瀏覽器快取 根據一套與服務器約定的規則進行作業，如果在瀏覽程序中前進或后退時訪問到同一個圖片，這些圖片可以從瀏覽器快取中調出而即時顯示，資料庫快取 經常需要從資料庫查詢的資料、或經常更新的資料放入到快取中，這樣下次查詢時，直接從快取直接回傳，減輕資料庫壓力，
??我們了解這么多基本概念有什么用呢？如果我們理解了計算機系統是如何將資料在記憶體中組織和移動的，那么在寫程式時就可以把資料項存盤在合適的位置，CPU能更快地訪問到它們，提高程式的執行效率，
??下一篇文章我們將介紹如何寫出高效的代碼，讓程式運行的更快！ 歡迎關注我的公眾號，第一時間獲取更新！
??養成習慣，先贊后看！如果覺得寫的不錯，歡迎關注，點贊，在看，轉發，謝謝！
有任何問題，均可通過公告中的二維碼聯系我
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/247026.html
標籤：嵌入式