【深入理解電腦系統CSAPP】第六章 存儲器層次結構

6 存儲器層次結構

存儲器系統(memory system)是一個具有不同容量、成本和訪問時間的存儲設備的層次結構。CPU 暫存器保存著最常用的數據。靠近 CPU 的小的、快速的高速快取存儲器(cache memory)作為一部分存儲在相對慢速的主存儲器(main memory)中的數據和指令的緩衝區域。主存暫時存放在容量較大的、慢速磁碟上的數據，而這些磁碟常常又作為存儲在通過網路連接的其他機器的磁碟或磁帶上的區域的緩衝區域。

具有良好局部性的程式傾向於一次又一次地訪問相同的數據項集合，或者是傾向於訪問鄰近的數據項集合。

多個具有不同容量、成本和訪問時間的存儲設備構成了存儲器層次結構，稱為存儲器系統。

執行指令時訪問數據所需的周期數：

  1. CPU暫存器：0個周期
  2. L1L3高速快取：475個周期
  3. 主存：上百個周期
  4. 磁碟：幾千萬個周期

6.1 存儲技術

幾種基本的存儲技術

  1. 隨機訪問存儲器，分為兩類：

    1. RAM，同時也是易失性存儲器，也分為兩類：

      1. SRAM：靜態隨機訪問存儲器，速度快，價格高。多用來作為高速快取存儲器。
      2. DRAM：動態隨機訪問存儲器，速度慢，價格低。多用來作為主存和圖形系統的幀緩衝器

    3. ROM，同時也是非易失性存儲器。快閃記憶體屬於 ROM，固態硬碟就是基於快閃記憶體開發而來。

  3. 機械硬碟

  4. 固態硬碟（SSD）

6.1.1 隨機訪問存儲器

隨機訪問存儲器 (Random-Access Memory, RAM)分為兩類：靜態的和動態的。SRAM 比 DRAM 更快，但也貴得多。SRAM 用來作為高速快取存儲器，既可以在 CPU 晶片上，也可以在片下。DRAM 用來作為主存以及圖形系統的幀緩衝區。

1、SRAM

SRAM 將每個位存儲在一個雙穩態的存儲器單元內。每個單元由六個電晶體組成。

雙穩態即該電路無限期地穩定保持在兩個不同的電壓狀態。

對於 SRAM，只要有電，就永遠地保持它的值。即使有干擾，當干擾消除，電路也會恢復到穩定值。

2、DRAM

DRAM 將每個位存儲為對一個電容的充電。每個 DRAM 單元由一個電容和一個訪問電晶體組成。

DRAM 對干擾非常敏感。當電容的電壓被擾亂後，就永遠不會恢復了。

3、SRAM和DRAM的區別

只要有電源，SRAM是持續的。與DRAM不同，不需要刷新。SRAM的存取比DRAM快。SRAM對諸如光和電雜訊之類的干擾不敏感。其代價是SRAM電池比DRAM電池使用更多的電晶體，因此密度更低，價格更貴，消耗更多電力。

image-20220506160959027

4、傳統的 DRAM

DRAM 晶片被分為 d 個超單元，每個超單元包含 w 個 DRAM 單元，w 一般為 8。當從 DRAM 中讀取數據時，一次可以讀取一個超單元的數據（可以近似的將超單元理解為一個位元組）。

DRAM 中的超單元按行列組織，DRAM 中還包含一個行緩衝區。

記憶體控制器 依次將行地址和列地址發送給 DRAM，DRAM 將對應的超單元的內容發回給記憶體控制器以實現讀取數據。

行地址和列地址共享相同的 DRAM 晶片地址引腳。

image-20220506162802433

從 DRAM 中讀取超單元的步驟：

  1. 記憶體控制器發來行地址 i，DRAM 將整個第 i 行複製到內部的行緩衝區。
  2. 記憶體控制器發來列地址 i，DRAM 從行緩衝區中複製出超單元 (i,j) 並發送給記憶體控制器。

