initial_vectorized_ntt_hls_configuration 模块深度解析

一句话概括

这个模块是 CRYSTALS-Kyber 后量子密码算法中多项式向量 NTT（数论变换）的 Vitis HLS 优化版本，它通过手动展开嵌套循环来暴露算法内部的并行性，为后续的 DATAFLOW 优化奠定基础。你可以把它想象成一条原本串行工作的流水线——Version0 是"一个人干所有活"，而 Version1 则是把一个人的工作拆成了七个独立工位，虽然这些工位目前还是串行执行，但已经为后续的真正并行化铺平了道路。

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

背景：后量子密码学的性能挑战

CRYSTALS-Kyber 是 NIST 标准化的后量子公钥加密算法，其核心计算依赖于多项式向量的数论变换（NTT）。与 RSA 依赖大整数质因数分解不同，Kyber 的安全性建立在格（Lattice）问题上——具体来说，是求解多项式向量方程组的困难性。

NTT 本质上是 FFT 在有限域上的变体，它将时域的多项式乘法转换为频域的点乘，将 \(O(n^2)\) 的复杂度降为 \(O(n \log n)\)。然而，对于资源受限的嵌入式系统或需要高吞吐量的场景，纯软件实现的 NTT 仍然太慢。

Version0 的瓶颈

baseline_ntt_hls_configuration（Version0）是直接移植自 Kyber 参考实现的 C 代码，其 ntt() 函数采用三层嵌套循环结构：

// Version0 的结构
ntt_stage_outer:for(len = K; len >= 2; len >>= 1) {      // 外层：7个阶段
    for(start = 0; start < 256; start = j + len) {       // 中层
        zeta = zetas[k++];
        for(j = start; j < start + len; j++) {           // 内层
            #pragma HLS PIPELINE
            // 蝶形运算
        }
    }
}

HLS Code Analyzer 的分析结果显示：

问题在于：HLS 工具无法自动展开动态变化的循环边界。外层循环的迭代次数从 128 递减到 2，每次迭代的 len 值不同，这导致 HLS 只能生成一个单一的硬件单元顺序执行 7 个阶段，无法利用阶段间的独立性进行并行化。

Version1 的设计洞察

Version1 的核心洞察是：NTT 的 7 个计算阶段在逻辑上是独立的——每个阶段只读取前一阶段的输出，没有跨阶段的反向数据依赖。如果我们手动展开外层循环，HLS 就能识别出这 7 个独立的计算单元，即使它们目前仍是顺序执行，也为后续引入 DATAFLOW 任务级并行创造了条件。

架构与数据流

整体架构图

关键组件详解

1. polyvec_ntt(polyvec *v) —— 批量处理入口

这是整个模块的顶层函数，负责遍历包含 128 个多项式的向量，对每个多项式调用 poly_ntt。

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

设计考量：

• 使用 unsigned int 作为循环变量，避免有符号整数的潜在溢出问题
• 循环标签 polyvec_ntt_loop 便于 HLS 报告和调试时识别
• 当前实现是顺序执行的，每个多项式的 NTT 完成后才开始下一个

2. poly_ntt(poly *a) —— 单项式包装器

简单的转发函数，将 poly 结构体中的系数数组传递给核心 ntt 函数。

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

注意：在 Version1 中，ntt 函数直接就地修改输入数组（in-place）。这种设计虽然节省内存，但也意味着输入数据在计算过程中被破坏，限制了数据重排和流水线优化的可能性。intermediate_optimized_ntt_hls_configuration（Version2）会解决这个问题。

3. ntt(uint16_t p[N]) —— 核心计算引擎

这是本模块的核心，实现了 7 阶段的 Cooley-Tukey 风格 NTT 算法。

阶段展开策略：

每个阶段的代码模式相同：

ntt_stageN: for(start = 0; start < N; start = j + len) {
    int16_t zeta = zetas[k++];  // 从预计算的旋转因子表读取
    ntt_stageNi: for(j = start; j < start + len; j++) {
        #pragma HLS PIPELINE   // 关键：内层循环流水线化
        int16_t t = fqmul(zeta, p[j + len]);  // 旋转因子乘法
        p[j + len] = p[j] - t;   // 蝶形运算：减法分支
        p[j] = p[j] + t;         // 蝶形运算：加法分支
    }
}

