1. 项目概述为什么我们需要一个专用的BFV同态加密计算单元如果你正在研究隐私计算、安全多方计算或者联邦学习那么“同态加密”这个词对你来说一定不陌生。简单来说它就像给你的数据套上一个“加密黑盒”你可以在不打开黑盒、不接触原始数据的情况下对里面的密文进行各种计算比如加法、乘法得到的结果解密后和你在原始数据上做同样计算的结果完全一致。这听起来像是魔法但它确实是现代密码学送给数据隐私保护的一份大礼。在众多同态加密方案中BFVBrakerski/Fan-Vercauteren方案因其对整数运算的良好支持在隐私保护机器学习、安全生物特征识别等领域应用广泛。然而魔法的代价是巨大的计算开销。BFV的核心运算发生在多项式环上尤其是多项式乘法其复杂度是O(n²)当多项式阶数n达到4096甚至更高时软件实现的性能瓶颈就变得难以忍受。想象一下每次同态乘法都需要进行数万次的大整数模乘和模加这足以让最强大的CPU也气喘吁吁。为了加速学术界引入了残数系统RNS。它把一个大模数q拆解成多个小模数qi的集合将原本在一个大数域上的复杂运算分解到多个并行的小数域上进行这天然适合硬件并行加速。在RNS-BFV的众多变体中HPSHalevi-Polyakov-Shoup变体因其采用实数近似而非纯整数模运算硬件实现上更为友好成为了我们硬件加速的首选目标。即便如此HPS-BFV的计算流程中依然充满了“硬骨头”频繁的数论变换NTT/INTT用于加速多项式乘法、大量的模乘累加MAC操作用于RNS基扩展和缩放、以及无处不在的模加和模乘。这些操作共同构成了性能瓶颈。通用处理器CPU/GPU的架构并非为这类定点、密集的模运算而设计效率低下。因此设计一个专用的、高度并行的算术计算单元ACU来卸载这些核心计算任务就成为了突破性能瓶颈的必然选择。我这次分享的正是我们在Xilinx Alveo U250 FPGA上实现的一个高性能ACU设计。这个单元不是一个孤立的NTT加速器而是一个统一、可配置的计算核心能够灵活执行BFV-HPS方案中所需的所有关键多项式运算。我们的目标很明确在有限的硬件资源查找表LUT、触发器FF、数字信号处理器DSP、块存储器BRAM内实现最高的计算吞吐量和最低的延迟为构建一个完整的同态加密硬件加速器打下坚实的基础。2. 核心思路如何为BFV-HPS量身定制一个计算引擎设计一个高效的ACU不能只盯着单个运算的速度必须从BFV-HPS算法的整体计算流出发进行通盘考虑。我们的核心设计哲学是在数据流的关键路径上消除瓶颈通过硬件复用和精细的流水线设计在面积、功耗和性能之间取得最佳平衡。2.1 从算法到架构的映射首先我们需要清晰地理解BFV-HPS中哪些操作是“热点”。根据论文中的分析可以总结为以下几类多项式加/减MA/MS基础但频繁的操作。多项式乘法最核心的瓶颈通过NTT/INTT对来实现。乘累加MAC在RNS基扩展Algorithm 1和缩放Algorithm 2中大量出现形式为 Σ(A_i * constant_i) mod q_j。模乘MMNTT蝶形运算和MAC中的基本操作。一个直观的想法是为每种操作设计独立的硬件模块。但这会导致两个问题一是硬件资源碎片化利用率低二是不同模块间的数据调度和传输会引入额外开销。因此我们选择了可配置处理单元Configurable PE的路线。我们的核心思路是设计一种统一的蝶形运算单元它既能通过配置实现NTTCooley-Tukey蝶形和INTTGentleman-Sande蝶形又能在需要时将其内部的乘法器重用于独立的模乘或作为MAC操作的乘法部分。这样同一套硬件资源就能覆盖绝大部分计算需求。2.2 内存访问模式与并行度的权衡NTT/INTT的计算过程具有特定的数据访问模式即位反转、步长变化的蝶形运算。如果内存架构设计不当会产生大量的访问冲突迫使计算单元停滞等待数据严重制约性能。我们针对 n4096 的典型参数进行了深度优化。我们采用了多Bank块存储器BRAM的方案。具体来说我们使用了64个独立的BRAM Bank来存储多项式系数。通过精心设计数据在Bank间的分布规律基于系数索引的特定映射我们确保了在NTT计算的每一级stagePE阵列所需的所有输入数据都能从不同的Bank中无冲突地并行读取。这是实现高吞吐量的关键。并行度的选择我们使用了32个并行PE是另一个权衡点。更多的PE意味着更高的理论峰值性能但也会指数级增加PE间互联网络的复杂度、布线拥塞和功耗。我们通过综合评估目标FPGAAlveo U250的资源、时钟频率目标以及算法固有的数据依赖关系确定了32路并行是一个在性能提升和实现复杂度之间的理想折中点。2.3 统一的控制与数据通路一个灵活的ACU需要一个强大的“指挥官”。我们的控制单元负责协调整个数据流操作模式切换根据指令将PE阵列配置为NTT、INTT或MAC模式并设置相应的数据通路选择器MUX。地址生成为BRAM Bank生成正确的读/写地址序列以匹配NTT各级的蝶形运算模式。流水线调度管理MA、MM、MAC等操作的多级流水线确保数据在正确的时间到达正确的位置避免流水线冒险。数据通路的设计围绕“减少数据搬运”的原则。在NTT/INTT模式下PE级联输出可以直接作为下一级PE的输入形成了高效的流水线。在MAC模式下所有PE的乘法结果被直接导向一个集中的模加树MAT单元进行累加避免了将中间结果写回内存再读取的昂贵开销。提示在硬件设计中数据搬运的能耗和延迟常常超过计算本身。因此架构设计的艺术很大程度上在于如何让数据“待在原地”或“短距离移动”就能完成计算。3. 架构深潜可配置处理单元与模加树的设计奥秘下面我们来拆解ACU中最核心的两个部件可配置处理单元PE和模加树MAT。理解了它们你就掌握了这个ACU设计的精髓。3.1 可配置处理单元PE一芯多用的瑞士军刀我们的PE是一个高度集成的运算单元其设计目标是最大化硬件复用率。下图展示了其内部结构和三种配置模式----------------------------------- | PE (Processing Element)| | | inA -----|---- | | |MUX| | inB -----|---- | ---- | \ | | | | \ ---------------- | | MA |--- outA | ----| Modular Mult. |---------| | | / | (MM) | | ---- | / ---------------- | inC -----|---- | | ---- | |MUX| | | | | | --- v | | MS |--- outB | ------ ------| | | | FIFO | | ---- | ------ | | | -----------------------------------关键组件解析模乘单元MM这是PE的心脏采用基于Barrett约减算法的设计。它被设计为5级流水线能够在每个时钟周期开始一次新的30位模乘运算具体位数可根据参数调整并在5个周期后输出结果。Barrett算法通过预计算与模数q相关的常数用乘法和移位来代替昂贵的除法非常适合FPGA实现。模加MA与模减MS单元设计为2级流水线执行模q的加法和减法。它们不仅用于独立的加/减操作更重要的是处理NTT蝶形运算中的加/减部分。半乘器Half Multiplier这是一个针对INTT运算的优化设计。INTT的最后一步需要乘以一个常数 n^(-1) mod q即模逆元。我们发现在参数选择合理的情况下这个常数通常具有简单的二进制形式如2的幂次相关。因此我们用“移位条件加”的逻辑电路替代了一个完整的乘法器节省了大量DSP资源。FIFO与多路选择器MUX这些是实现“可配置”的关键。通过控制MUX的选通信号我们可以改变数据路径NTT模式inA和inB输入系数对inC输入旋转因子twiddle factor。数据流经MM单元相乘结果与直通路径进行MA/MS操作实现CT蝶形。INTT模式配置类似但内部数据路径和MA/MS的顺序遵循GS蝶形算法并使用半乘器进行最后的缩放。MAC模式此时PE被简化为一个模乘器。inB和inC作为乘数输入MM单元乘积结果直接输出到外部总线送往MAT单元进行累加。PE内部的MA/MS单元在此模式下不被使用。设计考量将NTT/INTT蝶形和乘法器融合在一个PE里带来了显著的硬件节省。传统的设计可能需要独立的蝶形单元和乘法单元。我们的方案通过增加一些多路选择逻辑面积开销很小换来了整体资源利用率的提升这对于资源受限的FPGA至关重要。3.2 模加树单元高效实现大规模累加MAC操作在BFV的基扩展和缩放中表现为多个多项式系数与常数的乘积之和。每个PE可以并行计算一个乘积项但我们需要将多达192个PE6级x 32个/级的输出快速累加起来。如果使用顺序累加器需要192个时钟周期这将成为严重的性能瓶颈。因此我们采用了并行模加树的设计。Stage 1 PE0..PE31 - [32个输入] | v ---------- | 16个加法器 | (第一级加法树) ---------- | v [16个中间和] | v ---------- | 8个加法器 | (第二级加法树) ---------- | v [8个中间和] | v ---------- | 4个加法器 | (第三级加法树) ---------- | v [最终和] -- 输出MAT工作流程每一级的32个PE输出同时送达本级对应的MAT子单元。MAT子单元内部是一个3级流水线的加法树。第一级32个数被两两相加得到16个部分和第二级16个部分和两两相加得到8个第三级得到最终的1个累加和。这样仅用3个时钟周期加上流水线填充时间就能完成32个数的模q累加而不是32个周期。最终6个MAT子单元的输出对应6个不同的模数q_j或p_j会被收集并写回内存用于后续计算。优势这种树形结构将O(N)的累加延迟降低到了O(log N)极大地加速了MAC操作。虽然它消耗了额外的加法器资源每个MAT子单元31个模加器但考虑到MAC在算法中的比重和其对整体延迟的影响这笔资源投资是非常划算的。实操心得流水线深度与频率的权衡。MA、MS、MM和MAT都采用了流水线设计。增加流水线级数可以提高系统的最大时钟频率因为每一级的逻辑更简单。但也会增加从数据输入到输出的初始延迟。我们需要在时序报告中找到关键路径然后有选择地插入流水线寄存器。在我们的设计中MM的5级流水和MAT的3级流水就是经过多次综合实现迭代后确定的“甜点”使得整个ACU能在目标FPGA上稳定运行在较高的频率例如250MHz以上。4. 数据流与调度让计算永不停止有了强大的计算单元如何高效地给它们“喂数据”是另一个挑战。我们的设计核心是精细化的数据流调度与无冲突内存访问。4.1 NTT/INTT的双迭代与内存管理对于n4096点的NTT我们采用了两级迭代的算法。为什么不是完全流水的单次计算因为完全展开4096点NTT需要log2(4096)12级流水线需要大量的PE和极其复杂的互连网络资源消耗巨大。我们采用折中的“半并行”方案第一级迭代使用6级PE流水线计算一个“块”的NTT。每级32个PE并行工作每次处理64个系数32个蝶形对。计算完一个“块”的中间结果后将其写回64个BRAM Bank中。第二级迭代从BRAM中按特定地址序列读出上一轮的结果再次送入相同的6级PE流水线进行剩余阶段的NTT计算。这种设计只需要6级物理PE通过重复使用它们两次来完成完整的12级NTT逻辑大幅节省了硬件资源。内存在这里扮演了“数据重排”的角色。控制单元根据NTT算法的阶数生成复杂的读地址序列确保第二次迭代时PE总能拿到正确的数据对进行蝶形运算。4.2 系数索引与PE互联为了实现无冲突访问数据在BRAM中的存储位置和PE之间的连接方式必须精心设计。我们的策略是基于系数索引的规律性进行静态映射。以NTT第一级迭代的第一阶段为例PE需要处理索引相差2048的系数对如Coeff[0]和Coeff[2048]。我们通过硬件连线将存储Coeff[0]的BRAM Bank输出直接连接到PE0的端口A将存储Coeff[2048]的Bank输出连接到PE0的端口B。这种连接是固定的、预定义的。通过为NTT的每一级都设计这样的固定互联模式我们完全消除了对复杂交叉开关Crossbar或动态路由网络的需求。数据从内存读出后通过一层简单的多路选择器根据当前计算阶段选择连接模式就能直接进入正确的PE路径极短延迟极低。4.3 控制状态机整个ACU由一个主状态机控制其状态大致包括空闲等待指令。加载配置根据操作类型NTT, INTT, MAC, MA等配置所有PE和路由MUX。数据加载从外部DDR内存或片上缓冲区将多项式系数加载到BRAM Banks。执行计算对于NTT/INTT依次进入迭代1、写回、迭代2、写回状态。于MAC广播常数和系数启动PE乘法收集结果到MAT累加写回结果。数据输出将最终结果从BRAM写回外部内存。状态机的设计保证了即使在不同操作间切换数据通路和控制信号也能正确建立使ACU成为一个真正通用的算从核。5. 实现、优化与性能对比我们将整个ACU设计用SystemVerilog HDL编写在Xilinx Vivado 2020.1工具链上针对Alveo U250加速卡进行综合、布局布线和实现。5.1 资源利用与时序达成下表展示了我们的ACU在Alveo U250上的资源占用情况资源类型使用数量占用率 (约)主要用途查找表 (LUT)232,742~15%控制逻辑、路由多路选择器、模加/减器、半乘器、状态机等。触发器 (FF)111,626~7%流水线寄存器、状态寄存器、数据缓冲等。数字信号处理器 (DSP)2,112~22%192个PE中每个PE的模乘单元MM核心。这是最主要的计算资源。块存储器 (BRAM)144 KB (32个36Kb块)~1%存储多项式系数的64个Bank每个Bank深度定制。利用率低是因为我们只存储中间数据而非全部系数。关键优化点DSP高效利用每个PE的模乘器都映射到FPGA的专用DSP Slice上。我们通过流水线化设计确保每个DSP在每个时钟周期都能开始一次新的乘法实现了接近100%的利用率。逻辑压缩通过手动的代码优化和综合属性设置如use_dsp48的智能推断确保加法树等逻辑尽可能使用LUT/FF实现为更关键的DSP和BRAM留出空间。时钟约束与物理优化我们为设计设置了250MHz的时钟约束。通过布局布线后的物理优化如手动设置模块布局、优化高扇出网络最终时序收敛在240MHz左右。这是一个在性能、功耗和布线难度之间平衡后的结果。5.2 性能指标与对比分析我们最关心的性能指标是吞吐量和延迟。延迟完成一次完整操作所需的时间。对于最复杂的4096点NTT从第一个系数输入到第一个结果输出我们的设计需要159个时钟周期。在240MHz下这大约是0.66微秒。吞吐量单位时间内处理的数据量。由于我们的处理是流水线的当管道填满后每个时钟周期都能输出64个系数每个系数30位。因此持续吞吐率为64 coeff/cycle * 30 bits/coeff * 240 MHz 460.8 Gbps。为了客观评价我们选取了近年来同样针对NTT进行FPGA加速的多个前沿工作进行比较。比较时我们统一使用面积-时间积ATP作为效率指标它同时考虑了资源占用和速度快慢数值越小通常意味着效率越高。设计平台时钟频率 (MHz)NTT延迟 (cycles)吞吐量 (Gbps)LUT-ATP (LUT·μs)BRAM-ATP (KB·μs)特点Our ACUAlveo U250240159460.836.70.10统一ACU支持多操作Ye et al. [21]Virtex-7200350200.125.10.94全展开流水线高资源Paludo et al. [22]Zynq-7000142200034.19.51.26紧凑型设计针对特定模数Hu et al. [24]Artix-716682097.414.21.15可配置多项式乘法器Di Matteo et al. [25]Zynq UltraScale167523718.8123.54.72面向SEAL库的可配置NTT对比分析吞吐量与延迟的领先我们的设计在吞吐量上达到460.8 Gbps是对比工作中最高的[21]的2.3倍同时延迟也是最低的159周期。这得益于我们高度并行的PE阵列32路和精心设计的无冲突内存访问流水线。BRAM效率的显著优势我们的BRAM-ATP仅为0.10远低于其他设计最高有9.4倍的差距。这验证了我们双迭代内存管理策略和精简Bank设计的有效性用很少的存储资源支撑了高吞吐计算。LUT效率的权衡我们的LUT-ATP36.7并非最低[22]的设计在这方面更优。这是因为我们的ACU集成了更复杂的控制逻辑、可配置路由和MAT单元以换取功能的全面性支持MAC等操作。这是一个为通用性付出的合理代价。架构的独特性需要强调的是大多数对比工作都是专用的NTT加速器。而我们的设计是一个通用的算术计算单元NTT只是其功能之一。在支持MAC、模加、模乘等BFV全操作集的前提下依然能在核心的NTT性能上超越多数专用设计这体现了我们架构的整体优越性。5.3 常见问题与调试经验在实际的FPGA实现过程中我们踩过不少坑这里分享几点关键经验问题一时序违例集中在互联网络。现象布局布线后关键路径出现在PE阵列与MAT单元之间或者BRAM输出到PE输入的多路选择器上。排查使用Vivado的时序报告工具定位到具体net和cell。发现是因为某些控制信号如MUX选择信号扇出过大导致布线延迟过长。解决寄存器复制对高扇出控制信号进行复制生成多个驱动源分担负载。手动布局约束使用PBLOCK约束将相关的PE、MUX和MAT单元在物理上布局得更近。优化代码将大型的case语句用于路由选择拆分成多级减少单级组合逻辑深度。问题二MAC操作结果偶尔出错。现象在长时间压力测试下MAC累加结果与软件模型比对有极低概率出现单个系数错误。排查这是一个棘手的间歇性错误。首先排除了软件模型问题。然后在硬件仿真中注入随机测试向量并增加断言检查。最终发现是MAT加法树的流水线控制信号存在一个时钟周期的竞争条件。当累加数据流突然停止时控制状态机提前了一个周期复位导致最后一组数据未被正确累加。解决仔细检查并重写了MAT单元及其与控制单元接口的有限状态机FSM确保所有握手信号如data_valid,ready都严格遵守流水线协议并增加了跨时钟域检查尽管是同步设计但时序检查很重要。修改后进行了超过10亿次随机测试未再出现错误。问题三功耗高于预期。现象上板实测功耗比Vivado功耗预估报告高出约15%。排查使用板卡上的功耗监测和Vivado的功耗分析工具。发现动态功耗主要来自两个部分一是大量DSP单元在240MHz下的频繁翻转二是时钟网络功耗因为我们的设计规模大时钟树负载重。解决时钟门控对暂时闲置的模块如某些未使用的PE组引入时钟门控。当ACU执行小规模操作时关闭部分PE的时钟显著降低了动态功耗。数据门控为输入到PE和MAT的数据路径添加使能信号。当数据无效时阻止寄存器不必要的翻转。降低电压在保证时序稳定的前提下轻微调低了FPGA核心电压。经过这些优化满载功耗从最初的18W左右降低到了15.8W。注意事项验证策略。对于密码学硬件设计正确性至关重要。我们的验证策略是分层的1) 单元级测试用随机向量测试每个MA、MS、MM模块2) 模块级测试验证PE在不同模式下的功能以及MAT的累加正确性3) 系统级测试用C软件模型如SEAL库生成大量的随机BFV操作序列加密、同态加、同态乘、解密将结果与硬件仿真输出进行逐位比对。只有通过所有层次的测试才能确信设计的正确性。6. 总结与展望这次在Alveo U250上实现BFV同态加密专用ACU的经历让我对硬件加速的复杂性有了更深的认识。它不仅仅是写RTL代码更是对算法、计算机体系结构、数字电路和EDA工具的深度融合。我们成功地将一个支持多操作、可配置的ACU集成到了芯片上并在吞吐量、延迟和BRAM效率上取得了竞争力的结果。这个ACU目前还是一个独立的计算核心。未来的工作方向很明确将其集成到一个完整的同态加密SoC系统中。这需要设计高效的外部内存接口当前系数从片外DDR加载仍是瓶颈。需要设计更宽的总线、预取缓存和DMA引擎以匹配ACU的计算吞吐。开发完整的控制器与指令集将BFV的各个步骤密钥生成、加密、同态运算、解密编译成一系列ACU指令由一个RISC-V之类的轻量级核心或专用状态机进行调度。探索更高阶的优化研究支持更大多项式如n8192, 16384的扩展架构或者探索更先进的数论变换算法如Good-Thomas算法在硬件上的实现。进行系统级应用验证将整个加速卡部署到实际的隐私计算框架中例如作为微软SEAL库的后端硬件加速器评估其在真实机器学习推理等应用中的端到端性能提升。硬件加速的道路没有捷径每一次性能的提升都来自于对细节的反复打磨和对架构的深入思考。这个ACU的设计特别是可配置PE和无冲突内存访问的思路或许也能为其他需要高性能多项式运算的领域如后量子密码学中的Kyber、Dilithium算法提供有价值的参考。希望这篇详细的分享能给正在探索硬件加速领域的你带来一些启发。