1. 模约减技术背景与挑战

模约减（Modular Reduction）作为现代密码学的基石运算，其性能直接影响着同态加密（HE）和零知识证明（ZKP）等隐私计算技术的实用性。这项看似简单的数学运算——计算R = A mod M（其中A为2n位数，M为固定n位模数）——在实际硬件实现中却面临严峻挑战。

在ECC椭圆曲线加密中，224-bit模运算是基本要求；RSA算法则需要支持1024-bit乃至更高位宽的运算。随着安全需求的提升，业界对2048-bit甚至8192-bit模运算的需求日益增长。这种指数级增长的位宽要求，使得传统基于乘法器的方法（如Barrett和Montgomery算法）遭遇物理极限——高位宽乘法器不仅面积开销大，时序收敛也愈发困难。

2. 现有技术方案对比分析

2.1 LUT-based方法的优势与局限

查找表（LUT）方法通过空间换时间的策略，将模运算结果预计算并存储在FPGA的BRAM中。其核心流程包括：

1. 输入位分割：将2n位输入A的高n位分割为k-bit的段（如k=8）
2. 预计算存储：离线计算每段对应的(段值×2^(n+ki)) mod M
3. 并行查表：运行时并行查表获取部分结果
4. 加法树聚合：通过多级加法器汇总结果

以n=128bit为例，采用8-bit分段需要16个36Kb BRAM存储查找表，配合16输入加法树。这种方法虽然能实现2周期超低延迟，但资源消耗随位宽呈指数增长——当n=8192bit时，需要4096个BRAM，这远超主流FPGA的可用资源。

2.2 迭代法的特性分析

迭代法采用最直观的"减模数直至余数小于模数"思路：

// 简化版迭代模约减
module iterative_mod(
  input [2n-1:0] A,
  input [n-1:0] M,
  output [n-1:0] R
);
  reg [2n-1:0] temp = A;
  always @(*) begin
    for(int i=0; i<n; i++) begin
      if(temp >= (M << (n-1-i)))
        temp = temp - (M << (n-1-i));
    end
    R = temp[n-1:0];
  end
endmodule

该方法仅需1个n-bit减法器，面积效率极高。但完成n=2048bit运算需要2048周期，延迟难以接受。更关键的是，其串行特性使得吞吐量提升必须通过资源复制实现，反而抵消了面积优势。

3. ALLMod混合架构设计

3.1 核心创新：动态位宽分割

ALLMod的核心突破在于发现：高位段对最终结果的贡献度呈现指数衰减。基于此，提出混合工作负载策略：

1. 高位段（n-m bit）：采用LUT处理
   • 贡献值大，查表收益高
   • 分段数d=(n-m)/k显著减少
2. 低位段（n+m bit）：采用迭代处理
   • 贡献值小，减法开销可控
   • 迭代次数m可精确控制

通过公式推导得出最优分割点：

m = (n + k)/(k + 1)

当k=8时，约89%高位段用LUT处理，11%低位段用迭代法。这种非对称分割既保留了LUT的低延迟特性，又大幅减少了资源消耗。

3.2 硬件模板设计

ALLMod的FPGA实现包含五个关键模块（如图3所示）：

1. 并行查表单元 ：

   • 采用Block RAM实现压缩LUT
   • 每个BRAM配置为k-bit输入、n-bit输出
   • 通过位宽压缩技术，n=2048bit时仅需410个BRAM（传统方法需512个）

2. 串行累加器 ：

   • 用1个n+log2d位加法器替代加法树
   • 通过时间复用完成d次累加（需d周期）
   • 关键路径优化：采用进位保留加法器（CSA）

3. 迭代减法单元 ：

   • 包含1个n+m bit减法器和移位寄存器
   • 创新采用Booth编码减法器，面积减少30%
   • 支持提前终止机制：当差值小于阈值时跳过后续周期

