# 計算機結構（Computer Architecture）
參考來源：清大黃婷婷教授CA

## 概念（Introduction）

* Moore's Law
每隔一段時間半導體晶片裡面的電晶體數量就可以呈倍數再成長，因製程改善推動科技進步，是電腦革新的推手，但近年逐漸變慢

* Performance
Response time:
Def. 一份工作從進入了系統開始到全部完成離開系統所花的一個完整的時間
-> 換上較快的處理器，理應當在系統需要處理器執行的時間會縮短
-> 如果針對單一的工作，沒有辦法同時 "切割成好幾個小的部分"，然後丟到不同的處理器來執行的話
可預期的是實際上它的Response time並沒辦法減少
-> 若可"切割成好幾個小的部分" -> 平行計算

Throughput:
Def. 一個單位時間裡面這個系統它所能夠完成的總工作量
-> 增加一個系統內的處理器數量，理應當能提高總工作量

Elapsed Time:
Def. 完整的程式在這個系統裡面執行的時間
Ex: CPU處理時間、I/O input and output、system idle time
Elapsed time比較短 -> 系統效能比較高
Elapsed time比較長 -> 系統效能比較差
-> 針對單一工作的定義

CPU time:
Def. 只關注CPU，不管I/O回應時間等花費

Performance其實就是execution time倒數

* Amdahl's Law
速度的提升受程式中串列部分(程式中不能並行執行的部分)的限制
串列部分的執行時間不會縮短固定工作量，看時間
由此觀點 : 多核心和平行處理終有極限

* Gustafson's Law
電腦所做的工作每年都在變化，資料要處理的量也越來越多，如果固定時間，看工作量
-> 不斷增加需要完成的工作量(這正是電腦發展中的實際狀況) ，串列部分對我們的影響將逐漸減弱，運行速度將隨著處理器數量的增加而迅速提升

* Instruction Set Architecture（ISA）
電腦大致可分為軟體及硬體，電腦的結構及組織是由指令集結構(Instruction Set Architecture)及機器組織(Machine Organization)組成
ISA是軟體及硬體間的介面，當軟體有需求時，會透過硬體專屬的ISA去呼叫硬體做事，如果在不同時期的電腦使用的ISA相同，則軟體在兩台電腦上都可正常執行
Architecture為較高階，如Processor、Memory和I/O System
Organization為較低階，了解元件功能、描述實際硬體的表示法

* 電腦層次
Application Software : 使用高階語言寫成。
Systems Software : 把程式編譯成機器語言，控制I/O處理記憶體，排程工作、分享資源。(系統程式、loader)

* Instruction Set特性
RISC(reduced instruction set computer)
指令集是比較簡單的 (一個指令可能做一件事)

CISC(complex instruction set computer)
指令集是比較複雜的 (一個指令可以做很多件事情)
-> 需要花的instruction count的個數可能比RISC少 -> 執行時間較長

* Organization處理器本身的架構
Single cycle
Multi cycle
Pipeline
-> 對於CPI造成影響，也對應到clock frequency and clock rate

* 半導體（Semiconductor）
決定現今IC跑得多快 -> 讓電腦跑的更快

* Power Wall
電壓不能太小，會造成訊號不穩定，雜訊可能會比真正的訊號還大
散熱不佳，晶片面積太小不利於散熱，因此晶片沒有辦法再小

Solution :
可以採用多處理器(Multiple Chip)，但須要改寫程式碼，或是採用多核心(Multicore)

* SPEC(Standard Performance Evaluation Corp)
讓電腦跑兩個程式看回應時間等各項數據來評估電腦效能

## CPU Time
* 電腦最基本的執行單位
最核心的部分就是processor，而處理器的工作完全是依據使用者給它的命令，再依照這些命令來產生對應的行為，而這些命令我們叫做 instruction(指令)

* CPU Time計算
CPU Time = CPU Clock Cycle * Clock Cycle Time = CPU Clock Cycle / Clock rate

* Clock Cycles 計算
Clock Cycle = Instruction Count * Cycle per Instruction

