<4D F736F F F696E74202D20B5DAC6DFD5C220D6B8C1EEC1F7CBAECFDF2E707074>

Transcription

1 Ch7: Instruction Pipeline 指令流水线 第一讲流水线数据通路和控制逻辑 第二讲流水线冒险处理 第三讲高级流水线技术

2 Pipeline.2 第一讲流水线数据通路和控制主要内容 日常生活中的流水线处理例子 : 洗衣服 单周期处理器模型和流水线性能比较 什么样的指令集适合于流水线方式执行 如何设计流水线数据通路 以 MIPS 指令子集来说明 详细设计取指令部件 详细设计执行部件 分析每条指令在流水线中的执行过程, 遇到各种问题 : - 资源冲突 - 寄存器和存储器的信号竞争 - 分支指令的延迟 - 指令间数据相关 如何设计流水线控制逻辑 分析每条指令执行过程中的控制信号 给出控制器设计过程 流水线冒险的概念

3 Branch Jump Zero Clk RegDst 复习 :A Single Cycle Processor busw 32 Clk Instruction Fetch Unit Rt 1 RegWr Rd Mux imm16 Instr<15:0> Rs 5 Rw Ra Rb bit Registers 16 <31:26> Instruction<31:0> op <16:20> <21:25> Rt busb 32 Extender <11:15> Rd Imm16 busa 32 <0:15> 32 <5:0> 0 Mux 1 func Src op ctr Main Control Data In 3 Control 3 32 Clk Zero 32 RegDst Src : WrEn MemWr Adr Data Memory 32 MemtoReg 0 Mux 1 Pipeline.3 ExtOp

4 复习 :Multiple Cycle Processor MCP: 一个功能部件在一个指令周期中可以被使用多次 PCWr PC IorD 0 Mux PCWrCond PCSrc BrWr Zero MemWr IRWr RegDst RegWr SelA 1 Target 32 RAdr Ideal Memory WrAdr Din Dout 32 Instruction Reg 32 Rs Rt Rt Rd 1 0 Mux Mux 0 Ra Rb Reg File Rw busa busw busb << Mux Mux Control Zero 32 Imm 16 ExtOp Extend 32 MemtoReg SelB Op Pipeline.4

5 复习 :Timing Diagram of a Load Instruction Clk PC Rs, Rt, Rd, Op, Func ctr Old Value Instruction Fetch Instr Decode / Reg. Fetch Clk-to-Q New Value Old Value Old Value Instruction Memory Access Time New Value 1 Address Delay through Control Logic New Value Data Memory Reg Wr ExtOp Old Value New Value Src Old Value New Value RegWr Old Value New Value Register File Access Time busa Old Value New Value Delay through Extender & Mux busb Old Value New Value Delay Address Old Value New Value 2 Data Memory Access Time busw Old Value New 3 Register File Write Time Pipeline.5

6 一个日常生活中的例子 洗衣服 Laundry Example Ann, Brian, Cathy, Dave each have one load of clothes to wash, dry, and fold Washer takes 30 minutes Dryer takes 40 minutes Folder takes 20 minutes A B C D 如果让你来管理洗衣店, 你会如何安排? Pipelining: It s Natural! Pipeline.6

7 Sequential Laundry( 串行方式 ) 6 PM Midnight Time T a s k O r d e r A B C D 串行方式下, 4 批衣服需要花费 6 小时 (4x( )=360 分钟 ) N 批衣服, 需花费的时间为 Nx( ) = 90N 如果用流水线方式洗衣服, 则花多少时间呢? Pipeline.7

8 Pipelined Laundry: (Start work ASAP) 6 PM Midnight Time T a s k O r d e r A B C D 串行方式为 6 小时,N 批则为 90N 分钟 只需 30+4x40+20=210 分 (3.5 小时 ) 如果有 N 批衣服呢? 所花时间为 :30+Nx40+20 分钟 假定每一步时间均衡, 则比串行方式提高约 3 倍! 流水方式下, 所花时间主要与最长阶段时间有关! Pipeline.8

9 复习 :Load 指令的 5 个阶段 阶段 1 阶段 2 阶段 3 阶段 4 阶段 5 Ifetch Reg/Dec Exec Mem Wr Ifetch ( 取指 ) : 从指令存储器取指令并计算 PC+4 ( 用到哪些部件?) 指令存储器 Adder Reg/Dec ( 取数和译码 ) : 寄存器取数, 同时对指令进行译码 ( 用到哪些部件?) 寄存器堆读口 指令译码器 Exec ( 执行 ) : 计算内存单元地址 ( 用到哪些部件?) 扩展器 Mem ( 读存储器 ) : 从数据存储器中读 ( 用到哪些部件?) 数据存储器 Wr( 写寄存器 ): 将数据写到寄存器中 ( 用到哪些部件?) 寄存器堆写口这里寄存器堆的读口和写口可看成两个不同的部件 指令的执行过程是否和 洗衣 过程类似? 是否可以采用类似方式来执行指令呢? Pipeline.9

10 单周期指令模型与流水线性能 假定以下每步操作所花时间为 : - 取指 :2ns - 寄存器读 :1ns Load 指令执行时间总计为 :8ns - 操作 :2ns ( 假定控制单元 PC 访问 信号传递等没有延迟 ) - 存储器读 :2ns - 寄存器写 :1ns 单周期模型 每条指令在一个时钟周期内完成 时钟周期等于最长的 lw 指令的执行时间, 即 :8ns 串行执行时,N 条指令的执行时间为 :8Nns 流水线性能 时钟周期等于最长阶段所花时间为 :2ns 每条指令的执行时间为 : 2nsx5=10ns N 条指令的执行时间为 :(4+N)x2ns 在 N 很大时, 比串行方式提高约 4 倍 若各阶段操作均衡 ( 例如, 各阶段都是 2ns), 则提高倍数为 5 倍 非流水线执行时间 / 流水线执行时间 = 流水线步骤数流水线方式下, 单条指令的执行时间不能缩短, 但能大大提高指令的吞吐量 Pipeline.10

11 流水线指令集的设计 具有什么特征的指令集有利于流水线执行呢? 指令长度尽量一致, 有利于简化取指令和指令译码操作 - MIPS 指令都是 32 位, 每次取四个单元的指令, 且下址计算方便 : PC+4 - X86 指令从 1 字节到 17 字节不等, 使取指部件及其复杂 指令格式少, 且源寄存器位置相同, 有利于在指令未知时就可取操作数 - MIPS 指令的 Rs 和 Rt 位置一定, 在指令译码时就可读 Rs 和 Rt 的值 ( 若位置随指令不同而不同, 则需先译码确定指令后才能取寄存器编号 ) 只有 load / Store 指令才能访问存储器, 有利于减少操作步骤, 规整流水线 - 可以把 lw/sw 指令的地址计算和运算指令的执行步骤规整在同一个周期 - X86 运算类指令的操作数可以是内存数据, 故需计算地址 访存 执行 数据和指令在内存中要 对齐 存放, 有利于减少访存次数和流水线的规整总之, 规整 简单和一致等特性有利于指令的流水线执行指令的流水线执行方式能大大提高指令的吞吐率, 现代计算机都采用流水线方式 Pipeline.11

12 Load 指令的流水线 Clock Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 1st lw Ifetch Reg/Dec Exec Mem Wr 2nd lw Ifetch Reg/Dec Exec Mem Wr 3rd lw Ifetch Reg/Dec Exec Mem Wr 每个周期有五个功能部件同时在工作 后面指令在前面完成取指后马上开始 每个 load 指令仍然需要五个周期完成 但是吞吐率 (throughput) 提高许多, 理想情况下, 有 : 每个周期有一条指令进入流水线 每个周期都有一条指令完成 每条指令的有效周期 (CPI) 为 1 Pipeline.12

13 R-type 指令的 4 个阶段 Cycle 1 Cycle 2 Cycle 3 Cycle 4 R-type Ifetch Reg/Dec Exec Wr Ifetch: 取指令并计算 PC+4 Reg/Dec: 从寄存器取数, 同时指令在译码器进行译码 Exec: 在 中对操作数进行计算 Wr: 计算的结果写到寄存器 Pipeline.13

14 含 R-type 和 Load 指令的流水线 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Clock R-type Ifetch Reg/Dec Exec Wr Ops! We have a problem! R-type Ifetch Reg/Dec Exec Wr Load Ifetch Reg/Dec Exec Mem Wr R-type Ifetch Reg/Dec Exec Wr R-type Ifetch Reg/Dec Exec Wr 上述流水线有个问题 : 两条指令试图同时写寄存器 Load 在第 5 阶段用寄存器写口 R-type 在第 4 阶段用寄存器写口 把一个功能部件同时被多条指令使用的现象称为结构冒险 (Struture Hazard) 为了流水线能顺利工作, 规定 : 每个功能部件每条指令只能用一次 ( 如 : 写口不能用两次或以上 ) 每个功能部件必须在相同的阶段被使用 ( 如 : 写口总是在第五阶段被使用 ) Pipeline.14 可以用以下两种方法解决上述结构冒险问题!

15 解决方案 1: 在流水线中插入 Bubble ( 气泡 ) Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Clock Ifetch Reg/Dec Exec Wr Load Ifetch Reg/Dec Exec Mem Wr R-type Ifetch Reg/Dec Exec R-type Ifetch Reg/Dec R-type Ifetch Wr Wr Pipeline Exec Wr Exec Wr Reg/Dec Bubble Reg/Dec Exec Wr Exec Wr Ifetch Reg/Dec Ifetch Reg/Dec Exec Exec 插入 Bubble 到流水线中, 以禁止同一周期有两次写寄存器 缺点 : 控制逻辑复杂 第 5 周期没有指令被完成 (CPI 不是 1, 而实际上是 2) 方案不可行! Pipeline.15

16 解决方案 2: R-type 的 Wr 操作延后一个周期执行 NOOP! R-type Ifetch Reg/Dec Exec Mem Wr 加一个 NOP 阶段以延迟 写 操作 : 把 写 操作安排在第 5 阶段, 这样使 R-Type 的 Mem 阶段为空 NOP Clock Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 R-type Ifetch Reg/Dec Exec Mem Wr R-type Ifetch Reg/Dec Exec Mem Wr Load Ifetch Reg/Dec Exec Mem Wr R-type Ifetch Reg/Dec Exec Mem Wr R-type Ifetch Reg/Dec Exec Mem Wr 这样使流水线中的每条指令都有相同多个阶段! Pipeline.16

17 Store 指令的四个阶段 Cycle 1 Cycle 2 Cycle 3 Cycle 4 NOOP! Store Ifetch Reg/Dec Exec Mem Wr Ifetch: 取指令并计算 PC+4 Reg/Dec: 从寄存器取数, 同时指令在译码器进行译码 Exec:16 位立即数符号扩展后与寄存器值相加, 计算主存地址 Mem: 将寄存器读出的数据写到主存 Wr: 加一个空的写阶段, 使流水线更规整! Pipeline.17

18 Beq 的四个阶段 Cycle 1 Cycle 2 Cycle 3 Cycle 4 NOOP! Beq Ifetch Reg/Dec Exec Mem Wr Ifetch: 取指令并计算 PC+4 Reg/Dec: 从寄存器取数, 同时指令在译码器进行译码 Exec: 执行阶段 Pipeline.18 中比较两个寄存器的大小 ( 做减法 ) Adder 中计算转移地址 Mem: 如果比较相等, 则 : 转移目标地址写到 PC Wr: 加一个空的写阶段, 使流水线更规整! 按照上述方式, 把所有指令都按照最复杂的 load 指令所需的五个阶段来划分, 不需要的阶段加一个 NOP 操作 给出的流水线通路中的处理过程和多周期通路中的有什么不同? 多周期通路中, 在 Reg/Dec 阶段 投机进行了转移地址的计算! 可以减少 Branch 指令的时钟数 为什么流水线中不进行 投机 计算? 因为, 流水线中所有指令的执行阶段一样多,Branch 指令无需节省时钟, 因为有比它更复杂的指令

19 A Pipelined Datapath( 五阶段流水线数据通路 ) Clock-to-Q delay Clk PC 1 0 Ifetch (IF) Reg/Dec (ID) Exec (Ex) Mem Wr 有! 寄存器写口 PC+4 AIUnit I IF/ID Register 为什么需要这些 Reg? 保存每个周期执行的结果! 不同于 PC, 属于内部寄存器, RegWr PC+4 Imm16 Rs Ra Rt Rt Rd 对程序员透明 Pipeline.19, 不需作为现场保存 Rb RFile Rw Di ID/Ex Register RegDst ExtOp 0 1 PC+4 Imm16 busa busb Exec Unit Op Src Ex/Mem Register Zero Branch MemWr Data Mem RA Do WA Di 下面看一下每条指令在流水线通路中的执行过程 Mem/Wr Register MemtoReg Wr 阶段没有 DataPath 吗? 1 Mux 0

