# Chap. 04 - The Processor (1): Design a Single-Cycle Processor
> 課程內容 : 清華大學開放式課程 黃婷婷教授
> 參考書目 : Computer Organization and Design: The Hardware/Software Interface (5th), David A. Patterson, John L. Hennessy
>
> 其他科目內容請參見 [[Here]](https://hackmd.io/@ChenZE/By4SOO6Jyl)

## Contents
* [Sec. 4.1 Introduction to designing a processor](#Sec-41-Introduction-to-designing-a-processor)
* [1. Instruction execution](#1-Instruction-execution)
* [2. Logic design basics](#2-Logic-design-basics)
* [3. Sequential elements](#3-Sequential-elements)
* [Sec. 4.2 Analyzing the instruction set (step 1)](#Sec-42-Analyzing-the-instruction-set-step-1)
* [1. Logical register transfer](#1-Logical-register-transfer)
* [2. Requirements of instruction set](#2-Requirements-of-instruction-set)
* [Sec. 4.3 Buliding the datapath (step 2 & 3)](#Sec-43-Buliding-the-datapath-step-2-amp-3)
* [1. Step 2(a): combinational components for datapath](1-Step-2a-combinational-components-for-datapath)
* [2. Step 2(b): sequential components for datapath](#2-Step-2b-sequential-components-for-datapath)
* [2.1 Storage element: register file](#21-Storage-element-register-file)
* [2.2 Storage element: memory](#22-Storage-element-memory)
* [3. Step 3(a): datapath assembly](#3-Step-3a-datapath-assembly)
* [4. Step 3(b): add and subtract](#4-Step-3b-add-and-subtract)
* [5. Step 3\(c): store/load operations](#5-Step-3c-store/load-operations)
* [6. Step 3(d): branch operations](#6-Step-3d-branch-operations)
* [Sec. 4.4 A single-cycle implementation](#Sec-44-A-single-cycle-implementation)
* [1. Single cycle datapath](#1-Single-cycle-datapath)
* [2. Data flow during add](#2-Data-flow-during-add)
* [2.1 Data flow](#21-Data-flow)
* [2.2 The critical path](#22-The-critical-path)
* [Sec. 4.5 Control for the single-cycle CPU](#Sec-45-Control-for-the-single-cycle-CPU)
* [1. Control of CPU operation (step 4)](#1-Control-of-CPU-operation-step-4)
* [1.1 Design main control](#11-Design-main-control)
* [1.2 Example: $\mathtt{add}$](#12-Example-)
* [1.3 Example: $\mathtt{lw}$](#13-Example-)
* [1.4 Example: $\mathtt{beq}$](#14-Example-)
* [2. ALU controller (step 5a)](#2-ALU-controller-step-5a)
* [2.1 ALU control](#21-ALU-control)
* [2.2 Logic equation for ALUcontrol](#22-Logic-equation-for-ALUcontrol)
* [3. Main controller (step 5b)](#3-Main-controller-step-5b)
* [Sec. 4.6 Adding jump instruction](#Sec-46-Adding-jump-instruction)

## Sec. 4.1 Introduction to designing a processor
### 1. Instruction execution
Instruction 的執行過程大致上可以分為以下步驟:
1. Fetch instruction (program counter → instruction memory): 根據 program counter 的內容 (32-bits 的 address) 去 memory 拿 instruction
2. Read register (register number → register file): 讀取 register 中的資料
3. Depend on instruction class to decode
* 使用 ALU 計算
* 取得 data memory
* 計算 program counter

CPU 整體概覽設計如下圖所示，每個顏色的螢光筆分表代表不同意義 (粗體字表示該方框所代表的意義)


首先，register 由上到下分別表示 \$rs、\$rt、\$rd 三種用途。<font color="#0000C6">藍色螢光筆</font>表示 ALU 計算完結果後將資料放回 register，通常用於 R-format。<font color="#00A600">綠色螢光筆</font>表示 ALU 計算完後取得 address，並從該 memory address 將資料載入到 register，通常用於 $\mathtt{lw}$ 指令。<font color="#FF0000">紅色螢光筆</font>表示將資料存入到 memory 中，通常用於 $\mathtt{sw}$ 指令

當同一條 wires (纜線，電線) 有兩個輸入時 (下圖一紅圈處)，到體要傳輸哪一邊的資料流，會由 multiplexers (MUX) 控制，而 MUX 會選擇哪一條線路讓資料流傳輸則是用 control 所發出的訊號控制 (下圖二)



### 2. Logic design basics
要傳輸的資訊通常被 encoder 成 binary，低電壓 (low voltage) 表示 0 ，高電壓 (high voltage) 表示 1。一個 wire 通常表示一個 bit，multi-bits data 就會使用多個 wire 來組成，稱為 bus (匯流排)

### 3. Sequential elements
##### Register
Registe 用來在電路 (circuit) 中儲存資料，一般使用 clock signal 來決定要不要更新 register 中儲存的數值，通常是在 signal 從 0 到 1 的瞬間才能儲存資料，稱為 edge-triggered。

如下圖所示， D 表示 輸入到 register 中的資料，Q 表示 register 的輸出，當 clk 從 0 到 1 的瞬間會捕捉輸入的資料 D，並更新輸出的 Q


##### Register with write control
另一種 register 帶有 write control，並非單純使用 clock signal 來控制資料的寫入，當 (1) edge-triggered 發生且 (2) wirte control = 1 時才會更新 register 中的資料。與一般的 register 相比，好處在於只有在需要的時候才會寫入，可以避免不必要的資料更改

如下圖所示，在 clock edge 的情況下 (黃色螢光筆) 且 write control = 1 (藍色螢光筆) 時才會寫入資料


### 4. How to design a processor
1. 分析 instruction set (datapath requirements)
2. 選擇 datapath 並建立 clocking methodology
3. Assemble datapath 來滿足 requirement

:::info
datapath 是指計算幾組織中處理數據和執行指令的部分，由一系列的數據操作元件 (register、ALU 等) 和 數據傳輸元件 (bus 等) 組成
:::
## Sec. 4.2 Analyzing the instruction set (step 1)
> 重點回顧: MIPS 的指令架構


### 1. Logical register transfer
**R**egister **T**ransfer **L**anguage (RTL) 是一種用來描述 instruction 意義的方式，包含了 instruction 如何操作 register 以及 memory 等。所有的 instruction 都從 fetch instruction 開始，並經歷 read registers 後再透過 ALU 計算。 Instruction 的格式有以下三種:
* R - format: op | rs | rt | shamt | funct
* I - format: op | rs | rt | imm-16
* J - format: op | imm-26

| Instruction | Register transfer |
| :-: | :-: |
| $\mathtt{add}$ | `R[rd] <- R[rs] + R[rt];` `PC <- PC + 4` |
| $\mathtt{sub}$ | `R[rd] <- R[rs] + R[rt];` `PC <- PC + 4` |
| $\mathtt{lw}$ | `R[rt] <- Mem[ R[rs] + sign_ext(imm16)];` `PC <- PC + 4`|
| $\mathtt{sw}$ | `Mem[ R[rs] + sign_ext(imm16)];` `PC <- PC + 4`|
| $\mathtt{addi}$ | `R[rt] <- R[rs] + sign_ext(imm16);` `PC <- PC + 4`|
| $\mathtt{beq}$ | `if (R[rs] == R[rt]) then PC <- PC + 4 + sign_ext(imm16)\|\|00 else PC <- PC + 4` |

以 $\mathtt{add}$ 為例，`R[rd] <- R[rs] + R[rt];` 表示拿 \$rt 與 \$rs 的資料相加後儲存在 \$rd 中，並同時進行 `PC + 4`

### 2. Requirements of instruction set
根據上述的 register transfer，我們可以發現 datapath 需要以下的物件:
* Memory: 儲存 instruction 與 data
* Register: 又分為讀取資料用的 \$rs 與 \$rt 以及寫入資料用的 \$rt 或 \$rd
* Program counter
* Extender: 做 zero extension 或 sign extension

## Sec. 4.3 Buliding the datapath (step 2 & 3)
### 1. Step 2(a): combinational components for datapath
Datpath 中有 3 個基本的 combinational logic elements (組合邏輯元件): Adder、MUX 與 ALU，如下圖所示，其中數字部分表示輸入 (or 輸出) 的 bits


### 2. Step 2(b): sequential components for datapath
Register 的功能類似 Flip Flop D，差別在於可以支援 n-bits 的輸入或輸出，以及可以透過 write enalble 決定何時需要寫入資料。當 write enable = 0 時資料不會改變 (不寫入)，當 write enable = 1 時資料才會改變並寫入到 register 中。

#### 2.1 Storage element: register file
Register file 由 32 個 register 組成，簡單來說，register file 可以看成是由 32 個 register 所組成的矩陣，輸入與輸出大致如下:

* 兩個 32-bits 的 output busses: bus A 與 bus B
* 一個 32-bits 的 input busses: bus W
* 一個 clock input (CLK): 影響是否會寫入資料的因子

運算時，要從哪個 register 讀取或寫入資料是由 RA、RB 與 RW 來選擇。 RA 與 RB 分別表示從某兩個 register 讀取資料並將資料分別推至 bus A 與 bus B 輸出，RW 表示將 bus W 所輸入的資料存在 RW 之中，且只有在 write enable = 1 時才會將 bus W 輸入的資料寫進 RW 中，詳細架構如下圖所示。


#### 2.2 Storage element: memory
Memory 一次只能進行一個動作，通常不是做讀取資料 (read) 就是寫入資料 (write)，所以只要一個 address 即可，輸入與輸出大致如下:

* 一個 32-bits 的 input bus: data in
* 一個 32-bits 的 output bus: data out
* 一個 clock input (CLK): 影響是否會寫入資料的因子

Address 會挑選該位址的內容推送給 data out 做輸出，只有當 write enable = 1 時才會把從 data in 輸入的資料寫入到 address 提供的位址中，詳細架構如下圖。


### 3. Step 3(a): datapath assembly
首先進行 fetch instruction，根據 PC 所提供的 address 來提取並輸出要執行的 instruction，如下圖所示，其中<font color=#ff0000>紅色線段</font>表示提取當前 PC 所指向的位址後執行 PC + 4，並在 edge trigger 發生時才會將 PC + 4 寫入 PC，也就是執行 `PC = PC + 4`


### 4. Step 3(b): add and subtract
以 R-format 中的 add 與 subtract 舉例，架構如下。 Read register 1 與 2 分別對應到先前 register file 中所提到的 RA 與 RB，write register 對應到 RW，read data 1 與 2 對應到 bus A 與 bus B，write data 對應到 bus W。


此架構表示從 \$rs 與 \$rt 中所指向的 register 提取資料並透過 bus A 與 bus B 送到 ALU 中計算結果，計算完成的結果透過 bus W 輸入至 register file 中，並在 RegWrite = 1 時寫入到 \$rd 所指向的 register

### 5. Step 3\(c): store/load operations
接下來以 store 與 load 舉例。在進行 store 與 load 時會牽涉到資料的儲存與載入，因此根據 $\mathtt{sw}$ 與 $\mathtt{lw}$ 的不同，\$rt 也有不同的用途，架構如下，以<font color="#FF8000">橘色</font>表示 $\mathtt{sw}$ 的操作，<font color="#00DB00">綠色</font>表示 $\mathtt{lw}$ 的操作。


##### <font color="#0000E3">Base and offset</font>
\$rs 中儲存的資料是 base address，read register 1 (RA) 根據 \$rs 所指示的位置將該 register 中的資料推送到 read data 1 (bus A) 後在輸入至 ALU 中。

16-bits 的 immediate 經過 sign extened 後擴增為 32-bits，在輸入至 ALU 中與 base address 相加，最後得到 address。

##### <font color="#00DB00">Load: memory → register</font>
在進行 load 時，以 write register (RW) 作為 \$rt，透過前一步所計算出的 address，從該 address 讀取資料後透過 write data (bus W) 輸入至 register file，並將 bus W 輸入進來的資料儲存在 \$rt 所指向的 write register 中。

##### <font color="#FF8000">Store: register → memory</font>
在進行 store 時，以 read register 2 (RB) 作為 \$rt，並將 \$rt 所指向的 register 中的資料推送至 read data 2 (bus B) 並輸入至 memory。

當 memory write = 1 (MemWrite) 時才會將輸入到 memory 的資料寫入

##### <font color="#ff0000">Complementary</font>
不論是 $\mathtt{lw}$ 或 $\mathtt{sw}$，圖中紅色勾勾處都會計算 memory address 以及讀取資料，但因為只有 $\mathtt{lw}$ 時才需要將資料寫入到 register，所以圖中紅色實心處會有一個 MUX 來控制是否要做寫入的動作。

##### Remark
總結來說，將 R-format 與 load/store 的 datapath 整理如下圖。


<font color="#00DB00">綠色框框的 MUX</font>用來控制輸入至 ALU 中的資料是: (1) 要做 R-format (2) 還是 $\mathtt{sw}$ / $\mathtt{lw}$，<font color="#FF8000">橘色框框的 MUX</font>用來控制: (1) 讀取 memory address 的資料到 register 還是 (2) 將做完 $\mathtt{add}$ / $\mathtt{sub}$ 的結果寫入到 register 中

### 6. Step 3(d): branch operations
在進行 branch equal 時，不論是否要做 branch，都要事先計算出欲跳轉的位置。具體結構如下圖所示。


\$rs 與 \$rt 分別輸入至 read register 1 與 2 之中並推送至 bus A 與 bus B，接著在輸入至 ALU 中進行相減來判斷條件。

Imm-16 經過 sign extend 後擴增為 32-bits，再經過左移 2-bits 後輸入至 adder 與 PC + 4 來計算 branch target。此處還需要一個 MUX 來控制是否要做 branch

總結以上，最後的架構如下圖所示


## Sec. 4.4 A single-cycle implementation
### 1. Single cycle datapath
Single cycle datapath 的架構圖如下所示:


<font color="#0000E3">1. \$rt 也可能作為 destination register 來將資料寫入至 register (load 運算時)</font>
<font color="#ff0000">2. 決定要使用 \$rt 還是 \$rd 來作為 write register</font>
<font color="#0000E3">3. 寫入 R-format 的結果</font>
<font color="#0000E3">4. 讀取 memory 的資料並寫入到 register (for $\mathtt{lw}$)</font>
<font color="#00A600">5. ALU 做 +/- 由 ALUop (funct) 決定</font>
<font color="#00A600">6. 決定做 R-format 還是 immediate</font>

### 2. Data flow during add
#### 2.1 Data flow
以 add 運算為例，資料流的傳輸如下所示，其中紅色框框表示當有 clock signal 發生時才會寫入資料。紅色實線表示在進行 add 運算時一樣會計算 memory address 的位置並讀取該 address 的資料，但是會根據後方的 MUX 來控制要不要將這筆來自於 memory 的資料寫入至 register


#### 2.2 The critical path
clock cycle 在設計時，必須將時間設為最長的 delay，才可以確保資料都有被正確的讀取或寫入，如下圖一所示，而資料流在傳輸時所經過的最長路經則稱為 critical path，如下圖二所示。



## Sec. 4.5 Control for the single-cycle CPU
### 1. Control of CPU operation (step 4)
#### 1.1 Design main control
在設計 datapath 時，在某些節點處需要 MUX 來控制與選擇輸入值，而影響 MUX 輸出結果的稱為 control signal，以下圖為例指的是橘色部分。Control signal 作為 MUX 的輸入可以影響 MUX 的輸出結果。


對於 control signal 觀察可以歸納出以下幾點:
* OPcode 的位置在 bits 31-26
* 兩個用於讀取的 register (read register) 分別為 bits 25-21 的 rs 以及 bits 20-16 的 rt (針對 R-format、$\mathtt{beq}$ 與 $\mathtt{sw}$)
* $\mathtt{lw}$ 與 $\mathtt{sw}$ 中的 base register 是 bits 25-21 的 rs
* $\mathtt{lw}$、$\mathtt{sw}$ 與 $\mathtt{beq}$ 中的 bits 15-0 為 16-bits 的 offset
* destination register 有兩種不同的位置
* 對 $\mathtt{lw}$ 來說在 bits 20-16 (即 rt)
* 對 R-format 來說在 bits 15-11 (即 rd)

此外，所有的 control signal 都是統一由 control unit 來發送 (見下圖)，control unit 會根據輸入 instruciton 的 OPcode 來判斷當前是執行何種指令，並根據指令的運作模式來發送訊號給 MUX 來控制各節點的輸出。


上圖中各編號的說明如下:
1. 根據輸入的 OPcode 來判斷當前執行何種指令，才知道要發送哪種訊號
2. ALU control: 另一種控制 ALU 的 control unit (之後會提到)
2.1 僅有 OPcode 的資訊，ALU不見得知道該做何種運算 (例如 R-format 的 OPcode 都是 0)
2.2 還需要 bits 5-0 的 funct 才可進一步判斷
3. 要不要做 branch 的跳轉並不是單純由 control 來決定，還需要打溝處的配合才能決定

#### 1.2 Example: $\mathtt{add}$
##### Instruction fetch
再次以 add 的運算為例。首先先擷取指令，包含兩個動作: (1) `instruction = mem[PC]` 將 instruction 從 memory 移出 (2) 執行 `PC = PC + 4`


##### Instruction decode
擷取兩個 register 作為 operand 並對 instruction 解碼。如下圖所示，進行 add 運算時，綠色的 MUX 會被設為 0 來選擇 bus B 作為 ALU 的另一個輸入。紅色的 MUX 會被設為 0 來選擇執行 PC + 4 而不是 branch


##### ALU operation: R[rs] + R[rt]
兩個 register 中的資料藉由 bus A 與 bus B 輸入至 ALU 後進行相加，並將結果傳送到下紅色的 MUX


:::danger
注意，在此階段中 data memory 內部也會計算 address 並根據計算所得的 address 來讀取資料，再傳送至下紅線的 MUX
:::

##### Write back
將資料寫入至 destination register，包含兩個步驟: (1) `R[rd] = ALU` 將結果寫入 rd (2) `PC = PC + 4` 計算下一個指令的位置，見下圖。


粉紫色 control 所發出的 signal 中，綠色線段的 MUX 會被設為 0，表示接收 ALU 相加後的結果而不是 read data 所讀取的資料。結果經由紅色線段的 bus W 回傳至 write register 中，此時 control 所發出的訊號會讓 RegWrite 設為 1，以此來控制將資料寫入到 rd 中。

#### 1.3 Example: $\mathtt{lw}$
執行 load 運算時，需要從 \$rs 中取出 base address 再與 immediate-16 計算 target address，最後從 target address 中取出資料寫入 \$rt 中，具體指令為: `R[rt] = Mem[ R[rs] + sign_extend[imm16]]`，datapath 如下圖所示。


1. 因為從 memory 載入的資料會被寫進 \$rt，編號 1 的 MUX 會被設為 0 (set to 0)， 並將 \$rt 指向的 register 位址輸出至 write register
2. 因為要與使用到 imm-16 來計算 address，所以綠色 control 會發出訊號使編號 2 的 MUX 被設為 1 (set to 1)，用來接收 sign extend 後的 imm-16
3. 載入資料時，control 發出訊號給編號 3 的 MUX 使其設為 1 (set to 1)，用來接收 address 中的資料並傳給 bus W
4. load 的過程沒有做 branch，所以編號 4 的 MUX 會被設為 0，用來執行基本的 PC + 4
5. control 會發出訊號使編號 5 的 RegWrite = 1，此時才可將資料寫入 register

#### 1.4 Example: $\mathtt{beq}$
執行 $\mathtt{beq}$ 時需要先判斷 \$rs 與 \$rt 中的資料是否相等，根據是否相等來決定要執行下一行指令 (PC + 4) 還是做 branch，具體過程為:

if (R[rs] - R[rt] == 0) # 判斷
    zero = 1
else
    zero = 0

if zero == 1            # next instruction
    PC = PC + 4 + sign_ext[imm16]||00
else
    PC = PC + 4

datapath 如下圖所示:
1. control 會發出訊號使編號 1 的 MUX 設為 0，接收由 bus B 傳遞來自 \$rt 的資料
2. ALU 的減法運算由 control 所發出的訊號影響編號 2 的 ALU control，再透過 ALU control 發出訊號使 ALU 做減法來比較 \$rs 與 \$rt 是否相等
3. \$rs 與 \$rt 相減後是否為 0，會有 ALU 以及 control 所發出的訊號控制編號 3 的 MUX，以此決定要做 PC + 4 還是 branch
4. 編號 4 的 memory 內部一樣會計算 address 並讀取資料，但可以透過 control 發出的訊號影響編號 5 的 RegWrite = 0，藉此讓資料不要被寫入至 register


### 2. ALU controller (step 5a)
對於 ALU 而言，某些情況下可以從 instruction 的 OPcode 知道要做哪種運算:

* 看到 $\mathtt{lw}$ 與 $\mathtt{sw}$ 知道要做加法 (add)
* 看到 $\mathtt{beq}$ 知道要做減法 (sub)
* 看到 R-format 則不確定要做哪種運算，因為 OPcode 都是 0

由上可知，ALU 運算方式的判斷可以使用 2 個 bits 來控制，如下圖藍色標記所示


#### 2.1 ALU control
回顧 Lecture 03 的 Sec. 3.1 與 Sec. 3.2，對於 R-format 來說要做哪種運算可以透過 ALU control 來控制 (見下表)，這裡所說的 ALU control 就是上圖 ALU control 的輸出訊號，共有 4-bits

| ALU Control | Function |
| :-: | :-: |
| 0000 | and |
| 0001 | or |
| 0010 | add |
| 0110 | subtract |
| 0111 | set on less than |
| 1100 | NOR |

仔細看上圖的 datapath 會發現，ALU control 會有兩個輸入，一個來自於 instruction[6-0]，也就是 R-format 中的 funct filed (6-bits)，另一個是由 main control 所發出的訊號 (2-bits)。單看 main control 與 ALU control 的細部分解如下圖所示


Main control 會根據 instruction 的 OPcode 來輸出不同的訊號，編號 1 所指的 7-bits 是指扣除 ALUop 後剩下的 7 個不同位置的 MUX (i.e. 可參考上上圖中橘色 control 所發出的 8 種訊號)。第 8 個訊號會傳遞 2-bits 的 ALUop 給 ALU control，用來告訴 ALUcontrol 目前是 3 種狀況的哪一種:

* Load/store requirt ALU performing add: 00
* beq/bne require ALU performing sub: 01
* R-format need to reference funct field of instruction: 10

可用下列表格呈現。表格中左邊紅框指的是 ALUcontrol 的兩個輸入: ALUop 與 funct，右邊紅框指的是對應的 ALUcontrol 的輸出。其中因為 $\mathtt{lw}$、$\mathtt{sw}$ 與 $\mathtt{beq}$ 等 instruction 沒有 funct field，所以用 xx 表示


:::info
:bulb: 上述的輸出與輸入是如何對應與計算的 :question:
:::

#### 2.2 Logic equation for ALUcontrol
##### ALUcontrol bit[3]
將上述 ALUcontrol 的兩個輸入與輸出整理誠如下表，可以發現到 ALUcontrol 的 bit[3] 是一個常數 (橘框，都是 0)，表示該位元沒有意義，所以輸入與輸出不會影響到 bit[3] 的結果。

此外，因為 lw/sw 與 beq 沒有 funct bit，所以不會影響到輸出結果 (紅框處)。R-format 中 ALUop 的第 0 bit 以及 funct bit 的第 5 與 4 bit 都是 0，也可以視為不影響輸出結果的常數 (綠框處)


:::info
註：表格中第 1 列是對應 lw 與 sw，第 2 列對應 beq，第 3 列到第 7 列對應 R-format
:::

##### ALUcontrol bit[2]

1. 對 ALUcontrol 的 bit[2] 來說，只要 ALUop 的 bit[0] 是 1 則結果就是 1 (藍線處)
2. 不論 funct 的 bit[3] 是 0 還是 1，結果都會是 1，表示 funct 的 bit[3] 不會影響到結果 (紅圈處)
3. 只有 ALUop 的 bit[1] 以及 funct 的 bit[2:0] 會影響到輸出結果 (黃圈與綠框處)

總結來說，ALUcontrol 的 bit[2] 可以透過以下邏輯運算式得到:

$$
\text{ALUcontrol [2]} = \text{ALUop [1]} + \text{ALUop [1]} \cdot \text{funct' [2]} \cdot \text{funct[1]} \cdot \text{funct'[0]}
$$

:::warning
$\text{funct' [2]}$ 表示 $\text{funct [2]}$ 的反向，也就是當 $\text{funct [2]} = 1$ 時，$\text{funct' [2]} = 0$
:::

##### ALUcontrol bit[1]

1. 以前兩列來說，不論 ALUop 的 bit[0] 是 0 或 1，都不會影響輸出結果 (紅框處)，只有 ALUop 的 bit[1] 會影響輸出 (小綠框處)
2. 不論 funct 的 bit[3]與 bit[1] 是 0 還是 1，同樣不會影響到結果 (藍框處)
3. 只有 ALUop 的 bit[1] 以及 funct 的 bit[2] 與 bit[0] 會影響到輸出 (大綠框處)

總結來說，ALUcontrol 的 bit[1] 可以透過下列邏輯算式得到:

$$
\text{ALUcontrol [1]} = \text{ALUop' [1]} + \text{ALUop [1]} \cdot \text{funct' [2]} \cdot \text{funct' [0]}
$$

##### ALUcontrol bit[0]

ALUcontrol 的 bit[0] 可以透過下列邏輯算式得到:

$$
\begin {align}
\text{ALUcontrol [0]} = &\text{ALUop [1]} \cdot \text{funct' [3]} \cdot \text{funct [2]} \cdot \text{funct' [1]} \cdot \text{funct [0]}+\\
&\text{ALUop [1]} \cdot \text{funct [3]} \cdot \text{funct' [2]} \cdot \text{funct' [1]} \cdot \text{funct' [0]}
\end{align}
$$

根據上述的算式，可以設計 ALUcontrol block 為下列形式


### 3. Main controller (step 5b)
前一節說明的是 ALUcontrol 的輸出 signal 要怎麼計算與設計，此節討論 main control 輸出的 signal 要如何計算與設計。

以 single cycle 的 datapath 來看 (下圖)


可以發現到 main control 有 6 個 input ( 6-bits for OPcode) 以及 9 個 output (ALUop 的輸出是 2-bits，要視為 2 個輸出)，根據輸入與輸出的狀況可以列出下列的 truth table (紅框的 func 是 ALUcontrol 的輸入，藍框的 op 才是 main control 的輸入)


此處以 RegWrite 舉例說明。因為只有 R-format 以及 lw 的情況下要寫入資料 (RegWrite = 1)，所以可得 RegWrite 的邏輯運算如下:

$$
\begin{align}
\text{RegWrite} = &\text{R-format} + \text{lw} \\
= &\text{op' [5]} \cdot \text{op' [4]} \cdot \text{op' [3]} \cdot \text{op' [2]} \cdot \text{op' [1]} \cdot \text{op' [0]} +\\
&\text{op [5]} \cdot \text{op' [4]} \cdot \text{op' [3]} \cdot \text{op' [2]} \cdot \text{op [1]} \cdot \text{op [0]}
\end{align}
$$


## Sec. 4.6 Adding jump instruction
$\mathtt{jump}$ 的指令如下


$\mathtt{jump}$ 指令在計算 target 時是使用以 word 為單位的 word address 方式，會牽涉到下列內容:

* 前一個 PC 的 前 4 bits
* 指令中 26-bits 的 address (i.e., $\mathtt{jump}[25:0]$)
* 左移 2-bits (append 00)

因次我們需要在 single cycle datapath 中新增一些 control signal 來控制與計算 target address，具體如下圖所示


1. 編號 1 處表示將 instrustion[25:0] 的 address bit 做 shift left 2-bits
2. 編號 2 處表示跟下一步的 PC + 4 做 concate，補在 instruction[27:0] 的前面 4-bits，形成 28-bits 的 jump address 輸出
3. 編號 3 的 MUX 表示要選擇 sequenntial 的執行 (PC + 4) 還是做 branch，由 main control 所發出的 branch signal 控制
4. 編號 4 的 MUX 決定是否要做 jump，由 main control 所發出的 jump signal 控制