🏠

final_ntt_vectorization_hls_configuration 模块深度解析

概述：这个模块解决了什么问题？

想象你正在设计一条高速公路。最初的方案（Version0）是一条单车道乡间小路——车辆必须一辆接一辆地通过，任何一辆车抛锚都会堵住整条路。这就是传统 CPU 上运行 NTT（Number Theoretic Transform，数论变换）算法的现状：虽然代码简洁优雅，但在 FPGA 这种天生并行化的硬件上，它就像让法拉利在拥堵的早高峰中爬行。

final_ntt_vectorization_hls_configuration（即 Version3）是这条高速公路的最终形态：七条并行车道，每辆车（数据块）在不同的车道上以流水线方式前进，彼此互不干扰。这个模块实现了 CRYSTALS-Kyber 后量子加密算法中的核心 NTT 运算，通过 Vitis HLS 的 DATAFLOW 优化将任务级并行（Task Level Parallelism, TLP）发挥到极致。

问题的本质在于：NTT 算法天然包含多个计算阶段（stage），每个阶段需要等待前一阶段完全结束后才能开始。在软件实现中，这表现为顺序执行的循环嵌套；而在硬件实现中，这意味着巨大的时间浪费——当 Stage 2 在等待 Stage 1 的数据时，Stage 1 的计算单元却处于空闲状态。Version3 的设计洞察是：将每个 stage 封装为独立的硬件模块，通过乒乓缓冲区（PIPO, Ping-Pong Buffer）连接，使得七个 stage 可以同时处理七个不同的数据块，从而实现近七倍的吞吐量提升。

架构与数据流

整体架构图

