ch4-1指令级并行_记分牌算法_现在微处理机

复习

流水线基本概念– 能够流水的前提条件 – 流水线的评价指标

DLX基本流水线– 五个阶段，各阶段的功能 – 不同数据通路的作用 – 段间寄存器的设置和作用

表3.1 DLX流水线的每个流水段的操作流水段 IF 任何指令类型 IF/ID.IR ← Mem[PC] IF/ID.NPC,PC ← (if EX/MEM.cond{EX/MEM.ALUOutput} else {PC+4}); ID/EX.A ← Regs[IF/ID.IR6...10]; ID/EX.B ← Regs[IF/ID.IR11...15]; ID/EX.NPC ← IF/ID.NPC; ID/EX.IR ← IF/ID.IR; ID/EX.Imm ← (IR16)16##IR16...31; ALU 指令 EX/MEM.IR ← ID/EX.IR; EX/MEM.ALUOutput ← ID/EX.A op ID/EX.B 或 EX/MEM.ALUOutput ← ID/EX.A op ID/EX.Imm; EX/MEM.cond ← 0; Load/Store 指令 分支指令

ID

EX/MEM.IR ← ID/EX.IR; EX/MEM.ALUOutput← ID/EX.NPC+ID/EX.Imm; EX/MEM.B ←ID/EX.B EX/MEM.ALUOutput ← ID/EX.A + ID/EX.Imm; EX/MEM.cond ← 0;

EX

EX/MEM.cond ← (ID/EX.A op 0);

DLX流水线的每个流水段的操作(续)流水段 ALU 指令 任何指令类型 Load/Store 指令 MEM/WB.LMD ← Mem[EX/MEM.ALUOutput]; 或 Mem[EX/MEM.ALUOutput] ← EX/MEM.B; 分支指令 MEM/WB.IR ←EX/MEM.IR; MEM/WB.IR ← EX/MEM.IR; MEM

MEM/WB.ALUOutput ← EX/MEM.ALUOutput;

WB

Regs[MEM/WB.IR16...20] ← MEM/WB.ALUOutput; 或 Regs[MEM/WB.IR11...15] ← MEM/WB.ALUOutput;

Regs[MEM/WB.IR11...15] ← MEM/WB.LMD;

复习

流水线中的相关– 结构相关：需要更多的硬件资源 – 数据相关：需要定向，编译器调度

– 控制相关：尽早检测条件，计算目标地址，延 迟转移，预测 – 如何构造，如何避免

实例分析：MIPS R4000– 特点

ADD R1, R2, R3

IF ID

EX

ME WB

SUB R5, R1, R7XOR R6, R1, R7 OR R7, R1, R7

IF

IDIF

EXID IF

ME WBEX ID ME WB EX

ME WB

LW

R1, 45(R2)

IF ID

EX

ME WB

SUB R8, R6, R7ADD R5, R1, R7

IF

IDIF

EXID

ME WBEX ME WB

LW ADD ADD SUB SW LW SW

R1, R2, R3 30(R2) R1, R2, R3 R8, R6, R7 R5, 30(R1) R5, 45(R1) R6, 45(R1)

IF ID IF ID IF IF

EX EX ID ID

WB WB ME WB ME WB IF ID EX ME WB IF ID EX ME WB

ME ME EX EX

ADD R1, R2, R3

IF ID

EX

ME WB

SWSW

R1, 45(R3)R1, 45(R4)

IF

IDIF

EXID

ME WBEX ME WB

LW

R1, 56(R2)

IF ID

EX

ME WB

SWSW

R1, 45(R3)R1, 45(R4)

IF

IDIF

EXID

ME WBEX ME WB

Ch 4 指令级并行

Embedded System Lab Fall 2012

内容提要 基本的指令调度方法 记分牌算法 Tomasulo算法

4.1 指令级并行 (Instruction Level Parallelism)

相关是程序运行的本质特征 Loop: 相关带来数据冒险 冒险导致CPU停顿 Stall相关的分类： – 数据相关 – 结构相关 – 控制相关

LD F0,0(R1) SUBI R2,R2,8 SUBI R3,R3,8 ADDD F4,F0,F2

ILP: 无关的指令重叠执行

名相关 另一种相关称为名相关( name dependence): 两条指令使用同一个名字(register or memory location) 但不交换数据– 反相关(Antidependence) (WAR) Instruction j 所写的寄存器或存储单元，与 instruction i 所读的寄存

器或存储单元相同，注instruction i 先执行

– 输出相关(Output dependence) (WAW) Instruction i 和instruction j 对同一寄存器或存储单元进行写操作， 必须保证两条指令的写顺序

下列是否有名相关?1 Loop: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 LD ADDD SD LD ADDD SD LD ADDD SD LD ADDD SD SUBI BNEZ NOP F0,0(R1) F4,F0,F2 0(R1),F4 F0,-8(R1) F4,F0,F2 -8(R1),F4 F0,-16(R1) F4,F0,F2 -16(R1),F4 F0,-24(R1) F4,F0,F2 -24(R1),F4 R1,R1,#32 R1,LOOP

;

如何消除名相关?

指令级并行的若干定义 基本块的定义– 直线型代码，无分支 – 整个程序是由分支语句连接基本块构成 – MIPS 的分支指令占15%左右，基本块的大小在4~7条指令

指令级并行的若干定义 OS代码中的分支较少 负责资源管理 填写状态寄存器 填写控制寄存器 设置控制变量

跨基本块的并行(循环级并行)– 循环的特征 控制循环的分支指令是有执行偏好的 绝大多数是成功的, 预测比较容易，但必须有预测方 案

流水线的平均CPIPipeline CPI = Ideal Pipeline CPI + Struct Stalls + RAW Stalls + WAR Stalls + WAW Stalls + Control Stalls

本章研究– 减少停顿(stalls)数的方法和技术