Review 指令级并行LP):流水线的平均CPI Pipeline cpl= ldeal pipeline cpl +t struct stalls RAW Stalls War Stalls WaW stalls Control Stalls 提高指令级并行的方法 软件方法:指令流调度,循环展开,软件流水线, trace scheduling 硬件方法 软件方法:指令流调度-循环展开 指令调度,必须保证程序运行的结果不变 ·偏移量的修改 寄存器的重命名 循环步长的调整 计算机体系结构 17
2021/2/7 计算机体系结构 17 -Review • 指令级并行(ILP) : 流水线的平均CPI – Pipeline CPI = Ideal Pipeline CPI + Struct Stalls + RAW Stalls + WAR Stalls + WAW Stalls + Control Stalls +…… – 提高指令级并行的方法 • 软件方法：指令流调度，循环展开，软件流水线，trace scheduling • 硬件方法 • 软件方法：指令流调度-循环展开 • 指令调度，必须保证程序运行的结果不变 • 偏移量的修改 • 寄存器的重命名 • 循环步长的调整
从编译器角度看代码移动(1/4) 编译器分析程序的相关性依赖于给定的流水线 编译器进行指令调度来消除相关 True)数据相关( Data dependencies) 对于指令和,如果指令傅用指令广生的结果,或 指令j与指令k相关,并且指令k与指令数据相 关 ·如果相关不能并行执行(x)|m 对于寄存器比较容易确定( fixed names 但对 memory的引用,比较难确定 100(R4)=20(R6)? 在不同次的循环中,20(R6)=20(R6
2021/2/7 18 从编译器角度看代码移动（1/4) • 编译器分析程序的相关性依赖于给定的流水线 • 编译器进行指令调度来消除相关 • (True) 数据相关（Data dependencies） – 对于指令i和j，如果指令j使用指令i产生的结果 , 或 指令 j 与指令 k相关, 并且指令 k 与指令 i有数据相 关. • 如果相关, 不能并行执行 • 对于寄存器比较容易确定(fixed names) • 但对memory的引用，比较难确定: – 100(R4) = 20(R6)? – 在不同次的循环中，20(R6) = 20(R6)?
下列程序哪里有数据相关? 1 Loop: Ld FO,O(R1) ADDD F4F0F2 2345 SUBI R1R1 8 BNEZ R1, Loop ,delayed branch Sd 8(R1), F4 altered when move past SUBI 计算机体系结构
2021/2/7 计算机体系结构 19 下列程序哪里有数据相关? 1 Loop: LD F0,0(R1) 2 ADDD F4,F0,F2 3 SUBI R1,R1,8 4 BNEZ R1,Loop ;delayed branch 5 SD 8(R1),F4 ;altered when move past SUBI
从编译器角度看代码移动(2/4) 另一种相关称为名相关( name dependence): 两条指令使用同名参数 (register or memory location) 但不交换数据 一反相关( Antidependence)( WaR if a hazard for hw) Instruction j所写的寄存器或存储单元,与 instruction I所读的 寄存器或存储单元相同,注 cinstruction i是先执行 Dependency Graph 输出相关( Output dependence) WAW if a hazard for hw) Instruction i和 instruction j对同一寄存器或存储单元进行写操 作,必须保证两条指令的写顺序 Dependency Grapt h
2021/2/7 20 从编译器角度看代码移动(2/4) • 另一种相关称为名相关（ name dependence）: 两条指令使用同名参数(register or memory location) 但不交换数据 – 反相关（Antidependence） (WAR if a hazard for HW) • Instruction j 所写的寄存器或存储单元，与 instruction i 所读的 寄存器或存储单元相同，注instruction i 是先执行 – – 输出相关(Output dependence) (WAW if a hazard for HW) • Instruction i 和instruction j 对同一寄存器或存储单元进行写操 作，必须保证两条指令的写顺序
下列是否有名相关? 1 Loop: LD FO,O(R1) ADDD F4F0F2 23456789 SD 0(R1),F4 edrop sUBl BNEZ LDF0,-8(R1) ADDD F4F0F2 SD -8(R1),F4 drop suBl BNEZ LD F0,-16(R1) ADDD F4F0F2 SD -16(R1),F4 edrop sUBl BNEZ 10 LD F0,-24(R1) ADDD F4, F0, F2 SD 24(R1)F4 13 SUBI R1.R1#32 alter to 4*8 14 BNEZ R1 LOOP 15 NOP 如何消除名相关? 21
1 Loop: LD F0,0(R1) 2 ADDD F4,F0,F2 3 SD 0(R1),F4 ;drop SUBI & BNEZ 4 LD F0,-8(R1) 5 ADDD F4,F0,F2 6 SD -8(R1),F4 ;drop SUBI & BNEZ 7 LD F0,-16(R1) 8 ADDD F4,F0,F2 9 SD -16(R1),F4 ;drop SUBI & BNEZ 10 LD F0,-24(R1) 11 ADDD F4,F0,F2 12 SD -24(R1),F4 13 SUBI R1,R1,#32 ;alter to 4*8 14 BNEZ R1,LOOP 15 NOP 如何消除名相关? 2021/2/7 21 下列是否有名相关?