06. 容量大且速度快的記憶體

區域性原則 (Principle of Locality)

程式的執行在任何一個時間點只會存取一小部分的記憶體位址空間，又稱 locality of reference

• 時間區域性(temporal locality): 如果一個指令或資料被存取到，那麼它很快又會被存取到

  $^{ex.}$ 迴圈中的指令或資料

• 空間區域性(spatial locality): 如果一個指令或資料被存取到，那麼它位址附近的指令或資料也會很快被存取到

  $^{ex.}$ 循序執行的指令或陣列

$^{ex.}$ Write a C program which exhibits the temporal and spatial localities.

void clearArray(int array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        array[i] = 0;   // i: temporal locality; array: spatial locality
    }
}

不同的記憶體技術

$\because$ 記憶體容量 $\uparrow \Rightarrow$ 找尋存取位址的解碼時間 $\uparrow \therefore$ 記憶體速度 $\downarrow$，不過幸好有 locality of reference，因此可使用不同的大小與速度的記憶體組成階層式記憶體來達到容量大且速度快之需求，以下為三種主要的技術:

• 靜態隨機存取記憶體(Static Random Access Memory, SRAM)
• 動態隨機存取記憶體(Dynamic Random Access Memory, DRAM)

• 磁碟(Magnetic Disk)

記憶體階層 (Memory Hierarchy)

目的: 讓使用者能用最便宜的技術來擁有足夠的記憶體，且利用最快的記憶體來提供最快的存取速度

現行技術:

• Cache Memory: SRAM
• Main Memory: DRAM

區塊的命中與失誤

• 兩記憶體層次中最小的資料傳輸單位稱為區塊(block)或行(line)
• 命中(hit): CPU 可以在層次較近的記憶體中找到需要的資料

  比率: 命中率(hit rate/ratio)

• 失誤(miss): CPU 無法在層次較近的記憶體中找到需要的資料，需要至層次較遠的記憶體裡找尋包含此資料的區塊

  比率: 失誤率(miss rate) = 1 - hit rate

• 命中時間(hit time): CPU 用在判斷命中或失誤 + 從層次較近的記憶體存取資料的時間

  其中大部分時間花在資料存取上

• 失誤懲罰時間(miss penalty): CPU 從層次較遠的記憶體抓取失誤的區塊，載入層次較近的記憶體 + CPU 存取記憶體區塊裡的資料之時間

  其中大部分時間花在記憶體層次間的區塊抓取與載入上

$\rightarrow$ $\because$ 層次距離 CPU 較近的記憶體容量小且存取速度快 $\therefore$ 命中時間 << 失誤懲罰時間

• 命中率夠高:
  • CPU 存取資料的速度 = 層次距離 CPU 最近之記憶體的存取速度
  • 記憶體的儲存容量 = 層次距離 CPU 最遠之記憶體的儲存容量

直接對映快取記憶體 (Direct-mapped Cache Memory)

Main Memory 如果是 word addressing, offset = word(block) offset.

快取記憶體位元的計算

考試時給:

• Cache size(不包含 tag 欄位和 valid bit): ? bytes = (? / 4) words $\, \text{------} \, \spadesuit$
• block size: word(s) / block $\, \text{------} \, \clubsuit$
• address length: ?-bits

Steps:

• 求 block 總數: $\dfrac{\spadesuit}{\clubsuit} \, \text{------} \, \heartsuit$
• 切位址求 tag 欄位 bit 數 $\text{------} \, \diamondsuit$
• [$1$ + $\diamondsuit$ + ($\clubsuit$ in bits)] $\times \heartsuit$

  $1$: valid bit

區塊大小與快取失誤率

減少失誤懲罰時間之方法(CPU 皆無需等到距離層次較近的記憶體區塊的字組全部載入完才開始讀取):

• 儘早重新開始(early start): CPU 直到區塊中所需要的字組送到層次較近的記憶體裡時，才讀取該字組

  $^{ex.}$ 若直接對映快取記憶體之第一張圖裡 9 號 block [36, 37, 38, 39] 為四個字組，則 CPU 讀取 38 號字組之順序為:
  載入 36 $\rightarrow$ 37 $\rightarrow$ 38, CPU 讀取 $\rightarrow$ 39

• 需要的字組先送(requested/critcal word first): CPU 所需要的字組會先從層次較遠的記憶體送到層次較近的記憶體裡並讀取，剩餘的字組才依序載入

  $^{ex.}$ 若直接對映快取記憶體之第一張圖裡 9 號 block [36, 37, 38, 39] 為四個字組，則 CPU 讀取 38 號字組之順序為:
  載入 38, CPU 讀取 $\rightarrow$ 36 $\rightarrow$ 37 $\rightarrow$ 39

$\therefore$ 速度上: 儘早重新開始 > 需要的字組先送

快取的基礎概念

讀取快取的命中與失誤已在區塊的命中與失誤中講解，以下為寫入命中後與失誤時快取與主記憶體如何處理與配置

寫入命中後快取的處理

• 寫穿(write-through): CPU 寫入快取的同時也寫入主記憶體
  • 優點: 設計簡單
  • 缺點: 效能差
• 寫入緩衝器(write-buffer): 寫穿的改良，CPU 寫入快取的同時也寫入緩衝器，寫入後 CPU 可以繼續執行；當 CPU 企圖寫入已滿的緩衝器時，必須被暫停直到緩衝器寫入主記憶體後清空為止

  緩衝器(buffer): 小小記憶體，可用 SRAM

• 寫回(write-back): CPU 要寫入記憶體時，只先寫入快取，直到在快取中被寫入的區塊要被置換時才寫入主記憶體
  • 優點: 效能佳
  • 缺點: 設計複雜

寫入失誤時快取的配置

• 寫入配置(write-allocate): 在快取中配置一區塊，由主記憶體中取得所需區塊資料後，將其寫入配置之區塊中

  通常搭配: 寫回(write-back)

• 寫入不配置(no-write-allocate): 又稱繞過寫入(write-around)，直接繞過快取，寫入在主記憶體中該區塊的部分，而不在快取中配置此區塊

  通常搭配: 寫穿(write-through)

快取的實現

• 分離式快取(split/seperate cache): 分成指令快取與資料快取，為 Harvard Architecture，現今的商用 computer、pipeline Datapath($\because$ avoid structural hazard) 皆是
  • 優點: 頻寬較大
  • 缺點: 命中率較低
• 結合式快取(combined/unified cache)
  • 優點: 命中率較高
  • 缺點: 頻寬較小

頻寬(bandwidth): 資料量 / 單位時間

設計支援快取的記憶體系統

交錯(interleaving): 位址透過匯流排送至需要存取的 1 word Memory banks 時，允許同時存或取所需資料

提升記憶體結構支援快取

• EDO RAM(Extended Data Output Random Access Memory): 2 dimensions(page)
• SDRAM(Synchronous Dynamic Random Access Memory): 3 dimensions(pages)，爆量存取(burst access)的資料藉由時脈訊號(clock signal)所控制
• DDR SDRAM(Double Data Rate Synchronous Dynamic Random Access Memory): 資料在時脈的上升與下降邊緣皆可傳輸 $\Rightarrow$ 同樣的時脈速度可獲得雙倍頻寬
• QDR SDRAM(Quad Data Rate Synchronous Dynamic Random Access Memory): 分開輸入與輸出，讀寫可同時進行 $\Rightarrow$ 同樣的時脈速度可獲得四倍頻寬

考試會考縮寫拼出全名

快取效能的量測