Implementation of Precise Interrupts in Pipelined Processors

Introduction

精确中断的定义：当中断发生时会保存中断进程的状态，如果保存的进程状态与顺序架构模型一致，则中断是精确的。下面是详细的条件：

1. 如果中断是程序中的指令引发的异常条件引起的，则保存的PC应该指向中断的指令。（中断的指令可能执行了，也可能未执行，跟体系结构的定义有关）
2. PC指示的指令之前（程序顺序之前的）的所有指令都已执行并正确修改了进程状态
3. PC指示的指令之后（程序顺序之后的）的所有指令都未执行，且未修改进程状态

要保存的中断状态包括：PC、寄存器、存储器，这些又称之为进程套件（process suite）

中断的分类

中断分为程序中断（异常）和外部中断（中断）

中断可以被定义为精确的或是不精确的，但有些中断必须是精确的：

1. 对于I/O和定时器中断，精确的进程状态使重启成为可能
2. 对于软件调试，希望保存的状态精确。此信息有助于隔离导致异常情况的确切指令和环境
3. 在虚拟内存系统中，精确的中断允许在页面故障得到处理后正确地重新启动进程
4. 如果中断是精确的，系统软件可以以对程序员透明的方式模拟未实现的操作码。这样，体系结构的低性能模型可以使用扩展指令集保持与高性能模型的兼容性
5. 如果特权指令错误是导致的精确中断，则可以实现虚拟机
6. 为了从算术异常中优雅地恢复，软件例程可以采取步骤，例如重新缩放浮点数，以允许进程继续。

Preliminaries

假设进程套件是PC、寄存器、存储器，假设没有操作数缓存，不使用条件码，使用流水线实现。

下图是假设的简单架构，假设功能单元执行时间是确定的，顺序处理指令，并行功能单元。

在指令发射之前发生的中断

指令在发射前的顺序是不变的，而且流水线中的状态不会受未发射指令的影响

发射之前的中断包括特权指令错误、未实现的指令和发射阶段产生的外部中断

当检测到这种中断时，停止发射指令，等待之前已发射的指令执行完成。

当指令执行完成后，进程处于精确状态：发射寄存器的值为异常指令，寄存器和存储器的状态都与该指令一致

方法一：In-order Instruction Completion

本章提供了一种简单易实现但是会降低性能的方法

使用了结果移位寄存器来控制result bus的使用权，结果移位寄存器中保存了指令的控制信息，结构如下图所示，结果移位寄存器的条目数量N是最长功能单元的长度

由于功能单元的执行时间是固定的，当一条指令发射到对应功能单元后，如果该功能单元需要5个时钟周期才能完成，则将该指令分配到结果移位寄存器中的stage 5，每过一个时钟周期会向上移一位，如果指令到了stage 1，则下个时钟周期由它来控制result bus。

结果移位寄存器中保存的result都通往寄存器

实现寄存器的精确中断

如果一条指令需要i个时钟周期完成（stage i），它之前的一条指令需要j个时钟周期完成（stage j-1，上个时钟周期在stage i），且$j > i$ ，如果j还未完成时i发生了中断，此时的中断是非精确的，如何解决？——使用保留结果移位寄存器条目的方法：

• 假设结果移位寄存器为空，如果浮点加法指令需要6个时钟周期完成，则会保留结果移位寄存器中stage1-6中的所有条目给浮点加法指令，如果下一条2个时钟周期的整数加法指令要加入stage 2（此时已经过了一个时钟周期，浮点加法所在的条目为stage 5，浮点加法所保留的条目为stage 1-5），则会被拒绝加入，因为stage 2被保留给了浮点加法！
• result bus在指令完成时检查指令中的异常条件，如果指令包含非屏蔽异常条件，则控制逻辑“取消”结果总线上的所有后续指令，以便它们不会修改进程状态

这保证了修改寄存器的指令按顺序完成

实现主存的精确中断

store指令会修改存储器的值

方法一：等待结果移位寄存器中为空后再发射store指令

方法二：将访存指令发射到memory流水线中，直到已知所有前面的指令都是无异常的，然后store指令的访存可以执行。将存储器看作一个特殊的功能单元

方法二的实现：

• store指令也能在结果移位寄存器中占有条目，store指令的条目称之为dummy store。dummy store条目并不产生结果，即没有目的寄存器这一属性，只是用来控制流水线
• 当store指令发射时就在结果移位寄存器中分配一个条目，放在所有前面指令条目的后面，当dummy store成功到达stage 1时，说明前面所有的指令都已完成且无异常发生，此时可以通知memory流水线释放store访问内存
• 如果store指令产生了异常，则取消store指令和后续所有load/store指令，并向流水线发出信号，让存储指令之后的指令在离开结果移位寄存器时被取消

