SRT除法器Skip-Zero优化：基于零商检测的动态迭代加速策略

1. 项目概述：当除法运算成为性能瓶颈

在处理器设计，尤其是面向机器学习、科学计算等数据密集型应用的高性能处理器设计中，算术逻辑单元（ALU）的性能至关重要。加法、乘法、移位等操作经过数十年优化，其延迟已大幅降低，甚至能在一个时钟周期内完成。然而，除法运算却始终是一个“顽固分子”。其固有的迭代特性，使得一次64位整数除法可能需要消耗数十个时钟周期，远高于其他基本运算。在梯度下降、归一化、学习率调整等核心机器学习算法中，除法操作虽不密集，但一旦出现，往往就躺在关键数据路径上，成为拖慢整个训练或推理流程的“短板”。

为了攻克这个难题，硬件工程师们发展出了多种除法算法，其中SRT（Sweeney-Robertson-Tocher）算法因其在迭代延迟和硬件实现复杂度之间的优异平衡，成为了现代高性能处理器除法器的首选。它通过允许商数位为负，放宽了每步迭代的精度要求，从而简化了商数选择逻辑，并天然支持高基（Radix）运算，即每次迭代能产生多位商数。但即便如此，SRT除法器的延迟依然可观。

一个常被忽视的细节是：在SRT算法的迭代过程中，有相当一部分迭代产生的“部分商”是零。在传统的实现中，即便商为零，电路仍需走完一次完整的迭代流程（包括查表、乘法、加法等），这无疑是一种计算资源的浪费。如果我们能识别出这些“零商”迭代，并为其设计一条“快速通道”，是否能显著提升整体性能呢？这正是“Skip-Zero策略”诞生的核心动机。它不是对SRT算法的根本性改变，而是一种巧妙的微架构优化，旨在榨干算法中每一处潜在的效率红利。本文将深入拆解这一策略的原理、硬件实现细节，并分享基于Chisel硬件构造语言进行参数化设计、在FPGA上验证性能的完整过程与实战心得。

2. 核心原理：为什么可以“跳过”零？

要理解Skip-Zero策略为何有效，我们必须先回到SRT算法的运作机制，特别是其最基础的Radix-2（基2）版本。Radix-2 SRT每次迭代产生一个商数位，其值可以是-1， 0， 或+1。决定这个值的，是当前部分余数（Partial Remainder）的最高几位。

2.1 SRT算法中的“零商”区间

让我们看一个简化的模型。假设我们将除数和部分余数都归一化到某个范围以便分析。在经典的Radix-2 SRT算法中，商数选择规则可以通过一个二维查找表（或等价的组合逻辑）来定义，其输入是部分余数的最高两位。

一个关键的特性是：存在一个明确的“零商”区间。当部分余数的值落在某个范围内时，算法会判定当前商数位为0。具体来说，在归一化的表示下，如果部分余数R满足-D/2 <= R < D/2（其中D是除数），那么这一位的商就是0。从概率上讲，如果除数和被除数在运算过程中是均匀分布的（这是一个合理的近似），那么出现“零商”的概率接近50%。

注意：这里提到的“经典”或“原始”SRT算法，与后续一些变体（如Variant SRT）在零商区间的定义上有所不同。变体算法为了简化高基扩展，改变了约束条件，导致零商出现的概率降至约1/3。这也是本设计选择经典SRT算法作为基础的重要原因之一。

2.2 “零商”迭代的硬件本质

当商数位qi = 0时，迭代的核心公式R_{i+1} = R_i - qi * D简化为R_{i+1} = R_i。这意味着新的部分余数就是旧的部分余数，无需进行任何加法或减法运算。硬件上，这等价于将部分余数寄存器左移一位（为下一次迭代准备），然后直接进入下一轮商数选择逻辑。

然而，在传统的串行迭代设计中，即使qi=0，时钟周期依然被消耗，电路仍然会经过一个完整的“商数选择 -> 乘法（对于高基）-> 加法 -> 移位”的数据通路。这个通路的延迟（Critical Path Delay）决定了除法器能运行的最高时钟频率。对于qi=0的情况，其中的加法器（或乘加单元）完全在做无用功，但其延迟却实实在在地限制了整个迭代步骤的速度。

2.3 Skip-Zero的核心思想：旁路与预判

