1CS365 1Multiple Cycle Data PathCS 365 Lecture 7Prof. Yih HuangCS365 2 Break up the instructions into steps, each step takes a cycle– balance the amount of work to be done– restrict each cycle to use only one major functional unit At the end of a cycle– store values for use in later cycles – introduce additional “internal” registersMulticycle Approach2CS365 3Multicycle Datapath and ControlShift left 2PCM u x01RegistersWrite registerWrite dataRead data 1Read data 2Read register 1Read register 2Instruction [15–11]M u x01M u x014Instruction [15–0]Sign extend3216Instruction [25–21]Instruction [20–16]Instruction [15–0]Instruction registerALU controlALU resultALUZeroMemory data register ABIorDMemReadMemWriteMemtoRegPCWriteCondPCWriteIRWriteALUOpALUSrcBALUSrcARegDstPCSourceRegWriteControlOutputsOp [5–0]Instruction [31-26]Instruction [5–0]M u x02Jump address [31-0]Instruction [25–0]26 28Shift left 2PC [31-28]11M u x032M u x01ALUOutMemoryMemDataWrite dataAddressCS365 4Highlights in the New Datapath Instruction and data memory merged. An Instruction Register (IR) is introduced to store the current instruction. A Memory Data Register (MDR) is introduced to store data read from memory. New registers, simply called A and B, store the output of register read port 1 and 2. A new register, ALUout, stores the output of ALU. PC-only adders removed.3CS365 5New Control Signals IorD: Determine the input to the memory address port– 0: PC (for instruction fetches)– 1: ALU output (for data accesses) RegDst: select rt or rd as the destination register Write signals for IR, MDR, A, B, PC, and ALUout.CS365 6 ALUsrcA: determines the first operand to ALU– 0: PC– 1: A ALUsrcB (2 bits): determines the first operand to ALU– 00: B– 01: 4– 10: Sign-extended immediate– 11: shifted immediate4CS365 7 Instruction Fetch Instruction Decode and Register Fetch Execution, Memory Address Computation, or Branch Completion Memory Access or R-type instruction completion Write backINSTRUCTIONS TAKE FROM 3 - 5 CYCLES!Five Execution StepsCS365 8 ActionsIR = Memory[PC];PC = PC + 4;Can we figure out the values of the control signals? Parallel or sequential actions ?Step 1: Instruction Fetch5CS365 9 Read registers rs and rt in case we need them Compute the branch address in case the instruction is a branch ActionsA = Reg[IR[25-21]];B = Reg[IR[20-16]];ALUOut = PC + OffsetStep 2: Instruction Decode and Register FetchCS365 10 ALU is performing one of three functions, based on instruction type Memory Reference:ALUOut = A + sign-extend(IR[15-0]); R-type:ALUOut = A op B; Branch:if (A==B) PC = ALUOut;Step 3: instruction dependent6CS365 11MDR = Memory[ALUOut]; (lw)orMemory[ALUOut] = B; (sw)orReg[IR[15-11]] = ALUOut; (R type)Step 4: R-type or memory-accessReg[IR[20-16]]= MDR;Step5: Write-backCS365 12SummaryStep nameAction for R-type instructionsAction for memory-reference instructionsAction for branchesAction for jumpsInstruction fetch IR = Memory[PC]PC = PC + 4Instruction A = Reg [IR[25-21]]decode/register fetch B = Reg [IR[20-16]]ALUOut = PC + (sign-extend (IR[15-0]) << 2)Execution, address ALUOut = A op B ALUOut = A + sign-extend if (A ==B) then PC = PC [31-28] IIcomputation, branch/ (IR[15-0]) PC = ALUOut (IR[25-0]<<2)jump completionMemory access or R-type Reg [IR[15-11]] = Load: MDR = Memory[ALUOut]completion ALUOut orStore: Memory [ALUOut] = BMemory read completionLoad: Reg[IR[20-16]] = MDR7CS365 13Control Signals for ADD Sub, and, or, slt are similar ALUOpRegWriteMemReadMemWriteMem2RegIRWriteMDRWrAWriteBWriteALUoutWrIorDALUsrcAALUsrcBPCWriteRegDstPCsrcCS365 14Control Signals for LWALUOpRegWriteMemReadMemWriteMem2RegIRWriteMDRWrAWriteBWriteALUoutWrIorDALUsrcAALUsrcBPCWriteRegDstPCsrc8CS365 15Control Signals for SWALUOpRegWriteMemReadMemWriteMem2RegIRWriteMDRWrAWriteBWriteALUoutWrIorDALUsrcAALUsrcBPCWriteRegDstPCsrcCS365 16ALUOpRegWriteMemReadMemWriteMem2RegIRWriteMDRWrAWriteBWriteALUoutWrIorDALUsrcAALUsrcBPCWriteRegDstPCsrc9CS365 17Control Signals for BEQALUOpRegWriteMemReadMemWriteMem2RegIRWriteMDRWrAWriteBWriteALUoutWrIorDALUsrcAALUsrcBPCWriteRegDstPCsrcCS365 18 Finite state machines:– a set of states and – next state function (determined by current state and the input)– output function (determined by current state and possibly input)Review: finite state machines10CS365 19FSM ImplementationState RegisterNext State Function(Combinational Circuit)OutputFunction(Combinational Circuit)InputOutputCS365 20Review: finite state machines Example: A fake security device consists of three lights lined up in a row, controlled by the outputs Left, Middle, and Right, which, if asserted, indicate that a light should be on. Only one light is on at a time, and the light “moves” from left to right and then from right to left, thus scaring away thieves who believe that the device is monitoring their activity. The rate of the eye’s movement is controlled by the clock speed (which should not be too great) and that there are essentially no inputs.11CS365 21Solution State Transition diagram Next/output functions ImplementationCS365 22FSM-based Control Unit 3-bit state register keeps track of the current instruction step. FSM Inputs: – opcode (IR[31:26]), – funct (IR[5:0]), – Zero (that is rs==rt) Outputs: all control signals12CS365 23State Transition Diagram1 2 3 4 5CS365 24FSM ControlNext State FunctionOutputFunctionALUopS0S1S2opcodefunctzero66NS0NS1NS23ALUsrcA2ALUsrcB2IR-Write13CS365 25The Output