
Complete Datapath and Single-Cycle MIPS CPU Overview
Dive into the world of MIPS architecture by exploring the datapath, control components, instruction formats, and types of instructions. Learn how to create a full single-cycle MIPS CPU following Montek Singh's teachings and relevant course materials.
Download Presentation

Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
COMP541 Datapath & Single-Cycle MIPS Montek Singh Mar {5, 7}, 2018 1
Topics Complete the datapath Add control to it Create a full single-cycle MIPS! Reading Chapter 7 Review MIPS assembly language Chapter 6 of course textbook Or, Patterson Hennessy (inside front flap)
A MIPS CPU reset clk clk memwrite dataaddr writedata pc Instr Memory Data Memory MIPS CPU instr readdata 3
Top-Level: MIPS CPU + memories reset clk Top-level module reset clk clk memwrite dataaddr writedata pc Instr Memory Data Memory MIPS CPU instr readdata We will add I/O devices (display, keyboard, etc.) later 4
One level down: Inside MIPS Datapath: components that store or process data registers, ALU, multiplexors, sign-extension, etc. we will regard memories as outside the CPU, so not part of the core datapath Control: components that tell datapath what to do and when control logic (FSMs or combinational look-up tables) MIPS CPU clk Control reset memwrite opcode, func, flagZ ALUFN, regwrite, regdst clk pc dataadr writedata Instr Memory MIPS Datapath Data Memory instr readdata
Review: MIPS instruction types Three instruction formats: R-Type: register operands I-Type: immediate operand J-Type: for jumps 6
Review: Instruction Formats R-Type op 6 bits rs rt rd shamt funct 5 bits 5 bits 5 bits 6 bits 5 bits I-Type rs rt imm op 6 bits 5 bits 5 bits 16 bits J-Type op 6 bits addr 26 bits
R-Type instructions Register-type 3 register operands: rs, rt: source registers rd: destination register Other fields: op: the operation code or opcode (0 for R-type instructions) funct: the function together, op and funct tell the computer which operation to perform shamt: the shift amount for shift instructions, otherwise it is 0 R-Type op 6 bits rs rt rd shamt funct 5 bits 5 bits 5 bits 6 bits 5 bits
R-Type Examples Field Values rt Assembly Code rs op rd shamt funct 0 17 18 16 0 32 add $s0, $s1, $s2 0 11 13 8 0 34 sub $t0, $t3, $t5 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits Note the order of registers in the assembly code: add rd, rs, rt Machine Code rs rt op rd shamt funct 000000 10001 10010 10000 00000 100000 (0x02328020) 000000 01011 01101 01000 00000 100010 (0x016D4022) 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
I-Type instructions Immediate-type 3 operands: op: the opcode rs, rt: register operands imm: 16-bit two s complement immediate I-Type rs rt imm op 6 bits 5 bits 5 bits 16 bits
I-Type Examples Assembly Code Field Values rt rs op imm 8 17 16 5 addi $s0, $s1, 5 8 19 8 -12 addi $t0, $s3, -12 35 0 10 32 lw $t2, 32($0) 43 9 17 4 sw $s1, 4($t1) 6 bits 5 bits 5 bits 16 bits Machine Code Note the differing order of registers in the assembly and machine codes: rs rt op imm 001000 10001 10000 0000 0000 0000 0101 (0x22300005) (0x2268FFF4) 001000 10011 01000 1111 1111 1111 0100 addi rt, rs, imm (0x8C0A0020) 100011 00000 01010 0000 0000 0010 0000 lw rt, imm(rs) (0xAD310004) 101011 01001 10001 0000 0000 0000 0100 sw rt, imm(rs) 6 bits 5 bits 5 bits 16 bits
J-Type instructions Jump-type 26-bit address operand (addr) Used for jump instructions (j) J-Type op 6 bits addr 26 bits
Summary: Instruction Formats R-Type op 6 bits rs rt rd shamt funct 5 bits 5 bits 5 bits 6 bits 5 bits I-Type rs rt imm op 6 bits 5 bits 5 bits 16 bits J-Type op 6 bits addr 26 bits
MIPS Design from Comp411 We will not be implementing the textbook version of MIPS in our labs. Instead, we will implement the MIPS design from Comp411, which has more features. 14
Design Approach Incremental Featurism We will implement circuits for each type of instruction individually, and merge them (using MUXes, etc). Our Bag of Components: Steps: 1. 3-Operand ALU instrs 2. ALU w/immediate instrs 2. Loads & Stores 3. Jumps & Branches 4. Exceptions (briefly) Registers Muxes 1 0 + ALU & adders A B ALU RA1 RA2 WA WD Register File (3-port) A Instruction Memory Data Memory A WE D RD WD R/W RD1 RD2 Memories
Review: The MIPS ISA OP 6 The MIPS instruction set as seen from a Hardware Perspective 5 5 5 5 6 16 26 rs rt rd shamt func 000000 R-type: ALU with Register operands Reg[rd] Reg[rs] op Reg[rt] rs rt ALU with constant operand Reg[rt] Reg[rs] op SEXT(immediate) rs rt Load and Store Reg[rt] Mem[Reg[rs] + SEXT(immediate)] Mem[Reg[rs] + SEXT(immediate)] Reg[rt] rs rt immediate 001XXX I-type: Instruction classes distinguished by types: 1) 3-operand ALU 2) ALU w/immediate 3) Loads/Stores 4) Branches 5) Jumps immediate 10X011 I-type: immediate 10X011 I-type: Branch Instructions if (Reg[rs] == Reg[rt]) PC PC + 4 + 4*SEXT(immediate) if (Reg[rs] != Reg[rt]) PC PC + 4 + 4*SEXT(immediate) 26-bit constant 00001X J-type: jump PC (PC & 0xf0000000) | 4*(immediate)
Fetching Sequential Instructions 32 + 4 Read Address 32 32 P C Instruction 32 register Instruction Memory We will talk about branches and jumps later.
Instruction Fetch/Decode Use a counter to FETCH the next instruction: PROGRAM COUNTER (PC) use PC as memory address add 4 to PC, load new value at end of cycle fetch instruction from memory use some instruction fields directly (register numbers, 16-bit constant) decode rest of the instruction use bits <31:26> and <5:0> to generate controls PC 00 A Instruction Memory D 32 +4 32 32 INSTRUCTION WORD FIELDS OP[31:26], FUNC[5:0] Control Logic CONTROL SIGNALS
3-Operand ALU Data Path rs rt rd 00000 100XXX 000000 R-type: ALU with Register operands Reg[rd] Reg[rs] op Reg[rt] 00 PC Instruction Memory A D +4 Rs: <25:21> Rt: <20:16> Register File RA1 RA2 Rd: <15:11> WD WA WERF RD1 RD2 WE 32 32 Control Logic A B ALU ALUFN ALUFN WERF! WERF 32
Shift Instructions rs rt rd shamt 000XXX 000000 R-type: ALU with Register operands sll: Reg[rd] Reg[rt] (shift) shamt sllv: Reg[rd] Reg[rt] (shift) Reg[rs] 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> Register File RA1 RA2 Rd: <15:11> WD WA WERF RD1 RD2 WE shamt:<10:6> Control Logic ASEL 0 1 A B ALU ALUFN ASEL! ALUFN WERF ASEL 32
ALU with Immediate rs rt immediate 001XXX I-type: ALU with constant operand Reg[rt] Reg[rs] op SEXT(immediate) 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> BSEL Rd:<15:11> RA1 RA2 Register File 0 1 WD WA WA Rt:<20:16> WERF RD1 RD2 WE imm: <15:0> SEXT SEXT BSEL shamt:<10:6> 1 0 Control Logic ASEL 0 1 How do you build SEXT? 1 pad with sign 0 pad with 0s SEXT A B ALU ALUFN BSEL! BSEL ALUFN WERF ASEL
Load Instruction rs rt 100011 immediate I-type: Load Reg[rt] Mem[Reg[rs] + SEXT(immediate)] 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> BSEL Rd:<15:11> RA1 RA2 Register File 0 1 WD WA WA Rt:<20:16> WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT shamt:<10:6> Control Logic ASEL BSEL 0 1 1 0 SEXT A B ALU Wr WD BSEL WDSEL ALUFN Wr R/W ALUFN Data Memory Adr RD 32 WERF ASEL 32 0 1 2 WDSEL
Store Instruction rs rt immediate 101011 I-type: Store Mem[Reg[rs] + SEXT(immediate)] Reg[rt] 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> BSEL Rd:<15:11> RA1 RA2 Register File 0 1 WD WA WA Rt:<20:16> WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT shamt:<10:6> Control Logic ASEL BSEL 0 1 1 0 32 No WERF! A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WD ALUFN R/W Data Memory Adr RD WERF ASEL 0 1 2 WDSEL
JMP Instructions PC<31:28>:J<25:0>:00 26-bit constant 00001X J-type: j: PC (PC & 0xf0000000) | 4*(immediate) jal: PC (PC & 0xf0000000) | 4*(immediate); Reg[31] PC + 4 PCSEL 3 2 1 0 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT shamt:<10:6> Control Logic ASEL BSEL 0 1 1 0 PCSEL WASEL A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WD ALUFN R/W Data Memory Adr RD WERF ASEL PC+4 32 0 1 2 WDSEL
BEQ/BNE Instructions PC<31:28>:J<25:0>:00 rs rt BT 00010X R-type: immediate PCSEL 3 2 1 0 Branch Instructions if (Reg[rs] == Reg[rt]) PC PC + 4 + 4*SEXT(immediate) if (Reg[rs] != Reg[rt]) PC PC + 4 + 4*SEXT(immediate) 00 PC Instruction Memory A That x4 unit is trivial. I ll just wire the input shifted over 2 bit positions. D +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT Z x4 shamt:<10:6> + Why add, another adder? Couldn t we reuse the one in the ALU? Nope, it needs to do a subtraction. Control Logic ASEL BSEL 0 1 1 0 PCSEL WASEL BT A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WD ALUFN R/W Data Memory Z Adr RD WERF ASEL PC+4 32 0 1 2 WDSEL
Jump Indirect Instructions PC<31:28>:J<25:0>:00 rs rt rd BT JT 00100X 00000 000000 PCSEL 3 2 1 0 R-type: Jump Indirect, Jump and Link Indirect jr: PC Reg[rs] jalr: PC Reg[rs], Reg[rd] PC + 4 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT JT Z x4 shamt:<10:6> + Control Logic ASEL BSEL 0 1 1 0 PCSEL WASEL BT A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WD ALUFN R/W Data Memory Z Adr RD WERF ASEL PC+4 32 0 1 2 WDSEL
Comparisons rs rt 00101X immediate PC<31:28>:J<25:0>:00 BT JT I-type: set on less than & set on less than unsigned immediate slti: if (Reg[rs] < SEXT(imm)) Reg[rt] 1; else Reg[rt] 0 sltiu: if (Reg[rs] < SEXT(imm)) Reg[rt] 1; else Reg[rt] 0 PCSEL 3 2 1 0 00 PC Instruction Memory A NOTE: Sign-extension done for both! WHY?? But ALUFN is unsigned comparison (LTU) for sltiu. D +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> JT SEXT SEXT Z x4 shamt:<10:6> + Control Logic ASEL BSEL 0 1 1 0 PCSEL WASEL BT A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WD ALUFN R/W Data Memory Z Adr RD WERF ASEL PC+4 32 0 1 2 WDSEL
More comparisons rs rt rd 10101X 00000 000000 PC<31:28>:J<25:0>:00 BT JT R-type: set on less than & set on less than unsigned slt: if (Reg[rs] < Reg[rt]) Reg[rd] 1; else Reg[rd] 0 sltu: if (Reg[rs] < Reg[rt]) Reg[rd] 1; else Reg[rd] 0 PCSEL 3 2 1 0 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT JT Z x4 shamt:<10:6> + Control Logic ASEL BSEL 0 1 1 0 PCSEL WASEL BT A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WD ALUFN R/W Data Memory Z Adr RD WERF ASEL PC+4 32 0 1 2 WDSEL
LUI rt 00000 001111 PC<31:28>:J<25:0>:00 immediate BT JT I-type: Load upper immediate lui: Reg[rt] Immediate << 16 PCSEL 3 2 1 0 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT JT Z x4 shamt:<10:6> + Control Logic 16 ASEL BSEL 0 1 2 1 0 PCSEL WASEL BT A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WERF ASEL WD ALUFN R/W Data Memory Z Adr RD PC+4 32 0 1 2 WDSEL
All put together PC<31:28>:J<25:0>:00 BT JT PCSEL 3 2 1 0 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT JT Z x4 shamt:<10:6> + Control Logic 16 ASEL BSEL 0 1 2 1 0 PCSEL WASEL BT A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WERF ASEL WD ALUFN R/W Data Memory Z Adr RD PC+4 32 0 1 2 WDSEL
Reset, Interrupts, and Exceptions Upon reset/reboot: Need to set PC to where boot code resides in memory Interrupts/Exceptions: any event that causes interruption in program flow FAULTS: e.g., nonexistent opcode, divide-by-zero TRAPS & system calls: e.g., read-a-character I/O events: e.g., key pressed How to handle? interrupt current running program invoke exception handler return to program to continue execution Registers $k0, $k1 ($26, $27) reserved for operating system (kernel), interrupt handlers any others used must be saved/restored
Exceptions 0x80000000 Reset: PC 0x80000000 PC<31:28>:J<25:0>:00 0x80000040 BT JT 0x80000080 Bad Opcode: Reg[27] PC+4; PC 0x80000040 PCSEL 6 5 4 3 2 1 0 IRQ: Reg[27] PC+4; PC 0x80000080 00 PC Instruction Memory A D +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 3 WD WA WA 31 27 WERF RD1 RD2 WE Imm: <15:0> RESET SEXT SEXT JT Z IRQ x4 shamt:<10:6> + Control Logic 16 ASEL BSEL 0 1 2 1 0 PCSEL WASEL BT A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WERF ASEL WD ALUFN R/W Data Memory Z Adr RD PC+4 32 0 1 2 WDSEL
Our Lab version: three changes 1. No support for exceptions 2. Supports Reset: PC starts over at 0x0040_0000 address chosen for compatibility with MARS assembler 3. Supports Enable: Freezes when Enable = 0 will allow us to single-step through execution debugging aid 33
Support for Reset Reset input: starts PC over at 0x0040_0000 address chosen for compatibility with MARS assembler PC<31:28>:J<25:0>:00 JT BT On Reset: PC 0x0040_0000 PCSEL 3 2 1 0 00 PC Instruction Memory A RESET D +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT JT Z x4 shamt:<10:6> + Control Logic 16 ASEL BSEL 0 1 2 1 0 PCSEL WASEL BT A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WERF ASEL WD ALUFN R/W Data Memory Z Adr RD PC+4 32 0 1 2 WDSEL
Support for Enable Enable input: Enable = 0 disables the processor disables writes to: PC, register file and data memory PC<31:28>:J<25:0>:00 JT BT On Reset: PC 0x0040_0000 PCSEL 3 2 1 0 00 PC Instruction Memory A ENABLE RESET D Writes disabled by controller +4 Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> RA1 RA2 Register File 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT JT Z x4 shamt:<10:6> + Control Logic 16 ASEL BSEL 0 1 2 1 0 PCSEL WASEL BT A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WERF ASEL WD ALUFN R/W Data Memory Z Adr RD PC+4 32 0 1 2 WDSEL
MIPS: Our Final Version This is a complete 32-bit processor. Although designed in one class lecture, it executes the majority of the MIPS R2000 instruction set. PC<31:28>:J<25:0>:00 BT JT PCSEL 3 2 1 0 00 PC Instruction Memory A ENABLE RESET D +4 Executes one instruction per clock Rt: <20:16> Rs: <25:21> WASEL J:<25:0> Rd:<15:11> Rt:<20:16> Register File RA1 RA2 0 1 2 WD WA WA 31 WERF RD1 RD2 WE Imm: <15:0> SEXT SEXT JT Z x4 shamt:<10:6> + Control Logic 16 ASEL BSEL 0 1 2 1 0 PCSEL BT WASEL A B SEXT ALU Wr BSEL WDSEL ALUFN Wr WERF ASEL WD ALUFN R/W Data Memory Z Adr RD PC+4 32 0 1 2 WDSEL
Our MIPS: Top-level hierarchy PC<31:28>:J<25:0>:00 BT JT PCSEL 3 2 1 0 newPC pcPlus4 00 PC MIPS CPU Instruction Memory ENABLE A pc pc[31:0] RESET Datapath D +4 instr Rt: instr<20:16> Rs: instr<25:21> reg_writeaddr WASEL J: instr<25:0> Rd: instr<15:11> Rt: instr<20:16> RA1 RA2 Register File 0 1 2 reg_writedata WD WA WA 31 WERF RD1 ReadData1 RD2 ReadData2 WE Imm: instr<15:0> ENABLE op: instr<31:26> func: instr<5:0> Z SEXT SEXT JT signImm <<2 shamt: instr<10:6> + Control Logic 16 ASEL BSEL 0 1 2 1 0 mem_writedata PCSEL WASEL BT aluB aluA A B SEXT ALU mem_wr BSEL WDSEL ALUFN Wr WERF ASEL WD ALUFN R/W Wr Data Memory mem_addr Z Adr RD alu_result mem_readdata (PC+4) pcPlus4 32 0 1 2 WDSEL
Make design modular Follow hierachy specified Small amounts of logic can be inlined (instead of separate module) e.g.: muxes, sign extension, adders, shift-by-2 38
Summary We learned about a complete MIPS CPU NOTE: Many details in textbook are different from what you will implement in the lab our lab MIPS has more features