# Memory

電腦中的「記憶體」分成了很多階層：

<iframe src="https://drive.google.com/file/d/1xYmck9xYnoXQ_s4P-fDVx7NJgpbwFpAf/preview" height="580"></iframe>

之前寫組語時接觸到的 REG 就是速度最快的記憶體，但同時他也容量最小，最昂貴。

接下來我們要接觸到的記憶體是「Cache」，REG 的下一層級，也就是 L1 L2 L3 快取，單位是「==Block==」

## Locality

記憶體能分成這麼多階層，是因為 Program 在記憶體的操作上具有「區域性」：

- Temporal Locality
- 時間上的區域性，在一定短的時間內都是操作相同的區域，例如迴圈操作
- Spatial Locality
- 空間上的區域性，如果操作某個區域，則鄰近區域也很有可能會一起操作，例如陣列存取

這樣的區域性，搭配較小的硬體可以有更快的速度，造就了現今的記憶體層級。

## Hit 跟 Miss

如果某個資料可以在 Cache 中找到，代表不用從 Memory 去拿，此時稱作 ==Hit==
否則就需要將資料從 Memory 搬進 Cache 裡面，此時稱作 ==Miss==。

- Hit Rate：Cache 中可以 Hit 的比率
- Miss Rate：1 - Hit Rate。
- Hit Time：Hit 所需的時間
- 「判斷是否為 Hit」的時間，加上「讀取 Cache」的時間，不過這兩個的時間都非常短
- Miss Penalty：Miss 時需要的時間
- 「將資料從 Memory 搬到 Cache」的時間，加上「將資料送到 Processor」的時間
- 因為需要從 Memory 搬資料，花的時間很長
- Hit Time << Miss Penalty

# 資料的 Address

:::warning
當 CPU 需要某個 Memory 的資料時，通常會透過 MMU (**memory management unit**) 先把地址換成實體地址(Physical Address)，然後這個地址再傳給 Cache。
:::

資料的實體地址因為是 2 進制 & Byte-Address，其實有個有趣且好用的性質，假設我們有 1 個 bytes 的資料 A 在下面的地址：

$$
A=0011\ 0011\ 1010\ 0101\ 1111
$$

那假如我們對資料做 ==分區== 的動作，例如從地址 0 開始：

- 每 16 個 bytes 為一小組
- 每 256 個 bytes 為一中組
- 每 4096 個 bytes 為一大組

我們可以注意到：

- A 所在的小組是 $0011\ 0011\ 1010\ 0101$，剛好就是他的地址 mod 16 的結果
- A 所在的中組是 $0011\ 0011\ 1010$，剛好就是他的地址 mod 256 的結果
- A 所在的大組是 $0011\ 0011$，剛好就是他的地址 mod 4096 的結果

A 換個方式可以說他在 $0011\ 0011$ 大組的 $1010$ 中組的 $0101$ 小組，並且他在小組的編號是 $1111$。

所以對於任何其他地址，我們都可以這樣快速的找到他是哪個大中小組。
這在接下來的 Cache 結構中起到很重要的作用。

# Directed-mapped cache

這種 Cache 的結構，顧名思義就是直接用地址 Map 到 Cache 裡面。

- Cache 只有有限的大小，這裡我們假設只能放 4 個 Block 的資料
- 一個 Block 這裡定義為 16 bytes

現在我們要將 0xAFFF0800 到 0xAFFF0807 這 8 個 ==Block 資料== 放到 Cache 裡面，那要怎麼知道 Cache 中誰是誰？就是上面的提到的分組概念：

