CS/COE0447 Computer Organization & Assembly LanguageSingle-cycle Implementation of MIPSA Multi-cycle DatapathMulti-Cycle Control What we need to coverExecution: single-cycle (reminder)Slide 6Multi-Cycle Execution: R-typeExecution: single-cycle (reminder)Slide 9Multi-cycle Execution: lwSlide 11Slide 12Multi-cycle Execution: swSlide 14Slide 15Multi-cycle execution: beqSlide 17Slide 18Multi-cycle execution: jSlide 20Multicycle ApproachOperationsSlide 23Five Execution StepsStep 1: Instruction FetchStep 2: Decode and Reg. ReadStep 3: Various ActionsStep 4: Memory Access…Step 5: Register Write BackSummary of Instruction ExecutionMulticycle Execution Step (1): Instruction FetchMulticycle Execution Step (2): Instruction Decode & Register FetchMulticycle Execution Step (3): Memory Reference InstructionsMulticycle Execution Step (3): ALU Instruction (R-Type)Multicycle Execution Step (3): Branch InstructionsMulticycle Execution Step (3): Jump InstructionMulticycle Execution Step (4): Memory Access - Read (lw)Multicycle Execution Step (4): Memory Access - Write (sw)Multicycle Execution Step (4): ALU Instruction (R-Type)Multicycle Execution Step (5): Memory Read Completion (lw)For ReferenceSlide 42Slide 43Slide 44Slide 45Slide 46Example: CPI in a multicycle CPUSlide 48A (Refined) Datapath fig 5.26Datapath w/ Control Signals Fig 5.27Final Version w/ Control Fig 5.28Multicycle Control Step (1): FetchMulticycle Control Step (2): Instruction Decode & Register FetchMulticycle Control Step (3): Memory Reference InstructionsMulticycle Control Step (3): ALU Instruction (R-Type)Multicycle Control Step (3): Branch InstructionsSlide 57Multicycle Control Step (4): Memory Access - Read (lw)Multicycle Execution Steps (4) Memory Access - Write (sw)Multicycle Control Step (4): ALU Instruction (R-Type)Multicycle Execution Steps (5) Memory Read Completion (lw)Slide 62Fig 5.28 For referenceState Diagram, Big PictureHandling Memory InstructionsR-type InstructionBranch and JumpA FSM State DiagramFSM ImplementationExample: Load (1)Example: Load (2)Example: Load (3)Example: Load (4)Example: Load (5)Example: Jump (1)Example: Jump (2)Example: Jump (3)To Summarize…Slide 79Slide 80Slide 81Summary1CS/COE0447Computer Organization & Assembly LanguageChapter 5 Part 32Single-cycle Implementation of MIPS•Our first implementation of MIPS used a single long clock cycle for every instruction•Every instruction began on one up (or, down) clock edge and ended on the next up (or, down) clock edge•This approach is not practical as it is much slower than a multicycle implementation where different instruction classes can take different numbers of cycles–in a single-cycle implementation every instruction must take the same amount of time as the slowest instruction–in a multicycle implementation this problem is avoided by allowing quicker instructions to use fewer cycles•Even though the single-cycle approach is not practical it was simpler and useful to understand first•Now we are covering a multicycle implementation of MIPS3A Multi-cycle Datapath•A single memory unit for both instructions and data•Single ALU rather than ALU & two adders•Registers added after every major functional unit to hold the output until it is used in a subsequent clock cycle4Multi-Cycle ControlWhat we need to cover•Adding registers after every functional unit–Need to modify the “instruction execution” slides to reflect this•Breaking instruction execution down into cycles–What can be done during the same cycle? What requires a cycle? –Need to modify the “instruction execution” slides again–Timing•Control signal values –What they are per cycle, per instruction–Finite state machine which determines signals based on instruction type + which cycle it is•Putting it all together5Execution: single-cycle (reminder)•add–Fetch instruction and add 4 to PC add $t2,$t1,$t0–Read two source registers $t1 and $t0–Add two values $t1 + $t0–Store result to the destination register $t1 + $t0  $t26A Multi-cycle Datapath•For add:•Instruction is stored in the instruction register (IR)•Values read from rs and rt are stored in A and B •Result of ALU is stored in ALUOut7Multi-Cycle Execution: R-type•Instruction fetch–IR <= Memory[PC]; sub $t0,$t1,$t2–PC <= PC + 4;•Decode instruction/register read–A <= Reg[IR[25:21]]; rs–B <= Reg[IR[20:16]]; rt–ALUOut <= PC + (sign-extend(IR[15:0])<<2);  later•Execution–ALUOut <= A op B; op = add, sub, and, or,…•Completion–Reg[IR[15:11]] <= ALUOut; $t0 <= ALU result8Execution: single-cycle (reminder)•lw (load word) –Fetch instruction and add 4 to PC lw $t0,-12($t1)–Read the base register $t1–Sign-extend the immediate offset fff4  fffffff4–Add two values to get address X = fffffff4 + $t1–Access data memory with the computed address M[X]–Store the memory data to the destination register $t09A Multi-cycle Datapath•For lw: lw $t0, -12($t1)•Instruction is stored in the IR•Contents of rs stored in A $t1•Output of ALU (address of memory location to be read) stored in ALUOut•Value read from memory is stored in the memory data register (MDR)10Multi-cycle Execution: lw•Instruction fetch–IR <= Memory[PC]; lw $t0,-12($t1)–PC <= PC + 4;•Instruction Decode/register read–A <= Reg[IR[25:21]]; rs–B <= Reg[IR[20:16]];–ALUOut <= PC + (sign-extend(IR[15:0])<<2);•Execution–ALUOut <= A + sign-extend(IR[15:0]); $t1 + -12 (sign extended) •Memory Access–MDR <= Memory[ALUOut]; M[$t1 + -12]•Write-back–Load: Reg[IR[20:16]] <= MDR; $t0 <= M[$t1 + -12]11Execution: single-cycle (reminder)•sw –Fetch instruction and add 4 to PC sw $t0,-4($t1)–Read the base register $t1–Read the source register $t0–Sign-extend the immediate offset fffc  fffffffc–Add two values to get address X = fffffffc + $t1–Store the contents of the source register to the computed address $t0  Memory[X]12A Multi-cycle Datapath•For sw: sw $t0, -12($t1)•Instruction is stored in the IR•Contents of rs stored in A $t1•Output of ALU (address of memory location to be written) stored in ALUOut13Multi-cycle Execution: sw•Instruction fetch–IR <= Memory[PC]; sw $t0,-12($t1)–PC <= PC + 4;•Decode/register read–A <= Reg[IR[25:21]]; rs–B <= Reg[IR[20:16]]; rt–ALUOut <= PC + (sign-extend(IR[15:0])<<2);•Execution–ALUOut <= A + sign-extend(IR[15:0]); $t1 + -12 (sign extended) •Memory