第四讲 高级流水技术.pptVIP

第二章 高级流水技术 第一节 乱序流动中的数据相关 第二节 循环展开技术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 Unrolling Pipeline 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先读后写) Tomasulo’s algorithm WAW(WW写写) Tomasulo’s algorithm Control Hazard Unrolling Dynamic branch prediction Speculation Instruction Latencies Simple Loop and assembler FP Loop: Where are the Hazards? Loop: LD F0,0(R1) ;F0=vector element ADDD F4,F0,F2 ;add scalar from F2 SD 0(R1),F4 ;store result SUBI R1,R1,8 ;decrement pointer 8B (DW) BNEZ R1,Loop ;branch R1!=zero NOP ;delayed branch slot FP Loop Hazards FP Loop Showing Stalls 10 clocks: Rewrite code to minimize stalls? Revised FP Loop Minimizing Stalls 7 clocks: Unroll loop 4 times code to make faster? Unroll Loop Four Times (straightforward way) Rewrite loop to minimize sta