4. 结果融合单元 ：

   • 三级流水线结构：

   // 融合单元伪代码
   logic [n+log2d:0] stage1 = LUT_result + iter_result;
   logic [n:0] stage2 = stage1[n:0] + (stage1 >> n);
   logic [n-1:0] stage3 = (stage2 >= M) ? stage2 - M : stage2;
   

   • 时钟频率可达200MHz（Xilinx UltraScale+实测）

5. 动态配置接口 ：

   • 支持运行时调整m参数
   • 提供AXI-Lite配置总线
   • 可实时监控各单元利用率

3.3 设计空间探索算法

ALLMod的创新搜索算法（Algorithm 3）能在10分钟内完成8192-bit设计空间的探索：

1. 参数枚举 ：

   • m：0到n（分割点）
   • WidthTree：加法树宽度（0表示全串行）

2. 约束评估 ：

   # 延迟评估模型
   def eval_latency(m, WidthTree):
       lut_latency = 1 + max((n-m)/k - WidthTree, log2(WidthTree))
       iter_latency = m
       return max(lut_latency, iter_latency)
   
   # 面积评估模型
   def eval_area(m, WidthTree, TP):
       brams = (n-m)/k
       adders = (2*WidthTree-1) + ((n-m)/k - WidthTree)*TP
       subs = m * TP
       return brams*BRAM_LUT + adders*Adder_LUT + subs*Sub_LUT
   

3. Pareto前沿筛选 ：

   • 采用ε-支配排序算法
   • 支持用户定义权重（如latency_weight=0.7, area_weight=0.3）

4. 实现优化与实测结果

4.1 关键优化技术

1. BRAM压缩技术 ：

   • 利用模数M的固定特性，存储差分值而非绝对值
   • 实测n=1024bit时，BRAM用量减少42%

2. 近似减法器 ：

   • 低位段采用MSB-truncated减法器
   • 误差<2^-16时对最终结果无影响
   • 面积减少55%，频率提升18%

3. 动态时钟门控 ：

   // 迭代单元时钟门控
   always_comb begin
     if(iter_state == IDLE)
       iter_clk_en = 0;
     else if(sub_ready)
       iter_clk_en = |remain_bits;
   end
   

   • 静态功耗降低37%

4.2 性能对比

在Xilinx Alveo U280板卡上的实测数据：

指标	n=128bit	n=2048bit	n=8192bit
传统LUT方法
周期数	9	14	17
BRAM用量	16	512	4096
面积效率	15258	2.59	0.02
ALLMod
周期数	20	415	2736
BRAM用量	15	410	2731
面积效率	25040	6.45	0.06
提升倍数	1.65x	2.49x	3.00x

4.3 实际应用案例

在同态加密推理场景下（n=1024bit）：

• 传统LUT方法：占用205个BRAM，延迟13周期
• ALLMod方案：占用171个BRAM，延迟176周期
• 实际吞吐量：在200MHz下达到1.14MOPS
• 能效比：3.2pJ/op，比GPU方案优1000倍

5. 工程实践建议

1. 参数选择指南 ：

   • 安全敏感场景：优先选择n≥2048bit
   • 延迟敏感型：设置m≤n/4
   • 面积受限型：设置m≈n/(k+1)

2. FPGA实现技巧 ：

   • BRAM配置：使用URAM替代BRAM36E3（Vivado 2023.1+）
   • 加法器实现：采用DSP48E2硬核（Xilinx）
   • 时序约束：set_multicycle_path到加法器输出

3. 验证方法学 ：

   • 黄金参考：使用Python的gmpy2模块生成测试向量

   def gen_testcase(n):
       M = random.getrandbits(n)
       A = random.getrandbits(2*n)
       R = A % M
       return (A, M, R)
   

   • 覆盖率：确保测试所有边界条件（A=0, A=2^(2n)-1等）

4. 扩展应用方向 ：

   • 支持可变模数：增加LUT更新接口
   • 批处理模式：设计深度为16的输入FIFO
   • 安全防护：添加抗侧信道攻击的随机延迟