SRT除法器性能优化：Skip-Zero策略的原理、实现与Chisel实践

1. 项目概述与核心价值

在处理器微架构设计，尤其是面向高性能计算和机器学习的专用加速器领域，除法器一直是个让人又爱又恨的模块。爱的是，从梯度下降中的学习率调整到信号处理中的归一化运算，除法无处不在，是算法实现的基础；恨的是，它的硬件实现往往伴随着高延迟和低吞吐量，动不动就占据几十个时钟周期，一不小心就成了整个数据通路的“堵点”。我这些年参与过好几个处理器核的设计，每次做性能分析，除法单元（尤其是整数除法）的延迟曲线总是最刺眼的那一根。

传统的硬件除法算法，比如恢复除法（Restoring）和非恢复除法（Non-Restoring），原理直观但效率有限，难以满足现代处理器的性能需求。SRT（Sweeney-Robertson-Tocher）算法因此成为了高性能除法器的主流选择。它通过引入冗余的商数集和基于查找表（LUT）的快速商数选择逻辑，在保持合理硬件复杂度的同时，支持高基数的迭代，从而显著提升计算速度。简单来说，SRT把一次复杂的比较-减法操作，简化成了查表+可能的一次加法/减法，迭代的关键路径短了，频率就能做上去。

然而，SRT算法也并非完美。在基数为2（Radix-2）的SRT实现中，根据部分余数和除数的几个最高位查表，部分商的结果可能是-1， 0， 或+1。我们发现，在大量随机除法的仿真中，部分商为0的情况出现的概率接近50%。这意味着，在近一半的迭代周期里，硬件逻辑（主要是那个用于计算新余数的加法器）其实是在“空转”——因为当商为0时，新的部分余数就是旧余数左移一位，根本不需要经过加法器。加法器的延迟通常是迭代周期中的主要部分，这个“空转”就造成了潜在的周期浪费。

Skip-Zero策略的核心思想，就是识别并利用这些“商为零”的低延迟迭代机会。当检测到当前迭代的部分商将为0时，我们不是按部就班地走完一个完整的迭代周期（查表、可能的多路选择、加法），而是直接跳过加法环节，仅执行移位操作，并立即准备下一个迭代的商数选择。更进一步，我们可以通过并行预判连续多个迭代的商数，实现一次跳过多个“零商”迭代，从而压缩总的迭代周期数。这个策略的精妙之处在于，它几乎没有增加关键路径的延迟（预判逻辑非常轻量级），硬件开销也极小，却能换来可观的性能提升，相当于用极小的代价“挤”出了除法器的潜在算力。接下来，我将深入拆解SRT算法的原理、Skip-Zero策略的硬件实现细节，并分享我们在用Chisel语言构建参数化除法器生成器过程中的一些实战经验和避坑指南。

2. SRT算法核心原理与迭代过程拆解

要理解Skip-Zero策略为何有效，必须首先吃透SRT算法，特别是其部分商选择机制。我们常说的“基数”是理解其效率的关键。基数r表示每次迭代能产生log₂(r)个商位。基数越高，完成整个除法所需的迭代次数就越少，但每次迭代的逻辑（尤其是商选择逻辑）会变得更复杂。

2.1 从恢复除法到SRT：为什么选择冗余表示？

让我们从最基础的恢复除法说起。它的过程很像我们手算除法：每一轮，用部分余数减去移位后的除数，如果结果非负，则该商位为1，并将差值作为新的余数；如果结果为负，则该商位为0，并且需要“恢复”原来的余数（即把减去的除数加回去），这也是其名称的由来。这个过程每次只能确定一个商位（0或1），是基数2算法。问题在于，当试图扩展到高基数时（比如一次确定2个商位），我们需要精确比较部分余数和多个不同倍数的除数，这需要多个并行的减法器和优先级选择器，硬件复杂度急剧上升。

