基本硬體架構及指令集
硬體包括
1. Register
2. Memory
3. Instruction format
4. Addressing mode
1. Control Unit
2. Datapath
3. Memory
4. Input
5. Output
堆疊的某個區段,其中包含程序的區域變數及儲存暫存器
1.基本區塊
一連串沒有分支(有?只能出現在最後一個指令處)及分支目的(有?只能出現在第一個指令處)的指令
2.最佳化
使用最少最精簡的指令完成程式所需功能以減少程式大小並加速執行
硬體沒有實作但組譯器可以接受的指令
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 | CISC |
---|---|
指令長度相同 | 指令長度不一 |
少數定址模式 | 多種定址模式 |
少數指令格式 | 多種指令格式 |
運算原只能來自暫存器 | 可來自記憶體 |
記憶體資料須先載入暫存器 | 記憶體資料可直接處理 |
一個指令用一個cycle完成
Cycletime取決於最長指令執行時間
允許一個指令重複使用功能單元
Cycle time取決於最長Stage
硬體最少
允許多個指令重疊被執行以提高Throughput
Stage少則Latency低
Throughput要提高則Cycle time要變低
達不到理想加速的原因
1. Stage切的不平衡
2. Control/Data Hazard
3. 清空和填滿Pipeline的時間
4. Pipeline Register的延遲
三種實作方式Cycle time皆取決於Critical path
即下一個指令無法在下一個Cycle正確地被執行
1. Structual Hazard
硬體資源不足,導致同一時間內要執行的多個指令無法正確執行
2. Data Hazard
下個指令需要用到前面指令尚未產生的結果
3. Control Hazard
當分支指令尚未決定是否分支,後面指令已進入Pipeline,若分支發生則指令執行順序便會產生錯誤
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:於分支使用多個預測器,哪個準確率高就用哪個
一種解決Control hazard的方法
Compiler將不論分支是否發生都會執行到的指令(安全指令)放至Delayed slot,延遲後面執行的指令
即可避免Control hazard所帶來的Cycle浪費
Deeper pipeline 使更多指令能同時進到Pipeline執行
Speedup變高
增加ILP
Difficult to balance stage
Hazard變嚴重
複製電腦內部功能單元,使得每個stage可以執行多個指令
分析指令性質,決定與此指令相關之後續指令能否提早被執行
靜態多重分發的一種,允許多個指令同時在某個Stage被執行
ALU/BEG | LW/SW
將迴圈展開使得Compiler能更有彈性的重新排程指令
用來消除Antidependency的一種方法
指令間因為使用相同的暫存器,導致Compiler無法彈性地將指令重新排程或有潛在的Hazard出現,但指令之間其實並沒有資料的流通稱之
靜態多重分發的一種
順序如下:
1. Compiler分析指令流
2. 把沒Data Dependency和硬體衝突的指令放在超長指令格式中
3. 若Hazard無法解決 只能在Run-time暫停Pipeline
優點:簡單易擴充
缺點:
1.Code佔用空間變大(Loop Unroll)
2.Bandwith需求大
3.Compile time變長
1. 與MIPS差異
1.暫存器比MIPS多很多
2.把有固定格式且清楚標明相依性的指令裝在一起
3.含特殊指令可以把分支消除
2. 比VLIW更加彈性
3. 含Instruction Group及Bundle(無法形成前者的指令)
含2個HW分別執行以上兩個
4. Prediciotn
使用條件指令取代分支指令以消除分支跳躍
使用Dynamic Pipleline Scheduling在Run-time時重排指令順序,解決Hazard避免Pipeline暫停
1.Flush掉IF ID EX並讓MEM WB完成
2.存發生例外的指令位置至EPC
3.存原因到Cause Register
4.呼叫OS處理
5.返回User Code
若處理器可以清楚知道是哪個Stage的指令造成Exception,此處理器擁有非精準中斷
提供使用者能用最便宜的技術來擁有足夠的記憶體,並利用最快的記憶體來提供最快的存取速度
主要利用到Locality
程式在執行時,一個時間點只會存取一小部分的位置空間
1.Temporal Locality
若某個項目被存取到,那麼它很快會被再次存取到
2.Spatial Locality
若一個項目被存取到,那麼它位置附近的項目也會很快被存取到
前者為Cache之間的資料不一致
後者為上下層Mem資料不一致
1. Write Through
寫入Cache的同時也寫入下層Mem
2. Write Back
只寫入Cache並記錄哪些Block被寫過,被寫過的Block被置換時會寫回下層Mem
3.Write Buffer
儲存等待被寫入記憶體的資料
資料寫入Cache與Buffer後處理器即可繼續執行。
若Buffer已滿,處理器需等待
1.Write Allocate
從記憶體中取得要寫入的Block放入Cache後寫入
2.Write Around
直接寫入記憶體
將Cache切分成數個集合,記憶體的每個區塊可以對應至某個集合內任何block
CPU平均存取一次Mem的時間稱之
使用Mem當作Disk的快取,採取Demand Paging,即程式不只需部分載入記憶體即可執行。
一種Virtual Mem與Physical Mem對應的技術
動機
1.使得多個程式可以安全有效的分享記憶體
2.程式大小可以超過記憶體大小
保存近期常被存取的位置轉換資訊,用來加速虛擬與實體位置的轉換
注意
1.TLB Miss可由硬體或軟體處理,Cache為硬體
2.TLB使用完全關聯式,因可有較小的Miss Rate且因TLB較小,成本不至太高
3.在完全關聯式中使用LRU成本太高且TLB Miss比Page Fault機率高,因此一般採用Random
使用虛擬位置存取快取,可以使得Hit Time較低
不同的Virtual Page對應到相同的Physical Page稱之
當Aliasing發生,若某個程式寫入資料,另一個程式可能不知道資料已被改變
Virtually Addressed | Physically Addressed | Virtually indexed, Physically tagged | |
---|---|---|---|
優點 | 存取速度快 | 架構簡單 | 架構簡單,存取效率佳 |
缺點 | Aliasing Problem | 存取效率低 | 總是要轉換虛擬位置至實體位置 |
硬體須提供
1. 支援至少兩種模式以區分使用者與OS
2. 區分有些資料結構User只能讀不能寫
3. User Mode與Kernel Mode之間的切換
三種Cache Miss的原因
存取第一次使用的Block時發生的Miss稱之
Cache不足以容納所有該程式所需區塊,導致Block不斷的被取代、替換而稍後需要時又要重新擷取
在集合關聯式或直接關聯式快取當中,若多個Block被對應至相同地方所產生的Miss稱之
當發生Miss時允許處理器繼續執行會存取資料的指令,通常用在Out-of order execution處理器中
1. Reducing miss penalty
1. Multilevel cache
2. Critical word first
3. Read priority over write on miss
4. Merging write buffer
1. Larger block size
2. Larger cache size
3. Higher associativity
4. Compiler optimization
5. Vimtim cache
1. Prefetching
2. Non-blocking cache
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 | - | + |
1. 用Software Simulation技術模擬出與硬體元件一模一樣的功能介面,此一抽象化機器稱之。
2. 最近又受到關注原因有四
1. 現代系統中,隔離性與安全性日益重要
2. 標準作業系統中,安全性與可靠性不足
3. 多個不相干的使用者使用同一台計算機
4. 處理器的進步使得虛擬機的Overhead可被接受
3. Virtual machine software run in kernel mode since it is operating system
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用來衡量一個系統提供服務的品質
用Reliability和Availability來量化一個系統的Dependability
一段時間內可以正常運作的機率
某個時間點可以正常運作的機率
MTTF:系統平均運作多久會失效
MTTR:系統失效後平均用多少時間可恢復運作
MTBF=MTTF+MTTR
Availability=MTTF/MTBF
1. 錯誤避免(Fault Avoidance)
2. 錯誤容忍(Fault Tolerence)
3. 錯誤預測(Fault forecasting)
使用多個容量較小,比較便宜的硬碟來獲得比單一較大且貴的硬碟更好的性能
可選擇性壞多個
1. 硬體及維護成本太高=>沒人用
2. 還原速度快於3.45
1. Small read/write throughput最差
2. Large read/write 3 4 5 一樣爛
3. Read 的latency最短
4. Write的latency最短是RAID0或RAID3 取決block size(大的話3,小的話0)
1. Small read不錯
2. Small write可平行,但Parity disk是bottleneck
解決RAID4中Parity disk的問題,打散Parity到各Data disk
7.RAID6(P+Q Redundancy)
允許兩顆壞
更新硬碟資料
4.5.6兩讀兩寫
部分記憶體空間被用來指定I/O設備。對這些位置做讀取或寫入,被解讀對I/O下指令
Resoonse time小
這些I/O指令能夠明確指出裝置號碼和命令在記憶體中的位置。有額外的I/O bus與設備溝通
含有兩個以上處理器之電腦稱之
若Process不能分解=>Job level parallelism
若Process可以分解=>Thread level parallelism
Computer 有很多處理器受控於單一個Control,同一時間不同處理器執行同一指令,處理不同資料
一個IC有多顆處理器
電腦硬體支援有效率的執行多個Thread
一個程式可以分配給多個處理器同時執行
電腦裡有多個處理器可以同時執行一個程式或多個Thread
電腦有多個處理器可以同時執行多個程式
一個程式平均有多少指令可以同時被執行
允許多筆獨立資料同時被運算
允許多個Memory的存取同時進行
電腦允許多個Thread同時或交錯的被執行
不用增加問題的Size大小就能獲得Speedup
當透過與處理器數量增加成比例的增加問題大小來獲得Speedup
提供給所有處理器單一"邏輯"的記憶體空間,彼此之間可以透過共用變數來溝通。所有處理器都可以存取記憶體中任何位置的資料
不管是哪個處理器(同處理器)發出存取,不論是存取哪個字組,存取的時間都相同
不同處理器(異處理器)存取不同字組所需時間不同
擴展性較好
此架構下所有處理器有自己的私有空間,彼此透過explictly sending and receiving來溝通
不須擔心Cache coherency => 架構簡單
在Multiprocessor架構中不同快取中可能會保存相同筆的資料,當有處理器對其快取進行存取,就有可能導致不同快取之間的資料不一致性稱之
在寫入自己快取之間,先無效化其他處理器之快取的相同備份再進行寫入
進行寫入的處理器廣播資料最新的值,其他處理器之快取也隨之更新
每寫一個word都要廣播
Write-invalidate與Write back皆可降低匯流排頻寬的好處
=> 商業中使用以上兩種方法來使用單一匯流排連接更多處理器
一種硬體技術,允許多個thread交錯在單一處理器上執行來增加單一處理器上功能單元使用率
用到TLP
每個clock切換thread執行thread的一個Instr. pack
優點:可以隱藏short及long stall所帶來的throughput損失 TLP
缺點:各別thread的執行會慢下來
用到TLP
直到遇到long-latency event才換thread
優點:不會使個別thread執行慢下來
缺點:Pipeline start-up cost,因為切換thread時,pipeline要flush及refill
Hardware multithreading的一種變化,使用superscalar的硬體資源來獲得較好的ILP及TLP
Pipeline ALU來獲得performance的提升
有許多vector registers保存運算原及結果
結合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的操作
把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為容錯能力評估
Power = Capacitive-load X Voltage^2 X Frequency