FPGA加速同态矩阵向量乘法的技术解析与实践

1. 项目概述：FPGA加速同态矩阵向量乘法的技术背景

同态加密（Homomorphic Encryption, HE）作为密码学领域的重大突破，允许在加密数据上直接执行计算而无需解密。这项技术从根本上改变了传统隐私计算的范式，使得数据在处理过程中始终保持加密状态。在隐私消息检索（Oblivious Message Retrieval, OMR）场景中，HE使得服务器能够在不解密用户消息的情况下，帮助用户筛选出相关消息，同时保护了通信双方的元数据隐私。

然而，HE的计算开销一直是制约其实际应用的主要瓶颈。以BFV（Brakerski-Fan-Vercauteren）方案为例，其核心运算涉及大规模多项式环上的模乘和模加操作，这些操作在通用处理器（CPU）上的执行效率极低。特别是当处理矩阵向量乘法（MatMul）这类基础线性代数运算时，性能问题尤为突出。

FPGA（现场可编程门阵列）因其可重构特性和并行计算能力，成为加速HE运算的理想平台。与CPU相比，FPGA可以实现：

  • 指令级并行：同时执行多个同态运算操作
  • 数据级并行：对多项式系数进行批量处理
  • 流水线设计：隐藏运算延迟，提高吞吐量

本项目的核心创新点在于：针对OMR中的关键MatMul运算，提出了一套完整的FPGA加速方案，通过多层次并行化设计和自动化设计空间探索（Design Space Exploration, DSE），实现了13.86倍的性能提升。

2. 同态加密基础与矩阵向量乘法原理

2.1 BFV同态加密方案解析

BFV方案作为目前最主流的全同态加密方案之一，其数学基础建立在环学习有误（RLWE）难题之上。方案的核心参数包括：

  • 环维度n：决定安全性和计算复杂度的关键参数，通常取2的幂次
  • 明文模数t：限定明文数据的取值范围
  • 密文模数Q：一个大整数，通常分解为多个小素数的乘积（RNS表示）

BFV的核心运算流程包括：

  1. 密钥生成：

    # 伪代码示例：BFV密钥生成 def key_generation(n, q, t): secret_key = sample_from_error_distribution(n) public_key = (a, b) # 其中b = [-(a*s + e)]_q evaluation_keys = generate_galois_keys(secret_key) return (secret_key, public_key, evaluation_keys)

  2. 加密/解密：

    • 加密：将明文多项式m编码为环元素，添加噪声后生成密文(ct0, ct1)
    • 解密：计算[ct0 + ct1s]_q ≈ mt (mod q)

  3. 同态运算：

    • 加法（CCadd）：简单对应系数相加
    • 明文-密文乘法（PCmul）：明文多项式与密文多项式的逐系数乘法
    • 旋转（Rot）：通过Galois自同构实现密文slot的循环移位

2.2 矩阵向量乘法的同态实现

在OMR的Detect阶段，核心计算可以抽象为：

M·v = Σ_{i=0}^{k-1} diag_i(M) ⊙ Rot^i(v)

其中M是N×k的明文矩阵，v是长度为k的密文向量，diag_i(M)表示矩阵M的第i条对角线，⊙表示明文-密文点乘。

SophOMR采用的优化算法（Algorithm 1）通过baby-step giant-step技巧，将旋转次数从k减少到√k级别。该算法的主要计算瓶颈在于：

  1. PCmul操作：占总计算时间的50%以上
  2. Rot操作：虽然数量较少，但单次执行时间较长

关键观察：在FPGA实现中，PCmul具有极高的并行潜力，而Rot则需要特殊的优化策略。

3. FPGA加速架构设计

3.1 整体硬件架构

基于Alveo U55C FPGA平台的加速器设计采用分层结构：

（图示：简化版硬件架构，包含Rot核心、多个PCmul核心和数据通路）

主要功能单元包括：

  1. 旋转核心（Rot Core）：

    • 集成KeySwitch模块
    • 采用limb-based流水线设计
    • 配置64个并行NTT蝶形单元（PB=64）

  2. 并行乘法核心（PCmul Cores）：

    • 16个并行实例（PI=16）
    • 每个实例处理16个系数（PC=16）
    • 采用完全流水线设计（II=1）

  3. 数据通路：

    • 基于URAM的双缓冲设计
    • 矩阵数据分布式存储
    • 使用AXI4接口连接HBM2内存

3.2 关键优化技术

3.2.1 多层次并行设计

  1. 系数级并行（PC）：

    // HLS代码示例：PCmul核心的系数并行处理 #pragma HLS PIPELINE II=1 for(int i=0; i<COEFF_NUM/PC; i++) { #pragma HLS UNROLL for(int j=0; j<PC; j++) { res_coeff[i*PC+j] = mul_mod(p_coeff[i*PC+j], c_coeff[i*PC+j]); } }

  2. 操作级并行（PI）：

    • 同时运行16个PCmul核心
    • 通过加法树（adder tree）合并部分结果

  3. NTT蝶形单元并行（PB）：

    • 采用autoNTT库的优化实现
    • 配置64个并行蝶形单元
