计算机系统结构复习（五）：ILP指令集并行
指令集并行和两种方式基本快相关与从冲突的关系循环展开循环展开的注意事项 动态分支预测动态分支预测与静态分支预测的区别分支历史表BHT一位分支历史表二位分支历史表 相关分支预测器竞赛预测器分支目标缓冲BTB 动态调度记分牌算法（了解）Tomasulo 算法（了解） 前瞻技术与带有前瞻的Tomasulo 算法（了解思想）多流出/多发射--超标量和超长指令字 P142指令集并行和两种方式
ILP定义：当指令之间不存在相关，他们在流水线中可以重叠起来 并行执行，这种潜在的并行性称为指令级并行。
开发ILP的两种方法：
1.静态调度：利用编译器对代码进行静态调度，以减少相关 和冲突。是在编译期间而不是执行期间进行调度和优化。
2.动态调度：在程序执行过程中依靠硬件对代码进行调度。
基本快
定义：除入口和出口外没有其他分支的线性指令序列。BB内 部的指令可能相互依赖，且每4-7条指令就会有分支。为明显提升性能，开发ILP更多是在BB之间。
比如循环级并行（loop-level parallelism）采用循环展开：
for (i=1; i<=1000; i=i+1) （共1000个BB，ILP就是使得这1000个BB能并行计算）x[i] = x[i] + s //（一个循环中的不同循环体并行执行）
循环展开的两种方法：
1.静态循环展开：编译器静态调度指令
2.动态循环展开：动态分支预测
上一章的分支预测是静态
相关与从冲突的关系
相关：两条指令之间存在某种依赖关系（数据相关、名相关、 控制相关）
冲突: 在具体流水线中，由于相关的存在，使得指令流中下一 条指令不能在指定的时钟周期开始执行。
两者之间的关系：
相关性是程序的固有属性，反映了程序中指令之间的相互依赖 关系；具体的一次实际冲突的发生以及该冲突会带来多长的停顿，是流水线的特性；相关性的存在只预示着存在有冲突的可能性.
循环展开
循环展开和分支预测（动态）是解决分支问题的常用手段。
循环展开的注意事项
1.找到循环体的无关性。
2.使用不同的寄存器，避免冲突。
3.删除多余的测试指令和分支指令，并对相应代码进行修 正，减小开销。
4.注意load和store指令访问的存储器地址，如果是不同的， 则说明相互独立。
5.最后进行指令调度。
动态分支预测
动态分支预测与静态分支预测的区别
静态分支预测（第三章分支延迟槽）：预测操作都是预先 设定好的，预分支的实际执行情况无关。
动态分支预测：根据硬件动态进行处理，根据分支指令过 去的表现预测将来的行为。如果分支行为发生了变化，预 测结果也跟着改变，因此有更好的预测准确度和适应性。
分支历史表BHT
一位分支历史表
最简单的动态分支预测方法，利用BHT记录相关分支指令最近一次或几次的执行情况是成功还是失败。
1-bit的BHT存在的问题： 最后一次预测错误不可避免，因为前面分支总是成功 第一次预测错误是源于上次程序的执行，因为上一次程 序最后一次分支不成功。
两位分支预测可以解决上述问题，且性能与高位分支预测器相差不大，所以采用。
二位分支历史表
连续两次判断错误才修改预测。
2-bit的BHT存在的问题：
1.如果不止一个分支（branch）存在，前面的分支可能会影响后面的分支，即相关分支。
2.由于使用PC的低位置查找BHT表，可能得到错误的分支历史记录。
相关分支预测器
将其他邻近分支的历史结果也纳入考虑，进行预测。
一个（2,2）分支预测器，前2个分支的全局历史为：10， 即分支跳转成功、分支跳转失败。
图中 address 为不同分支 的地址，GBH记录类上一次运行时两个相关分支的 taken 情况。定位到具体状态是 01，根据二位分支历史表判断，说明预测为not taken。
竞赛预测器
看对方预测是否成功，连续两次对方预测正确我方预测错误则翻转。
分支目标缓冲BTB
BHT方法是在ID段末尾算出分支目标地址，并得到顺序 下一条指令地址及预测的结果。
BTB方法更提前一拍，在IF段就知道这些信息，分支开销 可以减少为0。表格包括两个字段：执行过的成功分支指 令地址；预测的分支指令地址。
在取指令时，用该指令地址与BTB中所有项的第一字段比 较，如果有匹配，说明上一次分支成功，推测这一次分支也成功，跳转到目标地址。否则按非分支指令执行。
BTB的另一种形式是增设一个分支历史表字段，这种方法 是普通BTB和BHT的结合。
下图为BTB的两种形式：
动态调度
动态调度与静态调度的区别
静态调度是在编译阶段（代码执行前）利用编译器对代码进行调度。如第三章的流水线。如果存在数据冲突且 无法通过重定等方法解决，只能停顿。
动态调度是在程序执行阶段利用硬件进行调度。同时还 能保证数据流和异常行为。
动态调度的优点
1.能够处理情况不明的相关（编译器无法检测出）。
2.一条指令的不同阶段可以在不同流水线中完成。
动态调度的基本思想
关键思想： 允许被stall的指令停顿期间执行后面的指令（顺序发射， 乱序执行，乱序完成）。
如下代码：
DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F12,F8,F14
DIVD 和 ADDD 之间有关于F0 存在 RAW，因此 ADDD 被stall，此时 SUBD 和两者不存在任何相关和冲突，因此硬件可以在ADDD的 stall 期间执行 SUBD。
上例具体实现
将ID段拆成两段：Issure 和 Read operands，前者检测结 构冲突，没有指令就发射；后者检测数据冲突，等到没有，就读操作数。
这种方法可能会引入WAR和WAW冲突。因此动态调度必 须能够检测出，或是采用寄存器更名的方法。
记分牌算法（了解）
记分牌的作用：
负责检测并控制指令的流出和执行。在 没有结构冲突时，尽早执行没有数据冲突的指令，实现 每个周期执行一条指令。
四个阶段
1.流出：功能部件空闲且正在执行的指令目的reg与该 指令不同时发射指令。（解决WAW）
2.读op：如果前面已发射的指令不对源操作数所在reg 进行写操作，就读取操作数。（解决RAW冲突）
3.执行
4.写回：检测是否存在WAR。没有写回，若有检测相关 指令是否已经读取操作数
Tomasulo 算法（了解）
核心思想：
1.记录和检测指令相关，操作数一旦就绪就立即执行， 将RAW冲突降低到最少。
2.利用reg换名消除WAR和WAW冲突。
记分牌和tomasulo比较
1.tomasulo 的控制和缓存分布在各保留站中 而记分牌中控制和缓存集中在记分牌
2.功能单元对操作数进行计算不再是从寄存器取数（记分牌），而是从保留站的操作数缓存中取数，减少RAW。
3.Reg换名
优点
1.冲突检测逻辑是分布的，如果多条指令已经获得一个操作数，在等同一运算结果。则结果产生时可同时传播这些指令。（通过保留站和CDB实 现）
2.消除了WAR和WAW冲突
缺点
1.实现复杂
2.需要大量的高速相联存储
3.性能受CDB影响大
前瞻技术与带有前瞻的Tomasulo 算法（了解思想）
前瞻技术的目的：
对于多流出处理机而言，只准确地预测分支已经不能满足要求，因为可能每个时钟周期都要执行一条分支指令。利用前瞻技术更好地解决控制相关。
核心思想：
循序处理器还未判断指令是否能执行 之前就提前执行，以克服控制相关。只要操作数 就绪，指令就执行。**执行结果写到ROB （ReOrder Buffer）**中，如果前瞻正确，结果写 回reg或存储器中；否则清空ROB，重新执行。
三种核心思想：
1.动态分支预测，用来选择后续执行的指令。
2.在控制相关的结果尚未出来之前，前瞻执行后续指令。
3.用动态调度对基本块的各种组合进行跨基本块调度。
特点：乱序执行，顺序确认。
方法：将写结果分为“写结果”和“指令确认”。
多流出/多发射–超标量和超长指令字 P142
多流出技术（Multiple issue）是指在一个时钟周期流出多条指令，进一步提升性能，使CPI小于1.
超标量：每个时钟周期流出的指令条数不固定，依代码情况而定。既可以通过编译器静态调度，又可以通Tomasulo算法动态调度。硬件复杂度提升。
超长指令字：每个时钟周期流出的指令条数固定，只能通过编译器静态调度。硬件复杂度下降。
