--- # System prepended metadata title: 計算機結構_Memory Hierarchy Design tags: [計算機結構] --- # 計算機結構_Memory Hierarchy Design ###### tags: `計算機結構` > 通常主記憶體會小於Megabyte且不在Disk儲存 > 結構如下圖，資料在前三個傳遞稱為Block，在MEM與IO間傳遞稱為page ![](https://i.imgur.com/APXiudVh.png) \ ### 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數量的餘數 ![](https://i.imgur.com/0K2WbQL.png) #### Block identification > 搜尋block的方法 ![](https://i.imgur.com/rLusuDw.png) > > 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公式統整 > ![](https://i.imgur.com/ppdidAt.png) \ ### 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性質) - ![](https://i.imgur.com/lRFbq5T.png) - Victim caches - 紀錄丟棄的case(因miss被取代或是可能很有價值的值)，當他再次取到時表示能降低penalty - 需要一個small, fully-associative cache來記錄，稱為recycling - ![](https://i.imgur.com/YQUUNWv.png) 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) ![](https://i.imgur.com/79XbOuXg.png) 2. Loop Interchange : 觀察row/column major下去做調整![](https://i.imgur.com/PwlxbfQ.png) 3. Loop Fusion : 合併兩個有相同循環且獨立運算的迴圈![](https://i.imgur.com/H7rh18Y.png) 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 ### 優化整理 ![](https://i.imgur.com/738DwjQ.png) \ ### 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