# 計算機組織與結構 L6 容量大且速度快的記憶體

## 區域性原則

- 利用不同大小及速度的 Memory 組成 **Hierarchy Memory** 來達到**容量大**且**速度快**的要求
- 由於 **Hard Disk與 Memory 之間的存取速度差數百萬倍**，因此要盡量減少 Memory Swap 的次數</br>→ Memory 要設計大一點

- CPU 存取 Memory 地址時需要 **Decoder**，為了降低 Decoder 電路複雜度，以加速解碼的速度</br>→ Memory 要設計小一點

> **離 CPU 最近的 Memory 決定 Hierarchy Memory 的速度**
> **離 CPU 最遠的 Memory 決定 Hierarchy Memory 的大小**

- Principle of **Locality**
- **Temporal Locality :** 例如 Loop
- **Spatial Locality :** 例如 Array

- 不同**記憶體技術 :**
- **Dynamic Random Access Memory (DRAM) :**
- **Main Memory** 以 **DRAM** 組成
- 一位元資料用**電荷**存在**電容器**中
- **需要 Refresh (一直充電)**
- 所用到的電路器材體積小

- **Static Random Access Memory (SRAM) :**
- **Cache** 以 **SRAM** 組成
- 較靠近 **Processor**
- 一位元資料存在**一對反向閘之間**
- 所用到的電路器材體積大

- **Flash**
- **Magnetic Disk**
</br>
> 

> **存取資料的速度**
> **SRAM > DRAM > Flash > Magnetic Disk**

> **價格多寡**
> **SRAM > DRAM > Flash > Magnetic Disk**

## 記憶體階層

- 記憶體階層符合
- **Temporal Locality :** 將最近存取過的資料放在距離 Processor 近的地方
- **Spatial Locality :** 從較低層 Memory 移動連續字組到較高層的 Memory

- **Cache System** 和 **Virtual Memory**

- **Cache System :**
- 存在在 **Cache 和 Memory** 之間
- 最小資料傳輸單位叫 **Block (Line)**，一個 Block 通常就幾個 Word 而已
- 將 **Memory Block Address 轉為 Cache Block Address**
- 一些術語 :
- **Cache Hit :** Processor 可以在 Cache 中找到資料
- **Cache Miss :** Processor 在 Cache 中找不到資料，要到 Memory 中找
- **Hit Rate (= Hit Ratio) :** 在 Cache 找到資料的比例
- **Miss Rate :** 在 Cache 中找不到資料的比例
- **Miss Penalty :** 將 Memory 中所需的 Block 搬進 Cache，並傳給 Processor 所需的時間

- **Virtual Memory :**
- 存在在 **Memory 和 Hard Disk** 之間
- 最小資料傳輸單位叫 **Page**，一個 Page 有 4KB 起跳
- 將 **Virtual Page Number 轉為 Physical Page Number**
- 一些術語 :
- **Page Hit :** Processor 可以在 Memory 中找到資料
- **Page Fault :** Processor 在 Memory 中找不到資料，要到 Hard Disk 中找

## Cache System

- Cache **結構**可分為
- **Direct Mapped :**
- 按照字組在記憶體的位置安排其在快取中的位置
- 規定一個一個記憶體區塊只能放到快取的一個位置
- 為 **Set Associative 的極端值**
- **Block 置換方式 :** 會因為受到衝突被替換掉
- 
- **Set Associative :**
- 將快取分成數個集合，每個集合包含固定數量的 Block
- 只要集合還有空閒的區塊，記憶體區塊就可以使用
- **增加 Associativity 會降低 Miss Rate，但會增加 Hit Time**
- **Block 置換方式 :** **Random** 或 **Least Recently Used (= LRU)**
- 

- **Fully Associative :**
- 一個記憶體區塊可以放在快取中任何位置
- 比較器採平行的比較
- 為 **Set Associative 的極端值**
- **Block 置換方式 :** **Random** 或 **Least Recently Used (= LRU)**

