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

儲存資訊
看圖，可用栓鎖器latch，也可用正反器flip-flop
（注意此處是用主從式架構）
其中latch是level-sensitive(準位觸發)
而flip-flop是edge-sensitive(邊緣觸發)
（一般不喜歡準位觸發，因為希望某些動作是「瞬間」發生）

Sequential Elements

​​​​下圖是D型正反器的介紹圖，上為一般型，下為加入enable功能

Clocking Methodology

​​​​配合clock的概念，設計電路會變得簡單
​​​​因為只要控制組合電路的運算時間是在clock與clock之間即可。
​​​​也就是說：

最長的組合電路所花費的時間一定不能比clock的週期長

​​​​換句話說，就是最長的組合電路delay time決定了clock period/time，所以在下一個clock來臨之前，要將預計運算的資料準備好。

How to Design a Processor?

1. 分析有哪些指令，以及那些指令要做什麼→得知datapath應有什麼、要用什麼
2. 將datapath要用的元件建立，並建立clocking的機制

   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）

根據上圖，可以得知我們需要的元件有：

• 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，決定寫入的時機

此處因不想太複雜，所以直接獨立出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

   上圖是進行Load運算。注意：記憶體的資料是放到暫存器的rt欄位（不是rd！因為I-format將rd field改用在immediate field中，所以沒有rd可以用）。
   首先從rs讀取base以及將immediate的值送進sign extend，然後兩者的結果一起送進ALU，計算出address，再從memory中對應的位址取出資料，送回register的busW，也就是存入rt。

   Note 2

   如何進行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：

   因為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

核心：每個指令從開始到結束花費的時間是1個cycle

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

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更新。

橘色字體的部分是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是下圖的描述，很重要，多看幾次！！

這是一個Processor執行R-format指令的過程

所以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

注意藍色跟橘紅色的運作是同時開始，只是因為暫存器的讀取時間較長，所以橘紅色做完了之後藍色還在做（但實際上不一定是暫存器讀取時間較長!還是要看運作內容，反正要等最久的人就對了。）

6. (灰綠)一段時間後，ALU運算完，再等待一段時間後，待下個clock edge來臨，更新資料

   注意這邊等待時間並不是浪費，因為可能會有memory access，剛好可在這段時間完成

7. (黃色)更新資料(PC跟register file)

The Critical Path

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

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

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

黃色框框包含的部分，是黃色底線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）

因為不同用途的暫存器也不一樣，所以要用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
   
   

注意圖中有特別標示的地方

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

一般而言，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

正常而言，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）