計算機組織名詞

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的原因

Compulsory Miss

存取第一次使用的Block時發生的Miss稱之

Compacity Miss

Cache不足以容納所有該程式所需區塊，導致Block不斷的被取代、替換而稍後需要時又要重新擷取

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

Reducing miss rate

1. Larger block size
2. Larger cache size
3. Higher associativity
4. Compiler optimization
5. Vimtim cache

Reducing miss penalty or miss rate via parallelism

1. Prefetching
2. Non-blocking cache

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

Reliability

一段時間內可以正常運作的機率

Availability

某個時間點可以正常運作的機率

Dependability測量

MTTF:系統平均運作多久會失效
MTTR:系統失效後平均用多少時間可恢復運作
MTBF=MTTF+MTTR
Availability=MTTF/MTBF

改善MTTF方法

1. 錯誤避免(Fault Avoidance)
2. 錯誤容忍(Fault Tolerence)
3. 錯誤預測(Fault forecasting)

RAID(Redundant Arrays of Inexpensive Disks)

使用多個容量較小，比較便宜的硬碟來獲得比單一較大且貴的硬碟更好的性能

RAID0(Block stripping)
RAID1(Mirror)

可選擇性壞多個

RAID2(Error Detecting and Correcting Code)

1. 硬體及維護成本太高=>沒人用
2. 還原速度快於3.45

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)

RAID4(Block-Interleaved Parity)

1. Small read不錯
2. Small write可平行，但Parity disk是bottleneck

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同時或交錯的被執行

撰寫平行程式的挑戰

排程(Schedule)
負載平衡(Load balance)
同步的時間(Time for synchronization)
溝通的成本(Overhead of communication)

Speedup 分類

Strong scaling

不用增加問題的Size大小就能獲得Speedup

Weak scaling

當透過與處理器數量增加成比例的增加問題大小來獲得Speedup

Shared-memory Multiprocessor

提供給所有處理器單一"邏輯"的記憶體空間，彼此之間可以透過共用變數來溝通。所有處理器都可以存取記憶體中任何位置的資料

Uniform Memory Access Multiprocessor(UMA)

不管是哪個處理器(同處理器)發出存取，不論是存取哪個字組，存取的時間都相同

NonUniform Memory Access Multiprocessor(NUMA)

不同處理器(異處理器)存取不同字組所需時間不同
擴展性較好

Message Passing Multiprocessor

此架構下所有處理器有自己的私有空間，彼此透過explictly sending and receiving來溝通
不須擔心Cache coherency => 架構簡單

Cache Coherence

在Multiprocessor架構中不同快取中可能會保存相同筆的資料，當有處理器對其快取進行存取，就有可能導致不同快取之間的資料不一致性稱之

Snooping

Write-invalidate

在寫入自己快取之間，先無效化其他處理器之快取的相同備份再進行寫入

Write-update(Write-broadcast)

進行寫入的處理器廣播資料最新的值，其他處理器之快取也隨之更新
每寫一個word都要廣播

Write-invalidate與Write back皆可降低匯流排頻寬的好處
=> 商業中使用以上兩種方法來使用單一匯流排連接更多處理器

Hardware multithreading

一種硬體技術，允許多個thread交錯在單一處理器上執行來增加單一處理器上功能單元使用率

Fine-grained multithreading

用到TLP
每個clock切換thread執行thread的一個Instr. pack
優點:可以隱藏short及long stall所帶來的throughput損失 TLP
缺點:各別thread的執行會慢下來

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