CS/COE0447 Computer Organization & Assembly LanguageA Multi-cycle DatapathMulti-Cycle Control What we need to coverExecution: single-cycle (reminder)Slide 5Execution: single-cycle (reminder)Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Multicycle ApproachOperationsFive Execution StepsStep 1: Instruction FetchStep 2: Decode and Reg. ReadStep 3: Various ActionsStep 4: Memory Access…Step 5: Register Write BackMulticycle Execution Step (1): Instruction FetchMulticycle Execution Step (2): Instruction Decode & Register FetchMulticycle Execution Step (3): Memory Reference InstructionsMulticycle Execution Step (4): Memory Access - Write (sw)Multicycle Execution Step (4): Memory Access - Read (lw)Multicycle Execution Step (5): Memory Read Completion (lw)Multicycle Execution Step (3): ALU Instruction (R-Type)Multicycle Execution Step (4): ALU Instruction (R-Type)Multicycle Execution Step (3): Branch InstructionsMulticycle Execution Step (3): Jump InstructionFor ReferenceMulti-Cycle Execution: R-typeMulti-cycle Execution: lwMulti-cycle Execution: swMulti-cycle execution: beqMulti-cycle execution: jSlide 39Datapath w/ Control SignalsFinal Version w/ ControlExample from beginning to endSlide 43Example: Load (1)Example: Load (2)Example: Load (3)Example: Load (4)Example: Load (5)Example: Jump (1)Example: Jump (2)Example: Jump (3)A FSM State DiagramMulticycle 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 58Multicycle 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 63For referenceSlide 65State Diagram, Big PictureHandling Memory InstructionsR-type InstructionBranch and JumpFSM ImplementationTo Summarize…Slide 72Slide 73Slide 74Summary1CS/COE0447Computer Organization & Assembly LanguageMulti-Cycle Execution2A 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 cycle3Multi-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 together4Execution: 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  $t25A 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 ALUOut6Execution: 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 $t07A 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)8Execution: 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]9A 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 ALUOut10Execution: single-cycle (reminder)•beq–Fetch instruction and add 4 to PC beq $t0,$t1,L•Assume that L is +4 instructions away–Read two source registers $t0,$t1–Sign Extend the immediate, and shift it left by 2 •0x0003  0x0000000c–Perform the test, and update the PC if it is true •If $t0 == $t1, the PC = PC + 0x0000000c11A Multi-cycle Datapath•For beq beq $t0,$t1,label•Instruction stored in IR•Registers rs and rt are stored in A and B•Result of ALU (rs – rt) is stored in ALUOut12Execution: single-cycle (reminder)•j–Fetch instruction and add 4 to PC–Take the 26-bit immediate field–Shift left by 2 (to make 28-bit immediate)–Get 4 bits from the current PC and attach to the left of the immediate–Assign the value to PC13A Multi-cycle Datapath•For j•No accesses to registers or memory; no need for ALU14Multi-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 together15•Break up the instructions into steps–each step takes one clock cycle–balance the amount of work to be done in each step/cycle so that they are about equal–restrict each cycle to use at most once each major functional unit so that such units do not have to be replicated–functional units can be shared between different cycles within one instructionMulticycle ApproachOperations•These take time:•Memory (read/write); register file (read/write); ALU operations•The other connections and logical elements have no latency (for our purposes)17Five Execution Steps•Each takes one cycle•In one cycle, there can be at most one memory access, at