* CPU Time（結合Clock Cycle計算）
CPU Time = Instruction Count * Clock per Instruction * Clock Cycle Time
-> 一個程式裡面有多少個指令 X 每一個指令需要多少個clock cycle來執行 X 每一個cycle花多少的時間

* 最基本的指令需要幾個時間單位的執行時間?
Ans : 不一定

Case 1:
加法跟乘法所需要的執行時間是不同的，因為乘法比加法更複雜

Case 2:
不同的處理器設計技術，single cycle, multi cycle或者pipeline，採用這些不同的設計技術，每一個基本指令所需要的執行時間，時間單位都可能不盡相同

## Instruction Set Architecture, ISA
* MIPS(Million instructions per second)
Def. a measure of a processor's speed

Design principle
1.Simplicity favors regularity(簡單、有規律)
2.Smaller is faster(小就是快)
3.Make the common case fast(讓常用功能更快)
4.Good design demands good compromises(好的設計需要好的取捨)

* Instruction Format
R-type(All Register)

I-type(Have Immediate)

J-type(Support Jump)

* Register
處理器在運算的時候主要都是透過操作register
1.共有32個通用型register，每個register有32 bit (design principle 2)
32 bits是基本操作單位 -> 稱為一個word
每個register都有一個編號(0~31)，也能透過命名給register名字
2.32個浮點數型register，每個register也有32bit
3.特殊運用register -> HI, LO, PC

Pros:
register已經在processor硬體裡面，所以比從memory存取還快
可提供compiler將高階語言轉換成低階組合語言時，一些常用的資料讓他可以暫時存放
可將常用資料存放在register，減少processor與memory的溝通
可改進code density

* Register architecture
1.accumulator(只有一個register) : 做完再存回自己
2.stack : 操作都要在stack裡面，answer後再pop出來
3.GPR(general purpose register) : 可以任意把資料取出來做運算再放回去
4.Load/Store(GPR的變形)
所有跟processor有關的運算，operands都要在register裡面進行。
若要對記憶體進行運算，只能透過Load/Store將資料從記憶體取出放到暫存器再重新運算
只有Load/Store必須在register內運算，其他架構沒有
MIPS就是一種Load/Store架構

不同架構下執行C=A+B的組語

* Register Operands
在MIPS裡面它的運算速度和processor運算時脈一致
MIPS指令全部都是32bit -> design principle 1

* Immediate Operands(常數運算元)
當需要使用到常數時，processor必須要時常與memory進行資料溝通，所以為了提升效率，就把常用的常數嵌入在register裡

I-Format (Immediate Frmat)
Ex: addi(add immediate)
addi $29,$29,4
把29號暫存器裡面的值跟4常數相加，加完的結果再把它放回到29號暫存器裡面
Design Principle 3 -> 盡可能把常用的情況加速

I-Format vs R-Format
1 Op 2 Reg 1Imm vs 1 Op 3 Reg
一個是immediate type，一個是register type

0在程式內經常被用到，必須要放在很快的位置，所以在MIPS insttuction中，規定register 0的值恆為0並且不能變更
Ex: addi $0,$0,5不會發生任何作用 -> register 0無法被變更

* Represent instruction
Key Idea:
assembly != instruction
人 -----------> processor
assembler
assembly與instruction set還是有差異

Instruction Word :
instruction是由32 bits所組成，而每一個instruction word會把分成好幾個不同的fields，這些fields會分別的告訴processor需要處理的事情
在MIPS裡分成R、I、J format

R-Format(All Register)
表格上的數字為每個fields所需的bits

1.opcode(operation code)
Def. 做的事情是甚麼
在MIPS裡，所有R-format的instruction opcode都為0

2.rs(first resource register number)
Def. 處理第一個operand

3.rt(second resource register number)
Def. 處理第二個operand

4.rd(destination register number)
Def. 將指令完成的結果存入的register

5.shamt (shift amount)
Def. 提供給shift的指令使用
在MIPS內，任何R-format的instruction只要不是shift，那麼shamt=0

6.funct(function)
Def. 在MIPS的指令集裡面，由於R-format的opcode都為0，因此需要搭配0的opcode再加上function，才能夠決定這個R-format的指令要做的事情是什麼

I-format(Have Immediate)
1.opcode(operation code)
Def. 做的事情是甚麼
在MIPS裡，所有R-format的instruction opcode都為0