- 0xAFFF0800 是 ==Block Address==，0xAFFF0800 跟 0xAFFF0801 之間實際有 16 個 bytes
- 0xAFFF0801 各 16 個 bytes 的地址是 0xAFFF0801==0== ~ 0xAFFF0801==F==
- 因為 Cache 只能放 4 個 Block，所以==Block 地址 mod 4== 就是該 Block 在 Cache 中用來放置跟查找的==編號 Index==。
- 例如 0xAFFF0801 就會放在 Cache 中==編號 1== 的位置
- 但是 0xAFFF0800 跟 0xAFFF0804 都會對應到 Cache 中的==編號 0==，如果 Cache 中有==編號 0== 的話我要怎麼知道他是誰？
- 所以 Cache 中會把 0xAFFF0800 除以 Cache 大小(目前的情境是 4 個)的部分作為==標籤 Tag==
- 0xAFFF080~16~0001~2~ 就是 0xAFFF0804 的 ==標籤==
- 別忘記地址是 16 進制， 4~16~=0100~2~ 除以 4 會得到 0001~2~
- 當我們想拿 0xAFFF0804 的資料時
- 先檢查 Cache 中 ==編號 0== 有沒有資料
- 有的話檢查 ==標籤== 是不是 0xAFFF0804 的標籤
- 如果我們只想要 0xAFFF0804 這個 Block 的第 3 個 byte
- 別忘記 0xAFFF0804 是 block address
- 所以實際上 0xAFFF08043 就是第 3 個 byte 的地址
- 地址中 3 這個值就代表第 3 個 byte 在這個 block 的 ==offset 位移==
:::info
所以當 CPU 想要某 1 個 byte 時，會傳一個地址給 Cache，這個 Cache 根據上面的流程可以分成 ==Tag==、==Index== 跟 ==offset== 3 個部分。
這 3 個部分就是上面提到的 3 個大中小組。
:::

## 電路圖

下圖是電路結構圖，但是其實算是化簡的版本：

<iframe src="https://drive.google.com/file/d/1NaqwK4txXcMP-R978JSryf50ipHDfo3S/preview" height="580"></iframe>

<!--  -->

<iframe src="https://drive.google.com/file/d/18ln6QGNq7ayajR-_igR7tsA-FylkFlQx/preview" height="280"></iframe>

<!--  -->

這就是上面提到的，Memory Address 會被拆成 3 個部分，Offset 是小組，Index 是中組，Tag 是大組。

- 地址通常是 32 bit，代表 Memory 中可以有 4G 的資料
- 對照上面的電路圖，可以看到 Tag 就會拿去跟 Cache 中的 Tag 來比較 (那個 = 電路)
- Index 就會決定要拿 Cache 中的哪一個 Block 資料，==或者說第幾個 Set(見下方)==
- Offset 決定要這個 Block 的第幾個(作為 MUX 的 flag)

我們聚焦到 Cache 的部分：

<iframe src="https://drive.google.com/file/d/1EWFUgQUlpiB6h2WKjYSCYIxnJV3QcFZF/preview" height="380"></iframe>

<!--  -->
>我 Sets 忘記加 s

這個部分就是我們的 Cache，一個 Cache 是由很多個 Sets 組成；每個 Set 裡面則有：

- Valid Bit
- 這個是一個用來判斷的 Bit，下面會介紹
- Cache Tag
- 當一個 block 資料放進 Cache 時，要記得紀錄 Tag
- Cache Data
- 就是一個 Block 裡面的資料，上圖中一個 Block 為 16 Bytes
- 當我們講 1 KB Direct Mapped Cache，**這個 1 KB 是指 Cache Data 的大小**
- 所以上圖就是 256x16=4096=4 KB 的 Direct Mapped Cache

:::warning
所以總結來說，對於一個 $2^n$ bytes direct-mapped cache，並且 Block size 是 $2^m$ Bytes：

- Bytes Offset 需要 $m$ 個 bit
- Cache Index 需要 $n-m$ 個 bit
- 因為 Sets 數量為 $2^n÷2^m=2^{n-m}$ 個
- 所以需要 $n-m$ 個 bit 來定位 set
- Cache Tag 需要 $32-(n-m)-m=32-n$ 個 bit
- 換個角度說，這 $n$ 個 bit 可以決定一個 byte 在哪裡
- $n-m$ 決定第幾 row，$m$ 決定第幾 col
:::

:::info
有些題目會特別問 Cache Size，此時極有可能是在問 valid + tag + data 的部分，而不是只有 data 的部分。
:::

## 手算

- Cache 有 64 個 block，每個 block 16 個 Bytes
- 某個資料在 memory 中的地址為 1200~10~：

$$
\displaylines{
\left \lfloor \frac{1200}{16} \right \rfloor = 75\\
75\ \text{mod}\ 64=11
}
$$