image-20220506162915189

5、記憶體模組

許多 DRAM 晶片封裝在記憶體模組中，插到主板的擴展槽上。

常用的是雙列直插記憶體模組 (DIMM)，以 64 位為塊與記憶體控制器交換數據。

比如一個記憶體模組包含 8 個 DRAM 晶片，每個 DRAM 包含 8M 個超單元，每個超單元存儲一個位元組（8bit）。使用 8 個 DRAM 晶片上相同地址處的超單元來表示一個 64 位字，DRAM 0 存儲第一個位元組，DRAM 1 存儲第 2 個位元組，依此類推。

要取出記憶體地址 A 處的一個字，記憶體控制器先將 A 轉換為一個超單元地址 (i,j)，然後記憶體模組將 i,j 廣播到每個 DRAM。作為響應，每個 DRAM 輸出它的 (i,j) 超單元的 8 位內容，合併成一個 64 位字，再返回給記憶體控制器。

主存由多個記憶體模組連接到記憶體控制器聚合成。

image-20220506165420823

image-20220506165359774

6、增強的 DRAM

有一些經過優化的 DRAM：

  1. 快頁模式 DRAM (FPM DRAM)：當連續訪問位於同一行的超單元時，第二次以後，FPM DRAM 可以直接從行緩衝區獲取數據。
  2. 擴展數據輸出 DRAM (EDO DRAM)：FPM DRAM 的一個增強的形式，更快一些。
  3. 同步 DRAM (SDRAM)：常規的、FPM 和 EDO 都是非同步的。從效果而言，SDRAM 可以比非同步存儲器更快地輸出它的超單元的內容。
  4. 雙倍數據速率同步 DRAM(DDR SDRAM)：對 SDRAM 的一種增強，使速度翻倍。不同的 DDR SDRAM 以提高有效頻寬的很小的預留緩衝區的大小來劃分：DDR(2位)、DDR2(4位)、DDR3(8位)。位越多速度越快，近乎翻倍。
  5. 影片 RAM (VRAM)：用在圖形系統的幀緩衝區中，其思想與 FPM DRAM 類似。VRAM 允許對記憶體進行並行地讀和寫。因此系統可以在寫下一次更新的新值時（寫），用幀緩衝區的像素刷螢幕（讀）。

現在電腦使用的大多數都是 DDR3 SDRAM。

7、非易失性存儲器

DRAM 和 SRAM 會在斷電後丟失資訊，因此是易失性存儲器。ROM 是非易失性存儲器，在斷電後仍保存著資訊。

ROM 是只讀存儲器，但是實際上有些 ROM 既可以讀也可以寫。

幾種常見的非易失性存儲器：

  1. 可編程 ROM (PROM)：只能被編程一次。
  2. 可擦寫可編程 ROM (EPROM)：可以被擦除和重編程上千次。
  3. 電子可擦除 PROM (EEPROM)：類似於 EPROM，但是可以被重編程十萬次。
  4. 快閃記憶體：基於 EEPROM 的一種存儲技術。快閃記憶體無處不在，固態硬碟就是一種基於快閃記憶體的磁碟驅動器。

存儲在 ROM 設備中的程式通常稱為韌體，當電腦系統通電後，會運行存儲在 ROM 中的韌體。

8、訪問主存

數據流通過匯流排在處理器與主存間來往，每次處理器和主存間的數據傳送的一系列步驟稱為匯流排事務。

匯流排是一組並行的導線，能攜帶地址、數據和控制訊號。

系統匯流排連接 CPU 和 IO 橋接器，記憶體匯流排連接 IO 橋接器和主存。IO 橋同時也連接著 I/O 匯流排。

image-20220508111246708