PC的精确中断

在结果移位寄存器中添加一个域pc，见上面的图

当result bus发现一条异常指令出现时，保存结果移位寄存器域中对应的pc值

方法二：The Reorder Buffer

前一章提供的是最简单最低效的方法，只允许程序顺序执行

本章提供了一种更好的方法，允许程序乱序执行，使用了一种特殊的循环buffer：reorder buffer（ROB），如下图所示

尾指针指向待分配的指令条目，当一条指令发射时就会在ROB的尾指针处分配一个条目，然后尾指针自增指向后面一个待分配的条目

结果移位寄存器的结构发生了变化，结果寄存器域和pc域都保存在ROB中，因此在结果移位寄存器中去除了这两个域，新增了一个tag域，指向ROB中的entry number。如下图所示

指令执行完成时的操作：

• 当指令完成时，结果会通过result bus发送到ROB中，如果指令发生异常也会将异常记录到ROB。当ROB中头指针指向的条目中result准备就绪并且valid是1，然后就会检查该条目的异常，如果没有异常就会将result写入寄存器；如果有异常，停止指令的发射，禁止进一步写寄存器文件

实现寄存器的精确中断

见ROB和结果移位寄存器的图，两者都是是整数加法和浮点加法发出之后的状态，整数加法会先执行完将结果写到ROB中，但是由于头指针指向的是浮点加法，因此整数加法不会写回寄存器，如果整数加法发生了异常，也会先等浮点加法提交过后再检查异常，保证了寄存器的精确中断

实现主存的精确中断

实现方式和上一章中顺序实现的一致，使用了dummy store

当dummy store从ROB中删除时就会发送信号memory流水线提示可以访问存储器

当store指令被发射到memory流水线后，如果它ROB中的dummy store没有被删除，它就会被阻塞到memory流水线中

疑问

如果在ROB中删除dummy store，那么在访存的同时后续指令也可以继续执行，如果访存发生异常，此时是不精确的？

我的想法：并不是删除dummy store，而是将其替换成了store指令真正的ROB条目，保存有异常条件和PC值。由于store指令此时仍然在ROB头部，后续指令仍然要等待store指令提交后才能提交，如果访存发生异常，则会将异常条件放入ROB条目中，ROB头部检查到异常后会清空ROB，保存PC值，保证精确状态。

实现PC的精确中断

每条指令的PC值被保存在ROB中，而不是保存在结果移位寄存器中，为什么？

• 因为结果移位寄存器中的条目数量会比ROB多（功能单元会有多个执行周期），因此要尽可能地减少每个条目所占的硬件资源，将大部分的域都放置到ROB中

当一条指令在异常情况下到达ROB的头部时，在ROB中的PC值将成为保存的精确状态的一部分

旁路路径

由于ROB是顺序提交的，后面的指令如果对ROB中的结果有数据依赖，则依然要等到ROB提交后才可以读取到寄存器文件中更新后的值。

解决方法：增加ROB到寄存器文件出口锁存器的旁路网络，如下图所示

此方法的实现需要为每个ROB条目增加比较器和寄存器指示符。

一条指令在发射阶段会比较自身的操作数指示符和ROB中的寄存器指示符，如果相匹配则设置多路选择器以将数据从ROB选通到寄存器文件输出锁存器，此时在没有其他发射阻塞条件的情况下，允许发射指令，并且在将ROB写入寄存器文件之前使用该数据。

为了防止同一寄存器的多次旁路，当一条指令放入ROB时，必须禁止具有相同目标寄存器指示符的任何条目与旁路检查匹配，只有最近的匹配的ROB条目才会产生一条到输出锁存器的路径

这种方法的最大缺点是需要的旁路比较器的数量和多重旁路检查所需的电路数量

疑问

结果移位寄存器有什么用？

个人认为是用于控制功能单元对ROB的写入

方法三：History Buffer

本章提供的方法结果写入的方法和第一种方法提供的类似，但是可以乱序执行，结果移位寄存器中的结果会直接写入寄存器文件，没有提供ROB。但使用history buffer保留足够的状态信息，以便在发生异常时恢复精确的状态，同时避免了ROB中复杂的旁路网络