非恢复除法（Non-Restoring）提供了一个新思路：它允许商位取-1和+1。选择逻辑简化了——直接看部分余数的符号位。如果是正或零，商位取+1，做减法；如果是负，商位取-1，做加法。这样就不需要“恢复”操作了，迭代延迟降低（一个异或门选择加/减操作+一个加法器）。代价是最终结果可能需要一个校正步骤来处理负商。更重要的是，它揭示了一个关键洞见：允许负商位后，我们不再需要精确比较部分余数和除数，只需判断余数落在哪个大致区间即可。这为SRT算法的高基数实现铺平了道路。

SRT算法继承了非恢复除法允许负商的思想，并将其系统化、表格化。其核心是维持一个不变式：在整个迭代过程中，部分余数R必须被约束在一个特定的范围内，通常表示为-k * D <= R < k * D，其中D是除数，k是一个与基数相关的常数。这个范围保证了，在每一轮迭代中，我们都能根据R和D的少数几个最高有效位（MSB），从一个预先定义好的查找表（LUT）中，快速选出一个合适的部分商q_i（q_i ∈ {-a, ..., 0, ..., +a}），使得新的部分余数R' = R - q_i * D仍然落在下一个迭代所要求的范围内。

2.2 商选择表：SRT算法的“决策大脑”

商选择表是SRT算法的灵魂。以基数2（Radix-2）的原始SRT算法为例，部分商q_i的取值范围是{-1, 0, +1}。选择逻辑极其简单：仅观察部分余数R的最高两位（符号位和最高数值位）。如图2(a)所示，在一个归一化的数轴上（除数D被缩放至[0.5, 1)区间），根据R的这两位，可以直接映射到q_i。例如，当R的最高两位为01（表示R在[0.5D, D)区间），则q_i=+1；为10（表示R在[-D, -0.5D)区间），则q_i=-1；为00或11（表示R在[-0.5D, 0.5D)区间），则q_i=0。这个查找操作延迟极低。

对于基数4（Radix-4）的SRT，q_i的取值范围会更大（例如{-2,-1,0,1,2}），一次迭代能产生2个商位。此时，商选择需要参考R的更多位（如前3位）以及除数的次高位。虽然查找表变大了，但迭代次数减半，在追求高吞吐量的设计中经常能带来净收益。

这里有一个关键点，也是我们选择原始SRT算法而非其变种（Variant SRT）作为Skip-Zero策略基础的原因。如原文图2所示，在基数2下，原始SRT算法中q_i=0的概率区域（图2a中灰色区域）约占整个可行区域的一半。而在变种SRT算法中（图2c），q_i=0的区域缩小到了约1/3。更高的“零商”概率，意味着Skip-Zero策略有更大的发挥空间和优化潜力。尽管变种SRT在高基数下有其优势（解决了基数缩减问题），但在我们聚焦的、Skip-Zero收益最大的基数2场景下，原始SRT是更优的选择。

2.3 迭代的硬件流程：一次循环做了什么？

一次典型的SRT迭代（以基数2为例）在硬件上的步骤如下，这也是我们后面优化时要针对的环节：

1. 商选择：根据当前部分余数R的固定高位（如最高2位），查询商选择表，得到部分商q_i。
2. 除数倍数生成：根据q_i的值（-1, 0, +1），生成相应的除数倍数（-D， 0， +D）。对于基数2，这通常只需一个取反操作和/或一个多路选择器，无需真正的乘法器。
3. 部分余数更新：计算R_new = R - q_i * D。当q_i=0时，R_new = R；当q_i=±1时，需要一个加法器来执行R ± D。
4. 移位与准备：将R_new左移一位（对于基数2），作为下一轮迭代的输入R。同时，将q_i累加到最终的商寄存器中。

可以看到，当q_i=0时，步骤3中的加法器是完全不需要的。而加法器通常是迭代周期中延迟最大的部件。Skip-Zero策略瞄准的，正是���跳过”这个加法器延迟的机会。

