如何设计一个控制器来产生信号以控制数据通路

1 . ECE4680 Computer Organization and Architecture Designing Single Cycle Control How to design a controller to produce signals to control the datapath ECE4680 Control.1 2003-3-17 Recap: The MIPS Instruction Formats °All MIPS instructions are 32 bits long. The three instruction formats: 31 26 21 16 11 6 0 • R-type op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits 31 26 21 16 0 • I-type op rs rt immediate 6 bits 5 bits 5 bits 16 bits • J-type 31 26 0 op target address 6 bits 26 bits °The different fields are: • op: operation of the instruction • rs, rt, rd: the source and destination registers specifier • shamt: shift amount • funct: selects the variant of the operation in the “op” field • address / immediate: address offset or immediate value • target address: target address of the jump instruction ECE4680 Control.2 2003-3-17 

2 . Recap: The MIPS Subset 31 26 21 16 11 6 0 °ADD and subtract op rs rt rd shamt funct • add rd, rs, rt 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits • sub rd, rs, rt 31 26 21 16 0 °OR Imm: op rs rt immediate • ori rt, rs, imm16 6 bits 5 bits 5 bits 16 bits °LOAD and STORE • lw rt, rs, imm16 • sw rt, rs, imm16 °BRANCH: • beq rs, rt, imm16 °JUMP: 31 26 0 • j target op target address 6 bits 26 bits ECE4680 Control.3 2003-3-17 Recap: A Single Cycle Datapath °We have everything except control signals (underline) • Today’s lecture will show you how to generate the control signals Branch Instruction<31:0> <21:25> <16:20> <11:15> Instruction <0:15> Jump Fetch Unit Rd Rt RegDst Clk 1 Mux 0 Rs Rt Rs Rt Rd Imm16 RegWr 5 5 5 ALUctr busA Zero MemWr MemtoReg Rw Ra Rb busW 32 ALU 32 32-bit 32 0 Registers busB 0 32 Mux Clk Mux 32 Data In 32 WrEn Adr 1 Extender 1 32 imm16 Data 32 16 Memory Clk ALUSrc ExtOp ECE4680 Control.4 2003-3-17 

3 . The Big Picture: Where are We Now? °The Five Classic Components of a Computer Processor Input Control Memory Datapath Output °Today’s Topic: Designing the Control for the Single Cycle Datapath ECE4680 Control.5 2003-3-17 RTL: The ADD Instruction 31 26 21 16 11 6 0 op rs rt rd shamt funct 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits °add rd, rs, rt • mem[PC] Fetch the instruction from memory • R[rd] <- R[rs] + R[rt] The actual operation • PC <- PC + 4 Calculate the next instruction’s address °A note: 2nd step and 3rd step can be done in parallel. ECE4680 Control.6 2003-3-17 

4 . Instruction Fetch Unit at the Beginning of Add / Subtract °Fetch the instruction from Instruction memory: Instruction mem[PC] • This is the same for all instructions 30 Addr<31:2> PC<31:28> 30 Addr<1:0> “00” Target 4 1 Instruction Instruction<25:0> 30 Mux 26 Memory PC 0 Adder 30 0 32 30 Mux “1” Adder 1 Jump = previous Instruction<31:0> Clk 30 SignExt imm16 30 Instruction<15:0> 16 Branch = previous Zero = previous ECE4680 Control.7 2003-3-17 The Single Cycle Datapath during Add and Subtract 31 26 21 16 11 6 0 op rs rt rd shamt funct °R[rd] <- R[rs] + / - R[rt] Branch = 0 Instruction<31:0> <21:25> <16:20> <11:15> Instruction <0:15> Jump = 0 Fetch Unit Rd Rt RegDst = 1 Clk 1 Mux 0 Rs Rt ALUctr = Add Rs Rt Rd Imm16 RegWr = 1 5 5 5 or Subtract MemtoReg = 0 busA Zero MemWr = 0 Rw Ra Rb busW 32 ALU 32 32-bit 32 0 Registers busB 0 32 Mux Clk Mux 32 32 WrEn Adr 1 Extender 1 Data In 32 imm16 Data 32 16 Memory Clk ALUSrc = 0 ExtOp = x ECE4680 Control.8 2003-3-17 

