Clockhands: Rename-free Instruction Set Architecture for Out-of-order Processors

发表于 更新于 分类于

随着寄存器数量增加，处理器也由单发射架构转为多发射机构，但是受限制于数据竞争，内存读写，长周期指令等原因，顺序发射的数量存在瓶颈，因此引入了乱序发射。乱序发射的核心思想是 latency hiding，当指令陷入停滞时允许后续的指令以乱序发射，继续执行，避免处理器的性能损失。

寄存器重命名

寄存器重命名则是解决了其中数据竞争的问题，在不考虑编译器优化的前提下，由于寄存器的数量有限，存在 RAW，WAR，WAW 三种类型的数据竞争（在乱序发射的情况下只要有写入的操作就可能存在竞争）。这一技术则是将物理寄存器映射到逻辑寄存器上，减少数据竞争的发生。汇编指令指代的为逻辑寄存器编号，根据具体的指令集可能存在不同的数量，而处理器将其映射到自身实际实现的物理寄存器上，并采取一定的映射策略，这样可以将数据竞争通过映射到不同寄存器的方法消除。

实现寄存器重命名则需要维护 rename file，根据处理器的指令吞吐量有对应数量的读口和写口（RAM-like），而由于现代寄存器较多且多为64位宽，RAM 的逻辑大小又呈读写口的平方的级别增长，rename file 通常会占据较大的面积，并带来较大的功耗。

编译器的寄存器优化

llvm的后端设计已经引入了寄存器逻辑编号的概念，在后端模型中有无数个可用的寄存器，在这个过程中编译器可以进行寄存器分配的优化，尽可能地减少寄存器数量限制带来的数据竞争。那为什么还需要硬件花费这么大的代价做寄存器的重命名呢？我认为一个可能的原因是：硬件在运行过程中的行为是一个不可预测的混沌系统，由中断、异常、分支预测、乱序发射带来的不确定性导致硬件重命名可以利用的动态信息大大超出编译器可利用的静态信息，优化效果自然更好，因此在编译器已经优化过的基础上，处理器仍然需要设计硬件的寄存器重命名结构。

基于映射表的简单实现

最简单的实现方式是基于映射表，只需要在寄存器前维护一个映射关系表即可，这张表存储体系寄存器编号（即指令集对于寄存器的约定）到物理寄存器编号（处理器硬件实现）的映射关系。对于读请求，通过查询映射表返回物理寄存器的值，对于写请求，则维护一个可用映射的FIFO，每一次读请求都会建立一个新的逻辑寄存器到物理寄存器的映射关系，以消除 WAW 和 WAR 竞争。

为了解决 RAW 竞争，表中还需要维护该逻辑寄存器的状态，每个逻辑寄存器只会被更新一次（即创建该映射的写操作），因此只需要一个位维护是否处于就绪状态，当指令所有需要的操作数都就绪后允许发射，另外在 EX/WB 段也需要相应的广播机制来更新状态和数据。这一机制也有效保证了乱序执行的正确性，所有具有依赖关系的指令都会被就绪状态控制发射。为了解决 WAR 竞争，在 ISSUE 段需要存储当前指令映射到的物理寄存器编号，作为指令的一部分随流水线逐级流动。（ISSUE QUEUE 的实现代价也是巨大的）

需要考虑的是异常或者分支预测错误的情况，此时流水线中执行了错误的指令，因此需要回滚映射表的状态，这就需要进行状态储存，或者依赖于提交阶段的信息进行回滚。基于此一个常见的优化是通过流水线划分，将分支预测结果在跳转指令执行前得出，避免起引起对映射状态的修改。

基于保留站的寄存器重命名

Tomasulo 算法中引入了 保留站（Reservation station）和通用数据总线（Common Data Bus）的概念，在每一个功能单元中加入了保留站，进一步地拆分为逻辑控制部分和功能执行部分。

指令首先由 instruction queue 进入到 issue queue 中，如果对应的执行单元的保留站中有空余，则发射到保留站中。保留站中的每一项都是一条发射了但尚未执行的指令，在保留站中的操作数可以分为两种情况：若该操作数的数据就绪，则直接写入到保留站的数据域中；否则则使用一个占位符来表示该数据是由哪个保留站中的指令产生的，当该指令执行完毕后会广播至CDB中，此时保留站则会更新状态至第一种情况。具体来说保留站中的每一项中包含：

  • \(op\)：表示操作的类型
  • \(Q_j, V_j, Q_k, V_k\)：表示两个操作数的状态，\(Q\)表示占位符编号，如果为0则表示数据已经就绪，\(V\)表示具体的数据域
  • \(A\)：内存读写操作的地址
  • \(busy\)：表示该保留站标项的占用状态

除此以外 register file 中也需要增加一个新的域，表示该寄存器的逻辑编号，如果没有就绪那么由哪一个保留站产出，便与后续发射指令更新占位符状态。在功能单元完成一条指令后，其结果会被广播，寄存器堆如果匹配到对应的编逻辑编号（即这是最后一条对该寄存器进行的写操作），那么就会更新其中的值。也就是说，如果寄存器的值不断地被写入，那么寄存器堆中并不会存储它一整串过程中的中间值，因为每一次新的写入操作都会修改该物理寄存器对应的逻辑寄存器编号，过程中的值只会在保留站中不断传递，这也给精确异常的实现带来了较大的困难。