4. fqmul 与 montgomery_reduce —— 模运算核心

有限域乘法是 NTT 中最频繁的操作。为了避免昂贵的除法运算，实现采用了蒙哥马利约减（Montgomery Reduction）：

int16_t montgomery_reduce(int32_t a) {
#pragma HLS INLINE
    int16_t t1, t2;
    t1 = (int16_t)a*QINV;                    // 低 16 位乘以 Q 的模逆
    t2 = (a - (int32_t)t1*Q) >> 16;          // 消除低 16 位，保留高位
    return t2;
}

int16_t fqmul(int16_t a, int16_t b) {
#pragma HLS INLINE
    return montgomery_reduce((int32_t)a*b);  // 先扩展为 32 位再相乘
}

数学原理：

• \(Q = 3329\)（Kyber 选择的素数）
• \(QINV = -3327 \equiv Q^{-1} \pmod{2^{16}}\)（Q 对 \(2^{16}\) 的模逆元）
• 蒙哥马利约减将 \(a \cdot b \mod Q\) 的计算转化为移位和乘法，避免了除法

#pragma HLS INLINE 确保这两个函数被完全内联，消除函数调用开销，使流水线能够连续执行。

数据依赖与内存访问模式

关键问题：数组 p 的竞争访问

Version1 虽然展开了外层循环，但所有 7 个阶段仍然共享同一个数组 p：

void ntt(uint16_t p[N]) {  // 单一数组，读写混合
    // Stage 1: 读 p[], 写 p[]
    // Stage 2: 读 p[], 写 p[]
    // ...
}

这导致了**读后写（RAW）、写后读（WAR）、写后写（WAW）**三种数据依赖。HLS Code Analyzer 会显示大量的通道依赖边，表明这些阶段不能自由并行执行。

性能对比

解读：

• polyvec_ntt 的 TI 从 51.5M 降到 804K，提升了约 64 倍
• 这一巨大提升来自于 HLS 能够更好地调度展开后的循环结构
• 但 ntt 函数的 TI 仍有 6281 周期，因为阶段间依赖仍然存在

设计决策与权衡

1. 手动循环展开 vs. #pragma HLS UNROLL

选择：手动展开 7 个阶段

原因：

• 原始循环的边界 len 是动态变化的（128→64→32→...），UNROLL pragma 对这种模式效果有限
• 手动展开使代码结构显式化，便于 HLS 分析和后续优化
• 为下一阶段（Version2/3）引入 DATAFLOW 创造条件

代价：

• 代码量增加，维护成本上升
• 如果 NTT 点数改变（如从 256 改为 512），需要重新手动展开

2. In-Place 计算 vs. Ping-Pong 缓冲

选择：继续使用 in-place 计算（p[N] 就地修改）

原因：

• Version1 的主要目标是验证循环展开的收益
• 保持与 Version0 相同的接口，便于对比分析

局限：

• 这是 Version1 的关键瓶颈，也是 intermediate_optimized_ntt_hls_configuration（Version2）要解决的核心问题
• In-place 访问模式阻止了 DATAFLOW 优化，因为 HLS 无法确定读写依赖关系

3. 定点数表示 vs. 浮点数

选择：16 位定点整数（uint16_t/int16_t）

原因：

• Kyber 算法定义在有限域 \(\mathbb{Z}_Q\) 上，\(Q=3329\) 可以用 12 位表示
• FPGA DSP48 单元擅长定点乘法，比浮点更高效
• 蒙哥马利约减需要精确的整数运算

4. 旋转因子表的存储

const int16_t zetas[K] = { -1044, -758, ... };

设计：

• 使用 const 修饰，提示编译器这是只读数据
• 存储在片外 DRAM，但通过缓存机制访问
• 128 个 16 位值 = 256 字节，可以放入片上 BRAM

配置与构建

HLS 配置文件 (hls_config.cfg)

part=xcvp1202-vsva2785-1LP-i-L

[hls]
flow_target=vivado
package.output.format=ip_catalog
package.output.syn=false
tb.file=polyvec_tb.cpp
syn.file=polyvec.cpp
syn.file=polyvec.h
syn.top=polyvec_ntt
csim.code_analyzer=1
csim.clean=true