3. Skip-Zero策略的硬件实现与设计权衡

理解了SRT迭代中“零商”场景的低延迟特性后，Skip-Zero策略的实现思路就非常直观了：检测并跳过那些不需要加法操作的迭代周期。但如何高效、正确地实现，里面有不少细节。

3.1 基础的单级Skip-Zero单元

最直接的实现是在每个迭代单元前增加一个“预判”逻辑。对于基数2 SRT，这个逻辑非常简单：它并行检查当前部分余数R的最高两位R[N:N-1]。如果这两位的组合对应于q_i=0（在原始SRT中，即00或11），那么本次迭代的“有效操作”就只是将R左移一位。我们可以立即启动对移位后结果R<<1的最高两位R[N-1:N-2]的检查，以判断下一个迭代的q_{i+1}。

如果连续检测到多个q_i=0，理论上我们可以连续移位多次。硬件上，我们可以设计一个多级的零检测链。例如，一个s级的Skip-Zero单元，可以同时检查R的从最高位开始的s个重叠的2位窗口（即[N:N-1],[N-1:N-2], ...,[N-s+1:N-s]）。通过一个前导零检测（Leading Zero Detection）风格的逻辑，我们可以一次性计算出从当前位开始，连续有多少个迭代的q_i会是0，然后控制一个桶形移位器（Barrel Shifter）将R一次性左移相应的位数。

图4展示的就是这样的并行选择逻辑。其核心是一组异或门和优先级编码器。每个2位窗口通过一个简单的组合逻辑（比如，两位相等则q_i=0）产生一个“零商”标志。然后，一个优先级检测电路（类似于找第一个‘1’的电路，但这里是找第一个‘非零商’标志）可以确定最多能连续跳过的迭代次数s'（s' ≤ s）。这个电路的延迟非常小，远小于一个完整加法器的延迟。

3.2 性能增益的理论分析

Skip-Zero策略带来的加速比是可以定量分析的。假设硬件支持s级跳过（即最多连续跳过s个零商迭代），并且每次迭代出现q_i=0的概率是p（对于基数2原始SRT，p≈1/2）。那么，平均每次使用Skip-Zero单元可以跳过的迭代次数期望值是：E[skip] = p + p^2 + ... + p^s = (1 - p^s) / (1 - p) * p。当p=1/2时，化简为E[skip] = 1 - (1/2)^s。

对于一个基数2^b的SRT除法，完成整个除法所需的平均迭代次数约为N/b（N为商的有效位数）。引入Skip-Zero后，平均每次“有效迭代”（指需要执行加法操作的迭代）可以附带跳过E[skip]个“零商迭代”。因此，总的加速因子S可以近似表示为：S ≈ 1 + E[skip] / b = 1 + (1 - (1/2)^s) / b

对于最实用的s=1, b=1（基数2）的情况，S = 1 + (1 - 1/2)/1 = 1.5。这意味着理论上迭代阶段可以获得高达50%的速度提升。这是一个非常可观的收益，尤其是考虑到其硬件开销几乎可以忽略不计。

3.3 与迭代单元级联的协同设计

在实际的高性能除法器设计中，我们常常采用迭代单元级联（Cascaded Iteration Units）的技术，即在单个时钟周期内串联多个迭代单元，以在一个周期内完成多次迭代，从而提高吞吐量。Skip-Zero策略可以很好地与这种设计融合。

如图5所示，我们在每个迭代单元前都放置了一个Skip-Zero单元。数据流进入第一级，Skip-Zero单元1先判断是否可以跳过初始的零商迭代。如果可以，则直接移位后送入迭代单元1（此时迭代单元1的加法器可能被旁路）；如果不可以，则正常进入迭代单元1计算。计算或移位后的结果送入Skip-Zero单元2，进行下一轮的判断，如此往复。

这种设计有两个关键优势：

