1Computer System DesignLecture 11: Multicycle OperationsProf. R. Iris BaharEN164February 21, 2007Reading: Appendix A, sections A.4, A.5 EN164Lecture 10-2Exceptions• Sometimes, instruction order execution is changed in unexpected ways, due to:–I/O device request– Integer arithmetic overflow– Page fault (data not in main memory)– Memory access error– Power failure• Some of these exceptions can occur within instructions and may also require that the program be restartable(e.g. memory page fault)–What does this imply for the pipeline hardware?EN164Lecture 10-3Precise Exceptions• On an exception:–Must save PC of instruction where program must resume– All instructions after that PC that might be in the pipeline must be converted to NOPs– Temporary program state not in memory (i.e., registers) has to be stored in memory– Potential problems if a later instruction has already modified memory or registers• If a pipeline can be stopped so that instructions before the fault are completed and those after are restarted, the pipeline has precise exceptions–useful for debugging and of course, correctnessEN164Lecture 10-4Precise Exceptions in the Pipeline• Does our current 5-stage pipeline design provide precise interrupts?EN164Lecture 10-5Handling Multicycle Operations• So far, we have assumed that all instructions take one cycle to execute, once they enter the EX stage.• This may be reasonable for simple integer operations, but what about more complex instructions:–Integer multiply– Floating point multiply– Integer divide– Square root• We could extend the EX stage to 2 or more cycles, but why is this a bad idea?• What about adding multiple execution units of various complexity?EN164Lecture 10-6Adding Specialized ALUs• It is more efficient to add multiple ALU, each with its own delay, meant to handle specific operations• What happens in the pipeline if we have 2 (non-dependent) multicycle operations executed one after the other?IM Re g DM RegALUALUALUALU2EN164Lecture 10-7Pipelined Execution• Balancing delay in each pipeline stage is very important to improve the processor efficiency.• An ALU may also be divided into finer grained stages to allow a new instruction to initiate execution every cycle 2525FP divide17FP multiply14FP add12Data memory11Integer ALUInitiation intervalLatencyFunctional unitEN164Lecture 10-8Pipeline Extensions• Not all functional units can be pipelinedEN164Lecture 10-9Effects of Multicycle Instructions• Creates structural hazards if the unit is not fully pipelined (e.g., the divider)• Data hazard stalls are more frequent• More than one instruction may try to write results to the register file in a cycle–Both a structural and data hazard• New data hazard (write-after-write) is created because of out-of-order instruction completion • Makes handling exceptions more complicated.EN164Lecture 10-10Example of Multicycle Execution• When is data ready for use?• What are the implications of these instructions taking differingnumbers of instructions to complete?– Hazards?– Exceptions?WB11MEM10WBMEMEXIDIFSTOREWBMEMEXIDIFLOADWBMEMA4A3A2A1IDIFADDDM7M6M5M4M3M2M1IDIFMULTD987654321EN164Lecture 10-11Multicycle Execution (cont.)• Where is data forwarded from/to in this example?• What is the implication on forwarding logic when you have multicycle operations?• What is the implication of allowing two instructions to be in the same stage, as shown in cycle 16?IFIDM711IDA1DM12EXA1WB13EXA314EXA415DMDM16IFIDM610IFIFIFIFIFSTOREF2, 0(R2)IDIDIDIDIDIFIFADDF2,F0,F8M5M4M3M2M1IDIDIFMULTF0,F4,F6WBDMEXIDIFLOAD F4, 0(R2)987654321EN164Lecture 10-13Dealing with Multicycle Execution• Multiple writes to the register file:–increase the number of ports, – stall one of the writers during ID, – stall one of the writers during WB (the stall will propagate)• Write-after-write (WAW) hazards:–detect the hazard during ID and stall the later instruction• Imprecise exceptions:–buffer the results if they complete early or save more pipeline state so that you can return to exactly the same state at which you left3EN164Lecture 10-14Instruction Level Parallelism• By pipelining instructions or allowing for multiple instruction execution, we are exploiting instruction-level parallelism (ILP)• What determines the degree of ILP?–Dependences: property of the program– Hazards: property of the