2.rs(resource register number)
Def. 這個指令要處理的operand

3.rt(destination register number)
Def. 將指令完成的結果存入的register

4.immediate
Def. 將指令完成的結果存入的register
immediate的fields共16 bits，可表示2^16個不同的值，實際處理時會做sign entension變成32 bits，所以就能跟register一起運算
Design Principle 4
Ex:

* Stored Program
每個processor都有一個counter program register，去指向現在要執行的程式在記憶體的位址
想法: 把常用的程式像資料一樣放在memory，需要時才去存取，不論instruction or data，都能在memory做access

作法:
想要執行某個程式
1.把program load在memory
2.用register指向想要執行的program
3.CPU執行program

執行其他程式
1.更改register指向其他想要執行的程式
2.CPU執行program
Pros: 簡易操作、快速、CPU效能提升
-> 檔案概念由此誕生

* 高階語言 vs 組合語言
動作解析 :
1. 把變數b從記憶體取出來，放到r1暫存器
2. 把常數5取出來，放到r2暫存器
3. 暫存器r1的值加上暫存器r2的值，放到暫存器r3
4. 暫存器r3的值取出來，放到記憶體變數a的位置

* Code density
4GB的資料=需2^32 bits
32個register=需2^5 bits

* Memory Operands
把資料從記憶體搬移到暫存器，告訴processor從記憶體哪個位址搬資料到哪個register
記憶體可視為一維陣列，以pointer存取
offset偏差值，以pointer作為基礎
Ex: 8($t0)
T0 = base register
8 = 8 bytes
有效記憶體:
register總長為32 bits (8 bytes * 4 = 4 32 bits)
實際上MIPS架構長度為32 bits (2^32 = 4GB)

Instruction:
lw (load word)
把一個word從記憶體搬移到暫存器
lw $t0,12($s0)
lw / destination / offset / base register
把暫存器s0的值再加上12個bytes當成是一個記憶體的位址，把它的值放到t0這個暫存器裡面

sw (store word)
把資料從register搬回memory (資料單元方向顛倒)
sw $t0,12($s0)
sw /destination /offset /base register
sw把t0這個暫存器裡面的值移動到，以s0當成base再加上12個bytes作為Offset所得到的記憶體位址

* byte address vs word address
1 word = 4 bytes
每一個小方塊代表的是一個byte，而相同顏色的4個小方塊代表的是一個word
把它們的記憶體位址用二進位的表示法來表示出來，byte address和word address相差四倍(2^2)，所以在byte address裡面最低位元的兩個bit一定都會為0

* Alignment
所有word被擺放到記憶體時，一定會是4 bytes的整數倍(1 word = 4 bytes)

* Endianness
word存放在記憶體是4 bytes，所以擺放時有一定的順序，分成big endian and little endian
Big Endian: 把最高位元放在word起始位址
Little Endian: 把最低位元放在word起始位址

Ex: 現有一組data，0A 0B 0C 0D

* Signed and Unsigned Numbers
Unsigned Numbers(無負號)
Ex: 若有一 4 digit 10進位系統，可表達範圍 0~9999

Signed Numbers(有負號)
1.Signed Magnitude
用一個bit代表負號
1負0正
Ex:
111代表-3
最左邊的1是最高位拿來判斷正負

2.complement(補數)
1's complement :
如果原本的數字是1
那麼他的logic complement就為0
反之 如果是0
那麼他就會是1
Ex:
000的complement就是111
->不論方法1 or 2，都會出現+-0，無法使用傳統的加法器unsigned address

2's complement
用里程的概念，假設99 mile往前1 mile = 100 mile，但在2進位下，100是進位可以忽略，所以就會變成00，而0 mile後退1 mile也因為借位，雖然為-1，但實際上為99 mile

用里程概念設計負數
1.環狀結構
既然99+1=0，那麼就可以將0放在中間，而99 98…當作負數

2.100為-4
低位元為0時是正數，高位元為1時是負數
特性: 低位元為正數，高位元為負數，高低相加可得有號數

