第四讲-高级流水技术.ppt

Slide Title,Body Text,Second Level,Third Level,Fourth Level,Fifth Level,01-11-1,Page,*,第二章 高级流水技术,第一节 乱序流动中的数据相关,第二节 循环展开技术,LOOP UNROLLING,第三节 重命名技术,第四节 动态调度技术,Scoreboard,Tomasulo,Algorithm,2.1,乱序流动中的数据相关,1.,顺序流动与乱序流动,顺序流动方式：,任务按顺序流入流水线,也按顺序流出流水线,乱序,(Out of order),流动方式：,指令流出流水线的顺序与流入流水线的顺序不同。,又称为,错序流动方式、无序流动方式、异步流动方式等。,2.,乱序流动中的数据相关,在乱序流动方式中，可能发生三种数据相关,写写相关,k,：,LOAD F1,A ;F1,（,A,）,写读相关,k+1,：,FADD F2,F1;F2,（,F2,）,+,（,F1,）,k+2,：,FMUL F1,F3;F1,（,F1,）,（,F3,）,k+3,：,STORE F1,B ;B,（,F1,）,读写相关,(1),写读相关：,指令,k,与指令,k+1,之间关于,F1,的相关，又称为,数据相关、先写后读相关、流相关、,WR,相关、,RAW,相关,等。,(2),读写相关：,指令,k+1,与指令,k+2,之间关于,F1,的相关，变量名相关、先读后写相关、反相关、,RW,相关、,WAR,相关等。,(3),写写相关：,指令,k,与指令,k+2,左边的,F1,之间的相关关系称为：输出相关、写写相关、,WW,相关、,WAW,相关或写后再写相关等。,有时把,相关,称为“,冒险,”,(hazard),、“,竟争,”,(competition),等。,在程序执行过程中，只有避免相关，执行结果才是正确的。,2.2,循环展开技术（,loop unrolling),指令级并行（,ILP,）研究的是一个基本程序块中指令序列之间存在的并行性。,最常见的基本块是循环体,开发循环级并行的最基本技术：,循环展开技术,重命名技术,静态指令调度,:,由优化的编译程序来完成，其基本思想是重排指令序列，拉开具有数据相关的有关指令间的距离。,例：下面程序完成,(A*B)+(C*D),的运算,LOAD R1,M(A),LOAD R2,M(B),MUL R5,R1,R2,LOAD R3,M(C),LOAD R4,M(D),ADD R2,R3,R4,ADD R2,R2,R5,LOAD R1,M(A),LOAD R2,M(B),LOAD R3,M(C),LOAD R4,M(D),MUL R5,R1,R2,ADD R2,R3,R4,ADD R2,R2,R5,Unrolling,P,ipeline CPI=ideal pipeline CPI+RAW stalls+WAR stalls+WAW stalls+Control stalls,LD F6,34(R2),LD F2,45(R3),MULTD F0,F2,F4,SUBD F8,F6,F2,DIVD F10,F0,F6,ADDD F6,F8,F2,RAW,（,WR,先写后读,),Basic scheduling,Scoreboarding,WAR(RW,先读后写,),Tomasulos,algorithm,WAW(WW,写写,),Tomasulos,algorithm,Control Hazard,Unrolling,Dynamic branch prediction,Speculation,Instruction Latencies,InstructionInstructionLatency inproducing resultusing result clock cycles,FP ALU opAnother FP ALU op3,FP ALU opStore double2,Load doubleFP ALU op1,Load doubleStore double0,Integer opInteger op0,Simple Loop and assembler,for,(i=1;i out-of-order completion,ID stage checked both for,structuralScoreboard,dates to CDC 6600 in 1963,HW Schemes:Instruction Parallelism,Out-of-order execution divides ID stage:,1.Issue,decode instructions,check for structural hazards,2.Read operands,wait until no data hazards,then read operands,Scoreboards allow instruction to execute whenever 1&2 hold,not waiting for prior instructions,CDC 6600:,In order issue,out of order execution,out of order commit(also called completion),Scoreboard Implications,Out-of-order completion=WAR,WAW hazards?,Solutions for WAR,Queue both the operation and copies of its operands,Read registers only during Read Operands stage,For WAW,must detect hazard:stall until other completes,Need to have multiple instructions in execution phase=multiple execution units or pipelined execution units,Scoreboard keeps track of dependencies,state or operations,Scoreboard replaces ID,EX,WB with 4 stages,A=B*C,B=D+E,Four Stages of Scoreboard Control,1.,Issue,decode instructions&check for structural hazards(ID1),If a functional unit for the instruction is free and no other active instruction has the same destination register(WAW),the scoreboard issues the instruction to the functional unit and updates its internal data structure.If a structural or WAW hazard exists,then the instruction issue stalls,and no further instructions will issue until these hazards are cleared.,2.Read operands,wait until no data hazards,then read operands(ID2),A source operand is available if no earlier issued active instruction is going to write it,or if the register containing the operand is being written by a currently active functional unit.When the source operands are available,the scoreboard tells the functional unit to proceed to read the operands from the registers and begin execution.The scoreboard resolves RAW hazards dynamically in this step,and instructions may be sent into execution out of order.,Four Stages of Scoreboard Control,3.,Execution,operate on operands(EX),The functional unit begins execution upon receiving operands.When the result is ready,it notifies the scoreboard that it has completed execution.,4.Write result,finish execution(WB),Once the scoreboard is aware that the functional unit has completed execution,the scoreboard checks for WAR hazards.If none,it writes results.If WAR,then it stalls the instruction.,Example:,DIVDF0,F2,F4,ADDDF10,F0,F8,SUBD,F8,F8,F14,CDC 6600 scoreboard would stall SUBD until ADDD reads operands,Three Parts of the Scoreboard,1.,Instruction status,which of 4 steps the instruction is in,2.Functional unit status,Indicates the state of the functional unit(FU).9 fields for each functional unit,Busy,Indicates whether the unit is busy or not,Op,Operation to perform in the unit(e.g.,+or),Fi,Destination register,Fj,Fk,Source-register numbers,Qj,Qk,Functional units producing source registers,Fj,Fk,Rj,Rk,Flags indicating when,Fj,Fk,are ready,3.Register result status,Indicates which functional unit will write each register,if one exists.Blank when no pending instructions will write that register,Detailed Scoreboard Pipeline Control,Read operands,Execution complete,Instruction status,Write result,Issue,Bookkeeping,Rj,No;,Rk,No,f(if,Qj(f,)=FU then,Rj(f,),Yes);,f(if,Qk(f,)=FU then,Rj(f,),Yes);Result(Fi(FU),0;Busy(FU),No,Busy(FU),yes;Op(FU),op;Fi(FU),D;,Fj(FU,),S1;,Fk(FU,),S2;,Qj,Result(S1);,Qk,Result(S2);,Rj,not,Qj,;,Rk,not,Qk,;Result(D),FU;,Rj,and,Rk,Functional unit done,Wait until,f(Fj,(f)Fi(FU)or,Rj,(f)=No)&(,Fk,(f)Fi(FU)or,Rk,(f)=No),Not busy(FU)and not result(D),Scoreboard Example,Scoreboard Example Cycle 1,Scoreboard Example Cycle 2,Issue 2nd LD?,Scoreboard Example Cycle 3,Issue MULT?,Scoreboard Example Cycle 4,Scoreboard Example Cycle 5,Scoreboard Example Cycle 6,Scoreboard Example Cycle 7,Read multiply operands?,Scoreboard Example Cycle 8a,Scoreboard Example Cycle 8b,Scoreboard Example Cycle 9,Read operands for MULT&SUBD?Issue ADDD?,Scoreboard Example Cycle 11,Scoreboard Example Cycle 12,Read operands for DIVD?,Scoreboard Example Cycle 13,Scoreboard Example Cycle 14,Scoreboard Example Cycle 15,Scoreboard Example Cycle 16,Scoreboard Example Cycle 17,Write result of ADDD?,Scoreboard Example Cycle 18,Scoreboard Example Cycle 19,Scoreboard Example Cycle 20,Scoreboard Example Cycle 21,Scoreboard Example Cycle 22,Scoreboard Example Cycle 61,Scoreboard Example Cycle 62,CDC 6600 Scoreboard,Speedup 1.7 from compiler;2.5 by hand BUT slow memory(no cache)limits benefit,Limitations of 6600 scoreboard:,No forwarding hardware,Limited to instructions in basic block(small,window,),Small number of functional units(structural hazards),especailly,integer/load store units,Do not issue on structural hazards,Wait for WAR hazards,Prevent WAW hazards,Summary,Instruction Level Parallelism(ILP)in SW or HW,Loop level parallelism is easiest to see,SW parallelism dependencies defined for program,hazards if HW cannot resolve,SW dependencies/compiler sophistication determine if compiler can unroll loops,Memory dependencies hardest to determine,HW exploiting ILP,Works when cant know dependence at compile time,Code for one machine runs well on another,Key idea of Scoreboard:Allow instructions behind stall to proceed(Decode=Issue,instr,&read operands),Enables out-of-order execution=out-of-order completion,ID stage checked both for structural,Review:Summary,ILP in,SW or HW,Loop level parallelism is easiest to see,SW parallelism dependencies defined for program,hazards if HW cannot resolve,SW dependencies/compiler sophistication determine if compiler can unroll loops,Memory dependencies hardest to determine,HW exploiting ILP,Works when cant know dependence at run time,Code for one machine runs well on another,Key idea of Scoreboard:Allow instructions behind stall to proceed(Decode=Issue,instr,&read operands),Enables out-of-order execution=out-of-order completion,ID stage checked both for structural,Review:Three Parts of the Scoreboard,1.,Instruction status,which of 4 steps the instruction is in,2.Functional unit status,Indicates the state of the functional unit(FU).9 fields for each functional unit,Busy,Indicates whether the unit is busy or not,Op,Operation to perform in the unit(e.g.,+or),Fi,Destination register,Fj,Fk,Source-register numbers,Qj,Qk,Functional units producing source registers,Fj,Fk,Rj,Rk,Flags indicating when,Fj,Fk,are ready,3.Register result status,Indicates which functional unit will write each register,if one exists.Blank when no pending instructions will write that register,Review:Scoreboard Example Cycle 3,Issue MULT?No,stall on structural hazard,Review:Scoreboard Example Cycle 9,Read operands for MULT&SUBD?Issue ADDD?,Review:Scoreboard Example Cycle 17,Write result of ADDD?No,WAR hazard,Review:Scoreboard Example Cycle 62,In-order issue;out-of-order execute&commit,Review:Scoreboard Summary,Limitations of 6600 scoreboard,No forwarding(First write,regsiter,then read it),Limited to instructions in basic block(small,window,),Number of functional units(structural hazards),Wait for WAR hazards,Prevent WAW hazards,Another Dynamic Algorithm:,Tomasulo,Algorithm,For IBM 360/91 about 3 years after CDC 6600(1966),Goal:High Performance without special compilers,Why Study?lead to Alpha 21264,HP 8000,MIPS 10000,Pentium II,PowerPC 604,Tomasulo,Algorithm vs.Scoreboard,Control&buffers,distributed,with Function Units(FU)vs.centralized in scoreboard;,FU buffers called“,reservation stations,”;have pending operands,Registers in instructions replaced by values or pointers to reservation stations(RS);called,register,renaming,;,avoids WAR,WAW hazards,More reservation stations than registers,so can do optimizations compilers cant,Results to FU from RS,not through registers,over,Common Data Bus,that broadcasts results to all,FUs,Load and Stores treated as,FUs,with,RSs,as well,Reservation Station Components,Op,Operation to perform in the unit(e.g.,+or),Vj,Vk,Value,of Source operands,Store buffers has V field,result to be stored,Qj,Qk,Reservation stations producing source registers(value to be written),Note:No ready flags as in Scoreboard;,Qj,Qk,=0=ready,Store buffers only have,Qi,for RS producing result,Busy,Indicates reservation station or FU is busy,Register result status,Indicates which functional unit will write each register,if one exists.Blank when no pending instructions that will write that register.,Three Stages of,Tomasulo,Algorithm,1.Issue,get instruction from FP Op Queue,If reservation station free(no structural hazard),control issues,instr,&sends operands(renames registers).,2.Execution,operate on operands(EX),When both operands ready then execute;if not ready,watch Common Data Bus for result,3.Write result,finish execution(WB),Write on Common Data Bus to all awaiting units;mark reservation station available,Normal data bus:data+destination (“go to”bus),Common data bus,:data+,source,(“,come from,”bus),64 bits of data+4 bits of Functional Unit,source,address,Write if matches expected Functional Unit(produces result),Does the broadcast,Tomasulo,Example Cycle 0,Tomasulo,Example Cycle 1,Yes,Tomasulo,Example Cycle 2,Note:Unlike 6600,can have multiple loads outstanding,Tomasulo,Example Cycle 3,Note:registers names are removed(“renamed”)in Reservation Stations;MULT issued vs.scoreboard,Load1 completing;what is waiting for Load1?,Tomasulo,Example Cycle 4,Load2 completing;what is waiting for it?,Tomasulo,Example Cycle 5,Tomasulo,Example Cycle 6,Issue ADDD here vs.scoreboard?,Tomasulo,Example Cycle 7,Add1 completing;what is waiting for it?,Tomasulo,Example Cycle 8,Tomasulo,Example Cycle 9,Tomasulo,Example Cycle 10,Add2 completing;what is waiting for it?,Tomasulo,Example Cycle 11,Write result of ADDD here vs.scoreboard?,Tomasulo,Example Cycle 12,Note:all quick instructions complete already,Tomasulo,Example Cycle 13,Tomasulo,Example Cycle 14,Tomasulo,Example Cycle 15,Mult1 completing;what is waiting for it?,Tomasulo,Example Cycle 16,Note:Just waiting for divide,Tomasulo,Example Cycle 55,Tomasulo,Example Cycle 56,Mult,2 completing;what is waiting for it?,Tomasulo,Example Cycle 57,Again,in-,oder,issue,out-of-order execution,completion,Compare to Scoreboard Cycle 62,Why takes longer on Scoreboard/6600?,Tomasulo,v.Scoreboard(IBM 360/91 v.CDC 6600),Pipelined Functional Units Multiple Functional Units,(6 load,3 store,3+,2 x/)(1 load/store,1+,2 x,1),window size:14 instructions 5 instructions,No issue on structural hazardsame,WAR:renaming avoidsstall completion,WAW:renaming avoidsstall completion,Broadcast results from FUWrite/read registers,Control:reservation stationscentral scoreboard,Tomasulo,Drawbacks,Complexity,delays of 360/91,MIPS 10000,IBM 620?,Many associative stores(CDB)at high speed,Performance limited by Common Data Bus,Multiple,CDBs,=more FU logic for parallel assoc stores,Tomasulo,Loop Example,Loop:LDF00R1,MULTDF4F0F2,SDF40R1,SUBIR1R1#8,BNEZR1Loop,Assume Multiply takes 4 clocks,Assume first load takes 8 clocks(cache miss?),second load takes 4 clocks(hit),To be clear,will show clocks for SUBI,BNEZ,Reality,integer instructions ahead,Loop Example Cycle 0,Loop Example Cycle 1,Loop Example Cycle 2,Loop Example Cycle 3,Note:MULT1 has no registers names in RS,Loop Example Cycle 4,Loop Example Cycle 5,Loop Example Cycle 6,Note:F0 never sees Load1 result,Loop Example Cycle 7,Note:MULT2 has no registers names in RS,Loop Example Cycle 8,Loop Example Cycle 9,Load1 completing;what is waiting for it?,Loop Example Cycle 10,Load2 completing;what is waiting for it?,Loop Example Cycle 11,Loop Example Cycle 12,Loop Example Cycle 13,Loop Example Cycle 14,Mult1 completing;what is waiting for it?,Loop Example Cycle 15,Mult2 completing;what is waiting for it?,Loop Example Cycle 16,Loop Example Cycle 17,Loop Example Cycle 18,Loop Example Cycle 19,Loop Example Cycle 20,Loop Example Cycle 21,？,If load,addr,=store,addr,.We must stop load and wait until the store buffer get a value,Tomasulo,Summary,Reservations stations:renaming to larger set of registers+buffering source operands,Prevents registers as bottleneck,Avoids WAR,WAW hazards of Scoreboard,Allows loop unrolling in HW,Not limited to basic blocks(integer units gets ahead,beyond branches),Helps cache misses as well,Lasting Contributions,Dynamic scheduling,Register renaming,Load/store disambiguation,360/91 descendants are Pentium II;PowerPC 604;MIPS R10000;HP-PA 8000;Alpha 21264,