# Ch.4-1 Single-Cycle Processor
###### tags: `Computer Organization`, `計算機組織`

## Outline
1. Designing a processor (背景知識、ISA)
2. Building the datapath (設計資料路徑)
3. **A single-cycle implementation** (由前兩節合成)
4. Control for the single-cycle CPU (控制CPU要做什麼運算)
(1) Control of CPU operations
(2) ALU controller (控制ALU)
(3) Main controller (控制整個CPU-分析指令、產生動作)

## 4-1--1 Designing a Processor
### Instruction Execution
指令被執行的流程：
1. 透過PC得知指令位子
2. 到instruction memory取出指令
3. 指令中有暫存器編號則到對應暫存器取出資料
4. 判斷要做哪一種運算
(1) ALU-一般算數、Load/Store、Branch
(2) 存取記憶體
(3) 令`PC = PC + 4`
### Logic Design Basics
#### 1.Information encode in binary
低電壓表示0；高電壓表示1
一個bit用一個wire傳輸
multi-bit用multi-wire(bus)傳輸
#### 2.Combinational element
運算，輸出boolean function
看圖，是用各種gate
#### 3.State/Sequential elements
:::info
儲存資訊
看圖，可用栓鎖器latch，也可用正反器flip-flop
（注意此處是用主從式架構）
其中latch是**level-sensitive**(準位觸發)
而flip-flop是**edge-sensitive**(邊緣觸發)
（一般不喜歡準位觸發，因為希望某些動作是「瞬間」發生）
:::
### Sequential Elements
下圖是D型正反器的介紹圖，上為一般型，下為加入enable功能
### Clocking Methodology
配合clock的概念，設計電路會變得簡單
因為只要控制組合電路的運算時間是在clock與clock之間即可。
也就是說：
:::danger
最長的組合電路所花費的時間**一定不能比clock的週期長**
:::
換句話說，就是最長的組合電路delay time決定了clock period/time，所以在下一個clock來臨之前，要將預計運算的資料準備好。

