🏠

baseline_ntt_hls_configuration 模块深度解析

一句话概括

这是后量子密码学 CRYSTALS-Kyber 算法中多项式向量 NTT（数论变换）的基线硬件实现。它代表了"未经优化的原始 C 代码直接综合成 RTL"的状态——性能很差，但功能正确，是整个优化教程的起点和参照物。

想象你手里有一份从 GitHub 下载的开源 Kyber 参考代码，它能在 CPU 上正确运行，但你希望把它放到 FPGA 上加速。这个模块就是那份代码几乎原封不动地丢进 Vitis HLS 后的结果。它的价值不在于性能，而在于告诉你：如果不做任何优化，HLS 会生成什么样的硬件？

问题空间：为什么需要这个模块？

后量子密码学的计算挑战

传统的 RSA 加密依赖大整数分解的困难性，但量子计算机可以用 Shor 算法在多项式时间内破解它。NIST 标准化的 CRYSTALS-Kyber 算法转而依赖多项式向量分解的困难性——这在量子计算机上仍然是难题。

Kyber 的核心运算是多项式乘法。对于次数为 \(N=256\) 的多项式，直接乘法的复杂度是 \(O(N^2)\)。NTT（Number Theoretic Transform，数论变换）将多项式乘法转化为点乘，复杂度降至 \(O(N \log N)\)，类似于 FFT 在信号处理中的作用。

为什么需要硬件加速？

NTT 涉及大量的模乘、蝶形运算和数据重排。虽然现代 CPU 可以执行这些运算，但在高吞吐量的加密场景（如 TLS 握手、VPN 网关）中，纯软件实现的延迟和功耗都难以接受。FPGA 的 DSP Slice 特别适合这种规则的向量运算，但需要将算法映射到硬件友好的形式。

"基线版本"的设计意图

这个模块的存在是为了回答一个问题：如果我们什么都不做，直接把参考 C 代码综合成硬件，会得到什么？

答案是：一个功能正确但性能极差的实现。它的 Transaction Interval (TI) 高达 5150 万时钟周期，意味着处理一个多项式向量需要极长时间。这并非设计缺陷，而是刻意为之——它为后续的优化版本提供了可量化的改进基准。

核心抽象与数据结构

多项式的表示

// polyvec.h
#define N 256    // 每个多项式的系数个数
#define K 128    // zetas 数组大小（旋转因子表）
#define Q 3329   // 模数：所有运算在此素数模下进行
#define QINV -3327  // Q 的模逆元，用于 Montgomery 约减

typedef struct {
    uint16_t coeff[N];  // 256 个 16 位无符号整数
} poly;

typedef struct {
    poly vec[K];  // K 个多项式组成的向量
} polyvec;

这里的 poly 结构体代表一个 \(256\) 次多项式，系数存储在 uint16_t 数组中。选择 \(Q = 3329\) 是因为它是 Kyber 标准参数，满足 \(Q \equiv 1 \pmod{2N}\)，使得 \(N\) 点 NTT 存在。

函数层级结构

polyvec_ntt(polyvec *v)      // 顶层入口：处理 K 个多项式
    └── poly_ntt(poly *a)    // 单个多项式的 NTT
            └── ntt(uint16_t p[N])  // 核心蝶形运算
                    ├── montgomery_reduce()  // 模约减
                    └── fqmul()              // 模乘法

这种三层结构反映了算法的自然分解：

  • polyvec_ntt：批处理层，遍历多项式向量
  • poly_ntt：调度层，将多项式系数传递给核心算法
  • ntt：计算层，执行 in-place 的 Cooley-Tukey 蝶形网络

数据流分析：一次完整的 NTT 计算

让我们追踪一个多项式从输入到输出的完整旅程：

阶段 1：测试台准备数据 (polyvec_tb.cpp)

// 初始化测试数据
for (int i = 0; i < N; i++)
    a.coeff[i] = i;  // 简单递增序列作为输入

// 构造多项式向量
polyvec v;
v.vec[0] = a;
v.vec[1] = b;

测试台创建两个多项式，填充测试数据，然后打包成 polyvec 结构。

阶段 2：顶层调用 (polyvec_ntt)

void polyvec_ntt(polyvec *v) {
    polyvec_ntt_loop:for( unsigned int i = 0; i < K; ++i)
        poly_ntt(v->vec+i);
}

这里 K 被定义为 128，但实际循环只执行两次（因为测试台只初始化了 v.vec[0] 和 v.vec[1]）。这是一个潜在的 bug——如果 polyvec 包含超过 2 个多项式，未初始化的内存会被当作有效输入。

阶段 3：单层 NTT 调度 (poly_ntt)

