当前位置：首页 > news >正文

UPP-NTT：统一并行流水线架构，实现后量子密码硬件加速

news 2026/5/27 14:42:36

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个时钟周期就能完成一次完整的NTT+INTT变换，频率跑到166MHz， latency只有2.8微秒。相比之前的一些设计，我们的执行时间减少了3到3.6倍，而“单位面积的吞吐量”这个关键效率指标，更是提升了最高4.5倍。下面，我就来拆解一下，这个“统一并行流水线NTT加速器”到底是怎么炼成的。

2. 核心思路：统一、并行与流水线的三位一体

在设计之初，我们就定下了三个核心原则：统一、并行和流水线。这三个词构成了UPP-NTT架构的骨架，也是它能在性能与面积间取得平衡的秘诀。

2.1 “统一”的智慧：一套硬件干两样活

NTT和INTT在数学上是互逆的，它们的核心计算单元——蝴蝶单元（Butterfly Unit, BFU）——看起来很像，都是做模加、模减和模乘。但魔鬼在细节里：在正向NTT（Cooley-Tukey算法）中，是先将输入b与旋转因子ω相乘，再与a进行加减；而在逆向INTT（Gentleman-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 MUX（s2, s3）来解决，在最后一个INTT阶段，将固定乘数3303注入数据通路，再次复用现有的模乘单元来完成。这种“统一”设计，直接省下了一套BFU的面积，对于我们要做四个并行BFU的设计来说，面积节省是倍增的。

实操心得：模式切换的时序模式信号（NTT/INTT）需要在开始计算一批数据前就确定好，并保持到这批数据全部计算完成。不能在流水线中途切换，否则会导致数据流混乱，产生错误结果。我们在控制器中设计了一个简单的状态机来管理这个模式信号。

2.2 “并行”的力量：四核驱动，吞吐量翻倍

理解了“统一”，再看“并行”就简单了。既然一个BFU能高效工作，那我们就把多个BFU堆起来一起算。我们选择了集成四个并行的BFU。为什么是四个？这是一个经过权衡的折中点。

对于一个256点（n=256）的NTT，每一级（stage）需要计算128个蝴蝶操作。如果只有一个BFU，那就要串行计算128次。如果我们有P个并行BFU，那么每级所需的时钟周期数就是(n/2) / P = 128 / P。

P=1: 每级128周期，总延迟太长。
P=8或16: 每级周期数少（16或8），速度极快，但需要实例化8或16个BFU以及配套的存储器端口，面积和布线复杂度会急剧上升，可能成为频率瓶颈。
P=4: 每级需要128 / 4 = 32个周期。这是一个非常均衡的点：它显著提升了速度（是单核的4倍），而四个BFU及其控制逻辑在目标FPGA（Virtex-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_q（q=3329）里，加减法后结果可能超出范围 [0, q-1]。模加器在相加后，判断结果是否大于等于q，如果是则减去q。模减器在相减后，判断结果是否为负，如果是则加上q。这些比较和条件操作通过组合逻辑实现，延迟很小。
模乘与Barrett约减：这是最复杂的部分。两个12比特的数（系数和旋转因子）相乘，得到一个24比特的中间乘积。我们需要将它模约减回12比特。直接做除法在硬件中非常昂贵。我们采用了经过移位-加法优化的Barrett约减算法。

Barrett约减的核心思想是用乘法和移位来近似代替除法。对于固定的模数q，我们可以预计算一个常数μ = floor(2^(2k) / q)，其中k = ceil(log2(q))（对于q=3329, k=12）。约减公式大致为：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 旋转因子地址生成器（TAG）

NTT计算需要用到预先计算好的旋转因子（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 3（s=3），公式变为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都用分布式RAM（LUTRAM）实现，这得益于我们紧凑的存储设计。
时序性能：最高运行频率达到166 MHz。完成一次NTT需要235个周期，一次INTT需要235个周期，一对完整的NTT+INTT需要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。

性能对比（表6）：

vs. Unif-NTT [25]：该设计也强调统一架构，但在Virtex-7上完成NTT+INTT需要约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-ATP（1.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%的功能覆盖是底线。