讀事務的三個步驟：

  1. CPU 將地址 A 放到記憶體匯流排上。
  2. 主存從匯流排讀出 A，取出字 x，然後將 x 放到匯流排上。
  3. CPU 從匯流排讀出字 x，並將它複製到相應暫存器中。

image-20220508111126882

寫事務的三個步驟：

  1. CPU 將地址 A 放到記憶體匯流排。主存讀出這個地址，並等待數據字。
  2. CPU 將數據字 y 放到匯流排上。
  3. 主存從匯流排讀數據字 y，並將它存儲在地址 A。

image-20220508111145429

6.1.2 磁碟存儲

1、磁碟構造

image-20220508162615557

磁碟由碟片組成，每個碟片有兩個表面（上面和下面），表面上覆蓋著磁性記錄材料。一個磁碟包含一個或多個碟片。

每個表面由一系列同心圓（稱為磁軌）組成，每個磁軌被劃分為一組扇區，每個扇區包含相同的數據位（一般為512位元組）。扇區之間由間隙分隔開，間隙中不存儲數據位，而存儲用來標識扇區的格式化位。如下圖a。

//note.youdao.com/yws/public/resource/1cbaebb119458e1d6043099a42e3db7c/xmlnote/F94A1AD8503F4306A32BD130A6F02A47/40196

名詞柱面用來表示距離主軸相等的磁軌的集合。比如一個磁碟有 3 個碟片，那麼每個柱面就有 6 個磁軌。如上圖b。

2、磁碟容量

磁碟容量：一個磁碟能夠存儲的最大位數，由以下因素決定：

  1. 記錄密度：單獨決定一個扇區可以存儲多少bit(或者至少是磁軌的一部分)
  2. 磁軌密度：相鄰的磁軌可以放置得多臨近。
  3. 面密度：記錄密度與磁軌密度的乘積。決定了整個磁碟的存儲容量。

磁碟容量公式：

​ 0

磁碟容量=每個扇區的位元組數 * 每個磁軌上的平均扇區數 * 每個盤面的平均磁軌數 * 一個碟片的盤面數 * 磁碟中碟片的數量

例如，假設我們有一個帶有5個磁碟的磁碟，每個扇區512位元組，每個表面20,000個磁軌，每個磁軌平均300個扇區。則磁碟的容量為：

image-20220508193842524

注意，製造商表示磁碟容量的單位是GB (GB)或TB (TB)，其中1GB = 10^9位元組，1tb = 10^12位元組。

DRAM 和 SRAM 相關的單位中 K = 2^10，磁碟、網路、速率、吞吐量相關的單位中 K=10^3。

註：磁碟格式化會填寫間隙、標識出有故障的柱面、在每個區中預留出一組柱面作為備用。所以格式化容量要比最大容量小。

3、磁碟操作

磁碟用讀寫頭來讀寫存儲在磁性表面的位。每個表面都有一個讀寫頭，任何時候所有的讀寫頭都位於同一個柱面上。

讀寫頭位於傳動壁的末端，讀寫頭的速度約為 80km/h，距磁碟表面約 1um，因此磁碟是很脆弱的，開機時不要挪動主機更不要拍主機。

磁碟讀寫數據時以扇區為單位，即一次讀寫一個扇區大小的塊。

image-20220508165434630

對扇區的訪問時間包括三部分：

尋道時間：為了讀取目標扇區的內容，傳動臂首先要將讀寫頭定位到包含目標扇區的磁軌上。

現代驅動器的平均尋道時間為 3~9 ms，最大為 20 ms。（機械原理）

這個時間除跨越n條磁軌的時間外，還包括啟動磁臂的時間s，即
$$
Tseek=m*n+s上式中，m是與磁碟驅動器速度有關的常數，約為0.2ms，磁臂的啟動時間s：約為2ms。
$$
旋轉時間：讀寫頭定位到期望的磁軌後，要等待目標扇區的第一個位旋轉到讀寫頭下。

  1. 旋轉時間依賴於磁碟的旋轉速度和讀寫頭到達目標磁軌時的位置。
  2. 最大旋轉時間是旋轉速度的倒數，平均旋轉時間是最大旋轉時間的一半。

