# 計算機組織名詞 # Chapter 1 ### ISA 基本硬體架構及指令集 硬體包括 **1. Register 2. Memory 3. Instruction format 4. Addressing mode** ### 計算機基礎架構 **1. Control Unit 2. Datapath 3. Memory 4. Input 5. Output** ### Activation Record 堆疊的某個區段，其中包含程序的區域變數及儲存暫存器 ### 基本區塊與最佳化 **1.基本區塊** ``` 一連串沒有分支(有?只能出現在最後一個指令處)及分支目的(有?只能出現在第一個指令處)的指令 ``` **2.最佳化** ``` 使用最少最精簡的指令完成程式所需功能以減少程式大小並加速執行 ``` ### 虛擬指令 硬體沒有實作但組譯器可以接受的指令 ### Addressing Mode **1. Immediate Addressing 2. Register Addressing 3. Base or Displacement Addressing 4. PC-Relative Addressing 5. Pseudodirect Addressing** ### 指令集設計原則 **1. Simplicity favors regularity** ``` 1.指令長度一致 2.不同指令格式的暫存器欄位在同個位置 3.算術指令皆須3個運算元 ``` **2. Smaller is faster** ``` MIPS只有32個暫存器 ``` **3. Make the common case fast** ``` 1.使用PC-Relative 2.Immediate addressing取得常數 ``` **4. Good design demands good compromises** ``` 在提供較大的記憶體位置和常數與保持指令長度一致性取得平衡=>使用多種指令格式 ``` ### RISC vs CISC | RISC | CISC | | ------------ | ------------ | | **指令長度相同** | **指令長度不一** | | **少數定址模式** | **多種定址模式** | | **少數指令格式** | **多種指令格式** | | **運算原只能來自暫存器** | **可來自記憶體** | | **記憶體資料須先載入暫存器** | **記憶體資料可直接處理** | --- # Chapter 5 ### Single-cycle Machine ``` 一個指令用一個cycle完成 Cycletime取決於最長指令執行時間 ``` ### Multi-cycle Machine ``` 允許一個指令重複使用功能單元 Cycle time取決於最長Stage 硬體最少 ``` ### Pipeline ``` 允許多個指令重疊被執行以提高Throughput Stage少則Latency低 Throughput要提高則Cycle time要變低 ``` 達不到理想加速的原因 ``` 1. Stage切的不平衡 2. Control/Data Hazard 3. 清空和填滿Pipeline的時間 4. Pipeline Register的延遲 ``` 三種實作方式Cycle time皆取決於Critical path ### Hazard 即下一個指令無法在下一個Cycle正確地被執行 **1. Structual Hazard** ``` 硬體資源不足，導致同一時間內要執行的多個指令無法正確執行 ``` **2. Data Hazard** ``` 下個指令需要用到前面指令尚未產生的結果 ``` **3. Control Hazard** ``` 當分支指令尚未決定是否分支，後面指令已進入Pipeline，若分支發生則指令執行順序便會產生錯誤 ``` ### Branch Prediction **1. Static Branch Prediction** ``` 假設分支不發生，若發生則Flush掉前面指令 ``` **2. Dynamic Branch Prediction** ``` BPB(BHB):保存分支是否發生的紀錄濃縮，輸出一個Bit指示預測跳或不跳 BTB:存放跳躍目的位址或目的指令，搭配BHB以消除Branch penalty ``` **3. More Complex Prediction** ``` Correlating predictor:同時使用Local與Global的分支資訊 Tournament predictor:於分支使用多個預測器，哪個準確率高就用哪個 ``` ### Delayed Branch 一種解決Control hazard的方法 Compiler將不論分支是否發生都會執行到的指令(安全指令)放至Delayed slot，延遲後面執行的指令 即可避免Control hazard所帶來的Cycle浪費 ### Superpipeline Deeper pipeline 使更多指令能同時進到Pipeline執行 ``` Speedup變高 增加ILP Difficult to balance stage Hazard變嚴重 ``` ### Multiple Issue 複製電腦內部功能單元，使得每個stage可以執行多個指令 ### Speculation 分析指令性質，決定與此指令相關之後續指令能否提早被執行 ### MIPS-64 靜態多重分發的一種，允許多個指令同時在某個Stage被執行 ``` ALU/BEG | LW/SW ``` ### Loop Unrolling 將迴圈展開使得Compiler能更有彈性的重新排程指令 ### Register Renaming 用來消除Antidependency的一種方法 ### Antidependency 指令間因為使用相同的暫存器，導致Compiler無法彈性地將指令重新排程或有潛在的Hazard出現，但指令之間其實並沒有資料的流通稱之 ### VLIW 靜態多重分發的一種 順序如下: ``` 1. Compiler分析指令流 2. 把沒Data Dependency和硬體衝突的指令放在超長指令格式中 3. 若Hazard無法解決 只能在Run-time暫停Pipeline ``` ``` 優點:簡單易擴充 缺點: 1.Code佔用空間變大(Loop Unroll) 2.Bandwith需求大 3.Compile time變長 ``` ### IA-64(Explicitly Parallel Instruction Computer,EPIC) **1. 與MIPS差異** ``` 1.暫存器比MIPS多很多 2.把有固定格式且清楚標明相依性的指令裝在一起 3.含特殊指令可以把分支消除 ``` **2. 比VLIW更加彈性** **3. 含Instruction Group及Bundle(無法形成前者的指令)** 含2個HW分別執行以上兩個 **4. Prediciotn** 使用條件指令取代分支指令以消除分支跳躍 ### 動態多重分發處理器(Superscalar) 使用Dynamic Pipleline Scheduling在Run-time時重排指令順序，解決Hazard避免Pipeline暫停 ### Exception處理 ``` 1.Flush掉IF ID EX並讓MEM WB完成 2.存發生例外的指令位置至EPC 3.存原因到Cause Register 4.呼叫OS處理 5.返回User Code ``` ### 非精準中斷 若處理器可以清楚知道是哪個Stage的指令造成Exception，此處理器擁有非精準中斷 --- # Chapter 6 ### Memory Hierarchy 提供使用者能用最便宜的技術來擁有足夠的記憶體，並利用最快的記憶體來提供最快的存取速度 主要利用到Locality ### Locality 程式在執行時，一個時間點只會存取一小部分的位置空間 **1.Temporal Locality** ``` 若某個項目被存取到，那麼它很快會被再次存取到 ``` **2.Spatial Locality** ``` 若一個項目被存取到，那麼它位置附近的項目也會很快被存取到 ``` ### Coherence vs Inconsistent 前者為Cache之間的資料不一致 後者為上下層Mem資料不一致 ### Write Hit **1. Write Through** ``` 寫入Cache的同時也寫入下層Mem ``` **2. Write Back** ``` 只寫入Cache並記錄哪些Block被寫過，被寫過的Block被置換時會寫回下層Mem ``` **3.Write Buffer** ``` 儲存等待被寫入記憶體的資料 資料寫入Cache與Buffer後處理器即可繼續執行。 若Buffer已滿，處理器需等待 ``` ### Write Miss **1.Write Allocate** ``` 從記憶體中取得要寫入的Block放入Cache後寫入 ``` **2.Write Around** ``` 直接寫入記憶體 ``` ### Set Associative 將Cache切分成數個集合，記憶體的每個區塊可以對應至某個集合內任何block ### AMAT CPU平均存取一次Mem的時間稱之 ### Virtual Memory 使用Mem當作Disk的快取，採取Demand Paging，即程式不只需部分載入記憶體即可執行。 一種Virtual Mem與Physical Mem對應的技術 **動機** ``` 1.使得多個程式可以安全有效的分享記憶體 2.程式大小可以超過記憶體大小 ``` ### TLB(Translation-lookaside Buffer) 保存近期常被存取的位置轉換資訊，用來加速虛擬與實體位置的轉換 **注意** ``` 1.TLB Miss可由硬體或軟體處理，Cache為硬體 2.TLB使用完全關聯式，因可有較小的Miss Rate且因TLB較小，成本不至太高 3.在完全關聯式中使用LRU成本太高且TLB Miss比Page Fault機率高，因此一般採用Random ``` ### Virtually Addressed Cache 使用虛擬位置存取快取，可以使得Hit Time較低 ### Aliasing 不同的Virtual Page對應到相同的Physical Page稱之 ### Aliasing Problem 當Aliasing發生，若某個程式寫入資料，另一個程式可能不知道資料已被改變 ### 比較 | | Virtually Addressed | Physically Addressed | Virtually indexed, Physically tagged | | --- | -------- | -------- | -------- | |**優點**| **存取速度快** | **架構簡單** | **架構簡單，存取效率佳** | |**缺點**| **Aliasing Problem** | **存取效率低** | **總是要轉換虛擬位置至實體位置** | ### Virtual Memory保護機制 硬體須提供 **1. 支援至少兩種模式以區分使用者與OS 2. 區分有些資料結構User只能讀不能寫 3. User Mode與Kernel Mode之間的切換** ### 3C 三種Cache Miss的原因 1. Compulsory Miss ``` 存取第一次使用的Block時發生的Miss稱之 ``` 2. Compacity Miss ``` Cache不足以容納所有該程式所需區塊，導致Block不斷的被取代、替換而稍後需要時又要重新擷取 ``` 3. Conflict Miss ``` 在集合關聯式或直接關聯式快取當中，若多個Block被對應至相同地方所產生的Miss稱之 ``` ### Non-blocking Cache 當發生Miss時允許處理器繼續執行會存取資料的指令，通常用在Out-of order execution處理器中 ### Cache Optimization **1. Reducing miss penalty** ``` 1. Multilevel cache 2. Critical word first 3. Read priority over write on miss 4. Merging write buffer ``` 2. Reducing miss rate ``` 1. Larger block size 2. Larger cache size 3. Higher associativity 4. Compiler optimization 5. Vimtim cache ``` 3. Reducing miss penalty or miss rate via parallelism ``` 1. Prefetching 2. Non-blocking cache ``` 4. Reducing hit time ``` 1. Small and simple cache 2. Trace cache 3. Avoiding address translation 4. Way prediction ``` | Technique | Hit time | Bandwidth | Miss penalty | Miss rate | | ---------------------- | -------- | --------- | ------------ | --------- | | Banked cache | | + | | | | Compiler | | | | + | | Prefetching | | | + | + | | Critical word first | | | + | | | Early restart | | | + | | | Merging write buffer | | | + | | | Non-blocking cache | | + | + | | | Way prediction | + | | | | | Trace cache | + | | | | | Small and simple cache | + | | | - | | Pipeline cache access | - | + | | | ### Virtual Machine **1. 用Software Simulation技術模擬出與硬體元件一模一樣的功能介面，此一抽象化機器稱之。** **2. 最近又受到關注原因有四** ``` 1. 現代系統中，隔離性與安全性日益重要 2. 標準作業系統中，安全性與可靠性不足 3. 多個不相干的使用者使用同一台計算機 4. 處理器的進步使得虛擬機的Overhead可被接受 ``` **3. Virtual machine software run in kernel mode since it is operating system** --- # Chapter 7 ### Flash ``` 1. Semiconductor Memory 2. Nonvolatile 3. 成本與速度介於DRAM與Disk 4. Smaller, lower power, more robust 5. 存取1000次左右就壞了=>手機不適合swap in/out ``` **Nor Flash** ``` 1. Random Access 2. Used for instruction memory in embedded system ``` **Nand Flash** ``` 1. Denser(bits/area),一次傳輸一個block 2. 比較便宜(密度高) 3. Used for USB, media storage ``` ### Dependability Dependability用來衡量一個系統提供服務的品質 用Reliability和Availability來量化一個系統的Dependability 1. Reliability ``` 一段時間內可以正常運作的機率 ``` 2. Availability ``` 某個時間點可以正常運作的機率 ``` 3. Dependability測量 ``` MTTF:系統平均運作多久會失效 MTTR:系統失效後平均用多少時間可恢復運作 MTBF=MTTF+MTTR Availability=MTTF/MTBF ``` 4. 改善MTTF方法 ``` 1. 錯誤避免(Fault Avoidance) 2. 錯誤容忍(Fault Tolerence) 3. 錯誤預測(Fault forecasting) ``` ### RAID(Redundant Arrays of Inexpensive Disks) 使用多個容量較小，比較便宜的硬碟來獲得比單一較大且貴的硬碟更好的性能 1. RAID0(Block stripping) 2. RAID1(Mirror) ``` 可選擇性壞多個 ``` 3. RAID2(Error Detecting and Correcting Code) ``` 1. 硬體及維護成本太高=>沒人用 2. 還原速度快於3.45 ``` 4. RAID3(Bit-Interleaved Parity) ``` 1. Small read/write throughput最差 2. Large read/write 3 4 5 一樣爛 3. Read 的latency最短 4. Write的latency最短是RAID0或RAID3 取決block size(大的話3，小的話0) ``` 5. RAID4(Block-Interleaved Parity) ``` 1. Small read不錯 2. Small write可平行，但Parity disk是bottleneck ``` 6. RAID5(Distributed Block-Interleaved Parity) ``` 解決RAID4中Parity disk的問題，打散Parity到各Data disk ``` 7.RAID6(P+Q Redundancy) ``` 允許兩顆壞 ``` **更新硬碟資料** 4.5.6兩讀兩寫 ### Memory Mapped I/O 部分記憶體空間被用來指定I/O設備。對這些位置做讀取或寫入，被解讀對I/O下指令 Resoonse time小 ### 專屬I/O指令 這些I/O指令能夠明確指出裝置號碼和命令在記憶體中的位置。有額外的I/O bus與設備溝通 --- # Chapter 8 ### 多處理器(Multiprocessor) 含有兩個以上處理器之電腦稱之 若Process不能分解=>Job level parallelism 若Process可以分解=>Thread level parallelism ### SIMD Computer 有很多處理器受控於單一個Control，同一時間不同處理器執行同一指令，處理不同資料 ### 晶片多核心微處理器(Chip Multicore microProcessors, CMPs) 一個IC有多顆處理器 ### Multi-Threading 電腦硬體支援有效率的執行多個Thread ### Parallel Program 一個程式可以分配給多個處理器同時執行 ### Parallel Processing 電腦裡有多個處理器可以同時執行一個程式或多個Thread ### Process-Level Parallelism(Job-level) 電腦有多個處理器可以同時執行多個程式 ### ILP 一個程式平均有多少指令可以同時被執行 ### DLP 允許多筆獨立資料同時被運算 ### MLP 允許多個Memory的存取同時進行 ### TLP 電腦允許多個Thread同時或交錯的被執行 ### 撰寫平行程式的挑戰 1. 排程(Schedule) 2. 負載平衡(Load balance) 3. 同步的時間(Time for synchronization) 4. 溝通的成本(Overhead of communication) ### Speedup 分類 1. Strong scaling ``` 不用增加問題的Size大小就能獲得Speedup ``` 2. Weak scaling ``` 當透過與處理器數量增加成比例的增加問題大小來獲得Speedup ``` ### Shared-memory Multiprocessor 提供給所有處理器單一"邏輯"的記憶體空間，彼此之間可以透過共用變數來溝通。所有處理器都可以存取記憶體中任何位置的資料 1. Uniform Memory Access Multiprocessor(UMA) ``` 不管是哪個處理器(同處理器)發出存取，不論是存取哪個字組，存取的時間都相同 ``` 2. NonUniform Memory Access Multiprocessor(NUMA) ``` 不同處理器(異處理器)存取不同字組所需時間不同 擴展性較好 ``` ### Message Passing Multiprocessor 此架構下所有處理器有自己的私有空間，彼此透過explictly sending and receiving來溝通 不須擔心Cache coherency => 架構簡單 ### Cache Coherence 在Multiprocessor架構中不同快取中可能會保存相同筆的資料，當有處理器對其快取進行存取，就有可能導致不同快取之間的資料不一致性稱之 ### Snooping 1. Write-invalidate ``` 在寫入自己快取之間，先無效化其他處理器之快取的相同備份再進行寫入 ``` 2. Write-update(Write-broadcast) ``` 進行寫入的處理器廣播資料最新的值，其他處理器之快取也隨之更新 每寫一個word都要廣播 ``` Write-invalidate與Write back皆可降低匯流排頻寬的好處 => 商業中使用以上兩種方法來使用單一匯流排連接更多處理器 ### Hardware multithreading 一種硬體技術，允許多個thread交錯在單一處理器上執行來增加單一處理器上功能單元使用率 1. Fine-grained multithreading ``` 用到TLP 每個clock切換thread執行thread的一個Instr. pack 優點:可以隱藏short及long stall所帶來的throughput損失 TLP 缺點:各別thread的執行會慢下來 ``` 2. Coarse-grained multithreading ``` 用到TLP 直到遇到long-latency event才換thread 優點:不會使個別thread執行慢下來 缺點:Pipeline start-up cost，因為切換thread時，pipeline要flush及refill ``` ### Simultaneous Multithreading(SMT) Hardware multithreading的一種變化，使用superscalar的硬體資源來獲得較好的ILP及TLP ### Vector Processor Pipeline ALU來獲得performance的提升 有許多vector registers保存運算原及結果 ### GPU(Graphic Processing Unit) 結合SIMP的簡單與MIMD的高彈性 **特色** ``` 1. 用來支援CPU運作的加速器。CPU-GPU是一種hetero-geneous的多處理器架構範例。 2. Interface是high-level API(OpenGL)加上high-level語言(NVIDIA's C for Graphics) 3. 圖形處理包含3D geometry指令(直線、三角及rendering(漸層)) 4. Graphic data type: 點(x,y,z,w)(32bits FP)和Pixel(red,green,blue,alpha)(每一格8bit unsingned int)。 5. 無Temporal locality ``` **與CPU差別** ``` 1. CPU靠Multilevel-caches，GPU用Thread來隱藏存取Mem的Latency 2. 使用大量的平行化來獲得高效能。有多個處理器與Thread 3. GPU與其Latency更需要Bandwidth 4. 現在GPU想做的與一般的CPU一樣來提供更高的彈性 5. GPU以前用的是SIMD的指令，現在希望用Scalar instruction增加可編程化和效率 6. 不支援Double FP的操作 ``` ### General Purpose GPU 把GPU拿來執行一般的應用程式以此利用GPU的優點獲得高效能 ### 網路拓撲學 **Single Stage** ``` 1. Ring 2. 2D-Mesh 3. Cube ``` **Multiple Stage** ``` 1. Crossbar 2. Omega network ``` **評估** ``` 1. Network bandwidth 2. Bisection bandwidth(對半切) 3. Diameter 4. Nodal degree 13為傳輸效能評估 24為容錯能力評估 ``` --- # Chapter 9 ### 功率計算 Power = Capacitive-load X Voltage^2 X Frequency