5 . Instruction Fetch Unit at the End of Add and Subtract °PC <- PC + 4 • This is the same for all instructions except: Branch and Jump 30 Addr<31:2> PC<31:28> 30 Addr<1:0> “00” Target 4 1 Instruction Instruction<25:0> 30 Mux 26 Memory PC 0 Adder 30 0 32 30 Mux “1” Adder 1 Jump = 0 Instruction<31:0> Clk 30 SignExt imm16 30 Instruction<15:0> 16 Branch = 0 Zero = x ECE4680 Control.9 2003-3-17 The Single Cycle Datapath during Or Immediate 31 26 21 16 0 op rs rt immediate °R[rt] <- R[rs] or ZeroExt[Imm16] Branch = 0 Instruction<31:0> <21:25> <16:20> <11:15> Instruction <0:15> Jump = 0 Fetch Unit Rd Rt RegDst = 0 Clk 1 Mux 0 Rs Rt ALUctr = Or Rs Rt Rd Imm16 RegWr = 1 5 5 5 MemtoReg = 0 busA Zero MemWr = 0 Rw Ra Rb busW 32 ALU 32 32-bit 32 0 Registers busB 0 32 Mux Clk Mux 32 32 WrEn Adr 1 Extender 1 Data In 32 imm16 Data 32 16 Memory Clk ALUSrc = 1 ExtOp = 0 ECE4680 Control.10 2003-3-17 

6 . The Single Cycle Datapath during Load 31 26 21 16 0 op rs rt immediate °R[rt] <- Data Memory {R[rs] + SignExt[imm16]} Branch = 0 Instruction<31:0> <21:25> <16:20> <11:15> Instruction <0:15> Jump = 0 Fetch Unit Rd Rt RegDst = 0 Clk 1 Mux 0 Rs Rt ALUctr Rs Rt Rd Imm16 RegWr = 1 5 5 5 = Add MemtoReg = 1 busA Zero MemWr = 0 Rw Ra Rb busW 32 ALU 32 32-bit 32 0 Registers busB 0 32 Mux Clk Mux 32 WrEn Adr 1 Extender 1 Data In 32 imm16 Data 32 32 16 Memory Clk ALUSrc = 1 ExtOp = 1 ECE4680 Control.11 2003-3-17 The Single Cycle Datapath during Store 31 26 21 16 0 op rs rt immediate °Data Memory {R[rs] + SignExt[imm16]} <- R[rt] Branch = 0 Instruction<31:0> <21:25> <16:20> <11:15> Instruction <0:15> Jump = 0 Fetch Unit Rd Rt RegDst = x Clk 1 Mux 0 Rs Rt ALUctr Rs Rt Rd Imm16 RegWr = 0 5 5 5 = Add MemtoReg = x busA Zero MemWr = 1 Rw Ra Rb busW 32 ALU 32 32-bit 32 0 Registers busB 0 32 Mux Clk Mux 32 32 WrEn Adr 1 Extender 1 Data In 32 imm16 Data 32 16 Memory Clk ALUSrc = 1 ExtOp = 1 ECE4680 Control.12 2003-3-17 

7 . The Single Cycle Datapath during Branch 31 26 21 16 0 op rs rt immediate °if (R[rs] - R[rt] == 0) then Zero <- 1 ; else Zero <- 0 Branch = 1 Instruction<31:0> <21:25> <16:20> <11:15> Instruction <0:15> Jump = 0 Fetch Unit Rd Rt RegDst = x Clk 1 Mux 0 Rs Rt ALUctr = Rs Rt Rd Imm16 RegWr = 0 Subtract 5 5 5 MemtoReg = x busA Zero MemWr = 0 Rw Ra Rb busW 32 ALU 32 32-bit 32 0 Registers busB 0 32 Mux Clk Mux 32 32 WrEn Adr 1 Extender 1 Data In 32 imm16 Data 32 16 Memory Clk ALUSrc = 0 ExtOp = x ECE4680 Control.13 2003-3-17 Instruction Fetch Unit at the End of Branch 31 26 21 16 0 op rs rt immediate °if (Zero == 1) then PC = PC + 4 + SignExt[imm16]*4 ; else PC = PC + 4 30 Addr<31:2> PC<31:28> 30 Addr<1:0> “00” Target 4 1 Instruction Instruction<25:0> 30 Mux 26 Memory PC 0 Adder 30 0 32 30 Mux “1” Adder 1 Jump = 0 Instruction<31:0> Clk 30 SignExt imm16 30 Instruction<15:0> 16 Assume Zero = 1 to see the interesting case. Branch = 1 Zero = 1 ECE4680 Control.14 2003-3-17 