Skip-Zero策略的核心洞察在于：识别qi=0的操作，其逻辑延迟远低于一次完整的迭代。判断qi是否为0，只需要检查部分余数的最高几位（对于Radix-2，就是最高两位），这是一个非常快速的组合逻辑操作。

因此，策略可以描述为：

1. 检测：在当前迭代开始时，快速判断根据当前部分余数，是否必然有qi=0。
2. 旁路：如果是，则绕过本应在本周期进行的、延迟较高的完整迭代单元（主要是加法器）。
3. 合并与提前：直接对部分余数执行移位操作，并立即（或在同一个周期的剩余时间里）对移位后的新部分余数进行下一次商数位的判断。
4. 连续跳过：如果判断下一个商数位还是0，则可以继续重复此过程。

从时序上看，这相当于将多个连续的“零商”迭代压缩到了更短的时间内完成，甚至可能在一个主时钟周期内完成多次“零商”迭代的判断和移位，从而显著减少了完成整个除法运算所需的平均周期数。

2.4 理论性能增益分析

假设硬件支持连续跳过s级“零商”迭代（即一个Skip-Zero单元能在一个周期内处理最多s个连续的零商位），并且每次判断为零的概率是1/2（Radix-2经典SRT），那么单次使用该单元可跳过的平均迭代次数为：E(skips) = 1*(1/2) + 2*(1/4) + ... + s*(1/2^s) = 1 - 1/2^s

对于Radix-2b的SRT算法，每次标准迭代能产生b个商数位。引入Skip-Zero后，整体的加速比S为：S = 1 + (1 - 1/2^s) / b

性能提升I则为：I = S - 1 = (1 - 1/2^s) / b

这个公式清晰地揭示了几个关键点：

• 基数b的影响：基数越大（每次迭代算得位数越多），Skip-Zero带来的相对收益I越小。因为分母b变大了。这使得Skip-Zero策略在Radix-2设计中收益最为显著。
• 跳过级数s的影响：s越大，收益越高，但硬件复杂度（用于并行预判的逻辑）也会增加。收益的增长是衰减的，从s=1到s=2收益显著，但s=3之后收益递增就不那么明显了。
• Radix-2的黄金组合：当b=1（Radix-2），s=1时，I = (1 - 1/2)/1 = 50%。这意味着理论上，迭代阶段的平均速度可以提升50%。这是一个非常可观的数字，尤其考虑到它可能以极小的硬件开销实现。

3. 硬件架构设计与实现细节

有了理论支撑，下一步就是将其转化为实际的硬件电路。我们采用Chisel硬件构造语言来构建一个参数化、可配置的除法器生成器，以便灵活探索不同参数（基数、迭代单元级联数、Skip-Zero级数）下的性能与面积权衡。

3.1 整体数据通路与三级流水

整个除法器的硬件架构可以清晰地划分为三个阶段，如图1所示，这构成了一个典型的三级流水线。理解这个整体框架是分析细节优化的基础。

+-----------------------+ | Pre-processing | | 1. Sign Handling | | 2. Corner Case Check | | 3. Input Normalization| +-----------+-----------+ | v +-----------------------+ | Iteration | | (Core Loop with | | Skip-Zero Units) | +-----------+-----------+ | v +-----------------------+ | Post-processing | | 1. Result Shifting | | 2. Sign Application | +-----------------------+

图1：除法器三级流水线总体框架

1. 预处理阶段：

   • 符号处理：提取并保存输入被除数（Dividend）和除数（Divisor）的符号位，然后将两者都转换为无符号数，以便后续的无符号迭代算法处理。
   • 边界情况处理：这是确保硬件鲁棒性的关键。我们严格遵循RISC-V指令集架构规范，检测诸如“除数为零”和“溢出”（如INT_MIN / -1）等情况。这些特殊情况会在此阶段被捕获，并直接生成预定义的结果（如商为全1、抛出异常等），绕过耗时的迭代阶段。
   • 输入规格化（Input Shifting）：这是一个常见但重要的优化。由于迭代从最高有效位（MSB）开始，如果被除数的高位有很多前导零，就会产生大量无效的、商为0的迭代。预处理阶段会计算被除数和除数的有效位宽，并通过左移除数、同时调整后续迭代计数的方式，“跳过”这些前导零。这与Skip-Zero策略在迭代阶段跳过“零商”的思想异曲同工，但发生在更早的阶段。

