---
# System prepended metadata

title: 課程｜計算機結構
tags: [課程]

---

# 計算機結構

[黃婷婷教學](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：
    ![](https://i.imgur.com/30gzbiI.png)
    ![](https://i.imgur.com/cXTjglB.png)

* 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
    ![](https://i.imgur.com/IQpafyU.png)
    * 例子1：
    lock(lk); 
    shvar=max(shvar,x); 
    unlock(lk); 
    lk in a0, shvar in a1, x in a2。
    ![](https://i.imgur.com/MfZ6AFi.png)
    * 例子2：
    shvar=max(shvar,x); 
    ![](https://i.imgur.com/odPgujx.png)   
* 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
    ![](https://i.imgur.com/bTw81Cs.png)
    ![](https://i.imgur.com/6Es8ArM.png)
    * 關於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**
    * ![](https://i.imgur.com/q9WF5VE.png)
    * 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 資料是否一致