碟片以固定速率旋轉，通常為 5400~15000，單位是轉每分鐘 (RPM)。

設磁碟的旋轉速度為RPM，則最大旋轉時間(以秒為單位)，為：
$$
Tmr=(1/RPM)(60secs/1min)
$$
平均旋轉延遲，Tavg旋轉時間，只是Tmax旋轉時間的一半。一般的旋轉時間是指的平均旋轉時間：
$$
Tar=(1/RPM)(60secs/1min)/2
$$
可以簡化為王道書上的，其中r為磁碟每秒的轉數
$$
Tr=1/2r
$$
對於硬碟，典型的旋轉速度為5400 轉/分，相當於一周11.1ms， 則Tr為5.55ms;

Tr=(1/5400)*60/2=11.1ms/2=5.55ms

對於軟盤，其旋轉速度為300600轉/分，則T為50100ms。

傳送時間：平均傳送時間是讀寫頭讀寫完整個扇區的時間。一個扇區的傳輸時間取決於轉速和每個軌道扇區的數量。

image-20220508190843012

王道書上：

傳送時間取決於磁碟的旋轉速度和每次讀寫的位元組數b。N為一個磁軌上的位元組數

image-20220508192217270

旋轉時間一般和尋道時間差不多，而傳送時間相對可以忽略不計，因此從磁碟讀取一個扇區的時間約為 10 ms。

例題：

image-20220508192719856

例題：

image-20220508200538620

4、邏輯磁碟塊

現代磁碟呈現為一個邏輯塊的序列，每個邏輯塊是扇區大小的整數倍，最簡單的情況下，邏輯塊的大小為一個扇區，即 512 位元組。塊從0開始編號，塊號是一系列增長的數字。

磁碟控制器保持物理扇區和邏輯塊之間的映射。當作業系統讀寫磁碟時，發送一個邏輯塊號到磁碟控制器，控制器上的韌體將邏輯塊號翻譯為一個（盤面、磁軌、扇區）的三元組。

5、連接 I/O 設備

系統匯流排與記憶體匯流排都是與 CPU 相關的，而 IO 匯流排與 CPU 無關。

Intel 的外部設備互連匯流排（PCI）就是一種 IO 匯流排（廣播匯流排）。

IO 匯流排速度相比於系統匯流排和記憶體匯流排慢，但是可以容納種類繁多的第三方 IO 設備。

連接到 IO 匯流排的三種設備：

  1. 通用串列匯流排（USB）：USB 匯流排是一個廣泛使用的標準，連接各種 IO 設備，包括鍵盤、滑鼠等。
  2. 顯示卡/顯示適配器：負責代表 CPU 在顯示器上畫像素。
  3. 主機匯流排適配器：連接磁碟。常總的磁碟介面是 SCSI 和 SATA。其中 SCSI 比 SATA 更快也更貴。

​ 0

6、訪問磁碟

CPU 使用記憶體映射 IO 技術來向 IO 設備發射命令。在使用記憶體映射 IO 的系統中，地址空間中有一塊地址是專為與 IO 設備通訊保留的，每個這樣的地址稱為一個 IO 埠。當一個設備連接到匯流排時，它與一個或多個埠相關聯。

假設磁碟控制器映射到埠 0xa0，讀一個磁碟扇區的步驟如下：

  1. CPU 依次發送命令字、邏輯塊號、目的記憶體地址到 0xa0，發起一個磁碟讀。因為磁碟讀的時間很長，所以此後 CPU 會轉去執行其他工作。

    image-20220508201953072

  2. 磁碟收到讀命令後，將邏輯塊號翻譯成一個扇區地址，讀取該扇區的內容，並將內容直接傳送到主存，不需要經過 CPU (這稱為直接記憶體訪問(DMA))。

    image-20220508202049560

  3. DMA 傳送完成後，即磁碟扇區的內容安全地存儲在主存中後，磁碟控制器給 CPU 發送一個中斷訊號來通知 CPU。

    image-20220508202109446