8 . The Single Cycle Datapath during Jump 31 26 0 op target address °Nothing to do! Make sure control signals are set correctly! Branch = 0 Instruction<31:0> <21:25> <16:20> <11:15> Instruction <0:15> Jump = 1 Fetch Unit Rd Rt RegDst = x Clk 1 Mux 0 Rs Rt ALUctr = x Rs Rt Rd Imm16 RegWr = 0 5 5 5 MemtoReg = x busA Zero MemWr = 0 Rw Ra Rb busW 32 ALU 32 32-bit 32 0 Registers busB 0 32 Mux Clk Mux 32 32 WrEn Adr 1 Extender 1 Data In 32 imm16 Data 32 16 Memory Clk ALUSrc = x ExtOp = x ECE4680 Control.15 2003-3-17 Instruction Fetch Unit at the End of Jump 31 26 0 op target address °PC <- PC<31:29> concat target<25:0> concat “00” 30 Addr<31:2> PC<31:28> 30 Addr<1:0> “00” Target 4 1 Instruction Instruction<25:0> 30 Mux 26 Memory PC 0 Adder 30 0 32 30 Mux “1” Adder 1 Jump = 1 Instruction<31:0> Clk 30 SignExt imm16 30 Instruction<15:0> 16 Branch = 0 Zero = x ECE4680 Control.16 2003-3-17 

9 . A Summary of the Control Signals See func 10 0000 10 0010 We Don’t Care :-) Appendix A op 00 0000 00 0000 00 1101 10 0011 10 1011 00 0100 00 0010 add sub ori lw sw beq jump RegDst 1 1 0 0 x x x ALUSrc 0 0 1 1 1 0 x MemtoReg 0 0 0 1 x x x RegWrite 1 1 1 1 0 0 0 MemWrite 0 0 0 0 1 0 0 Branch 0 0 0 0 0 1 0 Jump 0 0 0 0 0 0 1 ExtOp x x 0 1 1 x x ALUctr<2:0> Add Subtract Or Add Add Subtract xxx 31 26 21 16 11 6 0 R-type op rs rt rd shamt funct add, sub I-type op rs rt immediate ori, lw, sw, beq J-type op target address jump ECE4680 Control.17 2003-3-17 The Concept of Local Decoding op 00 0000 00 1101 10 0011 10 1011 00 0100 00 0010 R-type ori lw sw beq jump RegDst 1 0 0 x x x ALUSrc 0 1 1 1 0 x MemtoReg 0 0 1 x x x RegWrite 1 1 1 0 0 0 MemWrite 0 0 0 1 0 0 Branch 0 0 0 0 1 0 Jump 0 0 0 0 0 1 ExtOp x 0 1 1 x x ALUop<N:0> “R-type” Or Add Add Subtract xxx func ALU ALUctr op Main 6 ALUop Control 3 6 Control (Local) N ALU ECE4680 Control.18 2003-3-17 

10 . The Encoding of ALUop func op 6 ALU ALUctr Main ALUop Control 6 Control 3 (Local) N How many bits? °In this exercise, ALUop has to be 2 bits wide to represent: • (1) “R-type” instructions • “I-type” instructions that require the ALU to perform: Why not - (2) Or, (3) Add, and (4) Subtract consider J-type? °To implement the full MIPS ISA, ALUop hat to be 3 bits to represent: • (1) “R-type” instructions • “I-type” instructions that require the ALU to perform: - (2) Or, (3) Add, (4) Subtract, and (5) And (Example: andi) R-type ori lw sw beq jump ALUop (Symbolic) “R-type” Or Add Add Subtract xxx ALUop<2:0> 1 00 0 10 0 00 0 00 0 01 xxx ECE4680 Control.19 2003-3-17 The Decoding of the “func” Field func op 6 ALU ALUctr Main ALUop Control 6 Control 3 (Local) N R-type ori lw sw beq jump ALUop (Symbolic) “R-type” Or Add Add Subtract xxx ALUop<2:0> 1 00 0 10 0 00 0 00 0 01 xxx 31 26 21 16 11 6 0 R-type op rs rt rd shamt funct Recall ALU Homework (also P. 286 text): funct<5:0> Instruction Operation ALUctr ALUctr<2:0> ALU Operation 10 0000 add 000 Add 10 0010 subtract 001 Subtract ALU 10 0100 and 010 And 10 0101 or 110 Or 10 1010 set-on-less-than 111 Set-on-less-than ECE4680 Control.20 2003-3-17 