可知他在第 11 個 block；而 1200 mod 16 = 0，所以在第 0 個 offset。
但是我們也可以先這樣做：

$$
1200_{10}=4\text{B}0_{16}=0100\ 1011\ 0000_{2}
$$
最後 4 個 bit 是 offset，64 個 block 需要 6 個 bit 作為 index，那 6 個 bit 就是 001011=11。

## Block Size

如果我們有很大的 Block Size：

- 優點：
- 我們在空間區域性上可以有很好的優勢。
- 缺點：
- Cache 大小有限，Block Size 越大 Sets 數量會越少，也就代表越容易發生競爭 competition，反而可能夠容易發生碰撞。
- 並且還會有著更長的 miss penalty 時間

miss penalty 目前有一些方法可以緩解：

- Early restart
- 在搬運的過程，一旦發現已經搬到想要的 Bytes 了，就不繼續搬，直接結束
- 所以有可能不會把完整的 Block 搬回來
- Requested word first
- 不管其他 Bytes，直接鎖定我要的 Bytes 搬進來就好

# Read Write Handling

接著來細講要怎麼讀寫 Cache。

## Handling Read

Read 跟上面的介紹很像，就是去 Cache 裡面翻看有沒有資料：

1. Cache index 找到正確的 entry
2. Cache tag 判斷是否為想要的資料
3. Valid bit 看是不是 Valid
4. Btyes offset 找到想要的 Bytes

Valid bit 見下方：)

## Read Miss Policy

那 4 步有一個失敗的話就要從 Memory 去搬。

**搬好後 Valid bit 要設為 1**。
>因為剛開機時 Valid bit 會被設為 0

## Handling Writes

Write，有兩種 Policy：

- ==Write through==
- 資料除了會寫進 Cache，還會寫回 Memory
- 資料是同步的 Consistence
- ==Write back==
- 資料只寫進 Cache，設置「==Dirty Bit==」
- 如果有一筆資料即將因為一個 Read 而被替換 ==Eviction==掉
- 先檢查 ==Dirty Bit==，看他是不是某個 write back 的資料
- 如果是的話，就要先寫回 Memory

## Write Miss Policy

有 2 個 Policy，加上因為 write 有兩種，所以實際上有 4 種情況：

- Write allocate (fetch on write)
- 將要寫入的資料==搬到 Cache==
- WT：將資料搬到 Cache，再寫入 Cache & Memory
- WB：將資料搬到 Cache，一樣只寫在 Cache，設置 dirty bit
- 由於資料會搬進 Cache，所以 write miss 是有可能導致資料寫回 memory 的
- No-write allocate (write-around)
- 不會把要寫入的資料搬到 Cache
- WT：因為沒有搬進 Cache，所以只會寫進 Memory
- WB：因為沒有搬進 Cache，所以只會寫進 Memory
- 所以 write-around 的 Cache 資料都是 read 時搬的

### 優缺點

- WT
- 優點：資料保持一致，並且不會因為某次的 Read Miss 導致的替換，導致需要進行 Memory Write
- 缺點：每次都需要等待寫回 Memory 的時間
- WB
- 優點：如果對同個地址作多次寫入，就不用一直寫進 Memory，很省時間
- 缺點：資料沒有一致性，而且每次的 Read Miss 有可能要付出更多的時間

### Write Buffer for Write Through

由於 WT 每次都要等待完整的寫回 Memory，所以聰明的人們又想出了 Buffer 的技巧。

<iframe src="https://drive.google.com/file/d/1kgWNR_0zk-gRoKsAS2cX9Qk3sEVGlLPg/preview" height="380"></iframe>

<!--  -->

每次要寫的時候，除了一樣會寫入 Cache，原本的寫回 Memory 改成了寫入 Buffer 裡面：

- 如同其名，他就是個緩衝，寫入的速度會比 Memory 快很多
- 他是 FIFO
- 我猜應該是跟 Cache 同等級的
- 新增一個 Memory controller，負責將 Buffer 的內容寫回 Memory
- 因為寫進 Buffer 很快，就不會被寫回 Memory 的時間給拖累

