Chapter 5 b Overview a The principles of pipelining a A pipelined design of SRC b Pipeline hazards b Instruction level parallelism ILP Superscalar processors Very Long Instruction Word VLIW machines b Microprogramming Control store and micro branching Horizontal and vertical microprogramming Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 Instruction Dependence Pipeline Hazards Instructions that occupy the pipeline together are being executed in parallel This leads to the problem of instruction dependence The basic problem is that an instruction depends on the result of a previously issued instruction that is not yet complete or an instruction requires a resource used by another instruction in the pipeline Three categories of hazards Resource hazards not enough hardware to perform parallel operations e g single ALU for PC PC 4 for ALU instructions Data hazards incorrect use of old and new data Branch hazards fetch of wrong instruction on a change in PC Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 General Data Hazard Classification A read after write hazard RAW arises from a flow dependence where an instruction uses data produced by a prior instruction but the data is not ready add r0 r2 r4 sub r3 r0 r1 sub fetches r0 before add has updated its value A write after read hazard WAR comes from an anti dependence where an instruction writes a new value over one that is still needed by a previous instruction add r2 r1 r0 sub r0 r3 r4 if add sub executed in parallel or out of order and you could not guarantee that add completed prior to sub then one could get a WAR hazard Not possible on SRC Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 General Data Hazard Classification cont A write after write hazard WAW comes from an output dependence where two parallel instructions write the same register and must do it in the order in which they were issued add sub r0 r1 r2 r0 r4 r5 If add sub are executed in parallel or out of order then output register can be overwritten by add instruction Not possible on SRC WAW and WAR can sometimes be fixed by register renaming and synchronization Rename r0 in the add to rx Then add sub rx r1 r2 r0 r4 r5 Comp Sys Design Arch 2nd Edition r0 cannot now be overwritten by add even if they are performed out of order 2004 Prentice Hall Mark Franklin S07 Detecting Data Hazards Dependence Distance To detect hazards pairs of instructions must be considered Data is normally available after being written to register Can be made available for forwarding as early as the stage where it is produced Stage 3 output for ALU results stage 4 for memory fetch Operands normally needed in stage 2 Can be received from forwarding as late as the stage in which they are used Stage 3 for ALU operands and address modifiers stage 4 for stored register stage 2 for branch target Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 Data Hazards in SRC Since all data memory access occurs in stage 4 memory writes reads are sequential give rise to no hazards Since all registers are written in the last stage WAW WAR hazards do not occur Two writes always occur in the order issued and a write always follows a previously issued read SRC hazards on register data are limited to RAW hazards coming from flow dependence i e Values are written into registers at the end of stage 5 but may be needed by a following instruction at the beginning of stage 2 Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 Dealing with Register Data Hazards Detection The machine manual could list rules specifying that a dependent instruction cannot be issued less than a given number of steps after the one on which it depends too restrictive Since the operation and operands are known at each stage dependence on a following stage can be detected Preferred Solution SRC design uses detection forwarding where possible and stalling only when unavoidable Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 RAW Hazard Distance Analysis Stage 1 Stage 2 Inst Fetch Opr Fetch add r1 r2 r3 r2 r3 fetched C r2 r3 Normally register data required S2 Stage 3 Stage 4 ALU Oper Memory Latest time register data required S3 A Normal Latest 2 3 no op Stage 5 Stage 6 Reg Write r1 C Early availability of result S4 Normal availability of result S6 B Normal Early 6 4 B A 6 2 4 3 4 1 Without forwarding ALU instructions having RAW dependencies must be separated by 4 stages Comp Sys Design Arch 2nd Edition With forwarding ALU instructions having RAW dependencies may be separated by 1 stage 2004 Prentice Hall Mark Franklin S07 Instruction Pair Hazard Interaction Write to Reg File Result Normally Earliest available stage Read from Reg File Class Class N L N E alu 2 3 Value 2 3 Normally load ladr 2 3 Latest store 2 3 needed branch 2 2 stage alu 6 4 4 1 4 1 4 1 4 1 4 2 load 6 5 4 2 4 2 4 2 4 2 4 3 ladr 6 4 4 1 4 1 4 1 4 1 4 2 brl 6 2 4 1 4 1 4 1 4 1 4 1 Instruction separation to eliminate hazard Normal Forwarded Latest needed stage 3 for store is based on address modifier register The stored value is not needed until stage 4 Store also needs an operand from ra See Text Tbl 5 Instruction separation is used rather than bubbles because of the applicability to multi issue multi pipelined machines Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 RAW Delays Unavoidable by Forwarding Consider the Load column Note that the value loaded cannot be available to the next instruction even with forwarding Can enforce appropriate stalls Can restrict compiler not to put a dependent instruction in the next position after a load next 2 positions if the dependent instruction is a branch Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 Stalling the Pipeline on Hazard Detection Assuming hazard detection the pipeline can be stalled by inhibiting earlier stage operation allowing later stages to proceed A simple way to inhibit a stage is a pause signal that turns off the clock to that stage so none of its output registers are changed If stages 1 2 say are paused then something must be delivered to stage 3 so the rest of the pipeline can be cleared Insertion of nop into the pipeline is an obvious choice Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 Stalls Due to a Dependence Between Two ALU Instructions Comp Sys Design Arch 2nd Edition 2004 Prentice Hall Mark Franklin S07 Detecting ALU Hazards