- **Cache Address**
- 
- 
- ```[ Tag | Index | Block Offset | Byte Offset ]```
- **Tag：** 用來比對**是否存在 Cache 中**的索引
- **Index (= Entries) ：** 用來**存取某個 Set**，所以由 Way 和 Cache Block Entry 數目決定
- **Direct Mapped** : 有 Cache Block Entry 這麼多個 Set
- **Fully Associative :** 只有 1 個 Set (Index Bit 為零)
- **N-way Associative :** Set 數量為 Cache Block Entry / N
- **Block Offset ：** 用來存取 Cache Line 中的某個 Word (指**第幾個 Word**)
- **Byte Offset ：** 用來存取一個 Word 裡面的某個 Byte，所以所需的 Bit 數會是**一個 Word 可以存的 Byte 數**

- 例如此圖 : 
- 一個 Block 有 $2^2\ Words$ 的資料量
- 一個 Block 有 $2^4\ Bytes$ 的資料量
- 此 Cache 有 $2^{12}\ Blocks$
- 此 Cache 的資料量可存 $2^{12} * 2^{4} B$
- Memory 中有 $2^{16} * 2^{12}\ 個\ Blocks\ 的\ Address$

- **Block Size 大小**
> **Miss Rate** 根據 Block Size **先降後升**

**原因** :
- **Miss Rate 降:** **Spatial Locality** 增加，**Miss Rate** 因此降低
- **Miss Rate 升:** **Cache 固定大小**時，**Block 數量降低**，Block 容易被**替換**，**Miss Rate** 升高

## Cache 基本概念

- 如何減少 **Miss Penalty**
- **Early Restart :**
- 當區塊**所需要的字組送到就立刻開始繼續執行**，不用等到整個區塊都送完才開始
- 等待的時間一所需字組為第幾個字組而定
- **Requested Word First (= Critical Word First) :**
- 需要的字組先送到快取，剩餘字組再慢慢送
- 等待時間為傳送一個字組的時間
> **Requested Word First 比 Early Restart 快**

- 在 **Multi Cycle Machine** 或 **Pipeline** 中處理 **Cache Miss** 的步驟 :
1. 將造成 Cache Miss 的指令位址丟給記憶體
2. 告知記憶體讀取並等待
3. 將從記憶體得到的資料寫進快取，並將 Valid Bit 設為 1
4. 重新擷取送到記憶體那個執行造成 Cache Miss 的指令

- **Cache Read & Write**
- **Cache Read**
- **Read Hit**
- **Read Miss**
- **Read Allocate :** 預設為這個，Cache 到 Memory 搬整個 Block 到 Cache
- **Read Through :** CPU 到 Memory 直接取要用的 Block

- **Cache Write**
- **Write Hit**
- **Write Through :** CPU 一寫，Cache 和 Memory 都要一起改
- **Write Back :** 先只改 Cache，等到在 Cache 中的 Block 要被替換，才寫進 Memory
- **Write Miss**
- **Write Allocate :** Cache 到 Memory 搬整個 Block 到 Cache
- **Write Around (No Write Allocate) :** CPU 繞過 Cache 直接到 Memory 寫資料
</br>
> **Write Through 通常和 Write Around 搭配**
> **Write Back 通常和 Write Allocate 搭配**

- **Split Cache & Combined Cache**
- **Split Cache :**
- **Instruction Cache 和 Data Cache 分離**
- 因為**可同時抓 Instruction 和 Data**，所以**BandWidth 較大**
- **Hit Rate 較低**

- **Combined Cache :**
- **Instruction 和 Data Cache 合併**
- 不能同時抓取 Instruction 和 Data，所以 **Bandwidth 較小**
- **Hit Rate 較高**


- **支援快取的記憶體系統**
- 利用**增加 Memory 到 Cache 的 Bandwidth** 減少 Miss Penalty 的方法
- **One-word-wide Memory Organization**
- **Bus 的 Bandwidth 為 1 Word**

- **Wide Memory Organization**
- **增大 Memory 和 Bus 的 Bandwidth**

- **Interleaved Memory Organization**
- **增大 Memory 的 Bandwidth**
- Main Memory 用 **Bank** 組成，每個 Bank 為一字組寬

