# 計算機結構_Memory Hierarchy Design
###### tags: `計算機結構`
> 通常主記憶體會小於Megabyte且不在Disk儲存
> 結構如下圖，資料在前三個傳遞稱為Block，在MEM與IO間傳遞稱為page

\

### Locality
- Temporal locality:
-> It’s likely to need this word again in the near future
- Spatial locality:
-> There is high probability that the other data in the block will be needed soon

\

### Memory四大技巧
#### Block placement
> 看block應該放在哪裡
- Direct mapped (對號座) : 取餘數作為index
- Fully associative (自由座) : 任意位置都可以放置
- Set associative (只可選車廂) : 取Set數量的餘數


#### Block identification
> 搜尋block的方法
>
> Offset : word address
> Index : 找在cache的何處(用3個bits來表示，cache容量)
> Tag : (我不知道放進來的是4,12,20…，換成二進制為100,1100,10100…..，所以tag為扣掉00的值，且00可以做為index)

#### Block replacement
> 衝突發生時，Block的取代方式
- Random
- LRU
- FIFO

#### Write strategy
> 寫入記憶體的方式
- 兩種方式
- Write through -> 修改cache裡面的值惠怡並修改MEM裡面對應的Block內的值
- Write back -> 將要修改的值標記為**Dirty Block**，在下次Block要被取代時才寫回MEM

- 會用到
- Dirty bit
- Write stall
- Write buffer

- 若遇到Write miss可以選擇
- Write allocate -> 有想要寫入MEM得先放到cache裡面修改並標記為Dirty Block
- No-write allocate -> 直接將寫入訊號傳給MEM，直接修改

- Write miss的種類
- Compulsory misses -> 初始化時發生(透過加大Block size降低)
- Capacity misses -> fully associative時發生(透過加大cache size降低)
- Conflict misses -> 從set數高映射到較低set數的cache時發生(透過加大associattivity降低)

\

### Cache Performane
$Miss\ rate=\dfrac{指令缺失數}{總指令數}=$在特定次數的記憶體存取中發生快取錯誤的機率
$Average\ memory\ access\ time = Hit\ time + Miss\
rate \times Miss\ penalty$

\

### Performace公式統整
> 

\