20 取指令 (Ifetch) 阶段 第 10 单元指令 : lw $1, 0x100($2) 功能 :$1 <- Mem [($2) + 0x100] You are here! Clk Ifetch Reg/Dec Exec Mem RegWr ExtOp Op Branch PC = PC+4 AIUnit I IF/ID: lw $1, 100 ($2) PC+4 Imm16 Rs Rt Ra Rb RFile Rt Rw Di Rd ID/Ex Register 0 1 PC+4 Imm16 busa busb Exec Unit Ex/Mem Register Zero Data Me m RA Do WA Di Mem/Wr Register 1 Mux 0 下一目标 : 设计 IUnit 有谁发现这里有一个假设有问题? MIPS 指令的地址可能是 10 吗? Pipeline.20 RegDst Src MemWr MemtoReg

21 指令部件 IUnit 的设计 第 10 单元指令 : : lw $1, 0x100($2) 随后的指令在 14 号单元中! 指令部件的功能是什么? Instr <- Mem[PC] PC<- PC+4 Clk Ifetch You are here! Reg/Dec 这里 MUX 的控制信号由其他阶段产生! Pipeline.21 PC 新值 (14) 旧输出 (10) PC = 取指阶段有哪些控制信号? 4 Address Instruction Memory Instruction Adder 不需要控制信号, 因为每条指令所执行的功能都一样, 是确定的操作, 无需根据指令的不同来控制执行不同的操作! IF/ID: lw $1, 100 ($2) 开始从 14 号单元取指令! 流水段寄存器用来存放每个阶段 ( 一个时钟内 ) 的执行结果 总是在下个时钟到来后的 Clock-to-Q 写入 应该把哪些信息保存到流水段寄存器 IF/ID 中? 应保存后面阶段要用到的指令和 PC+4 的值! 指令在随后阶段送出译码! PC+4 用来计算转移目标地址!

22 译码 / 取数 (Reg/Dec) 阶段 Location 10: lw $1, 0x100($2) 功能 :$1 <- Mem[($2) + 0x100] You are here! Clk Ifetch Reg/Dec Exec Mem RegWr ExtOp Op Branch PC Pipeline 指令还要存在 ID/EX 中吗? 不要, 只要存相关信息! PC+4 AIUnit I IF/ID: PC+4 Imm16 Rs Ra Rt Rt Rd Rb RFile Rw Di ID/Ex: Reg. 2 & 0x100 Imm16 busa busb Exec Unit Ex/Mem Register Data Mem RA Do WA Di Reg[Rs],Reg[Rt],Rt,Rd,Imm16, PC+4 等被保存在 ID/EXE 中 RegDst Src MemWr MemtoReg 该阶段有哪些控制信号? 没有! 因是所有指令的公共操作, 故无控制信号! 0 1 PC+4 Zero Mem/Wr Register 1 Mux 0

23 Load 指令的地址计算阶段 Location 10: lw $1, 0x100($2) 功能 :$1 <- Mem[($2) + 0x100] 指令已被译码, 可确定执行部件的控制信号! You are here! Clk Ifetch Reg/Dec Exec Mem RegWr Op=? ExtOp=? Branch PC Pipeline PC+4 AIUnit I IF/ID: PC+4 Imm16 Rs Ra Rt Rt Rd Rb RFile Rw 如果目的寄存器 Rt 不传递下去, 会怎样? 其他指令的 Rt 作为目的地址, 指令执行错误! Di ID/Ex Register 0 1 RegDst=0 PC+4 Imm16 busa busb Exec Unit Ex/Mem: Load s Address Zero Src=? MemWr 下一目标 : 设计执行部件 (Exec Unit) Data Mem RA Do WA Di Mem/Wr Register MemtoReg 1 Mux 0

24 Pipeline.24 执行部件 (Exec Unit) 的设计 执行部件功能是什么? 综合前面每条指令在执行阶段的功能, Clk 可知 : 计算数据内存地址 计算转移目标地址 一般 运算 Load 指令的各控制信号取值? RegDes=0, Src=1 op=add, Extop=1 Store 指令呢? RegDes=x, Src=1 op=abb, Extop=1 Branch 指令呢? RegDes=x, Src=0 op=sub, Extop=1 Ori 指令呢? RegDes=0, Src=1 op=or, Extop=0 ID/Ex Register PC+4 busa busb imm Extender << 2 ExtOp=? 32 Exec Adder 用于计算分支指令的转移地址 0 Mux 1 Adder Src=? R 型指令呢? RegDes=1, Src=0 op= func, Extop=x Target 32 3 Control Zero out 32 ctr 3 Op=? You are here! Mem Ex/Mem: Load s Memory Address

25 Load 指令的存储器读 (Mem) 周期 Location 10: lw $1, 0x100($2) 功能 : $1 <- Mem[($2) + 0x100] You are here! Clk Ifetch Reg/Dec Exec Mem RegWr ExtOp Op Branch=0 Pipeline.25 PC 1 0 PC+4 AIUnit I IF/ID: PC+4 比较洗衣流水线, 指令流水线有什么不同? 洗衣流程不能反向进行, 但该阶段有反向数据流, 可能会引起冒险! 以后介绍 Imm16 Rs Ra Rt Rt Rd Rb RFile Rw Di ID/Ex Register RegDst 0 1 PC+4 Imm16 busa busb Exec Unit Src Ex/Mem Register Zero MemWr=0 周期以最长操作为准设计 Cycle > T read Data Mem RA Do WA Di Mem/Wr: Load s Data MemtoReg 1 Mux 0

26 Load 指令的回写 (Write Back) 阶段 Location 10: lw $1, 0x100($2) 功能 :$1 <- Mem[($2) + 0x100] Clk Ifetch Reg/Dec Exec Mem Wr RegWr=1 ExtOp Op Branch PC Pipeline PC+4 AIUnit I IF/ID: PC+4 Imm16 Rs Ra Rt Rt Rd 比较洗衣流水线, 指令流水线有什么不同? 洗衣流程不能反向进行, 但该阶段有反向数据流, 可能会引起冒险! 以后介绍 Rb RFile Rw Di ID/Ex Register RegDst 0 1 PC+4 Imm16 busa busb Exec Unit Src Ex/Mem Register Zero MemWr Data Mem RA Do WA Di 各阶段所经 DataPath 已有, 控制信号如何得到? Mem/Wr Register 1 Mux 0 MemtoReg=1

27 流水线中的 Control Signals 如何获得? 主要考察 : 第 N 阶段的控制信号, 它取决于是哪条指令的哪个阶段 N = Exec, Mem, or Wr ( 只有这三个阶段有控制信号 ) 例 : Load 的 Exec 段的控制信号 = Func (Load s Exec) Ifetch Reg/Dec Exec Mem Wr Op=Add RegWr ExtOp=1 Branch PC 1 0 PC+4 AIUnit I IF/ID: PC+4 Imm16 Rs Rt Ra Rb RFile Rt Rw Di Rd ID/Ex Register 0 1 PC+4 Imm16 busa busb Exec Unit Ex/Mem: Load s Address Zero Data Mem RA Do WA Di Mem/Wr Register 1 Mux 0 Pipeline.27 为什么 1 st 和 2 nd 阶段没有控制信号? RegDst=0 Src=1 MemWr MemtoReg IF 和 ID 阶段的功能对每条指令来说都一样, 且各阶段功能部件独立!

28 Load 指令 : 流水线中的控制信号 在取数 / 译码 (Reg/Dec) 阶段产生本指令每个阶段的所有控制信号 Exec 信号 (ExtOp, Src,...) 在 1 个周期后使用 Mem 信号 (MemWr, Branch) 在 2 个周期后使用 Wr 信号 (MemtoReg, RegWr) 在 3 个周期后使用 所以, 控制信号也要保存在流水段寄存器中! Reg/Dec Exec Mem Wr IF/ID Register Main Control ExtOp Src Op RegDst MemWr Branch MemtoReg RegWr ID/Ex Register ExtOp Src Op RegDst MemWr Branch MemtoReg RegWr Ex/Mem Register MemWr Branch MemtoReg RegWr Mem/Wr Register MemtoReg RegWr 各个流水段部件在一个时钟内完成某条指令的某个阶段的工作! 然后, 在下个时钟到达时, 把执行的结果以及前面传递过来的后面各阶段要用到的所有数据 ( 如 : 指令 立即数 目的寄存器等 ) 和控制信号保存到流水线寄存器中! Pipeline.28

29 流水线中的 Control Signals 通过对前面流水线数据通路的分析, 得知 : 因为每个时钟都会改变 PC 的值, 所以 PC 不需要写控制信号 流水段寄存器每个时钟都会写入一次, 也不需要写控制信号 Ifecth 阶段和 Dec/Reg 阶段都没有控制信号 Exec 阶段的控制信号有四个 - ExtOp ( 扩展器操作 ):1- 符号扩展 ;0- 零扩展 - Src ( 的 B 口来源 ):1- 来源于扩展器 ;0- 来源于 BusB - Op ( 主控制器输出, 用于辅助局部 控制逻辑来决定 Ctrl) - RegDst ( 指定目的寄存器 ):1- Rd;0- Rt Mem 阶段的控制信号有两个 - MemWr (DM 的写信号 ):Store 指令时为 1, 其他指令为 0 - Branch ( 是否为分支指令 ): 分支指令时为 1, 其他指令为 0 Wr 阶段的控制信号有两个 - MemtoReg ( 寄存器的写入源 ):1- DM 输出 ;0- 输出 - RegWr ( 寄存器堆写信号 ): 结果写寄存器的指令都为 1, 其他指令为 0 Pipeline.29

30 控制逻辑 Control) 的设计 流水线控制逻辑的设计 每条指令的控制信号在指令执行期间都不变 ( 谁记得单周期和多周期时是怎样的情况?) 与单周期控制逻辑设计类似 ( 谁记得单周期和多周期控制逻辑各是怎样设计的?) 设计过程 - 控制逻辑分成两部分 主控制逻辑 : 生成 op 和其他控制信号 局部 控制逻辑 : 根据 op 和 func 字段生成 Ctrl - 用真值表建立指令和控制信号之间的关系 - 写出每个控制信号的逻辑表达式 控制逻辑的输出在 ID 阶段生成, 并存放在 ID/EX 流水段寄存器中, 然后每来一个时钟跟着指令传送到下一级流水段寄存器 同一时刻在不同阶段执行不同指令, 因而不同阶段的控制信号对应不同的指令 忘记单周期和多周期控制设计的同学, 复习一下第五章的内容! Pipeline.30

31 蓝色部分是控制信号

32 Load 指令 : 流水线中的控制信号 在取数 / 译码 (Reg/Dec) 阶段产生本指令每个阶段的所有控制信号 Exec 信号 (ExtOp, Src,...) 在 1 个周期后使用 Mem 信号 (MemWr, Branch) 在 2 个周期后使用 Wr 信号 (MemtoReg, RegWr) 在 3 个周期后使用 ( 这里是否会有问题?) 所以, 控制信号也要保存在流水段寄存器中! Rt 和 Data 在 RegWr 后到达怎么办? Reg/Dec Exec Mem Wr IF/ID Register Main Control ExtOp Src Op RegDst MemWr Branch MemtoReg RegWr ID/Ex Register ExtOp Src Op RegDst MemWr Branch MemtoReg RegWr Ex/Mem Register 同样, 这里也有问题! MemWr Branch MemtoReg RegWr Mem/Wr Register Rt Data MemtoReg RegWr Pipeline.32 保存在流水段寄存器中的信息 ( 包括前面阶段传递来或执行的结果及控制信号 ) 一起被传递到下一个流水段!

33 Wr 阶段的开始 : 存在一个实际的问题! Clk Clk RegAdr WrAdr RegWr RegWr s Clk-to-Q MemWr MemWr s Clk-to-Q Mem/Wr RegWr RegAdr Data RegAdr s Clk-to-Q Reg File Ex/Mem MemWr WrAdr Data WrAdr s Clk-to-Q Data Memory 在流水线中也存在地址和写使能之间的 竞争 问题 Wr 段开始时, 如果 RegAdr s (Rd/Rt) Clk-to-Q > RegWr s Clk-to-Q, 则错写寄存器! Mem 阶段开始时, 如果 WrAdr s Clk-to-Q > MemWr s Clk-to-Q, 则错写存储器! 不能用多周期中的方法! 为什么? 哪个同学记得多周期中是如何处理 竞争 问题的? Pipeline.33

34 流水线中的 竞争 问题 多周期中解决 Addr 和 WrEn 之间竞争问题的方法 : 在第 N 周期结束时, 让 Addr 信号有效保证 Addr 信号在 WriteEnable 信号 在第 N + 1 周期让 WrEn 有效之前到达 上述方法在流水线设计中不能用, 因为 : 每个周期必须能够写 Register 每个周期必须能够写 Memory Clock Store Ifetch Reg/Dec Exec Mem Wr Store Ifetch Reg/Dec Exec Mem Wr R-type Ifetch Reg/Dec Exec Mem Wr 如何解决? R-type Ifetch Reg/Dec Exec Mem Wr Pipeline.34

