14:332:331Computer Architecture and Assembly LanguageSpring 2006Week 10Building a Multi-Cycle DatapathHead’s UpReview: Single Cycle Data and Control PathDisadvantages of the Single Cycle DatapathMulticycle Implementation OverviewThe Multicycle Datapath – A High Level ViewClocking the Multicycle DatapathMulticycle ApproachThe Complete Multicycle Data with ControlMulticycle Approach, con’tFive Instruction StepsStep 1: Instruction FetchFetch Control Signals SettingsStep 2: Instruction Decode and Register FetchDatapath Activity During Instruction DecodeDecode Control Signals SettingsStep 3 (instruction dependent)Datapath Activity During Instruction ExecuteExecute Control Signals SettingsStep 4 (instruction dependent)Datapath Activity During Memory AccessMemory Access Control Signals SettingsStep 5: Memory Read Completion (Write Back)Datapath Activity During Write BackWrite Back Control Signals SettingsRTL SummarySimple QuestionsMulticycle ControlFinite State Machine ImplementationDatapath Control Outputs Truth TableNext State Truth Table331 W10.1 Spring 200614:332:331Computer Architecture and Assembly LanguageSpring 2006Week 10Building a Multi-Cycle Datapath[Adapted from Dave Patterson’s UCB CS152 slides andMary Jane Irwin’s PSU CSE331 slides]331 W10.2 Spring 2006Head’s Up This week’s materialz Multicycle MIPS datapath implementation- Reading assignment – PH 5.5 and C.3331 W10.3 Spring 2006Review: Single Cycle Data and Control Path ReadAddressInstr[31-0]InstructionMemoryAddPC4Write DataRead Addr 1Read Addr 2Write AddrRegisterFileReadData 1ReadData 2ALUovfzeroRegWriteDataMemoryAddressWrite DataRead DataMemWriteMemReadSignExtend16 32MemtoRegALUSrcShiftleft 2AddPCSrcRegDstALUcontrol11100001ALUOpInstr[5-0]Instr[15-0]Instr[25-21]Instr[20-16]Instr[15 -11]ControlInstr[31-26]BranchShiftleft 201Jump28Instr[25-0]26PC+4[31-28]32331 W10.4 Spring 2006Disadvantages of the Single Cycle Datapath Uses the clock cycle inefficiently – the clock cycle must be timed to accommodate the slowestinstructionz especially problematic for more complex instructions like floating point multiply Is wasteful of area since some functional units must be duplicated since they can not be “shared” during an instruction executionz e.g., need separate adders to do PC update and branch target address calculations, as well as an ALU to do R-type arithmetic/logic operations and data memory address calculations331 W10.5 Spring 2006Multicycle Implementation Overview Each step in the execution takes 1 clock cycle An instruction takes more than 1 clock cycle to complete Not every instruction takes the same number of clock cycles to complete Multicycle implementations allowz functional units to be used more than once per instruction as long as they are used on different clock cycles, as a result- only need one memory- need only one ALU/adderz faster clock ratesz different instructions to take a different number of clock cycles331 W10.6 Spring 2006The Multicycle Datapath – A High Level View Registers have to be added after every major functional unit to hold the output value until it is used in a subsequent clock cycleAddressRead Data(Instr. or Data)MemoryPCWrite DataRead Addr 1Read Addr 2Write AddrRegisterFileReadData 1ReadData 2ALUWrite DataIRMDRABALUout331 W10.7 Spring 2006Clocking the Multicycle DatapathAddressRead Data(Instr. or Data)MemoryPCWrite DataRead Addr 1Read Addr 2Write AddrRegisterFileReadData 1ReadData 2ALUWrite DataIRMDRABALUoutSystem ClockMemWrite RegWriteclock cycle331 W10.8 Spring 2006 Break up the instructions into steps where each step takes a cycle while trying toz balance the amount of work to be done in each stepz restrict each cycle to use only one major functional unit At the end of a cyclez Store values needed in a later cycle by the currentinstruction in a state element (internal register) not visible to the programmerIR – Instruction RegisterMDR – Memory Data RegisterA and B – register file read data registersALUout – ALU output registerz All (except IR) hold data only between a pair of adjacent clock cycles (so don’t need a write control signal)z Data used by subsequent instructions are stored in programmer visible state elements (i.e., register file, PC, or memory)Multicycle Approach331 W10.9 Spring 2006The Complete Multicycle Data with ControlAddressRead Data(Instr. or Data)MemoryPCWrite DataRead Addr 1Read Addr 2Write AddrRegisterFileReadData 1ReadData 2ALUWrite DataIRMDRABALUoutSignExtendShiftleft 2ALUcontrolShiftleft 2ALUOpControlIRWriteMemtoRegMemWriteMemReadIorDPCWritePCWriteCondRegDstRegWriteALUSrcAALUSrcBzeroPCSource1111110000002234Instr[5-0]Instr[25-0]PC[31-28]Instr[15-0]Instr[31-26]3228331 W10.10 Spring 2006 Reading/writing toz any of the internal registers or the PC occurs (quickly) at the end of a clock cyclez reading/writing to the register file takes ~50% of a clock cycle since it has additional control and access overhead (reading can be done in parallel with decode) Have to add multiplexors in front of several of the functional unit inputs because the functional units are shared by different instruction cycles All operations occurring in one step occur in parallel within the same clock cyclez This limits us to one ALU operation, one memory access, and one register file access per step (per clock cycle)Multicycle Approach, con’t331 W10.11 Spring 2006 Instruction Fetch Instruction Decode and Register Fetch R-type Instruction Execution, Memory Read/Write Address Computation, Branch Completion, or Jump Completion Memory Read Access, Memory Write Completion or R-type Instruction Completion Memory Read Completion (Write Back)INSTRUCTIONS TAKE FROM 3 - 5 CYCLES!Five Instruction Steps331 W10.12 Spring 2006Step 1: Instruction Fetch Use PC to get instruction from the memory and put it in the Instruction Register Increment the PC by 4 and put the result back in the PC Can be described succinctly using RTL "Register-Transfer Language“IR = Memory[PC];PC = PC + 4;Can we figure out the values of the control signals?What is the advantage of updating the PC now?331 W10.13 Spring 2006Fetch Control Signals SettingsStartInstr Fetch331 W10.14 Spring 2006 Don’t know what the instruction is yet, so can onlyz Read registers rs and rt in case we need themz Compute the branch address in case the instruction is a branch RTL:A = Reg[IR[25-21]];B = Reg[IR[20-16]];ALUOut = PC