# 計算機組織與計算機結構(資料統整)
以下為本人大二、大三上修計算機組織與計算機結構的統整資料。

## ISA
電腦大致可分為軟體及硬體，電腦的結構及組織是由指令集結構(Instruction Set Architecture)及機器組織(Machine Organization)組成。
Instruction Set Architecture為軟體及硬體間的介面，當軟體有需求時，會透過硬體專屬的ISA去呼叫硬體做事，如果在不同時期的電腦使用的ISA相同，則軟體在兩台電腦上都可正常執行。
Architecture為較高階，如Processor、Memory和I/O System。
Organization為較低階，了解元件功能、描述實際硬體的表示法。
## Moore'as Law
每隔兩年，一個晶片所能放的電晶體個數double，因製程改善推動科技進步，是電腦革新的推手，但近年逐漸變慢，這點在後面會提到。
## 電腦層次
在硬體和Systems Software中間還有一層，這層就是ISA。
**Application Software** : 使用高階語言寫成。
**Systems Software** : 把程式編譯成機器語言，控制I/O處理記憶體，排程工作、分享資源。(系統程式、loader)
## 比較兩電腦效能
注重在運行時間，比較兩電腦跑同一個程式所花費的時間。
**Elapsed Time** : 所有回應的時長。
**CPU Time** : 只關注CPU，不管I/O回應時間等花費。
**Clock Period(clock cycle time)** : 一個clock cycle所花費的時間。
**Clock Frequency(clock rate)** : cycle per second。

### 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 = IC * CPI * CCT

## Power Wall
由於 :
1. 電壓不能太小，會造成訊號不穩定，雜訊可能會比真正的訊號還大。
2. 散熱不佳，晶片面積太小不利於散熱。
因此晶片沒有辦法再小。
Solution :
可以採用多處理器(Multiple Chip)，但須要改寫程式碼;或是採用多核心(Multicore)。
## SPEC(Standard Performance Evaluation Corp)
讓電腦跑兩個程式看回應時間等各項數據來評估電腦效能。
## Amdahl's Law
可以用簡單的例子來解釋。
要從台北到高雄，有很多種方法，可以假設從高雄火車站到目的地及從出發地點到台北火車站這兩段路是沒有辦法加快的，中間的路程是可以被加快的。(坐高鐵、自強號、莒光號等)，不同的加速因子可以得到不同的加強。
因此可以發現，加速是有極限的，了不起就是把可影響的時間變成0，不可能讓不能影響的時間也消失。
這個部分看起來較複雜，但其實十分的簡單，只要將F想成可以被加速的部分，X當成加速因子，可以讓這段時間少多少倍就可以了。
## MIPS(RISC)
設計原則:
1. 簡單、有規律。
2. 好設計需要好取捨
3. 越小越快
4. 讓經常用到的功能變快
### Register
### Instruction
指令主要分成三種分類 :
#### R-type
#### I-format
#### J-format