只要執行寫回指令的頻率，小於寫進 DRAM (buffer 寫進 Memory)的頻率，那麼 buffer 就起到很好的緩衝作用。
但要是反了過來， Buffer 就沒用了：)

而現在其實也有很多的 WB 也會使用 Buffer 的技術來減少 Miss Penalty。
>我猜應該是將寫回 Memory 的部分改成寫進 Buffer

# Split cache vs. Combined cache

Intel 在 Pentium 1993 開始，將 Cache 分成了 Data Cache 跟 Instruction Cache，這就是 Split cache。

- Split cache
- 優點：higher cache bandwidth，因為可以同時讀兩種資料，bandwidth 會變成兩倍
- 缺點：低 Hit rate，因為 Cache 總共大小不變，但是被分成了兩塊，所以 Sets 數量會變少
- Combined cache
- 優點：Split 的相反，高 Hit rate。
- 缺點：一樣是 Split 的相反，lower cache bandwidth

老師說現在的 CPU，大多會將：

- L1 Cache 設為 Split cache，因為要求速度，希望高的 bandwidth
- L2 或 L3 Cache 則會是 Combined cache，因為在下一層就是 Memory
- 如果發生 Miss 就會是 Memory 層級的速度，不像 L1 發生 Miss 的話是 Cache 層級的速度
- 因此才會採用高 Hit Rate 的 Combined cache

# Memory Design

有三種 Memory Design：

<iframe src="https://drive.google.com/file/d/1WJHS1txOcxH7rbSQtgUdmZxzcQsoSkpW/preview" height="580"></iframe>

<!--  -->

- One-word-wide memory organization
- Memory 跟 Cache 間的 Bus 寬度為 1 word (4 bytes)
- 如果一個 address 要求讀取 1 block (16 bytes)，就要進行 4 次「Memory 讀取」
- Wide memory organization
- Memory 跟 Cache 間的 Bus 寬度為多個 word
- 下面的例子中為 2 word
- Interleaved memory organization
- Memory 跟 Cache 間的 Bus 寬度為 1 word
- 但是資料會以 Bank 的方式儲存，每個 Bank 寬度為 1 word
- 假設這裡總共有 4 個 Bank，因此如果 address 要求讀取 1 block，1 block 有 4 個 word，只需要進行 1 次「Memory 讀取」

前面的介紹中，一個 Memory Address 只會要求一個 Byte，那這裡怎麼就可以要求 1 block？答案是Memory Address 的結構有經過修改，我猜應該是直接不管 Btyes Offset。

那個 Bank 的結構，我推測應該就是將原本 Memory 的資料分在四個地方儲存，每個地方寬度是 1 word；這樣進行 Memory 存取時，就可以四個地方同時進行存取，也因此才會有上面的『只需要進行 1 次「Memory 讀取」』

## 模擬

下面模擬中，一次 Address 要求回傳 1 block (4 個 word)的內容，並且情境為：

- 一條 bus 寬 4 個 bytes = 1 個 address = 1 個 word
- One-word-wide memory organization：Cache 跟 Memory 之間 1 條 bus 的寬度
- DRAM access 一次只能抓 1 個 word
- Wide memory organization：Cache 跟 Memory 之間變成 2 條 bus 的寬度
- DRAM access 一次可以抓 2 個 word
- Interleaved memory organization：有 4 個 bank
- 每個 bank one word 寬，1 個 bank access 一次可以抓 1 個 word
- 從 Cache 送 Address 到 Memory 要 ==1 memory bus cycle==。(簡稱 ==要求==)
- DRAM access 需要 ==15 memory bus cycle==(簡稱 ==查詢==)
- 從 Memory 傳 word 到 Cache 要 ==1 memory bus cycle== (簡稱 ==回傳==)

然後是三種情境：