35 寄存器组的同步和存储器的同步 解决方案 : 将 Write Enable 和时钟信号 与 须由电路专家确保不会发生 定时错误 ( 即 : 能合理设计 Clock!) Clk I_Addr I_WrEn 1. Address, Data, 和 WrEn 必须在 Clk 边沿到来后至少稳定一个 set-up 时间 2.Clk 高电平时间大于写入时间 C_WrEn Actual write WrEn WrEn C_WrEn Address Data I_WrEn I_Addr I_Data Reg File or Memory 等价于 Address Data Clk Reg File or Memory 相当于单周期通路中的理想寄存器和存储器 Pipeline.35

36 流水线举例 : 考察流水线 DataPath 的数据流动情况 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Clock 0: Load Ifetch Reg/Dec Exec Mem Wr 4: R-type Ifetch Reg/Dec Exec Mem Wr 8: Store Ifetch Reg/Dec Exec Mem Wr 12: Beq (target is 1000) Ifetch Reg/Dec Exec Mem Wr 考察以下几个点的情况 : End of Cycle 4 End of Cycle 5 End of Cycle 6 End of Cycle 7 End of Cycle 4: Load s Mem, R-type s Exec, Store s Reg, Beq s Ifetch End of Cycle 5: Load s Wr, R-type s Mem, Store s Exec, Beq s Reg End of Cycle 6: R-type s Wr, Store s Mem, Beq s Exec End of Cycle 7: Store s Wr, Beq s Mem 说明 : 后面仅考察数据流动情况, 控制信号随数据同步流动, 不再说明控制信号的流动 Pipeline.36

37 第四周期结束时的状态 : 0: Load s Mem 4: R-type s Exec 8: Store s Reg 12: Beq s Ifetch 12: Beq s Ifet 8: Store s Reg 4: R-type s Exec 0: Load s Mem? s Wr PC = PC+4 AIUnit I IF/ID: Beq Instruction RegWr=? Clk PC+4 Imm16 Rs Rt Ra Rb RFile Rt Rw Di Rd ID/Ex: Store s busa & B Op=R-type ExtOp=x 0 1 PC+4 Imm16 busa busb Exec Unit Ex/Mem: R-type s Result Zero Branch=0 Data Mem RA Do WA Di Mem/Wr: Load s Dout Load 指令前某条指令 1 Mux 0 如果 Mem 阶段是 Branch 且 Zero 为 1, 会怎样? Pipeline.37 RegDst=1 Src=0 Clk MemWr=0 MemtoReg=?

38 第五周期结束时的状态 : 0: Lw s Wr 4: R s Mem 8: Store s Exec 12: Beq s Reg 16: R s Ifetch 16: R s Ifet 12: Beq s Reg 8: Store s Exec 4: R-type s Mem RegWr=1 Op=Add ExtOp=1 Branch=0 0: Load s Wr 20 PC = PC+4 AIUnit I IF/ID: 16 Clk PC+4 Imm16 Rs Rt Ra Rb RFile Rt Rw Di Rd ID/Ex: Beq s busa & B 0 1 PC+4 Imm16 busa busb Exec Unit Ex/Mem: Store s Address Zero Data Mem RA Do WA Di Mem/Wr: R-type s Result 1 Mux 0 同一周期寄存器有读 有写, 可能吗? RegDst=x Src=1 Clk 利用时钟上升和下降沿两次触发, 能做 MemWr=0 到前半周期写, 后半周期读寄存器的写口和读口可看成是独立的两个部件! Pipeline.38 MemtoReg=1

39 第六周期结束时的状态 : 4: R s Wr 8: Store s Mem 12: Beq s Exec 16: R s Reg 20: R s Ifet 20:R-type s Ifet 16: R-type s Reg 12: Beq s Exec 8: Store s Mem 4: R-type s Wr Op=Sub RegWr=1 ExtOp=1 Branch=0 PC = PC+4 AIUnit I IF/ID: 20 Clk PC+4 Imm16 Rs Rt Ra Rb RFile Rt Rw Di Rd ID/Ex:R-type s busa & B 0 1 PC+4 Imm16 busa busb Exec Unit Ex/Mem: Beq s Results Zero Data Mem RA Do WA Di Mem/Wr: Nothing for St 1 Mux 0 Ifetch 和 Reg 两个周期每条指令执行的都一样! RegDst=x Src=0 Clk MemWr=1 MemtoReg=0 Pipeline.39

40 第七周期结束时的状态 : 8: Store s Wr 12: Beq s Mem 16: R s Exec 20: R s Reg 24: R s Ifet 24:R-type s Ifet 20: R-type s Reg 16: R-type s Exec 12: Beq s Mem 8: Store s Wr Op=R-type RegWr=0 ExtOp=x Branch=1 PC = 假定相等, 则 Zero=1 转移目标地址送 PC! PC+4 AIUnit I IF/ID: 24 Clk PC+4 Imm16 Rs Rt Ra Rb RFile Rt Rw Di Rd ID/Ex:R-type s busa & B 0 1 PC+4 Imm16 busa busb Exec Unit Ex/Mem: Rtype s Results Zero Data Mem RA Do WA Di Mem/Wr:Nothing for Beq 1 Mux 0 这里出现反向数据流! 转移目标地址反向送给 PC 可能会导致控制冒险! RegDst=1 Src=0 Clk MemWr=0 MemtoReg=x Pipeline.40

41 总结前面的流水线执行过程 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Clock 0: Load Ifetch Reg/Dec Exec Mem Wr 4: R-type Ifetch Reg/Dec Exec Mem Wr 8: Store Ifetch Reg/Dec Exec Mem Wr 1000: Target of Br Ifetch Reg/Dec Exec 回忆刚才的过程, 回答以下问题 : Branch 指令何时确定是否转移? 转移目标地址在第几周期计算出来? - 第六周期得到 Zero 和转移地址 第七周期控制转移地址送到 PC 输入端 第八周期开始 才能根据转移地址取指令 - 如果 Branch 指令执行结果是需要转移 ( 称为 taken), 则流水线会怎样? Load 指令何时能把数据写到寄存器? 第几周期开始写数据? - 第五周期写入 第六周期开始才能使用 - 如果后面 R-Type 的操作数是 load 指令目标寄存器的内容, 则流水线怎样? Pipeline.41 12: Beq (target is 1000) Ifetch Reg/Dec Exec Mem Wr 16: R-type Ifetch Reg/Dec Exec Mem Wr 20: R-type Ifetch Reg/Dec Exec Mem Wr 24: R-type Ifetch Reg/Dec Exec Mem

42 转移分支指令 (Branch) 引起的 延迟 现象 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10 Cycle 11 Clk 12: Beq Ifetch Reg/Dec Exec Mem Wr (target is 1000) 16: R-type Ifetch Reg/Dec Exec Mem Wr 20: R-type Ifetch Reg/Dec Exec Mem Wr 24: R-type Ifetch Reg/Dec Exec Mem Wr 1000: Target of Br Ifetch Reg/Dec Exec Mem Wr 虽然 Beq 指令在第四周期取出, 但 : 目标地址在第七周期才被送到 PC 的输入端 第八周期才能取出目标地址处的指令执行结果 : 在取目标指令之前, 已有三条指令被取出, 取错了三条指令! 这种现象称为控制冒险 (Control Hazard ) ( 注 : 也称为分支冒险或转移冒险 (Branch Hazard) ) BACK Pipeline.42

43 Clock 装入指令 (Load) 引起的 延迟 现象 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 I0: Load Ifetch Reg/Dec Exec Mem Wr Plus 1 Ifetch Reg/Dec Exec Mem Wr Plus 2 Ifetch Reg/Dec Exec Mem Wr Plus 3 Ifetch Reg/Dec Exec Mem Wr R-Type Ifetch Reg/Dec Exec Mem Wr 尽管 Load 指令在第一周期就被取出, 但 : 数据在第五周期结束才被写入寄存器 在第六周期时, 写入的数据才能被用结果 : 在 Load 指令结果有效前, 已经有三条指令被取出 ( 如果随后的指令要用到 Load 的数据的话, 就需要延迟三条指令才能用!) 这种现象被称为数据冒险 (Data Hazard) 或数据相关 (Data Dependency ) Pipeline.43

44 第一讲内容小结 指令的执行可以像洗衣服一样, 用流水线方式进行 均衡时指令吞吐率提高 N 倍, 但不能缩短一条指令的执行时间 流水段数以最复杂指令所需步骤数为准 ( 有些指令的某些阶段为空操作 ), 每个阶段的宽度以最复杂阶段所需时间为准 ( 尽量调整使各阶段均衡 ) 以 Load 指令为准, 分为五个阶段 取指令段 (IF) - 取指令 计算 PC+4(IUnit:Instruction Memory Adder) 译码 / 读寄存器 (ID/RF) 段 - 指令译码 读 Rs 和 Rt( 寄存器读口 ) 执行 (EXE) 段 - 计算转移目标地址 运算 (Extender Adder) 存储器 (MEM) 段 - 读或写存储单元 (Data Memory) 写寄存器 (Wr) 段 - 结果或从 DM 读出数据写到寄存器 ( 寄存器写口 ) 流水线控制器的实现 IF 和 ID/RF 段不需控制信号控制, 只有 EXE MEM 和 Wr 需要 ID 段生成所有控制信号, 并随指令的数据同步向后续阶段流动 寄存器和存储器的竞争问题可利用时钟信号来解决 流水线冒险 : 结构冒险 控制冒险 数据冒险 ( 下一讲主要介绍解决流水线冒险的数据通路如何设计 ) Pipeline.44

45 第二讲流水线冒险的处理主要内容 流水线冒险的几种类型 数据冒险的现象和对策 数据冒险的种类 - 相关的数据是 结果 : 可以通过转发解决 - 相关的数据是 DM 读出的内容 : 随后的指令需被阻塞一个时钟 数据冒险和转发 - 转发检测 / 转发控制 数据冒险和阻塞 - 阻塞检测 / 阻塞控制 控制冒险的现象和对策 静态分支预测技术 动态分支预测技术 缩短分支延迟技术 流水线中对异常和中断的处理 访问缺失对流水线的影响 Pipeline.45

46 总结 : 流水线的三种冲突 / 冒险 (Hazard) 情况 Hazards: 指流水线遇到无法正确执行后续指令或执行了不该执行的指令 Structural hazards (hardware resource conflicts): 现象 : 同一个部件同时被不同指令所使用 - 一个部件每条指令只能使用 1 次, 且只能在特定周期使用 - 设置多个部件, 以避免冲突 如指令存储器 IM 和数据存储器 DM 分开 Data hazards (data dependencies): 现象 : 后面指令用到前面指令结果时, 前面指令结果还没产生 - 采用转发 (Forwarding/Bypassing) 技术 - Load-use 冒险需要一次阻塞 (stall) - 编译程序优化指令顺序 Control (Branch) hazards (changes in program flow): 现象 : 转移或异常改变执行流程, 顺序执行指令在目标地址产生前已被取出 - 采用静态或动态分支预测 - 编译程序优化指令顺序 ( 实行分支延迟 ) SKIP Pipeline.46

47 Structural Hazard( 结构冒险 ) 现象 Time (clock cycles) Load Instr 1 Instr 2 Mem Reg Mem Reg Mem Reg Mem Reg Mem Reg Mem Reg Instr 3 Instr 4 Mem Reg Mem Reg Mem Reg Mem Reg 如果只有一个存储器, 则在 Load 指令取数据同时又取指令的话, 则发生冲突! 如果不对寄存器堆的写口和读口独立设置的话, 则发生冲突! 结构冒险也称为硬件资源冲突 : 同一个执行部件被多条指令使用 Pipeline.47

48 Structural Hazard 的解决方法 为了避免结构冒险, 规定流水线数据通路中功能部件的设置原则为 : 每个部件在特定的阶段被用!( 如 : 总在第三阶段被用!) 将 Instruction Memory (Im) 和 Data Memory (Dm) 分开将寄存器读口和写口独立开来 Time (clock cycles) I n s t r. O r d e r Load Instr 1 Instr 2 Instr 3 Instr 4 Im Reg Dm Reg Im Reg Dm Im Reg Dm Reg Im Reg BACK Reg Dm Reg Im Reg Dm Reg Pipeline.48

49 Data Hazard 现象 举例说明 : 以下指令序列中, 寄存器 r1 会发生数据冒险 add r1,r2,r3 sub r4, r1,r3 and r6, r1,r7 or r8, r1,r9 xor r10, r1,r11 想一下, 哪条指令的 r1 是老的值? 哪条是新的值? 读 r1 时,add 指令正在执行加法 (EXE), 老值! 读 r1 时,add 指令正在传递加法结果 (MEM), 老值! 读 r1 时,add 指令正在写加法结果到 r1(wb), 老值! 读 r1 时,add 指令已经把加法结果写到 r1, 新值 补充 : 三类数据冒险现象 画出流水线图能很清楚理解! RAW: 写后读 ( 基本流水线中经常发生, 如上例 ) WAR: 读后写 ( 基本流水线中不会发生, 多个功能部件时会发生 ) WAW: 写后写 ( 基本流水线中不会发生, 多个功能部件时会发生 ) 本讲介绍基本流水线, 所以仅考虑 RAW 冒险 Pipeline.49

50 Data Hazard on r1 Time (clock cycles) IF ID/RF EX MEM WB I n s t r. O r d e r add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11 Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg 最后一条指令的 r1 才是新的值! 如何解决这个问题? Pipeline.50