6.1.3 固態硬碟

固態硬碟 (SSD) 是一種基於快閃記憶體的存儲技術。

一個固態硬碟中封裝了一個快閃記憶體翻譯層和多個快閃記憶體晶片。快閃記憶體翻譯層是一個硬體/韌體設備，功能類似磁碟控制器，將對邏輯塊的請求翻譯成對底層物理設備的訪問。

一個快閃記憶體由 B 個塊的序列組成，每個塊由 P 頁組成，頁的大小為 512byte~4kb。數據以頁為單位進行讀寫。

enter description here

對於 SSD 來說，讀比寫快。因為只有在一頁所屬的塊整個被擦除後，才能寫這一頁。重複寫十萬次後，塊就會磨損，因此固態硬碟壽命較低。

image-20220508212736990

隨機寫 SSD 很慢的兩個原因：

  1. 擦除塊需要相對較長的時間。
  2. 如果寫操作試圖修改一個已經有數據的頁，那麼這個塊中所有帶有用數據的頁都必須複製到一個新的塊，然後才能向該頁寫數據。

SSD 相比於旋轉磁碟的優點：由半導體存儲器構成，沒有移動部件，所以更結實，隨機訪問也更快，能耗更低。

缺點：更容易磨損，不過現在的 SSD 已經可以用很多年了。

基於快閃記憶體（flash memory）的存儲技術

6.1.4 存儲技術趨勢

性能上：SRAM > DRAM > SSD > 旋轉磁碟

發展速度上：增加密度(降低成本) > 降低訪問時間

DRAM 和 磁碟的性能滯後於 CPU 的性能提升速度，兩者之間的差距越來越大。

image-20220508213652205

6.2 局部性

局部性

實際上彌補CPU和記憶體之間差距的關鍵，是程式的局部性。

局部性是程式的一個基本屬性。具有良好局部性的程式傾向於重複地訪問相同的數據 (時間局部性)，或傾向於訪問鄰近的數據 (空間局部性)，因此運行更快。

局部性有兩種形式：時間局部性和空間局部性。

現代電腦系統的各個層次，從硬體到作業系統到應用程式都利用了局部性。

6.2.1 對程式數據引用的局部性

​ for(int i=0; i<N; ++i) sum += v[i];

上例中，sum 具有好的時間局部性，向量 v 具有好的空間局部性。

這裡對向量 v 中元素的訪問是順序訪問的，稱為步長為 1 的引用模式。在空間局部性上，步長為 1 的引用模式是最好的。

6.2.2 取指令的局部性

程式指令存放在記憶體中，CPU 需要讀這些指令，因此取指令也有局部性。比如 for 循環中的指令具有好的時間局部性和空間局部性。

6.2.3 局部性小結

評價局部性的簡單原則：

  1. 重複引用相同變數的程式有好的時間局部性。
  2. 對於步長為 k 的引用模式的程式，k 越小，空間局部性越好。
  3. 對於取指令來說，循環有好的時間和空間局部性。循環體越小，循環迭代次數越多，局部性越好。

6.3 存儲器層次結構

//note.youdao.com/yws/public/resource/1cbaebb119458e1d6043099a42e3db7c/xmlnote/50EB11D7A28F4BAA9E08302865BDE592/50927

6.3.1 在存儲器層次結構中的快取

一般而言，高速快取(cache)是一個小而快速的存儲設備。使用高速快取的過程稱為快取(caching)。

存儲器層次結構的中心思想：對於每個 k，位於 k 層的更快更小的存儲設備作為位於 k+1 層的更大更慢的存儲設備的快取。換句話說，層次結構中的每一次都快取來自較低一層的數據對象。