### How to Design a Processor?
:::info
1. 分析有哪些指令，以及那些指令要做什麼→得知datapath應有什麼、要用什麼
2. 將datapath要用的元件建立，並建立clocking的機制
> [color=#907bf7]single-cycle的話，clocking機制很簡單→每個指令一個cycle
3. 將datapath要用的元件組合起來
4. 分析指令對應的datapath運作時機，並規劃control logic決定不同的datapath何時運作
5. 實現control logic
:::
#### 1.Analyze Instruction Set
此處不會真正設計一個MIPS處理器，而是透過設計其中幾個指令（R-format、L/S、immediate operand、branch、jump）來窺得全貌！
其中，做`sign extenstion`是為了維持原本的正負；最後面加上`:00`表示乘以4倍，因為branch是word address，而最小定址單位是byte，要從byte得到word就必須乘以4（1 word = 4 byte）
:::info
根據上圖，可以得知我們需要的元件有：
* Memory：用來存資料
* Register：至少要兩個可以讀的＆一個可寫入的
* PC：存指令位子
* Extender：做`zero extension` or `sign extension`
* ALU：做基本加減運算
* 另外的可以令`PC = PC + 4`的加法元件
:::
## 4-1--2 Building Datapath
### Datapath Components
#### 1.運算部分
利用adder、multiplexer、register等建構datapath

可以發現上述元件的input都是32bit，因為MIPS中暫存器的大小是32bit
此外，每個元件都還會有額外控制線：
Adder有CarryIn跟CarryOut；MUX有select；ALU有ALUop/ALU control

#### 2.儲存部分
利用register（可以是D flip-flop做成）存資料
一次處理32bits（因為MIPS中一個word就是32bits）
另外！還會加上write enable的訊號，決定資料是否寫入
最後！因為是sequential circuit，所以要有clock，決定寫入時機
### Storage Element: Register File
（此處的file不是檔案的意思，只是用來代表"一群"暫存器）
因為MIPS有32個registers，所以上一part設計好的單個register要複製出總共32個
又因為有32個register，所以要用5 bit控制線來選擇暫存器（RA、RB、RW）

RA、RB：同時可以讓所表示的兩個暫存器讀值，讀完將資料放到busA、busB
RW："運算完之後，要存入結果的暫存器的"編號，將放在busW的資料存入對應暫存器
Write Enable：確定是否真的要把資料寫入暫存器
Clk：因為是sequential circuit，所以要遵循clock，決定寫入的時機（附圖採用負緣觸發）

### Storage Element: Memory
因為MIPS中的address有32bits，所以最大定址範圍是2^32 = 4GB

DataOut：從記憶體讀出的資料，一次是32bit（因為MIPS一個word = 4byte）
但最小的定址單位是1byte = 8bit（詳見Ch.2）
DataIn：資料寫入記憶體（一次以1 word為單位）
Write Enable：確定資料是否真的要寫入記憶體
Memory Read：控制現在記憶體是要read還是write
Clk：因為是sequential circuit，所以要遵循clock，決定寫入的時機

:::warning
此處因不想太複雜，所以直接獨立出read跟write，但不可能讓記憶體"同時"讀寫
故一般市面上買到的、我們常用的記憶體將R/W整合，只需要一個bit(Write Enable)來判斷要R/W
但是這樣不是讀就是寫，或許你沒有一定要它動，它卻一接電就會讀or寫，所以會造成額外的cost
因此實際上memory會有一條chip select的控制線，為1時是選擇記憶體，此時記憶體才會開始運作；為0時沒有選擇記憶體，所以是忽略write enable訊號
:::
### Datapath Assembly
將元件組合起來
1. Instruction fetch unit
首先，從最簡單的元件開始下手
這個單元負責把指令從記憶體中讀出來
→需要用到PC、instrction memory
Step1. 得到PC存的資料（記憶體位址）
Step2. 到instruction memory中，找尋PC所存之位址對應的指令還有要用的暫存器
Step3. 取出指令，並更新`PC = PC + 4`；有暫存器的話暫存器開始讀值
**Note：** 如果是branch或是jump指令，則要對PC另外處理
2. Addition and Subtract
處理R-format的資料
會需要暫存器跟ALU，分別負責存資料跟運算
（橘色的是控制線）
3. Store/Load Operations
屬於I-format的一種（做**記憶體存取**→**最複雜的一種**）
需要暫存器、ALU、處理sign extension、記憶體
（橘色的是控制線）
**Note 1**
:::info
上圖是進行Load運算。注意：記憶體的資料是放到暫存器的**rt**欄位（不是rd！因為I-format將rd field改用在immediate field中，所以沒有rd可以用）。
首先從rs讀取`base`以及將immediate的值送進sign extend，然後兩者的結果一起送進ALU，計算出address，再從memory中對應的位址取出資料，送回register的busW，也就是存入rt。
:::
**Note 2**
:::info
如何進行Store運算？跟Load很像，只是記憶體資料輸送方向相反。
一樣是將rs的位址當作base，再把做過sign extension的immediate當作offset，得到相應資料；唯一差別是因為要從暫存器寫回記憶體中，所以rt讀取到的資料要直接連接到memory單元中write data的部分（所以可以注意到memory單元有`MemWrite`的控制線）。
:::
4. 整合上面兩個(2跟3)
**KEY POINT：** 盡量`reuse`，重複使用到原本已有的部分

| 相異處 | Ｒ－format | Ｉ－format |
| ------ | ----------- | ----------- |
| 寫入的暫存器 | rd | rt |
| 運算來源 | 只有暫存器 | 暫存器或immediate |
| 結果來源 | ALU | Memory |

Ｑ：如何將具有相異之處的電路結合成同一個電路？
Ａ：用**MUX**。
上述提及**三個相異點**，所以**用了三個MUX**。
綜合下來，也就是說，之後的control signal是要用在MUX選擇上的。
5. Branch Operations
需要ALU、sign extend、shift
以`beq`為例，是用ALU中的sub運算，再用zero output判斷是否相等
若相等（zero bit = 1）→跳到label處（`PC = PC + 4 + (SignExt(Imm16) * 4)`）
若不相等（zero bit = 0）→跳到下一行指令（`PC = PC + 4`）
**Note：**
:::info
因為branch跳的地方是某個指令的位址，MIPS中每個指令就是一個word，會做word align，所以要用**word address**，但是也就必須在最後乘上4，因為定址的最小單位是byte，要從byte得到word。（1 word = 4 byte）
:::
從register file取出rs跟rt的值，透過ALU用sub去比較兩者的大小（相減看後是否為0，是則ALU的zero bit = 1，反之為0）。
label表示的immediate做sign extension，並shift 2 bit成為target address。
根據ALU的zero bit判斷要branch到`PC + 4`就好，還是到`PC + 4 + target address`
## 4-1--3 Single-Cycle Implementation
::: danger
核心：每個指令從**開始到結束**花費的時間是**1個cycle**
:::

現已做出的電路有：
1. Instruction Fetch Unit
2. Branch
3. R-format + Memory + Add/Sub
將可共用處結合，相異處用MUX做選擇，則可作出如下的single-cycle processor

:::info
> [color=#907bf7]ps. MUX是第幾個是從左往右數。
1. 透過PC來做instruction位址的存取
2. 取出指令後，到register file存取暫存器
3. 根據指令，透過第一個MUX選擇，看是R-format還是I-format，決定要存入的暫存器
4. 再透過第二個MUX，決定要運算的東西要直接傳給ALU還是先將immediate做sign extension再傳給ALU
5. 做L/S時，需要去data memory裡面存取資料再送出；一般的R-format或某些I-format運算只需要經過ALU就可以輸出→此時用第四個MUX選擇輸出哪個結果
6. 需要branch（zero bit = 1）時，target address是把immediate做sign extension後乘上4（左移2bit）再送進ALU跟PC+4運算；不需要branch時（zero bit = 0），target address就直接是PC+4→透過ALU的zero bit連接第三個MUX選擇要輸出的target address是哪一個，並送到PC更新。
:::
::: warning
橘色字體的部分是control signal要處理的範圍
很重要！！！因為他負責控制如何做出正確的運算
:::
#### Clocking Methodology
clock決定信號什麼時候被讀寫
single-cycle時，所有的運作都會在一個cycle內完成（包含memory access的時間）
**所以一個cycle的長短，取決於combinational circuit最長的delay是多少**
新一個cycle來臨時，會同時更新上一個cycle的結果＆存取當下接收到的指令並運算
從上一小節的電路可以發現combinational circuit必定跟storage element連接
且組合電路的input是儲存元件的output；組合電路的output是儲存元件的input

影片10:39 - 15:10是下圖的描述，很重要，多看幾次！！

:::info
> [color=#907bf7]這是一個Processor執行R-format指令的過程
>> [color=red]所以storage element只有PC跟register file
1. (粉色)當clock edge來臨，開始運作
2. (綠色)PC更新成PC+4
3. (橘紅)Control將指令解碼，對各個MUX下命令
4. (橘紅)從instruction memory中取出rs、rt的值，並決定將結果寫入rd
5. (藍色)花費一點時間讀取暫存器，將rs、rt的值丟給busA、busB然後交給ALU
> [color=red]注意藍色跟橘紅色的運作是同時開始，只是因為暫存器的讀取時間較長，所以橘紅色做完了之後藍色還在做（但實際上不一定是暫存器讀取時間較長!還是要看運作內容，反正要等最久的人就對了。）
6. (灰綠)一段時間後，ALU運算完，再等待一段時間後，待下個clock edge來臨，更新資料
> 注意這邊等待時間並不是浪費，因為可能會有memory access，剛好可在這段時間完成
7. (黃色)更新資料(PC跟register file)
:::
#### The Critical Path

花費最久時間的（最長delay）的datapath稱為critical path
crititcal，主要的，表示這用來決定clock cycle的cycle time長短

:::warning
花費最長時間的路徑，同時應該是距離最長的路徑
也就是**Load**
因為他要讓PC更新成PC+4，還要用暫存器存記憶體中的資料，因為要用到記憶體，所以需要透過ALU計算位址，然後到記憶體中對應的位址取出資料，傳送到暫存器
換句話說，所有的單元都用到了，所以是最長路徑
:::

影片17:20 - 20:00解釋lw的運作

:::info
> 黃色框框包含的部分，是黃色底線control經過解碼後得出的控制訊號
1. 第一個clock來臨時，開始動作
2. 先令`PC = PC + 4`
3. 透過instruction memory取出rs、rt、instruction
4. 對instruction解碼，得到control要用的控制訊號
5. 與4同時，讀取rs、rt的值到busA、busB
6. 因為是做`lw`，所以不是要把rt的值拿來算，而是要把rs當作base，再將immediate的值做sign extension後作為offset，給ALU運算（所以此處要考慮到sign extend跟MUX選擇的delay，而實際上這兩者因為本身硬體的關係，delay時間都不長）
7. ALU將base加上offset後即為address，於是到memory中對應的位址取出資料，再傳送到register file中的rt
8. 等待下一個clock來臨後，就可以更新rt跟PC的資料
:::
## 4-1--4 Control for the Single-Cycle CPU
介紹controller對CPU運算的影響，並分別介紹ALU controller跟Main controller。
前面小節有提到的**橘色控制線**就是control signal，也就是controller，隨著輸入的不同會直接影響到datapath的運作，進而得到不同的CPU運算結果。
### Control of CPU operations
上圖是送入一個指令時的內部運作圖，先從instruction memory抓出指令，然後到controller解碼得到要運作的指令與對應暫存器，由controller派發指令（輸入對應的訊號到datapath），就是一系列的運作；注意datapath有一個指向controller的訊號`equal`，是用做`beq`指令時，拿來判斷是否相等的，若為相等，就會回傳`equal = 1`給controller（這個訊號線有時會叫zero）。
#### Designing Main Control
根據之前所學，推斷controller應該設計哪些部分。
（以下所述field僅限於MIPS，其他指令集會有所不同。）
1. opcode：表明這個指令要做什麼，佔31-26 bit
2. rs、rt：用來`read`的暫存器，佔25-21、20-16 bit（R-format、beq時會用到）；`lw`、`sw`時，base register都是rs
3. rd：作為destination，用來`write`的暫存器，R-format時佔15-11 bit，I-format時（`lw`）用rt取代
4. immediate：記錄常數，拿來做特殊處理，佔15-0 bit（用在beq、sw、lw）

:::info
因為不同用途的暫存器也不一樣，所以要用**MUX**控制**什麼時候要寫入什麼暫存器**。
:::
1. RegDst：決定要用來`write`的暫存器是rt還是rd
2. ALUSrc：決定ALU的第二個input應該來自暫存器還是sign-extend immediate
3. MemtoReg：決定寫回暫存器的值，應來自memory還是ALU的output
4. PCSrc：當進行`branch`指令時，決定要跳的下一個位址是`PC+4`還是`PC+4+target address`
:::warning
注意圖中有特別標示的地方
:::
1. （綠線）因為R-format的funct field跟I-format的immediate field有重疊，所以當我們使用R-format時，會將immediate牽到ALU controller以控制ALU運算方法
2. （紅圈）當執行`beq`時，會需要經由ALU運算，看zero output的結果，若`zero=1`則代表運算結果為0，那麼便控制要branch的位址是`PC+4+target address`
#### Datapath Operation
1. add
Step1. fetch instruction
Step2. instruction decode and fetch register
Step3. controller開始運作，register file存對應暫存器的值
Step4. controller判斷要令rd為write register、要將rs跟rt傳入ALU運算
Step5. controller將ALU的結果送回register file給rd
2. lw
Step1. fetch instruction
Step2. instruction decode and fetch register
Step3. controller開始運作，register file存對應暫存器的值
Step4. controller判斷要令rt為write register、要將rs跟immediate傳入ALU運算
Step5. controller將ALU的結果送到memory
Step6. controller決定將memory的結果送回register file給rt
3. beq
Step1. fetch instruction
Step2. instruction decode and fetch register
Step3. controller開始運作，register file存對應暫存器的值
Step4. controller判斷要令rd為write register、要將rs跟rt傳入ALU運算（減法）
Step5. 將immediate做sign extension之後再左移2 bit（做word align）
Step6. controller將ALU1的結果（zero bit）跟branch做and，送到ALU2
Step7. controller將ALU2的結果送回PC暫存器並更新
### ALU Controller
#### Control Signals
1. RegDst：決定要用來`write`的暫存器是rt還是rd
2. RegWrite：決定是否真的要寫入值
3. ALUSrc：決定ALU的第二個input應該來自暫存器還是sign-extend immediate
4. MemtoReg：決定寫回暫存器的值，應來自memory還是ALU的output
5. PCSrc：當進行`branch`指令時，決定要跳的下一個位址是
6. MemRd：決定是否真的要讀值
7. MenWr：決定是否真的要寫入值

以下舉例


其中R-format的指令，要做什麼是看funct field；I-format則是看opcode。
可以發現要看的標的不一樣，所以才會分割出ALU controller跟main controller。
main controller用來接收opcode；ALU controller接收funct。

#### Plan for the Controller
:::info
一般而言，I-format指令的opcode直接輸入給main controller，而R-format指令的funct輸入給ALU controller；但有時候I-format的指令也會需要用到ALU（如`lw`/`sw`），所以main controller被設計成可以用2bit控制ALU controller（見上圖中的下表），此時ALU controller的funct input被視為don't care。
:::
#### Logic Equation

上表是ALU controller送出的、用來控制ALU的ALU control信號。
根據此表可以得知，ALU controller的輸入訊號有8bit，輸出有4bit，因此可以得到下表以用來化簡布林代數，做出電路圖。
（這裡化簡跟接電路的方式都是暴力解）
（電路稱為PLA，programming logic array）

### Main Controller
#### Control Signals
:::info
正常而言，31-26bit必為opcode field
R-format時，25-21bit為rs；20-16bit為rt；15-11bit為rd
I-format時，25-21bit為rs；20-16bit為rt；15-0bit為immediate

1. R-format的opcode永遠為0，需要指令看funct field(5-0bit)
2. rs永遠都是用來read
3. rt通常用來read，只有lw時拿來write
4. rd在R-format時用來write，其他format沒有這個欄位
:::

下圖是main controller對應各種不同運作的真值表
由於I-format的immediate field與R-format的funct field重疊
所以使用I-format指令時，不需要管funct field（故為don't care）


根據真值表，可以得出main controller電路圖如下：

#### Implementing Jumps

觀察J-format指令的欄位，可以發現其表示地址的部分只有26bit
因其是用byte表示，左移2bit將之轉換成word後，要再向PC借最高的4bit
因此可以得出如下電路圖，藍框部分

## Conclusion
可以發現single-cycle processor花費的時間非常長，因為所有指令都必須在一個cycle內完成，所以大家**都**要等待datapath最長的指令（`lw`），即便本身很快就執行完了，還是要空等，直到下一個cycle來臨
因為每個指令等待`lw`的時間都被浪費掉了，所以single-cycle效率不彰
### Summary
1. CPI = 1 (因為是single-cycle)
2. clock cycle time較長
3. 設計步驟：分析指令集以得知所需datapath、選擇完成datapath要用到的元件、組合與需求對應的datapath、分析datapath中用來選擇要做什麼指令的控制訊號、將controller電路做好

※ MIPS使得設計controller變得簡單
因為MIPS當初設計時就想要做得很簡單，所以
1. 所有指令大小都一樣
2. source register位子都一樣
3. 各種instruction format的欄位大同小異
4. ALU運算只需要用到register或immediate（不需要memory差很多）
5. （見CH2的design principles）