- 利用**加速 Data 從 Memory 到 Cache** 減少 Miss Penalty
> 利用 **DRAM** 的 **Page Mode** 特性 : </br>在邏輯上是矩形陣列，存取時間分成 **Row Access** 和 **Cloumn Access**。</br>當在讀同一個 Block 時，**Row Address 幾乎不變**，而 DRAM 會把 Row 讀取的所有資料放到 Buffer 上，因此**只需要解碼 Column Address，移動 I/O Gate Mask 選擇要存取哪個 Word** 即可
> 

- **Extended Data Out Random Access Memory (EDO = EDO RAM) :** </br>
- 比較古老的技術
- 和 **SDRAM 的差別是 Row Decode 後一次只能放 1 個 Page 到 Buffer**
- 

- **Synchornous Dynamic Random Access Memory (SDRAM) :** </br>
- 提供資料的 **Burst Access (用 Clock Signal 控制)**
- 優勢是 **用 Clock 去除同步需求** 及 **在 Burst Access 時不需要再提供位址**
- 

</br>
> 而此前的 DRAM 都使用異步方式工作，由於沒有與系統的外頻同步，在存取數據時，系統必須等待若干時序才能接受和送出數據

- **Double Data Rate Synchornous Dynamic Random Access Memory (= DDR = DDR SDRAM) :** </br>
- 資料在 **Clock 的上升和下降邊緣**都可以傳輸資料，在同樣的 Clock Rate 和 Data Bandwidth 下得到**兩倍頻寬**
- 缺點是**要讀就不能寫，要寫就不能讀**
- 

- **Quad Data Rate Synchornous Dynamic Random Access Memory (= QDR = QDR SDRAM) :**</br>
- 將 DDR 改成**可讀寫同時**，變成 **DDR 的兩倍頻寬**

## 利用 Multilevel Cache 減少 Miss Penalty

- 大部分 **Cache 都放在 Processor 裡面**

- 如果利用 **2 層 Cache** :
- **第一層快取 (= 主要快取) :** 注重**減少 Hit Time**，通常用 **Split Cache** ( Bandwidth 寬，所以快)
- **第二層快取 (= 次要快取) :** 注重**減少 Miss Rate**，通常用 **Combined Cache**

- **Miss Rate 又分 :**
- **Global Miss Rate (= GMR)**
- **Local Miss Rate (= LMR)**

- **Average Memory Access Time (= AMAT) :** 在 Multilevel Cache 下，CPU 存取記憶體一次所需的平均時間
</br>$AMAT = Time\ For\ A\ Hit + \sum{(M_i*P_i)}$

## Cache 效能量測

- **影響 Cache 效能**兩大因素 :
- **Miss Rate**
- 可用 **Set Associative** 解決
- **Miss Penalty**
- 可用 **Multilevel Cache** 解決

- 計算 **CPI :**
- **Split Cache :**</br>
$CPI_{effective}=CPI_{base} + Memory\ Stall\ Per\ Instruction$
</br>$\qquad \qquad\ \ \ \ = CPI_{base} + Icache\ Stall\ Per\ Instruction$</br>
$\qquad\ \qquad \qquad \qquad \quad\ \ +Dcache\ Stall\ Per\ Instruction$
</br>$\qquad \qquad\ \ \ \ = CPI_{base} + Icache\ Access\ Per\ Instruction * Miss\ Rate*Miss\ Penalty$</br> $\qquad\ \qquad \qquad \qquad \quad\ \ +Dcache\ Access\ Per\ Instruction * Miss\ Rate*Miss\ Penalty$
- **Combined Cache :**</br>
$CPI_{effective}=CPI_{base} + Memory\ Stall\ Per\ Instruction$
</br>$\qquad \qquad\ \ \ \ = CPI_{base} + Cache\ Access\ Per\ Instruction*Miss\ Rate*Miss\ Penalty$</br>

## Virtual Memory