* Sign Extension
Ex: 3bits extend to 4bits
當想要把資料從位元小的空間搬到位元大的空間時，要做sign bit的延伸，複製最大位元確保數字最後是一樣的

## Computer Arithmetic
* ALU(arithmetic logic unit)
處理器裡面的算術邏輯單元
需要ALU的instruction:
add/sub
and/or/nor
slt(set on less than)
兩個register的大小可用一個減法達成，透過得出數字為正數或負數

* 設計ALU
Design Trick 1 : divide and conquer(做分化)
-> 加法進位，各個bit分開再進位(carry)
Design Trick 2 : solve part of the problem and extend(解決部分問題再延伸)
-> 先做出and/or/add/sub後來再擴充slt/nor

* 加法/or/and實現

* 減法實現
被減數維持不變，把減數拿來取2's complement，再跟被減數相加
最高位元: 檢查有沒有overflow
最低位元: 發送select signal選擇是否取2's complement(Bnegate)
2's complement: 先把它轉成1's complement然後再加1

* Nor實現
1.nor gate接到ALU裡面的MUX
2.用DeMorgan's Law，在MUX做A與B的2's complement得到A'與B'，再使用and gate即可
DeMorgan's Law : A nor B = (not A) and (not B)

* Carry-Lookahead adder
當多層的組織接在一起，一層一層等太慢了，可以使用Carry-Lookahead adder。簡單來說，有一些位置的數字在不論carry in還沒進來之前就已經進位了，或是即便carry in進來也不可能發生進位的情況，就可以先把carry out往上傳，用這樣的方法可以加快運算速度

* Overflow
兩個正的數字加起來得到一個負的數字，或是兩個負的數字加起來得到一個正的數字

當Overflow發生:
最高位元的carry out是1，最低位元的carry in是0
或是
最高位元的carry out是0，最低位元的carry in是1
只要判斷這兩個bit就能得知是否發生overflow，當xor gate為1時即發生overflow

* ALU Zero實現
把ALU裡面的bit透過nor gate連在一起

* Nor Gate

* Set on Less Than(比大小)
slt是一個R-format的指令
把Rs暫存器以及Rt暫存器的值拿來做減法，如果Rs暫存器的值小於Rt，那麼讓Rd暫存器的值為1，反之讓Rd暫存器的值為0
32個bit的減法只是把整個減法裡面最高位元的值拿來看它是正的還是負的

* Floating Point
floating point representation:
32 bits -> single-precision
64 bits -> double-precision -> 除表達數字範圍大，也有表達精準的位數，即小數點第幾位

IEEE Floating-Point Format(754)

## Processor
* Single Cycle Machine
一個cycle就包含五個執行步驟，因此一個cycle的時間必須以執行時間最長的指令(lw)為準，一個clock cycle只能做一種用途，指令與資料記憶體必須分開

* Multicycle Machine
把一個指令切成五個執行步驟，由於不同cycle做不同的事，指令與資料記憶體可合在一起，只要知道現在哪個cycle就能知道要讀指令還是資料

* Processor執行步驟
1.Instruction Fetch
2.Register
3.Execute(ALU)
4.Memory Access
5.Write Back

* Control unit(控制訊號線)
1.RegDst : 決定是否要Read Addr2
2.RegWrite : 是否寫入Reg
3.ALUsrcA : 控制ALU做PC加法(Branch或Jump指令)或是一般加法
4.ALUsrcB : 讀入的資料是offset、Address或是4、B
5.ALUOP : 告訴ALU要進行的動作是加法、減法或是其他動作
6.PC Source : 控制PC做Jump或是跳下一個指令
7.PC WriteCond : 看比較結果是否要挪動執行位址
8.PC Write : 檢查是要執行下一個指令還是跳到其他地方執行
9.IorD : 讀取Instruction或是Data

* Pipeline
Def. 硬體和邏輯上不衝突的情況下先開始下一個指令，但需要增加硬體，並會產生三大問題

Structural Hazard(硬體衝突)
通常都會直接應加硬體

Data Hazard(資料衝突)
在資料還沒寫回時就被引用，造成資料引用錯誤

解法:
1.Stall
最簡單的解法，等待寫回後再繼續執行，但是如果每個指令都要等待會造成很嚴重的延遲，不能完全靠這樣解決