51 I n s t r. O r d e r 方案 1: 在硬件上采取措施, 使相关指令延迟执行 硬件上通过阻塞 (stall) 方式阻止后续指令执行, 延迟到有新值以后! 这种做法称为流水线阻塞, 也称为 气泡 Bubble Time (clock cycles) IF ID/RF EX MEM WB add r1,r2,r3 stall stall stall sub r4,r1,r3 Im Reg Dm Reg Im bubble bubble bubble bubble Im bubble bubble bubble bubble Im bubble bubble bubble bubble Im Reg Dm Reg and r6,r1,r7 Im Reg Dm 缺点 : 控制相当复杂, 需要改数据通路! Pipeline.51

52 方案 2: 软件上插入无关指令 最差的做法 : 由编译器插入三条 NOP 指令, 浪费三条指令的空间和时间 I n s t r. O r d e r Time (clock cycles) add r1,r2,r3 nop nop nop sub r4,r1,r3 IF ID/RF EX MEM WB Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg and r6,r1,r7 Im Reg Dm Pipeline.52

53 方案 3: 利用 DataPath 中的中间数据 仔细观察后发现 : 流水段寄存器中已有需要的值 r1! 在哪个流水段 R 中? I n s t r. O r d e r Time (clock cycles) IF ID/RF EX MEM WB add r1,r2,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 xor r10,r1,r11 Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg 1. 把数据从流水段寄存器中直接取到 的输入端 2. 寄存器写 / 读口分别在前 / 后半周期, 使写入被直接读出 BACK Pipeline.53 称为转发 (Forwading) 或旁路 (Bypassing)

54 硬件上的改动以支持 转发 技术 加 MUX, 使流水段寄存器值返送 输入端 假定流水段寄存器能读出新写入的值 ( 否则, 需要更多的转发数据 ) Ex Mem ID/EX EX/MEM MEM/WB M u x M u x Zero? add r3, r2, r1 Sub r5, r3, r4 Data Memory lw r3, 100(r1) Or r6, r2, r1 Sub r5, r3, r4 add r3, r2, r1 Or r6, r2, r1 如果指令序列为 : Pipeline.54 lw r3, 100(r1) Or r6, r3, r1 Sub r5, r3, r4 能用 转发 技术解决第 1 2 两条指令间的数据冒险吗? 请看后面的幻灯片! Sub r5, r3, r4

55 Clock 复习 : Load 指令引起的延迟现象 Cycle 1 Cycle 2 Cycle 3 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 I0: Load Ifetch Reg/Dec Exec Mem Wr Plus 1 Ifetch Reg/Dec Exec Mem Wr Plus 2 Ifetch Reg/Dec Exec Mem Wr Plus 3 Ifetch Reg/Dec Exec Mem Wr 若不采用转发, 则在何时才能用使用 Load 指令的结果? Plus 4 Ifetch Reg/Dec Exec Mem Wr Load 指令最早在哪个流水线寄存器中开始有后续指令需要的值? 实际上, 在第四周期结束时, 数据在流水段寄存器中已经有值 采用数据转发技术可以使 load 指令后面第二条指令得到所需的值但不能解决 load 指令和随后的第一条指令间的数据冒险, 要延迟执行一条指令! 这种 load 指令和随后指令间的数据冒险, 称为 装入 - 使用数据冒险 (load- use Data Hazard) BACK Pipeline.55

56 Forwarding 技术使 Load-use 冒险只需延迟一个周期 I n s t r. O r d e r Time (clock cycles) IF ID/RF EX MEM WB lw r1, 0(r2) sub r7,r1,r3 and r6,r1,r7 or r8,r1,r9 Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg 采用 转发 后仅第二条指令 SUB r7,r1,r3 不能按时执行! 需要阻塞一个周期 发生 装入 - 使用数据冒险 时, 需要对 load 后的指令阻塞一个时钟周期! Pipeline.56

57 方案 1: 硬件阻止指令执行来解决 load-use 用硬件阻塞一个周期 ( 指令被重复执行一次 ) I n s t r. O r d e r Time (clock cycles) lw r1, 0(r2) stall sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 IF ID/RF EX MEM WB Im Reg Dm Reg Im bubble bubble bubble bubble Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Pipeline.57

58 方案 2: 软件上插入 NOP 指令来解决 load-use 用软件插入一条 NOP 指令!( 有些处理器不支持硬件阻塞处理 ) 例如 :MIPS 1 处理器没有硬件阻塞处理, 而由编译器 ( 或汇编程序员 ) 来处理 I n s t r. O r d e r Time (clock cycles) lw r1, 0(r2) nop sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 IF ID/RF EX MEM WB Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Pipeline.58

59 方案 3: 编译器进行指令顺序调整来解决 load-use 以下源程序可生成两种不同的代码, 优化的代码可避免 Load 阻塞 a = b + c; d = e f; 假定 a, b, c, d,e, f 在内存 Slow code: lw $2, b lw $3, c add $1, $2, $3 sw a, $1 lw $5, e lw $6, f sub $4, $5, $6 sw d, $4 调整后 Fast code: lw $2, b lw $3, c lw $5, e add $1, $2, $3 lw $6, f sw a, $1 sub $4, $5, $6 sw d, $4 编译器的优化很重要! Pipeline.59

60 编译器优化以避免阻塞的情况调查 : scheduled unscheduled gcc spice tex 14% 25% 31% 42% 54% 65% 0% 20% 40% 60% 80% % loads stalling pipeline 由此可见, 优化调度后 load 阻塞现象大约降低了 1/2~1/3 Pipeline.60

61 数据冒险的解决方法 方法 1: 硬件阻塞 (stall) 方法 2: 软件插入 NOP 指令 方法 3: 编译优化 : 调整指令顺序, 能解决所有数据冒险吗? 方法 4: 合理实现寄存器堆的读 / 写操作, 能解决所有数据冒险吗? 前半时钟周期写, 后半时钟周期读 若同一个时钟内前面指令写入的数据正好是后面指令所读数据, 则不会发生数据冒险 方法 5: 转发 (Forwarding 或 Bypassing 旁路 ) 技术, 能解决所有数据冒险吗? - 若相关数据是 结果, 则如何? 可通过转发解决 - 若相关数据是上条指令 DM 读出内容, 则如何? 不能通过转发解决, 随后指令需被阻塞一个时钟或加 NOP 指令 称为 Load-use 数据冒险! 实现 转发 和 阻塞 要修改数据通路 : (1) 检测何时需要 转发, 并控制实现 转发 (2) 检测何时需要 阻塞, 并控制实现 阻塞 Pipeline.61

62 RAW( 写后读 ) 数据冒险的 转发 条件 ID/EX EX/MEM MEM/WB M u x M u x Ex Zero? C1 Mem ori r3, r2, 100 sub r5, r3, r4 Data Memory C3 lw r3, 100(r1) or r6, r2, r1 sub r5, r3, r4 C2 add r3, r2, r1 or r6, r2, r1 sub r5, r3, r4 后面指令需用 输出结果 C1: 目寄是后一条指令的源寄 C2: 目寄是后第二条指令的源寄 ( 例如 :R-Type 后跟 R- / lw / sw / beq 等 ) 后面指令需用从 DM 读出的结果 C3: 目寄是后第二指令的源寄 ( 例如 :load 指令后跟 R-Type / beq 等 ) Pipeline.62 用流水段寄存器来表示转发条件 (C3 以后考虑 ) C1(a): EX/MEM. RegisterRd=ID/EX. RegisterRs C1(b): EX/MEM. RegisterRd=ID/EX. RegisterRt C2(a): MEM/WB. RegisterRd=ID/EX. RegisterRs C2(b): MEM/WB. RegisterRd=ID/EX. RegisterRt 这里的 RegisterRd 是指目的寄存器实际上是 R-type 的 Rd 或 I-Type 的 rt

63 指令的回写 (Write Back) 阶段 Clk Ifetch Reg/Dec Exec Mem Wr RegWr=1 ExtOp Op Branch PC 1 0 PC+4 AIUnit I IF/ID: PC+4 Imm16 Rs Rt Ra Rb RFile Rt Rw Di Rd ID/Ex Register 0 1 PC+4 Imm16 busa busb Exec Unit Ex/Mem Register Zero Data Mem RA Do WA Di Mem/Wr Register 1 Mux 0 Rd 还是 Rt 取决于是 R- 型指令, 还是 I- 型指令! RegDst Src MemWr MemtoReg=1/0 若是 beq 指令会怎样? beq r3, r2, 100 sub r5, r3, r2 Pipeline.63 因为 beq 指令没有写结果, 不能进行转发!

64 转发条件的进一步完善 beq r3, r2, 100 以下两种情况下, 根据前面的转发条件转发会发生错误 sub r5, r3, r2 指令的结果不写入目的寄存器 Rd 时 - 例如,Beq 指令只对 rs 和 rt 相减, 不写结果到目的寄存器 - 即 :EX / MEM 或 MEM / WB 流水段寄存器的 RegWrite 信号为 0 Rd 等于 $0 时 - 例如, 指令 sll $0, $1, 2 的转发结果为 (R[$1]<<2), 但实际上应该是 0 因此, 修改转发条件为 : C1(a): EX/MEM.RegWrite and EX/MEM. RegisterRd 0 and EX/MEM. RegisterRd=ID/EX. RegisterRs C1(b): EX/MEM.RegWrite and EX/MEM. RegisterRd 0 and EX/MEM. RegisterRd=ID/EX. RegisterRt C2(a): MEM/WB.RegWrite and MEM/WB. RegisterRd 0 and MEM/WB. RegisterRd=ID/EX. RegisterRs C2(b): MEM/WB.RegWrite and MEM/WB. RegisterRd 0 and MEM/WB. RegisterRd=ID/EX. RegisterRt Pipeline.64

65 转发路径和转发条件 加 MUX, 使流水段寄存器值返送 输入端 Ex Mem ID/EX EX/MEM MEM/WB M u x M u x Zero? C1(a) Data Memory C1(b) C3 C2(a) C2(b) C1 反映的是本条指令和随后指令间的相关关系 C2 反映的是本条指令和随后第二条指令间的相关关系 C1(a) 和 C1(b) 可以合并为一个条件 C1, 并把转发线合一起后同时送 A 口和 B 口即 :C1=C1(a) or C1(b), 同样 :C2=C2(a) or C2(b), 转发线合起来实际上红线和兰线可以合并, 而且在原数据通路中是合并在一起的 记得吗? 由一个二路选择器 ( 控制端为 MemtoReg) 合并输出到寄存器堆! 所以不需另外有一个检测条件 C3! C1 和 C2 分别反映的是哪两条指令的相关关系呢? Pipeline.65