- **易混淆名詞 :**
- **Physical Address :**
- 存取 Physical Memory (= Main Memory) 內資料的 Address
- 長度由 **Memory** 大小決定
- **Virtual Address :**
- 由 Processor 產生，讓程式以為自己獨享整個 Memory 的假象的 Address
- 長度由 **ISA** 決定
- **Page Table :**
- Vurtual Page Number 過多，要找的話效率太差，就用 Page Table 查
- 放在 Main Memory 中
- **有幾個 Virtual Page 就有幾個 Page Table Entry**
- 
- 

- **Page Table Register (= PTR):** 在 Main Memory 中，指向現在 Active 的程式的 Page Table 起始位址的暫存器
- **Process :** 程式進行到一半要被打斷，就需要保存現在執行到的 **Page Table Register**、**Program Counter**、**General Purpose Register** 的狀態

- **Approximate LRU :** 因為如果要執行真正的 LRU，有用到的就要定期加 1，但有可能會因為加到最後數字太大而 Overflow，造成誤刪，所以需要定期清除為 0，若要刪 Page Table 的資料時，只需要檢查不是 0，就代表他近期被用過
- **Victim Page :** 要被換掉的 Page

- **Virtual Memory :** 一種 Main Memory 將 Hard Disk 當作儲存體的**技術**，由 **CPU** 和 **OS** 一起管理
> 為了讓程式有**自己在用全部、完整的記憶體＆擁有連續的記憶體位址**的錯覺，所以 CPU 輸出的 Address 有 $n\ Bits$，程式可以調到的資料量就有 $2^{n}\ Bytes$

</br>

- **設計動機 :**
- **早期一次只能跑一個程式， Virtual Memory 允許多個程式有效率且安全的分享記憶體**
- **早期 Memory 的容量小於程式大小就無法跑程式，Virtual Memory 消除因為 Main Memory 過小而對程式造成的限制**

- **作法 :**
1. 開啟執行檔
2. **OS 把程式複製到 Hard Disk 中的 Swap Space**，複製後的程式稱為 **Virtual Space (= User Program Space)**

3. 當程式使用到的空間比記憶體大時，**OS 會先把部分資料複製到 Physical Memory (= Main Memory)，並建立 Page Table**，以 Physical Page Number 來記錄已經載入 Physical Memory 的資料的記憶體位址或是還在 Hard Disk 的資料的位址。</br>Page Table 的 Entry 數量等於程式執行佔用的 Virtual Space 中 Virtiual Page 的數量，此外會加入 Memory Management Bits
</br>
> **Memory Management Bits :**
> - **Valid Bit**
> - **Reference Bit (= Use Bit) :** 用來達成**近似 LRU** 的
> - **Dirty Bit**

</br>

4. 當CPU要存取某一資料時，會發出 Virtual (Byte) Address 的要求指令，直接**指定 Virtual Space 的位址**
</br>
> **Virtual Address** 分為2個部分
> - **Virtual Page Number :** 對應到 Virtual Space 的哪個 Page
> - **Page Offset :** 指出 Page 中哪個 Byte
> - 題目說 $n\ Page$ 就代表 Page Offset 有 $\log_2n\ Bits$
> - Page Offset 在 Virtual Address 轉為 Physical Address 時不會被動到

5. 由於 Virtual Address 不是 Physical addess，不能直接存取 Memory，所以需要經過適當轉換。從 Virtual Address 擷取出 **Virtual Page Number**，加上 Page Table Register，取得相應的 **Physical Page Number**
</br>
> **PTR :** 一個 Pointer，指向 Active 程式的 Page Table 在 Memory 的起始位址

6. 有了 Physical Page Number，再結合 Page Offset，組合出 **Physical Address**

7. 以 Physical Address **存取 Physical Memory** (= Main Memory)取得資料

> 是藉由**硬體 (Page Table Register)** 和 **軟體 (Page Table)** 轉譯的過程

- **與 Cache 的比較**
- 

- **寫入處理 :** 因為不可能用 Write Through 同步改 Hard Disk 這種浪費時間的方法，所以只剩 **Write Back (= Copy Back)**