2.Forwarding
Def. 在所需要的值剛計算完成，就透過線路提前得知並執行，但也有部分指令基本上有forwarding也來不及(還沒決定時就要執行)， 這樣的狀況就真的只能stall
基本上透過Stall及Forwarding可以解決大部分的Data Hazard

Forward unit : 儲存之前的rd跟現在正在使用的rt及rs比較，如果有發現一樣代表需要進行forwarding，如果前面兩個rd都跟現在的rt rs一樣，則要拿最晚產生的值。(更新資料)
Hazard unit : 判斷是否有Hazard發生，如果有Hazard發生，會阻止Instruction Fetch讀入下一個指令，並且向Control unit發出noop，清空控制訊號線以達成stall

Control Hazard
Def. 在Jump的判斷還未決定前就先行執行指令造成的錯誤

解法:
1.forwarding
2.stall : Control Hazard所使用的stall不太一樣，由於Control Hazard抓錯的指令必需要洗掉重抓，所以會插入noop。
3.delay decision : 用compiler排程把無關的指令插入stall掉的空間內，以減少stall所產生的損失。(完全軟體技術)
4.static branch prediction : 先猜一個，如果猜錯了再洗掉重抓就好。但是由於猜法都是固定一種，如果遇到迴圈判斷的位置不同，猜錯的次數會變很多。
5.dynamic branch prediction : 隨進程改變而猜不同的結果，通常會需要額外硬體輔助。
6.branch history table(BHT) : 用Predictor記錄跳或不跳的狀態，如果上次有跳記1;反之記0，但只有BHT不夠。除了記跳或不跳，還記住指令、跳去哪裡，如果遇到一樣的指令，除了猜跳，連跳去哪裡都知道。(目前最常用)

Dealing with exception(OS)
分為兩種，一種為內部指令構成(Traps)，一種由外部事件構成(Interrupt)