快取的具體實現：數據總是以塊大小為傳送單元(transfer unit)在第 k 層和第 k+1 層之間來回拷貝的。雖然在層次結構中任何一對相鄰的層次之間塊大小是固定的，但是其他的層次對之間可以用不同的塊大小。

一般而言，層次結構較低的層(離 CPU 較遠)的設備訪問時間較長，因此為了補償這些較長的訪問時間，傾向於使用較大的塊。

enter description here

1、快取命中

當需要 k+1 層的某個數據對象 d 時，如果 d 恰好快取在 k 層中，就稱為快取命中。

2、快取不命中

快取不命中時，第 k 層的快取從 第 k+1 層快取中取出包含 d 的塊。

如果第 k 層快取已經滿了，需要根據替換策略選擇一個塊進行覆蓋 (替換)，未滿的話需要根據放置策略來選擇一個塊放置。

3、快取不命中的種類

  1. 冷不命中：一個空的快取稱為冷快取，冷快取必然不命中，稱為冷不命中。
  2. 衝突不命中：常用的放置策略是將 k+1 層的某個塊限制放置在 k 層塊的一個小的子集中。比如 k+1 層的塊 1,5,9,13 映射到 k 層的塊 0。這會帶來衝突不命中。
  3. 容量不命中：當訪問的工作集的大小超過快取的大小時，會發生容量不命中。即快取太小了，不能快取整個工作集。

4、快取管理

暫存器文件的快取由編譯器管理，L1,L2,L3 的快取由內置在快取中的硬體邏輯管理，DRAM 主存作為快取由作業系統和 CPU 上的地址翻譯硬體共同管理。

6.3.2 存儲器層次結構概念小結

存儲器層次結構行之有效，因為較慢的設備比較快的設備更便宜，還因為程式偏向於展示局部性：

  • 利用時間局部性，同一數據對象可能會被多次使用
  • 利用空間局部性，塊通常包含有多個數據對象

enter description here

6.4 高速快取存儲器

L1 高速快取的訪問速度約為 4 個時鐘周期，L2 約 10 個周期，L3 約 50 個周期。

當 CPU 執行一條讀記憶體字 w 的指令，它首先向 L1 高速快取請求這個字，如果 L1 沒有就向 L2，依此而下。

6.4.1 通用的高速快取存儲結構

假設一個電腦系統中的存儲器地址有 m 位，形成 M =2^m 個不同的地址。m 個地址為劃分為 t 個標記位，s 個組索引位，b 個塊偏移位。

高速快取被組織成 S=2^s 個高速快取組，每個組包含 E 個高速快取行，每個行為一個數據塊，包含一個有效位，t=m-(b+s) 個標記位，和 B=2^b 位元組的數據塊。高速快取的容量 = S * E * B。

高速快取可以通過簡單地檢查地址位來找到所請求的字。

當 CPU 要從地址 A(由m個地址位組成) 處讀一個字時：

  1. A 中的 s 個組索引位告訴我們在哪個組中
  2. A 中的 t 個標記位告訴我們在這個組中的哪一行：當且僅當這一行設置了有效位並且標記位與 A 中的標記位匹配時，才說明這一行包含這個字。
  3. A 中的 b 個塊偏移位告訴我們在 B 個位元組的數據塊中的字偏移。

img

image-20220517115624247

image-20220517120310461

理解

使用高位做標記位，可以避免連續的塊被映射到同一高速快取組中。

通過高速快取從記憶體讀字

假設一個系統中只有 CPU、L1 高速快取和主存。

當 CPU 執行一條從記憶體讀字 w 的指令，如果 L1 有 w 的副本，就得到 L1 高速快取命中；如果 L1 沒有，就是快取不命中。

當快取不命中，L1 會向主存請求包含 w 的塊(L1 中的塊就是它的高速快取行)的一個副本。當塊從記憶體到達 L1，L1 將這個塊存在它的一個高速快取行里，然後從中抽取出字 w，並返回給 CPU。