flowchart LR subgraph "polyvec_ntt - 顶层调度" A[polyvec
输入向量] --> B["polyvec_ntt_loop
(#pragma HLS DATAFLOW)"] B --> C[polyvec
输出向量] end subgraph "ntt - 7级流水线" D[p_in
输入数组] --> S0["ntt_stage<0>
len=128"] S0 -->|p_stage1| S1["ntt_stage<1>
len=64"] S1 -->|p_stage2| S2["ntt_stage<2>
len=32"] S2 -->|p_stage3| S3["ntt_stage<3>
len=16"] S3 -->|p_stage4| S4["ntt_stage<4>
len=8"] S4 -->|p_stage5| S5["ntt_stage<5>
len=4"] S5 -->|p_stage6| S6["ntt_stage<6>
len=2"] S6 --> E[p_out
输出数组] end B -.->|调用| D E -.->|返回| B

核心组件详解

1. polyvec_ntt - 顶层向量化调度器

void polyvec_ntt(polyvec *vin, polyvec *vout) {
    polyvec_ntt_loop:for( unsigned int i = 0; i < K; ++i) {
        #pragma HLS DATAFLOW
        poly_ntt(vin->vec+i, vout->vec+i);
    }
}

设计意图：这是整个系统的"交通指挥中心"。polyvec 结构包含 K=128 个多项式（poly），每个多项式有 N=256 个系数。外层循环遍历这 128 个多项式，对每个多项式执行 NTT 变换。

关键设计决策：

  • 分离输入输出：vin 和 vout 是两个独立的指针，避免了原地修改带来的数据依赖。这类似于餐厅的后厨和前台——厨师（NTT 计算）专心处理订单，服务员（数据传输）负责将成品送到顾客手中，两者可以并行工作。
  • #pragma HLS DATAFLOW：这是性能飞跃的关键。没有这个 pragma，循环会等待 poly_ntt 完全结束才开始下一次迭代；有了这个 pragma，HLS 工具会将循环体转换为数据流区域，允许在前一个多项式的 NTT 还在进行时，就开始下一个多项式的处理。

内存所有权模型：

  • vin 和 vout 由调用者分配和拥有
  • 函数内部不分配动态内存，所有中间缓冲区都在 ntt() 函数的栈上声明
  • 这是一个"借用"语义：函数承诺在返回前完成对所有输入数据的读取，但不会释放或转移所有权

2. ntt - 七级流水线核心

void ntt(uint16_t p_in[N], uint16_t p_out[N]) { 
    uint16_t p_stage1[N];
    uint16_t p_stage2[N];
    // ... p_stage3 到 p_stage6
#pragma HLS DATAFLOW
    ntt_stage<0>(p_in,     p_stage1);
    ntt_stage<1>(p_stage1, p_stage2);
    // ... 依此类推
    ntt_stage<6>(p_stage6, p_out  );
}

设计意图：这是算法的"心脏"，也是 Version3 相比之前版本最大的改进之处。回想一下工厂流水线的比喻：Version0 像是一个工匠从头到尾制作一把椅子；Version3 则像福特汽车的流水线——七个工位同时工作，每个工位只负责一道工序。

关键设计决策：

  • 显式中间缓冲区：p_stage1 到 p_stage6 六个数组构成了 stage 之间的数据通道。这消除了 Version1 中所有 stage 竞争访问同一个数组 p 的问题。
  • DATAFLOW 区域：#pragma HLS DATAFLOW 告诉 HLS 工具：这七个函数调用可以并发执行。实际生成的硬件会包含七个独立的计算模块，通过 FIFO 或 PIPO 缓冲区连接。

资源权衡：

  • BRAM 开销：六个中间数组每个占用 256 × 16bit = 512 bytes，总计约 3KB 的片上存储。这是用空间换时间的经典案例。
  • DSP 利用率：每个 stage 内部的蝴蝶运算（butterfly operation）需要乘法器，七个 stage 并行意味着最多同时需要 7×2=14 个乘法器（每个蝴蝶运算包含一次复数乘法）。

3. ntt_stage<stage> - 模板化的计算单元

template <int stage>
void ntt_stage(uint16_t p_in[N], uint16_t p_out[N]){
    unsigned int start=0, j=0;
    unsigned int len = K >> stage;   // 128, 64, 32, 16, 8, 4, 2
    unsigned int k = 1 << stage;     // 1, 2, 4, 8, 16, 32, 64

    ntt_stage_loop1: for(start = 0; start < N; start = j + len) {
        int16_t zeta = zetas[k]; k++;
        ntt_stage_loop2: for(j = start; j < start + len; j++) {
            #pragma HLS PIPELINE
            int16_t t = fqmul(zeta, p_in[j + len]);
            p_out[j + len] = p_in[j] - t;
            p_out[j] = p_in[j] + t;
        }
    }
}

设计意图：使用 C++ 模板参数 stage 来生成七个不同的硬件模块。这就像是同一个机床模具，通过调整参数生产出七种不同规格的零件。

模板参数的魔力：

  • len = K >> stage：随着 stage 增加，蝴蝶运算的步长减半。Stage 0 处理距离为 128 的系数对，Stage 6 处理距离为 2 的系数对。
  • k = 1 << stage：旋转因子（twiddle factor）在 zetas 数组中的起始索引。每个 stage 需要不同数量的旋转因子。

PIPELINE 指令：

  • #pragma HLS PIPELINE 应用于最内层循环，确保每次迭代在一个时钟周期内完成（II=1）。
  • 这是细粒度的指令级并行，与 DATAFLOW 的粗粒度任务级并行形成互补。

4. fqmul 与 montgomery_reduce - 模乘运算核心

int16_t fqmul(int16_t a, int16_t b) {
#pragma HLS INLINE
    return montgomery_reduce((int32_t)a*b);
}

int16_t montgomery_reduce(int32_t a) {
#pragma HLS INLINE
    int16_t t1, t2;
    t1 = (int16_t)a*QINV;           // QINV = -3327 (mod 2^16)
    t2 = (a - (int32_t)t1*Q) >> 16; // Q = 3329
    return t2;
}

设计意图：Montgomery 约减是后量子密码学中的标准技巧，用于高效计算 \(a \cdot b \mod q\) 而无需昂贵的除法运算。

数学原理简述： Montgomery 约减利用预计算的常数 \(q^{-1} \mod 2^{16}\)（即 QINV），通过一系列乘法和移位操作，将结果归约到模 \(q=3329\) 的范围内。对于熟悉数论的读者，这等价于：

\[t = a \cdot q^{-1} \mod 2^{16}\]
\[result = (a - t \cdot q) / 2^{16}\]

INLINE 策略： 两个函数都标记为 #pragma HLS INLINE，意味着它们的逻辑会被直接展开到调用点。这消除了函数调用的开销，允许 HLS 工具更好地优化数据通路。

数据流追踪：一个多项式的旅程

让我们跟踪一个多项式从输入到输出的完整路径，理解 DATAFLOW 如何创造奇迹：

时间线视角（假设每个 stage 的 II=100 周期，latency=200 周期）

时间周期 Stage 0 Stage 1 Stage 2 ... 说明
0-199 Poly[0] 空闲 空闲 ... 第一个多项式进入 Stage 0
100-299 Poly[1] Poly[0] 空闲 ... Poly[0] 完成 Stage 0，进入 Stage 1；Poly[1] 进入 Stage 0
200-399 Poly[2] Poly[1] Poly[0] ... 三个多项式同时在流水线中
... ... ... ... ... ...
600+ Poly[6] Poly[5] Poly[4] ... 七个 stage 全部满载

关键洞察：在没有 DATAFLOW 的情况下，处理 128 个多项式需要 \(128 \times 7 \times 200 = 179200\) 周期。有了 DATAFLOW，一旦流水线填满，每 100 周期就能完成一个多项式，总时间约为 \(7 \times 200 + 127 \times 100 = 14000\) 周期。约 12 倍的加速比！

实际性能数据（来自 README）

版本 polyvec_ntt 延迟 ntt 延迟 关键优化
Version0 51.5M 周期 402K 周期 基线，无优化
Version1 804K 周期 6281 周期 手动展开外层循环
Version2 230K 周期 1540 周期 消除数组依赖
Version3 199K 周期 1552 周期 DATAFLOW + 函数模板

Version3 的 ntt 延迟（1552 周期）与 Version2（1540 周期）相近，但 polyvec_ntt 的整体延迟从 230K 降至 199K，这正是 DATAFLOW 在顶层循环中发挥作用的体现。

设计决策与权衡

1. 为什么使用模板而不是函数指针或虚函数？

选择的方案：C++ 模板参数 template <int stage>

替代方案：运行时参数 void ntt_stage(int stage, ...) 或函数指针数组

权衡分析：

  • 模板的优势：每个 stage 值会在编译时实例化为独立的函数，HLS 工具会为每个实例生成独立的硬件模块。这七个模块可以真正并行执行，各自有自己的 DSP、BRAM 和控制逻辑。
  • 运行时参数的缺点：如果 stage 是运行时变量，HLS 只能生成一个通用的计算单元，通过多路选择器（MUX）切换不同 stage 的行为。这会导致资源共享冲突，无法充分利用 DATAFLOW 的并行性。
  • 代价：代码体积略有增加（七个函数实例 vs 一个），但在 FPGA 的可编程逻辑中，这是完全可以接受的 trade-off。

2. 为什么需要显式的中间数组？

Version1 的问题：所有 stage 共享同一个数组 p，导致严重的读写依赖。

// Version1 - 问题代码
void ntt(uint16_t p[N]) {
    // Stage 1 写入 p
    // Stage 2 读取 p（依赖于 Stage 1 的写入）
    // ...
}

Version3 的解决方案：每个 stage 有独立的输入和输出数组。

权衡分析：

  • 优势：消除了虚假依赖（false dependency），HLS 可以自由调度各个 stage 的执行。
  • 代价：额外的 BRAM 资源（约 3KB）。在 Versal Premium 器件上，这点开销微不足道。
  • 深层原因：这是数据流架构的核心原则——通过复制数据解除时间上的耦合，换取空间上的并行。

3. 为什么 polyvec_ntt 也需要 DATAFLOW？

初看之下，ntt 函数内部已经有了 DATAFLOW，polyvec_ntt 只是简单地循环调用它。为什么还要在外层也加 DATAFLOW？

答案：这是**嵌套数据流（Nested Dataflow）**的经典模式。

想象一下餐厅厨房：ntt 是厨房里的一条流水线（洗菜→切菜→炒菜），polyvec_ntt 是服务员不断往厨房送订单。如果外层没有 DATAFLOW，服务员必须等到前一个订单的所有菜品都炒完（ntt 完全返回），才能送下一个订单。这显然效率低下。

有了外层的 DATAFLOW，服务员可以在厨师还在炒上一道菜的最后一个步骤时，就把下一道菜的原料送进洗菜台。这样，两条流水线（厨房内 + 订单间）形成了完美的流水线嵌套。

4. 常量数组 zetas 的布局

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

设计考量：

  • zetas 是编译时常量，HLS 会将其综合为 ROM（只读存储器）。
  • 每个 stage 需要访问 zetas 的不同区间（Stage 0 用索引 1，Stage 1 用索引 2-3，等等）。
  • 由于 zetas 是只读的，多个 stage 可以同时读取而不会产生端口冲突。
  • 如果 zetas 很大，可以考虑使用 #pragma HLS ARRAY_PARTITION 将其分布到多个 BRAM 以提高并行访问能力。在本设计中，128 个 16-bit 值（256 bytes）足够小，可以直接放入单个 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
syn.csimflags=-Wall
tb.cflags=-Wall

关键配置项解析：

  • part=xcvp1202-vsva2785-1LP-i-L：目标器件是 Versal Premium 系列的 VP1202。这是一款高端自适应 SoC，拥有丰富的 DSP58 slice 和 UltraRAM，适合高性能信号处理。

  • flow_target=vivado：生成的 RTL 将打包为 Vivado IP，可以集成到更大的系统中。

  • package.output.format=ip_catalog：输出格式为 IP Catalog 格式，方便在 Vivado Block Design 中使用。

  • syn.top=polyvec_ntt：指定顶层函数。HLS 会以此为根生成硬件接口。

  • csim.code_analyzer=1：启用 HLS Code Analyzer，这是本教程的核心工具，用于可视化数据依赖和性能估计。

新贡献者需要注意的陷阱

1. 数组边界与循环范围

unsigned int len = K >> stage;  // K=128, stage=0..6
// stage=0: len=128, 但数组大小是 N=256，所以 j+len 最大为 127+128=255 ✓
// stage=6: len=2, j+len 最大为 254+2=256 ✗ 越界！

实际上不会越界的原因：仔细看循环条件 j < start + len，其中 start 的增量是 j + len。对于 stage=6，len=2，start 的取值是 0, 2, 4, ..., 254。当 start=254 时，j 从 254 开始，条件是 j < 254+2=256，所以 j 只能取 254，j+len=256 确实会越界！

修正：实际上代码是正确的，因为当 start=254 时，内层循环 j 的范围是 [254, 256)，即 j=254 唯一值。此时 j+len=256，而数组大小是 N=256，索引 256 确实是越界的。

经过仔细检查原始 Kyber 规范和参考实现，NTT 的最后一个 stage 实际上只处理到索引 255。这可能是代码中的一个潜在 bug，或者 N 的定义在实际使用时有所不同。建议新贡献者在修改循环边界时格外小心，并使用测试向量验证正确性。

2. DATAFLOW 的约束条件

HLS 的 DATAFLOW 优化有一些严格的限制，违反这些限制会导致优化失败或功能错误：

  • 单生产者单消费者：每个中间缓冲区（如 p_stage1）只能被一个 stage 写入，只能被另一个 stage 读取。如果有多个消费者，需要使用 hls::stream 进行显式复制。
  • 无条件执行：DATAFLOW 区域内的函数不能被条件调用（如 if (condition) ntt_stage<0>(...)）。所有函数必须无条件执行。
  • 固定次数循环：如果循环次数是变量，HLS 可能无法应用 DATAFLOW。本设计中 K=128 是编译时常量，满足要求。

3. Montgomery 约减的数值范围

int16_t montgomery_reduce(int32_t a) {
    int16_t t1 = (int16_t)a*QINV;  // 注意：这里是 int16_t 乘法，可能溢出！

潜在问题：(int16_t)a*QINV 将 a（int32）强制转换为 int16，然后与 QINV（int16）相乘。如果 a 的值很大，截断会丢失信息。

实际情况：在正确的 Montgomery 算法中，a 在进入此函数前已经被限制在一定范围内。fqmul 的输入 a 和 b 都是模 \(q\) 后的值，乘积 a*b 最大为 \((q-1)^2 \approx 11 \times 10^6\)，远小于 32 位整数范围。因此 (int16_t)a 的截断实际上是取了 a 的低 16 位，这正是 Montgomery 算法的要求。

4. 测试向量的重要性

polyvec_tb.cpp 中包含了硬编码的 golden reference：

uint16_t a_golden[N]= {5758, 65052, 3754, ...};

为什么重要：NTT 涉及大量模运算和位操作，肉眼很难验证结果的正确性。golden reference 来自 Kyber 的参考实现，是验证硬件实现正确性的金标准。

修改建议：如果你修改了算法（如改变模数 \(q\) 或多项式长度 \(N\)），必须重新生成 golden reference。可以使用 Kyber 的参考 C 实现或 SageMath 脚本生成新的测试向量。

与其他版本的关系

本模块是 Polynomial Vectorization 教程的第四个版本，代表了优化的最终形态：

演进路径体现了 HLS 优化的典型方法论：

  1. 功能正确性（Version0）
  2. 循环变换暴露并行性（Version1）
  3. 消除数据依赖（Version2）
  4. 架构级并行化（Version3）

总结

final_ntt_vectorization_hls_configuration 展示了如何将一个看似顺序的密码学算法转化为高度并行的硬件加速器。其核心设计洞察包括：

  1. 任务分解：将 NTT 的七个 stage 映射为七个独立的硬件任务
  2. 数据解耦：通过乒乓缓冲区消除任务间的数据依赖
  3. 流水线嵌套：在多个层次应用 DATAFLOW（stage 内、ntt 内、polyvec_ntt 内）
  4. 模板元编程：利用 C++ 模板在编译时生成专用硬件模块

对于新加入团队的工程师，建议按照 Version0 → Version1 → Version2 → Version3 的顺序阅读代码，配合 HLS Code Analyzer 的可视化报告，深入理解每一步优化的动机和效果。这将帮助你建立 HLS 设计的直觉，在未来的项目中做出正确的架构决策。

On this page