关键配置项：

测试平台 (polyvec_tb.cpp)

测试台包含两个 Golden Reference 多项式（a_golden 和 b_golden），用于验证 NTT 结果的正确性。测试流程：

1. 构造输入多项式 a（线性递增）和 b（比特反转排列）
2. 调用 polyvec_ntt(&v) 执行变换
3. 逐元素比对输出与 golden reference
4. 任何不匹配都会导致测试返回非零错误码

演进路径

Version1 是整个优化链条中的中间环节，理解它的位置有助于把握整体演进逻辑：

Version0 (Baseline)
    │
    ├── 问题：三层嵌套循环，HLS 无法自动并行化
    │
    ▼
Version1 (Current - 初始向量化)
    │
    ├── 改进：手动展开外层循环，暴露 7 个独立阶段
    ├── 遗留问题：仍共享同一数组 p[]，存在数据依赖
    │
    ▼
[intermediate_optimized_ntt_hls_configuration](Vitis_HLS-Design_Tutorials-01-Polynomial_Vectorization-workspace-Version2-hls_config-cfg-polyvec_ntt.md) (Version2)
    │
    ├── 改进：引入 ping-pong 缓冲区（p_stage1~p_stage6）
    ├── 效果：消除阶段间依赖，为 DATAFLOW 做准备
    │
    ▼
[final_ntt_vectorization_hls_configuration](Vitis_HLS-Design_Tutorials-01-Polynomial_Vectorization-workspace-Version3-hls_config-cfg-polyvec_ntt.md) (Version3)
    │
    ├── 改进：添加 #pragma HLS DATAFLOW
    ├── 改进：使用模板函数封装各阶段
    └── 效果：实现真正的任务级并行（TLP）

新贡献者注意事项

1. 隐式契约与前置条件

• 数组对齐：p[N] 数组必须至少 2 字节对齐（uint16_t 的自然对齐）
• 数值范围：输入系数必须在 \([0, Q-1]\) 范围内，即 \([0, 3328]\)，否则蒙哥马利约减结果未定义
• 常量假设：N=256、K=128、Q=3329 是编译时常量，修改它们需要同步更新所有相关代码

2. 常见陷阱

陷阱 1：忽略整数溢出

// 危险：int16_t * int16_t 可能溢出
int16_t bad_mul(int16_t a, int16_t b) {
    return (a * b) % Q;  // 溢出后再取模，结果错误！
}

// 正确：先扩展到 32 位
int16_t good_mul(int16_t a, int16_t b) {
    return montgomery_reduce((int32_t)a * b);
}

陷阱 2：混淆 NTT 与 FFT

• NTT 使用旋转因子 \(\omega^k \mod Q\)，不是复数单位根 \(e^{-2\pi i k/N}\)
• 旋转因子表 zetas 是预计算的，不要尝试用 cos/sin 动态生成

陷阱 3：流水线 II 不达预期

• 如果观察到 Initiation Interval > 1，检查是否有内存端口竞争
• 可能需要添加 #pragma HLS ARRAY_PARTITION 来增加内存端口数

3. 调试技巧

• 使用 HLS Code Analyzer：重点关注 Channels 视图中 p[*] 的依赖边
• 对比 Version0/1/2：三个版本的差异展示了渐进式优化的过程
• 检查综合报告：查看 "Loop Iteration Latency" 和 "Resource Utilization" 部分

4. 扩展方向

如果需要修改本模块，常见的扩展点包括：

• 支持不同的 NTT 点数：修改 N 并相应调整阶段数和 zetas 表
• 引入 SIMD 优化：在 fqmul 中使用更宽的数据类型进行向量运算
• 添加 AXI 接口：将 polyvec_ntt 包装为 AXI Stream 接口的 HLS IP

参考链接

• 父模块：polynomial_vectorization_ntt_versions —— 完整教程概览
• 前序版本：baseline_ntt_hls_configuration —— 基线实现
• 后续版本：intermediate_optimized_ntt_hls_configuration —— 消除数据依赖
• 最终版本：final_ntt_vectorization_hls_configuration —— DATAFLOW 优化