1.R-type overflow
2.undefined instruction
3.I/O device request
4.OS request
5.Hardware malfunction
除最後一個是硬體例外，其餘都是軟體例外，處理方式為趕快處理手邊的工作，將例外移出處理後，再繼續向下做
## Memory
* 記憶體
Def. 記憶體為存放指令、資料及程式碼的地方。
Memory在近年加速的幅度遠不如Processor加速的幅度，造成可能拖累Processor的現象，整體效能改善不了多少。(木桶效應)
[[組裝入門] 電腦組裝中的木桶效應 (CC中文字幕)](https://www.youtube.com/watch?v=UIP9T8HTlFk)

* N-way Set Associative
Def. n-way，是指將Cache分成n個組(set)，每一組對應一個位址。 也就是說一個位址可以映射到n個Cache Line中。和Direct Mapped很像，不同點在於在一組(set)中，第一個沒找到，可以找下一個，直到該組的最後一個

* Memory Hierarchy
越上層的速度越快、容量越小
Inclusive: 上層的資料在下層一定可以被找到

* One Word Wide Memory Organization
一個block一個word -> 浪費時間資源在搬運資料
一個block四個word -> 能夠稍微改善幅度，但改善幅度有限
Page Mode DRAM -> 把整個row搬進去，改善幅度較明顯

* Interleaved Memory Organization
一次有多個Memory Bank去處理，一次先對4筆資料進行request，再一次去接收

* Cache
Def. 用SRAM製成，容量小、密度小，但速度較DRAM快。程式碼本身並不知道Cache的存在，搬動是靠硬體執行。

Locality
Teamporal Locality: 存取過的資料短時間內可能再度被存取
Spatial Loacality: 存取過資料的附近資料可能一起被存取
Cache能實現就是因為有Locality

Direct Mapped Cache
檢查Tag及Valid，如果都是1表示這個值可以再Main Memory找到
1.一個block只有一個word，對附近的值沒有影響，只有Temporal Locality
2.如果一次有多個word一起被搬入，就同時用到Temporal及Spatial Locality

Cache Miss
1.Compulsory : 第一次Search一定是Miss(因為Cache是空的)。
2.Conflict : 同一個indexed的值只能放在固定的位址，造成資料搶位置，可以透過增加空間，或者讓空間彈性(Full Associative)
3.Capacity : block太大，造成cache一次放不下太多，容量不足

Write Back/Through
Write Back Cache: 允許寫回Cache就好，不每次都寫回Main Memory，但是當再次取用前一定要寫回
Write Through Cache: 每次都必須寫回Main Memory及Cache
Write Buffer: 只寫到buffer，程式就會以為已經寫回而繼續執行下去，再慢慢寫回Main Memory，可以節省時間，但是寫入的頻率不能太高。

Average Memory Access Time(AMAT)
AMAT = HitTime + MissRate * MissPenalty

針對miss rate改善cache效能
1.Fully Associative Cache
讓放的空間彈性一點，允許Block放在Cache任何一個位址，但搜尋較花時間，造成HitTime不太好看。較折衷的作法為N-way Set Associative

2.Multiple Levels Cach
使用多層的Cache，每一層的目的都不同，每一層改善的方向也不同

* Classical DRAM Organization
一次會讀取每一面的同一個位置

Classical DRAM Operation
一般的DRAM讀寫必須要讀一次Row Address及一次Column Address，會有一個RAS提醒要讀Row Address及一個CAS提醒要讀Column Address，兩者會在Address讀到一半時降下來

Page Mode DRAM Operation
讀取同一個Row的資料，不需要重複讀Row，節省時間（same row, different columns）

Synchronous DRAM Operation
只要指定讀一個位址，就能讀該位址的連續資料，但需要clock

* Virtual Memory（Backing Store）
執行一個大型程式不一定要把所有的程式碼跟資料都搬入，可以等到要用到的時候再搬入就好。Virtual Memory就是一個可以讓程式以為程式碼都已經搬入的虛擬空間
程式內會有虛擬位置，換成真正的位置去找資料(page table)，如果在Main Memory找不到資料，就代表發生Page Fault，必須進行Page Replacement將部分Page放回硬碟（swap out），並把必要的Page放到Main Memory存取（swap in）

TLB放在Memory內，用來記錄目前Process的狀態，如果需要找Victim Page時，可能會使用LRU(Least Recently Use)近似法則，意指最先替換掉最近最久沒有使用的Page，這時候reference bit and modification bit就會派上用場

## I/O System
* I/O System
Def. I/O裝置包含如鍵盤、硬碟及網路，任何可傳輸資料輸入輸出的部分。
I/O Bandwidth : 單位時間所能傳輸的資料量。
I/O Response Time : 完成工作回應的時間。
-> 兩者兼顧最佳

* Bus Characteristics
Control Lines
專門用於傳輸request及指示需要回傳什麼樣的資料

Data Lines
回傳資料、位址或複雜指令

Control + Data = transaction
匯流排是有東西接在上面進行傳輸才叫匯流排，否則就只是一堆線路

* Type of Buses
1.Processor-Memory Bus(proprietary) : 不同廠牌的不同，每個廠牌有每個廠牌專屬的
2.I/O Bus : 不同廠牌通用(如USB)
3.Backplane Bus : 為I/O Buses 及 Processor-Memory Buses的中介者角色，長、慢但便宜

* Synchronous and Asynchronous
Synchronous Bus: 如Processor-Memory Buses，由指令控制I/O，有clock
Asynchronous Bus: 如I/O Buses，利用Interrupt來觸發，不需要clock，但是相對較慢

* Bus Arbitration
期望匯流排可以讓高Priority的優先拿到，但低Priority的不至於完全拿不到，因此有arbitration

Daisy Chain Bus Arbitration:
無法確保低優先權的可以拿到request，Ack也是一個一個傳，效率不好

Centralized Parallel Arbitration
每個裝置都有各自的request線，用於較高速的cpu匯流排

* Typical I/O System
如果匯流排越長、裝置越多則越快不了

* Two-Bus System

* Three-Bus System（主流）

* I/O裝置與Processor的溝通
1.Polling: CPU主動I/O需求，但會浪費資源，用於低時系統
2.Interrupt: 藉由I/O interrupt告知CPU處理，但會需要額外硬體
3.I/O Controller: 是一個Special Purpose的CPU，專門用於搬運I/O資料，不用CPU自己去搬