除法是CPU最慢的操作之一。传统设计里除法单元独占24周期期间其他指令只能干等。流水线化让除法也能像加法一样流水执行大幅提升吞吐量。这篇聊聊除法流水化的原理、实现和代价。1. 传统除法慢且独占1.1 MIPS的FDIV经典MIPS处理器的浮点除法单元1延迟24周期双精度启动间隔25周期必须等上一个除法完成硬件非流水化独占使用这意味着Cycle 1: FDIV.D F1, F2, F3 ; 开始除法 Cycle 2-24: 其他指令执行但如果需要F1必须等 Cycle 25: FDIV.D F4, F5, F6 ; 下一个除法才能开始如果代码里有连续除法性能惨不忍睹。1.2 为什么除法难流水化算法复杂性恢复除法Restoring Division多步迭代每步依赖上一步的部分余数SRT算法Sweeney, Robertson, Tocher虽然可以流水但每级逻辑复杂面积开销流水化需要复制部分余数寄存器和控制逻辑24级流水线的面积可能超过整个整数单元2. 部分流水化子级拆分把24周期除法拆成4级每级6周期1传统 [Divider] 24周期 → 结果 流水化 [Div-P1][Div-P2][Div-P3][Div-P4] 每级6周期效果启动间隔从25周期降到6周期每6周期可以发射一个新除法吞吐量提升4倍代价每级需要存储中间结果部分商、部分余数控制逻辑复杂面积增加30-50%3. 算法革新更快的基础3.1 SRT算法基数提升SRT算法每周期产生多位商2[301]基数每周期商位数双精度周期数复杂度Radix-2153低Radix-4227中Radix-8318高Radix-16414很高Radix-4 SRT34每周期处理2位商需要查找表PLA选择商数字部分余数用冗余表示-2, -1, 0, 1, 2Radix-8 SRT3Weitek WTL2264芯片采用每周期3位商周期数从53降到183.2 Newton-Raphson迭代法用乘法逼近倒数将除法转为乘法567R i 1 R i ( 2 − D ⋅ R i ) R_{i1} R_i(2 - D \cdot R_i)Ri1Ri(2−D⋅Ri)其中R i R_iRi是1 / D 1/D1/D的近似值。特点二次收敛每次迭代精度翻倍需要快速乘法器现代CPU都有适合流水化乘法容易流水步骤6查表得初始近似值R 0 R_0R08-16位精度迭代1R 1 R 0 ( 2 − D ⋅ R 0 ) R_1 R_0(2 - D \cdot R_0)R1R0(2−D⋅R0)→ 16-32位精度迭代2R 2 R 1 ( 2 − D ⋅ R 1 ) R_2 R_1(2 - D \cdot R_1)R2R1(2−D⋅R1)→ 32-64位精度计算Q N ⋅ R 2 Q N \cdot R_2QN⋅R2优势延迟低2-3次乘法可以利用现有的乘法流水线Intel Skylake及以后采用此方法4. 现代处理器案例4.1 Intel x86演进处理器除法算法延迟启动间隔备注Core 2Radix-4 SRT~20~20非流水Sandy BridgeRadix-4 SRT14-2814-28部分流水HaswellRadix-4 SRT10-2410-24改进版SkylakeNewton-Raphson13-184-6用乘法器Intel从Skylake开始转向Newton-Raphson5因为复用现有的快速乘法器更容易流水化面积效率更高4.2 ARM Neoverse V2ARM Neoverse V2Graviton 4使用89宽发射6-wide乱序执行除法单元采用优化算法与乘法器共享硬件资源虽然具体除法延迟未公开但作为服务器级核心预计采用类似Newton-Raphson的方法。4.3 RISC-V的灵活性RISC-V的M扩展乘法/除法允许不同实现10实现算法周期数适用场景嵌入式迭代恢复除法32面积优先通用Radix-4 SRT16-20平衡高性能Newton-Raphson8-12性能优先SiFive U74采用Radix-4 SRT约20-32周期。5. 流水化的代价5.1 面积与功耗方案相对面积功耗吞吐量非流水迭代1x低1/244级部分流水1.4x中1/6完全流水2.5x高1/1完全流水化每周期发射需要24级流水线面积和功耗都难以接受。实际采用部分流水化4-8级。5.2 精度权衡GPU的近似除法游戏渲染允许1%误差用低精度倒数近似延迟减半NVIDIA/AMD GPU的除法单元比CPU简单CPU的精确除法必须符合IEEE 754标准需要额外周期处理舍入不能用近似算法6. 设计建议场景推荐方案理由嵌入式/IoT迭代恢复除法面积最小功耗最低移动/桌面Radix-4 SRT部分流水平衡面积和性能服务器/HPCNewton-Raphson利用乘法器延迟最低GPU/AI加速器低精度近似吞吐量优先精度可妥协7. 总结除法流水线化的演进阶段算法启动间隔代表早期恢复除法24-32周期MIPS FDIV中期Radix-4/8 SRT6-12周期Core 2, Haswell现代Newton-Raphson4-6周期Skylake, Zen关键认知完全流水化除法代价太高部分流水化是甜点区SRT算法通过提升基数减少周期数Newton-Raphson利用现有乘法器是现代主流除法单元面积和功耗敏感需要根据场景权衡理解除法流水化就能理解为什么现代CPU的除法性能提升比加法慢得多——这是算法复杂度和硬件成本的永恒博弈。参考ASEE. The Forgotten Horseman: Digital Implementation of Arithmetic Division. ↩︎ ↩︎Academia.edu. Implementation Of A Radix 4 SRT Divider/square-root Supporting Two Concurrent Operations. ↩︎Fandrianto. Algorithm for High-Speed Shared Radix 4 Division and Square-Root. Weitek Corporation. ↩︎ ↩︎Fandrianto. Algorithm for High-Speed Shared Radix 4 Division and Square-Root. ARITH8. ↩︎Fowler Smith. An Accurate, High Speed Implementation of Division by Reciprocal Approximation. 1989. ↩︎ ↩︎MathWorks. HDL Reciprocal - Newton-Raphson approximation method. ↩︎ ↩︎UCLA. Digital Arithmetic - Iterative Approximation. ↩︎Chips and Cheese. From AWS Graviton 4, Revealing Arm Neoverse V2. 2024. ↩︎Chips and Cheese. Hot Chips 2023: Arm’s Neoverse V2. ↩︎GitHub - RussPalms/VexRiscv_dev. RISC-V DivPlugin and MulDivIterativePlugin. ↩︎
除法流水线化：从24周期 stall 到每周期发射
除法是CPU最慢的操作之一。传统设计里除法单元独占24周期期间其他指令只能干等。流水线化让除法也能像加法一样流水执行大幅提升吞吐量。这篇聊聊除法流水化的原理、实现和代价。1. 传统除法慢且独占1.1 MIPS的FDIV经典MIPS处理器的浮点除法单元1延迟24周期双精度启动间隔25周期必须等上一个除法完成硬件非流水化独占使用这意味着Cycle 1: FDIV.D F1, F2, F3 ; 开始除法 Cycle 2-24: 其他指令执行但如果需要F1必须等 Cycle 25: FDIV.D F4, F5, F6 ; 下一个除法才能开始如果代码里有连续除法性能惨不忍睹。1.2 为什么除法难流水化算法复杂性恢复除法Restoring Division多步迭代每步依赖上一步的部分余数SRT算法Sweeney, Robertson, Tocher虽然可以流水但每级逻辑复杂面积开销流水化需要复制部分余数寄存器和控制逻辑24级流水线的面积可能超过整个整数单元2. 部分流水化子级拆分把24周期除法拆成4级每级6周期1传统 [Divider] 24周期 → 结果 流水化 [Div-P1][Div-P2][Div-P3][Div-P4] 每级6周期效果启动间隔从25周期降到6周期每6周期可以发射一个新除法吞吐量提升4倍代价每级需要存储中间结果部分商、部分余数控制逻辑复杂面积增加30-50%3. 算法革新更快的基础3.1 SRT算法基数提升SRT算法每周期产生多位商2[301]基数每周期商位数双精度周期数复杂度Radix-2153低Radix-4227中Radix-8318高Radix-16414很高Radix-4 SRT34每周期处理2位商需要查找表PLA选择商数字部分余数用冗余表示-2, -1, 0, 1, 2Radix-8 SRT3Weitek WTL2264芯片采用每周期3位商周期数从53降到183.2 Newton-Raphson迭代法用乘法逼近倒数将除法转为乘法567R i 1 R i ( 2 − D ⋅ R i ) R_{i1} R_i(2 - D \cdot R_i)Ri1Ri(2−D⋅Ri)其中R i R_iRi是1 / D 1/D1/D的近似值。特点二次收敛每次迭代精度翻倍需要快速乘法器现代CPU都有适合流水化乘法容易流水步骤6查表得初始近似值R 0 R_0R08-16位精度迭代1R 1 R 0 ( 2 − D ⋅ R 0 ) R_1 R_0(2 - D \cdot R_0)R1R0(2−D⋅R0)→ 16-32位精度迭代2R 2 R 1 ( 2 − D ⋅ R 1 ) R_2 R_1(2 - D \cdot R_1)R2R1(2−D⋅R1)→ 32-64位精度计算Q N ⋅ R 2 Q N \cdot R_2QN⋅R2优势延迟低2-3次乘法可以利用现有的乘法流水线Intel Skylake及以后采用此方法4. 现代处理器案例4.1 Intel x86演进处理器除法算法延迟启动间隔备注Core 2Radix-4 SRT~20~20非流水Sandy BridgeRadix-4 SRT14-2814-28部分流水HaswellRadix-4 SRT10-2410-24改进版SkylakeNewton-Raphson13-184-6用乘法器Intel从Skylake开始转向Newton-Raphson5因为复用现有的快速乘法器更容易流水化面积效率更高4.2 ARM Neoverse V2ARM Neoverse V2Graviton 4使用89宽发射6-wide乱序执行除法单元采用优化算法与乘法器共享硬件资源虽然具体除法延迟未公开但作为服务器级核心预计采用类似Newton-Raphson的方法。4.3 RISC-V的灵活性RISC-V的M扩展乘法/除法允许不同实现10实现算法周期数适用场景嵌入式迭代恢复除法32面积优先通用Radix-4 SRT16-20平衡高性能Newton-Raphson8-12性能优先SiFive U74采用Radix-4 SRT约20-32周期。5. 流水化的代价5.1 面积与功耗方案相对面积功耗吞吐量非流水迭代1x低1/244级部分流水1.4x中1/6完全流水2.5x高1/1完全流水化每周期发射需要24级流水线面积和功耗都难以接受。实际采用部分流水化4-8级。5.2 精度权衡GPU的近似除法游戏渲染允许1%误差用低精度倒数近似延迟减半NVIDIA/AMD GPU的除法单元比CPU简单CPU的精确除法必须符合IEEE 754标准需要额外周期处理舍入不能用近似算法6. 设计建议场景推荐方案理由嵌入式/IoT迭代恢复除法面积最小功耗最低移动/桌面Radix-4 SRT部分流水平衡面积和性能服务器/HPCNewton-Raphson利用乘法器延迟最低GPU/AI加速器低精度近似吞吐量优先精度可妥协7. 总结除法流水线化的演进阶段算法启动间隔代表早期恢复除法24-32周期MIPS FDIV中期Radix-4/8 SRT6-12周期Core 2, Haswell现代Newton-Raphson4-6周期Skylake, Zen关键认知完全流水化除法代价太高部分流水化是甜点区SRT算法通过提升基数减少周期数Newton-Raphson利用现有乘法器是现代主流除法单元面积和功耗敏感需要根据场景权衡理解除法流水化就能理解为什么现代CPU的除法性能提升比加法慢得多——这是算法复杂度和硬件成本的永恒博弈。参考ASEE. The Forgotten Horseman: Digital Implementation of Arithmetic Division. ↩︎ ↩︎Academia.edu. Implementation Of A Radix 4 SRT Divider/square-root Supporting Two Concurrent Operations. ↩︎Fandrianto. Algorithm for High-Speed Shared Radix 4 Division and Square-Root. Weitek Corporation. ↩︎ ↩︎Fandrianto. Algorithm for High-Speed Shared Radix 4 Division and Square-Root. ARITH8. ↩︎Fowler Smith. An Accurate, High Speed Implementation of Division by Reciprocal Approximation. 1989. ↩︎ ↩︎MathWorks. HDL Reciprocal - Newton-Raphson approximation method. ↩︎ ↩︎UCLA. Digital Arithmetic - Iterative Approximation. ↩︎Chips and Cheese. From AWS Graviton 4, Revealing Arm Neoverse V2. 2024. ↩︎Chips and Cheese. Hot Chips 2023: Arm’s Neoverse V2. ↩︎GitHub - RussPalms/VexRiscv_dev. RISC-V DivPlugin and MulDivIterativePlugin. ↩︎
