# 指令级并行 - 章节关键原文 ## 曲冠南老师（qgn） ### Slide 4 - 指令级并行的概念 ``` 指令级并行ILP概念:是指存在于指令一级即指令间的并行性, 主要是指机器语言一级, 如存储器访问指令、整型指令、浮点指令之间的并行性等。 指令级并行主要特点:是并行性由处理器硬件和编译程序自动识别和利用, 不需要程序员对顺序程序作任何修改。正是由于这一优点, 使得它的发展与处理器的发展紧密相连。 ``` ### Slide 5 - 开发指令级并行的重要性 ``` 理想CPI（无冲突）是衡量流水线最高性能的一个指标 实际CPI往往远大于理想CPI，它是理想流水线的CPI加上各类停顿的时钟周期数： CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突 减少等式右端的各项就减少了总的CPI,从而提高IPC.（Instructions Per Cycle：每个时钟周期完成的指令条数） ``` ### Slide 6 - 开发指令级并行需要解决的具体问题 ``` 相关 两条指令之间存在某种依赖关系 分类：数据相关、名相关、控制相关 ``` ### Slide 7 - 流水线冲突（冒险） ``` 流水线冲突（冒险） 对于具体的流水线来说，由于相关等原因的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。 流水线冲突有三种类型：结构冲突、数据冲突、控制冲突 小结与比较 相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。 具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，则是流水线的属性。 ``` ### Slide 8 - 相关的两类解决方案 ``` 保持相关，但避免发生冲突 指令调度 -- 编译器静态调度 通过代码变换，消除相关 寄存器重命名 -- 寄存器换名消除WAR和WAW ``` ### Slide 9 - 开发指令级并行的方法 ``` 基于软件的静态开发方法 基于硬件的动态开发方法 硬件＋软件技术 只有硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行。 ``` ### Slide 10 - 基本编译技术 – 循环展开 与 指令调度 ``` 充分开发指令之间存在的并行性，找出不相关的指令序列，让它们在流水线上重叠并行执行。 增加指令间并行性最简单和最常用的方法 开发循环级并行性——循环的不同迭代之间存在的并行性。 在把循环展开后，通过重命名和指令调度来开发更多的并行性。 编译器完成这种指令调度的能力受限于两个特性： 程序固有的指令级并行性； 流水线功能部件的执行延迟。 ``` ### Slide 12 - 循环展开示例题目 ``` 例 对于下面的源代码，转换成MIPS汇编语言，在不进行指令调度和进行指令调度两种情况下，分析其代码一次循环所需的执行时间。 for (i=1； i<=1000； i++) x[i] = x[i] + s； ``` ### Slide 13 - 循环展开示例代码 ``` Loop：L.D F0,0（R1） ADD.D F4,F0,F2 S.D F4, 0（R1） DADDIU R1,R1，#-8 BNE R1,R2,Loop 其中： 整数寄存器R1：指向向量中的当前元素。 （初值为向量中最高端元素的地址） 浮点寄存器F2：用于保存常数s。 ``` ### Slide 14 - 情况 I：不进行调度 ``` 情况 I ： 不进行调度 每个元素的操作需要10个时钟周期，其中5个是空转周期。 ``` ### Slide 15 - 情况 II：进行指令调度 ``` Loop: L.D F0, 0(R1) DADDIU R1,R1,#-8 ADD.D F4, F0, F2 （空转） BNE R1,R2,Loop S.D F4，8(R1) 情况 II ： 进行指令调度 一个元素的操作时间从10个时钟周期减少到6个,其中5个周期是有指令执行的，1个为空转周期。 ``` ### Slide 16 - 例子中的问题及解决方案 ``` 例子中的问题及解决方案 只有L.D、ADD.D和S.D这3条指令是有效操作。 占用3个时钟周期。 而DADDIU、空转和BEN这3个时钟周期都是附加的循环控制开销。 循环展开技术 把循环体的代码复制多次并按顺序排列，然后相应调整循环的结束条件。 这给编译器进行指令调度带来了更大的空间。 ``` ### Slide 19 - 结果分析 ``` 结果分析: 这个循环每遍共使用了28个时钟周期。 有4个循环体，完成4个元素的操作。 平均每个元素使用28/4=7个时钟周期 原始循环的每个元素需要10个时钟周期。 节省的时间：从减少循环控制的开销中获得的。 在整个展开后的循环中，实际指令只有14条，其他14个周期都是空转。 效率并不高 ``` ### Slide 20 - 情况 IV：进行指令调度 ``` 结果分析： 没有数据相关引起的空转等待。整个循环仅仅使用了14个时钟周期。平均每个元素的操作使用14/4=3.5个时钟周期。 通过循环展开、寄存器重命名和指令调度，可以有效地开发出指令级并行。 ``` ### Slide 21 - 循环展开和指令调度注意事项 ``` 循环展开和指令调度时注意： 保证正确性。在循环展开和调度过程中尤其要注意两个地方的正确性：循环控制，操作数偏移量的修改。 注意有效性。只有能够找到不同循环体之间的无关性，才能有效地使用循环展开。 使用不同的寄存器。（否则可能导致新的冲突） 删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正。 注意对存储器数据的相关性分析例如：对于load指令和store指令，如果它们在不同的循环迭代中访问的存储器地址是不同的，它们就是相互独立的，可以相互对调。 注意新的相关性。由于原循环不同次的迭代在展开后都到了同一次循环体中，因此可能带来新的相关性。 ``` ### Slide 23 - 基本思想 ``` 1. 相关与流水线冲突 结构冲突（冒险） 停顿 重复设置资源 相关：两条指令之间存在的某种依赖关系 相关有3种类型 数据相关 名相关 反相关 输出相关 控制相关 数据冲突（冒险）之写后读 定向/旁路 （forwarding） 编译器指令调度 控制冲突（冒险） 预测分支失败（静态） 预测分支成功（静态） 延迟分支（延迟槽） 数据冲突（冒险）之读后写 数据冲突（冒险）之写后写 ``` ### Slide 24 - 静态调度 V.S. 动态调度 ``` 静态调度 V.S. 动态调度 静态调度：是依靠编译器对代码进行调度，也就是在代码被执行之前进行调度；通过把相关的指令拉开距离来减少可能产生的停顿。 动态调度：在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。 指令顺序执行 V.S. 指令乱序执行 指令顺序执行：指令放入流水线的顺序和指令完成的顺序一致； 指令乱序执行：指令放入流水线的顺序和指令完成的顺序不一致，也就是说有些指令进入流水线后被阻塞的，而在其后进入流水线的指令先完成了。 ``` ### Slide 25-26 - 为什么要进行动态调度 ``` 首先，思考下面一段代码： 指令1 DIV.D F4，F0，F2 指令2 SUB.D F10，F4，F6 指令3 ADD.D F12，F6，F14 这段代码放到 MIPS 的五段流水线上，假如没有用任何定向等技术，会怎样执行？ 指令2和指令1是关于F4数据相关，因此进入流水线之后会产生数据冲突，导致指令2被阻塞，指令3也同时被阻塞了。指令3是很冤枉的，明明和前面指令什么关系都没有。 解决第一个问题： 将ID段又分成了两个阶段： 流出（Issue，IS）阶段：指令译码，检查是否存在结构冲突。 读操作数（Read Operands，RO）阶段：检测数据冲突，如果没有，继续执行；如果有，等待数据冲突消失，然后读操作数。 指令的动态调度，也就是在指令的执行过程中进行调度。 ``` ### Slide 27-28 - 动态调度带来的新问题 ``` 假如代码是这样的，第1条指令是个除法指令，执行阶段可能会比较长（假设执行需要3个周期时间）；第2和第3条有反相关。 指令1 DIV.D F4，F0，F2 指令2 SUB.D F10，F4，F6 指令3 ADD.D F6，F12，F14 指令3先写入F6， 指令2后读出F6，就产生了错误的执行结果。 也就是说，指令的动态调度导致了指令的乱序执行，指令的乱序执行导致了有反相关和输出相关的指令进入流水线之后产生读后写冲突和写后写冲突。 ``` ### Slide 29 - 解决第二个问题 ``` 采用寄存器换名技术，消除名相关。 于是下面这段代码： 指令1 DIV.D F4，F0，F2 指令2 SUB.D F10，F4，F6 指令3 ADD.D F6，F12，F14 可以变成： 指令1 DIV.D F4，F0，F2 指令2 SUB.D F10，F4，F6 指令3 ADD.D S，F12，F14 ``` ### Slide 30 - 动态调度基本思想小结 ``` 相对于静态指令调度，动态指令调度是在指令的执行过程中进行调度，使得无关的指令得以先执行，减少阻塞； 能够处理一些在编译时情况不明的相关（如存储器访问的相关）； 能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行； 动态指令调度将会引起指令乱序执行，因此，使用换名技术消除名相关（包括反相关和输出相关）； 指令乱序完成使得异常处理困难； 以硬件复杂性的显著增加为代价。 ``` ### Slide 32 - Tomasulo算法核心思想 ``` 核心思想 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小； 通过寄存器换名来消除WAR冲突和WAW冲突。 ``` ### Slide 33 - 寄存器换名示例 ``` 寄存器换名可以消除WAR冲突和WAW冲突。 考虑以下代码： DIV.D F0，F2，F4 ADD.D F6，F0，F8 S.D F6，0（R1） SUB.D F8，F10，F14 MUL.D F6， F10，F8 输出相关（F6） 导致WAW冲突 反相关（F8） 导致WAR冲突 ``` ### Slide 35 - Tomasulo的基本结构 ``` 2.Tomasulo的基本结构 主要部件： 指令队列 保留站 Store/load缓冲器 公共数据总线CDB 运算部件 存储部件 浮点寄存器 ``` ### Slide 36 - 保留站 ``` 保留站（reservation station） 每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。 每个保留站包括操作码、操作数以及用于检测和解决冲突的信息。 在一条指令流出送到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将操作数取到该保留站中。 如果操作数还没有计算出来，则在该保留站中记录即将产生这个操作数的保留站的标识。 浮点加法器有3个保留站：ADD1，ADD2，ADD3 浮点乘法器有2个保留站：MULT1，MULT2 每个保留站都有一个标识字段，唯一地标识了该保留站。 ``` ### Slide 37 - 公共数据总线CDB ``` 公共数据总线CDB （一条重要的数据通路） 所有功能部件的计算结果都是送到CDB上，由它把这些结果直接送到（播送到）各个需要该结果的地方。 在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条CDB。 从存储器读取的数据也送到CDB。 CDB连接到除了load缓冲器以外的所有部件的入口。 浮点寄存器通过一对总线连接到功能部件，并通过CDB连接到store缓冲器的入口。 ``` ### Slide 38 - load/store缓冲器 ``` load缓冲器的作用有3个 存放用于计算有效地址的分量； 记录正在进行的load访存，等待存储器的响应； 保存已经完成了的load的结果（即从存储器取来的数据），等待CDB传输。 store缓冲器的作用有3个： 存放用于计算有效地址的分量； 保存正在进行的store访存的目标地址，该store正在等待存储数据的到达； 保存该store的地址和数据，直到存储部件接收。 ``` ### Slide 39 - 浮点寄存器和指令队列 ``` 浮点寄存器FP 共有16个浮点寄存器：F0，F2，F4，…，F30。 它们通过一对总线连接到功能部件，并通过CDB连接到store缓冲器。 指令队列 指令部件送来的指令放入指令队列 指令队列中的指令按先进先出的顺序流出 运算部件 浮点加法器完成加法和减法操作 浮点乘法器完成乘法和除法操作 ``` ### Slide 40 - 寄存器换名 ``` 在Tomasulo算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。 当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号 换名 为将产生这个操作数的保留站的标识。 指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，不再与寄存器有关系。这样 后面指令对寄存器的写入操作就不可能产生WAR冲突了 ``` ### Slide 46 - Tomasulo算法优点 ``` 5.Tomasulo算法具有两个主要的优点： ①冲突检测和指令执行控制是分布的。 每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。 计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。 ②消除了WAW冲突和WAR冲突导致的停顿(详情见后面例题) 使用保留站进行寄存器换名，并且操作数一旦就绪就将之放入保留站。 ``` ### Slide 63 - Tomasulo要点总结 ``` 9.Tomasulo的要点总结 ① 指令按照程序原有的顺序进入指令队列，并按照原有的顺序流出指令队列，但是并不一定按照原有的顺序执行。 ② 操作数未就绪的指令在保留站中等待，操作数就绪的指令可以先被执行。 ③ 通过寄存器换名技术消除了名相关，从而解决了读后写和写后写冲突。换了什么名呢？把流出到保留站中的指令的操作数寄存器换成了操作数，或者产生该操作数的保留站号。 ④ 指令能够流出、执行和写结果这三步的进入条件请看详细的算法，但是还有一个隐含条件，即没有结构冲突。 ⑤ Tomasulo算法只能处理结构冲突和数据冲突，不能处理异常和控制冲突。指令队列里有分支指令，分支指令之后的指令不能流出，直到确定分支是否成功。 ⑥ 在算法中，有两个地方容易忽视，需要格外注意：一个是Load/store指令要按照FIFO次序访存；另一个是，store指令执行阶段和写结果阶段进入的条件。 ``` ### Slide 65-66 - 动态分支预测技术 ``` 什么是动态分支预测 优点： 根据程序的执行过程动态地改变转移的预测方向，因此有更好的准确度和适应性。 程序每次执行时，可能预测的分支方向与前次相同或不同。 以上预测机制的性能随着复杂性与硬件的增加而有效地提高。 从简单到复杂的动态转移预测技术如下： 分支预测缓存器（BHT） 分支目标缓冲器（BTB） 基于硬件的前瞻执行(ROB) 动态分支预测技术： 通过硬件技术，在程序执行时根据每一条转移指令过去的转移历史记录来预测下一次转移的方向。通过提前预测分支方向，减少或消除控制相关导致的流水线停顿。 要点： 动态分支预测技术和静态分支预测技术的区别 什么叫"分支指令过去的表现"？ 如何衡量分支预测的有效性？ 分支预测要解决的问题是什么？ 需要解决的关键问题？ ``` ### Slide 70-75 - 分支历史表BHT ``` 1.分支历史表BHT（Branch History Table） 或分支预测缓冲器（Branch Prediciton Buffer） 最简单的动态分支预测方法。 用BHT来记录分支指令最近一次或几次的执行情况（成功或不成功），并据此进行预测。 2. 只有1个预测位的分支预测缓冲 记录分支指令最近一次的历史，BHT中只需要1位二进制位。 　（最简单） "0"记录分支不成功 "1"记录分支成功 遇见1，预测成功。实际成功则保持1，实际失败置0 遇见0，预测失败。实际失败则保持0，实际成功置1 采用两位二进制位来记录历史 提高预测的准确度 研究结果表明：两位分支预测的性能与n位（n>2）分支预测的性能差不多。 4. BHT方法只在以下情况下才有用： 判定分支是否成功所需的时间大于确定分支目标地址所需的时间。 前述5段经典流水线：由于判定分支是否成功和计算分支目标地址都是在ID段完成，所以BHT方法不会给该流水线带来好处。 研究结果表明：对于SPEC89测试程序来说，具有大小为4K的BHT的预测准确率为82%～99%。 一般来说，采用4K的BHT就可以了。 ``` ### Slide 77-78 - 分支目标缓冲器BTB ``` 背景： 在高性能流水线中，特别是多流出的处理机中，只准确地预测分支还不够，还要能够提供足够的指令流。许多现代的处理器要求每个时钟周期能提供4～8条指令。这需要尽早知道分支是否成功、尽早知道分支目标地址、尽早获得分支目标指令。 1.为什么要用分支目标缓冲 方法：分支目标缓冲 将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识。 这个缓冲区就是分支目标缓冲器（Branch-Target Buffer，简记为BTB，或者Branch-Target Cache）。 目标：将分支的开销降为 0 2.BTB表结构 看成是用专门的硬件实现的一张表格。 表格中的每一项至少有两个字段： 执行过的成功分支指令的地址； （作为该表的匹配标识 ） 预测的分支目标地址。 ``` ### Slide 80 - BTB举例 ``` 5. 举例： 假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。 （1）求程序执行的CPI。 （2）相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？ ``` ### Slide 86 - 前瞻执行基本思想 ``` 前瞻执行（speculation）的基本思想： 对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取出、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，而是放到一个称为ROB（ReOrder Buffer）的缓冲器中。等到相应的指令得到"确认"（commit）（即确实是应该执行的）之后，才将结果写入寄存器或存储器。 目的：在猜测错误时能够恢复现场（即没有进行不可恢复的写操作） 动态预测+猜测执行+保留站技术 为了得到更高的并行性，将动态转移预测技术与Tomasulo结合，设计出了前瞻执行方法：处理器按转移预测方向，乱序执行推测的指令序列，如果预测正确，就能够消除控制相关的延迟。也解决了数据相关和消除名相关。如果预测错误，则废弃已经执行的指令序列，从另一个分支处重新开始执行。 ``` ### Slide 87 - 基于硬件的前瞻执行 ``` 基于硬件的前瞻执行结合了三种思想： ① 动态分支预测。用来选择后续执行的指令。 ② 在控制相关的结果尚未出来之前，前瞻地执行后续指令。 ③ 用动态调度对基本块的各种组合进行跨基本块的调度。（基本程序块：如果 一串连续的代码除了入口和出口以外，不包含其他分支指令和转入点。） 基本要点：动态预测+猜测执行+保留站技术 实质是数据流执行(data flow execution)：只要操作数有效，指令就执行 ``` ### Slide 88-89 - 写结果段和确认段 ``` ①写结果段 把前瞻执行的结果写到ROB中； 通过CDB在指令之间传送结果，供需要用到这些结果的指令使用。 ②指令确认段 在分支指令的结果出来后，对相应指令的前瞻执行 给予确认。 如果前面所做的猜测是对的，把在ROB中的结果写到寄存器或存储器。 如果发现前面对分支结果的猜测是错误的，那就不予以确认，并从那条分支指令的另一条路径开始重新执行。 ``` ### Slide 91 - ROB结构 ``` ROB中的每一项由以下4个字段组成： 指令类型 指出该指令是分支指令、store指令或寄存器操作指令。 目标地址 给出指令执行结果应写入的目标寄存器号（如果是load和ALU指令）或存储器单元的地址（如果是store指令）。 数据值字段 用来保存指令前瞻执行的结果，直到指令得到确认。 就绪字段 指出指令是否已经完成执行并且数据已就绪。 ``` ### Slide 95 - 确认阶段 ``` 对分支指令、store指令以及其他指令的处理不同： 其他指令（除分支指令和store指令） 当该指令到达ROB队列的头部而且其结果已经就绪时，就把该结果写入该指令的目标寄存器，并从ROB中删除该指令。 store指令 处理与上面类似，只是它把结果写入存储器。 分支指令 当预测错误的分支指令到达ROB队列的头部时，清空ROB，并从分支指令的另一个分支重新开始执行。（错误的前瞻执行） 当预测正确的分支指令到达ROB队列的头部时，该指令执行完毕。 异常指令（实现精确异常） 在该指令到达ROB头部前不处理，到达ROB头部时，产生中断，清空ROB，此操作能够完成精确的异常处理。但凡刷新ROB，连同指令队列一起刷新，因为假如指令队列中有指令已经是有问题的指令流。 ``` --- ## 李宏图老师（lht） ### Slide 7 - 数据相关 ``` 数据相关 对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。 指令j使用指令i产生的结果； 指令j与指令k数据相关，而指令k又与指令i数据相关。 数据相关具有传递性。 数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。 ``` ### Slide 10 - 名相关 ``` （2）名相关 名：指令所访问的寄存器或存储器单元的名称。 如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。 指令j与指令i之间的名相关有两种： 反相关：如果指令j写的名与指令i读的名相同，则称指令i和j发生了反相关。 指令j写的名＝指令i读的名 输出相关：如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。 指令j写的名＝指令i写的名 ``` ### Slide 11 - 换名技术 ``` 名相关的两条指令之间并没有数据的传送。 如果一条指令中的名改变了，并不影响另外一条指令的执行。 换名技术 换名技术：通过改变指令中操作数的名来消除名相关。 对于寄存器操作数进行换名称为寄存器换名。 既可以用编译器静态实现，也可以用硬件动态完成。 ``` ### Slide 13 - 控制相关 ``` （3）控制相关 控制相关是指由分支指令引起的相关。 为了保证程序应有的执行顺序，必须严格按控制相关确定的顺序执行。 典型的程序结构是"if-then"结构。 ``` ### Slide 16 - 程序顺序 ``` 程序顺序：由源程序确定的在完全串行方式下指令的执行顺序。 对于正确地执行程序来说，必须保持的最关键的两个属性是：数据流和异常行为。 保持异常行为是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。 即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。 弱化为：指令执行顺序的改变不能导致程序中发生新的异常。 如果我们能做到保持程序的数据相关和控制相关，就能保持程序的数据流和异常行为。 数据流：指数据值从其产生者指令到其消费者指令的实际流动。 分支指令使得数据流具有动态性，因为它使得给定指令的数据可以有多个来源。 仅仅保持数据相关性是不够的，只有再加上保持控制顺序，才能够保持程序顺序。 ``` ### Slide 30-31 - 控制冲突 ``` 控制冲突 执行分支指令的结果有两种 分支成功：PC值改变为分支转移的目标地址。在条件判定和转移地址计算都完成后，才改变PC值。 不成功或者失败：PC的值保持正常递增，指向顺序的下一条指令。 处理分支指令最简单的方法："冻结"或者"排空"流水线 。 优点：简单。 前述5段流水线中，改变PC值是在MEM段进行的。 给流水线带来了3个时钟周期的延迟。 ``` ### Slide 35-37 - 延迟分支 ``` 预测分支成功 假设分支转移成功，并从分支目标地址处取指令执行。 起作用的前题：先知道分支目标地址，后知道分支是否成功。前述5段流水线中，这种方法没有任何好处。 延迟分支 主要思想： 从逻辑上"延长"分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成，不管分支是否成功，都要按顺序执行延迟槽中的指令。 分支延迟指令的调度 任务：在延迟槽中放入有用的指令。 由编译器完成。能否带来好处取决于编译器能否把有用的指令调度到延迟槽中。 三种调度方法： 从前调度 从目标处调度 从失败处调度 ``` ### Slide 38 - 三种方法的要求及效果 ``` 三种方法的要求及效果 调 度 策 略 对调度的要求 什么情况下起作用 从 前 调 度 必须保证在分支失败时执行被调度　的指令不会导致错误。有可能需要　复制指令 任何情况 从目标处调度 被调度的指令必须与分支无关 分支成功时(但由于复制指令，有　可能会增大程序空间) 从失败处调度 必须保证在分支成功时执行被调度　的指令不会导致错误 分支失败时 ``` ### Slide 50-53 - 记分牌算法 ``` 1. 采用记分牌机制的动态调度 记分牌机制： 在没有资源冲突的前提下，尽可能早地执行其他没有数据相关的指令。 允许指令乱序执行的一种技术。 2. 采用记分板的DLX基本结构 每条指令都从记分板通过，由记分板决定何时发射，何时取得操作数以及执行指令。 若判断读出的指令当前还不能执行，那么它会监视硬件上的每一个变化，并决定该指令何时才能执行。 最后控制写回目的寄存器的操作。 3. 记分板记录并管理三张表： 指令状态表 记录每条指令当前状态 分4个阶段：发射、读操作数、执行完成和写回结果 功能部件状态表 每个工作部件是否在使用？在做何种操作？ 给出一份操作记录 寄存器结果状态表 表中条目数与寄存器个数相等 记录哪个功能部件将写入这个寄存器 ``` ### Slide 74 - 限制记分板机制性能的因素 ``` 限制记分板机制性能的因素： 指令中可开发的并行性　——决定了有多少独立的指令能够被发掘出来并行执行 记分板部件的入口数　——影响到流水线可以提前查找独立不相关指令的能力 功能部件的数量与类型　——影响到资源冒险的可能性 反相关和输出相关的存在　——会导致WAR冒险和WAW冒险 ``` ### Slide 78 - Tomasulo核心思想 ``` 核心思想 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小； 通过寄存器换名来消除WAR冲突和WAW冲突。 ``` ### Slide 91 - Tomasulo算法优点 ``` 5.Tomasulo算法具有两个主要的优点： ①冲突检测和指令执行控制是分布的。 每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。 计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。 ②消除了WAW冲突和WAR冲突导致的停顿 使用保留站进行寄存器换名，并且操作数一旦就绪就将之放入保留站。 ``` ### Slide 127 - Tomasulo要点总结 ``` 9.Tomasulo的要点总结 ① 指令按照程序原有的顺序进入指令队列，并按照原有的顺序流出指令队列，但是并不一定按照原有的顺序执行。 ② 操作数未就绪的指令在保留站中等待，操作数就绪的指令可以先被执行。 ③ 通过寄存器换名技术消除了名相关，从而解决了读后写和写后写冲突。换了什么名呢？把流出到保留站中的指令的操作数寄存器换成了操作数，或者产生该操作数的保留站号。 ④ 指令能够流出、执行和写结果这三步的进入条件请看详细的算法，但是还有一个隐含条件，即没有结构冲突。 ⑤ Tomasulo算法只能处理结构冲突和数据冲突，不能处理异常和控制冲突。 ⑥ 在算法中，有两个地方容易忽视，需要格外注意：一个是从Load/store指令要按照FIFO次序访存；另一个是，store指令执行阶段和写结果阶段进入的条件。 ``` ### Slide 129-132 - 动态分支预测技术 ``` 什么是动态分支预测 优点： 根据程序的执行过程动态地改变转移的预测方向，因此有更好的准确度和适应性。 程序每次执行时，可能预测的分支方向与前次相同或不同。 以上预测机制的性能随着复杂性与硬件的增加而有效地提高。 从简单到复杂的动态转移预测技术如下： 分支预测缓存器（BHT） 分支目标缓冲器（BTB） 基于硬件的前瞻执行(ROB) 动态分支预测技术： 通过硬件技术，在程序执行时根据每一条转移指令过去的转移历史记录来预测下一次转移的方向。通过提前预测分支方向，减少或消除控制相关导致的流水线停顿。 1. 动态分支预测技术和静态分支预测技术的区别 静态分支预测技术所进行的操作事先预定好的 ，与分支的实际执行情况无关； 动态分支预测技术的方法在程序运行时根据分支执行过去的表现预测其将来的行为（如果分支行为发生了变化，预测结果也跟着改变，此外有更好的预测准确度和适应性）。 2. 什么是"分支指令过去的表现"？ 就是记录分支的历史信息，在预测错误时，要作废已经预取和分析的指令，恢复现场，为了恢复现场，需要在执行预测的目标指令之前将现场保存起来。 3.分支预测的有效性取决于： 预测的准确性 预测正确和不正确两种情况下的分支开销 4.采用动态分支预测技术的目的 预测分支是否成功 尽快找到分支目标地址（或指令） （避免控制相关造成流水线停顿） 5. 需要解决的关键问题 如何记录分支的历史信息； 如何根据这些分支的历史信息来预测分支的去向（甚至取到指令）。 ``` ### Slide 148-150 - BTB举例 ``` 5. 举例： 假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。 （1） 求程序执行的CPI。 （2） 相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？ 解： （1）程序执行的CPI = 没有分支的基本CPI（1） + 分支带来的额外开销 分支带来的额外开销是指在分支指令中，缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。 分支带来的额外开销= 15% * (90%命中×10%预测错误×4 + 10％没命中×3)= 0.099 所以，程序执行的CPI ＝ 1 ＋ 0.099 = 1.099 （2）采用固定的2 个时钟周期延迟的分支处理CPI = 1 + 15%×2 = 1.3 由（1）（2）可知分支目标缓冲方法执行速度快。 ``` ### Slide 154-156 - 基于硬件的前瞻执行 ``` 前瞻执行（speculation）的基本思想： 对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取出、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，而是放到一个称为ROB（ReOrder Buffer）的缓冲器中。等到相应的指令得到"确认"（commit）（即确实是应该执行的）之后，才将结果写入寄存器或存储器。 目的：在猜测错误时能够恢复现场（即没有进行不可恢复的写操作） 动态预测+猜测执行+保留站技术 为了得到更高的并行性，将动态转移预测技术与Tomasulo结合，设计出了前瞻执行方法：处理器按转移预测方向，乱序执行推测的指令序列，如果预测正确，就能够消除控制相关的延迟。也解决了数据相关和消除名相关。如果预测错误，则废弃已经执行的指令序列，从另一个分支处重新开始执行。 基于硬件的前瞻执行结合了三种思想： ① 动态分支预测。用来选择后续执行的指令。 ② 在控制相关的结果尚未出来之前，前瞻地执行后续指令。 ③ 用动态调度对基本块的各种组合进行跨基本块的调度。（基本程序块：如果 一串连续的代码除了入口和出口以外，不包含其他分支指令和转入点。） 实质是数据流执行(data flow execution)：只要操作数有效，指令就执行 ``` ### Slide 158 - 前瞻执行汇总 ``` 汇总：前瞻执行的基本思想 顺序流出指令队列； 猜测路径和乱序执行； 顺序确认（保证顺序写回）； 猜错或发生异常，没写回的全部不算数。 ``` ### Slide 169 - 前瞻执行例题 ``` 例题： 假设浮点功能部件的延迟时间为：加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。对于下面的代码段，给出当指令MUL.D即将确认时的状态表内容。 L.D F6,34（R2） L.D F2,45（R3） MUL.D F0,F2,F4 SUB.D F8,F6,F2 DIV.D F10,F0,F6 ADD.D F6,F8,F2 ``` ### Slide 182-183 - 超标量与VLIW ``` 多流出处理机有两种基本风格的比较： 超标量（Super scalar） 在每个时钟周期流出的指令条数不固定，依代码的具体情况而定。（有上限） 设这个上限为n，就称该处理机为n流出（或称为n路）。 可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度。 超长指令字VLIW（Very Long Instruction Word） 在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包。 指令包中，指令之间的并行性是通过指令显式地表示出来的。 指令调度是由编译器静态完成的。 超标量处理机与VLIW处理机相比有两个优点： 超标量结构对程序员是透明的，因为处理机能自己检测下一条指令能否流出，从而不需要重新排列指令来满足指令的流出。 即使是没有经过编译器针对超标量结构进行调度优化的代码或是旧的编译器生成的代码也可以运行，当然运行的效果不会很好。 ``` ### Slide 196-199 - 多流出技术例题 ``` 例1： 对于采用了Tomasulo算法和多流出技术的MIPS流水线，考虑以下简单循环的执行。该程序把F2中的标量加到一个向量的每个元素上。 Loop: L.D F0, 0（R1） // 取一个数组元素放入F0 ADD.D F4, F0, F2 // 加上在F2中的标量 S.D F4, 0（R1） // 存结果 DADDIU R1,R1，#-8 // 将指针减少8（每个数据占8个字节） BNE R1,R2,Loop // 若R1不等于R2，表示尚未结束，转移到Loop继续 现做以下假设： ①每个时钟周期能流出一条整数指令和一条浮点指令，即使它们相关也是如此。 ②有一个整数部件，用于整数ALU运算和地址计算； 并且对于每一种浮点操作类型都有一个独立的流水化了的浮点功能部件。 ③指令流出和写结果各占用一个时钟周期。 ④具有动态分支预测部件和一个独立的计算分支条件的功能部件。 ⑤分支指令单独流出，没有采用延迟分支，但分支预测是完美的。分支指令完成前，其后续指令只能被取出和流出，但不能执行。 ⑥因为写结果占用一个时钟周期，所以产生结果的延迟为：整数运算1个周期，load为2个周期，浮点加法运算3个周期。 ``` ### Slide 207-208 - VLIW例题 ``` 3.例题 假设VLIW处理机每个时钟周期可同时流出5条指令：两条访存指令、两条浮点操作指令和一条整数指令或分支指令。对于例1中的循环展开后的代码，给出它在该VLIW中的代码序列。不考虑分支指令的延迟槽。 L.D F0,0(R1) L.D F6,-8(R1) L.D F10,-16(R1) L.D F14,-24(R1) L.D F18,-32(R1) ADD.D F4,F0,F2 ADD.DF8,F6,F2 ADD.DF12,F10,F2 ADD.DF16,F14,F2 ADD.DF20,F18,F2 S.D F4,0(R1) S.D F8,-8(R1) S.D F12,-16(R1) S.D F16,–24(R1) DADDIUR1,R1,#-40 S.D F20,8(R1) BNE R1,R2,Loop Loop ``` ### Slide 210 - VLIW运行结果 ``` 运行时间为8个时钟周期。 每遍循环平均1.6个时钟周期。 8个时钟周期内流出了17条指令，每个时钟周期17/8=2.1条。 8个时钟周期共有操作槽8×5=40个，有效槽的比例为(3*5+2)/40=42.5%。 ``` ### Slide 211 - VLIW存在的问题 ``` 4.VLIW存在的一些问题 程序代码长度增加了 提高并行性而进行的大量的循环展开。 指令字中的操作槽并非总能填满。 解决：采用指令共享立即数字段的方法，或者采用指 令压缩存储、调入Cache或译码时展开的方法。 采用了锁步机制 没有冲突检测硬件，并且所有功能部件同步操作，因而，任何一个操作部件出现停顿时，整个处理机都要停顿。 机器代码的不兼容性 配置不同的VLIW中，机器代码不能移植，而超标量处理及则可移植。 ``` --- ## 谭婧炜佳老师（tjwj） ### Slide 7 - 流水线的相关与冲突 ``` 流水线的相关与冲突 相关：两条指令之间存在某种依赖关系。（静态属性） 数据相关、名相关、控制相关 冲突：是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。（动态属性） 结构冲突、数据冲突、控制冲突 ``` ### Slide 8-9 - 数据相关 ``` 数据相关：（也称真数据相关）(RAW: read after write) 对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。 指令j使用指令i产生的结果； 指令j与指令k数据相关，而指令k又与指令i数据相关。 数据相关具有传递性。 数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。 当数据的流动是经过寄存器时，相关的检测比较直观和容易。 当数据的流动是经过存储器时，检测比较复杂。 相同形式的地址其有效地址未必相同。 形式不同的地址其有效地址却可能相同。 ``` ### Slide 11 - 名相关 ``` 名相关： 名：指令所访问的寄存器或存储器单元的名称。 如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。 指令j与指令i之间的名相关有两种： 反相关：如果指令j写的名与指令i读的名相同，则 称指令i和j发生了反相关。(WAR: write after read) 指令j写的名＝指令i读的名 输出相关：如果指令j和指令i写相同的名，则称指 令i和j发生了输出相关。(WAW: write after write) 指令j写的名＝指令i写的名 ``` ### Slide 12 - 思考：为什么会出现名相关？ ``` 思考：为什么会出现名相关？ 物理寄存器数量有限 ``` ### Slide 13 - 换名技术 ``` 名相关的两条指令之间并没有数据的传送。 执行顺序必须不能颠倒->保证正确性 如果一条指令中的名改变了，并不影响另外一条指令的执行。 换名技术 换名技术：通过改变指令中操作数的名来消除名相关。 对于寄存器操作数进行换名称为寄存器换名。 既可以用编译器静态实现，也可以用硬件动态完成。 区别？ ``` ### Slide 17 - 流水线冲突 ``` 流水线冲突 流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。 流水线冲突有3种类型： 结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。 数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。 控制冲突：流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。 ``` ### Slide 18 - 冲突带来的问题 ``` 冲突带来的问题 导致错误的执行结果。 流水线可能会出现停顿，从而降低流水线的效率和实际的加速比。 我们约定： 当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行（否则就永远无法消除冲突）。 ``` ### Slide 19-23 - 结构冲突 ``` 结构冲突 在流水线处理机中，为了能够使各种组合的指令都能顺利地重叠执行，需要对功能部件进行流水或重复设置资源。 如果某种指令组合因为资源冲突而不能正常执行，则称该处理机有结构冲突。 常见的导致结构相关的原因： 功能部件不是完全流水（瓶颈段） 资源份数不够（寄存器组只有一个端口port） 结构冲突举例：访存冲突 有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致访存冲突。 解决办法Ⅰ：插入暂停周期（"流水线气泡"或"气泡"） 解决方法Ⅱ：设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。 有时流水线设计者允许结构冲突的存在 主要原因：减少硬件成本 ``` ### Slide 24-26 - 数据冲突 ``` 数据冲突 当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们非流水实现时的顺序，则发生了数据冲突。（发生错误） 数据冲突的类型 根据指令读访问和写访问的顺序，可以将数据冲突分为3种类型。 考虑两条指令i和j ，且i在j之前进入流水线，可能发生的数据冲突有： 写后读冲突（RAW）最常见，对应真数据相关 在 i 写入之前，j 先去读。 j 读出的内容是错误的。 写后写冲突（WAW）对应输出相关 在 i 写入之前，j 先写。 最后写入的结果是 i 的。错误！ 读后写冲突（WAR）由反相关引起 在 i 读之前，j 先写。 i 读出的内容是错误的！ ``` ### Slide 27 - 控制冲突 ``` 控制冲突 执行分支指令的结果有两种 分支成功：PC值改变为分支转移的目标地址。 在条件判定和转移地址计算都完成后，才改变PC值。 不成功或者失败：PC的值保持正常递增，指向顺序的下一条指令。 处理分支指令最简单的方法： "冻结"或者"排空"流水线 。 优点：简单。 ``` ### Slide 28 - 通过软件减少分支延迟的方法 ``` 通过软件（编译器）减少分支延迟的方法 ①预测分支失败 ②预测分支成功 ③延迟分支 共同点： 对分支的处理方法在程序的执行过程中始终是不变的，是静态的。 要么总是预测分支成功，要么总是预测分支失败。 ④循环展开 ``` ### Slide 31-32 - 指令级并行的概念 ``` 指令级并行的概念 几乎所有的处理机都利用流水线来使指令重叠并行执行，以达到提高性能的目的。这种指令之间存在的潜在并行性称为指令级并行。（ILP：Instruction-Level Parallelism） 指令级并行ILP概念：是指存在于指令一级即指令间的并行性, 主要是指机器语言一级，如存储器访问指令、整型指令、浮点指令之间的并行性等。 指令级并行主要特点：是并行性由处理器硬件和编译程序自动识别和利用，不需要程序员对顺序程序作任何修改。正是由于这一优点，使得它的发展与处理器的发展紧密相连。 本章研究：如何通过各种可能的技术，获得更多的指令级并行性。 硬件＋软件技术 必须要硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行。 ``` ### Slide 33 - 开发指令级并行的重要性 ``` 开发指令级并行的重要性 理想CPI（无冲突）是衡量流水线最高性能的一个指标 实际CPI往往远大于理想CPI，它是理想流水线的CPI加上各类停顿的时钟周期数： CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突 减少等式右端的各项就减少了总的CPI,从而提高IPC.（Instructions Per Cycle：每个时钟周期完成的指令条数） ``` ### Slide 34 - 开发指令级并行需要解决的具体问题 ``` 开发指令级并行需要解决的具体问题 相关与冲突 两类解决方法 保持相关，但避免发生冲突 指令调度 依靠编译器静态调度 通过代码变换，消除相关 寄存器重命名 寄存器换名消除WAR和WAW ``` ### Slide 49 - 静态调度 V.S. 动态调度 ``` 静态调度 V.S. 动态调度 静态调度：是依靠编译器对代码进行调度，也就是在代码被执行之前进行调度；通过把相关的指令拉开距离来减少可能产生的停顿。 动态调度：在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。 指令顺序执行 V.S. 指令乱序执行 指令顺序执行：指令放入流水线的顺序和指令完成的顺序一致； 指令乱序执行：指令放入流水线的顺序和指令完成的顺序不一致，也就是说有些指令进入流水线后被阻塞的，而在其后进入流水线的指令先完成了。 ``` ### Slide 50-51 - 动态调度的基本思想 ``` 动态调度的基本思想 到目前为止我们所使用流水线的最大的局限性: 指令必须按序流出和执行（in-order issue & execution） 考虑下面一段代码： DIV.D F4，F0，F2 SUB.D F10，F4，F6 ADD.D F12，F6，F14 SUB.D指令与DIV.D指令关于F4相关，导致流水线停顿。 ADD.D指令与流水线中的任何指令都没有关系，但也因此受阻。 DIV.D指令执行需要20时钟周期的延迟时间 在前面的基本流水线中： 一旦一条指令受阻，其后的指令都将停顿。 解决办法：允许乱序执行 ``` ### Slide 52 - 乱序执行 ``` 乱序执行 为了允许乱序执行，我们将5段流水线的译码阶段(ID)再分为两个阶段： 流出（Issue，IS）：指令译码，检查是否存在结构冲突。 （in-order issue) 读操作数（Read Operands，RO）：等待数据冲突消失，然后读操作数。 (out of order execution) ``` ### Slide 53 - 乱序执行所带来的问题 ``` 乱序执行所带来的问题 在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。 例如，考虑下面的代码 DIV.D F10, F0, F2 SUB.D F10, F4, F6 ADD.D F6, F8, F14 F10存在输出相关 F6存在反相关 可以通过使用寄存器重命名来消除 ``` ### Slide 54 - 动态调度基本思想小结 ``` 动态调度基本思想小结 相对于静态指令调度 ，动态指令调度是在指令的执行过程中进行调度，使得无关的指令得以先执行，减少阻塞； 能够处理一些在编译时情况不明的相关（如存储器访问的相关）； 能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行； 动态指令调度将会引起指令乱序执行，因此，使用换名技术消除名相关（包括反相关和输出相关）； 指令乱序完成使得异常处理困难； 以硬件复杂性的显著增加为代价。 ``` ### Slide 56 - Tomasulo算法 ``` Tomasulo算法 核心思想 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小； 通过寄存器换名来消除WAR冲突和WAW冲突。 IBM 360/91首先采用了Tomasulo算法。 IBM 360/91的设计目标是基于整个360系列的统一指令集和编译器来实现高性能，而不是设计和利用专用的编译器来提高性能。 需要更多地依赖于硬件。 IBM 360体系结构只有4个双精度浮点寄存器，限制了编译器调度的有效性。 360/91的访存时间和浮点计算时间都很长。（也是Tomasulo算法要解决的问题） ``` ### Slide 68 - Tomasulo算法特点 ``` Tomasulo算法 Tomasulo算法具有以下两个特点： 冲突检测和指令执行控制是分布的。 每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。 计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。 使用Tomasulo算法的流水线需3段： 流出 执行 写结果 ``` ### Slide 73 - Tomasulo算法的两个主要优点 ``` Tomasulo算法的两个主要优点 冲突检测逻辑是分布的 （通过保留站和CDB实现） 如果有多条指令已经获得了一个操作数，并同时在等待同一运算结果，那么这个结果一产生，就可以通过CDB同时播送给所有这些指令，使它们可以同时执行。 消除了WAW冲突和WAR冲突导致的停顿 使用保留站进行寄存器换名，并且操作数一旦就绪就将之放入保留站。 ``` ### Slide 87 - Tomasulo算法限制 ``` 该算法对于指令的执行有个限制，就是如果流水线中还有分支指令没有执行，那么当前指令就不能进入"执行"阶段。这是因为在"流出"阶段后，程序顺序就不再被保证了。所以，为了保持正确的异常行为，必须加上这个限制。 ``` ### Slide 108-112 - 动态分支预测技术 ``` 动态分支预测技术 所开发的ILP越多，控制相关的制约就越大，分支预测就要有更高的准确度。 动态分支预测技术：通过硬件技术，在程序执行时根据每一条转移指令过去的转移历史记录来预测下一次转移的方向。通过提前预测分支方向，减少或消除控制相关导致的流水线停顿。 优点： 根据程序的执行过程动态地改变转移的预测方向，因此有更好的准确度和适应性。 程序每次执行时，可能预测的分支方向与前次相同或不同。 分支预测的有效性取决于： 预测的准确性 预测正确和不正确两种情况下的分支开销 决定分支开销的因素： 流水线的结构 预测的方法 预测错误时的恢复策略等 采用动态分支预测技术的目的 预测分支是否成功 尽快找到分支目标地址（或指令） （避免控制相关造成流水线停顿） 需要解决的关键问题 如何记录分支的历史信息； 如何根据这些信息来预测分支的去向（甚至取到指令）。 从简单到复杂的动态转移预测技术如下： 分支预测缓存器（BHT） 分支目标缓冲器（BTB） 基于硬件的前瞻执行(ROB) 以上预测机制的性能随着复杂性与硬件的增加而有效地提高。 ``` ### Slide 113-118 - BHT ``` 分支历史表 BHT 分支历史表BHT（Branch History Table）或分支预测缓冲器（Branch Prediction Buffer） 最简单的动态分支预测方法。 用BHT来记录分支指令最近一次或几次的执行情况（成功或不成功），并据此进行预测。 只有1个预测位的分支预测缓冲 　　记录分支指令最近一次的历史，BHT中只需要1位二进制位。 　（最简单） 采用两位二进制位来记录历史 提高预测的准确度 研究结果表明：两位分支预测的性能与n位（n>2）分支预测的性能差不多。 两位分支预测的状态转换如下所示： 两位分支预测中的操作有两个步骤： 分支预测。 当分支指令到达译码段（ID）时，根据从BHT读出的信息进行分支预测。 若预测正确，就继续处理后续的指令，流水线没有断流。否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。 状态修改。 BHT方法只在以下情况下才有用： 判定分支是否成功所需的时间大于确定分支目标地址所需的时间。 前述5段经典流水线：由于判定分支是否成功和计算分支目标地址都是在ID段完成，所以BHT方法不会给该流水线带来好处。 研究结果表明：对于SPEC89测试程序来说，具有大小为4K的BHT的预测准确率为82%～99%。 一般来说，采用4K的BHT就可以了。 ``` ### Slide 119-124 - BTB ``` 分支目标缓冲器BTB 目标：将分支的开销降为 0 方法：分支目标缓冲 将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识。 这个缓冲区就是分支目标缓冲器（Branch-Target Buffer，简记为BTB，或者Branch-Target Cache）。 BTB的结构 看成是用专门的硬件实现的一张表格。 表格中的每一项至少有两个字段： 执行过的成功分支指令的地址； （作为该表的匹配标识 ） 预测的分支目标地址。 采用BTB后，在流水线各个阶段所进行操作 采用BTB后，各种可能情况下的延迟 BTB的另一种形式 在分支目标缓冲器中存放一条或者多条分支目标处的指令，而非地址。 有三个潜在的好处： 更快地获得分支目标处的指令； 可以一次提供分支目标处的多条指令，这对于多流出处理器是很有必要的； 使我们可以进行称为分支折叠（branch folding）的优化。 实现零延迟无条件分支，甚至有时还可以做到零延迟条件分支。（直接将目标指令送到ID段，避免执行分支指令本身） ``` ### Slide 125-133 - 基于硬件的前瞻执行 ``` 基于硬件的前瞻执行 前瞻执行（speculation）的基本思想： 对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，而是放到一个称为ROB（ReOrder Buffer）的缓冲器中。等到相应的指令得到"确认"（commit）（即确实是应该执行的）之后，才将结果写入寄存器或存储器。 前瞻执行的基本步骤： 流出、执行、写结果、确认四个阶段 顺序流出、准备好的先执行（乱序执行），顺序确认 分支预测错误，刷新ROB 异常指令到达ROB头部，刷新ROB 基于硬件的前瞻执行结合了三种思想： 动态分支预测。用来选择后续执行的指令。 在控制相关的结果尚未出来之前，前瞻地执行后续指令。 用动态调度对基本块的各种组合进行跨基本块的调度。 对Tomasulo算法加以扩充，就可以支持前瞻执行。 把Tomasulo算法的写结果和指令完成加以区分，分成两个不同的段： 写结果，指令确认 实现前瞻的关键思想： 允许指令乱序执行，但必须顺序确认。 写结果段 把前瞻执行的结果写到ROB中； 通过CDB在指令之间传送结果，供需要用到这些结果的指令使用。 指令确认段 在分支指令的结果出来后，对相应指令的前瞻执行给予确认。 如果前面所做的猜测是对的，把在ROB中的结果写到寄存器或存储器。 如果发现前面对分支结果的猜测是错误的，那就不予以确认，并从那条分支指令的另一条路径开始重新执行。 ROB中的每一项由以下4个字段组成： 指令类型 指出该指令是分支指令、store指令或寄存器操作指令。 目标地址 给出指令执行结果应写入的目标寄存器号（如果是load和ALU指令）或存储器单元的地址（如果是store指令）。 数据值字段 用来保存指令前瞻执行的结果，直到指令得到确认。 就绪字段 指出指令是否已经完成执行并且数据已就绪。 Tomasulo算法中保留站的换名功能是由ROB来完成的。 采用前瞻执行机制后，指令的执行步骤 流出 从浮点指令队列的头部取一条指令。 如果有空闲的保留站（设为r）且有空闲的ROB项（设为b），就流出该指令，并把相应的信息放入保留站r和ROB项b。 如果保留站或ROB全满，便停止流出指令，直到它们都有空闲的项。 执行 如果有操作数尚未就绪，就等待，并不断地监测CDB。 (检测RAW冲突) 当两个操作数都已在保留站中就绪后，就可以执行该指令的操作。 写结果 当结果产生后，将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上，经CDB写到ROB以及所有等待该结果的保留站。 释放产生该结果的保留站。 store指令在本阶段完成，其操作为: 如果要写入存储器的数据已经就绪，就把该数据写入分配给该store指令的ROB项。 否则，就监测CDB，直到那个数据在CDB上播送出来，这时才将之写入分配给该store指令的ROB项。 确认 对分支指令、store指令以及其他指令的处理不同： 其他指令（除分支指令和store指令） 当该指令到达ROB队列的头部而且其结果已经就绪时，就把该结果写入该指令的目标寄存器，并从ROB中删除该指令。 store指令 处理与上面类似，只是它把结果写入存储器。 分支指令 当预测错误的分支指令到达ROB队列的头部时，清空ROB，并从分支指令的另一个分支重新开始执行。（错误的前瞻执行） 当预测正确的分支指令到达ROB队列的头部时，该指令执行完毕。 ``` ### Slide 134-135 - 前瞻执行示例 ``` 前瞻执行示例 例 假设浮点功能部件的延迟时间为：加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。对于下面的代码段，给出基于Tomasulo算法的前瞻执行的执行过程。 L.D F6,34（R2） L.D F2,45（R3） MUL.D F0,F2,F4 SUB.D F8,F6,F2 DIV.D F10,F0,F6 ADD.D F6,F8,F2 ``` ### Slide 167 - 前瞻执行小结 ``` 前瞻执行小结 通过ROB实现了指令的顺序完成。 能够实现精确异常。 很容易地推广到整数寄存器和整数功能单元上。 主要缺点：所需的硬件太复杂。 ``` ### Slide 170-171 - 超标量与VLIW ``` 多指令流出技术 超标量（Super scalar） 在每个时钟周期流出的指令条数不固定，依代码的具体情况而定。（有上限） 设这个上限为n，就称该处理机为n流出（或称为n路）。 可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度。 超长指令字VLIW（Very Long Instruction Word） 在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包。 指令包中，指令之间的并行性是通过指令显式地表示出来的。 指令调度是由编译器静态完成的。 超标量的优点 超标量结构对程序员是透明的，因为处理机能自己检测下一条指令能否流出，从而不需要重新排列指令来满足指令的流出。 即使是没有经过编译器针对超标量结构进行调度优化的代码或是旧的编译器生成的代码也可以运行，当然运行的效果不会很好。要想达到很好的效果，方法之一是使用动态超标量调度技术。 ``` ### Slide 172-174 - 静态超标量处理器 ``` 基于静态调度的多流出技术 静态超标量处理器 在典型的超标量处理器中，每个时钟周期可流出1到8条指令。 指令按序流出，在流出时由流出部件进行冲突检测（依靠硬件）。 在当前流出的指令序列中，不存在数据冲突或者结构冲突 静态超标量处理器举例 一个4流出的静态调度超标量处理机 在取指令阶段，流水线将从取指令部件收到1～4条指令（称为流出包）。 在一个时钟周期内，这些指令有可能是全部都能流出（4条指令都不存在冲突），也可能是只有一部分能流出（有冲突）。 流出部件检测结构冲突或者数据冲突。 由于检测冲突的复杂性，一个时钟难以完成，把它分成多个流水段按流水方式工作。 一般分两阶段实现： 第一阶段：进行流出包内的冲突检测，选出初步判定可以流出的指令。 第二阶段：检测所选出的指令与正在执行的指令是否有冲突。 ``` ### Slide 177 - 限制超标量流水线性能发挥的障碍 ``` 限制超标量流水线的性能发挥的障碍。 load指令1个时钟延迟 load后续3条指令（同时流出的和下一时钟流出的两条指令）都不能使用其结果，否则就会引起停顿。因为，load指令有一个时钟周期的延迟，其后继的、并使用其结果的指令要停顿一个时钟周期流出。 分支延迟 1个时钟 前面简单的流水线，分支延迟为一个时钟周期 如果分支指令是流出包中的第一条指令，则其延迟是3个时钟周期； 否则就是流出包中的第二条指令，其延迟就是2个时钟周期。 综上分析：为了有效利用超标量处理机的并行性，需要更有效的编译技术和硬件跳读技术（循环展开，Tomasulo及前瞻） ``` ### Slide 179 - 基于动态调度的多流出技术 ``` 基于动态调度的多流出技术 动态超标量处理器 静态调度性能提高较少，因此，采用动态调度。 扩展Tomasulo算法：支持两路超标量 每个时钟周期流出两条指令； 一条是整数指令，另一条是浮点指令。 采用一种比较简单的方法： 指令按顺序流向保留站，否则会破坏程序语义。 将整数所用的表结构与浮点数用的表结构分离开，分别进行处理，这样就可以同时地流出一条浮点指令和一条整数指令到各自的保留站。 ``` ### Slide 181-183 - 多流出技术例题 ``` 例1： 对于采用了Tomasulo算法和多流出技术的MIPS流水线，考虑以下简单循环的执行。该程序把F2中的标量加到一个向量的每个元素上。 Loop: L.D F0, 0（R1） // 取一个数组元素放入F0 ADD.D F4, F0, F2 // 加上在F2中的标量 S.D F4, 0（R1） // 存结果 DADDIU R1,R1，#-8 // 将指针减少8（每个数据占8个字节） BNE R1,R2,Loop // 若R1不等于R2，表示尚未结束，转移到Loop继续 现做以下假设： ①每个时钟周期能流出一条整数指令和一条浮点指令，即使它们相关也是如此。 ②有一个整数部件，用于整数ALU运算和地址计算； 并且对于每一种浮点操作类型都有一个独立的流水化了的浮点功能部件。 ③指令流出和写结果各占用一个时钟周期。 ④具有动态分支预测部件和一个独立的计算分支条件的功能部件。 ⑤分支指令单独流出，没有采用延迟分支，但分支预测是完美的。分支指令完成前，其后续指令只能被取出和流出，但不能执行。 ⑥因为写结果占用一个时钟周期，所以产生结果的延迟为：整数运算1个周期，load为2个周期，浮点加法运算3个周期。 列出该程序前面3遍循环中各条指令的流出、开始执行和将结果写到CDB上的时间。 说明： ①store和分支指令不经过写结果，因为他们不写寄存器 ②对load和store指令，在执行段进行有效地址计算 ③对于分支指令，在执行段进行转移条件判断，并检测分支预测是否正确。这里假设，它所用的操作数一旦就绪，就立即执行 ④注意：下一个循环迭代中的load指令比当前迭代的store指令先访问存储器。 ``` ### Slide 188-197 - VLIW ``` 超长指令字技术（VLIW） 思想： 把能并行执行的多条指令组装成一条很长的指令。（100多位到几百位） 设置多个功能部件。 指令字被分割成一些字段，每个字段称为一个操作槽（基本指令单元），直接独立地控制一个功能部件。 在VLIW处理机中，所有的处理和指令安排都是由编译器完成的。 VLIW体系结构 特点：控制逻辑简单 3.例题 假设VLIW处理机每个时钟周期可同时流出5条指令：两条访存指令、两条浮点操作指令和一条整数指令或分支指令。对于例1中的循环展开后的代码，给出它在该VLIW中的代码序列。不考虑分支指令的延迟槽。 L.D F0,0(R1) L.D F6,-8(R1) L.D F10,-16(R1) L.D F14,-24(R1) L.D F18,-32(R1) ADD.D F4,F0,F2 ADD.DF8,F6,F2 ADD.DF12,F10,F2 ADD.DF16,F14,F2 ADD.DF20,F18,F2 S.D F4,0(R1) S.D F8,-8(R1) S.D F12,-16(R1) S.D F16,–24(R1) DADDIUR1,R1,#-40 S.D F20,8(R1) BNE R1,R2,Loop Loop 运行时间为8个时钟周期。 每遍循环平均1.6个时钟周期。 8个时钟周期内流出了17条指令，每个时钟周期17/8=2.1条。 8个时钟周期共有操作槽8×5=40个，有效槽的比例为(3*5+2)/40=42.5%。 VLIW存在的问题 程序代码长度增加了 提高并行性而进行的大量的循环展开。 指令字中的操作槽并非总能填满。 解决：采用指令共享立即数字段的方法，或者采用指令压缩存储、调入Cache或译码时展开的方法。 采用了锁步机制 没有冲突检测硬件，并且所有功能部件同步操作，因而，任何一个操作部件出现停顿时，整个处理机都要停顿。 机器代码的不兼容性 配置不同的VLIW中，机器代码不能移植，而超标量处理及则可移植。 ```