2. 迭代阶段：这是除法器的核心，也是Skip-Zero策略发挥作用的主战场。它包含多个级联的迭代单元（Iteration Unit），每个单元前都配备了一个Skip-Zero单元。

3. 后处理阶段：

   • 结果移位：将迭代得到的商和余数，根据预处理阶段的规格化因子进行反向移位，得到正确的数值。
   • 符号应用：根据预处理保存的符号位信息，为商和余数赋予正确的符号。

3.2 迭代核心：Skip-Zero单元与迭代单元的协同

迭代阶段的详细硬件框图是理解设计精髓的关键。假设我们级联了l=3个迭代单元，其结构如图2所示。

+-------------------------------------------------+ | Iteration Stage | | | | +---------------+ +---------------+ +-----+ | R/Q -> |-->| Skip-Zero |->| Iteration |->| ... | | Reg | | Unit (s=1) | | Unit (Radix-2)| | | | | +---------------+ +---------------+ +-----+ | | ^ ^ | | | | | | +------+----------------+------+ | | | Partial Remainder & Divisor | | | | Registers & Table | | | +------------------------------+ | +-------------------------------------------------+

图2：迭代阶段硬件框图示意（以3级为例）

• Skip-Zero单元：位于每个迭代单元之前。其核心功能是并行检查当前部分余数的最高若干位，判断接下来连续的多个商数位是否可能都为0。以s=1为例，它只需检查当前部分余数最高两位R[N:N-1]。如果判断为0，它不会启动后方的迭代单元，而是直接控制多路选择器，将部分余数左移一位后的结果，连同更新后的商寄存器，直接反馈到本级Skip-Zero单元的输入端，进行下一次判断。这个过程可以在一个时钟周期内发生多次，直到遇到非零商，或者达到s次跳过的上限，才将数据和使能信号传递给后方的迭代单元。

  • 实现细节：Skip-Zero单元本质上是一个优先级编码器（Priority Encoder）和移位逻辑的组合。它并行检查R[N:N-1],R[N-1:N-2], ...,R[N-s+1:N-s]这些连续的比特对，找出第一个不满足“零商”条件的位对，然后根据这个位置生成相应的控制信号，决定是执行移位还是进入标准迭代。

• 迭代单元：这是执行标准SRT迭代的模块。当Skip-Zero单元判断无法跳过，或已跳过s次后，数据进入迭代单元。对于Radix-2 SRT，其内部包含：

  1. 商数选择逻辑（QSL）：根据部分余数的最高几位（和除数的次高几位，对于高基）查找或计算当前商数位qi。对于Radix-2，这就是一个简单的组合逻辑，输入2位部分余数，输出qi ∈ {-1, 0, 1}。
  2. 乘加（MAC）单元：计算R_new = R_old - qi * D。由于qi取值很小（-1,0,1），这个乘法退化为简单的取反或置零操作，与加法器合并，实际上就是一个带选择器的加法器。
  3. 移位与合并逻辑：将新的部分余数左移（为下次迭代准备），并将本次的商数位qi并入商寄存器中。

• 级联迭代单元：将多个迭代单元串联起来，使得一个时钟周期内可以顺序执行多次迭代。这是提高吞吐量的经典方法，但会增加该周期的关键路径延迟。Skip-Zero策略的引入，使得在级联的入口处就有可能“压缩”掉一些零迭代，从而在相同的级数下实现更高的平均迭代次数/周期。

3.3 关键优化技巧与设计权衡

除了Skip-Zero策略，设计中还集成了其他几项关键优化，共同塑造了最终的硬件形态：

1. 部分余数查找表复用：在高基（如Radix-4）设计中，商数选择逻辑（QSL）通常需要一个查找表，其输入是部分余数和除数的若干高位。当级联多个迭代单元时，每个单元都需要这个表。我们发现，在连续的迭代中，除数D是不变的，变化的只是部分余数R。因此，我们可以只实例化一个共享的查找表，存储与当前除数D相关的所有可能输出行。每个迭代单元根据自己当前的部分余数值，从这个共享表中快速选择出对应的qi。这显著节省了高基设计中的查找表资源。