### Cache效能提升/優化
> reference:[https://tobygao.github.io/Learning-Lounge/2018/03/03/ca-2-mem-design.html](https://)

- Average memory access time(AMAT) = Hit time + Miss rate × Miss penalty
- 提升cache的四大種類
1. Reducing the miss penalty
- Multilevel caches
- 優點：使cache跟DRAM一樣快，同時加大cache空間
- 通常第一層很小，重點在至少需要跟DRAM速度一致；第二層需要大到足夠所有資料進入MEM
- $AMAT=Hit\ time_1\ +Miss\ rate_1 \times (Hit\ time_2 + Miss\ rate_2 \times Miss\ rate_2)$
-
|| Local miss rate | Global miss rate |
|-------| -------- | -------- |
|L1| Miss rateL1 | Miss rateL1 |
|L2| Miss rateL2 | Miss rateL1 × Miss rateL2 |
- Multilevel Exclusion : L1的資料不會存在L2裡面，以避免浪費(通常L1都會包含於L2)

- Read miss before write miss
- 在write-through中，設一個write buffer能提高效率
- 由於write buffer裡面可能有read miss要取的最新的值，所以讓寫入先都完成在讀就可以降低錯誤發生，或是也可以直接讀取buffer裡面的值
- Critical word first & Early restart
- 微處理器在cache取資料的時候通常只需要一個word，所以才適用這個方法
- Critical(緊急) word first : **先到MEM取得該word**，在cache拿到資料之後，無論如何直接丟給CPU，讓CPU去做執行並同時更新Block內的值
- Early restart : **以正常流程到MEM取的該word，等同於將此word放到要求序列的第一個**，後面動作一樣。
- Merging write buffers
- 資料通常會先寫到緩衝區在寫到MEM
- 由於記憶體特質，一次寫入大量比多筆輸入來的快，因此我們會在緩衝區整理資料(用Locality性質)
- 

- Victim caches
- 紀錄丟棄的case(因miss被取代或是可能很有價值的值)，當他再次取到時表示能降低penalty
- 需要一個small, fully-associative cache來記錄，稱為recycling
- 

3. Reducing the miss rate
- larger block size(降compulsory miss)
- larger cache size(降capacity miss),
- higher associativity(降conflict miss),
- Pseudo-associativity
- Compiler optimizations, Multilevel caches, Split cache

5. Reducing the miss penalty or miss rate via parallelism
> 參考:[https://hackmd.io/@Rance/Hy3KRm1CG?type=view]

- 前情提要Prefetching : 在MEM不須讀寫時(ALU運作時)平行下載資料以降低miss latency的方法
- 預取注重MEM bandwidth優化，如果干擾到需求data則會降低效能，可以透過編譯器減少無用的prefetching
- Hardware prefetching :
- 透過硬體預先提取指令或是資料，放到cache或是緩衝區(要比MEM快才有意義)。
- 當miss發生且緩衝無資料須到MEM取時，被請求的資料會正常回傳，下一個相鄰的block會存入預取區(考慮Locality)
- 優點 : 不用增加指令，可以直接硬體時做，而且可以訓練
- 缺點 : 無法過大量操作，也無法存取不規則記憶體資料
- Software prefetch
- 在程式中插入指令執行預取
- 優點 : 可以做不規則存取,可以做存取的cache level指定, Loop Bounds(unrolling)
- 缺點 : 會增加指令數, 改變程式結構始可讀性下降(unrolling)
- Compiler prefetching
- 依照預取區位置可分為 : register prefetch 及 cache prefetch
- 依照是否會導致例外發生則分為 : faulting 及 nonfaulting(把指令變成no-op，直接無視，也稱為nonbinding prefetching)
- Semantically invisible : 最有效的預取方法，他不會更動register或是MEM裡面的值
- Loop通常在預取裡面效果最佳
- Compiler prefetching要是nonblockong才有意義，不然等停止時般資料就可以，且此方法會增加指令，須謹慎使用
- Nonblocking caches

7. Reducing the hit time
- Avoiding address translation, Vitual cache
- 利用虛擬位可以減少轉譯的時間
- 缺點 :
1. 若虛擬要轉為實際，必須檢查上面的保護資訊，以防程序修改別的程序的資料(通常miss時會將保護資訊存在TLB)；
3. 虛擬位置跟實際位置對應位置可能會改變，改變時需刷掉整個快取(設置PID_process identify去記錄需要刷掉的部分)；
4. 不同虛擬位置可能會對應到同一個實際位置，稱為synonyms或aliases(硬體解:antialiasing，保證每一個block都有獨一無二的實體位址；軟體解:page coloring，決定虛擬位址和實體位址最低位元要有幾個完全相同，即共有幾組相同size的虛擬位址組可以用)
- 目前最常用組合為：虛擬索引，實體標籤(virtually indexed, physically tagged)
- Way prediction
- 在cache中新增一個bits去預測可能會存取的Way或是Block，猜對可以大大節省hit time，猜錯會增基miss penalty
- 最大的缺點是pipeline難以實現
- Trace Cache
- Small and Simple caches
- Piplines cache access
5. Increasing cache bandwidth
- Pipelined caches
- 將hit time分散到多個clock cycle
- 缺點 : 增加miss penalty當預測錯誤，從lw指令到資料使用之間的週期數上升
- Multibanked caches
- 將緩存分位好幾個緩存區，便可以做同步存取
- 最簡單的影射方法是sequential interleaving，就是餘數的概念
- Nonblocking caches/lockup-free cache
- 就算miss也可以繼續提供cache給其他data使用
- hit under miss(缺失卻命中)=降低miss penalty
- hit under multiple miss” or “miss under miss=將多個缺失視為通一個處理以減少miss penalty
6. Reducing Misses by Compiler Optimizations
- 唯一透過軟體解決的方法
- 指令優化:
1. 將程序重新排序，以降低conflict(衝突) miss
2. 使用工具查看衝突發生原因並剖析
- 資料優化
1. Merging Arrays : 用spatial locality去做合併(降低conflicts)

2. Loop Interchange : 觀察row/column major下去做調整

3. Loop Fusion : 合併兩個有相同循環且獨立運算的迴圈

4. Blocking : 將陣列切成許多小陣列，小陣列讀進快取後要能在被置換前使用(降低conflicts & capacity & miss rate)，主要是利用tempal locality和spatial locality的特性

> 有趣觀察 ->
> 2:1 cache rule of thumb = a direct-mapped cache of size N has about the same miss rate as a 2-way set associative cache of size N/2

### 優化整理

\

### Main Memory
- Performance
- Latency: Cache Miss Penalty
- Access Time : 發送要求 ~ word抵達的時間
- Cycle Time : 要求發送的週期
- Bandwidth: I/O ~ 最大MEM(L2) Penalty
- 主記憶體用DRAM
- DRAM用一個晶體存一個bits，每次讀取會破壞該訊息
- DRAM會需要固定周期刷新(refreshed)，防止在讀寫時丟失某bits資料
- 位址傳遞會分為col(CAS) & row(RAS)傳遞
- Cache用SRAM
- 不用刷新，他用6個晶體來儲存一個bits的資訊
- 只需要低功率就能維持電荷
- 在Latency & Bandwidth之間沒有差別

### 嵌入式系統的MEM技術
- Read-Only Memory (ROM)
- Flash memory
- 閃存是ROM
- 在改寫內存時比需先全部清掉
- 靜態(Static)，即在沒有供電時一樣可以保存資料
- 寫入比SRAM慢，但是比disk快

### 在DRAM晶片上提升Memory效能
- 現今有許多提升bandwidth的方法(跟latency無關)
- Fast page mode
- 給予一個timing signals，可以重複的存取row buffer而不需要另外設置一個存取時間
- Synchronous DRAM (SDRAM)
- 給予一個clock signal, 可以重複存取不需要支付處理同步的overhead
- Double Data Rate (DDR SDRAM)
- 在clock signal上升或是下將都允許傳輸資料，稱為doubling the peak data rate

\

### 在DRAM晶片上提升可靠性
- 動機 : 錯誤發生時間跟bits數成正比，且DRAM單元越來越小以至於越來越脆弱
- 如何增加可靠性 :
- Random error correction(常用概念) : SEC_DED(奇偶交錯驗證)，通常8 bits設一個驗證碼
- 物理解決

\

### Virtual Machines
- 背景
- 安全性/可靠度需求的提升
- 一台主機多人共享
- 處理器速度的劇烈增加
- 優點
- 方便進行硬體管理 : 支持許多OS在同個硬體上獨立執行，也允許執行中的OS移動到其他硬體上執行
- 方便管理軟體 : 提供抽象介面，可以跑不同版本OS

- VMM(virtual machine monitor = hypervisor)
- VM的核心，決定虛擬資源與硬體支援的分配，因此硬體資源可以分時共享, 分區或是在軟體上進行模擬
- 比傳統OS小非常多
- 被VMM用來執行一個或多個虛擬機器的電腦稱為主體機器（host machine），這些虛擬機器則稱為客體機器（guest machine）

- Overhead
- 計算導向程式(User-level processor-bound) : 沒什麼開銷，大部分時間還是在原生機器上跑，所以原機器速度會等於執行速度
- IO密集程式(I/O-intensive workloads) : 有高密度系統/特權指令呼叫，有較多的虛擬overhead
- 如果I/O密集程式也是I/O-bound，則虛擬化overhead會因為CPU運作沒有效率而被掩蓋(low)

- VMM需要
- 提供SW介面給用戶，且每個用戶彼此獨立(包含自己)
- 用戶在VM上的使用與原始電腦上沒有區別，當然會部分受限於固定的資源共享
- 用戶不得修改原始電腦上的資源分配，且VMM的權限高於所有人
- VM的需求幾本上跟paged-VM相同
- 至少需要兩個模式 : system & user
- 部分模式只有system模式下才能修改

- 缺少ISA的VM
- 目前大部分的指令架構都沒有考慮到虛擬化
- VMM須確保user只能和虛擬的資源做互動，若否，則會向VMM發出中斷，讓VMM對其相對位置做修正

- 在虛擬記憶體上使用VM的影響
- VMM分為real and physical memory，user透過paged table來將虛擬MEM映射到實際MEM上，VMM則是反過來
- VMM擁有一個 shadow page table 可以直接對用user的虛擬位置到實際位置

- ISA Support for VMs & Virtual Memory
- IBM新增了一個功能使user可以直接管理自己的paged
- 則VMM擁有的就是每個user的TLB副本

- 在虛擬記憶體上I/O的影響
- 由於連上記憶體的設備數量/種類, 驅動程式增加也使這部分的虛擬化最為困難
- 虛擬IO映射到時計IO方式取決於設備類型(方法不贅述)

### 謬論&誤解(描述皆是錯的)
- 謬論
- Predicting cache performance of one program from another(可以從不同程式碼去預測快取效能)
-
- 陷阱
- Simulating enough instructions to get accurate performance measures of the memory hierarchy(只要模擬足夠的指令就能計算出記憶體效能)
- Not delivering high memory bandwidth in a cache-based system(沒有在cache系統中提供高MEM的bandwidth) : cache可以幫助平均縮短MEM latency，但可能不會提供process進入MEM所需要的bandwidth