11 . The Truth Table for ALUctr funct<3:0> Instruction Op. 0000 add ALUop R-type ori lw sw beq 0010 subtract (Symbolic) “R-type” Or Add Add Subtract 0100 and ALUop<2:0> 1 00 0 10 0 00 0 00 0 01 0101 or 1010 set-on-less-than ALUop func ALU ALUctr bit<2> bit<1> bit<0> bit<3> bit<2> bit<1> bit<0> Operation bit<2> bit<1> bit<0> 0 0 0 x x x x Add 0 0 0 0 x 1 x x x x Subtract 0 0 1 0 1 x x x x x Or 1 1 0 1 x x 0 0 0 0 Add 0 0 0 1 x x 0 0 1 0 Subtract 0 0 1 1 x x 0 1 0 0 And 0 1 0 1 x x 0 1 0 1 Or 1 1 0 1 x x 1 0 1 0 Set on < 1 1 1 ECE4680 Control.21 2003-3-17 The Logic Equation for ALUctr<0> ALUop func bit<2> bit<1> bit<0> bit<3> bit<2> bit<1> bit<0> ALUctr<0> 0 x 1 x x x x 1 1 x x 0 0 1 0 1 1 x x 1 0 1 0 1 This makes func<3> a don’t care °ALUctr<0> = !ALUop<2> & ALUop<0> + ALUop<2> & !func<2> & func<1> & !func<0> ECE4680 Control.22 2003-3-17 

12 . The Logic Equation for ALUctr<1> ALUop func bit<2> bit<1> bit<0> bit<3> bit<2> bit<1> bit<0> ALUctr<1> 0 1 x x x x x 1 1 x x 0 1 0 0 1 1 x x 0 1 0 1 1 1 x x 1 0 1 0 1 °ALUctr<1> = !ALUop<2> & ALUop<1> + ALUop<2> & !func<3> & func<2> & !func<1> ALUop<2> & func<3> & !func<2> & func<1> & !func<1> ECE4680 Control.23 2003-3-17 The Logic Equation for ALUctr<2> ALUop func bit<2> bit<1> bit<0> bit<3> bit<2> bit<1> bit<0> ALUctr<2> 0 1 x x x x x 1 1 x x 0 1 0 1 1 1 x x 1 0 1 0 1 °ALUctr<2> = !ALUop<2> & ALUop<1> + ALUop<2> & !func<3> & func<2> & !func<1> & func<0> + ALUop<2> & func<3> & !func<2> & func<1> & !func<0> ECE4680 Control.24 2003-3-17 

13 . The ALU Control Block func 6 ALU ALUctr ALUop Control 3 (Local) 3 °ALUctr<0> = !ALUop<2> & ALUop<0> + ALUop<2> & !func<2> & func<1> & !func<0> °ALUctr<1> = !ALUop<2> & ALUop<1> + ALUop<2> & !func<3> & func<2> & !func<1> + ALUop<2> & func<3> & !func<2> & func<1> & !func<1> °ALUctr<2> = !ALUop<2> & ALUop<1> + ALUop<2> & !func<3> & func<2> & !func<1> & func<0> + ALUop<2> & func<3> & !func<2> & func<1> & !func<0> ECE4680 Control.25 2003-3-17 The “Truth Table” for the Main Control RegDst func ALUSrc ALU ALUctr op Main 6 6 Control : Control 3 ALUop (Local) 3 op 00 0000 00 1101 10 0011 10 1011 00 0100 00 0010 R-type ori lw sw beq jump RegDst 1 0 0 x x x ALUSrc 0 1 1 1 0 x MemtoReg 0 0 1 x x x RegWrite 1 1 1 0 0 0 MemWrite 0 0 0 1 0 0 Branch 0 0 0 0 1 0 Jump 0 0 0 0 0 1 ExtOp x 0 1 1 x x ALUop (Symbolic) “R-type” Or Add Add Subtract xxx ALUop <2> 1 0 0 0 0 x ALUop <1> 0 1 0 0 0 x ALUop <0> 0 0 0 0 1 x ECE4680 Control.26 2003-3-17 

