SRT除法器Skip-Zero优化：基于零商检测的动态迭代加速策略 1. 项目概述当除法运算成为性能瓶颈在处理器设计尤其是面向机器学习、科学计算等数据密集型应用的高性能处理器设计中算术逻辑单元ALU的性能至关重要。加法、乘法、移位等操作经过数十年优化其延迟已大幅降低甚至能在一个时钟周期内完成。然而除法运算却始终是一个“顽固分子”。其固有的迭代特性使得一次64位整数除法可能需要消耗数十个时钟周期远高于其他基本运算。在梯度下降、归一化、学习率调整等核心机器学习算法中除法操作虽不密集但一旦出现往往就躺在关键数据路径上成为拖慢整个训练或推理流程的“短板”。为了攻克这个难题硬件工程师们发展出了多种除法算法其中SRTSweeney-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_{i1} R_i - qi * D简化为R_{i1} R_i。这意味着新的部分余数就是旧的部分余数无需进行任何加法或减法运算。硬件上这等价于将部分余数寄存器左移一位为下一次迭代准备然后直接进入下一轮商数选择逻辑。然而在传统的串行迭代设计中即使qi0时钟周期依然被消耗电路仍然会经过一个完整的“商数选择 - 乘法对于高基- 加法 - 移位”的数据通路。这个通路的延迟Critical Path Delay决定了除法器能运行的最高时钟频率。对于qi0的情况其中的加法器或乘加单元完全在做无用功但其延迟却实实在在地限制了整个迭代步骤的速度。2.3 Skip-Zero的核心思想旁路与预判Skip-Zero策略的核心洞察在于识别qi0的操作其逻辑延迟远低于一次完整的迭代。判断qi是否为0只需要检查部分余数的最高几位对于Radix-2就是最高两位这是一个非常快速的组合逻辑操作。因此策略可以描述为检测在当前迭代开始时快速判断根据当前部分余数是否必然有qi0。旁路如果是则绕过本应在本周期进行的、延迟较高的完整迭代单元主要是加法器。合并与提前直接对部分余数执行移位操作并立即或在同一个周期的剩余时间里对移位后的新部分余数进行下一次商数位的判断。连续跳过如果判断下一个商数位还是0则可以继续重复此过程。从时序上看这相当于将多个连续的“零商”迭代压缩到了更短的时间内完成甚至可能在一个主时钟周期内完成多次“零商”迭代的判断和移位从而显著减少了完成整个除法运算所需的平均周期数。2.4 理论性能增益分析假设硬件支持连续跳过s级“零商”迭代即一个Skip-Zero单元能在一个周期内处理最多s个连续的零商位并且每次判断为零的概率是1/2Radix-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越大收益越高但硬件复杂度用于并行预判的逻辑也会增加。收益的增长是衰减的从s1到s2收益显著但s3之后收益递增就不那么明显了。Radix-2的黄金组合当b1Radix-2s1时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除法器三级流水线总体框架预处理阶段符号处理提取并保存输入被除数Dividend和除数Divisor的符号位然后将两者都转换为无符号数以便后续的无符号迭代算法处理。边界情况处理这是确保硬件鲁棒性的关键。我们严格遵循RISC-V指令集架构规范检测诸如“除数为零”和“溢出”如INT_MIN / -1等情况。这些特殊情况会在此阶段被捕获并直接生成预定义的结果如商为全1、抛出异常等绕过耗时的迭代阶段。输入规格化Input Shifting这是一个常见但重要的优化。由于迭代从最高有效位MSB开始如果被除数的高位有很多前导零就会产生大量无效的、商为0的迭代。预处理阶段会计算被除数和除数的有效位宽并通过左移除数、同时调整后续迭代计数的方式“跳过”这些前导零。这与Skip-Zero策略在迭代阶段跳过“零商”的思想异曲同工但发生在更早的阶段。迭代阶段这是除法器的核心也是Skip-Zero策略发挥作用的主战场。它包含多个级联的迭代单元Iteration Unit每个单元前都配备了一个Skip-Zero单元。后处理阶段结果移位将迭代得到的商和余数根据预处理阶段的规格化因子进行反向移位得到正确的数值。符号应用根据预处理保存的符号位信息为商和余数赋予正确的符号。3.2 迭代核心Skip-Zero单元与迭代单元的协同迭代阶段的详细硬件框图是理解设计精髓的关键。假设我们级联了l3个迭代单元其结构如图2所示。------------------------------------------------- | Iteration Stage | | | | --------------- --------------- ----- | R/Q - |--| Skip-Zero |-| Iteration |-| ... | | Reg | | Unit (s1) | | Unit (Radix-2)| | | | | --------------- --------------- ----- | | ^ ^ | | | | | | ---------------------------- | | | Partial Remainder Divisor | | | | Registers Table | | | ------------------------------ | -------------------------------------------------图2迭代阶段硬件框图示意以3级为例Skip-Zero单元位于每个迭代单元之前。其核心功能是并行检查当前部分余数的最高若干位判断接下来连续的多个商数位是否可能都为0。以s1为例它只需检查当前部分余数最高两位R[N:N-1]。如果判断为0它不会启动后方的迭代单元而是直接控制多路选择器将部分余数左移一位后的结果连同更新后的商寄存器直接反馈到本级Skip-Zero单元的输入端进行下一次判断。这个过程可以在一个时钟周期内发生多次直到遇到非零商或者达到s次跳过的上限才将数据和使能信号传递给后方的迭代单元。实现细节Skip-Zero单元本质上是一个优先级编码器Priority Encoder和移位逻辑的组合。它并行检查R[N:N-1],R[N-1:N-2], ...,R[N-s1:N-s]这些连续的比特对找出第一个不满足“零商”条件的位对然后根据这个位置生成相应的控制信号决定是执行移位还是进入标准迭代。迭代单元这是执行标准SRT迭代的模块。当Skip-Zero单元判断无法跳过或已跳过s次后数据进入迭代单元。对于Radix-2 SRT其内部包含商数选择逻辑QSL根据部分余数的最高几位和除数的次高几位对于高基查找或计算当前商数位qi。对于Radix-2这就是一个简单的组合逻辑输入2位部分余数输出qi ∈ {-1, 0, 1}。乘加MAC单元计算R_new R_old - qi * D。由于qi取值很小-1,0,1这个乘法退化为简单的取反或置零操作与加法器合并实际上就是一个带选择器的加法器。移位与合并逻辑将新的部分余数左移为下次迭代准备并将本次的商数位qi并入商寄存器中。级联迭代单元将多个迭代单元串联起来使得一个时钟周期内可以顺序执行多次迭代。这是提高吞吐量的经典方法但会增加该周期的关键路径延迟。Skip-Zero策略的引入使得在级联的入口处就有可能“压缩”掉一些零迭代从而在相同的级数下实现更高的平均迭代次数/周期。3.3 关键优化技巧与设计权衡除了Skip-Zero策略设计中还集成了其他几项关键优化共同塑造了最终的硬件形态部分余数查找表复用在高基如Radix-4设计中商数选择逻辑QSL通常需要一个查找表其输入是部分余数和除数的若干高位。当级联多个迭代单元时每个单元都需要这个表。我们发现在连续的迭代中除数D是不变的变化的只是部分余数R。因此我们可以只实例化一个共享的查找表存储与当前除数D相关的所有可能输出行。每个迭代单元根据自己当前的部分余数值从这个共享表中快速选择出对应的qi。这显著节省了高基设计中的查找表资源。校正阶段合并在SRT和非恢复除法算法中如果最终余数为负需要一个校正操作R R D, Q Q - 1。我们将这个校正逻辑集成到了最后一个迭代单元中。当级联执行时如果最后一轮迭代产生的余数为负校正操作可以在同一个周期的末尾逻辑中完成而无需占用一个额外的完整时钟周期。寄存器合并在迭代过程中部分余数R的位宽逐次减少因为高位被消耗而商数Q的位宽逐次增加。我们可以将这两个寄存器合并为一个宽寄存器其中一部分存储当前的R另一部分存储已累积的Q。每次迭代R左移消耗高位Q从低位并入新的商数位。这优化了寄存器资源的利用。参数化设计使用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的配置。性能评估主要关注三个指标最大时钟频率Fmax由综合最差负时序余量Worst Negative Slack决定反映了设计的时序性能。平均操作频率MOPS即Fmax / 平均执行周期数。这是衡量除法器实际吞吐量的关键指标。能效MOPS/J即平均操作频率 / 动态功耗。在移动和嵌入式场景下尤为重要。平均执行周期数通过软件建模估算基于以下合理假设输入移位后由于预处理进行了规格化第一次迭代产生的商数位总为非零。零商概率对于经典Radix-2 SRT后续每次迭代出现qi0的概率为1/2。有效位宽分布假设被除数和除数的有效位宽去除前导零后在0到64之间均匀分布。这会导致约一半的商结果本身为0我们通过赋予这些情况一个较小的修正权重0.25而非1来纠正这种偏差使模型更贴近真实运算的混合分布。4.2 设计空间探索与最佳配置我们使用(b, l, s)三元组来标识一个配置例如(1, 4, 1)表示Radix-2 (b1)级联4个迭代单元 (l4)使用1级Skip-Zero单元 (s1)。通过遍历参数空间我们得到了如图3所示的性能-能效散点图示意图。每个点代表一种配置。高能效 ^ | * (1,4,1) -- 最佳权衡点 | * | * * | * * * | * * * *(2,3,1) | * * * * | * * * * ---------------------------------- 高吞吐平均操作频率图3不同配置下除法器的性能-能效分布示意图分析发现Radix-2的优势在Skip-Zero策略的加持下Radix-2配置(b1)的表现普遍优于Radix-4(b2)。这是因为根据公式I (1-1/2^s)/b当s1时Radix-2能获得50%的迭代加速而Radix-4只能获得25%。Radix-4虽然每周期算力翻倍但其迭代单元更复杂需要更宽的QSL和乘加逻辑导致关键路径延迟增加时钟频率Fmax下降。综合下来Radix-2配合Skip-Zero在吞吐和能效上找到了更好的平衡。级联数l的影响增加l可以提高每周期完成的迭代次数从而降低总周期数提升吞吐。但l增大会线性增加组合逻辑深度降低Fmax同时增加面积和功耗。存在一个收益递减的拐点。Skip-Zero级数s的影响s1带来的收益最为显著几乎不增加关键路径延迟仅增加少量多路选择器和判断逻辑却能将迭代阶段的平均速度提升近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处理器中的除法器玄铁C910 (Xuantie-910) 内置除法器这是一款商用的高性能RISC-V处理器核。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比特比较器和一个优先级编码器。对于s1这仅仅是几个门电路的代价。与一个完整的Radix-2迭代单元包含一个商数选择器、一个多路选择器和一个加法器相比其面积和功耗开销几乎可以忽略不计。这正是该策略的魅力所在以微小的硬件代价换取显著的性能提升。5. 实现中的挑战与避坑指南在将Skip-Zero策略从算法转化为实际Chisel代码并最终部署到FPGA的过程中我们遇到了一系列工程挑战也积累了一些宝贵的经验。5.1 时序收敛与关键路径管理尽管Skip-Zero单元本身延迟很低但当它与级联的迭代单元结合并试图在一个周期内完成“判断-跳过-再判断”的多步操作时可能会形成新的关键路径。挑战Skip-Zero单元的输出选择信号和移位后的数据需要反馈到其自身的输入形成组合逻辑环。当s1时这个环的延迟会随着s增大而增加。如果这个环的延迟加上寄存器建立时间超过了时钟周期就会导致时序违例。解决方案流水线化Skip-Zero逻辑对于s较大的设计可以将多级跳过判断本身进行流水线划分但这会引入额外的流水线气泡抵消部分收益需要精细权衡。限制最大跳过级数我们的实验表明s1或s2是性价比最高的选择。对于s1这个反馈环非常短通常不会成为时序瓶颈。仔细的综合约束在综合工具中需要对这部分组合反馈路径设置合理的时序约束引导工具进行优化。5.2 与输入规格化Input Shifting的协同预处理阶段的输入规格化跳过被除数前导零和迭代阶段的Skip-Zero跳过中间过程的零商是两种不同的优化它们需要协同工作而不是相互冲突。潜在问题输入规格化左移了除数改变了迭代过程中与部分余数比较的基准。这会不会影响Skip-Zero单元中判断qi0的逻辑解决方案不会。因为SRT算法的商数选择规则是相对于规格化后的除数定义的。只要Skip-Zero单元的判断逻辑是基于当前迭代的“部分余数高位”和“当前迭代所看到的除数缩放值”那么它就是正确的。在硬件实现上输入规格化阶段会记录一个“移位量”这个量会影响迭代的总次数和最终结果的反向调整但不会影响每步迭代中商数选择逻辑的规则。两者是正交的优化可以叠加。5.3 验证策略与测试向量生成一个复杂的、参数化的除法器设计其验证工作至关重要。我们采用了多层次验证策略单元测试ChiselTest为每个模块如Skip-Zero单元、迭代单元编写独立的测试验证其输入输出行为是否符合算法预期。特别是对Skip-Zero单元需要覆盖所有可能的连续零商模式。随机化系统测试使用Chisel的peek/poke接口或配合Verilator对完整的除法器模块进行大量随机测试。测试向量包括边界值测试0 1 最大正值最小负值等。随机数测试生成数百万组随机的64位有符号/无符号数对将硬件计算结果与软件参考模型如Scala的BigInt除法的结果进行比对。定向压力测试专门生成那些容易产生连续零商的被除数/除数对以充分锻炼Skip-Zero路径。形式化验证可选对于核心的商数选择逻辑可以使用SMT求解器进行形式化验证确保其数学正确性。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这样“顺势而为”的微创新往往能以最小的代价收获意想不到的性能红利。