2. 校正阶段合并：在SRT和非恢复除法算法中，如果最终余数为负，需要一个校正操作（R = R + D, Q = Q - 1）。我们将这个校正逻辑集成到了最后一个迭代单元中。当级联执行时，如果最后一轮迭代产生的余数为负，校正操作可以在同一个周期的末尾逻辑中完成，而无需占用一个额外的完整时钟周期。

3. 寄存器合并：在迭代过程中，部分余数R的位宽逐次减少（因为高位被消耗），而商数Q的位宽逐次增加。我们可以将这两个寄存器合并为一个宽寄存器，其中一部分存储当前的R，另一部分存储已累积的Q。每次迭代，R左移消耗高位，Q从低位并入新的商数位。这优化了寄存器资源的利用。

4. 参数化设计：使用Chisel语言，我们将关键设计点参数化：

   • data_width (w)：操作数位宽（如32/64位）。
   • iteration_radix (b)：迭代基数2^b。
   • level_of_iteration_units (l)：级联的迭代单元数（每周期迭代次数）。
   • skip_zero_level (s)：Skip-Zero单元的跳过级数。 这种参数化设计允许我们快速进行设计空间探索（DSE），寻找在目标工艺（如FPGA或ASIC）下的最佳性能-面积-功耗平衡点。

4. 性能评估与最佳权衡点探索

理论分析和架构设计之后，必须通过实际的硬件综合与仿真来验证效果。我们使用Xilinx Vivado 2019.1对设计进行FPGA综合（目标器件：xc7a35tcpg236-1），并通过软件建模来估算平均执行周期数。

4.1 实验方法与假设

为了公平评估和对比，我们固定操作数位宽为64位，以匹配对比对象（如玄铁C910）的配置。性能评估主要关注三个指标：

1. 最大时钟频率（Fmax）：由综合���最差负时序余量（Worst Negative Slack）决定，反映了设计的时序性能。
2. 平均操作频率（MOPS）：即Fmax / 平均执行周期数。这是衡量除法器实际吞吐量的关键指标。
3. 能效（MOPS/J）：即平均操作频率 / 动态功耗。在移动和嵌入式场景下尤为重要。

平均执行周期数通过软件建模估算，基于以下合理假设：

• 输入移位后：由于预处理进行了规格化，第一次迭代产生的商数位总为非零。
• 零商概率：对于经典Radix-2 SRT，后续每次迭代出现qi=0的概率为1/2。
• 有效位宽分布：假设被除数和除数的有效位宽（去除前导零后）在0到64之间均匀分布。这会导致约一半的商结果本身为0，我们通过赋予这些情况一个较小的修正权重（0.25而非1）来纠正这种偏差，使模型更贴近真实运算的混合分布。

4.2 设计空间探索与最佳配置

我们使用(b, l, s)三元组来标识一个配置，例如(1, 4, 1)表示Radix-2 (b=1)，级联4个迭代单元 (l=4)，使用1级Skip-Zero单元 (s=1)。

通过遍历参数空间，我们得到了如图3所示的性能-能效散点图（示意图）。每个点代表一种配置。

高能效 ^ | * (1,4,1) <-- 最佳权衡点 | * | * * | * * * | * * * *(2,3,1) | * * * * | * * * * +----------------------------------> 高吞吐（平均操作频率）

图3：不同配置下除法器的性能-能效分布示意图

分析发现：

• Radix-2的优势：在Skip-Zero策略的加持下，Radix-2配置(b=1)的表现普遍优于Radix-4(b=2)。这是因为根据公式I = (1-1/2^s)/b，当s=1时，Radix-2能获得50%的迭代加速，而Radix-4只能获得25%。Radix-4虽然每周期算力翻倍，但其迭代单元更复杂（需要更宽的QSL和乘加逻辑），导致关键路径延迟增加，时钟频率Fmax下降。综合下来，Radix-2配合Skip-Zero在吞吐和能效上找到了更好的平衡。
• 级联数l的影响：增加l可以提高每周期完成的迭代次数，从而降低总周期数，提升吞吐。但l增大会线性增加组合逻辑深度，降低Fmax，同时增加面积和功耗。存在一个收益递减的拐点。
• Skip-Zero级数s的影响：s=1带来的收益最为显著，几乎不增加关键路径延迟（仅增加少量多路选择器和判断逻辑），却能将迭代阶段的平均速度提升近50%。将s增加到2或3，带来的额外收益（1/4,1/8）相对较小，但硬件复杂度（并行判断逻辑）却增加较多，性价比下降。