1. 隐藏Skip-Zero检测延迟：Skip-Zero单元的检测延迟可以部分或全部被隐藏在前一级迭代单元的计算周期内，特别是当级间采用流水线寄存器时。
2. 动态适应零商模式：除法的中间过程零商出现是随机的，这种每级前都检测的设计可以动态地、最大化地利用每一个跳过的机会。

注意：在级联设计中，需要仔细处理数据通路。当某级Skip-Zero单元跳过了k个迭代时，它需要通知后续的逻辑：商寄存器需要累加k个0，并且迭代计数器需要减去k。这需要额外的控制逻辑，但复杂度不高。

3.4 参数化设计：寻找最佳平衡点

为了评估Skip-Zero策略在不同配置下的效果，并找到性能、面积、功耗的最佳平衡点，我们用Chisel实现了一个高度参数化的除法器生成器。主要参数包括：

• 数据位宽：支持常见的32位、64位等。
• 迭代基数：支持基数2、基数4等。
• 级联级数：单个周期内串联的迭代单元数量。
• Skip-Zero级数：每个Skip-Zero单元支持的最大连续跳过次数。

通过脚本化地遍历这些参数组合，进行综合和仿真，我们可以绘制出设计空间探索图。如图6所示，横轴可以是最大时钟频率，纵轴是能效（每秒操作数/焦耳），每个点代表一种配置。我们的实验发现，在目标FPGA平台上，配置(b=1, l=4, s=1)，即基数2、4级级联、1级Skip-Zero，往往能达到最佳的“频率-能效”平衡点。

为什么是基数2？这似乎与“高基数更快”的直觉相悖。原因在于Skip-Zero策略的收益与基数b成反比（公式中除以b）。在基数2下，s=1就能带来50%的迭代加速。而在基数4下，同样的s=1只能带来25%的加速。高基数迭代单元本身更复杂，关键路径更长，可能会降低最大频率。当Skip-Zero带来的迭代次数减少收益，无法抵消高基数单元本身频率下降的损失时，基数2反而综合表现更好。这凸显了系统化设计空间探索的重要性，不能孤立地看待某个优化技术。

4. 完整除法器架构与关键优化技巧

一个完整的、工业级的除法器模块远不止迭代核心。围绕SRT迭代器和Skip-Zero策略，还需要一系列前处理和后处理逻辑，以及针对面积和功耗的优化。图3展示了我们设计的完整数据流。

4.1 预处理阶段：为迭代做好准备

预处理阶段处理三件关键事情，其优化直接影响整体性能：

1. 符号处理与取绝对值：硬件除法通常直接处理无符号数。对于有符号除法，我们首先提取操作数的符号位，并记录最终结果的符号（被除数与除数符号异或）。然后将输入转换为绝对值。这一步需要小心处理整数补码的最小值（如-2^31）取绝对值时的溢出问题，通常通过一个简单的条件逻辑处理。
2. 边界情况处理：这是RISC-V等指令集架构的合规性要求。必须在迭代开始前检测并处理诸如“除数为零”和“溢出”（如INT_MIN / -1）等情况。这些情况会触发异常或返回架构定义的特定结果，并应完全旁路掉耗时的迭代过程。一个常见的优化是将边界情况检测与符号处理、绝对值计算电路合并，减少关键路径。
3. 输入移位：这是一个经典且至关重要的优化。由于迭代是从最高有效位（MSB）开始产生商位，如果被除数远小于除数，商的高位会有很多前导零。输入移位逻辑通过一个前导零计数器（LZC），计算被除数和除数的有效位差，并将被除数左移相应的位数。这相当于跳过了所有商的前导零迭代，对于小商值的除法，性能提升是数量级的。Skip-Zero��略主要优化的是迭代过程中的零商，而输入移位优化的是迭代开始前的“结构性”零商，两者是互补的。

4.2 迭代核心的微架构优化

在迭代核心部分，除了Skip-Zero，我们还采用了以下优化来提升面积效率和时序：

