# Chap. 05 - Memory Hierarchy
> 課程內容 : 清華大學開放式課程 黃婷婷教授
> 參考書目 : Computer Organization and Design: The Hardware/Software Interface (5th), David A. Patterson, John L. Hennessy
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

## Contents
* [5.1 Memory hierarchy](#51-Memory-hierarchy)
* [1. Memory technology](#1-Memory-technology)
* [2. Memory hierarchy: Principle](#2-Memory-hierarchy-Principle)
* [3. Memory hierarchy: terminology](#3-Memory-hierarchy-terminology)
* [5.2 The basic of caches](#52-The-basic-of-caches)
* [1. Direct-mapped cache](#1-Direct-mapped-cache)
* [1.1 Tags and valid bits: block finding](#11-Tags-and-valid-bits-block-finding)
* [2. Address sub-division](#2-Address-sub-division)
* [2.1 Example: large block size](#21-Example-large-block-size)
* [2.2 Address subdivision](#22-Address-subdivision)
* [3. Cache hit and miss](#3-Cache-hit-and-miss)
* [3.1 Read cache](#31-Read-cache)
* [3.2 Write hit: write-through](#32-Write-hit-write-through)
* [3.3 Write hit: write-back](#33-Write-hit-write-back)
* [3.4 Write miss: write allocation](#34-Write-miss-write-allocation)
* [3.5 Example: Intrinsity FastMATH](#35-Example-Intrinsity-FastMATH)
* [4. Memory support](#4-Memory-support)
* [4.1 Interleaving v.s. without interleaving](#41-Interleaving-vs-without-interleaving)
* [4.2 Access of DRAM](#42-Access-of-DRAM)
* [5.3 Measuring cache performance](#53-Measuring-cache-performance)
* [1. Average access time](#1-Average-access-time)
* [5.4 Improving cache perofrmance](#54-Improving-cache-perofrmance)
* [1. Set associative cache](#1-Set-associative-cache)
* [1.1 Associative caches](#11-Associative-caches)
* [1.2 A 4-way set-associative cache](#12-A-4-way-set-associative-cache)
* [1.3 Compare data available time](#13-Compare-data-available-time)
* [1.4 Data placement policy](#14-Data-placement-policy)
* [2. Multiple level cache](#2-Multiple-level-cache)
* [5.5 Virtual memory](#55-Virtual-memory)
* [1. Basics](#1-Basics)
* [2. Issues in virtual memory](#2-Issues-in-virtual-memory)
* [2.1 Block size and placement policy](#21-Block-size-and-placement-policy)
* [2.2 Page tables](#22-Page-tables)
* [2.3 Page fault](#23-Page-fault)
* [2.4 Page replacement and write](#24-Page-replacement-and-write)
* [3. Handling huge page table](#3-Handling-huge-page-table)
* [4. TLB](#4-TLB)
* [4.1 Fast translation using a TLB](#41-Fast-translation-using-a-TLB)
* [4.2 TLB hit](#42-TLB-hit)
* [4.3 TLB miss](#43-TLB-miss)
* [5. TLB and cache](#5-TLB-and-cache)
* [5.1 Making address translation practical](#51-Making-address-translation-practical)
* [5.2 Integrating TLB and cache](#52-Integrating-TLB-and-cache)
* [5.6 A common framework for memory hierarchy](#56-A-common-framework-for-memory-hierarchy) (暫略)
* [5.7 Using a finite state machine to control a simple cache](#57-Using-a-finite-state-machine-to-control-a-simple-cache)
* [5.8 Parallelism and memory hierarchies: cache coherence](#58-Parallelism-and-memory-hierarchies-cache-coherence)
* [1. Cache coherence problem](#1-Cache-coherence-problem)

## 5.1 Memory hierarchy
### 1. Memory technology
記憶體依照儲存技術可以大致分成兩種: (1) random access 與 (2) magnetic disk

Random Access Memory (RAM，隨機存取記憶體)，表示 access 任何位置所需的時間都是一樣的 (access time same for all location)。RAM 又可分為兩種類型:

(1) SRAM: Static Random Access Memory，靜態隨機存取記憶體
* 性質
* 低密度 (density): 單位面積能儲存的的資料較少
* 高耗能
* 價格高，速度快 (幾乎同步於 clock cycle)
* Static
* 意指只要保持電力供應，SRAM 所儲存的資料就可以繼續保存，不會消失也不需要定期更新 (refresh)
* 但只要斷掉電力，所儲存的資料就會消失 (揮發性記憶體)
* Address 不可再細分，只要給定 address 就可以找到該位址的內容
* 通常用在 caches (快取記憶體) 之中

(2) DRAM: Dynamic Random Access Memory，動態隨機存取記憶體
* 性質
* 高密度
* 低耗能
* 價格便宜，但速度慢
* Dynamic
* 意指需要定期更新 (refresh) 來保持資料
* 如果不定期更新，則資料會因為物理特性而慢慢消失
* Address 包含了兩個部分
* 以類似 2-D matrix 的方式，尋找 address 所對應的資料
* 先找 row，在找 column
* 通常用在 main memory (一般所說的 memory 指的就是 DRAM)

:::info
在記憶體中，更新 (refresh) 指的不是更新資料內容，而是重新穩定並保護原有資料
:::

一般來說，理想的記憶體最好是: (1) 具有 SRAM 的 access time 和 (2) disk 的容量與成本。但實際上並沒有單一的記憶體可以做到這件事，所以目前都是採用階層化的設計，如下圖所示。


就算花錢把 cache 搞大，但速度一樣會變慢 (small is fast)

### 2. Memory hierarchy: Principle
階層化的記憶體設計，使得資料一般會在相鄰的兩層間進行複製與傳輸。相對位置的層級概念會用以下兩種方式表達:

* Upper level: 靠近 processor 的記憶體，容量較小，速度快，價格昂貴
* Lower level: 遠離 processor 的記憶體，容量較大，速度慢，價格便宜

此外，資料在層級之間傳輸的過程是以 block 為單位，是由一個小範圍的的資料組成，常見的單位是 32 bytes 或 64 bytes，這樣的設計可以避免資料做過多的搬移。

##### Why hierarchy works ?
記憶體架構採用階層化的設計是有原因的，可以由程式執行過程所觀察到的結果來做歸納

> **Principle of locality**
> Program access a relatively small portion of the address space at any instant of time

根據 90/10 rule，程式執行的過程中，大約 90% 的時間都在執行 10% 的程式碼，像是 loop，if-else 等。同理，程式執行的過程中，大部分的時間只會 access 一小部分的記憶體空間。

> **Two types of locality**
> (1) Temporal locality: if an item is referenced, it will tend to be referenced again soon
> (2) Spatial locality: if an item is referenced, it whose address are close by tend to be referenced soon

當某個程式碼區塊被執行時，他會馬上再次被執行，例如 loop 的設計。同理，當某個記憶體位址的內容被 access 時，他會馬上再次被 access。

當程式中某個資料被使用時，它鄰近的位址的資料也會被使用到，例如 array 的資料結構、 instruction fetch 的設計(PC = PC + 4)。同理，當某個記憶體位址的內容被 access 時，該記憶體位址附近的區塊不久後也會被執行

##### How is the hierarchy managed
記憶體的階層式設計如下圖所示:


* Register $\leftrightarrow$ cache
* 兩者之間由 compiler 做管理
* 資料傳輸單位是 instruction 或 operands
* Cache $\leftrightarrow$ memory
* 兩者之間由 hardware 進行管理
* 資料傳輸單位是 block
* Memory $\leftrightarrow$ disk
* 兩者之間由 OS (virtual memory) + 少量的 hardware 管理
* 資料傳輸單位是 pages

### 3. Memory hierarchy: terminology
處理器進行運算時需要資料，當所需存取的資料在上層記憶體 (upper level) 時，就稱為 hit (命中，hit)

* Hit rate: 命中比例，指的是在上層記憶體中找到資料的比例，也就是資料存取時發生命中的比例
* Hit time: 命中時間，表示從 upper level 存取資料所需的時間，包含了從從記憶體存取的時間，以及檢查發生 hit/miss 的時間
* Hit time = RAM access time + time to determine hit/miss

當所需存取的資料不在 upper level，必須從 lower level 尋找載入時，就稱為 miss (未命中)

* Miss rate = 1 - hit rate
* Miss penalty: 當發生 miss 時，因為需要進行更多的資料搬移，所以得要付出更多的成本，包括將資料傳輸到 upper level，將資料傳輸到 processor

通常，hit time << miss penalty，命中的情況是非常少的，所以提升命中率對處理器的效能很重要。

### 4. 4 Question for hierarchy design
記憶體的階層式架構設計中，主要有 4 個關鍵的問題，每個問題剛好對應一個關鍵的解法

> Q1: Where can block be place in the upper level ?

此問題要探討的是，當從 lower level 載入一個 block 到 upper level 時，block 應該要放在 upper level 中的哪個位置 ?

此問題會牽涉到解決方法稱為 block placement

> Q2: How is a block found if it is in the upper level ?

此問題討論，當資料在 upper level 時，要透過什麼方式可以找到這個 block。此問題牽涉到的解決方法稱為 block findind

> Q3: Which block should be replaced on a miss ?

當 upper level 的空間已經滿了，且沒有發生命中 (hit) 時，需有一個 block 從 upper level 移出。此問題會牽涉到的解決方法稱為 block replacement，用來決定哪個 block 會先被移出。

> Q4: What happens on a write ?

當把新的資料從 processor 寫入 cache 時，如何做到讓 cache 和 memory 的資料同步。
此問題會牽涉到的解決方法稱為 write strategy

## 5.2 The basic of caches
### 1. Direct-mapped cache
> 當 block 從 lower level 載入至 upper level 時，應該要放在 upper level 的哪個位置 ?

此處牽涉到 4 個關鍵問題的第一個解決策略: block placement，最簡單的 block placement 稱為 direct-mapped cache。

以下圖為例，upper level 的 cache 總共有 8 個 block，而 lower level 的 memory 有很多個 block。


* <font color=#0000C6>將 lower level 的 block 取 module 8 後所得到的餘數，就可以找對該 lower level 所對應的 upper level 的 block 的位置。</font>
* 以上圖為例
* lower level 中的 4 個橘色的 block 對應到 upper 的橘色的 block，當 lower level 的 block 要移到 upper 時，就會去找對應的位置放進去
* lower level 中的 4 個灰色的 block 對應到 upper 的灰色的 block，當 lower level 的 block 要移到 upper 時，就會去找對應的位置放進去
* <font color=#00a600>除了取 module 外，看 lower level block 的 address 的末三碼也是一樣的意思</font>

#### 1.1 Tags and valid bits: block finding
> 因為一個 cache 的位置 (location) 對應到很多個 lower level 的 block，當 CPU 嘗試 access 某個 cache 的位置時，要如何知道這個 cache 的位置是我要的資料 ?

因此，在 cache 中除了儲存 data 以外，也要儲存 block address。但實際上在 direct-mapped 中，一個 cache location 所對應的 block 的 address 的末幾碼是相同的 (E.g. 以上述為例是末三碼)，所以只要比較 high-order 的 bits 即可。這些 high-order bits 稱為 tag

此外，還要確認當前的 cache location 有沒有資料，所以會在使用一個 valid bit 來儲存當前狀態

* valid bit = 1: present
* valid bit = 0: NOT present
* 初始化狀態時，valid bit 皆設為 0

##### Example


* 以 cache loction = 8 block，1 word/block 的 direct mapped 為例
* 上圖為初始狀態，valid bit = 0


當 processor 要存取 word address = 22 為例 (上圖)，會去找 word address = 22 所對應的 cache 有沒有資料

* <font color=00a600>Word address = 22 對應的 binary address 是 10110，先從末三碼 110 找對應 cache location 的 index</font>
* <font color=ea0000>再從 high-order bit 找到 tag = 10</font>
* <font color=ff5809>因為 cache location 中沒有資料 (valid = 0，cache miss)，所以讀取來自 Mem[10110] 的資料放入 cache 中</font>
* valid bit = 1


當 processor 要存取 word address = 26 為例 (上圖)

* <font color=00a600>對應的 binary address = 11010，先從末三碼 010 找對應 cache location 的 index</font>
* <font color=ea0000>再從 high-order bit 找到 tag = 11</font>
* <font color=ff5809>因為原先 cache location 中沒有資料 (valid = 0，cache miss)，所以再從 Mem[10110] 中將資料搬移至 cache 中</font>
* valid bit = 1


當 processor 要再次存取 word address = 22 的資料 (上圖)

* <font color=00a600>對應的 binary address = 10110，先從末三碼的 110 找對應的 cache location 的 index</font>
* <font color=ea0000>再從 high-order bit 找到 tag = 10</font>
* <font color=ff5809>因為原先的 cache location 已經有資料 (cache hit)，所以直接取用 cache 中的資料</font>


當 processor 要存取 word address = 18 的資料 (上圖)

* <font color=00a600>對應的 binary address = 10010，先從末三碼的 010 找對應的 cache location 的 index</font>
* <font color=ea0000>再從 high-order bit 找到 tag = 10</font>
* <font color=ff5809>雖然原先的 cache location 已經有資料 (valid bit = 1)，但因為新的 tag (=10) 與 cache location 內存有的 tag (=11) 不同 (cache miss)，所有要更新 tag，再從 Mem[10010] 中將資料搬移至 cache</font>

:::info
* word address 指的是記憶體中以 word 為單位來定址記憶體位址的的方式，也就是說每個位址指向一個 word，常見的 word 大小是 32/64 bits，或 4/8 bytes
* bytes address 是以 bytes 為單位來對記憶體位址定址，每個位址指向一個 bytes
:::

### 2. Address sub-division
#### 2.1 Example: large block size
> 以 block number = 64，block size = 16 bytes 為例，當 memory adderss = 1200 時，會對應哪個 block ?

Block number = 64 表示 cache 中總共有 64 個 block，每個 block 的大小是 16 bytes

$$
\text{block address} = \lfloor{1200/16}\rfloor = 75
$$

表示 memory addr = 1200 是第 75 個 block

$$
\text{block number} = 75 \mod{64}=11
$$
表示對應到 cache 中的第幾個 block

將 block address = 75 轉成 binary = 1**001011**，只要看最後的 6-bits 即可知道對應的 block index。所以 block index = 001011 = 11。以 32-bits 的 address length 為例 :


* 最後的 4-bits 代表 bytes offset (block size = 16 = $2^4$)
* 中間 6-bits 代表 block index (block number = 64 = $2^6$)
* 剩下 22-bits 的 high-order bits 作為 tag，如下圖所示。

#### 2.2 Address subdivision
以下列資訊為例:

* Cache 大小: 1k words，表示 cache 可以儲存 1000 個 words
* 因為 block number = 1k words，所以必須用 10-bits 來表示 block index
* block size: 1 word，表示每個 block 可以儲存 1 個 words
* 因為每個 block 可以儲存 1 個 word，又 1 word = 4 bytes，所以最後的 bytes offset 必須用 2-bits 表示，用以決定 access 該 block 中的哪個 bytes (4 選 1)
* 以 32-bits 為例，剩下的 20-bits 用來表示 tag，具體如下圖所示


Larger block size 的好處在於可以減少 cache miss 的發生，因為這樣的設計更符合 spatial locality 的性質。

然而，因為 cache 的大小是固定的 (fixed-size)，所以當 block size 越大，表示 block number 越小，越容易發生 cache miss (能儲存的資料不夠多)，所以 block size 與 block number 有 trade-off 的問題。


此外，越大的 block size 也會有越大的 miss penalty

* 發生 pollution 的問題 : 因為一次載入了過多的資料，但其中的多數資料是不會被處理器使用到的，導致 cache 中充斥太多不必要的資訊
* 為了降低 miss rate 而擴大 block size，反而會導致載入資料的時間成本變大
* 解決辦法
* Early restart
* Critical-word-first

### 3. Cache hit and miss
Cache 在讀取 (read) 跟寫入 (write) 時，都會發生 hit/miss 的問題，排列組合下總共會有 4 種情況:

* Cache read
* Read hit
* Read miss
* Cache write
* Write hit，有兩種方法: (1) write-through (2) write-back
* Write miss
#### 3.1 Read cache
##### Read hit
當 CPU 讀取 cache 中的資料時，資料已經在 cache 之中 (hit)，所以 CPU 可以直接讀取資料，不用去存取 lower level 的 memory。

##### Read miss
當 CPU 讀取 cache 中的資料，但該資料並未在 cache 之中 (miss)，這會造成 CPU pipeline 的停頓 (stall)，所以 CPU 必須從 lower level 的 memory 去擷取資料 (fetch block)

如果是 instruction 沒有存取成功 (instruction cache miss)，那就必須要重新做一次 fetch instruction

如果是 data 沒有存取成功 (data cache miss)，那就必須等待資料完成存取 (lower to upper) 後，才能繼續執行

#### 3.2 Write hit: write-through
:::info
**What is cache write and write hit/miss ?**
Cache write 指的是 processor 欲將資料寫入到 memory 中，但必須先將資料寫入至 cache 才能提升速度，但此時會遇到兩個問題。此處以 8-block 的 cache 為例，processor 要寫入到 memory 中的 mem[block #25]，對應的 cache index 是 cache[block #1]
* 如果 cache[block #1] 中所紀錄的 memory address 是 mem[block #25] $\rightarrow$ write hit
* 如果 cache[block #1] 中所紀錄的 memory address 是 mem[block #17] $\rightarrow$ write miss

簡單來說
* 如果 cache 中所紀錄的是欲寫入資料的(記憶體)位址，write hit
* 如果 cache 中紀錄的不是欲寫入資料的(記憶體)位址，write miss
:::
在 write-through 的特色在於，當 cache 發生 write hit 時，在將資料寫入 cache 的同時也會將 memory 的資料做同步更新，也就是在 cache 與 memory 中會有同一個資料的兩份備份。

* 優點 : 可以同步更新 main memory 的資料，數據一致
* 缺點: (1) Increase the traffic to memory (2) Makes write take longer
* 每次寫入 cache 時都需要同步更新記憶體，導致大量的記憶體操作，增加記憶體負擔
* 因為 main memory 的寫入速度遠比 cache 慢，所以大量的 memory 操作會脫慢寫入速度

:::info
**E.g.** 假設 base CPI = 1，有 10% 的 instruction 執行 store 的運算，寫入 memory 所需的時間是 100 clock cycle
[Sol]
Effective CPI = $1 + 10\% \times 100 =11$
:::

##### 解決方式: 使用 write buffer
當需要將資料寫入 memory 時，先將 資料寫入緩衝區，可以避免每次的寫入都發生 stall，只有當緩衝區滿位時才會把資料一次寫入 memory 之中，如下圖所示


Processor 會將資料寫入至 cache 與 write buffer (WB) 中，memory controller (hadware) 再將資料慢慢從 WB 也入 memory。只有當 WB 發生 saturation，CPU 才會 stall。

:::info
Write buffer 也是一種 FIFO 的結構
:::

#### 3.3 Write hit: write-back
與 write-through 相反，在 cache 更新資料的同時，不會同時更新 memory 的資料，但是會紀錄哪些 cache location 中的資料有被更新過，為此需要多一個 bit 來做紀錄，稱為 dirty bit。

當 cache block 中的資料被修改/更新過，則 該 block 的 dirty bit = 1，表示這個 block 的資料與 memory 不同步。當這個 block 需要被替換時，會先把 cache block 中修改過的資料寫回 memory 中。

Write-back 的策略也可以使用 buffer 的概念，當 dirty block 的資料被替換時，要寫入 memory 的資料可以先寫入 buffer 之中，待 buffer 滿了之後再一次寫入 memory，可以避免 CPU stalled。

#### 3.4 Write miss: write allocation
對應到 write hit 有兩種處理方式: (1) Write-through，同步更新記憶體 (2) Write-back，不同步更新記憶體。在 write miss 上也有對應這兩個的處理方式的解決策略。

##### Write-through
Write-through 會同步更新記憶體中的資料，此時有兩種不同的 write miss 策略:

* Allocate on miss
* 發生 write miss 時，先將欲存入資料的 block 從 memory 載入至 cache 中，再從 cache 中完成寫入操作，可以保持 cache 中存有最新的資料
* 優點 : 適合需要頻繁存取該 block 的狀況，降低記憶體存取的次數
* Write around
* 發生 write miss 時，不會將 block 從 memory 載入至 cache 中，而是直接將資料寫入至 memory block
* 優點 : 適合初始化狀況，先寫入資料但不會立即需要讀取的 block

##### Write-back
Write-back 的策略控制的是「何時會將資料寫入 memory」，所以可以搭配上述的 allocate on miss 一起使用。一般來說還是會先將 block 從 memory 載入至 cache，並在後續進行更新 cache 的操作。

#### 3.5 Example: Intrinsity FastMATH
以 embedded MIPS processor 為例，有 12-stage 的 pipeline，並在每個 cycle 可以分別處理 instruction access 與 data access。

此外也採用 split cache (分離式快取)，將 cache 分成 I-cache (for instruction) 與 D-cache (for data)，每個 cache 的大小是 16 KB (256 blocks × 16 words/block)，如下圖所示。


以類似 array 的方式做搜尋與選擇:
* 以 word address 的方式設計，所以 field_1[0:1] 用來做 bytes offset (1word = 4 bytes)
* <font color=#0000c6>因為 block size = 16 words，所以 field_2[2:5] 用來選擇哪個 words
* 這 16 words (1 block) 的資料會一起搬到 cache 中</font>
* 因為 block number = 256，所以 field_3[6:13] 用來做 block index 的 search
* 剩下的 field_4[14:31] 作為 tag

### 4. Memory support
此處要討論的是如何設計 memory，並思考如何將 memory 的資料傳輸到 cache 中，為此需要增加 memory bandwidth (頻寬) 來減少 miss penalty。

:::info
**Memory width**
記憶體位寬，指的是記憶體在一次傳輸中可以處理的位元數，頻寬越大則一次可以傳輸的資料越多
**Memory bandwidth**
記憶體頻寬，指的是單位時間內可以傳送的資料量
$$
\text{Memory bandwidth}=\text{Memory width} \times \text{frequency}
$$
:::


記憶體的設計可以分成 3 種方式 :
* One-word-wide memory organization (上圖 a.)
* 每次只能傳輸 1 個 word
* 容易發生 cache miss 而導致延遲
* Wide memory organization (上圖 b.)
* 加大位寬，可以同時傳輸更多 words
* 因為同時傳輸更多資料，所以減少 memory access 的次數
* 但同時也需要更複雜的硬體設計
* 比較偏向增加 memory wide 進而提升 bandwidth
* Interleaved memory organization (上圖 c.)
* 將 memory 分成多個 memory bank 的交錯設計，使得 CPU 可以同時 access 多個 memory bank
* 因為可以同時 access 多個 memory bank，所以不必等候其他 memory bank 完成讀取/寫入後再操作
* 比較偏向是增加 frequency 而提升 bandwidth

#### 4.1 Interleaving v.s. without interleaving
Memory 讀取資料的時間分成兩個部分 : (1) access time (2) cycle time，必須等待 cycle time 結束後才能進行下一步的動作。

以下圖的 access pattern without interleaving 為例，就算 access 已經結束，也必須等到該次的 cycle 結束時才能執行後續其他 block 的 access，因為也會浪費較多的時間再進行等待。


但如果是 access pattern with interleaving 的設計 (下圖)，因為將 memory 分成多個 bank，所以可以同時進行多個 memory 的 access，不必等待其他 bank 做完，存取提高效率。


#### 4.2 Access of DRAM
DRAM 的讀取是使用類似 array 的方式來搜索資料，以下圖為例 :


* <font color=ff0000>先以 11-bits 經過 raw decoder 後產生 row index</font>
* <font color=0000c6>再從 2048 個 row 中讀取解法出來的 row</font>
* <font color=00bb00>接著再選擇該 row 中的 column，以此來查找記憶體中的資料</font>

這樣設計的好處是為了符合 spatial locality，因為連續的記憶體位址可以讓資料有更快的讀取速度。

## 5.3 Measuring cache performance
CPU 運行計算時間主要包含兩個部分: (1) program 執行的 cycle (2) memory stall 的 cycle。第一部分包含了 cache hit 的時間，第二部分主要來自於 cache miss

簡單來說，memory stall cycle 的評估方式如下:

$$
\begin{split}
\text{Memory stall cycles} & =\frac{\text{Memory access}}{\text{Program}} \times \text{Miss rate} \times \text{Miss penalty}\\
& =\frac{\text{Instruction}}{\text{Program}} \times \frac{\text{Misses}}{\text{Instruction}} \times \text{Miss penalty}
\end{split}
$$

> 備註 : Miss penalty 代表 CPU 存取記憶體所需要的時間

##### Example
已知以下條件 :

* I-cache miss rate = 2%
* 每個 instruction 都需要 access I-cache : 100%
* D-cache miss rate = 4%
* 只有 load/store 需要 access D-cache : 36%
* Miss penalty = 100 cycles
* Base CPI = 2
* Load and store are 36% of instructions

所以，每個 instruction 的 miss cycle 為 :
* I-cache : $2\% \times 100 = 2$
* D-cache : $36\% \times 4\% \times 100 = 1.44$
> 備註 : × 100 是因為每次 miss 時都需要付出 100 個 cycle 的成本 (miss penalty)

因此，實際的 CPI 應該是

$$
\text{CPI} = 2 + 2 + 1.44 = 5.44
$$

而理想的 CPI 效能會比實際的 CPU 效能快了 $\cfrac{5.44}{2}=2.72$ 倍

### 1. Average access time
**A**verage **M**emory **A**ccess **T**ime (AMAT)，表示平均記憶體存取時間，此處的記憶體不僅僅是包含 main memory，同時也包含了 access cache 所需要的時間，具體算法如下 :

$$
\text{AMAT} = \text{hit time} + \text{miss rate} \times \text{miss penalty}
$$

##### Example
假設以下條件 :

* CPU 的 clock cycle 時長 = 1 ns
* hit time = 1 cycle
* miee penalty = 20 cycle
* I-cache miss rate = 5%

則 $\text{AMAT}=1+
5\%\times20=2$(ns)，表示每個 instruction 平均需要 2 ns 的時間完成。

簡而言之，改善 cache performance 的效能可以從以下 3 個面向著手 :
* Reduce the time to hit in the cache
* Decreasing the miss ratio
* Decreasing the miss penalty

## 5.4 Improving cache perofrmance
回顧 direct mapped 的 block placement，當 processor 需要 access 資料時，需要比對 tag 才知道 hit/miss

此處介紹另一種做 block placement 的方式，稱為 associative caches

### 1. Set associative cache
#### 1.1 Associative caches
Associative 的方式可以再細分為兩種 : (1) fully associative 與 (2) n-way set associative

(1) Fully associative
在 fully associateve 中，允許將 block 放到任意的 cache entry 之中，不像 direct mapped 會有限制。也因為這種機制，所以當 block 從 memory 移到 cache 時需要 search 每個 cache entry 看哪裡有空的位置可以放入資料，如果有 n 個 entry 就必須要比對 n 次 (comparator per entry)，成本較高。

(2) N-way set associative
有點類似 fully associative 與 direct mapped 的結合，這種方式是將 n 個 cache entry 組合成一個更大的單位 (稱為 set)，每個 set 都包含了 n 個 entry，再以類似 direct mapped 決定 block 的方式來決定 set (取 module)

$$
\text{Set address} = \text{Block number} \mod \text{#set}
$$

當決定好 set address 後， 因為每個 set 中有 n 個 entry，再將 block 放入。因為比對次數少於 fully associative，所以成本也會比較低。

##### Example
以下圖為例，假設 block address = 12，cache block = 8


* <font color="ff0000">Direct mapped</font>
* block address $= 12 \bmod 8 = 4$，表示 mapping 到 cache 中的 第 4 個 entry
* 直接找到，不用做 search
* <font color="0000c6">2-way set associative</font>
* #set $= 8 \bmod 2= 4$，表示每 2 個 entry 組成一個 set，共有 4 個 set
* set address $= 12 \bmod 4 = 0$，表示 mapping 到第 0 個 set
* 因為每個 set 有 2 個 entry，所以 search 兩次後選擇要放入哪個
* <font color="00a600">Fully associative</font>
* 8 個 entry 都要做 search 才知道要放哪裡

從上述例子可以知道 :
1. 當 n-way set associateive 中的 n = #cache entry 時，則 n-way set associateve 等價於 fully associative
2. 當 n = 1 時，n-way set associative 等價於 direct mapped

此外，在 n-way set associative 系統中，index 是用來選擇 which set，所以 set 的 size 越大 (n 越大) :arrow_right: index 越小 :arrow_right: tag bit 越大。

再以下圖為例，比較 2-way set associative 與 fully assiciative 中 hit/miss 的差別。


<font color="00a600">在 2-way set associative 中，每個 set 有 2 個 entry，所以需要比對 2 次</font>
* t = 1 時 cache miss，所以從 Mem[0] 把 block 載入至 set[0] 的 entry (有空位就放)
* t = 2 時 cache miss，所以從 Mem[8] 把 block 載入至 set[0] 的 entry (有空位就放)
* t = 3 時 cache hit，所以直接從 set[0] 的第 1 個 entry 提取資料
* t = 4 時 cache miss，所以 Mem[8] 出去，Mem[6] 進來


<font color="00a600">在 fully associative 中有 4 個 entry，所以需要比對 4 次</font>
* t = 1 時 cache miss，所以從 Mem[0] 把 block 載入 (有空位就放)
* t = 2 時 cache miss，所以從 Mem[8] 把 block 載入 (有空位就放)
* t = 3 時 cache hit，所以直接從第 1 個 entry 提取資料
* t = 4 時 cache miss，所以從 Mem[6] 把 block 載入 (有空位就放)

:::info
增加 associative 的目的在於降低 miss rate
:::

#### 1.2 A 4-way set-associative cache
一個 4-way set associative cache 的架構如下圖所示 :


* <font color="0000c6">後 2-bits 是做 bytes offset (since 1 word = 4 bytes)</font>
* <font color="00a600">中間的 8-bits 是因為總共有 256 個 index/sets</font>
* <font color="ff0000">每個 set 有 4 個 blocks</font>
* 最後由一個 4-to-1 的 MUX 做選擇

#### 1.3 Compare data available time
* 在 direct mapped 中
* cache block 在 cache hit/miss 判斷前就可以取得
* 因為 (假設) 資料本身就在 cache 中，且 cache entry 的位址與 memory addrsss 的位址是 1-1 mapping 的，不用再去做額外的 compare
* 在 n-way set associatie 中
* cache block 在 cache hit/miss 判斷後才可以取得
* (假設) 資料本身就在 cache 中，但因為 cache entry 的位址與 memory address 是 n-1 mapping，所以需要再去做額外的 compare 才能取得資料

#### 1.4 Data placement policy
不論是 n-way 或是 fully，當 cache entry 填滿時，都需要將先前的 data block 移出，才能從 memory 載入新的 data block，此時就必須要決定搬出哪一個 data block。

常見的 replacement 方法如下 :

* 對 direct mapped 來說
* 不用作選擇，因為 cache entry 與 memory address 是 1-1 mapping
* 對 n-way/fully 來說
* Random : 隨機移出
* Least Rencently Used (LRU) : 使用一個 hardware 來追蹤 access 的歷史紀錄，並替換那些長久沒有被使用的 block

### 2. Multiple level cache
Multilevel cache 指的是將多個 cache 分層，類似 memory 的 階層式設計。通常命名為 L-1 cache、L-2 cache、...

* 上層的 cache (L-1 cache)
* 越小、越快、越靠近 CPU
* 用來減少 hit time
* 下層的 cache (L-2 cache)
* 越大、越慢 (但還是比 main memory 快)、越遠離 CPU
* 用來減少 miss rate

##### Example
已知下列條件 :
* CPU base CPI = 1
* Clock rate = 4 GHz ($4 \times 10^9$ cycle/s)
* Miss rate/instruction = 2%
* Main memory access time = 100 ns ($100 \times 10^{-9}$ sec)
* Miss penalty = 100 ns / 0.25 ns = 400 (cycle)

對 single cache 來說

$$
\text{effective CPI} = 1 + 2 \% \times 400 = 9
$$

加入 L-2 cache 後條件如下 :
* Miss rate
* L-1 to L-2 : 2%
* L-2 to memory : 0.5%
* Access time
* Access L-2 : 5 ns
* Access memory : 100 ns
* Miss penalty
* Access L-2 : 4 GHz × 5 ns = 20 cycles
* Access memory : 4 GHz × 100 ns = 400 cycles

最後的 CPI 需包含 : base CPI + 存取 L-2 的時間 (L-1 miss rate) + 存取 memory 的時間 (L-2 miss rate)

$$
\text{effective CPI} = 1 + 2\% \times 20 + 0.5\% \times 400 = 3.4
$$

速度與 single cache 相比快了 $\cfrac{9}{3.4}=2.6$ 倍

## 5.5 Virtual memory
:::info
**Concept of Multi-Progamming**
* 一開始是沒有 disk 的 single program 系統，一次只能執行一支程式
* 為了節省時間加快效率，所以發展出 multi-programming 的概念，希望可以同時執行多支程式
* 但因為每個 program 的 user address 都不同，大小也不同，如果一次放入整支程式的話容量太大
* 因此只要放入需要使用的部分到 memory 就好
* 這個「需要使用的部分」比 block 更大，速度更慢，所以稱為 page
* 也因為搬移的資料量更大，所以使用 software (OS) 來操作
:::

### 1. Basics
回顧記憶體的階層式設計，目前要討論的是下圖紅圈處


Programs 在執行的時候是共享 main memory 的。此外，program 是執行在 name space (virtual address space) 之中，這個虛擬空間與 memory space (physical address space) 是不一樣的。

每支程式會有一個私人 (private) 的 virtual address space 用來儲存自己的 code 與 data，這個空間是從 address 0 開始，且只有該程式本身可以做存取。Virtual memory 可以讓程式在 memory space 的任意位址執行，但是需透過 translations 將 virtual address 轉換成 physical address。


每支程式所佔有的 (虛擬)記憶體空間可能非常大，甚至大於 physical memory，但因為只要將需要用到的部分 access 到 main memory 就好，所以不影響。

Memory 與 disk 的概念如同 cache 與 memory 類似，但主要是依靠 OS 來做管理 (再加一點 hardware)。相關的名稱如下表 :

| In cache & memory | In memory & disk |
| :-: | :-: |
| block | page/frame |
| cache miss | page fault |

在 disk 中，data block 的概念被稱為 page，但在 memory 中 data block 被稱為 frame，兩者的大小相同，且會透過 translation 做 mapping。


### 2. Issues in virtual memory
在 virtual memory 中，與 cache & memory 一樣要討論 4 個問題

* Size of data blocks/page
* 載入資料大，可以減少存取次數
* 但同時也會載入太多不必要的資訊
* Placement policy
* 因為 memory space 是有限的，所以將資料從 disk 載入至 memory 時要放在哪個位址
* Replacement policy
* 當 memory space 額滿時，要替換哪個空間給新的資料使用
* 何時才要將資料從 disk 載入至 memory
* 通常是發生 miss/page fault 時

#### 2.1 Block size and placement policy
因為 page size >> block size，所以當發生 page fault 時也會有更大的 penalty，通常需要 millions of cycle 來處理。常見的 page size 是 4 KB。因此，減少 page fault 的發生是非常重要的事情。

在 memory & disk 中的 placement policy 是使用 fully associative，原因如下 :

* 更靈活的設計，可以放在 physical space 中的任意位址而不受限制，降低 replcement 的機率
* Virtual space 需要的空間比較大，使用 n-way 切割的話難以管理

然而，fully associative 會遇到 search 的問題，我們不可能一個一個的找位址，所以在 memory 中使用了 page table 來尋找 page。Page table 其實就是查表的概念，用來尋找第幾個 page 要放在第幾個 frame 的對應關係。以 4K 的 page size 為例 :


* 因為 page size = 4 K = 4096 bytes，所以需要 12-bits 來在 page 內做 search，剩餘的是 virtual page number。Virtual page number 經過 translation 轉換成 physical frame number 後才是真的位址。

#### 2.2 Page tables
Page table 其實就是一個類似 array 的結構，存放在 main memory 之中，這個 array 由 Page Table Entry (PTE) 組成，每個 entry 都存放 virtual page number。此外，在 CPU 中有一個 page table register 指向 memory 中 page table 的位址。

* 如果 page 在 memory (hit)
* PTE 儲存了 physical page number
* 也儲存了其他相關的 status bit (Ex : dirty bit)
* 如果 page 不在 memory 中 (miss/page fault)
* 從 disk 將 page 載入至 memory 中


:::info
在 page table mapping 的時候，會衍生兩個問題 :

* 做 address location 時會需要幾次的 memory reference ? 2 次
* 第一次是 access memory 中的 page table，用來找 physical address
* 第二次是用找到的 physical address 來 access memory 找 frame
* 但 2 次的 access 太多了
* 每個 page 都需要一個 page entry，導致 page table 可能非常大

這兩個問題日後會有討論
:::

##### Example

#### 2.3 Page fault
如前所述，當發生 page fault 時，表示該 page 目前不在 memory 之中，而處理 page fault 也必須付出即大的代價，通常需要 million of cycles。另外， hardware 可以偵測 page fault，但不能修正 (remedy) 這個問題，只有 software 可以能夠處理。Software (OS) 的處理流程如下 :

* 首先會由 hardware 發出一個訊號 (trap) 告訴 OS 發生 page fault，接著由 OS 執行下述動作
* 選擇一個 page 丟棄 (if full)，通常會將要丟棄的 page 寫入 disk
* 從 disk 載入 page
* 更新 page table
* 重新執行 program
* OS 要如何從 disk 中尋找特定的 page ?
* OS 會在 disk 中創建一個空間 (called swap space)，把不常用的 page 移動到這個空間中
* 使用一個 data structure 來紀錄 page 在 disk 中的位址，在需要時能夠快速找到
* 使用另一個 data structure 來追蹤 physical page 被哪些 virtual address 使用，用來作為 replacement 的依據

#### 2.4 Page replacement and write
為了降低 page fault 的比例，一般會使用 LRU 的方式做替換，也就是將太久沒用到的 page 搬走，但要怎麼紀錄 page 有沒有被使用過呢 ?

* 使用一個 reference bit (或稱 use bit) 來紀錄 page 有沒有被存取
* 初始狀態為 0，如果 page 有被 access 就設為 1
* 一段時間後，會再進行初始化將 use bit 設為 0
* 這個 use bit 儲存在 PTE 之中

也因為 page fault 有很大的 penalty，所以在寫入策略上會使用 write-back (不用每次更新 disk) 的方式，當 page 被寫入時，同樣會設置一個儲存在 PTE 的 dirty bit。

### 3. Handling huge page table
接下來討論前述所說 page table 過大的問題。以 32-bits 的 virtual address 為例

* Virtual space 大小為 $2^{32}$
* 假設 page size 為 4 KB = $2^{12}$ bytes
* 每個 page table entry 可儲存的大小為 = 4 bytes/entry

因此，virtual space 總共可以儲存 $\cfrac{2^{32}}{2^{12}}=2^{20}$ 個 pages，又因為每個 page table entry 可以儲存 4 bytes 大小的內容，所以整個 page table 的大小為

$$
4 \ \ \text{bytes}\times 2^{20} = 4 \ \ \text{MB}
$$

解決 page table 過大的方法有以下幾種 :

* Use bounds register to limit table size
* Let pages to grow in both directions
* Use hashing
* Multiple level of page tables
* Pages page table

### 4. TLB
接下來討論前述所說 memory access 次數太多的問題。任何跟 memory 有關的操作基本上都必須經過兩次的 access，一次是存取 PTE，第二次是存取實際的 memory address。

但與 memory 的基本設計原則相同，既然是要存取記憶體位址，所以 page tables 也會符合 spatial locality 的性質，並且可以透過這個性質來加快存取的速度。

#### 4.1 Fast translation using a TLB
因為 page table 也具有 spatial locality 的性質，所以我們可以在 CPU 之中設計一個額外的 cache 作為 buffer 用來儲存最近使用過的 PTE，這個額外的 cache buffer 稱為 **T**ranslation **L**ook-aside **B**uffer (TLB)。


如上圖所示，TLB 會儲存最近常用的 physical，當 CPU 需要做 address translation 時會優先從 TLB 中尋找。當 <font color=0000cc> TLB miss 時再從 page table 查找。 </font>

#### 4.2 TLB hit
* TLB hit on read : 直接從 TLB 讀取 physical address
* TLB hit on write : 以 write-back 的方式操作，當 TLB 中的 page 被替換 (replacement) 時，再將新的資訊寫回 page table

#### 4.3 TLB miss
分兩種狀況討論 TLB miss 的處理機制 :

* 如果 page 在 memory 之中
* 直接從 memory 中載入 page table entry 並重新執行
* 可以透過 HW/SW 操作
* 如果 page 不在 memory 之中 (page fault)
* OS 會將 page 從 disk 載入至 memory 並更新 page table
* 再重新執行錯誤的指令

### 5. TLB and cache
#### 5.1 Making address translation practical
在 virtual memory 的概念中，memory 之於 disk 的地位就相當於 cache 之於 memory 一樣，搭配 TLB 的概念後 data flow 架構如下圖，其中 t 表示執行時的時間比


1. CPU 發出一個 virtual address 來存取資料，優先查詢 TLB 內部有沒有欲存取的 virtual address
2. 依照 TLB 的查詢結果分兩種情況
2.1 Hit : TLB 中有對應 virtual address 的 physical address
2.2 Miss : TLB 中沒有對應的 virtual address，因此透過 page table 做 translation 來找到對應的 physical address
3. 當找到 physical address 後，再透過 cache 來存取資料，此時依照 access 結果可以再分成兩種情況
3.1 Cache hit : cache entry 有正確的 data block，直接提供 CPU 使用
3.2 Cache miss : cache entry 沒有正確的 data block，往下一層 memory 做存取
4. 在 memory 存取時，把 data block 載入至 cache 與 CPU

#### 5.2 Integrating TLB and cache
單純看 TLB 與 cache 的關係如下圖所示 :


<font color=0000c6>一個 virtual address 會透過 TLB 將 virtual address 做 translation 後得到 physical address (= physical page number + page offset)。</font>

<font color=ff0000>Physical address 再透過 cache 的解析 (=tag + index + bytes offset) 得到要存取的資料。</font>

## 5.6 A common framework for memory hierarchy
本章節的重點整理，暫略

## 5.7 Using a finite state machine to control a simple cache

:::info
**Finite State Machine (FSM，有限狀態機)**
有限狀態機指的不是機器，而是一種數學模型，用來描述有限個狀態以及這些狀態之間轉移動作的行為。


FSM 的模型包含了 4 種元素，以上圖的開關門為例
* State (狀態) : 一個 FSM 至少要包含兩種狀態，例如上圖的 opened (門開著) 與 closed (門關著)
* Initial state (初始狀態) : 系統重置或啟動後的起始狀態
* Transition condition (轉移條件) : 指的是觸發狀態變化的條件，例如上圖的 open (開門) 與 close (關門)
* Action (動作) : 指的是轉移條件發生後要執行的動作，可再系分為 4 種
* Entry action (進入動作) : 進入這個狀態時會執行什麼動作，如上圖的 open door (開門) 或 close door (關門)
* Exit action (退出動作) : 退出這個狀態時會執行什麼動作
* 輸入動作 : 處於某狀態時，收到事件會執行什麼動作 (但不轉變狀態)
* 轉移動作 : 轉移狀態過程中會執行什麼動作
* Transition : 從一個狀態轉變為另一個狀態，如上圖的 opened 變為 closed

以紅綠燈號的轉變舉例，假設當前狀態是紅燈
* 進入動作 : 燈號顯示為紅色，並開始紅色倒數
* 退出動作 : 紅色倒計時為 0
* 輸入動作：收到闖紅燈事件發出警告
* 轉移動作 : 紅燈轉為綠燈的過程中，對用路人發出提醒
:::

以 FSM 描述 cache controlled 的方式如下圖


## 5.8 Parallelism and memory hierarchies: cache coherence

### 1. Cache coherence problem
假設有兩個 CPU 共享一個 physical address space，並使用 write-through 的方式。由下圖會發現到，在 t = 3 時，CPU B 的 cache 的值並沒有同步更新，如果後續在兩顆 CPU 中有對 x 的操作就會有不同結果


以 snooping 的解決方法為例

<font color=ff0000>當 CPU A 更改了 X 的內容時，會同時發出一個 invalidate message 的訊號在 bus 上，告訴其他 CPU 這個值已經更動過，使得 CPU B 中對於 X 的 cache 被標記為 invalidate (無效)</font>

<font color=00a600>接著在 CPU B 讀取 X 的內容時，因為是無效的所以發生 cache miss，此時再從 memory 或 CPU A 讀取資正確的資料</font>