# Memory Hierarchy ## 1. Introduction <img src="https://hackmd.io/_uploads/rkl_Uut2C.png" width="100%"> - AMAT: average memory access time - cache 和 main memory 的資料交換單位: block miss (cache裡沒有) 稱 cache miss - main memory 和 virtual memory 的資料交換單位: page miss (main memory裡沒有) 稱 page fault ## 2. Multi-core architecture ### 2.1 Symmetric multiprocessor (SMP) ![8FC5D617-C25C-4EA0-89BF-C555F2292F4F](https://hackmd.io/_uploads/BkFbGp5hC.jpg) - 有 shared memory，每個處理器都可以直接且以相同的時間成本訪問到記憶體中的任何一部分 - SMP 系統中需要特別處理記憶體一致性(coherent)問題，因為多個處理器可能會同時讀寫同一記憶體位置。這通常通過hardware-level memory coherence protocols（如MESI）來解決。 `MESI: Modified, Exclusive, Shared, Invalid` - 資料在 bus 上傳遞，容易有 bandwidth problem ### 2.2 Distributed shared-memory multiprocessor ![Untitled (8)](https://hackmd.io/_uploads/SJfGu_thC.png) - 每個處理器或處理器群都有自己的local memory，但可以通過一個高速網絡（如InfiniBand）相互訪問對方的記憶體。 - Comparison - **性能**：SMP 由於所有處理器都能均等且快速地訪問共享記憶體，通常在低到中等規模的設置中性能較好。DSM 則在大規模和高度分散的系統中表現更佳。 - **可擴展性**：SMP的可擴展性受限於shared memory 的 bandwidth 和記憶體 coherent protocol的效率，而DSM設計理論上可以支援更多的處理器。 - **複雜度**：DSM 在實現和維護上通常比 SMP 更為複雜。 ## 3. 關於 Cache ### **3.1 Block Placement** **Cache mapping: 有三種 mapping function** block: the unit of data transfer 1. **Direct mapping (1 way set)** - (block address) MOD (number of blocks in a cache) - access time 小，miss rate大 (cache entry 數不夠，會遇到多個address競爭同個entry導致大量miss) - 管理簡單 2. **Fully associative** - cache 全部位置都可以上 - access time大(找資料需要收尋整個 cache)，miss rate 小 - has no index field 3. **n-way set associative** 每個 set 有 n 個 block，每個 address 會對應到一個 set，1個 memory block 有 n 個 cache block 去對應 example (下圖: 假設main memory有32個block，cache有8個block ) 問題: main memory中的第12個block 可以去cache的哪個位置 ![Untitled (9)](https://hackmd.io/_uploads/r10Uuut3R.png) ! 最右邊的例子為 2-way set ### **3.2 Block Identification** 怎麼在 cache 中找到想要的 data? → 找 set，再找 block，最後找到想要的資料如 words/ bytes <img src="https://hackmd.io/_uploads/B1Tu_dK2C.png" width="80%"> - Index 1. 找set 2. fully associative cache has no index field (fully associative 沒有 set ) - tag 1. 找block 2. if no candidates match, then declare cache miss - block offset select data within a block (block裡找words, bytes) 讀寫流程: 拿到 address，利用 address 的 **index 去找出對應的 set**，先去看該 set 是否 valid，**再去比較兩者 tag**，若 valid 且 tag 一致，代表 hit，把 data 讀出/ 寫入 ### **3.3 Block Replacement** Which block should be replaced when cache miss (cache miss 誰要出去) - direct-mapped cache: 該 block missed 就踢掉該 block - fully associative/ set associative 1. random 2. least recently used (LRU) 3. first in, first out (FIFO) ### **3.4 Write Strategy** What happens on a write. 將下層記憶體寫到上層記憶體的方法 - write latency >> read latency - write cache 的 policy 1. **Write-Through** 更新上層 memory 時會直接更新下層的 memory 2. **Write-Back** 當上層的 block要被 replace (有別的 block 要上來，該 block 要被踢掉)，才寫回下層 memory dirty bit is commonly used - write buffer - 允許 CPU 在不等待數據完全寫入到較慢的主記憶體中的情況下，繼續執行後續的指令 - CPU 將 data 放入 buffer，然後繼續執行下一條指令，無需等待寫入 main memory 的過程完成。這樣，write operation 就變成了異步(asynchronous)的，提高 CPU 的運行效率。 - both write-through and write-back can use write-buffer to make writes asynchronous ![Untitled (11)](https://hackmd.io/_uploads/HJZHYOtnR.png) - Write buffer 的問題 - Write Through - example `SW R3, 512(R0) `: 將 R3 的數據寫入 write buffer。 `LW R1, 1024(R0)` `LW R2, 512(R0) `: R2 是否等於 R3 取決於 write buffer 中的數據是否已經被存進 main memory - 問題: - 原則: cache 和 main memory 的資料要同步 - Read miss waits until the write buffer 存進 main memory → large read miss penalty - 解決: 檢查 write buffer 的內容，如果沒有衝突，則 memory access 繼續 - Write Back - 只要cache 上是最新資料就好 - dirty block 的概念: 數據只會寫入 cache，還不用更新 main memory，只要相應的 cache block 被標記為 dirty block 就好。當此 dirty block 需要被替換才寫回 main memory - 發生 write miss 要被 write 的資料不在 cache 上，我們要不要去 lower-level 搬資料上來 cache 1. 要 → Write Allocate - 到 lower level 搬資料，然後 overwrite it - act like read miss - 優點: guarantee nearby data (要讀旁邊的資料時，該資料已經在cache 了) 缺點: 如果對該數據的訪問不頻繁，可能會無意中替換掉其他更頻繁訪問的 data - 如果預期對寫入的數據有重複的讀取，使用 write allocate 策略比較好 2. 不要 → No-write Allocate - 不搬上cache，直接到 lower level memory 進行 write，如果之後 read 該 block，才上去cache - 如果寫入操作較多且這些數據之後很少被再次訪問，使用 No-Write Allocate 策略比較好，避免不必要的替換。 write-through caches often use no-write allocate write-back caches often use write allocate ### 3.5 Cache Miss - 種類 1. Compulsory (cold-start miss, first-reference miss) 一開始 cache 是空的，當 program 第一次讀寫某個資料時，無論 cache size 如何，一定會發生miss 2. Capacity 跟cache size有關，越大越不會cache miss，但 hit time 會越長 3. Conflict 和cache mapping的方式有關，multiple memory location mapped to the same cache location increase associativity 可減少 miss rate，但 hit time 會越長 1. Coherence 當多個處理器或核心需要存取同一個資料時，如果 cache system 的資料沒有一致，就是 coherence miss - 情境 1. cache size remain, increase block size means block number will decrease → compulsory miss decrease → miss penalty increase 2. larger total cache capacity → decrease miss rate → increase hit time → increase power consumption 3. higher associativity → decrease conflict misses (miss rate) → increase hit time → increase power consumption ### 3.6 Multi-level caches - AMAT (average memory access time) 1-level <img src="https://hackmd.io/_uploads/SkDjY_Y3C.png" width="80%"> AMAT = hit time + miss rate * miss penalty 2-level <img src="https://hackmd.io/_uploads/SJxgW9OKhC.png" width="80%"> AMAT = hit time of L1 + miss rate of L1 * (hit time of L2 + miss rate of L2 * miss penalty of L2) - local miss rate vs. global miss rate 以 2-level cache system 為例 local miss rate: 單看一個 cache，如 L1 cache or L2 cache global miss rate: miss rate of L1 * miss rate of L2 → global miss rate is what matters，想辦法降低 global miss rate - 基本上，為了使 global hit time 小，level 1 cache size 小，且以 direct mapping 為主 為了使 global miss rate 小，level 2 則以 set-associative mapping 為主 ## 4. Memory Technology ### 4.1 Volatile 停止供應電源，記憶體資料就會消失 - SRAM (static random access memory) - commonly used for cache - 6 transistors/ bit <img src="https://hackmd.io/_uploads/HJ6B5OK2R.png" width="80%"> - no refresh - DRAM (dynamic random access memory) - a high bandwidth memory with many banks, commonly used for main memory - 1 transistor/ bit - must be re-written after being read 當讀取DRAM中的數據時，內部的電荷會被釋放，這導致存儲的數據被破壞。因此，在讀取數據後，必須立即將數據重新寫回去，以確保數據的完整性。 - must be periodically refreshed 電荷會隨時間逐漸流失，為了防止數據丟失，DRAM需要定期 refreshc each row - organization ![Untitled (15)](https://hackmd.io/_uploads/rJD5c_t3R.png) ### 4.2 Non-Volatile 即使沒有供應電源，也能保存已經寫入的資料 - ROM (read only memory) - programmed at the time of manufacture - Flash - commonly used as an alternative to hard disk - NAND flash vs. NOR flash 1. architecture NOR Flash：平行架構，使隨機存取速度較快，適用於需要快速讀取的應用，如微控制器中的固件儲存。 NAND Flash：串行架構，多個記憶體單元串聯以達到更高的密度，但隨機存取速度較慢。常見於大容量儲存裝置，如 USB 和固態硬碟 (SSD)。 2. Density and cost NOR Flash：儲存密度較低，不適合大容量儲存應用。每GB成本較高。 NAND Flash：提供更高的儲存密度和更低的每GB成本，是需要大容量儲存的裝置的首選。 3. Erase and write operations NOR Flash：允許單獨修改位元組或字，不需要擦除整個區塊。適合頻繁更新或修改的應用。 NAND Flash：**需要先擦除區塊後才能寫入新資料**，這種塊擦除過程比較不靈活，但在大規模資料儲存中更有效率。 - Page: 最小的可寫入單位，讀取操作也通常是以頁為單位進行。 通常由數十到數百個位元組（bytes）組成 - Block: 是最小的擦除單位，由多個page組成 4. Endurance and lifespan NOR Flash：通常具有比 NAND Flash 更高的耐用度和壽命，能承受更多的程式/擦除循環。 NAND Flash：由於塊擦除過程，其耐用度較低，不適合需要頻繁更新的應用。