高速快取確定一個請求是否命中，然後抽取出被請求的字的過程分為三步：

  1. 組選擇
  2. 行匹配
  3. 字抽取

高速快取有以下幾類：

  1. 直接映射高速快取：每個組只有一行，即 E=1。
  2. 組相聯高速快取：每個組有多行，1
  3. 全相聯高速快取：只有一個組，E=C/B。

6.4.2 直接映射高速快取

每個組只有一行（E=1）的高速快取被稱為直接映射高速快取

1、直接映射高速快取中的組選擇

​ 0

從 w 的 m 位地址中抽取出 s 個組索引位，並據此選擇相應的高速快取組。

2、直接映射高速快取中的行匹配

因為直接映射高速快取每個組只有一行，只要這一行設置了有效位且標記位相匹配，就說明想要的字的副本確實存儲在這一行中。

3、直接映射高速快取中的字抽取

從 w 的地址中抽取出 b 個塊偏移位，塊偏移位提供了所需的字的第一個位元組的偏移。

4、直接映射高速快取不命中時的行替換

快取不命中時需要從下一層取出被請求的塊，然後將其存儲在組索引位指示的組中的高速快取行中。

因為直接映射高速快取每個組只有一行，所以替換策略很簡單：用新取出的行替換當前行。

5、運行中的直接映射高速快取

標記位和索引位連接起來標識了整個記憶體中的所有塊，而高速快取中的高速快取組（塊）是少於記憶體中的塊數的。因此位於不同標記位，相同組索引位的塊會映射到高速快取中的同一個高速快取組。

在一個高速快取組中存儲了哪個塊，可以由標記位唯一地標識。

理解：對於主存中的整個地址空間，根據標記位不同將其分為了若干個部分，每個部分可以單獨且完整地映射到高速快取中，且剛好佔滿整個直接映射高速快取。

6、直接映射高速快取中的衝突不命中

衝突不命中在直接映射高速快取中很常見。因為每個組只有一行，不同標記位的塊會映射到同一行，發生衝突不命中。

6.4.3 組相聯高速快取

直接映射高速快取中衝突不命中造成的問題是源於每一個組只有一行，組相聯高速快取（set associative cache）放鬆了這條限制，所以每個組都保存了有多於一行的高速快取

1、組相聯高速快取中的組選擇

與直接映射高速快取一樣，組索引位標識組。

2、組相聯高速快取中的行匹配

組相聯高速快取中的行匹配更複雜，因為要檢查多個行的標記位和有效位，以確定其中是否有所請求的字。

注意：組中的任意一行都可能包含映射到這個組的記憶體塊，因此必須搜索組中的每一行，尋找一個有效且標記位相匹配的行。

3、組相聯高速快取中的字抽取

與直接映射高速快取一樣，塊偏移位標識所請求的字的第一個位元組。

4、組相聯高速快取中不命中時的行替換

幾種替換策略

  1. 隨機替換策略：隨機選擇要替換的行
  2. 最不常使用策略：替換在過去某個時間窗口內引用次數最少的一行。
  3. 最近最少使用策略：替換最後一次訪問時間最久遠的那一行。

因為存儲器層次結構中越靠下，不命中開銷越大，好的替換策略越重要。

enter description here

6.4.4 全相聯高速快取

全相聯高速快取由一個包含所有高速快取行 (E=C/B) 的組組成。

因為高速快取電路必須並行地搜索不同組已找到相匹配的標記，所以全相聯高速快取只適合做小的高速快取。

DRAM 主存採用了全相聯高速快取，但是因為它採用了虛擬記憶體系統，所以在進行類似行匹配的頁查找時不需要對一個個頁進行遍歷。

1、全相聯高速快取中的組選擇

