FrodoKEM硬件加速架构设计与优化策略

1. FrodoKEM硬件加速架构设计精要

在格基后量子密码算法中，矩阵运算占据了90%以上的计算耗时。以FrodoKEM-640为例，其核心运算B=AS+E涉及640×640矩阵的乘法，传统串行实现需要超过17万时钟周期。我们的硬件架构创新性地采用三级并行策略：

1.1 存储层次优化设计

矩阵元素访问存在明显的时空局部性特征。实测显示，在FrodoKEM的矩阵乘法中，约85%的访存集中在4×4的子矩阵块内。基于此观察，我们设计了分块交织存储架构：

• 物理存储划分：将Bank 0和Bank 1各划分为4个32位宽的RAM块（RAM0-RAM3），每个RAM块可存储：

  • 4个S/S'矩阵元素（int16类型）
  • 2个E/E'矩阵元素（int32类型）

• 数据映射策略：

  // S矩阵的存储映射示例 assign RAM0_wdata = {S[3], S[2], S[1], S[0]}; assign RAM1_wdata = {S[7], S[6], S[5], S[4]}; // 地址生成逻辑 always_comb begin ram0_addr = base_addr + (row_idx[1:0] << 2); ram1_addr = base_addr + (row_idx[1:0] << 2); end

• 动态访问模式：通过可编程地址生成器支持：

  • 写入模式：行优先写入4元素/周期
  • 读取模式：支持4×4或2×4矩阵块的并行读取

1.2 计算单元微架构

矩阵乘法单元采用脉动阵列设计，关键参数如下：

实际测试中，该设计在Artix-7上实现：

• 面积开销：2957 LUTs（占22%）
• 时序裕量：1.2ns（满足200MHz时钟）

关键技巧：采用进位保留加法器(Carry-Save Adder)减少关键路径延迟，使乘法器频率提升18%

2. 指令级并行实现细节

2.1 自定义指令集设计

针对FrodoKEM的计算特征，我们定义了三类指令：

1. 哈希控制指令：

   • HIA（Hash Input Absorption）：吸收阶段
   • HOS（Hash Output Squeezing）：挤压阶段

   // 示例指令序列 HIA 0x1000, 256 // 从地址0x1000吸收256字节 HOS 0x2000, 1024 // 挤压结果到0x2000

2. 矩阵操作指令：

   • MBR/MBW：矩阵块读写
   • MUL：矩阵乘法核心操作

3. 协议指令：

   • ENC/DEC：消息编解码
   • CMP：密文一致性校验

2.2 重叠执行机制

通过分析FrodoKEM-640的指令分布（表III数据）：

设计双发射流水线，实现：

• 时序重叠：当HOS执行时，可并行发射MUL/MBR指令
• 资源隔离：哈希单元与乘法阵列物理分离
• 冲突检测：通过Scoreboard机制避免RAW冲突

// 指令发射逻辑示例 always_ff @(posedge clk) begin if (HOS_valid && !HOS_busy && MUL_ready) begin issue_HOS <= 1; issue_MUL <= 1; end end

实测显示该方案使总周期数减少39.6%（表IV数据），关键路径时序如下：

图：HOS与MUL指令的重叠执行时序（灰色区域表示有效重叠）

3. 内存访问优化技术

3.1 交织访问模式

针对矩阵B的两种访问模式：

• 写访问：2×4块状写入
• 读访问：4×2列式读取

采用动态地址映射策略：

def get_ram_addr(mode, row, col): if mode == WRITE_2x4: return (row % 2) * 4 + (col % 4) else: # READ_4x2 return (row % 4) * 2 + (col % 2)

实测内存带宽利用率提升对比：

3.2 乒乓缓冲策略

设计双缓冲机制解决生产-消费延迟：

1. 哈希单元写入Buffer A时，乘法器读取Buffer B
2. 每完成8行矩阵A生成后切换缓冲
3. 采用原子指针交换避免锁开销

// 缓冲切换伪代码 void swap_buffers() { atomic_store(&current_buf, 1 - atomic_load(&current_buf)); }

4. 实现结果与对比分析

4.1 资源利用率

在Artix-7 FPGA上的资源消耗：

4.2 性能对比

与现有方案的执行时间对比（Frodo-640）：

关键优势体现在：

• 哈希与乘法的指令级重叠（节省约40%周期）
• 乘加器阵列深度流水（频率提升至207MHz）
• 紧凑的内存调度策略（仅需14 BRAM）

5. 工程实践中的经验总结

5.1 调试技巧

1. 时序收敛问题：

   • 对乘加器阵列采用寄存器重定时(Retiming)
   • 关键路径插入流水线寄存器

   always_ff @(posedge clk) begin stage1 <= mul_input; stage2 <= stage1 * coeff; stage3 <= stage2 + accum; end

2. 内存冲突检测：

   • 设计访问冲突预测器
   • 提前2周期暂停冲突指令

5.2 优化方向

1. 进一步并行化：

   • 扩展至64路乘加器（需平衡DSP利用率）
   • 探索3级指令并行（当前为2级）

2. 动态电压频率调节：

   • 根据工作负载调整VDD
   • 预期可降低30%动态功耗

在实际部署中发现，当矩阵规模超过1024时，内存带宽会成为新的瓶颈。此时可采用：

• 块压缩技术（利用矩阵稀疏性）
• 近似计算（在误差允许范围内）