第四章 指令级并行.ppt

1 指令之间存在的潜在并行性称为指令级并行 ILP Instruction LevelParallelism 流水线使指令重叠并行执行 可以达到提高性能的目的 如果指令间没有相关性 可以并行执行程序中存在潜在的指令间并行需要相应的硬件支持故指令级并行 硬件 软件技术硬件技术和软件技术互相配合 通过各种可能的技术 最大限度地挖掘出程序中存在的指令级并行 第四章指令级并行 4 1指令级并行的概念 2 流水线处理机的实际CPI理想流水线的CPI加上各类停顿的时钟周期数 CPI流水线 CPI理想 停顿结构冲突 停顿数据冲突 停顿控制冲突理想CPI是衡量流水线最高性能的一个指标 IPC InstructionsPerCycle 每个时钟周期完成的指令条数 流水线的IPC 1 4 1指令级并行 3 基本程序块基本程序块 一段除了入口和出口以外不包含其他分支的线性代码段 程序平均每5 7条指令就会有一个分支 循环程序具有潜在的指令级并行 4 循环级并行 使一个循环中的不同循环体并行执行 开发循环体中存在的并行性是指令级并行研究的重点之一 例如 for i 1 i 500 i i 1 a i a i s 每一次循环都可以与其他的循环重叠并行执行 在每一次循环的内部 却没有任何的并行性 最基本的开发循环级并行的技术循环展开 loopunrolling 技术采用向量指令和向量数据表示 4 1指令级并行 5 相关与流水线冲突相关有三种类型 结构相关 数据相关 控制相关流水线冲突是指由于相关的存在 使得流水线中指令流的下一条指令不能在指定的时钟周期执行 三种类型 结构冲突 数据冲突 控制冲突相关是程序固有的一种属性 它反映了程序中指令之间的相互依赖关系 相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿 则是流水线的属性 4 1指令级并行 6 数据相关 Datadependence 先写后读相关 正相关 两条指令之间存在数据相关链 具有传递性 先读后写相关 反相关 输出相关 又称为名相关 名相关的指令之间没有数据交换 改变一条指令中的寄存器名 并不影响另外一条指令的执行控制相关 controldependence 与控制相关的指令不能移到分支指令之前 即不能调度到分支指令控制范围以外 与控制无关的指令不能移到分支指令之后 即不能调度到分支指令控制范围以内 7 可以从两个方面来解决相关问题 保持相关 但避免发生冲突 通过代码变换 消除相关 可以将冲突检测和相关处理分开进行程序顺序 由源程序确定的在完全串行方式下指令的执行顺序 必须保持程序顺序改变程序执行顺序是否影响到程序的正确性 4 1指令级并行 8 对于正确地执行程序来说 必须保持的最关键的两个属性是 数据流和异常行为 保持异常行为是指 无论怎么改变指令的执行顺序 都不能改变程序中异常的发生情况 即原来程序中是怎么发生的 改变执行顺序后还是怎么发生 弱化为 指令执行顺序的改变不能导致程序中发生新的异常 如果我们能做到保持程序的数据相关和控制相关 就能保持程序的数据流和异常行为 4 1指令级并行 9 举例说明DADDUR2 R3 R4BEQZR2 L1LWR1 0 R2 L1 数据流 指数据值从其产生者指令到其消费者指令的实际流动 分支指令使得数据流具有动态性 因为它使得给定指令的数据可以有多个来源 仅仅保持数据相关性是不够的 只有再加上保持控制顺序 才能够保持程序顺序 4 1指令级并行 10 举例 DADDUR1 R2 R3BEQZR4 L1DSUBUR1 R5 R6L1 ORR7 R1 R8OR指令中R1的值随转移是否成功而不同 4 1指令级并行 11 某些情况下 不遵守控制相关既不影响异常行为 也不改变数据流 可以大胆地进行指令调度 把失败分支中的指令调度到分支指令之前 举例 DADDUR1 R2 R3BEQZR12 SkipnextDSUBUR4 R5 R6DADDUR5 R4 R9Skipnext ORR7 R8 R9 4 1指令级并行 12 1 两种流水线调度方法 静态调度 借助软件对指令执行顺序进行调度 以减少由于流水线中存在相关冲突而引起流水线的停顿时间 动态调度 通过硬件重新安排指令的执行顺序以减少流水线中数据相关引起的断流 硬件调度优点 1 能处理某些在编译时无法知道的相关情况 2 能简化编译程序设计 3 使代码有可移植性缺点 相应的硬件较为复杂 4 2指令的动态调度 13 顺序输入顺序输出顺序输入乱序输出乱序输入乱序输出 硬件调度可能导致程序进入流水线和流出流水线的顺序发生变化 4 2指令的动态调度 14 2 动态调度 通过硬件重新安排指令的执行顺序以减少流水线的停顿 集中调度 通过集中的控制部件进行冲突检测和控制功能部件的运行 分布式调度 功能部件中指令的执行由各功能部件控制 4 2指令的动态调度 15 集中式动态调度 集中式动态调度 令牌法 4 2指令的动态调度 16 数据重定向 数据相关的处理方法 专用通道建立专用物理通道数据重定向 A C B t t 先写后读相关 4 2指令的动态调度 17 A C B t t t A C B 写 写相关 t t A C B t t t A C B 先读后写相关 t t B t 4 2指令的动态调度 18 K LOADF1 AK 1 FADDF1 F2K 2 FMULF1 F3K 3 STOREF1 B 程序举例 A直接送入加法器 A有必要送入到F1吗 相加结果可直接送入乘法器 有必要送入F1吗 相乘结果可直接送入B 有必要送入F1吗 4 2指令的动态调度 19 分布式动态调度 Tomasulo调度算法 对IBM360 91机是通过给FLR设置一个 忙 标志来判别指令间所用的数据是否发生相关 另外还有一个标志 即站号 表示数据由何处来 用站号位控制相关通路连接 采用公共数据总线CDB来实现内部数据专用通路的连接 IBM360 91的浮点运算器部分包括了以下主要部件 1 运算部件 一个加法部件和一个乘除部件 2 保存站 加法部件中有A1 A3三个保存站 乘除部件有M1和M2两个保存站 用来保存当前参加运算的数据 4 2指令的动态调度 20 3 指令操作缓冲栈 存放经分析后由指令部件送来的指令 译码后 产生相应的控制信号送到各个部件 4 浮点操作数寄存器 FLB 存放由主存预取来的操作数 5 浮点寄存器 FLR 存放操作数的寄存器 6 存储数据缓冲站 SDB 存放将写入存储器的结果数据 也有站号 7 公共数据总线 CDB 以上各部件间的连接总线 4 2指令的动态调度 21 4 2指令的动态调度 22 K 把数据直接送入加法器保留站 不送F1K 1 加操作 由于结果未出 把加指令所在保留站站号送入F1站号位 并设 忙 标志 K 2 到F1中取数 由于加法结果未出 将F1中站号取到乘法器保留站 并将其站号改为乘法器保留站号 将从乘法器站号获得结果 完成加法后 其结果与所在站号送出 站号与所有寄存器中站号比较 相等即为目标地址 K 3 乘法结果未出 将F1中站号送入后行写入栈 乘法结果产生后 可直接写入F1和后行写入栈 执行 4 2指令的动态调度 23 各部件独立分析 检测和执行 当保存站的源数据到齐 所申请的操作部件可用 立即执行 并按比较结果写数据 通用寄存器设站号位和标志位 指出该数据是否可用和来源 指令分析检测后进行数据重定向 4 2指令的动态调度 24 特点 1 由于为加法器和乘法部件分别设置了3个和2个保存站 从而减小了资源使用冲突的机会 仅当这些保存站读都处于忙碌状态时 才有可能发生资源使用冲突 2 调度算法使用保存站 通过对寄存器重新命名 改写站号 自然地消除了WAR和WAW数据相关可能性 3 通过对FLR寄存器忙位状态的判别 来检测是否存在RAW数据相关 4 借助CDB公共数据总线作为专用相关通路 将有关数据直接送往所有需要它的功能部件 而不必先写入寄存器 然后再从此寄存器读出 由于这种调度是通过各部件 忙位 站号位 CDB数据总线 来实现的故称分布式调度 4 2指令的动态调度 25 核心思想记录和检测指令相关 操作数一旦就绪就立即执行 把发生RAW冲突的可能性减少到最小 通过寄存器换名来消除WAR冲突和WAW冲突 IBM360 91首先采用了Tomasulo算法 IBM360 91的设计目标是基于整个360系列的统一指令集和编译器来实现高性能 而不是设计和利用专用的编译器来提高性能 需要更多地依赖于硬件 Tomasulo算法基本思想 26 IBM360体系结构只有4个双精度浮点寄存器 限制了编译器调度的有效性 360 91的访存时间和浮点计算时间都很长 也是Tomasulo算法要解决的问题 寄存器换名可以消除WAR冲突和WAW冲突 考虑以下代码 DIV DF0 F2 F4ADD DF6 F0 F8S DF6 0 R1 SUB DF8 F10 F14MUL DF6 F10 F8 输出相关 F6 导致WAW冲突 反相关 F8 导致WAR冲突 27 消除名相关引入两个临时寄存器S和T把这段代码改写为 DIV DF0 F2 F4ADD DS F0 F8S DS 0 R1 SUB DT F10 F14MUL DF6 F10 T 两个F6都换名为S 两个F8都换名为T 基于Tomasulo算法的MIPS处理器浮点部件的基本结构 28 保留站 reservationstation 每个保留站中保存一条已经流出并等待到本功能部件执行的指令 相关信息 包括 操作码 操作数以及用于检测和解决冲突的信息 在一条指令流出到保留站的时候 如果该指令的源操作数已经在寄存器中就绪 则将之取到该保留站中 如果操作数还没有计算出来 则在该保留站中记录将产生这个操作数的保留站 寄存器或源地址 的标识 浮点加法器有3个保留站 ADD1 ADD2 ADD3浮点乘法器有两个保留站 MULT1 MULT2每个保留站都有一个标识字段 唯一地标识了该保留站 29 公共数据总线CDB 一条重要的数据通路 所有功能部件的计算结果都是送到CDB上 由它把这些结果直接送到 播送到 各个需要该结果的地方 在具有多个执行部件且采用多流出 即每个时钟周期流出多条指令 的流水线中 需要采用多条CDB load缓冲器和store缓冲器存放读 写存储器的数据或地址load缓冲器的作用有3个 存放用于计算有效地址的分量 记录正在进行的load访存 等待存储器的响应 保存已经完成了的load的结果 即从存储器取来的数据 等待CDB传输 30 store缓冲器的作用有3个 存放用于计算有效地址的分量 保存正在进行的store访存的目标地址 该store正在等待存储数据的到达 保存该store的地址和数据 直到存储部件接收 浮点寄存器FP共有16个浮点寄存器 F0 F2 F4 F30 它们通过一对总线连接到功能部件 并通过CDB连接到store缓冲器 指令队列指令部件送来的指令放入指令队列指令队列中的指令按先进先出的顺序流出 31 运算部件浮点加法器完成加法和减法操作浮点乘法器完成乘法和除法操作在Tomasulo算法中 寄存器换名是通过保留站和流出逻辑来共同完成的 当指令流出时 如果其操作数还没有准备好 则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识 指令流出到保留站后 其操作数寄存器号或者换成了数据本身 如果该数据已经就绪 或者换成了保留站的标识 不再与寄存器有关系 32 Tomasulo算法具有以下两个特点 冲突检测和指令执行控制是分布的 每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行 计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件 而不用经过寄存器 指令执行的步骤使用Tomasulo算法的流水线需3段 流出 从指令队列的头部取一条指令 如果该指令的操作所要求的保留站有空闲的 就把该指令送到该保留站 设为r 33 如果其操作数在寄存器中已经就绪 就将这些操作数送入保留站r 如果其操作数还没有就绪 就把将产生该操作数的保留站的标识送入保留站r 一旦被记录的保留站完成计算 它将直接把数据送给保留站r 寄存器换名和对操作数进行缓冲 消除WAR冲突 完成对目标寄存器的预约工作 消除了WAW冲突 如果没有空闲的保留站 指令就不能流出 发生了结构冲突 34 执行当两个操作数都就绪后 本保留站就用相应的功能部件开始执行指令规定的操作 load和store指令的执行需要两个步骤 计算有效地址 要等到基地址寄存器就绪 把有效地址放入load或store缓冲器写结果功能部件计算完毕后 就将计算结果放到CDB上 所有等待该计算结果的寄存器和保留站 包括store缓冲器 都同时从CDB上获得所需要的数据 35 每个保留站有以下6个字段 Op 要对源操作数进行的操作 Qj Qk 将产生源操作数的保留站号 等于0表示操作数已经就绪且在Vj或Vk中 或者不需要操作数 Vj Vk 源操作数的值 对于每一个操作数来说 V或Q字段只有一个有效 对于load来说 Vk字段用于保存偏移量 Busy 为 yes 表示本保留站或缓冲单元 忙 A 仅load和store缓冲器有该字段 开始是存放指令中的立即数字段 地址计算后存放有效地址 36 Qi 寄存器状态表 每个寄存器在该表中有对应的一项 用于存放将把结果写入该寄存器的保留站的站号 为0表示当前没有正在执行的指令要写入该寄存器 也即该寄存器中的内容就绪 Tomasulo算法举例 37 例 对于下述指令序列 给出当第一条指令完成并写入结果时 Tomasulo算法所用的各信息表中的内容 L DF6 34 R2 L DF2 45 R3 MUL DF0 F2 F4SUB DF8 F2 F6DIV DF10 F0 F6ADD DF6 F8 F2 38 当采用Tomasulo算法时 在上述给定的时刻 保留站 load缓冲器以及寄存器状态表中的内容 39 名称 保留站 Load1Load2Add1Add2Add3Mult1Mult2 Busynoyesyesyesnoyesyes OpLDSUBADDMULDIV Vj VkMem 34 Regs R2 Reg F4 Mem 34 Regs R2 QjLoad2Add1Load2Mult1 QkLoad2 A45 Regs R3 40 Tomasulo算法具有两个主要的优点 冲突检测逻辑是分布的 通过保留站和CDB实现 如果有多条指令已经获得了一个操作数 并同时在等待同一运算结果 那么这个结果一产生 就可以通过CDB同时播送给所有这些指令 使它们可以同时执行 消除了WAW冲突和WAR冲突导致的停顿使用保留站进行寄存器换名 并且操作数一旦就绪就将之放入保留站 41 例 对于例4 1中的代码 假设各种操作的延迟为 load 1个时钟周期加法 2个时钟周期乘法 10个时钟周期除法 40个时钟周期给出MUL D指令准备写结果时各状态表的内容 解 MUL D指令准备写结果时各状态表的内容如下图所示 42 指令 指令状态表流出执行写结果 L DF6 34 R2 L DF2 45 R3 MUL DF0 F2 F4 SUB DF8 F6 F2 DIV DF10 F0 F6 ADD DF6 F8 F2 43 名称 保留站 Load1Load2Add1Add2Add3Mult1Mult2 Busynonoyesyesnoyesyes OpMulDIV VjMem 45 Regs R3 VkReg F4 Mem 34 Regs R2 QjMult1 Qk A 44 各符号的意义r 分配给当前指令的保留站或者缓冲器单元编号 rd 目标寄存器编号 rs rt 操作数寄存器编号 imm 符号扩展后的立即数 RS 保留站 result 浮点部件或load缓冲器返回的结果 Qi 寄存器状态表 Regs 寄存器组 Tomasulo具体算法 45 与rs对应的保留站字段 Vj Qj与rt对应的保留站字段 Vk QkQi Qj Qk的内容或者为0 或者是一个大于0的整数 Qi为0表示相应寄存器中的数据就绪 Qj Qk为0表示保留站或缓冲器单元中的Vj或Vk字段中的数据就绪 当它们为正整数时 表示相应的寄存器 保留站或缓冲器单元正在等待结果 46 S DF3 40 R4 L DF2 45 R3 符号说明 举例 47 指令流出浮点运算指令进入条件 有空闲保留站 设为r 操作和状态表内容修改 if Qi rs 0 检测第一操作数是否就绪 RS r Vj Regs rs 第一操作数就绪 把寄存器rs 中的操作数取到当前保留站的Vj RS r Qj 0 置Qj为0 表示当前保留站的Vj 中的操作数就绪 else 第一操作数没有就绪 RS r Qj Qi rs 进行寄存器换名 即把将产生该 操作数的保留站的编号放入当前保留站的Qj 48 if Qi rt 0 检测第二操作数是否就绪 RS r Vk Regs rt 第二操作数就绪 把寄存器rt中的 操作数取到当前保留站的Vk RS r Qk 0 置Qk为0 表示当前保留站的Vk中的 操作数就绪 else 第二操作数没有就绪 RS r Qk Qi rt 进行寄存器换名 即把将产生该操作 数的保留站的编号放入当前保留站的Qk RS r Busy yes 置当前保留站为 忙 RS r Op Op 设置操作码Qi rd r 把当前保留站的编号r放入rd所对应 的寄存器状态表项 以便rd将来接收结果 49 load和store指令进入条件 缓冲器有空闲单元 设为r 操作和状态表内容修改 if Qi rs 0 检测第一操作数是否就绪 RS r Vj Regs rs 第一操作数就绪 把寄存器rs中的 操作数取到当前缓冲器单元的VjRS r Qj 0 置Qj为0 表示当前缓冲器单元的Vj 中的操作数就绪 else 第一操作数没有就绪 RS r Qj Qi rs 进行寄存器换名 即把将产生该 操作数的保留站的编号存入当前缓冲器单元的Qj L DF2 45 R3 50 RS r Busy yes 置当前缓冲器单元为 忙 RS r A Imm 把符号位扩展后的偏移量放入 当前缓冲器单元的A对于load指令 Qi rt r 把当前缓冲器单元的编号r放入 load指令的目标寄存器rt所对应的寄存器 状态表项 以便rt将来接收所取的数据 L DF2 45 R3 51 对于store指令 if Qi rt 0 检测要存储的数据是否就绪 RS r Vk Regs rt 该数据就绪 把它从寄存器rt取到 store缓冲器单元的VkRS r Qk 0 置Qk为0 表示当前缓冲器单元的Vk 中的数据就绪 else 该数据没有就绪 RS r Qk Qi rt 进行寄存器换名 即把将产生该数据的保留站的编号放入当前缓冲器单元的Qk S DF3 40 R4 52 执行浮点操作指令进入条件 RS r Qj 0 且 RS r Qk 0 两个源操作数就绪操作和状态表内容修改 进行计算 产生结果 load store指令进入条件 RS r Qj 0 且r成为load store缓冲队列的头部操作和状态表内容修改 RS r A RS r Vj RS r A 计算有效地址对于load指令 在完成有效地址计算后 还要进行 从Mem RS r A 读取数据 从存储器中读取数据 53 写结果浮点运算指令和load指令进入条件 保留站r执行结束 且CDB就绪 操作和状态表内容修改 x if Qi x r 对于任何一个正在等该结果 的浮点寄存器x Regs x result 向该寄存器写入结果Qi x 0 把该寄存器的状态置为数据就绪 x if RS x Qj r 对于任何一个正在等该结果 作为第一操作数的保留站x RS x Vj result 向该保留站的Vj写入结果RS x Qj 0 置Qj为0 表示该保留站的 Vj中的操作数就绪 54 x if RS x Qk r 对于任何一个正在等该结果作为 第二操作数的保留站x RS x Vk result 向该保留站的Vk写入结果RS x Qk 0 置Qk为0 表示该保留站的Vk中的 操作数就绪 RS r Busy no 释放当前保留站 将之置为空闲状态 store指令进入条件 保留站r执行结束 且RS r Qk 0 要存储的数据已经就绪操作和状态表内容修改 Mem RS r A RS r Vk 数据写入存储器 地址由store 缓冲器单元的A字段给出 RS r Busy no 释放当前缓冲器单元 将之置为空闲状态 55 回顾 转移猜测法 不转移 顺序执行 预测正确不断流转移 插入等待获得转移地址预测不正确导致断流本调度算法解决预测正确的问题 动态硬件预测转移调度方法 4 3动态分支预测技术 56 根据转移历史信息 预测本次转移方向建立转移历史信息记录表 记录转移历史信息 需要解决问题 a 如何记录历史信息b 利用转移历史信息的转移方法注 循环程序有历史记录可依 程序员的习惯可依 基本思路 4 3动态分支预测技术 57 1 记录历史转移正确与否正确以 T 1 表示 反之 F 0 可以记录连续多次的信息 若以前转移预测成功 此次按转移成功方向预取指令 按此次转移预测是否成功修改历史记录 可以用状态转换图描述预测转移过程 三种方法 4 3动态分支预测技术 58 在指令Cache中记录转移历史信息在指令Cache中专门设置一个字段 称为 转移历史表 在执行转移指令时 把转移成功或不成功的信息记录在这个表中 当下次再执行到这条指令时 转移预测逻辑根据 转移历史表 中记录的信息预测转移成功或不成功 4 3动态分支预测技术 59 只记录最近一次转移是否成功的历史信息如果 转移历史表 中记录的内容是 T 则预测转移成功 如果记录的是 N 则按照转移不成功的方向继续取指令 用实际转移是否成功的信息来修改 转移历史表 4 3动态分支预测技术 60 记录最近两次转移是否成功的历史信息图中采用偏向成功的预测策略 只有历史上最近两次执行这条转移指令时转移都没有成功 本次才预测转移不成功也可以采用其他预测策略 4 3动态分支预测技术 61 可以具有多种 转移历史表 的修改规则和转移预测记录转移预测是否成功的信息 用最近预测是否成功的信息作为是否转移的依据当 转移历史表 是空白时 可以有两种做法 在 转移历史表 中预置转移历史信息 根据指令本身的偏移字段的符号来预测转移的方向如果偏移字段为负 则预测转移成功 否则预测转移不成功 一般循环程序的开始处 偏移为负 4 3动态分支预测技术 62 2 转移目标地址缓冲栈 记录历史转移指令地址 用转移目标地址缓冲栈记录过去使用过的转移指令的情况 包括转移指令地址 历史记录及转移目标地址 用当前指令地址和历史转移指令地址全相联比较 若相等 按历史纪录确定转移方向 同时用转移目标地址预取指令 根据转移结果 修订转移历史纪录 多用于循环程序 4 3动态分支预测技术 63 3 转移目标指令缓冲栈 转移不成功的指令已经进入流水线 为了加快转移成功的处理 可以在转移目标缓冲栈中存放若干条转移目标处的指令 如果转移成功 可以直接调用这些指令 预测判断和修改历史记录同上 4 3动态分支预测技术 64 前述5段经典流水线 由于判定分支是否成功和计算分支目标地址都是在ID段完成 所以BHT方法不会给该流水线带来好处 研究结果表明 对于SPEC89测试程序来说 具有大小为4K的BHT的预测准确率为82 99 一般来说 采用4K的BHT就可以了 BHT可以跟分支指令一起存放在指令Cache中 也可以用一个专门的硬件来实现 4 3动态分支预测技术 65 前瞻执行 speculation 的基本思想 对分支指令的结果进行猜测 并假设这个猜测总是对的 然后按这个猜测结果继续取 流出和执行后续的指令 只是执行指令的结果不是写回到寄存器或存储器 而是放到一个称为ROB ReOrderBuffer 的缓冲器中 等到相应的指令得到 确认 commit 即确实是应该执行的 之后 才将结果写入寄存器或存储器 3基于硬件的前瞻执行 4 3动态分支预测技术 66 基于硬件的前瞻执行结合了三种思想 动态分支预测 用来选择后续执行的指令 在控制相关的结果尚未出来之前 前瞻地执行后续指令 用动态调度对基本块的各种组合进行跨基本块的调度 对Tomasulo算法加以扩充 就可以支持前瞻执行 把Tomasulo算法的写结果和指令完成加以区分 分成两个不同的段 写结果 指令确认 4 3动态分支预测技术 67 写结果段把前瞻执行的结果写到ROB中 通过CDB在指令之间传送结果 供需要用到这些结果的指令使用 指令确认段在分支指令的结果出来后 对相应指令的前瞻执行给予确认 如果前面所做的猜测是对的 把在ROB中的结果写到寄存器或存储器 如果发现前面对分支结果的猜测是错误的 那就不予以确认 并从那条分支指令的另一条路径开始重新执行 4 3动态分支预测技术 68 实现前瞻的关键思想 允许指令乱序执行 但必须顺序确认 支持前瞻执行的浮点部件的结构 4 3动态分支预测技术 69 70 ROB中的每一项由以下4个字段组成 指令类型指出该指令是分支指令 store指令或寄存器操作指令 目标地址给出指令执行结果应写入的目标寄存器号 如果是load和ALU指令 或存储器单元的地址 如果是store指令 数据值字段用来保存指令前瞻执行的结果 直到指令得到确认 就绪字段指出指令是否已经完成执行并且数据已就绪 4 3动态分支预测技术 71 Tomasulo算法中保留站的换名功能是由ROB来完成的 采用前瞻执行机制后 指令的执行步骤 在Tomasulo算法的基础上改造的 流出从浮点指令队列的头部取一条指令 如果有空闲的保留站 设为r 且有空闲的ROB项 设为b 就流出该指令 并把相应的信息放入保留站r和ROB项b 如果保留站或ROB全满 便停止流出指令 直到它们都有空闲的项 4 3动态分支预测技术 72 执行如果有操作数尚未就绪 就等待 并不断地监测CDB 检测RAW冲突 当两个操作数都已在保留站中就绪后 就可以执行该指令的操作 写结果当结果产生后 将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上 经CDB写到ROB以及所有等待该结果的保留站 释放产生该结果的保留站 store指令在本阶段完成 其操作为 4 3动态分支预测技术 73 如果要写入存储器的数据已经就绪 就把该数据写入分配给该store指令的ROB项 否则 就监测CDB 直到那个数据在CDB上播送出来 这时才将之写入分配给该store指令的ROB项 确认对分支指令 store指令以及其他指令的处理不同 其他指令 除分支指令和store指令 当该指令到达ROB队列的头部而且其结果已经就绪时 就把该结果写入该指令的目标寄存器 并从ROB中删除该指令 4 3动态分支预测技术 74 store指令处理与上面类似 只是它把结果写入存储器 分支指令当预测错误的分支指令到达ROB队列的头部时 清空ROB 并从分支指令的另一个分支重新开始执行 错误的前瞻执行 当预测正确的分支指令到达ROB队列的头部时 该指令执行完毕 4 3动态分支预测技术 75 例4 3假设浮点功能部件的延迟时间为 加法2个时钟周期 乘法10个时钟周期 除法40个时钟周期 对于下面的代码段 给出当指令MUL D即将确认时的状态表内容 L DF6 34 R2 L DF2 45 R3 MUL DF0 F2 F4SUB DF8 F6 F2DIV DF10 F0 F6ADD DF6 F8 F2 4 3动态分支预测技术 76 前瞻执行中MUL D确认前 保留站和ROB的状态 4 3动态分支预测技术 77 4 3动态分支预测技术 78 前瞻执行通过ROB实现了指令的顺序完成 能够实现精确异常 很容易地推广到整数寄存器和整数功能单元上 主要缺点 所需的硬件太复杂 4 3动态分支预测技术 79 寻求提高计算机性能的其它途径 1 超标量处理机在传统的计算机执行过程中 是否在每个时钟周期每个操作部件都处于 忙 状态 如 执行运算类指令时 存储器处于空闲 能否使不同类型的指令同时运行 4 4多指令流出技术 80 1 各操作部件并行连接 使不同类型的指令送入相应的操作部件执行 2 需要多条指令同时存取和译码 3 若每个操作部件内部为流水结构 可以实现每个时钟周期执行多条指令 基本思路 4 4多指令流出技术 81 单发射机 一个时钟周期送入执行一条指令 多发射机 一个时钟周期送入执行多条指令 多发射机制 4 4多指令流出技术 82 设一个时钟周期发射执行一条指令 其ILP 1 指令级并行度可由 m n 表示 m同时发射的并行指令条数n流水线中一个时钟周期分时发射的指令条数单流水线的ILP 1 相关性 指令级并行度ILP InstructionLevelParallelism 4 4多指令流出技术 83 4 4多指令流出技术 单流水普通标量 1 1 超标量 m 1 超流水 1 n 超标量超流水 m n 指令级并行度的描述 84 4 4多指令流出技术 85 每拍启动3条指令要求并行度 3 超级标量机 配置多个功能部件多个译码器 寄存器端口 总线 能同时执行多个操作 例 4 4多指令流出技术 86 1 结构相关重复设置操作部件 形成多操作部件计算机 既超标量计算机 以减缓结构相关性 2 数据相关3 控制相关a 等待 b 设置检测调度器和缓冲器 当出现相关指令 送入缓冲器 使不相关的指令先行处理 多发射中的相关性处理 4 4多指令流出技术 87 1 每个时钟周期内能启动n条指令 2 配置有多个性能不同的处理部件 采用多条流水线并行处理 3 能同时对若干条指令进行译码 将可并行的指令送往不同的执行部件 从而达到每个周期启动多条指令 4 在程序运行期间由硬件 通常是状态记录部件和调度部件 完成指令调度 小结 4 4多指令流出技术 88 超标量流水线调度 指令发射策略 指令发射所使用的协议或规则 按序发射 当指令按策划功能序的次序发射时 称之为按序发射 in orderissue 无序发射 为改善流水线性能 可以将有相关的指令推后发射 而将后面的无相关性的指令提前发射 即不按程序原有次序发射指令 称之为无序发射 out of order 4 4多指令流出技术 89 按序发射按序完成按序发射无序完成无序发射无序完成无论那种调度策略 都要保证程序运行的最终结果是正确的 Pentium处理器采用的是按序发射按序完成策略PentiumII III处理器采用的是按序发射无序完成 4 4多指令流出技术 90 指令 检测调度 4 4多指令流出技术 91 超标量处理机性能 单流水标量 单流水超标量 加速比 4 4多指令流出技术 92 4 4多指令流出技术 93 4 4多指令流出技术 94 有两条或两条以上能同时工作的指令流水线先行指令窗口 能够从指令Cache中预取多条指令 能够对窗口内的指令进行数据相关性分析和功能部件冲突检测 例如 Intel公司的i860 i960 Pentium Motolora公司的MC88110 IBM公司的Power6000 TI公司生产SuperSPARC等操作部件的个数一般多于每个周期发射的指令条数 通常为4个至16个操作部件 超标量处理机的指令级并行度 1 ILP m 4 4多指令流出技术 95 4 4多指令流出技术 96 普通标量处理机 希望相同操作连续出现 只有连续出现相同操作的指令序列时 流水线的效率才能得到充分发挥 超标量处理机则正好相反 希望相同操作不要连续出现 相同操作的指令序列连续出现时 会发生资源冲突 要求相同操作的指令能够相对均匀地分布在程序中 超标量处理机的这种要求正好符合一般标量程序的特点 超标量机的特点 4 4多指令流出技术 97 以一条长指令实现多个操作的并行执行 减少存储器访问 主要特点 1 单一的控制流 只有一个控制器 每个周期启动一条指令 2 超长指令字被分成多个控制字段 每个字段直接独立地控制每个功能部件 3 含有大量的数据通路和功能部件 由于编译器在编译时间已考虑可能出现的数据相关和资源相关 故控制硬件较简单 4 在编译阶段完成超长指令中多个可并行执行操作的调度 2 超长指令字计算机 4 4多指令流出技术 98 每拍启动一条长指令 执行3个操作 相当于3条指令 要求并行度 3 超长指令字计算机 VLIW 的原理结构 4 4多指令流出技术 99 超流水线处理机的两种定义 在一个周期内分时发射多条指令的处理机指令流水线的段数大于等于8的流水线处理机提高处理机性能的两种方法 通过增加硬件资源来提高处理机性能通过各部分硬件的重叠工作来提高处理机性能两种不同并行性 超标量处理机采用的是空间并行性 超流水线处理机采用的是时间并行性 3 超级流水方法 4 4多指令流出技术 100 每1 2拍启动一条指令 要求并行度 2 超级流水线的原理结构图 4 4多指令流出技术 101 每隔1 n个时钟周期发射一条指令 即处理机的流水线周期为1 n个时钟周期 4 4多指令流出技术 102 超流水线处理机性能 指令级并行度为 1 n 的超流水线处理机 执行N条指令所的时间为 超流水线处理机相对于单流水线普通标量处理机的加速比为 加速比的最大值为 S 1 n MAX n 每个时钟周期完成n条指令 4 4多指令流出技术 103 特点 超流水结构是把每一个流水级 一个周期 分成多个 例如3个 子流水级 而在每一个子流水级中取出的仍只有一条指令 但总的来看 在一个周期内取出了三条指令 对于超流水线结构 其中指令部件可以只有一套 也可以有多套独立的执行部件 它虽然每个机器周期只能流出一条指令 但它的周期比其它机器短 一台m度的超级流水线计算机的周期为一般机器周期的1 m 它的一个操作需要m个周期 因而在流水线能充分发挥作用时 其并行度能达到m 4 4多指令流出技术 这种方法主要通过提高流水线运行速度来增强机器性能 为提高运行速度 必须要加深流水深度 既增加流水段数 以减少每一段的延迟时间 这样就可加快流水线的运行频率 104 R4000超级流水情况分8段 取指1 IF 取指2 IS 读RF 执行 EX 取数1 DF 取数2 DS 标记检查 TC 写RF WB 4 4多指令流出技术 105 4 超级流水标量计算机 把超标量技术与超流水技术结合在一起 构成超标量超流水线处理机 超标量超流水线处理机在一个时钟周期内要发射指令n次 每次发射指令m条 因此 超标量超流水线处理机每个时钟周期总共要发射指令m n条 超标量超流水线处理机的指令执行时空图 4 4多指令流出技术 106 超标量超流水线处理机的性能 指令级并行度为 m n 的超标量超流水线处理机 连续执行N条指令所需要的时间为 超标量超流水线处理机相对于单流水线标量处理机的加速比为 在理想情况下 超标量超流水线处理机加速比的最大值为 S m n MAX mn 4 4多指令流出技术 107 三种标量处理机的性能比较 4 4多指令流出技术 108 从三种标量处理机的性能曲线中 有如下结论 1 三种处理机的性能关系超标量处理机的相对性能最高 其次是超标量超流水线处理机 超流水线处理机的相对性能最低 主要原因如下 1 超标量处理机功能部件的冲突比超流水线处理机小 在指令执行过程中的许多功能段 超标量处理机都重复设置有多个相同的指令执行部件 而超流水线处理机只是把同一个指令执行部件分解为多个流水级 4 4多指令流出技术 109 2 条件转移等操作造成的损失 超流水线处理机要比超标量处理机大 由于超流水线处理机采用深度流水线结构 对条件转移等操作比超标量处理机敏感 3 超流水线处理机的启动延迟通常要比超标量处理机大 超标量处理机在每个时钟周期的一开始就同时发射多条指令 超流水线处理机把一个时钟周期平均分成多个流水线周期 每个流水线周期只发射一条指令 4 4多指令流出技术 110 2 实际指令级并行度与理论指令级并行度的关系当横坐标给出的理论指令级并行度比较低时 处理机的实际指令级并行度的提高比较快 当理论指令级并行度进一步增加时 处理机实际指令级并行度提高的速度越来越慢 在实际设计超标量 超流水线 超标量超流水线处理机的指令级并行度时要适当 否则 有可能造成花费了大量的硬件 但实际上处理机所能达到的指令级并行度并不高 目前 一般认为 m和n都不要超过4 4 4多指令流出技术 111 3 最大指令级并行度一个特定程序由于受到本身的数据相关和控制相关的限制 它的指令级并行度的最大值是有限的 是有个确定的值 最大指令级并行度由程序自身的语义决定 与这个程序运行在那一种处理机上及采用何种方法开发并行性无关 对于某一个特定的程序 图中的三条曲线最终都要收拢到同一个点上 对于各个不同程序 这个收拢点的位置也是不同的 4 4多指令流出技术 112 充分开发指令之间存在的并行性 找出不相关的指令序列 让它们在流水线上重叠并行执行 增加指令间并行性最简单和最常用的方法开发循环级并行性 循环的不同迭代之间存在的并行性 在把循环展开后 通过重命名和指令调度来开发更多的并行性 4 5循环展开和指令调度 1循环展开和指令调度的基本方法 113 编译器完成这种指令调度的能力受限于两个特性 程序固有的指令级并行性 流水线功能部件的执行延迟 这里浮点流水线延迟为 4 5循环展开和指令调度 114 假设采用第3章的5段整数流水线 分支的延迟 1个时钟周期 整数load指令的延迟 1个时钟周期 整数运算部件是全流水或者重复设置了足够的份数 4 5循环展开和指令调度 115 例4 6对于下面的源代码 转换成MIPS汇编语言 在不进行指令调度和进行指令调度两种情况下 分析其代码一次循环所需的执行时间 for i 1 i 1000 i x i x i s 解把该程序翻译成MIPS汇编语言代码 假设R1的初值是指向第一个元素 8 R2 指向最后一个元素 4 5循环展开和指令调度 116 Loop L DF0 0 R1 ADD DF4 F0 F2S DF4 0 R1 DADDIUR1 R1 8BNER1 R2 Loop其中 整数寄存器R1 指向向量中的当前元素 初值为向量中最高端元素的地址 浮点寄存器F2 用于保存常数s 4 5循环展开和指令调度 117 不进行指令调度的情况下 程序的实际执行情况 指令流出时钟Loop L DF0 0 R1 1 空转 2ADD DF4 F0 F23 空转 4 空转 5S DF4 0 R1 6DADDIUR1 R1 87 空转 8BNER1 R2 Loop9 空转 10每个元素的操作需要10个时钟周期 其中5个是空转周期 4 5循环展开和指令调度 118 指令调度以后 程序的执行情况如下 把DADDIU指令调度到了L D指令和ADD D指令之间的 空转 拍 把S D指令放到了分支指令的延迟槽中 对存储器地址偏移量进行调整 4 5循环展开和指令调度 119 Loop L DF0 0 R1 空转 ADD DF4 F0 F2 空转 空转 S DF4 0 R1 DADDIUR1 R1 8 空转 BNER1 R2 Loop 空转 Loop L DF0 0 R1 DADDIUR1 R1 8ADD DF4 F0 F2 空转 BNER1 R2 LoopS DF4 8 R1 4 5循环展开和指令调度 120 指令流出时钟Loop L DF0 0 R1 1DADDIUR1 R1 82ADD DF4 F0 F23 空转 4BNER1 Loop5S DF4 8 R1 6一个元素的操作时间从10个时钟周期减少到6个 其中5个周期是有指令执行的 1个为空转周期 4 5循环展开和指令调度 121 例子中的问题及解决方案只有L D ADD D和S D这3条指令是有效操作 取 加 存 占用3个时钟周期 而DADDIU 空转和BEN这3个时钟周期都是附加的循环控制开销 循环展开技术把循环体的代码复制多次并按顺序排列 然后相应调整循环的结束条件 这给编译器进行指令调度带来了更大的空间 4 5循环展开和指令调度 122 例4 7 体现循环展开技术的特点 将上述例子中的循环展开3次得到4个循环体 然后对展开后的指令序列在不调度和调度两种情况下 分析代码的性能 假定R1的初值为32的倍数 即循环次数为4的倍数 消除冗余的指令 并且不要重复使用寄存器 解无需在循环体后面增加补偿代码 4 5循环展开和指令调度 123 F0 F4 用于展开后的第1个循环体F2 保存常数F6 F8 展开后的第2个循环体F10 F12 第3个循环体F14 F16 第4个循环体 分配寄存器 不重复使用寄存器 4 5循环展开和指令调度 for i 1 i 1000 i 4 x i x i s x i 1 x i 1 s x i 2 x i 2 s x i 3 x i 3 s 124 展开后没有调度的代码如下 指令流出时钟Loop L DF0 0 R1 1 空转 2ADD DF4 F0 F23 空转 4 空转 5S DF4 0 R1 6L DF6 8 R1 7 空转 8ADD DF8 F6 F29 空转 10 空转 11S DF8 8 R1 12L DF10 16 R1 13 空转 14 指令流出时钟ADD DF12 F10 F215 空转 16 空转 17S DF12 16 R1 18L DF14 24 R1 19 空转 20ADD DF16 F14 F221 空转 22 空转 23S DF16 24