void poly_ntt(poly *a) {
    ntt(a->coeff);
}

纯粹的透传函数，将 poly 结构解包为裸数组指针。

阶段 4：核心蝶形运算 (ntt)

这是整个模块的计算核心：

void ntt(uint16_t p[N]) {
    #pragma HLS INLINE OFF  // 关键：禁止内联，保持函数边界
    
    k = 1;
    ntt_stage_outer:for(len = K; len >= 2; len >>= 1) {  // 外层：log2(N) 个阶段
        ntt_stage_loop:for(start = 0; start < 256; start = j + len) {  // 中层：每阶段的蝴蝶组
            zeta = zetas[k++];  // 读取旋转因子
            ntt_stage_inner:for(j = start; j < start + len; j++) {  // 内层：每组内的蝶形运算
                #pragma HLS PIPELINE  // 尝试流水线化内层循环
                t = fqmul(zeta, p[j + len]);  // 模乘：旋转因子 × 远端系数
                p[j + len] = p[j] - t;        // 蝶形下支
                p[j] = p[j] + t;              // 蝶形上支
            }
        }
    }
}

蝶形运算的数学本质

标准的 Cooley-Tukey 蝶形运算为：

\[ \begin{aligned} Y_0 &= X_0 + \omega \cdot X_1 \\ Y_1 &= X_0 - \omega \cdot X_1 \end{aligned} \]

其中 \(\omega\) 是单位根（这里是 zeta），所有运算在模 \(Q\) 下进行。

Montgomery 约减

由于频繁取模运算代价高昂，实现采用了 Montgomery 约减：

int16_t montgomery_reduce(int32_t a) {
    #pragma HLS INLINE
    int16_t t1 = (int16_t)a * QINV;           // 低 16 位 × QINV
    int32_t t2 = a - (int32_t)t1 * Q;         // 消除低 16 位
    return t2 >> 16;                          // 右移得到约减结果
}

这是一种不需要除法的模约减技术，利用 \(Q^{-1} \pmod{2^{16}}\) 的性质，通过乘法和移位实现。

阶段 5：结果验证 (polyvec_tb.cpp)

for (int i = 0; i < N; i++) {
    if(a_golden[i] != v.vec[0].coeff[i]) {
        printf("mismatch on a[%d]...", i);
        return 1;
    }
}

测试台将输出与预计算的 golden reference 比较，任何不匹配都会导致测试失败。

HLS 配置解读 (hls_config.cfg)

part=xcvp1202-vsva2785-1LP-i-L  # Versal Premium 器件

[hls]
flow_target=vivado              # 生成 Vivado IP
package.output.format=ip_catalog # 输出格式：IP Catalog
package.output.syn=false        # 不进行综合（仅导出 RTL）
tb.file=polyvec_tb.cpp          # 测试台文件
syn.file=polyvec.cpp            # 源文件
syn.file=polyvec.h
syn.top=polyvec_ntt             # 顶层函数
csim.code_analyzer=0            # 禁用 Code Analyzer（后续版本启用）
csim.clean=true                 # 每次清理仿真环境

关键设计决策

  1. csim.code_analyzer=0：基线版本有意禁用 Code Analyzer。这是为了展示"传统"的 HLS 流程——先跑通功能，再逐步启用分析工具进行优化。

  2. package.output.syn=false：只导出 RTL，不自动进行综合。这让开发者可以在 Vivado 中手动控制综合策略，或者与其他模块集成后再统一综合。

  3. #pragma HLS INLINE OFF 在 ntt 函数中：这是一个关键的性能反模式。禁止内联意味着 HLS 会为 ntt 生成独立的硬件模块，每次调用都需要通过端口传递 256 个系数。考虑到 polyvec_ntt 循环调用 poly_ntt 128 次（理论上），这将产生巨大的数据传输开销。

架构角色与依赖关系

在模块树中的位置

polynomial_vectorization_ntt_versions (父模块)
├── baseline_ntt_hls_configuration (本模块 - Version0)
├── initial_vectorized_ntt_hls_configuration (Version1)
├── intermediate_optimized_ntt_hls_configuration (Version2)
└── final_ntt_vectorization_hls_configuration (Version3)

本模块是优化链条的起点。后续版本通过以下方式逐步改进：

  • Version1：手动展开外层循环，暴露更多并行性
  • Version2：分离输入/输出缓冲区，消除数据依赖
  • Version3：应用 DATAFLOW pragma，实现任务级并行

外部依赖

本模块依赖于 AI_Engine_Development.AIE.Design_Tutorials.02-super_sampling_rate_fir.DualSSR16_hw.sw.Makefile.aie_control_xrt.cpp 等组件提供的运行时支持，但这些主要是构建系统层面的依赖，不影响核心算法的理解。

