Intermediate Optimized NTT HLS Configuration (Version2)

概述：从依赖地狱到流水线的转折点

想象一下，你正在设计一条工厂流水线。在最初的版本中（baseline_ntt_hls_configuration），所有工人都挤在同一个工作台周围，争抢同一个工具箱——这就是Version0的内存访问模式。到了initial_vectorized_ntt_hls_configuration（Version1），你把工作分成了多个阶段，但工人们仍然在传递同一块工件，导致严重的拥堵。

Version2是这个优化旅程中的关键转折点。它引入了一个核心洞察：要释放HLS的空间并行性，必须消除对共享内存的竞争访问。通过将每个NTT阶段的输入和输出分离到独立的数组中，我们创建了一条清晰的"数据高速公路"——每个阶段都有自己的专用车道，数据可以单向流动而无需等待。这为后续的final_ntt_vectorization_hls_configuration（Version3）中应用#pragma HLS DATAFLOW奠定了结构性基础。

这个模块实现了CRYSTALS-Kyber后量子密码算法中的多项式向量NTT（Number Theoretic Transform）计算，是Vitis HLS教程系列中展示如何从算法级优化过渡到架构级优化的典型案例。

架构与数据流

整体架构图

核心抽象：解耦的数据通道

Version2的核心设计决策可以用一句话概括：每个计算阶段都拥有自己的输入缓冲区和输出缓冲区。这类似于现代CPU中的寄存器重命名技术——通过消除写后读（WAR）和读后写（WAW）冲突，允许更多的指令级并行。

在硬件层面，这意味着：

• p_stage1[N] ~ p_stage6[N]：六个中间缓冲区，每个256个uint16_t元素
• 每个阶段读取前一个阶段的输出，写入自己的输出缓冲区
• 没有两个阶段同时访问同一个数组

这种设计的代价是增加了片上BRAM的使用（约9个BRAM块 vs Version1的1个），但换来的是消除了所有由内存竞争导致的流水线停顿。

组件深度解析

polyvec_ntt(polyvec *v) — 顶层调度器

这是整个内核的入口点，负责协调K=128个多项式的批量处理。

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

设计意图：

• 保持简单的循环结构，为Version3的DATAFLOW优化预留空间
• 通过指针算术v->vec+i直接传递多项式地址，避免不必要的拷贝

关键限制：

• 当前版本尚未应用DATAFLOW，因此每次调用poly_ntt都会阻塞直到完成
• 这意味着处理128个多项式需要128 × ntt_latency的总时间

poly_ntt(poly *a) — 多项式包装器

void poly_ntt(poly *a) {
    // Create array to hold the output results
    uint16_t temp[N];

    // Call ntt() with the temporary arrays
    ntt(a->coeff, temp);

    // Copy the result back to the output polynomial
    for (unsigned int i = 0; i < N; i++) {
#pragma HLS pipeline
        a->coeff[i] = temp[i];
    }
}

为什么需要临时数组？

这里存在一个微妙的API设计约束。ntt()函数现在采用双缓冲区接口（输入/输出分离），但poly结构体的coeff数组既是输入又是输出。为了兼容这种"原地更新"的语义，我们需要：

1. 分配临时缓冲区temp[N]接收NTT结果
2. 将结果复制回原始位置

性能影响：

• 额外的256次内存写入操作
• 这个拷贝循环被标记为#pragma HLS pipeline，确保它以II=1高效执行
• 在Version3中，这个开销通过完全分离输入/输出结构体来消除

ntt(uint16_t p_in[N], uint16_t p_out[N]) — 核心变换引擎

这是Version2最重要的改进所在。与Version1使用单个数组p[N]不同，Version2明确分离了输入和输出：

void ntt(uint16_t p_in[N], uint16_t p_out[N]) {
    // ... 阶段变量声明 ...

    uint16_t p_stage1[N];
    uint16_t p_stage2[N];
    uint16_t p_stage3[N];
    uint16_t p_stage4[N];
    uint16_t p_stage5[N];
    uint16_t p_stage6[N];
    
    // Stage 1: 读取 p_in，写入 p_stage1
    // Stage 2: 读取 p_stage1，写入 p_stage2
    // ...以此类推...
    // Stage 7: 读取 p_stage6，写入 p_out
}

阶段分解的数学原理：

NTT是FFT在有限域上的变体。对于N=256点的变换，采用Cooley-Tukey算法的迭代形式，共log₂(256)=8层蝶形运算。由于Kyber的特定参数设置，实际实现为7个显式阶段（Stage 1-7）。

每个阶段的特点：

关键代码模式：

// 典型阶段的结构（以Stage 3为例）
len >>= 1;  // len从64变为32
ntt_stage3: for(start = 0; start < N; start = j + len) {
    int16_t zeta = zetas[k++];  // 获取旋转因子
    ntt_stage3i: for(j = start; j < start + len; j++) {
        #pragma HLS PIPELINE  // 关键：确保内层循环流水线化
        int16_t t = fqmul(zeta, p_stage2[j + len]);  // 复数乘法
        p_stage3[j + len] = p_stage2[j] - t;  // 蝶形运算：减法分支
        p_stage3[j] = p_stage2[j] + t;        // 蝶形运算：加法分支
    }
}

fqmul(int16_t a, int16_t b) — 有限域乘法

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

Montgomery约简的重要性：

在模Q=3329的有限域中进行乘法时，直接计算(a * b) % Q代价高昂（需要除法运算）。Montgomery约简通过巧妙的代数变换，将取模操作转化为廉价的位运算和乘法。