3.2.2 内存子系统优化

  1. 旋转键存储方案：

    • 原始旋转键大小：55MB × 2 = 110MB
    • FPGA片上存储：URAM（共270MB）
    • 采用"滑动窗口"策略，动态加载所需键片段

  2. 矩阵数据分布：

    // 矩阵存储分布示例 module matrix_buffer #(PI=16) ( input logic [PI-1:0] sel, output logic [127:0] data [PI-1:0] ); // 每个PCmul核心对应独立的BRAM存储体 for(genvar i=0; i<PI; i++) begin bram #(.WIDTH(128), .DEPTH(1024)) bram_inst (.addr(sel[i]), .data(data[i])); end endmodule

  3. 双缓冲设计：

    • 使用URAM实现ping-pong缓冲
    • 隐藏DDR/HBM访问延迟

3.3 设计空间探索策略

DSE流程采用多目标优化方法，权衡延迟和资源利用率：

  1. 参数空间定义：

    参数类型影响范围候选值
    PC所有算子2,4,8,16
    PBRot核心16,32,64
    PIPCmul实例数1,2,4,8,16

  2. 成本模型：

    • 延迟模型：公式(5)(6)
    • 资源模型：
      def estimate_dsp_usage(PC, PI, PB): dsp_pcmul = 897 * PI dsp_rot = 5123 * (64/PB) return dsp_pcmul + dsp_rot + (PI+2)*16

  3. 探索结果：

    配置PCPIPB延迟(ms)DSP利用率
    最优161664215076%
    次优16864217072%

4. 实现细节与性能分析

4.1 硬件实现结果

基于Vitis HLS 2024.1的实现指标：

模块DSP用量BRAMURAM延迟(ms)加速比
CCadd1000.803.05×
PCmul897000.8019.13×
Rot5123153631331.356.81×
总计69201536659215013.86×

4.2 性能瓶颈分析

  1. Rot核心限制因素：

    • KeySwitch占Rot时间的85%
    • NTT运算占KeySwitch时间的70%

  2. 内存带宽影响：

    • 矩阵数据带宽需求：1.28GB/s
    • HBM2实际带宽：460GB/s（利用率仅0.28%）

  3. 资源平衡：

    pie title FPGA资源分配 "Rot核心" : 65 "PCmul核心" : 30 "其他" : 5

4.3 对比实验

与CPU实现（Intel Xeon W-2295）的对比：

指标CPUFPGA加速比
单次MatMul29.8s2.15s13.86×
功耗105W38W2.76×能效提升
吞吐量0.03 ops/s0.47 ops/s15.67×

5. 工程实践中的挑战与解决方案

5.1 HLS实现挑战

  1. 复数控制流处理：

    • 原始SEAL代码包含大量条件分支
    • 解决方案：使用#pragma HLS LOOP_FLATTEN合并嵌套循环

  2. 大整数运算优化：

    // Barrett约减优化实现 inline uint64_t barrett_reduce(uint64_t a, uint64_t q, uint64_t mu) { #pragma HLS INLINE uint64_t hi = ((__uint128_t)a * mu) >> 64; return a - hi * q; }

5.2 精度保障措施

  1. RNS一致性检查：

    • 在每个limb处理完成后添加CRC校验
    • 发现错误时触发流水线刷新

  2. 边界条件处理：

    • 预计算特殊系数处理表
    • 使用ROM存储异常处理规则

5.3 实际部署经验

  1. 散热考虑：

    • 通过Vivado功耗分析确定热点区域
    • 在Rot核心周围添加散热约束

  2. 时序收敛技巧：

    • 对NTT关键路径使用register_duplication
    • 设置多周期路径约束

6. 应用前景与扩展方向

6.1 在隐私计算中的应用

  1. 隐私保护通信：

    • 消息检索延迟从分钟级降至秒级
    • 支持同时处理多个接收者的请求

  2. 区块链增强：

    • 实现交易内容的隐私保护验证
    • 典型应用：保密交易金额的UTXO验证

6.2 未来优化方向

  1. Rot核心架构改进：

    • 采用混合基NTT算法
    • 探索近似计算的可能性

  2. 系统级优化：

    • 与GPU组成异构计算系统
    • 研究流水线化的多MatMul并行

  3. 算法-硬件协同设计：

    • 定制化HE参数选择
    • 基于硬件特性的算法变形

在实际部署中，我们发现当N增加到2^18时，现有架构的URAM容量成为瓶颈。一个可行的解决方案是采用"矩阵分块"策略，将大矩阵分解为适合FPGA处理的子块。同时，通过重叠计算和数据传输，可以进一步隐藏内存访问延迟。