history buffer的结构和ROB非常相似，如下图所示

使用history buffer保存状态的方法是：

• 在指令发射时，会在history buffer的尾指针处分配一个条目，同时会将指令的目的寄存器的旧值读入该条目中，条目中同时还保存了指令的pc。

结果移位寄存器中的tag指示的是history buffer中对应的entry number，如果指令在执行时发生异常，异常报告在指令完成后返回，并根据tag域写入history buffer对应的条目

history buffer的条目数量可以小于流水线中执行单元的长度，但是也不能太小。如果指令在发射时发现history buffer中已经满了，则指令必须阻塞执行

寄存器文件需要三个端口，比前几种方法多了一个端口

实现寄存器的精确中断

当history buffer的头部包含一个异常条件时，停止指令发射，等待流水线中的活动全部完成，然后从history buffer的尾部到头部开始将条目中的历史值加载进寄存器文件，同时清空buffer中对应的条目

当history buffer的头部包含一个已知已完成且无异常的元素时，不再需要历史缓冲区条目，可以重新使用该缓冲区位置（递增头指针）

实现主存的精确中断

当一个存储条目出现在history buffer中时，会发信号提示另一个store的值能够被提交到内存（没搞明白）

实现PC的精确中断

history buffer中头部的PC值是精确的值，可以进行状态保存

方法四：Future File

Future File方法类似于History buffer，但是这里使用两个独立的寄存器文件

同时还有个ROB，功能和之前的一致，但是去除了旁路单元

第一个寄存器文件反映了体系结构（顺序）机器的状态，该文件将被称为体系结构文件，由ROB顺序提交更新

第二个寄存器文件在指令完成后立即更新，因此在体系结构文件之前运行（它反映了体系结构文件的未来）。该未来文件是功能单元用于计算的工作寄存器文件

思想：

• 功能单元将结果直接写入未来文件和ROB中，未来文件是乱序更新，而ROB是顺序更新体系结构寄存器文件（更新方法和ROB方法一致），功能单元使用的是未来文件中寄存器的值

如果发生异常：

• 如果ROB发现头部的指令有异常状况，则与头指针和尾指针之间的缓冲区条目相关联的寄存器指示符将用于从体系结构文件中恢复未来文件中的值，即从体系结构文件中加载ROB中头指针到尾指针之间的寄存器标识符指示的值到未来文件中

该方法的主要优势是体现在交换之中，如果中断是通过交换来实现的（即中断时将所有寄存器的值保存到内存中，新的寄存器值被交换进寄存器文件中运行中断程序），该方法可以将体系结构寄存器文件立马转储到内存中，如果是history buffer，则需要将history buffer中的值先加载到寄存器文件中，再将寄存器文件转储到内存

Performance Evaluation

特定方法的选择取决于：

1. 其对系统性能的影响
2. 还取决于实现的成本
3. 恢复精确CPU状态的容易程度

当ROB中的条目太少时，ROB的方法表现反而差于in-order

对于两种解决存储器精确中断的方法：将store指令阻塞在发射阶段\允许发射store指令到memory流水线中。后者表现出的性能更好

Extensions

Handling Other State Values

在使用条件码的体系结构中，条件码随指令保存在ROB中，指令执行时可以修改ROB中自己对应条目里的条件码，在ROB提交时才会更新处理器状态

在执行修改处理器状态的指令时，只有当ROB提交时才会引起状态的改变

Virtual Memory

要支持虚拟存储的精确异常，主要是从段错误中恢复。则要让地址转换流水线保证load/store指令顺序通过，同时store指令也会在ROB中占用条目，但是该条目仅用于异常报告和保存PC值

如果存在寻址错误，则该指令在寻址流水线中被取消，并且所有后续load/store指令在通过寻址流水线时被取消。这保证了没有额外的load/store指令修改process suite

当ROB中异常store的条目到达头部时，会清除ROB中其他的条目，保证后续指令不会修改进程状态，同时ROB条目中还保存了精确的PC

Cache-Memory

如果是写直达的cache，可以使用类似于寄存器文件一样处理cache，为cache保持一个history buffer。每个store指令都会生成一个条目，指示它写入的cache的位置，该条目可用于恢复缓存状态

对于写回的cache，在执行实际的写回操作之前ROB应该被清空，或者检查ROB中是否有属于要写回的行的数据，如果发现有，则写回必须要等待数据进入cache行。如果使用了history buffer，则cache行必须保存在buffer中

赏

谢谢你请我吃糖果

支付宝

微信