计算机体系结构（国防科大）-第四章-指令级并行_计算机系统结构 自由讨论

1 指令级并行概念

指令之间不存在相关时，它们在流水线中可以重叠起来并行执行。这种指令序列中存在潜在并行性称为指令级并行。

指令并行的一些基本概念：

• 基本（程序）块：一段除了入口和出口以外不包含其它分支的线性代码段。
  • 程序平均每6~7条指令就会有一个分支；
  • 必须在多个基本块之间开发指令级的并行性。
• 循环级并行：循环体中指令之间的并行性。
• 开发循环级并行的基本技术方法：
  • 指令调度（scheduling）
  • 循环展开(loop unrolling)
  • 换名(renaming)

循环展开调度的基本方法：

• 循环展开时，展开循环体若干次，将循环级并行转化为指令级并行技术；
• 这个过程既可以通过编译器静态完成，也可以通过硬件动态进行。
  • 开发循环级并行性的另外一个重要技术是向量处理技术；
  • 具有向量处理指令的典型机器是向量计算机，有关向量处理和向量计算机的内容本章不做讨论。
• 注意：本章中的分支指令就是条件转移指令。
• 编译器在完成这种指令调度时，受限于以下两个特性：
  • 程序固有的指令级并行性；
  • 流水线功能部件的执行延迟。

本章讨论的流水线其它特性说明：

• 整数流水线采用改进的MIPS整数流水线。
  • 数据的操作结果可以通过相关通路机制传送到数据存部件，所以延迟为0。
  • 定向通道或旁路机制。
• 分支指令，由整数流水线执行。
  • 分支条件检测调整到ID段；
  • 如果分支指令使用上一条指令的结果作为分支条件，将要延迟1节拍；
  • 分支指令有1节拍的延迟槽。
• 浮点运算一般为64位。
• 无结构冒险（结构冲突）。

循环展开总结：

• 对指令进行移动是有效的；
• 展开是有用的；
• 用不同的寄存器
  • 换名
  • 更多寄存器
• 消除额外的测试开销；
• 在循环展开时分析LOAD/STORE指令进行内存地址换名；
• 保留真相关（先写后读）。

2 指令的动态调度

冒险的检测和调度

• 如果数据存在相关，硬件检测机制会做如下的事情知道相关消除动态调度。
  • 暂停指令
  • 停止取指令和发射指令
• 静态调度（开始于60s，流行于80s）消除动态调度
  • 软件来负责调度指令减少空转。
• 动态调度
  • 硬件对指令的执行重新排序来减少空转。

动态调度的目的：在程序执行的时候，解决WAW,WAR和RAW带来的冒险（会增加硬件的复杂性）。

两种动态调度技术：

• 记分牌
• Tomasulo算法

2.1 记分牌：

• 1964被Cray用于DCD 6600;
• 记分牌允许指令乱序执行，前提：
  • 充足的资源，无数据相关；
  • 记分牌动态解决了先写后读相关
  • 指令可以乱序执行
• 基本原理：
  • 每条指令均经过记分牌，记录各指令间数据相关信息；
  • 如果记分牌判断出一条指令不能立即执行，它就检测硬件的变化从而决定何时能够执行。
• 记分牌处理：
  • 流水线ID段分为两级
    • 流出——解析指令，检查结构相关；
    • 读操作数——直到不存在数据相关时，才读取操作数。
  • 如果存在WAR或者WAW相关，记分牌会暂停这条指令的执行，直到相关消除后才继续执行。
• 记分牌执行过程
  • 流出
  • 读操作数
  • 执行
    • 开始于取到操作数后
    • 当结果产生后，修改记分牌
    • FP流水部件会占用多个周期
  • 写结果：检查WAR相关
  • 出现一下情况时，不允许指令写结果：
    • 前面某条指令还没有读取操作数；
    • 其中某个源操作数寄存器与本指令的目的寄存器相同。
• 记分牌性能：它的逻辑电路相当于一个功能部件，器件的耗费很低。

2.2 Tomasulo算法

Tomasulo算法背景：

• IBM 360/91比CDC6600晚三年推出
• 360系列仅一个指令系统和一个编译器

Tomasulo算法与记分牌差异

• Tomasulo算法中，冲突检测和执行控制是分布的，利用保留站（缓冲）实现；
• Tomasulo算法不检查WAR和WAW相关，通过算法本身消除掉了。