全相聯高速快取中只有一個組，所以地址中沒有組索引位，只有標記位和塊偏移位。

2、全相聯高速快取中的行匹配和字抽取

與組相聯高速快取一樣。與組相聯高速快取的區別在於規模大小

enter description here

enter description here

enter description here

6.4.5 有關寫的問題

寫相比讀要複雜一些。

寫命中（寫一個已經快取了的字 w）的情況下，高速快取更新了本層的 w 的副本後，如何處理低一層的副本有兩種方法：

  1. 直寫：立即將 w 的高速快取塊寫回到低一層中。

    1. 優點：簡單
    2. 缺點：每次寫都會佔據匯流排流量

  3. 寫回：儘可能地推遲更新，只有當替換演算法要驅逐這個更新過的塊時，才把它寫到低一層中。

    1. 優點：利用了局部性，可以顯著地減少匯流排流量。
    2. 缺點：增加了複雜性。必須為每個高速快取行維護一個額外的修改位，表明此行是否被修改過。

寫不命中情況下的兩種方法：

  1. 寫分配：載入相應的低一層的塊到本層中，然後更新這個高速快取塊。

    1. 優點：利用寫的空間局部性
    2. 缺點：每次不命中都會導致一個塊從低一層傳送到高速快取

  3. 非寫分配：避開高速快取，直接把這個字寫到低一層中

直寫一般與非寫分配搭配，兩者都更適用於存儲器層次結構中的較高層。

寫回一般與寫分配搭配，兩者都更適用於存儲器層次結構中的較低層，因為較低層的傳送時間太長。

因為硬體上複雜電路的實現越來越容易，所以現在使用寫回和寫分配越來越多。

6.4.6 指令高速快取和統一高速快取

三種高速快取：

  1. i-cache：只保存指令的高速快取。i-cache 通常是只讀的，因此比較簡單。
  2. d-cache：只保存程式數據的高速快取。
  3. 統一的高速快取：既保存指令又保存程式數據。

現代處理器一般包括獨立的 i-cache 和 d-cache，其中兩個原因如下：

  1. 使用兩個獨立的高速快取，CPU 可以同時讀一個指令字和一個數據字。
  2. 可以確保數據訪問不會與指令訪問形成衝突不命中（不過可能會使容量不命中增加）。

Core i7 的高速快取層次結構及其特性

​ 0

​ 0

6.4.7 高速快取參數的性能影響

  1. 高速快取的性能指標

    1. 命中率：命中的記憶體引用比率。
    2. 命中時間：從高速快取傳送一個字到 CPU 的時間，包括組選擇、行確認和字抽取的實踐。
    3. 不命中處罰：不命中產生的額外時間消耗。

    幾個影響因素

    1. 高速快取大小：較大的高速快取可以提高命中率，但是會運行得更慢，即增加命中時間。
    2. 塊大小：較大的塊更能利用空間局部性以提高命中率。但是對於給定的總容量，塊越大高速快取行就越少，不利用利用時間局部性。較大的塊因為傳送時間更長，所以也會增加不命中處罰。現代處理系統的高速快取塊一般為 64 位元組。
    3. 相聯度：參數E的選擇的影響（每個組中高速快取行數）。E越高優點是：降低了高速快取由於衝突不命中出現抖動的可能性。缺點：實現起來昂貴；增加命中時間；增加不命中處罰。
    4. 寫策略：高速快取越往下層，越可能使用寫會而不是直寫策略。

6.5 編寫高速快取友好的程式碼

  1. 讓最常見的情況運行得快
  2. 在每個循環內部使快取不命中數量小

6.6 綜合：高速快取對程式性能的影響

存儲器山（memory mountain）
enter description here

6.7 小結

程式設計師可以通過編寫有良好空間和時間局部性的程式來顯著地改進程式的運行時間。利用基於 SRAM 的高速快取存儲器特別重要。

Tags:

VirMach 便宜 VPS

QNews

QNews