除法器 — Divider

📖 恢复余数除法原理

恢复余数除法（Restoring Division）是最直观的硬件除法算法：

🖥️ Verilog实现：恢复余数除法器

// Lesson 14: Restoring Division — Unsigned 8-bit Divider
module divider(
    input  wire        clk, rst_n,
    input  wire        start,
    input  wire [7:0]  dividend, divisor,
    output reg  [7:0]  quotient, remainder,
    output reg         done,
    output reg         div_by_zero
);
    reg [7:0] Q, A, M; reg [3:0] step; reg [2:0] bit_cnt;
    always @(posedge clk or negedge rst_n) begin
        if(!rst_n) begin quotient<=0; remainder<=0; done<=0;
            div_by_zero<=0; step<=0; Q<=0; A<=0; M<=0; bit_cnt<=0; end
        else if(start && step==0) begin
            if(divisor==0) begin div_by_zero<=1; quotient<=8'hFF;
                remainder<=8'hFF; done<=1; end
            else begin M<=divisor; Q<=dividend; A<=0;
                step<=1; done<=0; div_by_zero<=0; bit_cnt<=0; end
        end else if(step==1) begin
            A<={A[6:0],Q[7]}; Q<={Q[6:0],1'b0}; step<=2;
        end else if(step==2) begin
            if(A>=M) begin A<=A-M; Q[0]<=1; end
            else Q[0]<=0;
            if(bit_cnt==7) begin quotient<=Q; remainder<=A; done<=1; step<=0; end
            else begin bit_cnt<=bit_cnt+1; step<=1; end
        end
    end
endmodule

代码解析

• 除零检测：divisor=0时直接返回0xFF并标记div_by_zero
• 16周期完成：8位除法需要8次迭代，每次2个时钟周期
• 左移+试减：step1左移A:Q，step2试减并设置商位
• 自动恢复：A

📊 处理器中的除法实现

🧪 实验练习

1. 实现非恢复余数除法：消除恢复步，减少周期数
2. 扩展到32位除法：支持RISC-V M扩展的DIV/DIVU/REM/REMU
3. 添加有符号除法：将操作数转为绝对值，除完后修正符号
4. 实现流水线除法：支持多条除法指令重叠执行

🔗 除法器在RISC-V M扩展中的实现

RISC-V M扩展定义了4条除法指令：

除法指令的特殊情况

高性能除法的替代方案

恢复余数除法是最基础的实现。现代处理器使用更快的算法：

• SRT除法：每步选择多个商位，速度更快（4-8位/步）
• Newton-Raphson：迭代逼近，适合浮点除法（4-6次迭代）
• 查表+乘法：用查找表获取初始近似值，再Newton迭代
• Goldschmidt：类似Newton但不需要除法，纯乘法

Apple M1的除法器使用高基数SRT，整数除法约10个周期。而Rocket的迭代除法需要25-37个周期。

🎯 本课与整体课程的关系

📚 延伸阅读与参考资料

相关课程

实验环境搭建

建议使用以下环境进行实验：

• Verilator 5.020：Verilog仿真和lint（本课程使用的验证工具）
• QEMU virt：RISC-V全系统模拟器，支持M/S/U特权级
• Spike：RISC-V ISA模拟器，适合指令级调试
• OpenOCD + GDB：硬件调试工具链
• Chisel/FIRRTL：BOOM和Rocket使用的硬件描述语言

📊 除法器延迟与面积权衡

SRT除法器

SRT除法器以Sweeney、Robertson、Tocher三人命名，是目前最快的硬件除法算法：

Intel Pentium FDIV bug是计算机史上最著名的硬件bug之一，正是因为SRT除法器的查找表设计错误导致的。此后，硬件除法器的形式化验证变得至关重要。

🔬 非恢复余数除法详解

非恢复余数除法消除了恢复步骤，每步固定一次加减运算：

非恢复余数除法比恢复余数除法每步少一次条件加法，性能提升约30%。这是硬件除法器最常用的基础算法。