设计权衡与陷阱

1. 内存访问模式：in-place 更新的代价

void ntt(uint16_t p[N]) {
    // ...
    p[j + len] = p[j] - t;  // 写入
    p[j] = p[j] + t;        // 读取刚才写入的位置？不，是另一个索引
}

虽然是 in-place 算法，但每次迭代同时读写数组 p。在 HLS 中，这会产生读后写（RAW）依赖，阻止流水线达到 II=1。Code Analyzer 显示这个版本的 TI 高达 402k 周期，主要原因就是这种内存竞争。

2. 循环结构的隐含假设

ntt_stage_outer:for(len = K; len >= 2; len >>= 1)

这里 K=128，所以循环执行 7 次（128→64→32→16→8→4→2）。但如果有人修改了 K 的定义，却没有同步更新其他地方的硬编码假设（如测试台的 golden reference），会导致静默的错误行为。

3. 数据类型的微妙之处

int16_t montgomery_reduce(int32_t a)  // 返回有符号 16 位
// ...
uint16_t p[N];  // 数组是无符号的
// ...
p[j + len] = p[j] - t;  // 无符号 = 无符号 - 有符号？

p 是 uint16_t，但 t 是 int16_t。C 语言的隐式类型转换规则会让 p[j] 提升为有符号整数进行减法，然后再转换回无符号存储。在模运算的上下文中，这种转换是安全的（因为结果保证在 \([0, Q)\) 范围内），但对阅读代码的人来说是一个认知负担。

4. 测试覆盖的局限性

测试台只验证了 polyvec 的前两个元素（索引 0 和 1），但 polyvec_ntt 的循环上限是 K=128。这意味着如果有人在实际使用中使用完整的 128 个多项式，这个基线版本从未被测试过。

性能特征（基于 README 数据）

指标 Version0 (本模块) Version1 Version2 Version3
polyvec_ntt TI 51.5M 周期 804k 周期 230k 周期 ~?
ntt TI 402k 周期 6281 周期 1540 周期 ~?
相对加速比 1× ~64× ~224× >1000×

TI = Transaction Interval，完成一次完整事务所需的时钟周期数

Version0 的性能瓶颈主要来自：

  1. 顺序执行：三重嵌套循环完全串行化
  2. 内存竞争：所有阶段共享同一个 p[] 数组
  3. 函数调用开销：INLINE OFF 导致的数据传输

给新贡献者的建议

如果你要修改这个模块...

  1. 永远不要直接修改 Version0：它是基线参照物。如果要实验优化，复制到新的 Version 目录。

  2. 理解 #pragma HLS INLINE OFF 的影响：在 ntt 函数中，这个 pragma 强制 HLS 保持函数边界。移除它可能让 HLS 将逻辑内联到调用者，减少调用开销，但也可能导致代码膨胀。

  3. 注意 K 的双重含义：在 polyvec.h 中 K=128 是 zetas 数组的大小；在 ntt 函数中，它也是外层循环的起始长度。这两个语义恰好一致，但如果修改必须同步更新。

  4. Montgomery 约减的正确性：QINV = -3327 是 \(Q^{-1} \pmod{2^{16}}\) 的补码表示。不要试图"简化"这个常数，它与 montgomery_reduce 的实现是耦合的。

常见的调试场景

问题：C Simulation 通过，但 C Synthesis 后的 RTL 仿真失败

检查是否违反了 HLS 的约束：

  • 数组 p 是否被同时读写导致依赖？
  • 循环边界是否为编译时常量？（HLS 需要静态分析）
  • 是否有未初始化的变量被使用？（C 仿真可能侥幸通过）

问题：综合后的资源利用率异常高

Version0 不应该有高资源消耗，因为它几乎没有并行化。如果出现这种情况，检查：

  • 是否意外展开了某个大循环？
  • 数组是否被错误地分区（partition）导致 BRAM 爆炸？

延伸阅读

总结

baseline_ntt_hls_configuration 是一个教学用的反例。它展示了当 C 代码未经硬件优化意识改写时，HLS 工具能生成的最差（但仍正确）的硬件实现。它的价值在于：

  1. 功能验证：确保算法在移植到 FPGA 前逻辑正确
  2. 性能基准：为后续优化提供量化的改进目标
  3. 教育意义：让开发者直观感受"软件思维"和"硬件思维"的差异

当你看到 5150 万周期的 TI 时，不要惊慌——这正是设计意图。真正的学习从这里开始：观察 Version1/2/3 如何一步步将这个数值降到几千甚至几百周期，理解每一次代码改写在硬件层面产生了什么影响。

On this page