66 转发路径和转发条件 ForwardA (ForwardB) = 01 当 c2=1 时 10 当 c1=1 时 转发检测 部件中缺何条件? C1 C2 C1: EX/MEM.RegWrite and EX/MEM. RegisterRd 0 and (EX/MEM. RegisterRd=ID/EX. RegisterRs or EX/MEM. RegisterRd=ID/EX. RegisterRt C2: MEM/WB.RegWrite and MEM/WB. RegisterRd 0 and (MEM/WB. RegisterRd=ID/EX. RegisterRs or MEM/WB. RegisterRd=ID/EX. RegisterRt Pipeline.66

67 带转发的流水线数据通路 ForwardA (ForwardB) = 01 当 c2=1 时 10 当 c1=1 时 ForwardA ForwardB C1: EX/MEM.RegWrite and EX/MEM. RegisterRd 0 and (EX/MEM. RegisterRd=ID/EX. RegisterRs or EX/MEM. RegisterRd=ID/EX. RegisterRt C2: MEM/WB.RegWrite and MEM/WB. RegisterRd 0 Pipeline.67 and (MEM/WB. RegisterRd=ID/EX. RegisterRs or MEM/WB. RegisterRd=ID/EX. RegisterRt

68 更加复杂的数据冒险问题 考察以下指令序列, 采用前述转发条件会发生什么情况? add $1, $1, $2 01 当 c2=1 时 ForwardA (ForwardB) = add $1, $1, $3 10 当 c1=1 时 add $1, $1, $4 本条指令 对于左边的指令序列,C1 和 C2 的值各是什么? C1=C2=1, 使得 Forward 信号取值不确定! 可能会使转发到第 3 条指令的操作数是第 1 条指令结果, 而不是第 2 条指令的结果! 怎样改写 转发 检测条件 : 改 C1 还是改 C2? 应该让 C1=1,C2=0! 需要改写 转发 条件 C2 为 : MEM/WB.RegWrite and MEM/WB.RegisterRd 0 and (EX/MEM.RegisterRd ID/EX.RegisterRs or EX/MEM.RegisterRd ID/EX.RegisterRt) and (MEM/WB.RegisterRd=ID/EX.RegisterRs or MEM/WB.RegisterRd=ID/EX.RegisterRt) 上述公式相当于加了一个条件限制 : 如果本条指令源操作数和上条指令的目的寄存器一样, 则不转发上上条指令的结果, 而转发上条指令的结果 ( 即 : 此时的 C1=1 而 C2=0) 至此, 解决了 RAW 数据冒险的 转发 处理 BACK Pipeline.68

69 I n s t r. O r d e r Load-use Data Hazard( 硬件阻塞方式 ) Time (clock cycles) IF ID/RF EX MEM WB lw r1, 0(r2) sub r4,r1,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 检测点 Im Reg Dm Reg 阻塞点 Im Reg bubble bubble bubble Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg 需解决以下问题 : (1) 判断什么条件下需要阻塞 Pipeline.69 ID/EX.MemRead and (ID/EX.RegisterRt=IF/ID.RegisterRs or ID/EX.RegisterRt=IF/ID.RegisterRt) (2) 如何修改数据通路来实现阻塞 前面指令为 Load 并且前面指令的目的寄存器等于当前刚取出指令的源寄存器

70 Load-use Data Hazard( 硬件阻塞方式 ) I n s t r. O r d e r 阻塞前的情况 : lw r1, 0(r2) sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 Time (clock cycles) IF ID EX MEM WB 检测点阻塞点 Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg 检测 阻塞 过程中 : 1) sub 指令在 IF/ID 段寄存器中, 并正被译码 / 取数, 控制信号和 Rs/Rt 的值将被写到 ID/EX 段寄存器 2) and 指令地址在 PC 中, 正被取出, 取出的指令将被写到 IF/ID 段寄存器中在阻塞点, 必须将上述两条指令的执行结果清除, 并延迟一个周期执行这两条指令 延迟一个周期执行后面的指令, 相当于把阻塞点前面一个周期的状态再保持一个周期 lw 指令还是继续正常执行下去想想看, 如何做到继续保持状态? Pipeline.70

71 I n s t r. O r d e r Load-use Data Hazard( 硬件阻塞方式 ) 阻塞后的情况 : lw r1, 0(r2) sub r4,r1,r3 sub r4,r1,r3 and r6,r1,r7 or r8,r1,r9 检测点 Time (clock cycles) IF ID/RF EX MEM WB Im Reg Dm Reg 阻塞点 Im Reg bubble bubble bubble Im Reg Dm Reg Im Reg Dm Reg Im Reg Dm Reg 在阻塞点, 必须将上述两条指令的执行结果清除, 并延迟一个周期执行这两条指令 1 将 ID/EX 段寄存器中所有控制信号清 0 2 IF/ID 寄存器中的信息不变,sub 指令重新译码执行 3 PC 中的值不变,and 指令重新被取出执行 Pipeline.71

72 带 转发 和 阻塞 检测的流水线数据通路 写使能 信号为 0, 使 PC 和 IF/ID 不变 2 使控制信号清 0, 阻塞随后指令! 0 1 ID/EX.MemRead and (ID/EX.RegisterRt=IF/ID.RegisterRs or ID/EX.RegisterRt=IF/ID.RegisterRt) 3 至此, 数据冒险的处理全部完成! Pipeline.72 BACK

73 Control Hazard 的解决方法 方法 1: 硬件上阻塞 (stall) 分支指令后三条指令的执行 使后面三条指令清 0 或其操作信号清 0, 以插入三条 NOP 指令 方法 2: 软件上插入三条 NOP 指令 ( 以上两种方法的效率太低, 需结合分支预测进行 ) 方法 3: 分支预测 (Predict) 简单 ( 静态 ) 预测 : - 总是预测条件不满足 (not taken), 即 : 继续执行分支指令的后续指令 可加启发式规则 : 在特定情况下总是预测满足 (taken), 其他情况总是预测不满足 如 : 循环顶 ( 底 ) 部分支总是预测为不满足 ( 满足 ) 能达 65%-85% 的预测准确率 动态预测 : - 根据程序执行的历史情况, 进行动态预测调整, 能达 90% 的预测准确率注 : 采用分支预测方式时, 流水线控制必须确保错误预测指令的执行结果不能生效, 而且要能从正确的分支地址处重新启动流水线工作 方法 4: 延迟分支 (Delayed branch)( 通过编译程序优化指令顺序!) 把分支指令前面与分支指令无关的指令调到分支指令后面执行, 也称延迟转移 另一种控制冒险 : 异常或中断控制冒险的处理 Pipeline.73

74 简单 ( 静态 ) 分支预测方法 基本做法 总预测条件不满足 (not taken), 即 : 继续执行分支指令的后续指令可加启发式规则 : 在特定情况下总是预测满足 (taken), 其他情况总是预测不满足 预测失败时, 需把流水线中三条错误预测指令丢弃掉 - 将三条丢弃指令的控制信号值设置为 0, 使其后续过程中执行 nop 操作 ( 注 : 涉及到当时在 IF ID 和 EX 三个阶段的指令 ) 性能 如果转移概率是 50%, 则预测正确率仅有 50% 预测错误的代价 预测错误的代价与何时能确定是否转移有关 越早确定代价越少 可以把 是否转移 的确定工作提前, 而不要等到 MEM 阶段才确定 那最早可以提前到哪个阶段呢? SKIP Pipeline.74

75 复习 : Control Hazard 现象 Cycle 4 Cycle 5 Cycle 6 Cycle 7 Cycle 8 Cycle 9 Cycle 10 Cycle 11 Clk 12: Beq Ifetch Reg/Dec Exec Mem Wr (target is 1000) 16: R-type Ifetch Reg/Dec Exec Mem Wr 20: R-type Ifetch Reg/Dec Exec Mem Wr 24: R-type Ifetch Reg/Dec Exec Mem Wr 1000: Target of Br Ifetch Reg/Dec Exec Mem Wr 虽然 Beq 指令在第四周期取出, 但 : 是否转移 在 Mem 阶段确定, 目标地址在第七周期才被送到 PC 输入端 第八周期才取出目标地址处的指令执行结果 : 在取目标指令之前, 已有三条指令被取出, 取错了三条指令! 发生转移时, 要在流水线中清除 Beq 后面的三条指令, 分别在 EXE ID IF 段中 延迟损失时间片 C: 发生转移时, 给流水线带来的延迟损失 BACK 这里 C=3 Pipeline.75

76 简单 ( 静态 ) 分支预测方法 缩短分支延迟, 减少错误预测代价 可以通过调整 转移地址计算 和 分支条件判断 操作到 ID 阶段来缩短延迟 - 将转移地址生成从 MEM 阶段移到 ID 阶段, 可以吗? 为什么? ( 是可能的 :IF/ID 流水段寄存器中已经有 PC 的值和立即数 ) - 将 判 0 操作从 EX 阶段移到 ID 阶段, 可以吗? 为什么? ( 用逻辑运算 ( 如, 先按位异或, 再结果各位相或 ) 来直接比较 Rs 和 Rt 的值 ) ( 简单判断用逻辑运算, 复杂判断可以用专门指令生成条件码 ) ( 许多条件判断都很简单 ) 预测错误的检测和处理 ( 称为 冲刷 冲洗 --Flush) 当 Branch=1 并且 Zero=1 时, 发生转移 (taken) 增加控制信号 :IF.Flush=Branch and Zero, 取值为 1 时, 说明预测失败 预测失败 ( 条件满足 ) 时, 完成以下两件事 ( 延迟损失时间片 C=1 时 ): 1 将转移目标地址 ->PC 2 清除 IF 段中取出的指令, 即 : 将 IF/ID 中的指令字清 0, 转变为 nop 指令 原来要清除三条指令, 调整后只需要清除一条指令, 因而只延迟一个时钟周期, 每次预测错误减少了两个周期的代价! Pipeline.76

77 带静态分支预测处理的数据通路 IF.Flush=Branch and Zero 40# 指令 beq $1,$3, 7 的 ID 阶段 sub $3, $5, $1 add $1, $5, $2 beq $1, $3, 7 转移目标地址 (72)->PC 控制转移目标地址 ->PC 将 IF/ID 中指令字清 0, 变为 nop 指令 若 $1 或 $3 和前面指令数据相关, 会怎么样? 上上条指令的 EXE 段结果可转发回来进行判断 Pipeline.77 上条指令的 EXE 段结果来不及转发回来, 引起 1 次阻塞! 需重新改 转发 条件和转发线路! 作业中有相应的练习 BACK

78 动态分支预测方法 简单的静态分支预测方法的预测成功率不高, 应考虑动态预测 动态预测基本思想 : 利用最近转移发生的情况, 来预测下一次可能发生的转移 预测后, 在实际发生时验证并调整预测 转移发生的历史情况记录在 BHT 中 ( 有多个不同的名称 ) - 分支历史记录表 BHT(Branch History Table) - 分支预测缓冲 BPB(Branch Prediction Buffer) - 分支目标缓冲 BTB(Branch Target Buffer) 每个表项由分支指令地址的低位索引, 故在 IF 阶段就可以取到预测位 - 低位地址相同的分支指令共享一个表项, 所以, 可能取的是其他分支指令的预测位 会不会有问题? - 由于仅用于预测, 所以不影响执行结果 现在几乎所有的处理器都采用动态预测 (dynamic predictor) Pipeline.78

79 分支历史记录表 BHT( 或 BTB BPB) 分支指令地址 =? 分支指令地址 分支历史记录表 BHT 预测位 转移目标地址 1 查找 转移取 顺序取 查找时发现都不相等, 则 未命中 未命中说明什么? 说明以前没有执行过该分支指令 加入新项 命中与否 4 修正 控制逻辑 2 预测 命中时 : 根据预测位, 选择 转移取 还是 顺序取 未命中时 : 加入新项, 并填入指令地址和转移目标地址 初始化预测位 3 选择 实际执行情况 指令预取器 指令执行 Pipeline.79

80 动态预测基本方法 采用一位预测位 : 总是按上次实际发生的情况来预测下次 1 表示最近一次发生过转移 (taken),0 表示未发生 (not taken) 预测时, 若为 1, 则预测下次 taken, 若为 0, 则预测下次 not taken 实际执行时, 若预测错, 则该位取反, 否则, 该位不变 可用一个简单的预测状态图表示 缺点 : 当连续两次的分支情况发生改变时, 预测错误 - 例如, 循环迭代分支时, 第一次和最后一次会发生预测错误, 因为循环的第一次和最后一次都会改变分支情况, 而在循环中间的各次总是会发生分支, 按上次的实际情况预测时, 都不会错 采用二位预测位 用 2 位组合四种情况来表示预测和实际转移情况 按照预测状态图进行预测和调整 在连续两次分支发生不同时, 只会有一次预测错误 采用比较多的是二位预测位, 也有采用二位以上预测位 如 :Pentium 4 的 BTB2 采用 4 位预测位 BACK Pipeline.80

81 一位预测状态图 发生 正确 不发生错误 不发生 预测发生预测不发生 1 0 发生错误 正确 Loop: g = g +A[i]; i = i+ j; if (i!= h) go to Loop: Assuming variables g, h, i, j ~ $1, $2, $3, $4 and base address of array is in $5 指令预取时, 按照预测读取相应分支的指令 预测发生时, 选择 转移取 预测不发生时, 选择 顺序取 指令执行时, 按实际执行结果修改预测位 对照状态转换图来进行修改 例如 : 对于一个循环分支 若初始状态为 0( 再次循环时为 0), 则第一次和最后一次都错 若初始状态为 1, 则只有最后一次会错 即 : 只要本次和上次的发生情况不同, 就会出现一次预测错误 Loop: add $7, $3, $3 ; i*2 add $7, $7, $7 ; i*4 add $7, $7, $5 lw $6, 0($7) ; $6=A[i] add $1, $1, $6 ; g= g+a[i] add $3, $3, $4 bne $3, $2, Loop BACK Pipeline.81

82 两位预测状态图 发生正确不发生错误预测发生预测发生 发生正确发生错误不发生错误不发生正确预测不发生预测不发生 发生错误不发生正确 Loop: add $7, $3, $3 ; i*2 add $7, $7, $7 ; i*4 add $7, $7, $5 lw $6, 0($7) ; $6=A[i] add $1, $1, $6 ; g= g+a[i] add $3, $3, $4 bne $3, $2, Loop 预测发生时, 选择 转移取 预测不发生时, 选择 顺序取 基本思想 : 只有两次预测错误才改变预测方向 00 状态时预测发生 ( 强转移 ), 实际不发生时, 转到状态 01( 弱转移 ), 下次仍预测为发生, 如果再次预测错误 ( 实际不发生 ), 才使下次预测调整为不发生 11 好处 : 连续两次发生不同的分支情况时, 可能会预测正确 例如, 对于循环分支的预测 - 第一次 : 初始态为 00( 再次循环时状态为 01), 预测发生, 实际也发生, 正确 - 中间 : 状态为 00, 预测发生, 实际也发生, 正确 - 最后一次 : 状态为 00, 预测发生, 但实际不发生, 错 Pipeline.82 BACK

83 分支延迟时间片的调度 属于静态调度技术, 由编译程序重排指令顺序来实现 基本思想 : 把分支指令前面的与分支指令无关的指令调到分支指令后面执行, 以填充延迟时间片 ( 也称分支延迟槽 Branch Delay slot), 不够时用 nop 操作填充 举例 : 如何对以下程序段进行分支延迟调度? ( 假定时间片为 2) lw $1, 0($2) lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 add $3, $3,$2 sw $1, 0($2) 调度后 若分支条件判断和目标地址计算提前到 ID 阶段, 则分支延迟时间片减少为 1 lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 lw $1, 0($2) nop add $3, $3,$2 sw $1, 0($2) lw $3, 0($2) add $6, $4, $2 beq $3, $5, 2 lw $1, 0($2) add $3, $3,$2 sw $1, 0($2) 调度后可能带来其他问题 : 产生新的 load-use 数据冒险 Pipeline.83 调度后, 降低了分支延迟损失 BACK

84 另一种控制冒险 : 异常和中断 异常和中断会改变程序的执行流程 某条指令发现异常时, 后面多条指令已被取到流水线中正在执行 例如 指令发现 溢出 时, 已经到 EX 阶段结束了, 此时, 它后面已有两条指令进入流水线了 流水线数据通路如何处理异常? ( 举例说明 ) 假设指令 add r1,r2,r3 产生了溢出 ( 记住 :MIPS 异常处理程序的首地址为 0x ) 处理思路 : 清除 add 指令以及后面的所有已在流水线中的指令 保存 PC 或 PC+4 到 EPC 从 0x 处开始取指令 Pipeline.84

85 异常的处理 异常 ( 溢出 ) 在第一条指令的 EXE 阶段被检出 Time (clock cycles) I IF ID/RF EX MEM WB n add r1,r2,r3 Im Reg bubble bubble bubble s t r. sub r4,r2,r3 Im Reg bubble bubble bubble O r d e r and r6,r1,r4 异常处理程序首指令 即 :0x 处指令 阻塞点 Im 不会!EX.Flush 使 EXE 段指令的控制信号清 0( 主要保证 RegWr 清 0), 避免了在 WB 阶段写寄存器 r1 的情况 bubble bubble bubble bubble Im Reg 异常处理 : IF.Flush 使 IF 段指令在 IF/ID 寄存器中清为 0, 变成 nop 指令 ID.Flush 与数据冒险阻塞检测信号相或 (or) 后, 使 ID 段指令的控制信号清 0 EX.Flush 使 EX 段指令的控制信号清 0 Dm Im Reg Dm Reg 将 0x 作为 PC 的一个输入, 并控制 PC 输入端的多路选择器会发生将溢出结果写到寄将断点 ( 可能是 PC 可能是 PC+4) 保存到 EPC 中存器 r1 中去的情况吗? Pipeline.85

86 带异常处理的流水线数据通路 Overflow H Pipeline.86

87 流水线方式下的异常处理的难点问题 流水线中有 5 条指令, 到底是哪一条发生异常? 根据异常发生的流水段可确定是哪条指令, 因为各类异常发生的流水段不同 溢出 在 EXE 段检出 无效指令 在 ID 段检出 除数为 0 在 ID 段段检出 无效指令地址 在 IF 段检出 无效数据地址 在 Load/Store 指令的 EXE 段检出 外部中断与特定指令无关, 如何确定处理点? 可在 IF 段或 WB 段中进行中断查询, 需要保证当前 WB 段的指令能正确完成, 并在有中断发生时, 确保下个时钟开始执行中断服务程序 检测到异常时, 指令已经取出多条, 当前 PC 的值已不是断点, 怎么办? 指令地址 ( 哪条?) 存放在流水段 R, 可把这个地址送到 EPC 保存, 以实现精确中断 ( 非精确中断不能提供准确的断点, 而由操作系统来确定哪条指令发生了异常 ) 一个时钟周期内可能有多个异常, 该先处理哪个? 异常 : 检出异常存到专门寄存器,( 前面指令优先级高?) 中断 : 在中断查询程序或中断优先级排队电路中按顺序查询 系统中只有一个 EPC, 多个中断发生时, 一个 EPC 不够放多个断点, 怎么办? 总是把优先级最高的送到 EPC 中 在异常处理过程中, 又发生了新的异常或中断, 怎么办? 利用中断屏蔽和中断嵌套机制来处理后面三个问题在第九章中详细介绍! Pipeline.87

88 复习 :Cache 的操作过程 如果被访问的信息不在 cache 中, 称为失效 (miss) 硬件如何进行缺失处理? 缺失处理 如果被访问的信息在 cache 中, 称为命中 (hit) Pipeline.88

89 Cache 缺失处理会引起流水线阻塞 ( 停顿 ) 在使用 Cache 的系统中, 数据通路中的 IM 和 DM 分别是 Code Cache 和 Data Cache CPU 执行指令过程中, 取指令或取数据时, 如果发生缺失, 则指令执行被阻塞 Cache 缺失的检测 ( 如何进行的? 记得吗?) Cache 中有相应的检测线路 ( 地址高位与 Cache 标志比较 ) 阻塞处理过程 冻结所有临时寄存器和程序员可见寄存器的内容 ( 即 : 使整个计算机阻塞 ) 由一个单独的控制器处理 Cache 缺失, 其过程 ( 假定是指令缺失 ) 还记得吗?: - 把发生缺失的指令地址 (PC- 4) 所在的主存块首址送到主存 - 启动一次 主存块读 操作, 并等待主存完成一个主存块 (Cache 行 ) 的读操作 - 把读出的一个主存块写到 Cache 对应表项的数据区 ( 若对应表项全满的话, 还要考虑淘汰掉一个已在 Cache 中的主存块 ) - 把地址高位部分 ( 标记 ) 写到 Cache 的 tag 字段, 并置 有效位 - 重新执行指令的第一步 : 取指令 若是读数据缺失, 其处理过程和指令缺失类似 - 从主存读出数据后, 从 取数 那一步开始重新执行就可以了 若是写数据缺失, 则要考虑用哪种 写策略 解决 一致性 问题 比数据相关或分支指令引起的流水线阻塞简单 : 只要保持所有寄存器不变 与中断引起的阻塞处理不同 : 不需要程序切换 Pipeline.89

90 TLB 缺失和缺页也会引起流水线阻塞 TLB 缺失处理 当 TLB 中没有一项的虚页号与要找的虚页号相等时, 发生 TLB miss TLB miss 说明可能发生以下两种情况之一 : - 页在内存中 : 只要把主存中的页表项装载到 TLB 中 - 页不在内存中 ( 缺页 ):OS 从磁盘调入一页, 并更新主存页表和 TLB 缺页 (page fault) 处理 当主存页表的页表项中 valid 位为 0 时, 发生 page fault Page fault 是一种 故障 异常, 按以下过程处理 (MIPS 异常处理 ) - 在 Cause 寄存器置相应位为 1 - 发生缺页的指令地址 (PC- 4) 送 EPC - 0x ( 异常查询程序入口 ) 送 PC 执行 OS 的异常查询程序, 取出 Cause 寄存器中相应的位分析, 得知发生了 缺页, 转到 缺页处理程序 执行 page fault 一定要在发生缺失的存储器操作时钟周期内捕获到, 并在下个时钟转到异常处理, 否则, 会发生错误 - 例 :lw $1, 0($1), 若没有及时捕获 异常 而使 $1 改变, 则再重新执行该指令时, 所读的内存单元地址被改变, 发生严重错误! 处理 Cache 缺失和缺页的不同之处在哪里? 哪种要进行程序切换? Pipeline.90

91 ( 缺页 ) 异常处理时要考虑的一些细节 缺页异常结束后, 回到哪里继续执行? 指令缺页 : 重新执行发生缺页的指令 数据缺页 : - 简单指令 ( 仅一次访存 ): 强迫指令结束, 重新执行缺页指令 - 复杂指令 ( 多次访存 ): 可能会发生多次缺页, 指令被中止在中间某个阶段, 缺页处理后, 从中间阶段继续执行 ; 因而, 需要能够保存和恢复中间机器状态 异常发生后, 又发生新的异常, 怎么办? 在发现异常 转到异常处理程序中, 若在保存正在运行进程的状态时又发生新的异常, 则因为要处理新的异常, 会把原来进程的状态和保存的返回断点破坏掉, 所以, 应该有一种机制来 禁止 响应新的异常处理 (?) 通过 中断 / 异常允许 状态位 ( 或 中断 / 异常允许 触发器 ) 来实现? 中断 / 异常允许 状态位置 1, 则 开中断 ( 允许异常 ), 清 0 则 关中断 ( 禁止异常 )? OS 通过管态指令来设置该位的状态? Pipeline.91

92 三种处理器实现方式的比较 单周期 多周期 流水线三种方式比较假设各主要功能单元的操作时间为 : 存储单元 :200ps 和加法器 :100ps 寄存器堆 ( 读 / 写 ):50ps 假设 MUX 控制单元 PC 扩展器和传输线路都没有延迟, 指令组成为 : 25% 取数 10% 存数 52% 11% 分支 2% 跳转则下面实现方式中, 哪个更快? 快多少? (1) 单周期方式 : 每条指令在一个固定长度的时钟周期内完成 (2) 多周期方式 : 每类指令时钟数 : 取数 -5, 存数 -4,-4, 分支 -3, 跳转 -3 (3) 流水线方式 : 每条指令分取指令 取数 / 译码 执行 存储器存取 写回五阶段 ( 假定没有结构冒险, 数据冒险采用转发处理, 分支延迟槽为 1, 预测准确率为 75%; 不考虑异常 中断和访问缺失引起的流水线冒险 ) Pipeline.92

93 三种处理器实现方式的比较 解 :CPU 执行时间 = 指令条数 x CPI x 时钟周期长度三种方式的指令条数都一样, 所以只要比较 CPI 和时钟周期长度即可 各指令类型要求的时间长度为 : Pipeline.93

94 三种处理器实现方式的比较 对于单周期方式 : 时钟周期将由最长指令来决定, 应该是 load 指令, 为 600ps 所以,N 条指令的执行时间为 600N(ps) 对于多周期方式 : 时钟周期将取功能部件最长所需时间, 应该是存取操作, 为 200ps 根据各类指令的频度, 计算平均时钟周期数为 : CPU 时钟周期 =5x25%+4x10%+4x52%+3x11%+3x2%=4.12 所以, N 条指令的执行时间为 4.12x200xN=824N(ps) 对于流水线方式 : Load 指令 : 当发生 Load-use 依赖时, 执行时间为 2 个时钟, 否则 1 个时钟, 故平均执行时间为 1.5 个时钟 ; Store 指令 :1 个时钟 ; Branch 指令 : 预测成功时,1 个时钟, 预测错误时,2 个时钟, 所以 : 平均约为 :.75x1+.25x2=1.25 个 ; Jump 指令 :2 个时钟 ( 总要等到译码阶段结束才能得到转移地址 ) 平均 CPI 为 :1.5x25%+1x10%+1x52%+1.25x11%+2x2%=1.17 所以, N 条指令的执行时间为 1.17x200xN=234N(ps) Pipeline.94

95 流水线冒险对程序性能的影响 结构冒险对浮点运算的性能影响较大, 因为浮点运算单元不能有效被流水化, 可能造成运算单元的资源冲突 控制冒险更多出现在整数运算程序中, 因为分支指令对应于循环或选择结构, 大多由整数运算结果决定分支 数据冒险在整数运算程序和浮点运算程序中都一样 浮点程序中的数据冒险容易通过编译器优化调度来解决 - 分支指令少 - 数据访问模式较规则 整数程序的数据冒险不容易通过编译优化调度解决 - 分支指令多 - 数据访问模式不规则 - 过多使用指针 Pipeline.95

96 第二讲小结 流水线冒险的几种类型 : 资源冲突 数据相关 控制相关 ( 改变指令流的执行方向 ) 数据冒险的现象和对策 数据冒险的种类 - 相关的数据是 结果, 可以通过转发解决 - 相关的数据是 DM 读出的内容, 随后的指令需被阻塞一个时钟 数据冒险和转发 - 转发检测 / 转发控制 数据冒险和阻塞 - 阻塞检测 / 阻塞控制 控制冒险的现象和对策 静态分支预测技术 缩短分支延迟技术 动态分支预测技术 异常和中断是一种特殊的控制冒险 访存缺失 (Cache 缺失 TLB 缺失 缺页 ) 会引起流水线阻塞 Pipeline.96

97 Pipeline.97 第三讲高级流水线技术 高性能流水线 - 指令级并行 (ILP) 技术 超流水线 多发射流水线 - 静态多发射 (VLIW 处理器 + 编译器静态调度 ) - 动态多发射 ( 超标量处理器 + 动态流水线调度 ) 静态多发射 (VLIW- 超长指令字 ) 编译器静态推测完成 指令打包 和 冒险处理 MIPS 2- 发射流水线数据通路 循环展开指令调度 IA-64 的 EPIC 技术 动态多发射 动态多发射流水线的通用模型 动态多发射流水线的执行模式 - 按序发射 按序完成 - 按序发射 无序完成 - 无序发射 无序完成 Pentium 4 动态多发射流水线 - 超流水 超标量 动态调度 无序发射 无序完成

98 提高性能措施 实现指令级并行 流水线实现了指令流内部的并行, 这种并行称为指令级并行 (ILP) 有两种指令级并行策略 超流水线 (Super- pipelining) - 级数更多的流水线 CPI=? CPI=1 - 理想情况下, 流水线的加速比与流水段的数目成正比 ( 即 : 理想情况下, 流水段越多, 时钟周期越短, 指令吞吐率越高 ) 但是, 它是有极限的! 可以怎样突破极限呢? 多发射流水线 (Multiple issue pipelining ) - 多条指令 ( 如整数运算 浮点运算 装入 / 存储等 ) 同时启动并独立运行 - 前提 : 有多个执行部件 如 : 定点 浮点 乘 / 除 取数 / 存数部件等 - 结果 : 能达到小于 1 的 CPI, 定义 CPI 的倒数为 IPC ( 例如 : 四路多发射流水线的理想 IPC 为 4) - 需要实现以下两个主要任务 指令打包 : 分析每个周期发射多少条? 哪些指令可以同时发射? 冒险处理 : 由编译器静态调整指令或在运行时由硬件处理 - 实现上述两个主要任务的基础 推测技术 - 两种实现方法 静态多发射 : 由编译器在编译时静态完成指令打包或冒险处理 动态多发射 : 由硬件在执行时动态完成指令打包或冒险处理 Pipeline.98

99 实现多发射技术的基础 推测 推测技术 : 由编译器或处理器猜测指令执行结果, 并以此来调整指令执行顺序, 使指令的执行能达到最大可能的并行 指令打包的决策依赖于 推测 的结果 - 可根据指令间的相关性来进行推测 与前面指令不相关的指令可以提前执行 - 可对分支指令进行推测 可提前执行分支目标处的指令 - 预测仅是 猜测, 有可能推测错误, 故需有推测错误检测和回滚机制 - 推测错误时, 会增加额外开销 有 软件推测 和 硬件推测 两种 - 软件推测 : 编译器通过推测来静态重排指令 ( 一定要正确!) - 硬件推测 : 处理器在运行时通过推测来动态调度指令 BACK Pipeline.99

100 静态多发射处理器 由编译器在编译时, 进行相关性分析和静态分支预测, 以静态完成 指令打包 或 冒险处理 指令打包 ( 将同时发射的多条指令合并到一个长指令中 ) - 将一个周期内发射的多个指令看成一条多个操作的长指令, 称为一个 发射包 - 静态多发射 最初被称为 超长指令字 (VLIW-Very Long Instruction Word), 采用这种技术的处理器被称为 VLIW 处理器 - 在同一个周期内发射的指令类型是受限制的 ( 例如, 只能是一条 指令 / 分支指令 一条 Load/Store 指令 ) - IA-64 采用这种方法,Intel 称其为 EPIC(Explicitly Parallel Instruction Computer 显式并行指令计算机 ) 冒险处理 ( 主要是数据冒险和控制冒险 ) - 做法 1: 完全由编译器通过代码调度和插入 nop 指令来消除所有冒险, 无需硬件实现冒险检测和流水线阻塞 - 做法 2: 由编译器通过静态分支预测和代码调度来消除同时发射指令间内部依赖, 由硬件检测数据冒险并进行流水线阻塞即 : 保证打包指令内部不会出现冒险! Pipeline.100

101 静态多发射处理器实例 实例 :MIPS ISA 指令集的静态多发射 发射处理器 Pipeline.101 要使原来的 MIPS 处理器能够同时处理两条流水线, 数据通路需要做哪些改进? 1. 同时要能取并译码两条指令, 怎么办? 将两条指令打包成 64 位长指令, 前面为 /Branch, 后面为 lw/sw 没有配对指令时, 就用 nop 指令代替 将 64 位长指令中的两个操作码同时送到控制器 ( 指令译码器 ) 进行译码 2. 两条指令同时要读两个寄存器 ( 和 sw 配对时 ) 或写寄存器 ( 和 lw 配对时 ), 怎么办? 增加一个读口和一个写口 3. 两条指令同时要使用 进行运算, 怎么办? BACK 增加一个 ( 包括 2 组输入总线和 1 组输出总线 )

102 2 发射流水线数据通路 ( 蓝色是增加部分 ) 需增加额外加法器或 / 分支指令进行 运算时, Load/Store 指令要计算地址 指令成对放在 64 位对齐内存区域, 前面是 / 分支指令 如果不能成对, 则用 nop 指令代替缺失指令, 每次取两条指令, 同时对两条指令译码 同时需为 和 Store 操作读两个寄存器, 同时需为 运算和 Load 结果写一个寄存器 Pipeline.102 控制器和控制信号会要求数据通路怎样改呢? 流水段寄存器要增宽, 控制信号分别传送

103 2 发射流水线的特点 优点 : 潜在性能将提高大约 2 倍 ( 实际上达不到!) 缺点 : 为消除结构冒险, 需增加额外部件 增加潜在的由数据冒险和控制冒险导致的性能损失 - 例 1: 对于 Load-use 数据冒险 单发射流水线 : 只有一条指令延迟 2 发射流水线 : 有一个周期 (2 条指令 ) 延迟 - 例 2: 对于 -Load/Store 数据冒险 单发射流水线 : 可用 转发 技术使 结果直接转发到 Load/Store 指令的 EXE 阶段 2 发射流水线 : 两条指令同时进行, 的结果不能直接转发, 因而不能提供给与其配对的 Load/Store 指令使用, 只能延迟一个周期 为了更有效地利用多发射处理器的并行性, 必须有更强大的编译器, 能够充分消除指令间的依赖关系, 使指令序列达到最大的并行性! Pipeline.103

104 例 :2 发射 MIPS 指令调度 前三条和后两条各具有相关性 以下是一个循环代码段可把第四条指令调到第一条后面 Loop: lw $t0, 0($s1) sw 指令是否有问题? 怎么办? addu $t0, $t0, $s2 $s1 被减 4, 故 sw 指令偏移改为 4 sw $t0, 0($s1) 能否把 addi 和 lw 配成一对? addi $s1, $s1, -4 冒险! 同时对同一个寄存器读, 且 bne $s1, $zero, Loop 读后要写, 取决于寄存器如何设计 ( 能看出这段程序的功能吗?) 循环内进行的是数组访问! 为了能在 2 发射 MIPS 流水线中有效执行, 该怎样重新排列指令 调度方案如下 : 没有指令配对时, 用 nop 指令代替 一个循环内, 五条指令在四个时钟内完成, 实际 CPI 为 0.8, 即 : IPC=1.25 在循环中访问数组的更好的调度技术是 循环展开 Pipeline.104

105 用 循环展开 技术进行指令调度 基本思想 : 展开循环体, 生成多个副本, 在展开的指令中统筹调度 上例采用 循环展开 后的指令序列是什么? 为简化起见, 假定循环执行次数是 4 的倍数 循环展开 4 次后循环内每条指令 (lw, addu, sw, 与数组访问相关 ) 有 4 条再加上 1 条 addi 和 1 条 bne, 共 14 条指令 指令最佳调度序列如下 : 为何第一条指令将 $s1 减 16? 与 $t0 关联的指令偏移为何不同? 14 条指令用了 8 个时钟,CPI 达到 8/14=0.57 好处 : 充分利用并行, 并消除部分循环分支! 需要用到 重命名寄存器 技术, 多用了三个临时寄存器 $t1,$t2,$t3, 消除了名字依赖关系 ( 非真实依赖, 只是寄存器名相同而已 ) 代价是什么? 多用了三个临时寄存器, 并增加了代码大小 ( 存储空间变大 ) Pipeline.105

106 循环展开后的偏移量 第一条指令将 $s1 减 16, 使指令执行后,$s1 的值变成了循环结束时 $s1 的值 所以循环体内各数组元素的访问指令的偏移量依次为 : 16 - 数组元素 1,12 - 数组元素 2,8 - 数组元素 3,4 - 数组元素 4 $s1-16 $s1 Pipeline.106 数组元素 4 数组元素 3 数组元素 2 数组元素 1 为什么第一个周期中的 lw 指令的偏移量为 0? 因为第一个周期中的 lw 指令进行地址计算时, addi 指令的执行结果还没有写到 $s1 中, 所以, 此时 $s1 中还是原来的值? 为什么第一条 addu 指令不放在第二周期? 为了避免 load-use 数据冒险! 当循环次数不是 4 的倍数时, 这样做就有问题! 可见 : 编译器和机器结构密切相关! 系统程序员必须非常了解机器结构! 编译器的好坏直接影响机器的性能!

107 Pipeline.107 实例 :Intel IA-64 架构 IA-64 类似于 64 位 MIPS 架构, 是 Register-Register 型的 RISC 风格指令集 但有独特性 : 要求编译器显式地给出指令级的并行性,Intel 称其为 EPIC Explicitly Parallel Instruction Computer 显式并行指令计算机 与 MIPS-64 架构的区别 更多寄存器 :128 个整数 128 个浮点数 8 个专用分支 64 个 1 位谓词 支持寄存器窗口重叠技术 同时发射的指令组织在指令包 (bundle) 中 引入特殊的谓词化技术, 以支持推测执行和消除分支, 提高指令级并行度 EPIC 的实现技术 指令组 (Instruction Group): 相互间没有寄存器级数据依赖的指令序列 - 指令组长度任意, 用 停止标记 在指令组之间明显标识 - 指令组内部的所有指令可并行执行, 只要有足够硬件且无内存操作依赖 指令包 : 同时发射的指令重新编码并形成指令包 - 长度为 128, 由 5 位长的模板字段 三个 41 位长的指令组成 - 模板字段对应于以下五类功能部件中的三条指令 整数 非整数 ( 移位和多媒体 ) 访存 浮点 分支 谓词化 : 将指令的执行与谓词相关联, 而不是与分支指令关联 Intel IA-64 是?- 发射流水线? 3- 发射流水线! BACK

108 RISC 的通用寄存器 RISC 机采用大量寄存器 其目的 : 减少程序访问存储器的次数 RISC 机寄存器的组织方式有两种 : 重叠寄存器窗口技术 ORW( 硬件方法 ) - 执行过程调用和返回时, 利用寄存器组而不是存储器来完成参数传递 - 通过重叠窗口技术, 使得不再需要保存和恢复寄存器内容 - 可大大提高了程序执行的速度 优化寄存器分配技术 ( 软件方法 ) - 规定一套寄存器分配算法 - 通过编译程序的优化处理来充分利用寄存器资源 - 编译器为那些在一定的时间内使用最多的变量分配寄存器 BACK Pipeline.108

109 重叠寄存器窗口技术 (Overlapped Register Window ) 用于保存局部数据 寄存器分为两类 : 全局寄存器 : 所有过程共享窗口寄存器 : 用于过程调用 与被调用子过程的输入寄存器重叠 与调用自己的父过程的输出寄存器重叠 A 调用 B 时, 由于各自使用不同的局部寄存器, 所以不需保存现场 A 过程的输出寄存器可直接把参数送给 B 从 B 返回时,B 将返回结果送到其输入寄存器,A 可直接得到 B 返回的结果 BACK Pipeline.109

110 Intel IA-64 架构的谓词和推测执行技术 谓词和谓词寄存器 分支指令中的条件称为谓词 每个谓词与一个谓词寄存器相关联 每条指令都可与最后 6 位标识 (64 个一位谓词, 故谓词寄存器的标号用 6 位表示 ) 的谓词寄存器相关联, 反映条件是否满足 可消除循环内 if-then-else 分支 ( 循环分支可由循环展开部分消除 ) 例 :if (p) { Statement1 } else { Statement2 } 被编译成 : (p) Statement1 (~p) Statement2 括号中的条件为 1 时, 执行后面的代码, 否则, 转化为 nop 指令 条件分支指令被转化为由谓词寄存器关联的指令, 消除了分支 通过谓词寄存器可实现指令的推测执行 IA-64 是采用静态多发射机制的最复杂指令集, 对编译器的要求极高 BACK Pipeline.110

111 Pipeline.111 动态多发射处理器 由硬件在执行时动态完成指令打包或冒险处理 通常被称为超标量处理器 (Superscalar) 在一个周期内执行一条以上指令 与 VLIW 处理器的不同点 : VLIW 处理器 : 编译结果与机器结构密切相关, 结构有差异的机器上要重新编译 超标量处理器 : 编译器仅进行指令顺序调整, 但不进行指令打包, 由硬件根据机器的结构来决定一个周期发射哪几条指令 因此, 编译后的代码能够被不同结构的机器正确执行 多数超标量处理器都结合动态流水线调度 (Dynamic pipeline scheduling) 技术 通过指令相关性检测和动态分支预测等手段, 投机性地不按指令顺序执行, 当发生流水线阻塞时, 可以到后面找指令来执行 举例说明动态流水线调度技术 : 左边指令序列中, 哪条指令可以提前执行? sub 指令可以提前执行, 不需等 lw 和 addu 指令执行完 如果不将 sub 调到前面, 可能要等很长时间 (lw 指令的访存操作耗时较长!), 从而影响 slti 指令的执行 最佳的方案是什么? SKIP

112 动态流水线调度的通用模型 动态流水线的一个重要的思想 : 在等待解决阻塞时, 到后面找指令提前执行! 动态流水线的通用模型 : 一个指令预取和译码单元 : 有序发射 多个并列执行的功能单元 : 乱序执行 一个提交单元 : 有序提交 每个功能单元有各自的保留站用于保存操作数和操作命令 功能单元一旦完成, 则将结果同时送其他等待该结果的保留站和提交单元 提交单元缓存所有完成的指令结果, 直到该结果能安全写回到寄存器或存储器, 称为 Reorder Buffer Pipeline.112 指令的结果也可在 Reorder Buffer 中被 转发

113 功能单元的性能 功能 : 用来执行特定类型的操作 性能 : 每个功能单元具有基本的操作性能, 用两个周期数来刻画 执行周期 (Latency): 完成特定操作所花的周期数 发射时间 (Issue Time): 连续 独立操作之间的最短周期数以下是 Pentium III 算术功能部件的性能 从上述图中看出, 哪些功能部件是流水化的? 哪些是非流水化的? 整数加 整数乘 浮点加 装入 存储这五种部件是流水化的 浮点乘部件是部分流水化 整数除和浮点除是完全没有流水化 CPU 设计的一个原则 : 有限的芯片空间应该在各功能部件之间进行平衡! 尽量让大多数资源用于最关键的操作 ( 对大量基准程序进行评估 ) 从上述图中能否看出 : 哪些是最重要的操作? 哪些是不常用的? 整数加法和乘法 浮点数加法和乘法是重要的操作除法相对来说不太常用, 而且本身难以实现流水线 Pipeline.113

114 动态流水线的几种执行模式 根据动态流水线指令发射和完成顺序, 可分为三种执行模式 : 按序发射按序完成 (Pentium) 按序发射无序完成 (Pentium II 和 Pentium III) 无序发射无序完成 (Pentium 4) ReOrder Buffer 重排序缓冲 : 用于保存已完成的指令结果, 等待在可能时写回寄存器堆 写回条件 : 与前面的所有指令结果不相关 并预测正确 最保守的方案是顺序完成, 好处 : (1) 简化异常检测和异常处理 (2) 能在被推测指令完成前得知推测结果的正确性 保留站 : 存放操作数和操作命令 Pipeline.114 SKIP 指令发射时, 其操作数可能在寄存器堆或 ROB 中, 可立即复制到保留站中, 故源操作数寄存器可被覆盖 若操作数不在寄存器堆或 ROB 中, 则一定在某个时刻被一个功能单元计算出来, 硬件将定位该功能单元, 并将结果从旁路寄存器复制到保留站

115 按序发射按序完成 举例 :2 发射超标量, 分为取指 (F) 译码(D) 执行(E) 写回(W) F D W 段在一个时钟周期内完成 ( 可同时有两条指令在这三个阶段 );E 段有三个执行部件 :Load/Store 部件完成数据 Cache 访问需要 1 个时钟, 整数 完成简单 操作需 2 个时钟, 整数乘法器完成乘法运算需要 3 个时钟 执行部件采用流水化方式 按序发射按序完成的过程如下 : 指令被阻塞在 译码器 中 i1 lw $1, A i2 add $2, $2, $1 i3 add $3, $3, $4 i4 mul $4, $5, $4 i5 lw $6, B i6 mul $6, $6, $7 i1 i2 间 RAW; i5 i6 间 RAW 和 WAW, 需阻塞一个时钟周期, 并一定要按序完成! 为了按序完成, 虽然 i5 在时钟 6 已经完成, 但一直推迟到 i4 写回后的第 9 时钟才写回 译码段执行段写回段 时钟 i1 i2 2 i3 i5 i2 i4 i6 i6 i1 i5 [i5] [i5] L/S i2 i2 i3 i3 i4 i4 i4 Mul i6 i6 i6 i1 i3 i5 i2 i4 i Pipeline.115 如果还有一条乘法指令, 则最多可有三条乘法指令同时在执行 BACK

116 按序发射无序完成 举例 :2 发射超标量, 分为取指 (F) 译码(D) 执行(E) 写回(W) F D W 段在一个时钟周期内完成 ( 可同时有两条指令在这三个阶段 );E 段有三个执行部件 :Load/Store 部件完成数据 Cache 访问需要 1 个时钟, 整数 完成简单 操作只需 2 个时钟, 整数乘法器完成乘法运算需要 3 个时钟 执行部件采用流水化方式 按序发射无序完成的过程如下 : i1 lw $1, A i2 add $2, $2, $1 i3 add $3, $3, $4 i4 mul $4, $5, $4 i5 lw $6, B i6 mul $6, $6, $7 无序完成时, 因为 i5 在时钟 6 已经完成, 和 i3 i4 没有相关性, 可以不需要等 i3 i4 写回后再写回, 所以可先于 i4 完成 译码段执行段写回段 时钟 i1 i2 2 i3 i5 i2 i4 i6 i6 i1 i5 [i5] [i5] L/S i2 i2 i3 i3 i4 i4 i4 Mul i6 i6 i6 i1 i3 i2 i5 i4 i Pipeline.116 BACK

117 无序发射无序完成 举例 :2 发射超标量, 分为取指 (F) 译码(D) 执行(E) 写回(W) F D W 段在一个时钟周期内完成 ( 可同时有两条指令在这三个阶段 );E 段有三个执行部件 :Load/Store 部件完成数据 Cache 访问需要 1 个时钟, 整数 完成简单 操作只需 2 个时钟, 整数乘法器完成乘法运算需要 3 个时钟 执行部件采用流水化方式 取指和译码按顺序进行, 发射前进行相关性无序发射无序完成的过程如下 : 检测, 无关指令可先行发射和先行完成例如 :i4 在 i3 前面发射! i1 lw $1, A 译码段执行段写回段时钟 i2 add $2, $2, $1 i3 add $3, $3, $4 i4 mul $4, $5, $4 i5 Pipeline.117 lw $6, B i6 mul $6, $6, $7 无序发射的超标量中, 译码后的指令被存放在一个 指令窗口 的缓冲器中, 等待发射 i1 i2 2 当所需功能部件可用 且无冲突或相关性阻碍指令的执行时, 就从指令窗口发射, 与取指和译码 L/S 的顺序无关 只要保证 i1 i2 和 i5 i6 的发射和完成顺序即可! i3 i5 i7 i4 i6 i8 i1 i5 i2 i2 i3 i3 i4 i4 i4 Mul i6 i6 i6 i1 i2 BACK i3 i5 i4 i

118 动态流水线调度的必要性 编译器可以依据数据依赖关系来调度代码, 为什么还要超标量处理器来动态调度? 并不是所有阻塞都能事先确定, 动态调度可在阻塞时, 提前执行无关指令 - 例如,Cache 缺失是不可预见的阻塞 动态分支预测需要根据执行的真实情况进行预测 采用动态调度使得硬件将处理器细节屏蔽起来 ( 不同处理器的发射宽度 流水线延时等可能不同, 流水线的结构也会影响循环展开的深度 通过动态调度使得处理器细节屏蔽起来, 软件发行商无需针对同一指令集的不同处理器发行相应的编译器, 并且, 以前的代码也可在新的处理器上运行, 无需重新编译 ) 理解程序的性能 : 高性能微处理器并不能持续进行多条指令的发射, 原因有 : (1) 指令间的高度依赖关系限制了指令之间的并行执行, 特别是隐含依赖关系的存在例如, 使用指针的代码段, 存在隐含依赖 (2) 分支指令预测错误 (3) 内存访问引起的阻塞 (Cache 缺失 缺页等 ) 使得流水线难以满负荷运转 Pipeline.118

119 回顾 :Pentium 4 处理器的芯片布局 前端总线及其接口 L1 数据 cache L2 cache 高级动态执行 定点运算器 超级流水线技术 Trace cache (L1 指令 cache) 浮点运算器 MMX Pipeline.119

120 回顾 :Pentium 4 处理器的逻辑结构 BTB1 静态预测从 L2 的何处预取指令 前端总线 64 位, 时钟频率 指令预取部件 指令译码器 分支预测器 BTB1 简单指令直接译码成 1~4 条微操作 ; 复杂指令从微码 ROM 中取 BTB2 动态预测从 trace cache 的何处取微操作 微码 ROM 执行跟踪 cache (12000 微操作 ) 分支预测器 BTB2 总线接口部件 预取控制逻辑 微操作队列 微操作队列 整数寄存器组 浮点寄存器组 慢 2x 2x 2xAGU 2xAGU L2 cache (48GB/s) 复杂指令 简单指令 简单指令 存地址 取地址 浮点存浮点取 浮点加浮点乘浮点除 SSE/ SSE2 MMX 256 位, 时钟频率 L1 数据 cache(8kb) Pipeline.120

121 Pentium 4 的超标量结构运算器 整数寄存器组 浮点寄存器组 慢 复杂指令 2x 简单指令 2x 简单指令 2xAGU 存地址 2xAGU 取地址 浮点存浮点取 浮点加 减 乘 除等运算 SSE SSE2 SSE3 MMX L1 数据 cache(8kb) 采用超标量 (superscalar) 结构, 一共包含 9 个运算部件, 可同时工作, 所花时钟不同 2 个高速整数 ( 每个时钟周期进行 2 次操作 ), 用于完成简单的整数运算 ( 如加 减法 ) 1 个慢速整数 ( 需要多个时钟周期才能完成 1 次操作 ), 用于完成整数乘 除法运算 2 个地址生成部件 (AGU), 用于计算操作数的有效地址, 所生成的地址分别用于从内存取操作数或向内存保存操作结果 1 个运算部件用于完成浮点操作数地址的计算 1 个运算部件用于完成浮点加法 乘法和除法运算 1 个运算部件用于执行流式的 SIMD 处理 (SSE/SSE2/SSE3 指令 ) 1 个运算部件用于完成多媒体信号处理 (MMX 指令 ) 在运算部件中执行的是微操作, 而不是指令! 运算器中的操作采用流水方式! Pipeline.121

122 回顾 :Pentium 4 的用户可见寄存器组 整数寄存器组 P4 Pentium 在 Pentium4 内部, 整数和浮点数各有 128 个寄存器寄存器换名操作 : 将用户可见的外部逻辑寄存器换成内部的物理寄存器寄存器换名时, 要确定是真实依赖还是名字依赖 ( 反依赖 ) 名字依赖时可用不同的物理寄存器替换相同的逻辑寄存器 指令计数器标志寄存器 浮点寄存器组 Pipeline.122

123 Pentium4 流水线结构部分 每个 MOP 相当于一条 RISC 指令但其格式没有公开 ROB 各项中记录对应 MOP 的资源分配状态 整数 / 浮点队列和存储队列各自有调度器, 用于检测相关性, 无序发射 指令译码结果是对应的若干条微操作 MOP TraceCache 存放指令对应的微操作序列, 一条分支微操作序列称为一个踪迹 ( trace),tc 中有多条 trace, 动态预测将哪条 trace 送 MOP 队列 (126 项 ROB) 分配资源 ( 内部寄存器 缓冲器 ) 并重命名后将 MOP 分别送两个不同队列 Pentium 4 是 CISC 壳 RISC 核 结构从 TC 中取 MOP 开始, 进入 MOP 的 20 级超标量超流水线 Pipeline.123

124 Pentium 4 的指令译码 对指令功能进行分解 指令译码逻辑 : 功能 : 将指令转换为一组基本操作, 称为微操作 MOP 输入 : 程序中的指令 输出 : 微操作 ( 简单计算任务 ) 例 1:addl %eax, %edx 的译码结果为什么? 一个 加法 操作 ( 对应一个微操作 MOP) 例 2:addl %eax, 4 (%edx) 的译码结果呢? 四个简单操作 ( 对应四个微操作 MOP): 地址计算 :Reg[%edx]+4->addr 装入 :Mem[addr]->Reg[Rtemp] 加法 :Reg[Rtemp]+Reg[%eax]->Reg[Rtemp] 存数 :Reg[Rtemp]->Mem[addr] 一个微操作相当于一条 RISC 指令, 译码生成的微操作序列被存放到 Trace Cache 中 Pipeline.124

125 Pentium4 的 20 级超流水线 (Hyper-pipeline) 整数运算微操作流水线为 20 级, 浮点为 29 级 ( 执行阶段的长度不同 ) 两个 drive 段用于芯片内传输信号的驱动, 使其保证长距离传输 沿一个踪迹顺序取 MOP, 直到遇到一条转移 MOP, 通过 BTB2 预测下个踪迹开始点, 继续取 MOP 送 ROB/Alloc/Ren 部件 预测目标处 MOP 不在时, 要通知指令预取器, 快从 L2 中取指令并译码 Pipeline.125 一个周期 3 条 MOP 送 ROB ROB 有 126 项, 记录每个 MOP 及分配的资源和执行状态, 根据资源分配情况进行寄存器重命名后, 分别送两个 MOP 队列中进行排队 每个队列按 FIFO 将 MOP 送到各自的调度器, 在调度器中进行数据相关性检测, 当所有源操作都就绪时, 将 MOP 发射到对应的执行部件 是 无序 发射 被发射的 MOP 开始读取物理寄存器中的源操作数, 或从旁路由 L1- D Cache 读取 在不同的执行部件中执行 每个部件执行时间长短不同 建立标志信息 ZF/CF 等, 并将执行结果写入物理寄存器 对 BTB2 中预测是否正确进行确认及相应处理