1. 部分余���表复用：在级联迭代单元中，除数D在多次迭代中是不变的。因此，我们不为每个迭代单元都复制一份完整的商选择表，而是共享一个全局的“部分余数表”（本质上是根据D预先计算好的选择边界）。每个迭代单元根据自己当前的部分余数R，从这个共享表的对应行中选择q_i。这显著减少了高基数设计中的查找表资源消耗。
2. 校正阶段合并：在非恢复除法或SRT除法中，如果最终余数为负，需要一个校正周期（将余数加回除数，商减1）。在我们的级联设计中，我们将校正逻辑集成在最后一级迭代单元中。这样，当最后一个迭代完成且检测到负余数时，可以在同一周期内完成校正，避免了一个额外的、独立的校正周期，提高了吞吐量。
3. 寄存器合并：在迭代过程中，部分余数R的位宽逐次减少（因为每次迭代后R会左移，低位补零），而累积的商Q的位宽逐次增加。我们可以将R和Q打包在同一个宽寄存器中。初始时，R占据寄存器的高位，Q占据低位（全零）。每次迭代，R左移，移出的高位进入Q的尾部。这种方法节省了寄存器数量，并简化了数据通路。

4.3 后处理与结果输出

迭代完成后，需要：

1. 结果移位：将合并寄存器中的商和余数根据预处理阶段的输入移位量进行右移，得到正确的绝对值结果。
2. 符号应用：根据预处理阶段保存的符号位，对商和余数应用正确的符号（对于商，可能是取补码；对于余数，符号通常与被除数相同）。
3. 结果格式化：按照指令集架构的要求，将结果写入目标寄存器。

5. 实验评估、问题排查与实战心得

我们使用Chisel生成RTL，在Xilinx Artix-7 FPGA上进行综合，并用软件仿真来统计平均迭代周期数。对比对象是开源RISC-V处理器中常用的除法器，如Xuantie-910和Rocket-Chip中的设计。

5.1 性能评估方法论

评估硬件除法器性能，不能只看最高频率，而应关注平均操作频率和能效。

• 平均操作频率：平均操作频率 = 时钟频率 / 平均执行周期数。这综合反映了设计的速度和效率。
• 能效：能效 = 平均操作频率 / 动态功耗。单位是每秒操作数每焦耳（OP/s/J），这在高性能计算和嵌入式领域都至关重要。

我们的仿真模型基于以下合理假设来估算平均周期数：

1. 由于输入移位，第一次迭代的商总是非零。
2. 后续迭代中，对于基数2原始SRT，q_i=0的概率为1/2。
3. 被除数和除数的有效位宽在0到总位宽（如64）之间均匀分布。这会导致一半的商为零，我们通过引入一个修正权重（0.25而非1）来纠正这种偏差，使模型更符合真实随机输入的统计特性。
4. 有符号和无符号除法以相等概率出现。

5.2 结果分析与最佳配置

如图6所示，在不同配置(b, l, s)中，(1, 4, 1)配置（基数2，4级级联，1级Skip-Zero）在目标FPGA上实现了最佳的“频率-能效”平衡。与关闭Skip-Zero的(1, 4, 0)配置相比，(1, 4, 1)的平均操作周期减少了约31%，而最大时钟频率和动态功耗几乎不变，从而使能效提升了近31%。这完美印证了Skip-Zero策略的价值：用几乎零代价的硬件，换取了显著的性能提升。

与Xuantie-910和Rocket-Chip的除法器相比，我们的最佳配置设计在平均操作频率上分别达到了1.13倍和1.59倍，在能效上分别达到了2.93倍和1.18倍。值得注意的是，我们的设计在绝对时钟频率上可能低于某些高度流水化、经过深度时序优化的商业设计（如Xuantie-910），但Skip-Zero策略带来的迭代次数减少，足以在整体操作频率上实现反超。这说明了在处理器设计中，降低关键操作的延迟（Latency）与提高时钟频率（Frequency）同等重要，甚至在某些场景下更有效。

