# 計算機結構

[黃婷婷教學](https://www.youtube.com/playlist?list=PLzVMIgd7ZHf92iTMYpgtPhmVNbbuI9VzQ)

## CH1 Computer Abstractions and Technology
* 1.**Moore's Law**：積體電路上可容納的電晶體（電晶體）數目，約每隔兩年便會增加一倍。由Intel創始人之一戈登·摩爾（Gordon Moore）提出來的，有預測認為摩爾定律的極限將在2025年左右到來。
* 2.因為Moore's Law，使得很多現代便利科技的出現。如汽車中的電腦、手機、WWW、搜尋引擎...
* 3.電腦的種類：
* 個人電腦：Cost/Price 的 trade off，最 general
* 伺服器電腦：高容量、高效率、高穩定，network為基礎
* 超級電腦：高端科學工程運算。
* 嵌入式電腦：較嚴格的電源/效率/花費限制。
* 4.The post PC era後個人電腦時代：蘋果公司提出，描述2010年代以後平板電腦與智慧型手機取代傳統設備，並促進雲計算的移動和跨平台的 Web 應用程序
* Personal Mobile Device(PMD)
* Cloud computing：
* 如WSC(warehouse scale computer)當作data center，用來處理巨量資料
* SaaS(Software as a Service)通過Internet提供軟體的模式
* Amazon、Google...
* New type：一部分在PMD跑一部分在Cloud跑
* 5.八個好主意(學習計算機結構所要了解的核心)：
* Design for **Moore’s Law**：電腦運算越來越有快，保持一個穩定的速度。
* Use **abstraction** to simplify design：透過model或image來表示最重要的部分，不需要把detail都講清楚。
* Make the **common case fast**：更有效地使電腦變快。
* Performance via **parallelism**：平行運算，可以同時處理多件事情。
* Performance via **pipelining**：管線化運算，減少idle的時間。
* Performance via **prediction**：判斷錯誤的代價不太高時，可不一定要等到該指令發生就預做判斷。
* **Hierarchy** of memories：就是在傳輸速度，和售價，和體積大小之間trade off，不同的狀況會有不同的是和存取方式。
* **Dependability** via redundancy：透過預先多存取一份來保持穩定性，有時還可以增加存取的效率。
* 6.Program在哪執行：
* **Application software**：Our code, written in high-level language
* **System Software**：Compiler, Operation System, Compiler, Loader, Assembler
* **Hardware**：Processor, Memory, IO...
* 7.Program code種類：
* **High Level Language**：如c code，給programmer看得，好理解。
*
* 經過Compiler
*
* **Assembly Language**：用文字呈現機器上實際做的事情。
*
* 經過Assembler
*
* **Hardware Representation**：Binary code,代表 指令 或是 資料。
* 8.電腦Component
* 幾乎所有的電腦都有一樣的架構
* **CPU**：中央處理單元
* **datapath**
* **control**：用來控制datapath如何在memory存取。
* cache memory(SRAM)：快但貴。
* **Memory**：記憶體
* **I/O**：輸入輸出裝置
* User-interface device
* storage device
* network adapter
* 9.IC晶片的生產
**Silicon ingot**-->Slicer-->**Blank Wafers**-->20~40steps-->**Patternd Wafers** -->TEST
wafer：晶圓
die：晶粒，晶圓中一小單位。
Cost per die = $\frac{Cost~per~wafer}{dies~per~wafer~\cdot ~Yield}$
Dies per wafer = $\frac{Wafer~area}{Die~area}$
Yield(良率) = $\frac{1}{(1+(Defects~per~area\times~Dies~Area/2))^2}$
* 10.Performance好壞，要看目的來決定要比較甚麼。常見電腦的performance標準有：
* Response Time：完成一件工作所需要時間。
* ThroughPut：單位時間可以完成多少工作。
如果把processor速度加快-->兩個都會變快
如果只增加更多processor-->RT不會變短，但TP變快
**使用者會重視Response Time，而服務提供者則會重視ThroughPut。**
* 11.再比較不同電腦(演算法)的performance時，我們可以**定義Performance = 1 / Execution Time**。和執行時間成反比，所以執行時間越長，performance越差。執行時間標準：
* **Elapsed Time**：各種CPU執行、I/O、IDLE時間總和，
* **CPU Time**：只計算CPU在此工作的執行時間，又分為user/system CPU time。
* 12.CLOCK時脈：電位從高變低在變高往復的過程。
* Clock Period(Clock Cycle Time,T~c~)：一個clock cycle的時間長度。
* Clock frequency/rate：每秒有幾個clock，代表CPU是幾HZ。
* (上面兩項互成倒數)
* **一個程式的CPU TIME = CPU Clock Cycles \* Clock cycle time**
**= CPU Clock Cycles / Clock Rate**
* 增加performance可以透過減少cycle數量 或是 增加clock rate來達成
* 硬體設計時需要trade off 處理器頻率(Clock Rate)和cycle count(cycle數量)，來達到最好效率，因為不太可能頻率很快然後cycle又很少。
* 13.Instructions Count and Cycles per Instruction(CPI)
* Instruction count指的是一個程式所需要的指令數量。
* Instruction count和**program本身設計、ISA規定的結構、及compiler的優化**有關。(所以演算法設計的再好，沒有好的硬體配合，performance也不會提升。)
* CPI指的是每個指令所需要的cycle數，通常每個指令會不一樣，所以我們會做**平均**。
* 比方說這隻程式的CPI，指的就是這支程式在CPU執行時的總cycle數/總指令數。
* $CPI=\frac{Clock~Cycles}{Instruction~Count}=\frac{\sum CPI_i~\times~Instructions~Count_i}{Instructions~Count}=\sum (CPI_i\frac{Instructions~Count_i}{Instructions~Count})$
* 14.Performance
* By 13 and 14,
* $CPU~Time~=~\frac{Instructions}{Program}\frac{Clock~Cycles}{Instructions}\frac{Seconds}{Clock~Cycles}$
* Algorithm：affects IC, CPI
* Language：affects IC, CPI
* Compiler：affects IC, CPI,Tc
* 15.Power
* 電路在設計時，也應該考慮電腦的耗電情形
* 尤其是在現在需要大量的運算能力做AI training，大量主機時，節省10%就可以節省好幾千萬焦耳
* 地球上的能源是有限的
* 現在的CPU大概可以做到平均2~3GHZ，尖峰4GHZ，而功率從之前的103瓦降到現在大約77瓦
* $Power~=~Capacitive~Load~\times~Voltage^2~\times~Frequency$
* 第一項指的是CPU中有多少東西需要能源。
* 第二項是維持CPU運作所需要的電壓，約在1.5V~1.2V之間，電壓越低會造成電路越不穩定，會出現0便1或是1變0的現象。
* 第三項指的是每秒CPU可以執行多少instructions。
* 16.**The Power Wall**：電路在設計時，會限制電量消耗在一個合理範圍(總不能趨近於無限大)，因此CPU的clock rate總會碰到上限的。
* 單一CPU遇到buttleneck時，仍希望效率繼續在提升，這時可以透過**parallelism**技術。
* Multiprocessor指說在一個chip上放多個processor，目的就是要平行化運算。
* 但實務上要把code運用平行化去執行，需要programmer寫的code形式和電腦本身硬體去配合，一般來說是非常困難的技術。
* (大部分的時候，我們寫的程式就像是音樂裡的獨奏曲，想要用平行化運算，就像是把個種獨奏曲彙編成一首美麗的協奏曲，只有像貝多芬一樣的天才才有可能XD)
* 17.SPEC CPU Benchmark
* 一種衡量CPU效能的方法，讓一些程式在CPU上跑，在和reference machine比較跑的效率差異
* 最後採用geometric mean作為整體表現，因為計算方式是和別台機器比較差異，用比例來看才有意義。
* $\sqrt[n]{\prod_{i=1}^{n} {Execution~Time~Ratio_i}}$
* 18.SPEC Power Benchmark
* 一種衡量Power耗電的方法，會是先給定數個target load 0,10%,...100%。
* 接著看在每個load下的performance(ssj_ops)和耗電(Watts)
* Performance可以看成CPU這時可以執行幾個指令。
* $\frac{\sum~ssj\_ops}{\sum~power}$
* 19.Pitfall and Fallacy就是指說一些常見的誤解
* **Amdahl’s Law**：電腦效能的增進是有極限的，分析時要把電腦分成可以增進效能和不行的兩部分，假設速度增進了n倍，則
T~增進後~ = T~可以增進部分~/n + T~不可增進部分~
* Low Power at Idle **is fault**：事實上現在的設計，電腦的load只剩10%的時候，可能耗電量還是在50%，所以我們平常不用電腦時應該把電腦睡眠或關機，更進一步我們應該要嘗試去改進電腦設計使得耗電和load成正比比較合理。
* Performance and Energy efficiency are unrelated goals **is fault**：有時候在優化performance時會在該程式多耗費一點能量，但這是可以的，因為電腦其他程式部分也仍然在耗電，如果特定程式時間可以縮短，那整體耗電仍會大大降低。 因此優化程式的效率也能達到省電的效果。
* MIPS as a Performance Metric **is fault**：MIPS(Millions of Instructions Per Second)每秒執行幾百萬的指令。我們不能用MIPS來代表電腦速度，因為不同電腦可能用不同的指令及RISC或是RISC，ISA可能不同，得到的instruction count本來就不同了，而且不同電腦跑相同的instruction的時間(CPI\*rate)也會不同。
我們去比較效能時，通常只用execution time的比例去比較，也就是選定一段特定程式在不同電腦跑，比較它們多久可以跑完。
* 20.設計硬體、電路最重要的事情就是，performance越快越好、及Power越低越好。 (其他需要的知識都是為了滿足這兩件事)
* 21.RISC vs CISC
* 精簡指令集計算機(RISC)，ex : MIPS、Arms。
* 希望每個指令很精簡，很常被使用
* 複雜指令用簡單指令組合出，而不另外implement
* 希望總指令數目很少
* 希望每個指令在hardware上implement很快
* **通常clock rate比較高**
* 複雜指令集計算機(CISC)，ex : intel x86, AMD。
* 希望每個指令都有被implement
* 通常clock rate比較低
## CH2 Instructions: Language of the Computer
* 1.**Instruction Set指令集**：CPU能做的所有可能instruction的集合。不同的電腦CPU會使用不同的指令集，但彼此之間仍會有許多共同的特質。
* 2.**MIPS**：課本使用的指令集，是很多embedded system所使用的instruction set，也成為許多現代ISA的典型。
* 複雜指令集計算機(CISC)，ex : x86, AMD。
* 精簡指令集計算機(RISC)，ex : MIPS, Arms。
* 3.MIPS設計原則
* **1.Simplicity favours regularity**
* 大部分的arithmetic operations都是相同型式
* add a b c #a=b+c
* a,b,c都是存在register的資料(指令不可直接處理memory data)
* 就只有兩個source到一個destination
* 有規則讓implement更簡單
* 簡單會讓performance更好(比方可以用pipeline)
* **2.Smaller is Faster**
* 如register比memory比disk快
* 但是快速物件通常比較貴，而且有容量限制
* **3.Make The Common Case Fast**
* 這樣可以有效率的讓效能提升
* 比方說常常用到加一的指令，因此有了 addi r0 r0 1
* **4.Good Design Demand Good Compromise**
* MIPS讓不同instruction有相同長度，而規定不同format來
* 4.Register
* MIPS提供32\*32個bit 的 register file(暫存器堆)
* 當初的晶片體積比較大，而之後為了相容性也沒有更多register的ISA。
* 和bit樹的identify也有關，總之全部會連帶一起設計
* register file是CPU中多個暫存器組成的陣列，通常由快速的static RAM（SRAM）實現
* register是CPU中較快速的存儲單位，通常register可以在一個clock cycle存取，而main memory要在十多個clock cycle才可存取。
* MIPS提供32個32bit的register處理整數和邏輯指令，另外有32個32bit的register處理浮點數。
* 一個32bit data稱為一個"**word**"，也就是4bytes
* \$t0~$t9 for saved value(暫存值)
* \$s0~$s7 for saved valuables(儲存變數)
* 5.Memory
* 儲存composed data(複合資料)：如Array,Structure, Dynamic Data
* 透過Load把memory的資料讀進register
透過store把register的資料存到memory

* **Byte Addressed：每一個Memory Address存8個bit(一個character要4個byte儲存，32bit儲存)**
* MIPS是**Big Endian**：字串的MSB存在memory中位置低的地方。
* int陣列的1個offset代表1個word，如A[1]和A[2]差了32個bit
* Memory的1個offset代表1個byte，所以從這個word讀到下個word(如A[1]到A[2])，memory要移4個offset。
* lw：load word
sw：save word
lb：load binary
sb：save binary
lbu：load unsigned binary
* 比較：
* register速度比memory快很多，且memory需要load,store很多instructions，平常CPU在透過ALU運算時通常會直接取用register的資料，只有在把資料操作完之後才會存回memory。
* Compiler盡量會使用register來做運算，除非是register spilling的情況，也就是register不夠用的情形，才會暫時把register先放回memory。
* 6.Immediate Operand
* 處理某些constant data時，可以直接使用
addi \$s1 \$s2 2
addi \$s1 \$s2 -3
* 但MIPS中沒有提供subi，需要自己使用addi和負數的常數。
* 7.\$zero代表0，有特殊用途，不能更改此rigister的值。在很多operation中很實用，如
* add \$s1 \$s2 \$zero
* 8.常見的整數知識：
* unsigned和signed integer儲存
* 2's complement的負數儲存
* Sign Negation
* Sign Extension
* ( 關於浮點數會比較複雜，這裡先省略 )
* 9.Instruction在機器裡，是用一串binary數字表達，我們稱為**machine code**，其中MIPS的machine code為32 bit。
* 這和總共有32個register有關，這樣要5個bit來確定一個register，而總共32bit來代表一個instruction也很足夠，
* 現在最多也是64bit的指令，再多有點不必要，總之就是各種硬體大小還有實作方不方便的trade off。
* Instruction就像data一樣，是一段由0和1組成的
* Instruction和data一樣，儲存在memory
* 因此program其實可以直接被其他program讀入，並執行。(就像可以直接讀data一樣)
* Binary compatibility：一種性質，代表不同的computer都可以執行相同一段binary code。
* **10.MIPS中的register和OPcode**
* OPcode可以用來區別不同的type，有6個bit共64種可能，
* 其中op=0代表R type，這時要去看funct去看這段指令功能。
* op=2代表J type的j，op=3代表J type的jal。
* op=其他代表為I type。
* register共有32顆用來處理整數
* 0：常數值0
* 1：at，給組譯器用
* 2-3：function回傳值(應付double型態變數)
* 4-7：function參數值
* 8-15：暫存值 ， \$t0~\$t7，caller會去maintain，callee可以直接更改
* 16-23：變數保留值 ， \$s0~\$s7，callee在使用前要先store，return前callee要store
* 24-25：暫存值 ， \$t8, \$t9，
* 26-27：給核心使用
* 28：global指標
* 29：stack指標
* 30：frame指標
* 31：return address
* 11.**MIPS指令集格式**
<table>
<tr>
<td></td>
<td>6</td>
<td>5</td>
<td>5</td>
<td>5</td>
<td>5</td>
<td>6</td>
</tr>
<tr>
<td>R-type</td>
<td>op</td>
<td>rs</td>
<td>rt</td>
<td>rd</td>
<td>shamt</td>
<td>funct</td>
</tr>
<tr>
<td>I-type</td>
<td>op</td>
<td>rs</td>
<td>rt</td>
<td colspan="3">immediate</td>
</tr>
<tr>
<td>J-type</td>
<td>op</td>
<td colspan="5">address</td>
</tr>
</table>

* 12.**各個格式說明**
* **Rtype**
* op：operation code, 指令運算碼
* rs：source register 1, 來源暫存器1
* rt：source register 2, 來源暫存器2
* rd：destination register, 目標暫存器
* shamt：shift amount, 位移量
* funct：function code, 功能碼(Rtype才有)

|指令|機器語言|組合語言|註解|
|-|-|-|-|
|加|0 17 18 16 0 32|add \$16 \$17 \$18|\$16=\$17+\$18|
|減|0 17 18 16 0 34|sub \$16 \$17 \$18|\$16=\$17-\$18|
|AND|0 17 18 16 0 36|and \$16 \$17 \$18|$16=\$17&\$18|
|向左移位|0 0 17 16 5 0|sll \$16 \$17 5|$16=\$17<<5|
|向右移位|0 0 17 16 5 2|srl \$16 \$17 5|$16=\$17>>5|
|小於設定|0 17 18 16 0 42|slt \$16 \$17 \$18|$16=(\$17<\$18)|
|跳到jr|0 31 0 0 0 8|jr \$31|goto \$31|
* **Itype**
* op：operation code, 指令運算碼
* rs：source register, 來源暫存器
* rt：target register, 目標暫存器
* immediate：常數C, 或相對記憶體位置
* 注意到在beq時，要用pc相對位置(距離幾個instruction)
* 在lw,sw時，用記憶體offset(要記得乘以4)

|指令|機器語言|組合語言|註解|
|-|-|-|-|
|相等就跳|4 17 16 25|beq \$16 \$17 100|if(\$16==\$17) goto pc+4+4\*25|
|不等就跳|5 17 16 25|bne \$16 \$17 100|if(\$16!=\$17) goto pc+4+4\*25|
|立即加法|8 17 16 50|addi \$16 \$17 50|$16=\$17+50|
|立小設定|10 17 16 50|slti \$16 \$17 50|$16=(\$17<50)|
|立即AND|12 17 16 50|andi \$16 \$17 100|$16=\$17&50|
|載入word|35 17 16 100|lw \$16 100(\$17)|$16=mem[\$17+100]|
|儲存word|43 17 16 100|sw \$16 100(\$17)|mem[\$17+100]=\$16|
* **Jtype**
* op：operation code, 指令運算碼
* address：跳躍記憶體絕對位址

|指令|機器語言|組合語言|註解|
|-|-|-|-|
|跳躍|2 2500|j 10000|goto位址4\*2500|
|跳躍連結|3 2500|jal 10000|goto 位址4\*2500且\$31=pc+4|
* 13.常見組合語言整理
* 注意到機器語言中目標的register是擺在後面，而組合語言中目標的register是擺在前面(像C一樣)。
* 1.Rtype
* add,or,add,sub
add $16 $17 $18
* sll表示shift left logic左移(不會用到rs)
sll $16 $17 5
* srl表示shift right logic右移(不會用到rs)
srl $16 $17 5
* (另外有sra代表算數右移(除2)，但是沒有sla)
* slt表示set less than
slt $16 $17 $18
* 2.Itype
* andi,ori,addi,subi
addi $16 $17 100
* slti，表示immediate set less than
slti $16 $17 100
* beq，等號成立時跳到label。
beq $16 $17 100
* bne，等號不成立時跳到label。
bne $16 $17 100
* sw,lw，表示從記憶體save,load一個word
lw $16 100($17)
* 3.Jtype
* j，直接跳到label。
j 10000
* jal，跳到label前，同時紀錄下一行位置(PC+4)到\$31。
jal 10000
* 4.其他
* NOT在MIPS是用NOR實作，NOT(a) = NOR(a, 0) = NOR(a, a)，MIPS中沒有提供not的operation
* Conditional Operation： bne, beq, j等等
* 可以用slt搭配bne
* if (\$s1 < $s2) branch to L
* slt $t0, $s1, $s2
bne $t0, $zero, L
* 不用blt,bge的原因，因為lt(<),ge(>)的hardware執行速度很慢，和branch合成同一指令，會使**一個指令的時間太長**，影響其他部分instruction處理的速度。
* sltu, sltui：unsigned integer的版本
* 5.陣列
* 注意下方的offset只能擺數字，所以需要特別處理
*
* 數字陣列：A[0]~A[9]，i 在s3裡，A在s6裡
* 0(\$s6) 代表A[0]
* 4(\$s6) 代表A[1]
* 0(\$s6+4) 代表A[1]
* **0(\$s6+4\*i) 代表A[i]**
* 0(\$s6+4\*\$s3) 代表A[i]
* sll \$t0 \$s3 2
add \$t0 \$s6 \$t0
lw \$t1 0(\$t0)
則就可以把A[i]的值從記憶體位置load到\$t1上面
* 字元陣列
* **0(\$s6+i) 代表A[i]**
* addi \$t0 \$s3 1
add \$t0 \$s6 \$t0
lw \$t1 0(\$t0)
則就可以把A[i]的值從記憶體位置load到\$t1上面
* 14.Basic Blocks
* 一段沒有embedded branch及branch target的Instruction Sequence稱為Basic Blocks。
* 也就是該段instruction，**只有一個入口，只有一個出口**
* Compiler可以辨認出basic block並優化該段code。
* Advanced Processor可以加速basic block的執行。
* 15.Procedure Call Steps
* Place **parameters** in registers
* **Transfer control** to procedure
* Acquire **storage** for procedure
* Perform procedure’s operations
* Place result in register for caller
* Return to place of call
* 16.**Procedure Call Instruction**
* jal ProcedureLabel
* jr \$ra
* 上面兩個指令是一組的，用來procedure call，其中第一行的意義是，jump到Label的部份去執行，並同時把原程序的記憶體位置計入\$31(\$ra)的register。而第二行的意義是，jump到\$31(\$ra)存的記憶體位置，會到原本的位置，執行原本程序。
* 根據我的理解，呼叫function的過程：
* 在MIPS中，return address不一定會儲存到stack中，因為有\$31的幫忙。
* 過程中確定不會呼叫其他function，則執行完這段code後必定是執行return address的位置，只需要一開始把它存入\$31之後再去讀出來就好，不需要另外放入stack。
* 過程中可能會呼叫其他function，則每一層function都要把return address放入stack中，因為\$31的值每多call一層(呼叫jal)就會改變，因此要關注的是存在stack中的return address，每一層要return前會去把該值load到\$31，接著再呼叫jr \$31。
* 在x86系統，return address會放到stack儲存，當要呼叫一個function時的過程，會把相關東西依序放入stack(好像沒有一個專門放return address的register)
**放參數 -> 放return address -> 存ebp -> allocate區域變數**
* MIPS的fp，功用和x86中的ebp相同，就是呼叫一個函數時，作為**該函數的一個基準點**，讓我們用offset 去access **所有和該函數相關的參數或是區域變數等資料**，注意到這些資料都是放在stack中，而sp和fp都可以去access裏頭資料，但是sp指的位置會隨著call function的次數而一直改變，而fp則是每個function會有自己的基準點。
* 17.**Procedure Call**：
* **Leaf Procedure** 指該procedure沒有呼叫其他procedure，也就是過程中沒有用到jal，所以該段code執行完就會呼叫jr，執行當初呼叫這段procedure的地方。
* **Nonleaf Procedure**，過程中有呼叫其他procedure，也就是過程中會呼叫jal及jr，使得instruction變得很複雜，其中會多次用到**STACK**去儲存argument即每一層得address。
* 這裡的比喻像是tree一樣，leaf表示下面沒有樹枝，nonleaf表示還有樹枝(別的procedure)。
* 呼叫procedure時，有時用到的register別的程式正在使用，這時要**放入stack儲存並在最後執行完時restore。**
* 一開始看stack需要多少空間來存register的資料，也就是看會用到幾個register，呼叫addi \$sp, \$sp, (-4\*nums)，這時stack就有空間來存東西，並記得最後要還回去。
* **Nonleaf precedure同時身兼caller以及callee，所以一定要把parameter跟return address先存起來!!!!!**
* 一個有用到遞迴的nonleaf procedure：

* 18.Memory Layout
* Text：存code，pc指標
* Static Data：存global變數，gp指標
* Heap：Dynamic Data，gp指標
* Stack：Functions...,automatic storage，sp指標
* gp這個register，指在static data的最上面，透過減offset來access 全域變數；或是透過加offset來access動態變數。
* 19.Byte\/Halfword Operation
* 一個byte 8個bit，一個halfword 16個bit，一個word 32個bit，一個register 32bit。
* 從memory中load一個byte(8bit)到register(32bit)，它會自動在register前面24bit補0。
* lb,lbu,sb，會在8 bit到32bit做轉換
* lh,lhu,sh，會在16 bit到32bit做轉換
* 20.32bit Constants by lui,ori
* MIPS裡可以直接使用Itype得到16bit常數，16bit其實就夠用了
* 但是register是32bit，有時候我們要得到32bit常數，這時可以透過
* lui rt const：load upper immediate，操作完後，rt變成16bit的const，後面再加上16個0。
* ori rt rt const：or immediate，rt只有前面16bit有值，const只有後面16bit有值，操作or完後，就變成一個32bit的常數了。
* 21.Branching Addressing
* beq或是bne時，用I format會有16bit可以跳到**相對位置**，通常跳的距離很近。
* 第一個bit為sign bit，剩下15bit則是offset。
* **一個指令為32bit=4byte，需要四個記憶體位置來存**，所以對應的記憶體位置一定是4的倍數
* Target address = PC + offset \*4
* 執行這一行時，program counter已經指到下一位置了。(所以offset要-1)
* machine code中的offset表示要跳幾個指令，target會自動將offset的數值乘以4
* 22.Jump Addressing
* 使用 j , jal 時，用J Format有26bit可以跳到我要jump的位置。(0~2^28^)
* **一個記憶體位置32bit**
* 26bit所表示的記憶體位置，實質上為(pseudo) direct jump：
* PC~31:28~ : 26bit : 00
* 前4個bit表示PC的MSB位置
* 26 bit為我們自己決定的地方
* 後2個bit為0，表示跳過去的記憶體位置一定是4的倍數
* 有時在使用beq或是bne時，因為要跳的位置太遠了，16bit不夠用，或是我們希望要跳到絕對位置，這時assembler會幫我們轉換成使用jump的方式，如：
* beq是16bit的位置，j是26bit的位置。
* beq \$s0,\$s1, L1
* bne \$s0,$s1, L2
j L1
L2 : …
* 23.**Synchronization**
* 當2 process要同時存取同一資料時，如果沒有synchronization的機制，就會造成race condition，result取決於instruction被執行的先後順序。
* Atomic Operation：原子操作，不需要另外有synchronize機制，保證其中的程式不會被context switch。
* MIPS中提供ll和sc工具來幫助我們達到synchronization的效果
* ll rt , offset (rs) #load link
* sc rt , offset (rs) #save conditional
* ll單純的把rs位置的值load出來，但同時會啟動一個機制，去檢查rs的位置是否有被更動過，直到sc觸發他
* sc為把值存回rs位置，這時候有兩種case
* 1.rs在過程中有被更動，則此時rt會被設定成0，告訴使用者這段ll-sc過程是不安全的，當中有別人也在操作rs的值，這時也不保證值有正確的存回rs裡(反正就有別人同時再更改)。
* 2.rs在過程中無被更動，此時rt會被設定成1，且執會正確的存回rs裡頭。
* 例子：下面這段assembly code可以保證s1和s4互換的synchronization
* 例子1：
lock(lk);
shvar=max(shvar,x);
unlock(lk);
lk in a0, shvar in a1, x in a2。
* 例子2：
shvar=max(shvar,x);
* 24.Assembler Pseudoinstructions
* \$at是一個給assembler專用的暫存register。
* Pseudoinstructions就是只說某些非正式MIPS的instruction，但是寫起來比較簡潔，assembler看得懂而且會常用，如blt在MIPS中不存在。
* 所以assembler就會把這樣的instruction透過\$at的幫助變成MIPS instruction。
* 25.Run a program
* 大概介紹一個C成是如何變成電腦看得懂的機器語言並被run起來
* Compiler：C程式碼->組合語言
* Assembler：組合語言->機器語言(object file)
* Linker：object file和library->執行檔
* Loader：把執行檔load到memory
* 26.Object Module
* 可能是一個程式，也可能是某個程式的一部分
* Compiler或是Assembler把程式碼轉換成對應的object file，這時還不是執行檔，還需要link一些其他的object file 或library。
* 包含了一下幾個部分：
* Header
* Text segment
* Static data segment
* Relocation information
* Symbol table
* Debug information
* 27.Linking
* Linker把相關的object file連結成為一個完整的執行檔。
* 需要以下步驟
* 1.Merges segments
* 2. Resolve labels (determine their addresses)
* 3. Patch location-dependent and external refs
* 28.Loading
* 把真正的執行檔，從disk上load到memory中執行
* 需要以下步驟
* 1.Read header to determine segment sizes
* 2.Create virtual address space
* 3.Copy text and initialized data into memory
* Or set page table entries so they can be faulted in
* 4.Set up arguments on stack
* 5.Initialize registers (including $sp, $fp, $gp)
* 6.Jump to startup routine
* Copies arguments to $a0, … and calls main
* When main returns, do exit syscall
* 29.Dynamic Linking vs Static Linking
* Library在程式執行時才被載入，而不是直接編譯在執行檔中
* 副檔名

-|win|linux
-|-|-
static|.lib|.a
dynamic|.dll|.so
* 各有優缺點：更新程式庫無需重新編譯其他程式、執行檔的大小等。
* Dynamic linking時，第一次call外部函數時才會Link相關code，這時候因為要額外處理Link部分，會跑得比較久。 而在第二次call外部函數，因為已經link過了，就會快得多了。這種需要該程式碼才去link的方式稱為**lazy linkage**。
* 30.Java Applications (Special Case)
* Java透過bytecode在JVM上面跑，有跨平台的特性。
* Compiler：java程式->class檔(bytecode)
* JVM：把class檔直譯
* JIT Compiler：一邊直譯，一邊優化hotspot
* 32.C Sort Example
* 可以想想看怎麼把bubble sort轉換成MIPS assembly
* 關於Compiler Optimization，在sort function中有呼叫swap function，但如果有使用compiler optimation，他可能回把對應得code，直接置入sort原本的code中。
* 這樣的優化，因為減少了stack堆疊，減少了多次的lw和sw，因此instruction數量會變少而使程式變快。
* 33.Arrays vs. Pointers
* Array的index方法為
* Multiplying index by element size
* Adding to array base address
會使得要access一個元素所花費的instruction比較多
* Pointer則是直接指到所求的記憶體位置
* 因此可以知道pointer的方式會比較快速且簡潔，Compiler在處理時，也會自動把用array的index轉換成用pointer的方式。
* 但是現在compiler技術成熟，寫code時仍建議用array寫，比較易懂且好maintain，compiler會自動轉換成pointer版本的assembly code。
* 34.ARM vs MIPS
* ARM和MIPS都是RISC的代表

-|Arms|MIPS
-|-|-|
Date announced |1985| 1985
Instruction size |32 bits |32 bits
Address space |32-bit flat |32-bit flat
Data alignment |Aligned |Aligned
Data addressing modes |9 |3
Registers |15 × 32-bit |31 × 32-bit
Input/output |Memory mapped |Memory mapped
* ARM因為register少一半，所以identify register只要4bit，有比較多bit使用空間。
* ARM特別使用**conditional code**
* 每一個指令的前4bit用來判斷condition code
* ARM只有16暫存器
* /(其他略，反正就看看資料)
* 35.The Intel x86 ISA
* CISC代表
* 市場龍頭
* 8080/8086
* 80186
* 80286
* 80386： **1985, 32bit**
* i486
* Pentium： **1993**
* Pentium Pro/2
* SSE
* AMD64： **2003, 64bit**
* Intel Core
* [register結構](https://en.wikibooks.org/wiki/X86_Assembly/X86_Architecture)
* 36.Fallacies
* Powerful instruction 不代表 higher performance
* Implement時要符合各種case，難implement
* 就算implement出來，該instruction速度也不會快
* 整個程式可能可以用比較少的instruction就做完
* 如同之前所講，加速的重點應該在於，使得常用的instruction更快，而不是把所有東西包在一起
* 寫Assembly code 不一定 higher performance
* 現代的compiler優化都很完善了
* 寫assebly code會使programmer很難去maintain，可能錯誤率會很高，很難修改，使整體產量下降
* Backward compatibility 不代表 instruction set doesn’t change
* 相容是為了不要讓以前的成果丟棄
* 但是新版本有目的的，為了加速,擴增register,
* 37.Pitfalls
* sequential word 不在 sequential address
* byte addressing以及word=32bit
* 所以要跳4個address
* Keeping a pointer to an automatic variable after procedure returns會造成指向錯誤地方
* pointer指向stack中，但是之後stack被pop掉
* memory bug
* 38.SSE, AVX
## CH3 Arithmetic for Computers
* 1.Arithmetic算數，是電腦可以執行的最基本單位。
* **Arithmetic Logic Unit(ALU)** 算術邏輯單元
* 1 bit ALU可以處理And, Or, Add, carry，再用multiplexer選擇結果。
* 1 bit enhanced ALU，可以先決定要不要把input invert，進而實現，加法減法、NAND、NOR。
* 把1 bit組合起來就可以變32bit。
* 2.ALU中的set less than。
* 規定：output 32bit中
* 前31bit皆為0
* a<b時最後一bit為1
* a>=b時最後一bit為0
* 直接把a-b的結果的 sign bit，當作slt output的LSB
* 3.Zero flag
* 把所有32bit結果or起來，再取not，則代表32bit是否全0
* 4.Arithmetic for Computers
接下來會介紹
* 整數加減法
* 整數乘除法
* overflow
* floating point表示法及運算
* 5.整數加減法
* 加法檢查Overflow的方式，check原本數字和結果的sign bit
* 兩個正數 相加結果 為負
* 兩個負數 相加結果 為正
* 減法檢查Overflow的方式，check原本數字和結果的sign bit
* 正減負 為負
* 負減正 為正
* Overflow發生後的對應
* 直接ignore，如C語言。
* 處理exception，如Ada或fortran。
* 這種時候要先save program counter到EPC裡頭。
* 接著才可以去handler處理exception，最後才跳回EPC裡的指令。
* MIPS中檢查overflow
* Signed
* c=a+b
* 檢查a,b是否同號，以及a,c是否異號
* 透過xor a,b和slt 0可以知道sign bit是否同號
* 用bne決定是否要branch去處理
* Unsigned
* c=a+b
* a最多只能和~a相加才不會overflow
* 所以去檢查b是否比~a還要大
* 6.MultiMedia
* SIMD(單指令流多資料流)機制：一個控制器來控制多個處理器，平行處理資料。
* Saturating operations：oveflow發生時要保持最大值
* 7.整數乘法(32bit)
* 版本一
* 有一個control控制shift以及write enable
* 有64 bit ALU
* 有64 bit Multiplicand，要依序往左移
* 有64 bit product答案
* 有32 bit Multiplier，要依序往右移
* 共要三個register，160 bits。
* 版本二
* 有一個control控制shift以及write enable
* 有32 bit ALU
* 有32 bit Multiplicand
* 有64 bit product，存答案即multiplier，要依序往右移
* 共要兩個register，96 bits。
* 每次檢查multiplier是否已被shift為0
* **Booth Algorithm**
* 如果multiplier連續1很多可以加速，但其他case不一定比較快
* multiplier中

current bit|right bit|meaning
-|-|-
0|0|在0中間
0|1|1的結束，要加上multiplcand
1|0|1的開始，要扣掉multiplcand
1|1|在0中間
* Faster Multiplier
* 可能可以用更多(二的次方)的ALU構成32bit乘法器
* 甚至能達到Pipeline，且需要clock數變少
* 但耗費的ALU需要更多成本
* 8.Carry Look Ahead Adder
* propogate是1代表carry out等於上一層的carry
* generate是1代表carry out等於1
* BIT- LEVEL中
* g=ab
* p=a+b
* c~i~ = g~i~ + p~i~c~i-1~
* 4bit carry look ahead adder
* 一開始會先把a和b接起來算出每bit的g和p，有兩種版本
* Ripple Adder
* 每一bit的carry out要透過c~i~ = g~i~ + p~i~c~i-1~，上一bit的carry out得到
* 算MSB的carry需要delay會很長
* Carry Look Ahead
* c~i~ = g~i~ + p~i~c~i-1~
* 但是可以透過展開，每一bit的carry out變成說某些g和b和C~in~先AND再OR起來。
* MSB需要比較多硬體(不能擴充成太多bit)
* 每一bit的carry需要delay相同，**可以一次算出4bit carry**
* Two Level(16bit為例
* 第一個level就是4bit的carry look ahead adder
* 第二個level把4個4bit的carry look ahead adder組成一組
* 每一組中會有該組的g和p
* 所有bit的carry被正確算出時機
* 一開始第一level處理，c1~c3是正確的
* 接下來第二level處理完，算出c4,c8,c12,c16
* 最後第一level再處理，c5,...,c15被正確算出
* Delay不會太多，硬體成本不會太大。
* 9.MIPS 乘法
* 提供HI/LO兩register，為了應付64bit的output
* mult rs,rt ，rs\*rt，放入HI/LO
* mfhi rd，取出結果
* mflo rd，取出結果
* mul rd,rs,rt ，rd=rs\*rt的後32bit
* 10.Division (32bit)
* 32次，每個iteration先做減法，看Output
* 結果為正，商補上1，繼續除
* 結果為負，不夠減，商補上0，被除數要加回剛剛減掉的數字
* 正負號處理
* 預先把被除數dividend和除數divisor判斷正負號
* 除法的過程**只處理正數除以正數**
* 版本一
* 有一個control控制shift以及write enable
* 有64 bit ALU
* 有64 bit Divisor，要依序往右移
* 有64 bit remainder，一開始存dividend
* 有32 bit quotient，記錄商，依序左移
* 共要三個register，160 bits。
* 版本二
* 有一個control控制shift以及write enable
* 有32 bit ALU
* 有32 bit Divisor
* 有64 bit remainder，依序左移
* 共要兩個register，96 bits。
* **Division Algorithm**
* 原本是減到remainder變成負數的時候，加回去restore，到下個iteration再做一次減法判斷...
* 可以不要restore：
* 再某個iteration先做r-d
* 如果是正的，商填1，下一回合從2(r-d)再-d
* 如果是負的，商填0，下一回合從2(r-d)再+d
* 正確版本
* 第一回合一定是r-d
* 根據上一回合商的LSB做r-d或是r+d
* 如果是正的，商填1，乘以二當作下一回合
* 如果是負的，商填0，乘以二當作下一回合
* Faster Division
* 不行透過平行運算加速
* 不滿足交換結合律
* SRT division
* 11.MIPS 除法
* 提供HI/LO兩register，為了應付64bit的output
* div rs,rt ，rs\*rt，
* remainder放入HI
* quitient放入LO
* mfhi rd，取出結果
* mflo rd，取出結果
* **並沒有提供overflow或是除以0的check**
* 12.Floting Point
* 表示小數， +/- 1.xxxxx * 2^yyyy^
* **IEEE standard 754**
* single(32bit)
* double(64bit)

~|S|Exponent|Fraction
-|-|-|-
single|1|8|23
double|1|11|52
* **x = (-1)^s^ * (1+fraction) * 2^exponent-bias^**
* fraction的第一位代表2的-1次方，第二位代表2的-2次方，因為只會**存normalized的數字**，所以必為1. XXX，XXX的二進位就是fraction。
* exponent，要先扣掉bias
* **在single，bias = 127**
* **在double，bias = 1023**
* bias的原因是讓exponent都變成正數，方便比較大小。
* Exponent規定
* 00000000保留給0
* 11111111保留給無限大
* 最小為00000001代表2^1-127^=2^-126^
* 最大為11111110代表2^254-127^=2^127^
* Fraction規定
* 最小為00..00代表1.00..00=1
* 最大為11..11代表1.11..11=2
* **轉換範例**
* 1 10000001 01000…00 = -5
* -0.75 = 1 01111110 1000…00
* 13.Precision, Table
* single有23 bit fraction，可表示2^-23^，約為小數點下六位
* double有52 bit fraction，可表示2^-52^，約為小數點下十六位
* 注意要先看exponent在看fraction
*
Exponent|Fraction|意義
-|-|-
0|0|0
0|非0|denormalized
1~254|任意|normalized fp
255|0|+-無限大
255|非0|NaN
* 最小normalized正數
* exp=1 (2^-126^)
* fraction=全0(1.0..0)
* 最小denormalized正數
* exp=0 (2^-126^)
* fraction=0..01(0.0..01)
* 14.FP加法
* 1 先align，**把次方小的數換成大的次方**
* 2 相加，(增加significand數)
* 3 normalized結果
* 4 round結果(可能要renormalized)
* 記得是要改變次方小的數，原因是因為避免大數的bit被刪除掉。
* 15.FP算數hardware
* 需要多個clock cycle才可做完
* 可以被設計成pipeline
* 16.FP乘法
* 1 先exponent相加(如果是bias版本要多扣一次bias)
* 2 significands相乘
* 3 normalized結果，檢查overflow
* 4 round結果(可能要renormalized)
* 5 決定sign bit
* 17.FP指令 in MIPS
* FP的操作不在CPU，而在coprocessor1，其只會操作fp register
* single precision：有\$f0~\$f31，32個fp register
* double precision：兩兩配成一對。
* load及save會使用
* lwc1,swc1,ldc1,sdc1
* 表示 load/save，word/double，coprocess1
* 算術運算會使用
* add.s, sub.s, mul .s, div.s
* add.d, sub.d, mul .d, div.d
* Comparison會使用
* c.eq.s, c.lt.d, c.le.d
* **把結果存在FP condition-code bit**
* branch會使用
* bc1t表示如果c1的condition bit是true則branch
* bc1f表示如果c1的condition bit是false則branch
* 18.Accuracy of FP operation
* guard bit：precision後的下1 bit，另外提供儲存空間。
* round bit：precision後的下2 bit，另外提供儲存空間。
* sticky bit：之後的位數有沒有數字，用來決定是否要round。機制為每次shift right檢查是否為1，只要有一次出現1就為1其他為0。
* 19.Other Issue
* Memory資料就是0或1，但是意義是programmer賦予的，必須要好好maintain。
* Associativity(交換律)：fp的運算不一定會有交換律，比較小的數字可能會在運算過程消失，這在**平行運算**中需要好好注意。
* 20.x86 instruction, SSE2
* SIMD = Single Instruction Multiple Data，是一種透過單一指令操作多處理器，對資料進行**平行運算**的技術。
* SSE2 = Streaming SIMD Extensions 2，是一種可以處理**平行運算**的指令集。
## CH4 Processor
* 這章節主要介紹兩個版本CPU和pipeline觀念
* 1. CPU中 和Instruction有關的動作
* PC：指到instruction memory，表示電腦正要執行的instruction位置
* register number：來identify不同的register
* 可能會用到的運算
* ALU
* load/store
* PC+4
* 2. CPU設計想法
* 分成Instruction Memory和Data Memory，因為一個clock cycle指可以讀一次memory，分成兩個部分才可同步進行
* 用multiplexer決定一些結果
* PC來自PC+4或是PC+4+branch
* register write來自ALU或是memory data
* ALU input來自instruction或是register值
* CPU基本結構
* PC
* Instruction Memory
* Register
* ALU
* Data Memory
* 3.Logic Design基礎
* 透過高低電位來存資料
* Combinational電路
* And,Or,...
* Sequential電路
* 有記憶功能，透過clock和write enable來控制D-FlipFlop
* positive edge trigger
* 電路設計可以大概看成，每個clock中
* state element，在clock 0變1時，改變狀態
* combinational電路，在其他時候，計算所需結果
* 4. 設計datapath
* instruction memory for fetch
* Read address的值為PC+4
* Register for Rtype
* 四個input，分別為Read Reg1/Read Reg 2/Write Reg/Write Data
* 兩個output，分別為Read data 1/Read data 2
* data memory for load/store
* 兩個input，分別為Address/WriteData
* 一個output，為Read Data
* memory offset要 sign extension
> * 比方說lw $16 100($17)
> 那麼代表要讀取mem[\$17+100]的值
> --- 17號register取出位置(32bit)
> --- 把16bit的100擴充成32bit
* branch
* 透過ALU的運算結果，決定PC下一階段的值
* branch offset要需要sign extension
> * 比方說beq $16 $17 100 ( machine code存25)
> 那麼代表要pc = (pc+4) + 4* 25的值
> 先把16bit的25擴充成32bit
> 再把25 shift left兩格
* 5.ALU control
* 透過4bit來控制ALU，第一bit代表a invert，第二bit代表b invert，34bit代表and/or/+/less
* 0000 AND
* 0001 OR
* 0010 加法
* 0110 減法
* 0111 stl
* 1100 nor
* load/store：ALU做加法
* branch：ALU做減法
* Rtype：根據instruction的funct
* 根據instruction的opcode，我們可以抓出來當作ALUop
* 當ALUop是00 -> load/store -> 0010
* 當ALUop是01 -> beq -> 0110
* 當ALUop是10 -> Rtype -> 根據funct
* 6.第一版CPU
* 一個clock cycle內要完成一種operation
* datapath同時只能做一件事情
* **2 level control**
* Main Control：input為opcode[31:26]
* Reg Write
* Mem Write
* Mem Read
* Branch
* ALUsrc：決定ALU第二input為register或instruction的extension
* PCsrc：決定PC+4或是branch：(pc+4) + 4* 25
* Mem To Register：決定ALU結果或Memory結果寫回Register
* Reg Destination：決定Mem Write要寫到[20:16]或[15:11]
* ALUop：00,01,10，給ALUcontrol使用
* ALU control：input為ALU op以及funct[5:0]
* ALUop 00 -> 0010
* ALUop 01 -> 0110
* ALUop 10 -> 根據funct
* 7.Jump Instruction
* 先把26bit捕兩個0變成28bit
* 前面再補上PC+4[31:28]
* Control再多一條控制訊號，多一個multiplexer，決定PC = jump/(branch, pc+4)
* 8.Control signal的設計(電路)
* 省略，主要就是將truth table化減成電路
* 9.Performance
* Critical path： load指令，每個步驟都需要操作
* 10.**Pipeline**
* 
* speed up = number of stages
* MIPS中可區分成五個stage
1. IF: Instruction fetch from memory
2. ID: Instruction decode & register read
3. EX: Execute operation or calculate address
4. MEM: Access memory operand
5. WB: Write result back to register
* 原本可能每隔800ps完成一個指令，使用pipeline就可以降到200ps
* 使throughput變短，且cycle time變短
* 每一個stage所花時間越相近越好
* 11.Hazard
* **造成bubble出現**
* Structure Hazard
* 競爭resource
* 問題：load/store，fetch instruction兩個階段都需要用到memory
* Data Hazard
* 後面指令input要等前面指令資料output，發生在**load 指令**
* add $s0, $t0, $t1
sub $t2, $s0, $t3
則會造成兩個bubble出現在pipeline中
* 解法：Forwarding/Bypassing
* 沒有bubble
* 把EX結果直接拿給下個cycle的ID
* read register就不用read，而是拿剛剛結果
* 問題：Load-Use Data Hazard
* 如果第一instruction要load到register，第二instruction要use register
* 透過Forwarding也一定會有bubble
* 解法：code的編排也可避免data hazard
* 把有data dependency的指令分開做
* Control Hazard
* 後面指令control要等前面指令資料，如beq
* 問題：如果有beq，一定要等到EX之後，下一指令才可以開始執行IF
* 解法：增加一些circuit，使得在ID就知道結果
* 這樣就只要一個bubble
* stall on branch
* 解法：Branch Prediction
* 猜對，直接執行下一個指令
* 猜錯，下一個指令的清掉IF，產生一個bubble，下下指令可以執行應該執行的指令。
* Static Branch Prediction
* backward通常要take，如迴圈
* forward通常不take，如if/else
* Dynamic Branch Prediction
* record recent history of each branch
* 12. MIPS pipeline
* 主要是improve throughput，但是latency不變。
* 4個Pipeline register來區分五個stage，用來keep五種指令同時做的一致性。
* single clock cycle pipeline diagram
* multi clock cycle pipeline diagram
* **Control signal、Write back address要跟data一起進入pipeline**
* 共有9個訊號
* reg-des/ mem-to-reg/ alu-src
* mem-wri/ mem-read/ reg-wri
* alu-op/ branch
* 並不是都要跑過每個stage
* 13. Data Hazard in ALU
* 發生data hazard時機
* EX/MEM.RegisterRd = ID/EX.RegisterRs
* EX/MEM.RegisterRd = ID/EX.RegisterRt
* MEM/WB.RegisterRd = ID/EX.RegisterRs
* MEM/WB.RegisterRd = ID/EX.RegisterRt
* 仍需要check，才決定是否要forward
* 一、RegWrite=1
* 前兩指令要檢查，EX/MEM.RegWrite
* 後兩指令要檢查，MEM/WB.RegWrite
* 二、RegisterRd ≠ 0
* EX/MEM.RegisterRd ≠ 0
* MEM/WB.RegisterRd ≠ 0
* 前面三個條件，是forward unit的判斷條件，都成立時可以forward。
* EX hazard：需要把EX後的結果，往前傳回ALU當source
* MEM hazard：需要把MEM後的結果，往前傳回ALU當source
* 14. Double Data Hazard
* 可能第一和第二，同時都要forward到第三
* add $1,$1,$2
* add $1,$1,$3
* add $1,$1,$4
* 第一個要 forward 到第三個的前提是個第二跟第三個之間 沒有hazard
* 15. Load/Use Data Hazard
* lw $2, 20($1)
and $4, $2, $5
or $8, $2, $6
* 何時會發生?
* ID/EX.MemRead and
( (ID/EX.RegisterRt = IF/ID.RegisterRs) or
(ID/EX.RegisterRt = IF/ID.RegisterRt) )
* 如何stall
* 把所有control設為0
* PC 和 IF/ID register再執行一次相同指令
* IF/ID 冰凍指令二
* PC 冰凍指令三
* 16. Branch Hazard
* 17. Dynamic Branch Hazard
* 透過branch prediction buffer
* Branch Delay Slot 分支延遲間隙
* From before
* From Target
* From fall-through
* Branch Target Buffer
* Exception and Interrupt
* 非預期的情形發生：Exception指發生在 CPU 裡面，Interrupt指發生在 CPU 外面。
* 由system control coprocessor(CP0)管理，把PC存入EPC。
* Cause Register：一個entry，裡面會在檢查是哪種例外，做對應處理。
* Vectored Interrupt：多個entry，依照哪種例外發生，進到不同的handler。
* Instuction Level Parallelism(ILP)
* Multiple Issue
* Static
* Dynamic
* VLIW Very Long Instruction Word
## Other
- 直接記憶體存取（Direct Memory Access，DMA）
- 允許某些電腦內部的硬體子系統，獨立直接讀寫記憶體，而不需 CPU 介入
- 允許不同速度的硬體裝置來溝通，而不需要依於中央處理器的大量中斷負載
- 會導致快取一致性問題
- 快取同調系統（Cache-coherent system）: DMA 寫入時，以訊號通知 cache 某記憶體位址的值已經過期
- 非同調系統（Non-coherent system）: 交給作業系統管，存取 cache 時保證不被 DMA 程式影響
- 使用 cache 的兩種方式
- `write through`：CPU 向 cache 寫入數據時，同時向 memory 也寫一份，使 cache 和 memory 的數據保持一致
- 每次都要訪問memory，速度比較慢
- `write back`：cpu更新cache時，只是把更新的cache區標記一下，並不同步更新memory
- 很多時候 cache 存入的是中間結果，沒有必要同步更新memory
- CPU 執行的效率提高
- 實現起來技術比較復雜
- Cache coherence 快取一致性
- 當許多不同的裝置共享一個共同記憶體資源，且各自有自己的 cache ，要注意 cache 資料是否一致