为了实现精确异常，那么就需要保留一定的历史状态，首先一定要为乱序执行引入 reordered buffer 保证指令顺序入队，乱序发射，顺序提交，当发生投机失败或者异常中断时，可以根据 buffer 中的状态判断需要继续等待哪些指令完成，又有哪些状态需要回滚。而与之相对应的，需要讲 register file 的功能一分为二，新增 future file 作为原来的 register file 功能，而 register file 本身则依赖于指令的提交进行更新，相当于不断更新的历史状态备份。当需要回滚状态时，可以等待需要执行的指令提交完毕，然后回滚到 register file 的状态，重置所有的保留站状态。

保留站相当于使用了保留站的编号作为寄存器重命名的逻辑编号，使用寄存器堆中额外的状态域作为映射表。相比于基于映射表的实现方式，由于每个功能单元的保留站项数有限且没有多口读写的依赖，其逻辑代价非常小，也在 issue 段拥有更优秀的时序，主要的压力转移到广播式的数据总线上，多个不同的功能单元都要使用总线广播结果，导致其成为设计的瓶颈。

clockshands 架构

新的寄存器重命名尝试

寄存器重命名无论采用何种实现方式都给硬件设计带来了巨大的逻辑复杂度和功耗压力，因此本篇文章尝试一种全新的架构解决这一问题。在这之前他们已经提出了一个叫做 straight 的指令集&架构方案，指令集的操作数指明为是从该条指令向前数第几条指令产生的结果，相当于每一条指令都将结果写入一个新的寄存器，从编译器层面完成了寄存器重命名，同时规定一个最远限度\(M\)，指令的引用不得超过\(M\)条指令。在硬件方面，寄存器堆由一个 FIFO ring buffer 实现，只保留最近的\(M\)个最近的寄存器结果，在消除了数据竞争的基础上，采用乱序多发射提高处理器性能，这样分支预测错误和异常都有较为简易地回滚方式。

这个指令集要求编译器做出较大的改动，并且编译出来的程序会有明显的膨胀，具体来说作者总结了三个使代码量显著增加的因素，都是由于\(M\)的限制引起：

  1. 循环变量保持：在多次循环中需要长期保持一些循环常量，这就要求编译器在其中添加大量的 move 指令
  2. 长生命周期变量：实际上也是和1情况类似，需要大量的 move 指令保持
  3. 汇合点处理：在多个分支的汇合点上，不同分支的历史指令情况不同，需要添加额外的指令让所有分支的上下文一致

根据其他研究，结果生命周期为\(x\)的指令占比约为\(O(\frac{1}{x^2})\)，需要的 move 指令约为\(\frac{k}{M}\)，那么额外的指令数量约为\(\sum_{1}^{P} O(\frac{1}{x^2}) * \frac{k}{M} = O(\frac{1}{M} lnP)\)。实测下来至少有30%以上的代码行数增加，代价比较大。

clockhands ISA

clockhands 就是基于这个架构设计，为了解决指令数暴涨的问题，它基于 straight 的结构扩展为多个不同 group 的 ring buffer，取操作数时需要指明是从哪一个组取最近\(M\)条指令的结果，写回结果时要指明写入了哪一个组。因此可以通过多个组的利用解决 straight 指令数量增加的问题，可以使用一个组专门存储长生命周期变量，经过实验选取了4组寄存器，最大距离16的配置，在编译器灵活性和硬件复杂性间取到平衡，编译器对四组寄存器做了特化处理：

  1. 临时变量存储在 t 组
  2. 长生命周期变量存储在 u 组
  3. 循环变量存储在 v 组
  4. sp 寄存器专门放在 s 组，编译器优化只允许进行立即数加减

因此硬件可以根据这一需求设计不同的寄存器组规格，例如增大 t 组的大小，减少 s 组的大小，并且可以适当增大 v 组的路径延时，在实际实现时并不会采用位移寄存器的方式移动组内所有的寄存器值，而是采用 counter 计数器变化来索引。在多发射过程中，issue 段就需要综合实际发射的指令数量动态变化距离，然后取到类似于保留站的占位符发射到功能单元中，在本文中作者添加了一个新的流水级来计算动态距离。对于乱序发射比较难办的错误恢复，clockhands 则是指需要根据 ROB 恢复四个组的计数器即可，乍一想没有太大问题。

总结

总的来说，clockhands 这篇文章有点意思但是又感觉有意义的不多，这个架构确实可以解决寄存器重命名的设计缺点，但是对于整个生态架构的修改太大了，而且很难说这样修改后一定就能提升整体效率，因为非常多作用于传统架构的软硬件优化未必可以继续使用，而本文的实验又缺乏更大规模更大覆盖度的说服力，当个 idea 看就可以了。

参考链接

  1. Register Renaming
  2. Tomasulo Algorithm