- One-word-wide memory organization
- ==要求==：1 memory bus cycle
- ==查詢==：4 x 15 memory bus cycle
- ==回傳==：4 x 1 memory bus cycle
- 總共為 $1 + 4 \times 15 + 4 \times 1=65$
- Wide memory organization：
- ==要求==：1 memory bus cycle
- ==查詢==：2 x 15 memory bus cycle
- ==回傳==：2 x 1 memory bus cycle
- 總共為 $1 + 2 \times 15 + 2 \times 1=33$
- Interleaved memory organization
- ==要求==：1 memory bus cycle
- ==查詢==：1 x 15 memory bus cycle
- 因為一次的 Memory Access 可以從 4 個 bank 各讀 1 word 出來
- ==回傳==：4 x 1 memory bus cycle
- 總共為 $1 + 1 \times 15 + 4 \times 1=20$

# Cache Performance

原本指考慮 CPU cycles，現在要多考慮 Memory 的 stall cycles：

$$
\begin{align}
&\text{CPU time} = \text{(CPU execution clock cycles + Memory stall clock cycles) × clock cycle time}\\
&\text{Memory stall clock cycles } = \text{Read-stall cycles + write-stall cycles }\\
&\text{Read-stall cycles }= \text{# of Read × Read miss rate × Read miss penalty}\\
&\text{Write-stall cycles } = \text{( # of Writes × Write miss rate × Write miss penalty) + Write buffer stalls.}
\end{align}
$$

:::warning
Memory 的 stall cycles 由 Read Write stall Cycle 所組成，但是 Hit 的話代價很小可以不管，我們只看 Miss 的 Penalty。
:::

### 如果不細分是 ready 或 write 的話

Memory stall clock cycle 則會是：

$$
\begin{align}
\text{Memory stall clock cycles } &= \text{# Memory accesses × Miss rate × Miss penalty}\\
&= \frac{\text{Instructions}}{\text{program}} × \frac{\text{Misses}}{\text{Instruction}} × \text{Miss penalty}\\
\end{align}
$$

$\text{# Memory accesses}=\frac{\text{Instructions}}{\text{program}}$ 單純是因為考量了多個 program 的可能，要把他換算成 per program 而已。

$$
\text{Average memory access time = Hit time + Miss rate × Miss penalty}
$$

# Memory Stall 的影響

如果我有個情境如下：

- $I$-Cache miss rate = 2%
- $D$-Cache miss rate = 4%
- Base CPI 2.0
- Miss penalty = 100 cycles
- Frequency of loads and stores is 36%
- 總共有 $X$ 個指令
- Clock cycle 為 $Y$ ps

**這個情境不細分 read 跟 write，所以不會有 write buffer stall**

所以我們可以算出：

- $I$-Cache stall cycle：
- $X\cdot 2\% \cdot 100=2X$
- $D$-Cache stall cycle：
- $X\cdot 36\% \cdot 4\% \cdot 100=1.44X$
- CPU cycle：
- $X\cdot 2=2X$
- CPU time with stalls：
- $(2X+1.44X+2X)\cdot Y=5.44XY$ ps

如果是完美沒有 Miss 的 Cache CPU，則會是 $2XY$ ps

速度上相差 $\frac{5.44XY}{2XY}=2.72$ 倍。

:::warning
CPU cycle 又稱 **hit time**
:::

## DRAM 速度問題

如果此時我們將 clock rate 提升為兩倍，也就是說 Clock cycle 變為 ==$\frac{Y}{2}$== ps。
但是要注意，因為我們只提升 CPU 的 clock rate，而沒有提升 Memory cycle 的 clock rate，因此 Miss penalty 會變為 ==200 cycles==；這就是老師提到的， CPU 速度上去了，但 Memory 速度沒上去的問題。

所以我們來算一次提升 clock rate 後的時間：

- $I$-Cache stall cycle：
- $X\cdot 2\% \cdot 200=4X$
- $D$-Cache stall cycle：
- $X\cdot 36\% \cdot 4\% \cdot 200=2.88X$
- CPU cycle：
- $X\cdot 2=2X$
- CPU time with stalls：
- $(4X+2.88X+2X)\cdot \frac{Y}{2}=4.44XY$ ps

拿來跟提升前的時間來比較的話，速度上相差 $\frac{5.44XY}{4.44XY}\approx 1.23$ 倍。
理論上頻率拉高兩倍，應該可以有 2 倍的進步，但是這跟我們所期望的 2 倍相差甚遠。

---

## 回顧

- Directed Mapped Cache
- Read Write Handling
- Memory Design
- Cache Performance