1. 项目概述为什么我们需要一个更快的NTT加速器如果你最近关注过密码学或者硬件安全领域大概率会听到“后量子密码学”这个词。简单来说我们目前广泛使用的RSA、ECC等公钥密码算法在未来的量子计算机面前可能不堪一击。为了应对这个“灰犀牛”式的威胁全球的密码学家和工程师们都在寻找新的、能抵抗量子攻击的算法。在这场竞赛中基于格Lattice的密码学方案脱颖而出并最终被NIST美国国家标准与技术研究院选为标准其中CRYSTALS-Kyber成为了密钥封装机制的赢家。Kyber算法的核心运算是什么是多项式乘法。但直接计算两个256次多项式的乘法复杂度是O(n²)对于嵌入式设备或需要高频次操作的服务器来说这简直是性能噩梦。于是数论变换NTT登场了。你可以把NTT理解为有限域上的“快速傅里叶变换FFT”它能把多项式乘法的复杂度神奇地降到O(n log n)。在硬件里实现一个高效的NTT就成了加速后量子密码学的关键。然而设计一个“好”的NTT硬件加速器就像在走钢丝需要在速度、面积成本和功耗之间找到最佳平衡点。有的设计追求极致速度用了大量并行单元结果芯片面积爆炸功耗也上去了不适合成本敏感的边缘设备。有的设计为了省面积只用单个计算单元串行工作虽然芯片小了但完成一次加解密要等上千个时钟周期吞吐量太低。更棘手的是NTT和它的逆变换INTT虽然数学上对称但数据流和计算顺序不同很多设计不得不为两者准备两套硬件进一步增加了面积开销。这就是我们设计UPP-NTT的出发点我们想要一个“全能选手”。它要足够快能满足现代通信的实时性要求它要足够“瘦”能在资源有限的FPGA上安家更重要的是它要足够“聪明”一套硬件既能算NTT也能算INTT不搞重复建设。我们最终在Xilinx Virtex-7 FPGA上实现的设计用470个时钟周期就能完成一次完整的NTTINTT变换频率跑到166MHz latency只有2.8微秒。相比之前的一些设计我们的执行时间减少了3到3.6倍而“单位面积的吞吐量”这个关键效率指标更是提升了最高4.5倍。下面我就来拆解一下这个“统一并行流水线NTT加速器”到底是怎么炼成的。2. 核心思路统一、并行与流水线的三位一体在设计之初我们就定下了三个核心原则统一、并行和流水线。这三个词构成了UPP-NTT架构的骨架也是它能在性能与面积间取得平衡的秘诀。2.1 “统一”的智慧一套硬件干两样活NTT和INTT在数学上是互逆的它们的核心计算单元——蝴蝶单元Butterfly Unit, BFU——看起来很像都是做模加、模减和模乘。但魔鬼在细节里在正向NTTCooley-Tukey算法中是先将输入b与旋转因子ω相乘再与a进行加减而在逆向INTTGentleman-Sande算法中则是先将a和b相减其结果再与ω相乘。数据流和乘法器的位置不同。传统的做法是为NTT和INTT各设计一套BFU或者设计一个能部分复用但控制逻辑复杂的单元。我们的思路更彻底设计一个真正统一的可重构数据通路。如图4所示我们的统一流水线蝴蝶单元UP-BFU内部通过一组精心设计的控制信号S0-S3和多路选择器MUX来动态配置数据流。在NTT模式S0-S3 “0011”多路选择器将输入b和旋转因子ω送入模乘单元计算(b * ω) mod q然后与a进行模加和模减得到输出A和B。在INTT模式S0-S3 “1100”多路选择器改为将(a - b) mod q的结果与ω送入模乘单元。同时加法器的输入也相应切换。这样一来昂贵的模乘器和模加/减器在两种模式下得到了100%的复用。唯一需要额外处理的是INTT最后一步的归一化乘法乘以n的模逆元对于Kyber是3303。我们通过一个模式相关的2-bit MUXs2, s3来解决在最后一个INTT阶段将固定乘数3303注入数据通路再次复用现有的模乘单元来完成。这种“统一”设计直接省下了一套BFU的面积对于我们要做四个并行BFU的设计来说面积节省是倍增的。实操心得模式切换的时序模式信号NTT/INTT需要在开始计算一批数据前就确定好并保持到这批数据全部计算完成。不能在流水线中途切换否则会导致数据流混乱产生错误结果。我们在控制器中设计了一个简单的状态机来管理这个模式信号。2.2 “并行”的力量四核驱动吞吐量翻倍理解了“统一”再看“并行”就简单了。既然一个BFU能高效工作那我们就把多个BFU堆起来一起算。我们选择了集成四个并行的BFU。为什么是四个这是一个经过权衡的折中点。对于一个256点n256的NTT每一级stage需要计算128个蝴蝶操作。如果只有一个BFU那就要串行计算128次。如果我们有P个并行BFU那么每级所需的时钟周期数就是(n/2) / P 128 / P。P1: 每级128周期总延迟太长。P8或16: 每级周期数少16或8速度极快但需要实例化8或16个BFU以及配套的存储器端口面积和布线复杂度会急剧上升可能成为频率瓶颈。P4: 每级需要128 / 4 32个周期。这是一个非常均衡的点它显著提升了速度是单核的4倍而四个BFU及其控制逻辑在目标FPGAVirtex-7上仍能在一个紧凑的布局内实现不会过度拥挤影响时序。四个BFU意味着每个时钟周期我们能同时读取8个系数4对进行4个蝴蝶操作并写回8个结果。这要求我们的存储器系统必须具备每个周期提供8个系数的带宽。2.3 “流水线”的哲学让硬件永远忙碌并行解决了“同时做多件事”的问题流水线则解决了“让每个部件一直有事做”的问题。想象一个汽车装配线底盘、发动机、轮胎安装在不同的工位多辆车可以同时在不同工位被加工。我们的BFU也是如此。如图4所示我们的UP-BFU被设计成一个11级深的流水线。这11级大致分为几个阶段地址生成与读取1周期计算要读取的系数地址从存储器中取出。输入寄存1周期将读取的系数存入输入寄存器reg-a。操作数选择1周期根据模式通过MUX选择正确的操作数送入reg-b。模乘运算4周期这是最耗时的部分我们将其拆分为4级流水线每一级完成部分积的生成或累加。模加/模减1周期对乘法结果进行加减运算结果存入reg-c。输出对齐与归一化2周期INTT模式下用于乘3303。写回1周期将最终结果写回存储器。关键点在于当流水线被填满后每一个时钟周期都会有一个新的蝴蝶操作进入第一级同时也会有一个完成的操作从最后一级输出。虽然一个数据走完全程需要11个周期流水线深度但系统的吞吐率是每个周期完成一个蝴蝶操作。这就像装配线虽然造一辆车要11小时但流水线稳定后每小时都能下线一辆新车。我们的整个UPP-NTT架构就是这条“超级装配线”四个并行的BFU四条产线都在以流水线方式全速运转。计算256点NTT的7个级stage每级32周期加上流水线填充和排空的少量开销总共只用235个周期就能完成一次NTT或INTT。这种深度流水线中度并行的组合是我们实现高吞吐量和低延迟的核心。3. 关键模块深度解析从算法到硬件的精妙实现有了顶层架构我们来看看几个关键模块是如何具体实现的这里藏着很多让设计变得高效、紧凑的“黑科技”。3.1 蝴蝶单元UP-BFU的解剖图4展示了UP-BFU的内部结构。除了前面提到的可重构数据流其核心是三个算术单元模加器、模减器和模乘器后接Barrett约减。模加器/模减器在有限域Z_qq3329里加减法后结果可能超出范围 [0, q-1]。模加器在相加后判断结果是否大于等于q如果是则减去q。模减器在相减后判断结果是否为负如果是则加上q。这些比较和条件操作通过组合逻辑实现延迟很小。模乘与Barrett约减这是最复杂的部分。两个12比特的数系数和旋转因子相乘得到一个24比特的中间乘积。我们需要将它模约减回12比特。直接做除法在硬件中非常昂贵。我们采用了经过移位-加法优化的Barrett约减算法。Barrett约减的核心思想是用乘法和移位来近似代替除法。对于固定的模数q我们可以预计算一个常数μ floor(2^(2k) / q)其中k ceil(log2(q))对于q3329, k12。约减公式大致为z a - q * floor((a * μ) / 2^(2k))。关键在于μ和q都是常数。在硬件中与常数的乘法a * μ和... * q并不需要通用的乘法器DSP。我们可以将其分解为一系列移位和加法操作。例如一个常数乘法a * 13可以分解为(a 3) (a 2) a即8a 4a a。在我们的设计中见算法3我们精确地设计了这样的移位-加法网络来实现与常数μ和q的乘法。这带来了一个巨大的优势整个Barrett约减模块完全由查找表LUT和寄存器FF实现没有使用任何DSP切片。DSP是FPGA中的珍贵资源通常只有几十到几百个。将它们节省下来可以用于其他更必要的乘法操作或者让我们的设计能部署在更小、更便宜的FPGA上。表1的对比很能说明问题我们设计的BFU仅需217个LUT和180个FF以及1个DSP仅用于系数与旋转因子的可变乘法。而一些参考文献中的设计需要600个以上的LUT和2-3个DSP。我们的BFU在面积上具有明显优势。3.2 无冲突的存储器组织与寻址艺术四个BFU并行工作每个周期要喂给它们8个系数这对存储器带宽提出了很高要求。最直接的想法是用多端口存储器如真双端口BRAM但FPGA中BRAM的端口数量是有限的通常最多两个读写端口。复制多份存储器又会导致面积浪费和数据一致性问题。我们的解决方案是创新的单存储器、无冲突访问组织。我们将256个系数看作一个整体但在物理上逻辑划分为两个128深的存储体Bank一个存放所有偶数索引的系数0, 2, 4, ...另一个存放所有奇数索引的系数1, 3, 5, ...。这个划分是静态的、确定的。为什么这样能实现无冲突并行访问这要归功于基-2 NTT算法本身的特性。在每一级stage s蝴蝶操作配对的系数之间的距离stride是2^(7-s)。例如Stage 1: 配对 (0,128), (2,130), (4,132) ... 跨度128。Stage 2: 配对 (0,64), (2,66), (4,68) ... 跨度64。...Stage 7: 配对 (0,1), (2,3), (4,5) ... 跨度1。观察这些配对在跨度大的阶段如Stage 1配对的系数索引的奇偶性总是相同都是偶数或都是奇数。在跨度小的阶段如Stage 7配对的系数索引是连续的因此奇偶性交替。我们的双Bank结构完美适配了这种模式当需要访问两个偶数索引时它们都来自偶数Bank。我们可以同时读取两个甚至四个偶数地址。当需要访问一奇一偶索引时它们分别来自奇数和偶数Bank同样可以并行读取。关键在于我们设计了一个统一的地址生成器算法4和地址解码器算法5。地址生成器根据当前级数s和一个5比特的级内计数器生成一个“基地址”。解码器则根据当前级数s计算出一个跨度stride并由此生成另外三个关联地址。例如在Stage 3跨度16如果基地址是0解码器会生成地址16, 1, 17。这样我们就得到了两对系数(0,16) 和 (1,17)。其中(0,16)来自偶数Bank(1,17)来自奇数Bank可以无冲突地同时读取。这种方案的精妙之处在于它用简单的逻辑划分奇偶Bank和巧妙的地址计算替代了复杂的多端口存储器或交叉开关网络以极低的控制开销实现了高带宽的并行数据供给。3.3 旋转因子地址生成器TAGNTT计算需要用到预先计算好的旋转因子twiddle factors。这些因子存储在ROM中。不同的计算阶段、不同的蝴蝶对需要不同的旋转因子。如何为四个并行的BFU实时、正确地提供旋转因子地址是另一个挑战。我们设计了一个与流水线阶段同步的旋转因子地址生成器TAG算法6。它的核心也是一个基于移位的计算。对于第s级s从1到7旋转因子地址可以通过公式计算tw_addr (coeff_addr (8 - s)) 2^(s-1)。这个公式的直观理解是在每一级所有具有相同“组”特征的蝴蝶使用同一个旋转因子。右移操作(coeff_addr (8-s))提取了系数地址的高位这些高位决定了它属于哪个组。加上偏移量2^(s-1)是因为旋转因子在ROM中是按阶段连续存储的。例如在Stage 3s3公式变为tw_addr (coeff_addr 5) 4。系数地址0-31右移5位后都是0加上4得到旋转因子地址4。系数地址32-63右移5位后是1加上4得到地址5依此类推。这样Stage 3的蝴蝶会使用旋转因子地址4,5,6,7对应ROM中预先计算好的4个值。TAG根据BFU正在处理的系数地址实时计算出这个地址确保每个BFU在每个周期都能拿到正确的旋转因子。对于INTT模式计算逻辑类似只是阶段顺序反过来从7到1并且使用一个不同的ROM基地址区域来获取逆变换的旋转因子。TAG通过一个模式信号mode来区分这两种情况。4. 实现、测试与性能对比设计完成后我们在Xilinx Vivado 2020.1环境下用Verilog HDL完成了RTL编码并在Xilinx Virtex-7 (xc7vx485tffg1157-1) 和更先进的Virtex UltraScale (xcvu9p-flga2104-2L-e) FPGA上进行了综合、布局布线和时序验证。4.1 资源消耗与性能数据表5总结了我们的实现结果。在Virtex-7上资源占用总共使用了905个Slices 2472个LUTs 1108个FFs以及仅4个DSPs。没有使用任何BRAM系数存储和旋转因子ROM都用分布式RAMLUTRAM实现这得益于我们紧凑的存储设计。时序性能最高运行频率达到166 MHz。完成一次NTT需要235个周期一次INTT需要235个周期一对完整的NTTINTT需要470个周期。总延迟为470 / 166 MHz ≈ 2.8 µs。效率指标吞吐量为每秒1 / (2.8e-6) ≈ 357,142次变换对。更重要指标是单位面积吞吐量Throughput per Slice达到了357.14 / 905 ≈ 394.62。这个数字越高说明硬件效率越好。在工艺更先进的Virtex UltraScale上由于逻辑单元速度更快频率提升到了250 MHz。虽然周期数不变但延迟降低到了1.8 µs吞吐量提升到约555,555次/秒。由于UltraScale架构的Slice结构可能更高效我们只用了475个Slices使得单位面积吞吐量飙升至1169.57是Virtex-7版本的近3倍这充分说明了我们的架构具有良好的工艺扩展性。4.2 与同类工作的横向对比我们选择了多个近年来发表的高性能NTT加速器设计进行公平对比均在Artix-7/Virtex-7/Kintex UltraScale等7系列或UltraScale系列FPGA上实现。对比结果详见表6和表7。性能对比表6vs. Unif-NTT [25]该设计也强调统一架构但在Virtex-7上完成NTTINTT需要约4.2-4.8 µs比我们的2.8 µs慢了约50%-70%而其切片Slice使用量1287却比我们905更高。vs. FP-NTT [20]该设计具有灵活的并行性但在Virtex-7上延迟为4.6-5.1 µs比我们慢65%-82%切片使用量1026也更高。vs. 超低延迟设计 [18]这个设计确实快延迟仅0.4 µs但它付出了巨大的面积代价使用了6090个Slices和64个DSPs其单位面积吞吐量仅为205.2远低于我们的394.62。这意味着为了获得一点速度提升需要付出巨大的芯片面积成本在很多场景下并不经济。vs. 轻量级设计 [24]该设计非常省面积仅314 Slices但代价是速度慢需要2016个周期延迟是我们的近3倍。综合效率对比表7 我们引入了一个更全面的指标平均面积-时间积。这个指标将面积用Slice Equivalent Cost, SEC衡量它综合了LUT、FF、DSP、BRAM的等效成本和延迟相乘。Avg-ATP越小说明设计在平衡面积和速度方面做得越好。 我们的设计在Virtex-7上取得了最低的Avg-ATP1.82e-3。相比FP-NTT [20]Avg-ATP 4.97e-3和Unif-NTT [25]Avg-ATP 5.56e-3我们的效率提升了约2.7-3倍。这清晰地表明UPP-NTT在取得低延迟的同时更好地控制了硬件开销实现了更优的“性价比”。4.3 实测中的注意事项与调试经验将这样一个并行流水线设计在FPGA上跑通并达到预期频率并非一帆风顺。这里分享几个踩过的坑流水线平衡是关键最初设计时模乘器的4级流水线划分不合理导致其中一级的组合逻辑延迟过长成为整个系统的关键路径频率只能跑到120MHz。我们通过重新划分乘法步骤将进位传播较重的部分拆到两级中并插入额外的流水线寄存器成功将关键路径缩短频率提升到166MHz。教训深度流水线中每一级的延迟要尽量均衡。存储器访问冲突的幽灵在早期仿真中偶尔会出现计算结果错误。经过漫长的调试发现是地址解码器在某个特定阶段stage过渡的边界周期产生了错误的地址导致一个BFU读到了不属于它的数据。问题根源在于控制状态机与地址生成计数器在阶段切换时的同步有单周期偏差。我们通过仔细调整状态机并添加了明确的“阶段预加载”周期来解决。教训对于并行访问的存储系统地址生成逻辑的时序必须万无一失边界情况要重点测试。复位与初始化由于有11级流水线系统从复位到稳定输出需要多个周期。我们必须确保在开始有效计算前所有流水线寄存器都被初始化为已知值通常是0并且旋转因子ROM的内容已正确加载。我们设计了一个简单的启动序列复位后先等待若干个周期进行初始化然后由外部控制器发出启动信号。教训复杂的流水线系统需要一个清晰、稳定的启动和复位序列。验证策略我们搭建了一个基于SystemVerilog的通用测试平台UVM风格。测试向量直接使用CRYSTALS-Kyber官方参考代码生成的随机多项式。测试平台自动将输入多项式送入加速器获取输出结果并与软件参考模型Python实现的计算结果进行逐点比较。除了随机测试我们还加入了边界测试如全零、全一多项式和压力测试连续发送多组数据。教训对于密码学硬件验证必须极其严格100%的功能覆盖是底线。5. 总结与展望不止于KyberUPP-NTT的设计证明通过统一数据通路、适度的并行度、深度流水线以及针对特定算法Kyber的优化如移位-加Barrett约减我们可以在FPGA上实现一个在延迟、吞吐量和面积效率之间取得出色平衡的NTT加速器。它为在资源受限的边缘设备上部署后量子密码学提供了有力的硬件支持。当然这个设计也有其明确的适用范围。它目前是针对Kyber的固定参数n256, q3329高度优化的。模数q3329和旋转因子都是硬编码在逻辑中的。那么它能用于其他算法吗答案是肯定的但需要调整。我们的架构核心——统一的并行流水线BFU、无冲突的存储器组织、阶段感知的地址生成器——是通用的适用于任何基于2的幂次长度的NTT。要适配其他算法如Dilithium, Falcon主要需要修改三个地方旋转因子ROM需要替换为对应算法和模数的预计算值。Barrett约减模块常数μ和q的移位-加法网络需要根据新的模数重新计算和优化。控制参数如变换长度n可能是512或1024这会影响地址生成器中的级数log2(n)和计数器位宽。未来的工作可以沿着几个方向展开一是将UPP-NTT扩展为一个完整的Kyber加速器集成多项式采样、点乘等模块二是探索对更大参数如n512, 1024的支持这可能需要调整并行度或存储器层次结构三是向ASIC移植进行更极致的功耗和面积优化。从更广的视角看UPP-NTT的设计哲学——在专用性和灵活性之间寻找最佳实践点通过算法与硬件的协同优化来挖掘性能——对于任何需要高性能计算加速的领域都有着普遍的借鉴意义。当摩尔定律逐渐放缓这种“精打细算”的架构创新正变得比以往任何时候都更加重要。
UPP-NTT：统一并行流水线架构，实现后量子密码硬件加速
1. 项目概述为什么我们需要一个更快的NTT加速器如果你最近关注过密码学或者硬件安全领域大概率会听到“后量子密码学”这个词。简单来说我们目前广泛使用的RSA、ECC等公钥密码算法在未来的量子计算机面前可能不堪一击。为了应对这个“灰犀牛”式的威胁全球的密码学家和工程师们都在寻找新的、能抵抗量子攻击的算法。在这场竞赛中基于格Lattice的密码学方案脱颖而出并最终被NIST美国国家标准与技术研究院选为标准其中CRYSTALS-Kyber成为了密钥封装机制的赢家。Kyber算法的核心运算是什么是多项式乘法。但直接计算两个256次多项式的乘法复杂度是O(n²)对于嵌入式设备或需要高频次操作的服务器来说这简直是性能噩梦。于是数论变换NTT登场了。你可以把NTT理解为有限域上的“快速傅里叶变换FFT”它能把多项式乘法的复杂度神奇地降到O(n log n)。在硬件里实现一个高效的NTT就成了加速后量子密码学的关键。然而设计一个“好”的NTT硬件加速器就像在走钢丝需要在速度、面积成本和功耗之间找到最佳平衡点。有的设计追求极致速度用了大量并行单元结果芯片面积爆炸功耗也上去了不适合成本敏感的边缘设备。有的设计为了省面积只用单个计算单元串行工作虽然芯片小了但完成一次加解密要等上千个时钟周期吞吐量太低。更棘手的是NTT和它的逆变换INTT虽然数学上对称但数据流和计算顺序不同很多设计不得不为两者准备两套硬件进一步增加了面积开销。这就是我们设计UPP-NTT的出发点我们想要一个“全能选手”。它要足够快能满足现代通信的实时性要求它要足够“瘦”能在资源有限的FPGA上安家更重要的是它要足够“聪明”一套硬件既能算NTT也能算INTT不搞重复建设。我们最终在Xilinx Virtex-7 FPGA上实现的设计用470个时钟周期就能完成一次完整的NTTINTT变换频率跑到166MHz latency只有2.8微秒。相比之前的一些设计我们的执行时间减少了3到3.6倍而“单位面积的吞吐量”这个关键效率指标更是提升了最高4.5倍。下面我就来拆解一下这个“统一并行流水线NTT加速器”到底是怎么炼成的。2. 核心思路统一、并行与流水线的三位一体在设计之初我们就定下了三个核心原则统一、并行和流水线。这三个词构成了UPP-NTT架构的骨架也是它能在性能与面积间取得平衡的秘诀。2.1 “统一”的智慧一套硬件干两样活NTT和INTT在数学上是互逆的它们的核心计算单元——蝴蝶单元Butterfly Unit, BFU——看起来很像都是做模加、模减和模乘。但魔鬼在细节里在正向NTTCooley-Tukey算法中是先将输入b与旋转因子ω相乘再与a进行加减而在逆向INTTGentleman-Sande算法中则是先将a和b相减其结果再与ω相乘。数据流和乘法器的位置不同。传统的做法是为NTT和INTT各设计一套BFU或者设计一个能部分复用但控制逻辑复杂的单元。我们的思路更彻底设计一个真正统一的可重构数据通路。如图4所示我们的统一流水线蝴蝶单元UP-BFU内部通过一组精心设计的控制信号S0-S3和多路选择器MUX来动态配置数据流。在NTT模式S0-S3 “0011”多路选择器将输入b和旋转因子ω送入模乘单元计算(b * ω) mod q然后与a进行模加和模减得到输出A和B。在INTT模式S0-S3 “1100”多路选择器改为将(a - b) mod q的结果与ω送入模乘单元。同时加法器的输入也相应切换。这样一来昂贵的模乘器和模加/减器在两种模式下得到了100%的复用。唯一需要额外处理的是INTT最后一步的归一化乘法乘以n的模逆元对于Kyber是3303。我们通过一个模式相关的2-bit MUXs2, s3来解决在最后一个INTT阶段将固定乘数3303注入数据通路再次复用现有的模乘单元来完成。这种“统一”设计直接省下了一套BFU的面积对于我们要做四个并行BFU的设计来说面积节省是倍增的。实操心得模式切换的时序模式信号NTT/INTT需要在开始计算一批数据前就确定好并保持到这批数据全部计算完成。不能在流水线中途切换否则会导致数据流混乱产生错误结果。我们在控制器中设计了一个简单的状态机来管理这个模式信号。2.2 “并行”的力量四核驱动吞吐量翻倍理解了“统一”再看“并行”就简单了。既然一个BFU能高效工作那我们就把多个BFU堆起来一起算。我们选择了集成四个并行的BFU。为什么是四个这是一个经过权衡的折中点。对于一个256点n256的NTT每一级stage需要计算128个蝴蝶操作。如果只有一个BFU那就要串行计算128次。如果我们有P个并行BFU那么每级所需的时钟周期数就是(n/2) / P 128 / P。P1: 每级128周期总延迟太长。P8或16: 每级周期数少16或8速度极快但需要实例化8或16个BFU以及配套的存储器端口面积和布线复杂度会急剧上升可能成为频率瓶颈。P4: 每级需要128 / 4 32个周期。这是一个非常均衡的点它显著提升了速度是单核的4倍而四个BFU及其控制逻辑在目标FPGAVirtex-7上仍能在一个紧凑的布局内实现不会过度拥挤影响时序。四个BFU意味着每个时钟周期我们能同时读取8个系数4对进行4个蝴蝶操作并写回8个结果。这要求我们的存储器系统必须具备每个周期提供8个系数的带宽。2.3 “流水线”的哲学让硬件永远忙碌并行解决了“同时做多件事”的问题流水线则解决了“让每个部件一直有事做”的问题。想象一个汽车装配线底盘、发动机、轮胎安装在不同的工位多辆车可以同时在不同工位被加工。我们的BFU也是如此。如图4所示我们的UP-BFU被设计成一个11级深的流水线。这11级大致分为几个阶段地址生成与读取1周期计算要读取的系数地址从存储器中取出。输入寄存1周期将读取的系数存入输入寄存器reg-a。操作数选择1周期根据模式通过MUX选择正确的操作数送入reg-b。模乘运算4周期这是最耗时的部分我们将其拆分为4级流水线每一级完成部分积的生成或累加。模加/模减1周期对乘法结果进行加减运算结果存入reg-c。输出对齐与归一化2周期INTT模式下用于乘3303。写回1周期将最终结果写回存储器。关键点在于当流水线被填满后每一个时钟周期都会有一个新的蝴蝶操作进入第一级同时也会有一个完成的操作从最后一级输出。虽然一个数据走完全程需要11个周期流水线深度但系统的吞吐率是每个周期完成一个蝴蝶操作。这就像装配线虽然造一辆车要11小时但流水线稳定后每小时都能下线一辆新车。我们的整个UPP-NTT架构就是这条“超级装配线”四个并行的BFU四条产线都在以流水线方式全速运转。计算256点NTT的7个级stage每级32周期加上流水线填充和排空的少量开销总共只用235个周期就能完成一次NTT或INTT。这种深度流水线中度并行的组合是我们实现高吞吐量和低延迟的核心。3. 关键模块深度解析从算法到硬件的精妙实现有了顶层架构我们来看看几个关键模块是如何具体实现的这里藏着很多让设计变得高效、紧凑的“黑科技”。3.1 蝴蝶单元UP-BFU的解剖图4展示了UP-BFU的内部结构。除了前面提到的可重构数据流其核心是三个算术单元模加器、模减器和模乘器后接Barrett约减。模加器/模减器在有限域Z_qq3329里加减法后结果可能超出范围 [0, q-1]。模加器在相加后判断结果是否大于等于q如果是则减去q。模减器在相减后判断结果是否为负如果是则加上q。这些比较和条件操作通过组合逻辑实现延迟很小。模乘与Barrett约减这是最复杂的部分。两个12比特的数系数和旋转因子相乘得到一个24比特的中间乘积。我们需要将它模约减回12比特。直接做除法在硬件中非常昂贵。我们采用了经过移位-加法优化的Barrett约减算法。Barrett约减的核心思想是用乘法和移位来近似代替除法。对于固定的模数q我们可以预计算一个常数μ floor(2^(2k) / q)其中k ceil(log2(q))对于q3329, k12。约减公式大致为z a - q * floor((a * μ) / 2^(2k))。关键在于μ和q都是常数。在硬件中与常数的乘法a * μ和... * q并不需要通用的乘法器DSP。我们可以将其分解为一系列移位和加法操作。例如一个常数乘法a * 13可以分解为(a 3) (a 2) a即8a 4a a。在我们的设计中见算法3我们精确地设计了这样的移位-加法网络来实现与常数μ和q的乘法。这带来了一个巨大的优势整个Barrett约减模块完全由查找表LUT和寄存器FF实现没有使用任何DSP切片。DSP是FPGA中的珍贵资源通常只有几十到几百个。将它们节省下来可以用于其他更必要的乘法操作或者让我们的设计能部署在更小、更便宜的FPGA上。表1的对比很能说明问题我们设计的BFU仅需217个LUT和180个FF以及1个DSP仅用于系数与旋转因子的可变乘法。而一些参考文献中的设计需要600个以上的LUT和2-3个DSP。我们的BFU在面积上具有明显优势。3.2 无冲突的存储器组织与寻址艺术四个BFU并行工作每个周期要喂给它们8个系数这对存储器带宽提出了很高要求。最直接的想法是用多端口存储器如真双端口BRAM但FPGA中BRAM的端口数量是有限的通常最多两个读写端口。复制多份存储器又会导致面积浪费和数据一致性问题。我们的解决方案是创新的单存储器、无冲突访问组织。我们将256个系数看作一个整体但在物理上逻辑划分为两个128深的存储体Bank一个存放所有偶数索引的系数0, 2, 4, ...另一个存放所有奇数索引的系数1, 3, 5, ...。这个划分是静态的、确定的。为什么这样能实现无冲突并行访问这要归功于基-2 NTT算法本身的特性。在每一级stage s蝴蝶操作配对的系数之间的距离stride是2^(7-s)。例如Stage 1: 配对 (0,128), (2,130), (4,132) ... 跨度128。Stage 2: 配对 (0,64), (2,66), (4,68) ... 跨度64。...Stage 7: 配对 (0,1), (2,3), (4,5) ... 跨度1。观察这些配对在跨度大的阶段如Stage 1配对的系数索引的奇偶性总是相同都是偶数或都是奇数。在跨度小的阶段如Stage 7配对的系数索引是连续的因此奇偶性交替。我们的双Bank结构完美适配了这种模式当需要访问两个偶数索引时它们都来自偶数Bank。我们可以同时读取两个甚至四个偶数地址。当需要访问一奇一偶索引时它们分别来自奇数和偶数Bank同样可以并行读取。关键在于我们设计了一个统一的地址生成器算法4和地址解码器算法5。地址生成器根据当前级数s和一个5比特的级内计数器生成一个“基地址”。解码器则根据当前级数s计算出一个跨度stride并由此生成另外三个关联地址。例如在Stage 3跨度16如果基地址是0解码器会生成地址16, 1, 17。这样我们就得到了两对系数(0,16) 和 (1,17)。其中(0,16)来自偶数Bank(1,17)来自奇数Bank可以无冲突地同时读取。这种方案的精妙之处在于它用简单的逻辑划分奇偶Bank和巧妙的地址计算替代了复杂的多端口存储器或交叉开关网络以极低的控制开销实现了高带宽的并行数据供给。3.3 旋转因子地址生成器TAGNTT计算需要用到预先计算好的旋转因子twiddle factors。这些因子存储在ROM中。不同的计算阶段、不同的蝴蝶对需要不同的旋转因子。如何为四个并行的BFU实时、正确地提供旋转因子地址是另一个挑战。我们设计了一个与流水线阶段同步的旋转因子地址生成器TAG算法6。它的核心也是一个基于移位的计算。对于第s级s从1到7旋转因子地址可以通过公式计算tw_addr (coeff_addr (8 - s)) 2^(s-1)。这个公式的直观理解是在每一级所有具有相同“组”特征的蝴蝶使用同一个旋转因子。右移操作(coeff_addr (8-s))提取了系数地址的高位这些高位决定了它属于哪个组。加上偏移量2^(s-1)是因为旋转因子在ROM中是按阶段连续存储的。例如在Stage 3s3公式变为tw_addr (coeff_addr 5) 4。系数地址0-31右移5位后都是0加上4得到旋转因子地址4。系数地址32-63右移5位后是1加上4得到地址5依此类推。这样Stage 3的蝴蝶会使用旋转因子地址4,5,6,7对应ROM中预先计算好的4个值。TAG根据BFU正在处理的系数地址实时计算出这个地址确保每个BFU在每个周期都能拿到正确的旋转因子。对于INTT模式计算逻辑类似只是阶段顺序反过来从7到1并且使用一个不同的ROM基地址区域来获取逆变换的旋转因子。TAG通过一个模式信号mode来区分这两种情况。4. 实现、测试与性能对比设计完成后我们在Xilinx Vivado 2020.1环境下用Verilog HDL完成了RTL编码并在Xilinx Virtex-7 (xc7vx485tffg1157-1) 和更先进的Virtex UltraScale (xcvu9p-flga2104-2L-e) FPGA上进行了综合、布局布线和时序验证。4.1 资源消耗与性能数据表5总结了我们的实现结果。在Virtex-7上资源占用总共使用了905个Slices 2472个LUTs 1108个FFs以及仅4个DSPs。没有使用任何BRAM系数存储和旋转因子ROM都用分布式RAMLUTRAM实现这得益于我们紧凑的存储设计。时序性能最高运行频率达到166 MHz。完成一次NTT需要235个周期一次INTT需要235个周期一对完整的NTTINTT需要470个周期。总延迟为470 / 166 MHz ≈ 2.8 µs。效率指标吞吐量为每秒1 / (2.8e-6) ≈ 357,142次变换对。更重要指标是单位面积吞吐量Throughput per Slice达到了357.14 / 905 ≈ 394.62。这个数字越高说明硬件效率越好。在工艺更先进的Virtex UltraScale上由于逻辑单元速度更快频率提升到了250 MHz。虽然周期数不变但延迟降低到了1.8 µs吞吐量提升到约555,555次/秒。由于UltraScale架构的Slice结构可能更高效我们只用了475个Slices使得单位面积吞吐量飙升至1169.57是Virtex-7版本的近3倍这充分说明了我们的架构具有良好的工艺扩展性。4.2 与同类工作的横向对比我们选择了多个近年来发表的高性能NTT加速器设计进行公平对比均在Artix-7/Virtex-7/Kintex UltraScale等7系列或UltraScale系列FPGA上实现。对比结果详见表6和表7。性能对比表6vs. Unif-NTT [25]该设计也强调统一架构但在Virtex-7上完成NTTINTT需要约4.2-4.8 µs比我们的2.8 µs慢了约50%-70%而其切片Slice使用量1287却比我们905更高。vs. FP-NTT [20]该设计具有灵活的并行性但在Virtex-7上延迟为4.6-5.1 µs比我们慢65%-82%切片使用量1026也更高。vs. 超低延迟设计 [18]这个设计确实快延迟仅0.4 µs但它付出了巨大的面积代价使用了6090个Slices和64个DSPs其单位面积吞吐量仅为205.2远低于我们的394.62。这意味着为了获得一点速度提升需要付出巨大的芯片面积成本在很多场景下并不经济。vs. 轻量级设计 [24]该设计非常省面积仅314 Slices但代价是速度慢需要2016个周期延迟是我们的近3倍。综合效率对比表7 我们引入了一个更全面的指标平均面积-时间积。这个指标将面积用Slice Equivalent Cost, SEC衡量它综合了LUT、FF、DSP、BRAM的等效成本和延迟相乘。Avg-ATP越小说明设计在平衡面积和速度方面做得越好。 我们的设计在Virtex-7上取得了最低的Avg-ATP1.82e-3。相比FP-NTT [20]Avg-ATP 4.97e-3和Unif-NTT [25]Avg-ATP 5.56e-3我们的效率提升了约2.7-3倍。这清晰地表明UPP-NTT在取得低延迟的同时更好地控制了硬件开销实现了更优的“性价比”。4.3 实测中的注意事项与调试经验将这样一个并行流水线设计在FPGA上跑通并达到预期频率并非一帆风顺。这里分享几个踩过的坑流水线平衡是关键最初设计时模乘器的4级流水线划分不合理导致其中一级的组合逻辑延迟过长成为整个系统的关键路径频率只能跑到120MHz。我们通过重新划分乘法步骤将进位传播较重的部分拆到两级中并插入额外的流水线寄存器成功将关键路径缩短频率提升到166MHz。教训深度流水线中每一级的延迟要尽量均衡。存储器访问冲突的幽灵在早期仿真中偶尔会出现计算结果错误。经过漫长的调试发现是地址解码器在某个特定阶段stage过渡的边界周期产生了错误的地址导致一个BFU读到了不属于它的数据。问题根源在于控制状态机与地址生成计数器在阶段切换时的同步有单周期偏差。我们通过仔细调整状态机并添加了明确的“阶段预加载”周期来解决。教训对于并行访问的存储系统地址生成逻辑的时序必须万无一失边界情况要重点测试。复位与初始化由于有11级流水线系统从复位到稳定输出需要多个周期。我们必须确保在开始有效计算前所有流水线寄存器都被初始化为已知值通常是0并且旋转因子ROM的内容已正确加载。我们设计了一个简单的启动序列复位后先等待若干个周期进行初始化然后由外部控制器发出启动信号。教训复杂的流水线系统需要一个清晰、稳定的启动和复位序列。验证策略我们搭建了一个基于SystemVerilog的通用测试平台UVM风格。测试向量直接使用CRYSTALS-Kyber官方参考代码生成的随机多项式。测试平台自动将输入多项式送入加速器获取输出结果并与软件参考模型Python实现的计算结果进行逐点比较。除了随机测试我们还加入了边界测试如全零、全一多项式和压力测试连续发送多组数据。教训对于密码学硬件验证必须极其严格100%的功能覆盖是底线。5. 总结与展望不止于KyberUPP-NTT的设计证明通过统一数据通路、适度的并行度、深度流水线以及针对特定算法Kyber的优化如移位-加Barrett约减我们可以在FPGA上实现一个在延迟、吞吐量和面积效率之间取得出色平衡的NTT加速器。它为在资源受限的边缘设备上部署后量子密码学提供了有力的硬件支持。当然这个设计也有其明确的适用范围。它目前是针对Kyber的固定参数n256, q3329高度优化的。模数q3329和旋转因子都是硬编码在逻辑中的。那么它能用于其他算法吗答案是肯定的但需要调整。我们的架构核心——统一的并行流水线BFU、无冲突的存储器组织、阶段感知的地址生成器——是通用的适用于任何基于2的幂次长度的NTT。要适配其他算法如Dilithium, Falcon主要需要修改三个地方旋转因子ROM需要替换为对应算法和模数的预计算值。Barrett约减模块常数μ和q的移位-加法网络需要根据新的模数重新计算和优化。控制参数如变换长度n可能是512或1024这会影响地址生成器中的级数log2(n)和计数器位宽。未来的工作可以沿着几个方向展开一是将UPP-NTT扩展为一个完整的Kyber加速器集成多项式采样、点乘等模块二是探索对更大参数如n512, 1024的支持这可能需要调整并行度或存储器层次结构三是向ASIC移植进行更极致的功耗和面积优化。从更广的视角看UPP-NTT的设计哲学——在专用性和灵活性之间寻找最佳实践点通过算法与硬件的协同优化来挖掘性能——对于任何需要高性能计算加速的领域都有着普遍的借鉴意义。当摩尔定律逐渐放缓这种“精打细算”的架构创新正变得比以往任何时候都更加重要。