- 因為 Page Table 太佔記憶體空間了，所以要**降低所需要的總儲存空間**和**最小化 Page Table 所占用的主記憶體**，有五種方法 :
- **一個 Limit Register :**
- 用 Limit Register 限制 Page Table 的大小，如果程式還需要更多空間，才再加入所需的 Entry 到 Page Table 中
- **兩個 Limit Register :**
- 在 Stack 和 Heap 的放兩份 Page Table(一個往下長，一個往上長)， 分別用分開的 Limit Register 存放 Page Table 的初始限制值

- **Inverted Page Table :**
- 原本是 Page Table Entry 數是根據 Virtual Page Numer 多寡決定，現在換成由 Physical Page Number 決定

- **Multilevel Page Table :**
- 用時間換取空間，只需要存目前指向 Page Table 的小區塊到 Memory 就可，其餘 Page Table 放在 Hard Disk 中，因為一個 Page 就可以用很久
- 

- **允許 Page Table 也被 Page**

## Translation-lookaside Buffer (TLB)

- **TLB :**
- **設置原因 :** 每次 Processor 放出 Virtual Address 後，都要跑到記憶題存取兩次，有了 TLB，第一次就不用跑到 Memory 裡了
- 第一次到 Memory 的 Page Table 將 Virtual Address 轉換為 Physical Address
- 第二次到 Memory 利用剛剛得到的 Physical Address 存取資料

> Virtual Address 到 TLB 只需要看 Virtual Page Number 就好，將 Virtual Page Number 拆成 Tag 和 Index

</br>

- **TLB Miss 的原因 :**
- 有可能其實要的 Page 在 Page Table 中，只是沒有更新到 Page Table 中而已
- 有可能要的 Page 根本不在 Page Table 中，而是在 Hard Disk 中，代表真的出現 Page Fault 了。此時 OS 就要到 Hard Disk 拿想要的 Page 到 Memory，TLB 再到 Memory 中看著 Page Table 更新此 Page 的相關資料，順便 Cache 也到 Memory 更新此 Page 要用到的 Block

- 因為一個 Page 可以用很久，所以 **TLB** 不用太大，就採用 **Fully Associative** 的方式，既**降低 Miss Rate**，**成本又不會太高**
- **TLB、Cache、Virtual Memory 整合 :**
- 
- 
- 

- **統整的 Hit & Miss**

## Physical Address Cache & Virtual Address Cache & Virtual Index, Physically Tagged

- **Physical Address Cache :**
- 
- 在 **Physical Address Cache** 中，輸入 Cache 的 Address 用的是 **Physically Indexed**、**Physically Tagged**
- 要先將 Virtual Address 轉為 Physical Address 才能給 Cache 使用
- **缺點 : 轉成 Physical Address 的過程太久**

- **Virtual Addressed Cache :**
- 
- 在 **Virtual Addressed Cache** 中，輸入 Cache 的 Address 用的是 **Virtually Indexed**、**Virtually Tagged**
- **缺點 : Aliasing :**
- Compiler 在 Compile 時，會把兩個程式共用資料的訊息告訴 OS，所以當 OS 把兩程式的 Virtual Space 複製到 Physical Memory 時，只會複製一份共用資料。而在兩個程式執行時，因為是使用 Virtual Address 當作 Cache 的輸入，兩個程式對於同一份資料安排的 Virtual Address 又不可能一樣，所以在記憶體中的共用資料會被複製到 Cache 其中兩個不同的地方，導致一個程式改了數據，另一程式卻不知情，無法資料同步
- 

- **Virtual Index, Physically Tagged**
- 
- 在 **Virtual Index, Physically Tagged** 中，輸入 Cache 的 Address 用的是 **Virtually Index**、**Physically Tagged**
- 通過**軟硬體配合**解決 Physical Address Cache & Virtual Address Cache 的問題
- 在這裡，Cache 和 TLB 是平行存取的，用 Physically Tag 和 TLB 比較，看是不是 Hit
- Cache 還是會複製成兩份，但只有 Tag 是 Physically 的那份才有效

