Pipeline Hazards!Hakim&Weatherspoon&CS&3410,&Spring&2011&Computer)Science)Cornell)University)See)P&H)Appendix)4.7))2)Announcements!PA1$available:$mini.MIPS$processor$PA1)due)next)Friday)Work)in)pairs)Use)your)resources)• FAQ,)class)notes,)book,)SecEons,)office)hours,)newsgroup,)CSUGLab))HW1)graded)• Max:)10;)Median:)9;)Mean:)8.3;)Stddev:)1.8)• Great$job!$• Regrade)policy)– Submit)wriUen)request)to)lead)TA,)lead)TA)will)pick)a)different)grader))– Submit)another)wriUen)request,)lead)TA)will)regrade)directly))– Submit)yet)another)wriUen)request)for)professor)to)regrade.))3)Announcements!Prelims:))• Thursday,)March)10th)in)class)• Thursday,)April)28th)Evening))Late)Policy)1))Each)person)has)a)total)of)four)“slip)days”)2))For)projects,)slip)days)are)deducted)from)all)partners))3))10%)deducted)per)day)late)a`er)slip)days)are)exhausted)4)Goals for Today!Data)Hazards)• Data)dependencies)• Problem,)detecEon,)and)soluEons)– (delaying,)stalling,)forwarding,)bypass,)etc))• Forwarding)unit)• Hazard)detecEon)unit)))Next)Eme)• Control)Hazards))What)is)the)next)instrucEon)to)execute)if))a)branch)is)taken?))Not)taken?)5)Broken Example!IF&ID&MEM&WB&IF&ID&MEM& WB&IF&ID&MEM& WB&IF&ID&MEM& WB&IF&ID&MEM&WB&Clock)cycle)1 )2 )3 )4 )5 )6 )7 )8 )9))sub)r5,)r3,)r4))lw)r6,))4(r3)))or)r5,)r3,)r5)sw)r6,)12(r3)))add)r3,)r1,)r2)6)What Can Go Wrong?!Data)Hazards)• register)file)reads)occur)in)stage)2)(ID)))• register)file)writes)occur)in)stage)5)(WB))• next)instrucEons)may)read)values)about)to)be)wriUen)How)to)detect?)Logic)in)ID)stage:))stall)=)(ID.rA)!=)0)&&)(ID.rA)==)EX.rD)||)))) ) ))ID.rA)==)M.rD)||)))) ) ))ID.rA)==)WB.rD)))) )))))))||)(same)for)rB)))7)IF/ID)+4#ID/EX) EX/MEM) MEM/WB)mem)din)dout)addr)inst)PC+4)OP)B)A)Rd)B)D)M) D)PC+4)imm)OP)Rd)OP)Rd)PC#inst)mem)Rd)Ra)Rb)D)B)A)detect)hazard)Detecting Data Hazards!add&r3,&r1,&r2&sub&r5,&r3,&r5&or&r6,&r3,&r4&&add&r6,&r3,&r8&8)Resolving Data Hazards!What)to)do)if)data)hazard)detected?)9)Stalling!Clock)cycle)1) 2) 3) 4) 5) 6) 7) 8)add)r3,)r1,)r2)sub)r5,)r3,)r5)or)r6,)r3,)r4))add)r6,)r3,)r8)10)Forwarding Datapath!data)mem)B)A)B)D)M)D)inst)mem)D)rD)B)A)Rd)Rd)Rd)WE)WE)Op)WE)Op)rA))rB)PC#+4#Op)nop)inst)/stall)11)Stalling!How)to)stall)an)instrucEon)in)ID)stage)• prevent)IF/ID)pipeline)register)update)– stalls)the)ID)stage)instrucEon)• convert)ID)stage)instr)into)nop)for)later)stages)– innocuous)“bubble”)passes)through)pipeline)• prevent)PC)update)– stalls)the)next)(IF)stage))instrucEon)12)Forwarding!Clock)cycle)1) 2) 3) 4) 5) 6) 7) 8)add)r3,)r1,)r2)sub)r5,)r3,)r5)or)r6,)r3,)r4))add)r6,)r3,)r8)13)Forwarding!Clock)cycle)1) 2) 3) 4) 5) 6) 7) 8)add)r3,)r1,)r2)sub)r5,)r3,)r4)lw)r6,))4(r3))or)r5,)r3,)r5)sw)r6,)12(r3))14)Forwarding!Forward)correct)value)from?)1. ALU)output:)too)late)in)cycle?)2. EX/MEM.D)pipeline)register)(output)from)ALU))3. WB)data)value)(output)from)ALU)or)memory))4. MEM)output:)too)late)in)cycle,)on)criEcal)path))to?)a) ID)(just)a`er)register)file))– maybe)pointless?)b) EX,)just)a`er)ID/EX.A)and)ID/EX.B)are)read)c) MEM,)just)a`er)EX/MEM.B)is)read:)on)criEcal)path))data)mem)B)A)B)D)M)D)inst)mem)D)B)A)15)Forwarding Path 1!add)r4,)r1,)r2)nop)sub)r6,)r4,)r1)data)mem)inst)mem)D)B)A)16)WB to EX Bypass!WB)to)EX)Bypass)• EX)needs)value)being)wriUen)by)WB)Resolve:))Add)bypass)from)WB)final)value)to)start)of)EX)Detect:))))))17)Forwarding Path 2!add)r4,)r1,)r2)sub)r6,)r4,)r1)data)mem)inst)mem)D)B)A)18)MEM to EX Bypass!MEM)to)EX)Bypass)• EX)needs)ALU)result)that)is)sEll)in)MEM)stage)Resolve:))Add)a)bypass)from)EX/MEM.D)to)start)of)EX)Detect:))))))19)Forwarding Datapath!data)mem)B)A)B)D)M)D)inst)mem)D)B)A)Rd)Rd)Rb)WE)WE)MC)Ra)MC)20)Tricky Example!data)mem)inst)mem)D)B)A)add)r1,)r1,)r2)SUB)r1,)r1,)r3)OR)r1,)r4,)r1)21)More Data Hazards!add)r4,)r1,)r2)nop)nop)sub)r6,)r4,)r1)data)mem)inst)mem)D)B)A)22)Register File Bypass!Register)File)Bypass)• Reading)a)value)that)is)currently)being)wriUen)Detect:))((Ra)==)MEM/WB.Rd))or)(Rb)==)MEM/WB.Rd))))and)(WB)is)wriEng)a)register))Resolve:))Add)a)bypass)around)register)file)(WB)to)ID)))BeUer:)(Hack))just)negate)register)file)clock)– writes)happen)at)end)of)first)half)of)each)clock)cycle)– reads)happen)during)second)half)of)each)clock)cycle)23)Quiz!Find)all)hazards,)and)say)how)they)are)resolved:))add# #r3,#r1,#r2#sub# #r3,#r2,#r1#nand# #r4,#r3,#r1#or# #r0,#r3,#r4#xor# #r1,#r4,#r3#sb# #r4,#1(r0)#24)Memory Load Data Hazard!lw)r4,)20(r8))sub)r6,)r4,)r1)data)mem)inst)mem)D)B)A)25)Resolving Memory Load Hazard!Load)Data)Hazard)• Value)not)available)unEl)WB)stage))• So:)next)instrucEon)can’t)proceed)if)hazard)detected)ResoluEon:)• MIPS)2000/3000:)one)delay)slot))– ISA)says)results)of)loads)are)not)available)unEl)one)cycle)later)– Assembler)inserts)nop,)or)reorders)to)fill)delay)slot)• MIPS)4000)onwards:)stall)– But)really,)programmer/compiler)reorders)to)avoid)stalling)in)the)load)delay)slot)26)Quiz 2!#add## #r3,#r1,#r2#nand# #r5,#r3,#r4##add## #r2,#r6,#r3##lw## #r6,#24(r3)##sw## #r6,#12(r2)##27)Data Hazard Recap!Delay)Slot(s))• Modify)ISA)to)match)implementaEon))Stall)• Pause)current)and)all)subsequent)instrucEons))Forward/Bypass)• Try)to)steal)correct)value)from)elsewhere)in)pipeline)• Otherwise,)fall)back)to)stalling)or)require)a)delay)slot))Tradeoffs?)28)More Hazards!beq)r1,)r2,)L)add)r3,)r0,)r3)sub)r5,)r4,)r6)L:)or)r3,)r2,)r4)data)mem)inst)mem)D)B)A)PC#+4#29)More Hazards!beq)r1,)r2,)L)add)r3,)r0,)r3)sub)r5,)r4,)r6)L:)or)r3,)r2,)r4)data)mem)inst)mem)D)B)A)PC#+4#30)Control Hazards!Control)Hazards)• instrucEons)are)fetched)in)stage)1)(IF))• branch)and)jump)decisions)occur)in)stage)3)(EX)))• i.e.)next)PC)is)not)known)unEl)2)cycles)a`er)branch/jump))Delay)Slot)• ISA)says)N)instrucEons)a`er)branch/jump)always)executed)– MIPS)has)1)branch)delay)slot))Stall)(+)Zap))• prevent)PC)update)• clear)IF/ID)pipeline)register)– instrucEon)just)fetched)might)be)wrong)one,)so)convert)to)nop)• allow)branch)to)conEnue)into)EX)stage)31)Delay Slot!beq)r1,)r2,)L)ori)r2,)r0,)1)L:)or)r3,)r1,)r4)data)mem)inst)mem)D)B)A)PC#+4#branch)calc)decide)branch)32)Control Hazards: Speculative Execution!Control)Hazards)• instrucEons)are)fetched)in)stage)1)(IF))• branch)and)jump)decisions)occur)in)stage)3)(EX)))•
View Full Document