以动态调度、多发射和推测来开发指令级并行

2020 年 12 月 6 日
笔记
读书笔记

近期因相关课程需要完成一个关于指令级并行(ILP)的汇报，我的主题为“以动态调度、多发射和推测来开发ILP”，是教材《计算机体系结构——量化研究方法》的第三章第九节内容，这里记录下来，用于以后回顾。
笔记分为以下几个部分：

复习
- 流水线
- 流水线冒险
动态调度
推测
多发射
将它们结合起来

复习

首先来介绍一下什么是流水线以及使用流水线所产生的一些问题

流水线

流水线是一种用来将多个指令重叠执行的技术。

上图是一个简单的例子，不使用流水线技术时，处理器每800ps完成一条指令，为了提高执行指令的吞吐量，将指令的执行划分为五个阶段(取指、译码、执行、访存、写回)并添加相应的运算单元后，处理器就可以重叠执行指令了，如上图中的第二张图所示，修改后的流水线每200ps就可以执行完一条指令，提高了吞吐量，可以看到流水线只是提高了处理器执行指令的吞吐量，并没有减小每天指令的执行周期，第二张图中执行每条指令还是需要800ps。
这里插入简单介绍一些经典五级流水线每个阶段：

取指(IF)，从指令存储器中读取指令
译码(ID)，对指令进行解析，同时读取寄存器
执行(EX)，执行操作或者计算地址(对于载入/存储指令)
访存(MEM)，从数据寄存器中读取操作数(对于载入/存储指令)
写回(WB)，将结果写回寄存器

流水线冒险

但是指令之间会存在一些数据相关等问题，所以流水线技术也会有一些局限性，接下来介绍三种常见的流水线冒险

结构冒险，即硬件不支持多条指令在同一个时钟周期中执行。
数据冒险，发生在由于一条指令必须等待另一条指令的完成而造成的流水线停顿的情况下。具体有两个原因：
- 数据依赖，也叫做真数据相关。就是两条指令间存在一个写后读(RAW)问题，也就是第一条指令要写的数据，刚好要被第二条指令使用，而又因为第一条指令需要在流水线的第5个阶段(写回)才会真正将数据写入寄存器中，而第二条指令在流水线第3个阶段(执行)就需要这个数据了，所以产生了这种真数据相关，可以通过旁路(bypassing)技术和停顿(也称为气泡)方法来解决。
- 名称依赖，也就是两条指令对同一个寄存器进行读后写(WAR)或者写后写(WAW)，和上面的写后读不一样，读后写和写后写不会产生数据流动，也就是两条指令之间其实不是真正的数据相关，只是因为要操作同一个寄存器而产生的依赖关系，可以通过寄存器重命名(register renaming)方法来解决。

上图是一个通过旁路技术来解决写后读问题的例子，第一条指令修改了寄存器s0的数据，第二条指令需要读取s0的数据，旁路技术通过在得到s0数据的那个周期，直接将数据通过一个旁路送到需要这个数据的地方，可以看那条蓝色的线路，正常情况下第一条指令需要在WB阶段才能修改s0的值，但通过旁路，可以在EX阶段获得数据后直接送到第二条指令的译码(ID)阶段，避免产生停顿。

上图是另外一个例子，由于这个例子中第一条指令是一个载入指令，必须要等到MEM阶段才能得到数据，但是第二条指令在EX阶段就要使用数据了，我们无法将未来的数据送给现在，所以这种情况下无法使用旁路技术，所以可以看见两条指令间有一个停顿，即蓝色的气泡(bubble)。

控制冒险，因为决策依赖于一条指令的结果，而这条指令正在执行中而发生。简单来说就是因为条件判断语句，在分支被解析前不能得知指令是否需要执行，会影响流水线的吞吐量。解决方法有停顿、分支预测(branch prediction)和延迟分支(delayed branch)。

上图是使用分支预测来解决分支冒险的例子，第二条指令需要一个判断，而判断的结果不能很快得到，为了不产生停顿，所以处理器预测这条指令不会跳转，所以处理器继续执行第三条指令而不是停顿等待结果，分支预测简单的说就是为了不停顿，所以就预测一个结果，让处理器先去执行那条预测的指令，分支预测技术还有其他的细节，如果感兴趣可以去阅读教材，这里不是重点。

上图中分支预测失败，所以对停止执行之前预测得到的指令，即简单的插入气泡，然后去执行正确的指令。

关于延迟分支技术，简单来说就是在分支解析的时候，去执行一条与分支无关的指令来避免流水线停顿。

动态调度

这里不会过多介绍动态调度，我的重点在推测和多发射，这里主要列举动态调度的特点：

乱序执行
乱序完成
非精确异常，一种因为乱序完成而导致的问题，即在发生异常时，有一些本不应该被执行的指令已经被执行了，或一些本应该被执行的指令却还未被执行。
Tomasulo算法，一种动态调度使用的算法

动态调度的执行指令过程分为发射、执行、写结果三个部分。

推测

推测技术主要是为了克服控制相关的限制，去开发更多的ILP。

思想：

同动态分支预测选择要执行哪些指令
利用推测，可以在解决控制相关问题之前执行指令(能够撤销错误推测序列的影响)
进行动态调度，以应对基本模块不同组合方式的调度

特点：

乱序执行
额外的指令提交
重排序缓冲区
顺序提交

我们来看一下基于硬件推测的基本结构图：

其中红色框是在动态调度结构的基础上进行改变的部分，黄色框是动态调度结构的重点部分，接下来进行解释。

重排序缓冲区(reorder buffer，简称ROB)：这是推测新加入的一个硬件，因为有了ROB，在推测的指令执行过程中的写结果后又多加了一个指令提交，所以推测下的指令执行有四部分，分别是发射、执行、写结果和提交。ROB中扩展了寄存器集，会在一定时间内保存指令的结果，这段时间从完成该指令的相关运算算起，到该指令提交完毕为止，寄存器和存储器只有在指令提交之后才会被更新(即我们非常确定该指令会被执行)，因此ROB是在指令执行完毕到指令提交这段时间内提供操作数。ROB类似于Tomasulo算法中的存储器缓冲区，所以将载入缓冲区(load buffers，第二个红色框)旁边的存储器缓冲区集成到ROB中了。

保留站(reservation stations，简称RS)：保留站提供了寄存器重命名功能，解决了WAR和WAW问题，它为等待发射的指令缓冲操作数，基本思想是：保留站在一个操作数可用时马上提取并缓冲它，这样就不再需要从寄存器中获取该操作数。此外，等待执行的指令会指定保留站，为自己提供输入。最后，在对寄存器连续进行写入操作并且重叠执行时，只会实际使用最后一个操作更新寄存器。在发射指令时，会将待用操作数的寄存器说明符更名，改为保留站的名字，这就实现了寄存器重命名功能。

公共数据总线(common data bus，简称CDB)：CDB将操作数从保留站中传递给所有需要它的功能单元，而不需要经过寄存器，加快了指令的执行。

上图是一些指令在执行过程中的某一个时刻的情况，其中最上面的两条指令是在动态调度情况下的执行情况，它们分别指向在推测情况下的执行情况，可以看出，在动态调度下，因为乱序执行，这两个指令已经执行结束并写入寄存器了。而在推测下同样的指令已经完成了执行，但由于这两条指令之前的MUL.D指令还未完成指令提交，所以这两条指令也不允许完成指令提交。
这一区别意味着具有ROB的处理器可以在维持精确异常的同时动态执行代码。