- **比較 :**
- 

## Virtual Memory 的保護機制

- **Virtual Memory 的保護機制 :**
- **起因 :** Virtual Memory 允許單一主機的 Main Memory 供眾多程式分享，但也要確保在分享時的安全
- **硬體**要讓 OS 可以介入保護，就要**提供** :
- **支援兩種模式**以區別執行的是使用者的程序還是作業系統 :
- **Supervisor Mode (= Kernel Mode) :** </br> 是 OS 的程序(= Supervisor Process = Kernel Process = Executive Process)
- **User Mode**

- **有些 Processor 的狀態只有 OS 的程序才能動**，如 :
- 區分 Processor 是在哪種模式下的 **User/Supervisor Mode Bit**
- **PTR**
- **TLB**
- **讓 User Mode 和 Kernel Mode 能互相跳切**，方法為 :
- **User Mode 變 Kernel Mode :** </br>用 **System Call**
- **Kernel Mode 變 User Mode :** </br>用 **Return From Exception (= ERET)** 跳到 **EPC (= Exception Program Counter)** 的 Address

> 第五章有提到 EPC

## 3C

- **Miss 可以被分為三種原因 :**
- **Compulsary Miss (= Cold-start Miss) :**
- 第一次存取時，因為前面都沒有存取過，所以當然會發生 Miss
- 解決方法 :
- **利用 Spatial Locality，將 Block Size 增大**，但可能會造成 Miss Penalty 增加(因為一次要搬更多)
- **利用 Prefetching**，預先抓後面 1 個 Block (Stride 決定跳幾抓)
- **Sequential (Stride = 1)** : 抓後面第 1 個
- **Stride** : 抓後面第 Stride 個
- **Capacity Miss :**
- Cache 記憶體容量不足以包含所有程式記憶體區塊
- **不會發生在 Direct Mapped 和 N-way Associative**
- 解決方法 : Cache 容量增大

- **Coflict Miss (= Collision Miss) :**
- 許多 Block 映射到 同一個 Block 或 Set 時發生的 Miss
- **不會發生在 Fully Associative**
- 解決方法 : 增加 Associativity

- **各種解決方法可能帶來的問題**
- 

- **Non-blocking Cache :** 遇到 Cache Miss 不會讓 Processor 停下，反而讓 Processor 繼續存取資料
- 通常存在在 **Out-of Order Execution 的 Superscalar** 中
- 用兩種實作來**隱藏 Miss Penalty**
- **Hit Under Miss :** 在 Cache Miss 後允許另一個 Cache Hit，**用其他工作隱藏 Miss**
- **Miss Under Miss :** 在 Cache Miss 後允許另一個 Cache Miss，**重疊 Miss**
</br>
> Out-of Order Execution 在第五章提到過

## Virtual Machine

- **Virtual Machine :**
- 讓**多個 OS 共享硬體資源**的同時，造出**讓 OS 覺得自己獨享硬體資源的假象**
- **Virtual Machine Monitor (= VMM = Hypervisor) :**
- 管理並支援 VM 們
- 利用 **Virtualization**
- **Time Sharing :** 切 Cycle Time，輪流讓 OS 使用
- **Partitioning :** 將 Main Memory 拆成數個片段，分給各個 OS，之後再利用 Virtual Memory 技術，讓 OS 誤以為有更大的記憶體空間
- **Emulation :** 改變 ROM 的程式，讓硬體做原本不能做的事
- VMM 是 **Guest Software 的軟體介面，要將所有 Guest Software 彼此隔離**，並且做下面兩件事。所以代表 **VMM 要是 Kernel Mode，Guest Software 要是 User Mode**
- **讓 Guest Software 以為自己動的是真實硬體** (實際上是 Virtual Memory 技術為他擴建的假空間)
- **Guest Software 不可以直接配置硬體的資源**
- 

- **好處 :**
- **安全性、隔離性佳**
- **一台可以跑多個 OS，不需要額外買電腦**
- **程式執行不限於 OS，需要的直接下載程式所需的 OS 就好**