1. 项目概述与核心价值在处理器微架构设计尤其是面向高性能计算和机器学习的专用加速器领域除法器一直是个让人又爱又恨的模块。爱的是从梯度下降中的学习率调整到信号处理中的归一化运算除法无处不在是算法实现的基础恨的是它的硬件实现往往伴随着高延迟和低吞吐量动不动就占据几十个时钟周期一不小心就成了整个数据通路的“堵点”。我这些年参与过好几个处理器核的设计每次做性能分析除法单元尤其是整数除法的延迟曲线总是最刺眼的那一根。传统的硬件除法算法比如恢复除法Restoring和非恢复除法Non-Restoring原理直观但效率有限难以满足现代处理器的性能需求。SRTSweeney-Robertson-Tocher算法因此成为了高性能除法器的主流选择。它通过引入冗余的商数集和基于查找表LUT的快速商数选择逻辑在保持合理硬件复杂度的同时支持高基数的迭代从而显著提升计算速度。简单来说SRT把一次复杂的比较-减法操作简化成了查表可能的一次加法/减法迭代的关键路径短了频率就能做上去。然而SRT算法也并非完美。在基数为2Radix-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_iq_i ∈ {-a, ..., 0, ..., a}使得新的部分余数R R - q_i * D仍然落在下一个迭代所要求的范围内。2.2 商选择表SRT算法的“决策大脑”商选择表是SRT算法的灵魂。以基数2Radix-2的原始SRT算法为例部分商q_i的取值范围是{-1, 0, 1}。选择逻辑极其简单仅观察部分余数R的最高两位符号位和最高数值位。如图2(a)所示在一个归一化的数轴上除数D被缩放至[0.5, 1)区间根据R的这两位可以直接映射到q_i。例如当R的最高两位为01表示R在[0.5D, D)区间则q_i1为10表示R在[-D, -0.5D)区间则q_i-1为00或11表示R在[-0.5D, 0.5D)区间则q_i0。这个查找操作延迟极低。对于基数4Radix-4的SRTq_i的取值范围会更大例如{-2,-1,0,1,2}一次迭代能产生2个商位。此时商选择需要参考R的更多位如前3位以及除数的次高位。虽然查找表变大了但迭代次数减半在追求高吞吐量的设计中经常能带来净收益。这里有一个关键点也是我们选择原始SRT算法而非其变种Variant SRT作为Skip-Zero策略基础的原因。如原文图2所示在基数2下原始SRT算法中q_i0的概率区域图2a中灰色区域约占整个可行区域的一半。而在变种SRT算法中图2cq_i0的区域缩小到了约1/3。更高的“零商”概率意味着Skip-Zero策略有更大的发挥空间和优化潜力。尽管变种SRT在高基数下有其优势解决了基数缩减问题但在我们聚焦的、Skip-Zero收益最大的基数2场景下原始SRT是更优的选择。2.3 迭代的硬件流程一次循环做了什么一次典型的SRT迭代以基数2为例在硬件上的步骤如下这也是我们后面优化时要针对的环节商选择根据当前部分余数R的固定高位如最高2位查询商选择表得到部分商q_i。除数倍数生成根据q_i的值-1, 0, 1生成相应的除数倍数-D 0 D。对于基数2这通常只需一个取反操作和/或一个多路选择器无需真正的乘法器。部分余数更新计算R_new R - q_i * D。当q_i0时R_new R当q_i±1时需要一个加法器来执行R ± D。移位与准备将R_new左移一位对于基数2作为下一轮迭代的输入R。同时将q_i累加到最终的商寄存器中。可以看到当q_i0时步骤3中的加法器是完全不需要的。而加法器通常是迭代周期中延迟最大的部件。Skip-Zero策略瞄准的正是跳过”这个加法器延迟的机会。3. Skip-Zero策略的硬件实现与设计权衡理解了SRT迭代中“零商”场景的低延迟特性后Skip-Zero策略的实现思路就非常直观了检测并跳过那些不需要加法操作的迭代周期。但如何高效、正确地实现里面有不少细节。3.1 基础的单级Skip-Zero单元最直接的实现是在每个迭代单元前增加一个“预判”逻辑。对于基数2 SRT这个逻辑非常简单它并行检查当前部分余数R的最高两位R[N:N-1]。如果这两位的组合对应于q_i0在原始SRT中即00或11那么本次迭代的“有效操作”就只是将R左移一位。我们可以立即启动对移位后结果R1的最高两位R[N-1:N-2]的检查以判断下一个迭代的q_{i1}。如果连续检测到多个q_i0理论上我们可以连续移位多次。硬件上我们可以设计一个多级的零检测链。例如一个s级的Skip-Zero单元可以同时检查R的从最高位开始的s个重叠的2位窗口即[N:N-1],[N-1:N-2], ...,[N-s1:N-s]。通过一个前导零检测Leading Zero Detection风格的逻辑我们可以一次性计算出从当前位开始连续有多少个迭代的q_i会是0然后控制一个桶形移位器Barrel Shifter将R一次性左移相应的位数。图4展示的就是这样的并行选择逻辑。其核心是一组异或门和优先级编码器。每个2位窗口通过一个简单的组合逻辑比如两位相等则q_i0产生一个“零商”标志。然后一个优先级检测电路类似于找第一个‘1’的电路但这里是找第一个‘非零商’标志可以确定最多能连续跳过的迭代次数ss ≤ s。这个电路的延迟非常小远小于一个完整加法器的延迟。3.2 性能增益的理论分析Skip-Zero策略带来的加速比是可以定量分析的。假设硬件支持s级跳过即最多连续跳过s个零商迭代并且每次迭代出现q_i0的概率是p对于基数2原始SRTp≈1/2。那么平均每次使用Skip-Zero单元可以跳过的迭代次数期望值是E[skip] p p^2 ... p^s (1 - p^s) / (1 - p) * p。当p1/2时化简为E[skip] 1 - (1/2)^s。对于一个基数2^b的SRT除法完成整个除法所需的平均迭代次数约为N/bN为商的有效位数。引入Skip-Zero后平均每次“有效迭代”指需要执行加法操作的迭代可以附带跳过E[skip]个“零商迭代”。因此总的加速因子S可以近似表示为S ≈ 1 E[skip] / b 1 (1 - (1/2)^s) / b对于最实用的s1, b1基数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进行下一轮的判断如此往复。这种设计有两个关键优势隐藏Skip-Zero检测延迟Skip-Zero单元的检测延迟可以部分或全部被隐藏在前一级迭代单元的计算周期内特别是当级间采用流水线寄存器时。动态适应零商模式除法的中间过程零商出现是随机的这种每级前都检测的设计可以动态地、最大化地利用每一个跳过的机会。注意在级联设计中需要仔细处理数据通路。当某级Skip-Zero单元跳过了k个迭代时它需要通知后续的逻辑商寄存器需要累加k个0并且迭代计数器需要减去k。这需要额外的控制逻辑但复杂度不高。3.4 参数化设计寻找最佳平衡点为了评估Skip-Zero策略在不同配置下的效果并找到性能、面积、功耗的最佳平衡点我们用Chisel实现了一个高度参数化的除法器生成器。主要参数包括数据位宽支持常见的32位、64位等。迭代基数支持基数2、基数4等。级联级数单个周期内串联的迭代单元数量。Skip-Zero级数每个Skip-Zero单元支持的最大连续跳过次数。通过脚本化地遍历这些参数组合进行综合和仿真我们可以绘制出设计空间探索图。如图6所示横轴可以是最大时钟频率纵轴是能效每秒操作数/焦耳每个点代表一种配置。我们的实验发现在目标FPGA平台上配置(b1, l4, s1)即基数2、4级级联、1级Skip-Zero往往能达到最佳的“频率-能效”平衡点。为什么是基数2这似乎与“高基数更快”的直觉相悖。原因在于Skip-Zero策略的收益与基数b成反比公式中除以b。在基数2下s1就能带来50%的迭代加速。而在基数4下同样的s1只能带来25%的加速。高基数迭代单元本身更复杂关键路径更长可能会降低最大频率。当Skip-Zero带来的迭代次数减少收益无法抵消高基数单元本身频率下降的损失时基数2反而综合表现更好。这凸显了系统化设计空间探索的重要性不能孤立地看待某个优化技术。4. 完整除法器架构与关键优化技巧一个完整的、工业级的除法器模块远不止迭代核心。围绕SRT迭代器和Skip-Zero策略还需要一系列前处理和后处理逻辑以及针对面积和功耗的优化。图3展示了我们设计的完整数据流。4.1 预处理阶段为迭代做好准备预处理阶段处理三件关键事情其优化直接影响整体性能符号处理与取绝对值硬件除法通常直接处理无符号数。对于有符号除法我们首先提取操作数的符号位并记录最终结果的符号被除数与除数符号异或。然后将输入转换为绝对值。这一步需要小心处理整数补码的最小值如-2^31取绝对值时的溢出问题通常通过一个简单的条件逻辑处理。边界情况处理这是RISC-V等指令集架构的合规性要求。必须在迭代开始前检测并处理诸如“除数为零”和“溢出”如INT_MIN / -1等情况。这些情况会触发异常或返回架构定义的特定结果并应完全旁路掉耗时的迭代过程。一个常见的优化是将边界情况检测与符号处理、绝对值计算电路合并减少关键路径。输入移位这是一个经典且至关重要的优化。由于迭代是从最高有效位MSB开始产生商位如果被除数远小于除数商的高位会有很多前导零。输入移位逻辑通过一个前导零计数器LZC计算被除数和除数的有效位差并将被除数左移相应的位数。这相当于跳过了所有商的前导零迭代对于小商值的除法性能提升是数量级的。Skip-Zero略主要优化的是迭代过程中的零商而输入移位优化的是迭代开始前的“结构性”零商两者是互补的。4.2 迭代核心的微架构优化在迭代核心部分除了Skip-Zero我们还采用了以下优化来提升面积效率和时序部分余表复用在级联迭代单元中除数D在多次迭代中是不变的。因此我们不为每个迭代单元都复制一份完整的商选择表而是共享一个全局的“部分余数表”本质上是根据D预先计算好的选择边界。每个迭代单元根据自己当前的部分余数R从这个共享表的对应行中选择q_i。这显著减少了高基数设计中的查找表资源消耗。校正阶段合并在非恢复除法或SRT除法中如果最终余数为负需要一个校正周期将余数加回除数商减1。在我们的级联设计中我们将校正逻辑集成在最后一级迭代单元中。这样当最后一个迭代完成且检测到负余数时可以在同一周期内完成校正避免了一个额外的、独立的校正周期提高了吞吐量。寄存器合并在迭代过程中部分余数R的位宽逐次减少因为每次迭代后R会左移低位补零而累积的商Q的位宽逐次增加。我们可以将R和Q打包在同一个宽寄存器中。初始时R占据寄存器的高位Q占据低位全零。每次迭代R左移移出的高位进入Q的尾部。这种方法节省了寄存器数量并简化了数据通路。4.3 后处理与结果输出迭代完成后需要结果移位将合并寄存器中的商和余数根据预处理阶段的输入移位量进行右移得到正确的绝对值结果。符号应用根据预处理阶段保存的符号位对商和余数应用正确的符号对于商可能是取补码对于余数符号通常与被除数相同。结果格式化按照指令集架构的要求将结果写入目标寄存器。5. 实验评估、问题排查与实战心得我们使用Chisel生成RTL在Xilinx Artix-7 FPGA上进行综合并用软件仿真来统计平均迭代周期数。对比对象是开源RISC-V处理器中常用的除法器如Xuantie-910和Rocket-Chip中的设计。5.1 性能评估方法论评估硬件除法器性能不能只看最高频率而应关注平均操作频率和能效。平均操作频率平均操作频率 时钟频率 / 平均执行周期数。这综合反映了设计的速度和效率。能效能效 平均操作频率 / 动态功耗。单位是每秒操作数每焦耳OP/s/J这在高性能计算和嵌入式领域都至关重要。我们的仿真模型基于以下合理假设来估算平均周期数由于输入移位第一次迭代的商总是非零。后续迭代中对于基数2原始SRTq_i0的概率为1/2。被除数和除数的有效位宽在0到总位宽如64之间均匀分布。这会导致一半的商为零我们通过引入一个修正权重0.25而非1来纠正这种偏差使模型更符合真实随机输入的统计特性。有符号和无符号除法以相等概率出现。5.2 结果分析与最佳配置如图6所示在不同配置(b, l, s)中(1, 4, 1)配置基数24级级联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除法器的过程中我们踩过一些坑也总结了一些经验Skip-Zero单元与级联迭代的时序闭合Skip-Zero单元的检测逻辑虽然简单但它的输出控制着桶形移位器和迭代单元的使能。在高速设计中需要确保这条控制路径的延迟不会成为新的关键路径。我们采用的方法是将Skip-Zero检测逻辑提前一级。即在当前时钟周期不仅计算当前迭代的q_i还并行预计算下一级迭代的Skip-Zero条件这样控制信号可以提前准备好。处理最大跳过限制s级Skip-Zero单元最多连续跳过s个迭代。当实际连续零商超过s时硬件必须能正确处理。我们的设计是当检测到连续s个零商后在本周期执行s次移位并正常进入下一个迭代单元。控制逻辑必须同步更新迭代计数器和商寄存器确保状态一致。仿真时务必构造极端用例测试连续零商长度等于和大于s的情况。验证的完备性除法器的验证非常关键尤其是涉及有符号数、边界情况和随机零商模式。我们搭建了一个基于UVM的验证环境除了常规的随机测试外还特别加入了零商密集测试向量主动构造被除数为除数一半左右的数字使得中间过程产生大量连续零商。输入移位与Skip-Zero交互测试测试小商值需要大量输入移位与迭代中零商同时发生的情况。与黄金模型Golden Model的周期精确比对不仅比对最终结果还比对中间重要状态如每周期后的余数确保迭代过程正确。Chisel生成代码的可读性Chisel在提高开发效率方面很棒但生成的Verilog有时可读性不佳不利于后端调试。我们养成了一个习惯为关键模块如SkipZeroUnit、SRTIterationStage添加详细的Chisel注释//并使用chiselName宏这些信息会体现在生成的Verilog模块名和信号名中极大方便了波形调试。面积-性能权衡sSkip-Zero级数并非越大越好。s增加会线性增加桶形移位器的宽度和零检测逻辑的复杂度。我们的实验显示从s1到s2性能提升的边际效应明显下降但面积和功耗增加却比较明显。对于大多数应用s1或2是最具性价比的选择。5.4 对系统集成的影响将这样一个优化的除法器集成到完整的处理器流水线中还需要考虑流水线互锁除法是长延迟操作。需要确保在除法完成前依赖其结果的后续指令被正确阻塞。Skip-Zero策略减少了平均延迟但最坏情况延迟全是非零商没有改变。调度器和记分板的设计仍需以最坏情况延迟为准。中断与异常处理除法执行过程中可能被中断。需要保存除法器的完整状态包括当前余数、商、迭代计数器等以便中断返回后能恢复执行。我们的参数化设计使得状态寄存器的大小是可配置的。与向量扩展的协同对于支持RISC-V V扩展的处理器可以考虑设计向量化的除法单元。Skip-Zero策略的思想同样可以应用但需要权衡控制逻辑的复杂度和向量车道Lane间的负载均衡。回过头看Skip-Zero策略的成功在于它敏锐地抓住了SRT算法在真实运算中的统计特性——零商的高频出现并用一个极其精巧的硬件改动将其利用起来。这提醒我们在微架构优化中有时与其追求更复杂的算法或更高的频率不如深入分析常见执行路径寻找这种“四两拨千斤”的优化机会。我们的参数化Chisel生成器框架使得快速探索这类设计权衡变得非常方便是架构探索的利器。未来我们计划将这一策略扩展到平方运算中因为SRT算法同样广泛应用于平方根计算其零商场景也有类似的优化潜力。