MIPS五阶段的流水线改造：

• ID和EX阶段被以下三个阶段代替：
  • 流出（Issue)
  • 执行(Execute)
  • 结果写回（Write results）
• 流出：
  • 从浮点指令队列中取一条指令；
  • 如果存在一个空的保留站，就流出这条指令；
  • 如果操作数在寄存器中，就送到该指令对应的保留站；
  • 存储器取/存指令只要有空闲的缓存就可以流出；
  • 如果没有空闲的保留站或者缓存，就存在结构相关，指令暂停，直到有空闲 的保留站或者缓存。
• 执行
  • 如果缺少一个或多个操作数，就监听CBD（公共数据总线）。(这个阶段实际就是检测和自动维护RAW相关)
  • 如果两个操作数都就绪，这条指令就可以执行。
• 结果写回：
  • 如果结果已经产生，将其写到CBD上；
  • 通过CBD，把这个结果写到目标寄存器和等待这个结果的所有功能单元的保留站。
• Tomsaulo算法的优点：
  • 分布式硬件冲突检测；
  • 利用寄存器换名，彻底消除WAW和WAR这两种相关；
  • 如果多个保留站等待同一个操作数，当操作数在CDB上广播时，他们可以同时获得所需数据。
• Tomsaulo算法的缺点：
  • 高复杂性；
  • 存在瓶颈：单个公共总线（CDB）引发竞争。解决方法：额外的CDB，即：在每个保留站上需要为每条CDB设置重复的硬件接口。

3 控制相关的动态解决技术

3.1 分支预测缓冲

分支预测缓冲（BPB）：原理

• 最简单的分支预测策略；
• 分支预测缓冲是一个小的存储器阵列
  • 每个单元只有1位，记录最近一次分支是否成功的信息；
  • 预测位为1则预测分支成功，并从目标位置开始取指令；
  • 单元由分支指令地址的低位索引进行寻址；
  • BPB的预测位会被具有相同低位地址的分支设置。
• BPB也称BHP(branch history buffer分支历史缓冲)

BPB实现：

• BPB的实现方案：实现一个小而特殊的“Cache”，利用指令地址进行索引，在IF流水段访问。或者，为指令Cache中每一块附加位，与指令一起取出。
• 若一个指令在ID段被译码为分支指令，且对应的BPB标志预测其成功，则
  • 一旦PC已知，立即从分支目标位置开始取指；
  • 或者，继续顺序取指。

3.2 分支目标缓冲

分支目标缓存：Branch Target Buffer,BTB。为了减小或消除流水线的分支开销，我们需要在IF段结束前知道从哪个地址开始取下一条指令。基本思想：BTB是指使用容量有限的缓存保存最近执行过的分支指令的PC值，以及他们跳转的目标地址。对于后续需要取指的每条PC值，将其与BTB中存储的各个PC值进行比较，如果出现匹配，则预测这是一条分支指令，并使用其对应存储的跳转目标地址作为预测的跳转地址。

BTB实现：

• BTB每个单元应该包括：
  • 分支指令地址
  • 分支目标地址
  • 分支预测标识
• 取指阶段，所有指令地址都与BTB中保存的分支指令地址做比较，一旦相同，就认为本指令是分支指令，并且分支成功。
• 它的目标地址就是保存在缓存区中的分支目标地址，取出后直接送入NPC.

BTB VS BPB

• 分支预测技术受限于预测精度，以及预测失效后产生的开销；
• 根据不同程序特点以及缓冲区的大小，典型的BTB可以实现80%到95%的预测精度。
• 降低失效开销技术：在一个时钟周期内同时取出不同分支路径的指令，会引入其他开销，比如存储系统的端口加倍。降低失效开销的唯一方法，比如AS/400 PowerPC处理器。

分支预测局限性：

• 预测精度：80%~90%；
• 预测性能依赖于：程序类型，缓冲区大小。
• 预测失效开销的优化：预取不同分支路径指令（存储端口数目加倍，交叉存取缓冲）。在目标缓冲中缓冲多个路径的指令。

4 多指令流出技术

多指令流出处理器：一个时钟周期内流出多条指令，达到CPI小于1.

多流出处理器2种基本结构：

• 超标量：每个时钟周期流出的指令数不定；可以编译器静态调度，也可以动态调度。
• 超长指令字(VLIW)：每个时钟周期流出指令数是固定的，只能通过编译器静态调度。