更多指令集可上網搜尋。
補充 :
**System Call** : 一般程式並不能直接進行I/O，必須透過system call使用作業系統的API讓作業系統做。
**Pseudo instruction** : 偽指令，不是真正的指令，而是用一串指令幫你模擬。不會產生任何工作碼。
## ALU
為Processor中的運算單元可進行加法、減法、比較等功能。
包含一個And Gate、Or Gate及1-bit的加法器(如下圖所示)
如果要做減法，則在輸入端做一次二補數。
當要進行A-B時，會將全部的B變成Binvert，(1's Complement)並且讓Cin變為1(2's Complement)。
## Overflow Detection
當兩正數相加時，由於MSB皆是0(二補數)，因此如果MSB的Carry in不等於Carry out，表示有溢位。
如上圖所示，兩正數相加變成負數，及兩負數相加變成正數，都是溢位的表現，用這個方法就可以偵測出來。
## Carry-Lookahead adder
當多層的組織接在一起，一層一層等，這樣太慢了，可以使用Carry-Lookahead adder。簡單來說，有一些位置的數字在不論carry in還沒進來之前就已經進位了，或是即便carry in進來也不可能發生進位的情況，就可以先把carry out往上傳。用這樣的方法可以加快運算速度。
## IEEE Floating-Point Format
這個部分在計概就已經教過，在這邊就不特別贅述。
到這邊為止，計算機組織的部分已經算告一個段落了，附上一張MIPS ISA的部分。
## Processor
這個部分的範圍很大，很多部分的東西會帶過，只講大重點。
### Processor大致上執行步驟
1. Instruction Fetch
2. Register
3. Execute(ALU)
4. Memory Access
5. Write Back
大致上分成這五個步驟。
### Single Cycle Machine
由於一個cycle就包含上面五個步驟，因此一個cycle的時間必須以執行時間最長的指令為準(lw)。一個clock cycle只能做一種用途，因此指令記憶體和資料記憶體必須要分開。
### Multicycle Machine
把一個指令的執行切成上面五個小步驟，分別進行，也由於不同cycle做的是不同的事情，資料跟指令的記憶體可以合在一起(只要知道目前是在哪個cycle就知道要讀指令還是讀資料)。
### 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
雖然Multicycle Machine的每一個step也可以切得更小，但由於邊界效應的影響，並不總是可以增加效能，因為切越多就需要越多硬體支援，硬體傳輸也需要時間。
Pipeline的定義即在硬體和邏輯上不衝突的情況下先開始下一個指令，但需要增加硬體。
但可能會發生問題，主要問題三大類。
#### Structural Hazard
硬體衝突，通常都會直接應加硬體。
#### Data Hazard
在資料還沒寫回時就被引用，造成資料引用錯誤。
**Solution**
1. stall : 

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

在所需要的值剛計算完成，就透過線路提前得知並執行，但也有部分指令基本上有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
在Jump的判斷還未決定前就先行執行指令造成的錯誤。
**Solution**
1. Forwarding(略)
2. Stall : Control Hazard所使用的Stall不太一樣，由於Control Hazard抓錯的指令必需要洗掉重抓，所以會插入noop。
3. Delay Decision : 用compiler排程把無關的指令插入Stall掉的空間內，以減少Stall所產生的損失。(完全軟體技術)
4. Static Branch Prediction : 先猜一個，如果猜錯了再洗掉重抓就好。但是由於猜法都是固定一種，如果遇到迴圈判斷的位置不同，猜錯的次數會變很多。
5. Dynamic Branch Prediction : 隨進程改變而猜不同的結果，通常會需要額外硬體輔助。
**Branch History Table(BHT)** : 用Predictor記錄跳或不跳的狀態，如果上次有跳記1;反之記0。但只有BHT不夠。(下圖示為2-bit Predictors)
**Branch Target Buffer(BTB)** :
除了記跳或不跳，還記住指令、跳去哪裡，如果遇到一樣的指令，除了猜跳，連跳去哪裡都知道了。(現在常用的)。
### Dealing with Exception
Exception又分成兩種，一種為內部指令構成(Traps)，一種由外部事件構成(Interrupt)。
1. R-type overflow
2. undefined instruction
3. I/O device request
4. OS request
5. Hardware malfunction
除了最後一個是硬體例外，其餘皆是軟體的例外，處理方式都是盡快將手邊工作做完，將例外移出處理後繼續下向做。
## Memory
記憶體為存放指令、資料及程式碼的地方。
Memory在近年加速的幅度遠不如Processor加速的幅度，造成可能拖累Processor的現象，整體效能改善不了多少。
### Cache
用SRAM製成，容量小、密度小，但速度較DRAM快。程式碼本身並不知道Cache的存在，
搬動是靠硬體執行。
#### Locality
**Teamporal Locality** : 存取過的資料短時間內可能再度被存取。
**Spatial Loacality** : 存取過資料的附近資料可能一起被存取。
Cache能實現就是因為有Locality
#### Direct Mapped Cache
檢查Tag及Valid，如果都是1表示這個值可以再Main Memory找到。一個block只有一個word，對附近的值沒有影響，只有Temporal Locality。
如果一次有多個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** : 只要寫到這裡，程式就會以為已經寫回而繼續執行下去，這裡再慢慢寫回Main Memory，可以節省時間，但是寫入的頻率不能太高。
#### Average Memory Access Time(AMAT)

AMAT = HitTime + MissRate * MissPenalty