算法步骤：

1. 计算32位乘积：int32_t prod = (int32_t)a * b
2. Montgomery约简：t1 = (int16_t)prod * QINV（QINV = -3327是Q的模逆元）
3. 调整并右移：t2 = (prod - (int32_t)t1 * Q) >> 16

硬件映射：

• #pragma HLS INLINE强制内联，消除函数调用开销
• 整个操作映射到DSP48 slice的乘加链
• 在Versal器件上，这可以在单个时钟周期完成

依赖关系分析

上游依赖（谁调用我）

下游依赖（我调用谁）

本模块是自包含的，不依赖外部库函数。所有数学运算都通过基本算术操作和HLS原语实现。

内部数据流

p_in (外部输入)
   ↓
p_stage1 ──→ p_stage2 ──→ p_stage3 ──→ p_stage4 
                                              ↓
p_out (外部输出) ←── p_stage6 ←── p_stage5 ←──┘

关键观察：这是一个纯粹的前馈（feed-forward）结构，没有反馈回路或条件分支。这种规律性使得HLS工具能够准确预测性能并生成高效的流水线。

设计决策与权衡

决策1：手动展开外层循环 vs 保持循环结构

选择：Version2延续了Version1的手动展开策略，将ntt_stage_outer展开为7个独立阶段。

理由：

• 暴露阶段间的并行性潜力
• 允许每个阶段有独立的流水线深度优化
• 为DATAFLOW pragma的应用创造条件

代价：

• 代码量增加（约150行vs Version0的65行）
• 维护复杂度上升（修改一个阶段需要同步修改所有阶段）

决策2：双缓冲区 vs 单缓冲区原地计算

选择：每个阶段使用独立的输入/输出数组。

理由：

• 消除假依赖：HLS工具不再需要在p[j]的读和p[j+len]的写之间插入保守的同步
• 支持任务级并行：不同阶段可以同时处理不同数据集（在Version3中实现）
• 简化调度：编译器可以独立优化每个阶段的II（Initiation Interval）

代价：

• BRAM资源增加：6个中间缓冲区 × 256元素 × 2字节 = 3072字节 ≈ 9个BRAM18K
• 延迟略微增加（数据需要流经更多缓冲层级）

决策3：保留poly_ntt中的结果拷贝

选择：维持原地更新的API语义，接受额外的拷贝开销。

理由：

• 保持与Version0/Version1的API兼容性
• 渐进式优化策略：先解决最紧迫的内存竞争问题，再处理接口重构

后续改进：Version3通过分离vin/vout参数彻底消除了这一开销。

性能特征

根据Code Analyzer和C Synthesis的结果：

关键洞察：

• 尽管BRAM使用增加，但FF和LUT大幅减少，表明控制逻辑显著简化
• 这是消除复杂内存仲裁逻辑的直接影响
• 性能提升主要来自更激进的流水线调度

新贡献者必读：陷阱与注意事项

⚠️ 陷阱1：误以为这是最优版本

Version2是一个过渡性优化。虽然相比Version1有显著提升，但它还没有利用任务级并行（Task-Level Parallelism）。看到p_stage1~p_stage6的声明时，应该意识到这是为Version3的DATAFLOW准备的铺垫。

⚠️ 陷阱2：忽略poly_ntt中的拷贝开销

如果你只关注ntt()函数的优化，可能会遗漏poly_ntt()中那256周期的拷贝循环。在系统级分析中，这部分开销在处理大量多项式时会累积。

⚠️ 陷阱3：zetas数组的索引管理

int16_t zeta = zetas[k++];  // 每个阶段递增k

k的初始值为1（跳过zetas[0]），在每个阶段的内层循环前递增。这个微妙的约定来自Kyber规范，修改时需要格外小心。

⚠️ 陷阱4：PIPELINE pragma的位置

ntt_stage3i: for(j = start; j < start + len; j++) {
    #pragma HLS PIPELINE  // 必须放在这里，而不是外层循环

PIPELINE pragam作用于它所在的循环体。放在内层循环确保每个蝶形运算都能流水线化；如果错误地放在外层循环，会导致完全不同的调度行为。

🔍 调试建议

1. 使用Code Analyzer验证依赖消除：在Vitis IDE中运行C Simulation后，打开Code Analyzer视图，确认Channels表格中没有显示p_stageX数组的多重依赖。

2. 检查循环标签：每个循环都有唯一的标签（如ntt_stage3、ntt_stage3i），这在分析综合报告时至关重要——它们会出现在调度视图中。

3. 验证Montgomery常数：QINV = -3327是Q=3329关于2^16的模逆元。如果修改Q值，必须使用扩展欧几里得算法重新计算QINV。

演进路径

Version2处于优化旅程的中点：

Version0 (Baseline)
    ↓ 识别瓶颈：三重嵌套循环
Version1 (Manual Unroll)
    ↓ 识别瓶颈：共享数组p[]的依赖
Version2 (Decoupled Buffers)  ← 你在这里
    ↓ 下一步：应用DATAFLOW
Version3 (Task Parallelism)

前往final_ntt_vectorization_hls_configuration了解如何将这个设计进一步加速约3倍。

参考

• baseline_ntt_hls_configuration — 原始基线实现
• initial_vectorized_ntt_hls_configuration — 首次向量化尝试
• final_ntt_vectorization_hls_configuration — 最终优化版本
• Vitis HLS用户指南 — DATAFLOW和PIPELINE pragma的完整文档