最佳权衡点：综合评估后，配置(1, 4, 1)脱颖而出，达到了性能与能效的最佳平衡。其平均操作频率达到11.39 MOPS，平均能效达到421.8 MOPS/J。

4.3 与现有设计的对比

为了证明Skip-Zero策略的有效性，我们在相同条件下（64位，相同FPGA器件与工具链）综合测试了业界知名的开源RISC-V处理器中的除法器：

1. 玄铁C910 (Xuantie-910) 内置除法器：这是一款商用的高性能RISC-V处理器核。
2. Rocket-Chip 生成器中的除法器：伯克利大学推出的经典RISC-V处理器生成器，其除法器也支持参数化配置，我们选取了其性能最好的4级迭代配置进行对比。

对比结果令人振奋（数据为归一化值，以玄铁C910为基准1.0）：

• 相对于玄铁C910：我们的(1,4,1)设计在平均操作频率上达到了1.13倍，在能效上达到了2.93倍的提升。
• 相对于Rocket-Chip：我们的设计在平均操作频率上达到了1.59倍，在能效上达到了1.18倍的提升。

实操心得：这个对比结果尤其值得玩味。玄铁C910作为商业IP，其除法器很可能经过了深入的时序优化，其最大时钟频率Fmax通常比我们的学术原型设计要高。然而，Skip-Zero策略通过大幅降低平均迭代周期数，使得即使我们的绝对时钟频率略低，平均操作频率（吞吐量）依然实现了反超。这充分说明了微架构优化（Architectural Optimization）有时比单纯的时序优化（Timing Optimization）更能带来系统性的性能收益。在评估硬件模块时，不能只看最高频率，更要关注其完成一个任务所需的平均周期数（IPC的一种体现）。

4.4 资源开销分析

Skip-Zero策略的硬件开销主要来自Skip-Zero单元本身，其核心是若干组2比特比较器和一个优先级编码器。对于s=1，这仅仅是几个门电路的代价。与一个完整的Radix-2迭代单元（包含一个商数选择器、一个多路选择器和一个加法器）相比，其面积和功耗开销几乎可以忽略不计。这正是该策略的魅力所在：以微小的硬件代价，换取显著的性能提升。

5. 实现中的挑战与避坑指南

在将Skip-Zero策略从算法转化为实际Chisel代码并最终部署到FPGA的过程中，我们遇到了一系列工程挑战，也积累了一些宝贵的经验。

5.1 时序收敛与关键路径管理

尽管Skip-Zero单元本身延迟很低，但当它与级联的迭代单元结合，并试图在一个周期内完成“判断-跳过-再判断”的多步操作时，可能会形成新的关键路径。

• 挑战：Skip-Zero单元的输出（选择信号和移位后的数据）需要反馈到其自身的输入，形成组合逻辑环。当s>1时，这个环的延迟会随着s增大而增加。如果这个环的延迟加上寄存器建立时间超过了时钟周期，就会导致时序违例。
• 解决方案：
  1. 流水线化Skip-Zero逻辑：对于s较大的设计，可以将多级跳过判断本身进行流水线划分，但这会引入额外的流水线气泡，抵消部分收益，需要精细权衡。
  2. 限制最大跳过级数：我们的实验表明s=1或s=2是性价比最高的选择。对于s=1，这个反馈环非常短，通常不会成为时序瓶颈。
  3. 仔细的综合约束：在综合工具中，需要对这部分组合反馈路径设置合理的时序约束，引导工具进行优化。

5.2 与输入规格化（Input Shifting）的协同

预处理阶段的输入规格化（跳过被除数前导零）和迭代阶段的Skip-Zero（跳过中间过程的零商）是两种不同的优化，它们需要协同工作，而不是相互冲突。

• 潜在问题：输入规格化左移了除数，改变了迭代过程中与部分余数比较的基准。这会不会影响Skip-Zero单元中判断qi=0的逻辑？
• 解决方案：不会。因为SRT算法的商数选择规则是相对于规格化后的除数定义的。只要Skip-Zero单元的判断逻辑是基于当前迭代的“部分余数高位”和“当前迭代所看到的除数缩放值”，那么它就是正确的。在硬件实现上，输入规格化阶段会记录一个“移位量”，这个量会影响迭代的总次数和最终结果的反向调整，但不会影响每步迭代中商数选择逻辑的规则。两者是正交的优化，可以叠加。