如果要改善Cache的效能，必須從這幾個點下手去改善，但是如果改善一個必定會讓另外兩個的表現受到影響，因此要謹慎評估。
1. Reduce Miss Rate #1 : 讓放的空間彈性一點，可以使用Fully Associative Cache(允許Block放在Cache任何一個位址)，但搜尋時會比較花時間，造成HitTime不太好看。較折衷的作法為N-way Set Associative。
2. Reduce Miss Rate #2 : Multiple Levels Cache，使用多層的Cache，每一層的目的都不同，每一層改善的方向也不同。
### Memory Hierarchy
越上層的速度越快、容量越小。
**Inclusive** : 上層的資料在下層衣錠可以被找到。
### Classical DRAM Organization
一次會讀取每一面的同一個位置
### Classical DRAM Operation

一般的DRAM讀寫必須要讀一次Row Address
及一次Column Address，會有一個RAS提醒要讀Row Address及一個CAS提醒要讀Column Address，兩者會在Address讀到一半時降下來。
### Page Mode DRAM Operation
讀取同一個Row的資料，不需要重複讀Row，節省時間。
### Synchronous DRAM Operation
指定一個位址讀連續的資料，只要讀一次位址，但是需要clock。
### One Word Wide Memory Organization
如果一個block一個word，一次只搬近一個word，會浪費很多時間在搬運資料。
但如果一個block是4個word，能夠稍微改善幅度，但改善幅度有限。
如果使用**Page Mode DRAM**，由於一次把一整個Row搬進來，改善的幅度也會較明顯。
### Interleaved Memory Organization

一次有多個Memory Bank去處理，一次先對4筆資料進行request，再一次去接收。
### Virtual Memory(Backing Store)
執行一個大型程式不一定要把所有的程式碼跟資料都搬入，可以等到要用到的時候再搬入就好。Virtual Memory就是一個可以讓程式以為程式碼都已經搬入的虛擬空間。
程式內會有虛擬位置，換成真正的位置去找資料，如果在Main Memory找不到資料，就代表發生Page Fault，必須進行Page Replacement將部分Page放回硬碟。
TLB為放在Memory內，用來記錄目前Process的狀態，如果需要找Victim Page時，可能會使用LRU(Least Recent Use)，意指最先替換掉最久沒有使用的Page，這時候reference bit就會派上用場
。
## I/O System
I/O裝置包含如鍵盤、硬碟及網路，任何可傳輸資料輸入輸出的部分。
**I/O Bandwidth** : 單位時間所能傳輸的資料量。
**I/O Response Time** : 完成工作回應的時間。
希望能兼顧Response Time及Bandwidth。
### Typical I/O System
如果匯流排越長、裝置越多則RC越高，越快不了。
### Bus Characteristics
**Control Lines**是專門用於傳輸request及指示需要回傳什麼樣的資料;**Data Lines**則是回傳資料、位址或複雜指令。這個過程叫做Transaction。
匯流排是有東西接在上面進行傳輸才叫匯流排，否則就只是一堆線路。
### Type of Buses
1. Processor-Memory Bus(proprietary) : 不同廠牌的不同，每個廠牌有每個廠牌專屬的。
2. I/O Bus : 不同廠牌通用(如USB)
3. Backplane Bus : 為I/O Buses 及 Processor-Memory Buses的中介者角色，長、慢但便宜。

**Two-Bus System**

**Three-Bus System**(主流)
### Synchronous and Asynchronous
**Synchronous Bus** : 如Processor-Memory Buses，由指令控制I/O，有clock。
**Asynchronous Bus** : 如I/O Buses，利用插斷(Interrupt)來觸發，不需要clock，但是相對較慢。
### Bus Arbitration
期望匯流排可以讓高Priority的優先拿到，但低Priority的不至於完全拿不到，因此有仲裁。
#### Daisy Chain Bus Arbitration
無法確保低優先權的可以拿到request。Ack也是一個一個傳，效率不好。
#### Centralized Parallel Arbitration

每個裝置都有各自的request線，用於較高速的cpu匯流排。
### I/O裝置與Processor的溝通
1. **Polling** : 一段時間cpu主動查詢一次，超級浪費時間，因為太浪費時間了根本沒人在用。
2. **Interrupt** : 藉由I/O插斷告知CPU處理，但會需要額外硬體。
**I/O Controller** : 是一個Special Purpose的cpu，專門用於搬運I/O資料，不用cpu自己去搬。
到這裡為止，兩個學期的課程就結束了。