5.3 常见问题与调试心得

在实现和测试Skip-Zero除法器的过程中，我们踩过一些坑，也总结了一些经验：

1. Skip-Zero单元与级联迭代的时序闭合：Skip-Zero单元的检测逻辑虽然简单，但它的输出控制着桶形移位器和迭代单元的使能。在高速设计中，需要确保这条控制路径的延迟不会成为新的关键路径。我们采用的方法是将Skip-Zero检测逻辑提前一级。即在当前时钟周期，不仅计算当前迭代的q_i，还并行预计算下一级迭代的Skip-Zero条件，这样控制信号可以提前准备好。
2. 处理最大跳过限制：s级Skip-Zero单元最多连续跳过s个迭代。当实际连续零商超过s时，硬件必须能正确处理。我们的设计是：当检测到连续s个零商后，在本周期执行s次移位，并正常进入下一个迭代单元。控制逻辑必须同步更新迭代计数器和商寄存器，确保状态一致。仿真时务必构造极端用例，测试连续零商长度等于和大于s的情况。
3. 验证的完备性：除法器的验证非常关键，尤其是涉及有符号数、边界情况和随机零商模式。我们搭建了一个基于UVM的验证环境，除了常规的随机测试外，还特别加入了：
   • 零商密集测试向量：主动构造被除数为除数一半左右的数字，使得中间过程产生大量连续零商。
   • 输入移位与Skip-Zero交互测试：测试小商值（需要大量输入移位）与迭代中零商同时发生的情况。
   • 与黄金模型（Golden Model）的周期精确比对：不仅比对最终结果，还比对中间重要状态（如每周期后的余数），确保迭代过程正确。
4. Chisel生成代码的可读性：Chisel在提高开发效率方面很棒，但生成的Verilog有时可读性不佳，不利于后端调试。我们养成了一个习惯：为关键模块（如SkipZeroUnit、SRTIterationStage）添加详细的Chisel注释（//），并使用chiselName宏，这些信息会体现在生成的Verilog模块名和信号名中，极大方便了波形调试。
5. 面积-性能权衡：s（Skip-Zero级数）并非越大越好。s增加会线性增加桶形移位器的宽度和零检测逻辑的复杂度。我们的实验显示，从s=1到s=2，性能提升的边际效应明显下降，但面积和功耗增加却比较明显。对于大多数应用，s=1或2是最具性价比的选择。

5.4 对系统集成的影响

将这样一个优化的除法器集成到完整的处理器流水线中，还需要考虑：

• 流水线互锁：除法是长延迟操作。需要确保在除法完成前，依赖其结果的后续指令被正确阻塞。Skip-Zero策略减少了平均延迟，但最坏情况延迟（全是非零商）没有改变。调度器和记分板的设计仍需以最坏情况延迟为准。
• 中断与异常处理：除法执行过程中可能被中断。需要保存除法器的完整状态（包括当前余数、商、迭代计数器等），以便中断返回后能恢复执行。我们的参数化设计使得状态寄存器的大小是可配置的。
• 与向量扩展的协同：对于支持RISC-V V扩展的处理器，可以考虑设计向量化的除法单元。Skip-Zero策略的思想同样可以应用，但需要权衡控制逻辑的复杂度和向量车道（Lane）间的负载均衡。

回过头看，Skip-Zero策略的成功在于它敏锐地抓住了SRT算法在真实运算中的统计特性——零商的高频出现，并用一个极其精巧的硬件改动将其利用起来。这提醒我们，在微架构优化中，有时与其追求更复杂的算法或更高的频率，不如深入分析常见执行路径，寻找这种“四两拨千斤”的优化机会。我们的参数化Chisel生成器框架，使得快速探索这类设计权衡变得非常方便，是架构探索的利器。未来，我们计划将这一策略扩展到平方��运算中，因为SRT算法同样广泛应用于平方根计算，其零商场景也有类似的优化潜力。