5.3 验证策略与测试向量生成

一个复杂的、参数化的除法器设计，其验证工作至关重要。我们采用了多层次验证策略：

1. 单元测试（ChiselTest）：为每个模块（如Skip-Zero单元、迭代单元）编写独立的测试，验证其输入输出行为是否符合算法预期。特别是对Skip-Zero单元，需要覆盖所有可能的连续零商模式。
2. 随机化系统测试：使用Chisel的peek/poke接口或配合Verilator，对完整的除法器模块进行大量随机测试。测试向量包括：
   • 边界值测试：0， 1， 最大正值，最小负值等。
   • 随机数测试：生成数百万组随机的64位有符号/无符号数对，将硬件计算结果与软件参考模型（如Scala的BigInt除法）的结果进行比对。
   • 定向压力测试：专门生成那些容易产生连续零商的被除数/除数对，以充分锻炼Skip-Zero路径。
3. 形式化验证（可选）：对于核心的商数选择逻辑，可以使用SMT求解器进行形式化验证，确保其数学正确性。
4. FPGA在位验证：将生成的设计综合到FPGA，通过JTAG/UART等接口与上位机通信，运行更长时间的测试套件，确保在实际硬件上也能稳定工作。

5.4 Chisel编码实践与可配置性

使用Chisel这类硬件构造语言（HDL）的优势在于其强大的参数化和元编程能力。

• 定义可配置参数类：我们创建了一个DividerParams的case class，封装所有可配置参数（w,b,l,s, 是否支持有符号等）。这比使用全局变量或模块参数更清晰、类型更安全。
• 利用Scala生成逻辑：Skip-Zero单元中并行判断s级零商的逻辑，可以用一个for循环简洁地生成，代码可读性和可维护性远优于手动实例化s个比较器。
• 条件生成硬件：通过if (params.s > 0) { ... }来条件性地实例化Skip-Zero单元。当params.s = 0时，就退化为传统的迭代器。这使我们的代码库能同时支持传统设计和优化设计。
• 注意寄存器初始化：在Chisel中，要特别注意带有反馈路径的组合逻辑的寄存器初始化，避免上电后进入不确定状态。使用RegInit明确指定初始值。

6. 总结与展望

Skip-Zero策略为SRT除法器的优化提供了一条新颖且高效的路径。它敏锐地抓住了算法中“零商迭代”这一低延迟操作的机会窗口，通过简单的硬件逻辑将其识别并“加速”跳过，从而在不显著增加关键路径延迟和功耗的前提下，大幅降低了除法的平均执行延迟。我们的实践表明，在Radix-2 SRT基础上，仅需1级Skip-Zero单元，就能带来接近50%的迭代阶段加速，最终在整体性能上超越了一些经过深度优化的工业级设计。

从更广阔的视角看，这种思路可以归纳为一种“异构迭代”或“动态步进”的微架构思想。传统的迭代电路每一步都走相同的、最慢的路径（以最坏情况设计）。而Skip-Zero策略则根据当前迭代的实际计算需求，动态选择走“快速通道”（仅移位）还是“标准通道”（完整计算）。这种思想可以推广到其他迭代算法中，只要算法中存在某些迭代步骤的计算复杂度显著低于其他步骤。

未来的工作可以沿着几个方向展开：一是将优化后的除法器集成到一个完整的RISC-V处理器流水线中，评估其在真实负载（如SPECint基准测试）下的整体性能收益。二是探索该策略在其他基数（如Radix-4）以及其他迭代算法（如平方根算法）中的应用潜力。三是研究在更先进工艺节点（如ASIC）下，该策略对面积、功耗和时序的最终影响，进一步提炼其设计指导原则。

对于正在设计高性能处理器的工程师而言，当除法性能成为瓶颈时，除了考虑增加迭代单元级联数、提高基数这些传统方法外，不妨审视一下算法本身的数据特性。像Skip-Zero这样“顺势而为”的微创新，往往能以最小的代价，收获意想不到的性能红利。