14 . The “Truth Table” for RegWrite op 00 0000 00 1101 10 0011 10 1011 00 0100 00 0010 R-type ori lw sw beq jump RegWrite 1 1 1 0 0 0 °RegWrite = R-type + ori + lw = !op<5> & !op<4> & !op<3> & !op<2> & !op<1> & !op<0> (R-type) + !op<5> & !op<4> & op<3> & op<2> & !op<1> & op<0> (ori) + op<5> & !op<4> & !op<3> & !op<2> & op<1> & op<0> (lw) op<5> .. op<5> .. op<5> .. op<5> .. op<5> .. op<5> .. <0> <0> <0> <0> <0> op<0> R-type ori lw sw beq jump RegWrite ECE4680 Control.27 2003-3-17 PLA Implementation of the Main Control op<5> .. op<5> .. op<5> .. op<5> .. op<5> .. .. op<5> <0> <0> <0> <0> <0> op<0> R-type ori lw sw beq jump RegWrite ALUSrc RegDst MemtoReg MemWrite Branch Jump ExtOp ALUop<2> ALUop<1> ALUop<0> ECE4680 Control.28 2003-3-17 

15 . Putting it All Together: A Single Cycle Processor ALUop ALU ALUctr RegDst 3 func Control op Main 3 ALUSrc Instr<5:0> 6 6 Control Instr<31:26> : Branch Instruction<31:0> <21:25> <16:20> <11:15> Instruction <0:15> Jump Fetch Unit Rd Rt RegDst Clk 1 Mux 0 Rs Rt Rt Rs Rd Imm16 RegWr 5 5 5 ALUctr busA Zero MemWr MemtoReg Rw Ra Rb busW 32 ALU 32 32-bit 32 0 Registers busB 0 32 Mux Clk Mux 32 32 WrEn Adr 1 Extender 1 Data In 32 imm16 Data 32 Instr<15:0> 16 Memory Clk ALUSrc ExtOp ECE4680 Control.29 2003-3-17 How is this Different from a Real MIPS Processor? °The effect of load in a real MIPS Processor is delayed: - lw $1, 100 ($2) // Load Register R1 - add $3, $1, $0 // Move “old” R1 into R3 - add $4, $1, $0 // Move “new” R1 into R4 • The effect of load in our single cycle processor is NOT delayed - lw $1, 100 ($2) // Load Register R1 - add $3, $1, $0 // Move “new” R1 into R3 °The effect of branch and jump in a real MIPS Processor is delayed: - Instruction Address: 0x00 j 1000 - Instruction Address: 0x04 add $1, $2, $3 - Instruction Address: 0x1000 sub $1, $2, $3 • Branch and jump in our single cycle processor is NOT delayed - Instruction Address: 0x00 j 1000 - Instruction Address: 0x1000 sub $1, $2, $3 ECE4680 Control.30 2003-3-17 

16 . Worst Case Timing Clk Clk-to-Q PC Old Value New Value Instruction Memory Access Time Rs, Rt, Rd, Old Value New Value Op, Func Delay through Control Logic ALUctr Old Value New Value ExtOp Old Value New Value ALUSrc Old Value New Value MemtoReg Old Value New Value Register Write Occurs RegWr Old Value New Value Register File Access Time busA Old Value New Value Delay through Extender & Mux busB Old Value New Value ALU Delay Address Old Value New Value Data Memory Access Time busW Old Value New ECE4680 Control.31 2003-3-17 Drawback of this Single Cycle Processor °Long cycle time: • Cycle time must be long enough for the load instruction: PC’s Clock -to-Q + Instruction Memory Access Time + Register File Access Time + ALU Delay (address calculation) + Data Memory Access Time + Register File Setup Time + Clock Skew °Cycle time is much longer than needed for all other instructions ECE4680 Control.32 2003-3-17 

17 . Where to get more information? °Chapter 5.1 to 5.3 of your text book: • Daid Patterson and John Hennessy, “Computer Organization & Design: The Hardware / Software Interface,” Morgan Kaufman Publishers, San Mateo, California, 1998. °For a reference on the MIPS architecture: • Gerry Kane, “MIPS RISC Architecture,” Prentice Hall. ECE4680 Control.33 2003-3-17