🏠

多项式向量化与NTT优化教程 (Polynomial Vectorization NTT Versions)

一句话总结

本模块是一套渐进式HLS优化教程，演示如何将后量子密码学中关键的**数论变换(NTT)**多项式乘法，从纯软件实现逐步优化为高度并行化的硬件加速器——核心思想是打破内存访问瓶颈，通过数据重排和流水线并行实现"计算隐藏在内存访问背后"。

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

背景：格密码中的多项式乘法

在后量子密码学（如CRYSTALS-Kyber、CRYSTALS-Dilithium）中，核心运算是在模 \(q\) 下的多项式乘法：

\[c(x) = a(x) \times b(x) \mod (x^n + 1, q)\]

其中 \(n\) 通常是256或512，\(q\) 是一个素数（如3329或8380417）。直接计算的复杂度是 \(O(n^2)\)，对于高吞吐量应用来说太慢了。

NTT：从 \(O(n^2)\) 到 \(O(n \log n)\)

数论变换(NTT)是FFT在有限域上的版本。它利用卷积定理：

\[\text{NTT}(a \times b) = \text{NTT}(a) \circ \text{NTT}(b)\]

这样多项式乘法就变成了：

  1. 前向NTT：\(\hat{a} = \text{NTT}(a)\)，\(\hat{b} = \text{NTT}(b)\) —— \(O(n \log n)\)
  2. 逐点相乘：\(\hat{c}_i = \hat{a}_i \cdot \hat{b}_i \mod q\) —— \(O(n)\)
  3. 逆向NTT：\(c = \text{INTT}(\hat{c})\) —— \(O(n \log n)\)

为什么要硬件加速？

虽然NTT将复杂度降到了 \(O(n \log n)\)，但在高吞吐量场景（如TLS握手、大量签名验证）中，纯软件实现仍然成为瓶颈：

  1. 内存墙问题：NTT是内存密集型算法，随机访问模式导致缓存未命中率高
  2. 位反转重排：NTT前后的位反转索引重排破坏数据局部性
  3. 蝴蝶操作数据依赖：每级NTT的蝴蝶操作有复杂的读写依赖模式

这就是本模块要解决的问题：通过Vitis HLS将NTT算法逐步优化为FPGA加速器，学习如何在硬件上高效实现复杂的数字信号处理算法。

核心抽象：四个版本的演进思维

本模块的核心教学设计是渐进式优化——从纯软件实现开始，逐步引入硬件并行技术。想象你在教一个只能顺序执行的学生如何并行工作：

类比：工厂流水线的演进

想象一个工厂生产多项式乘法：Version0 就像一个工匠在一张桌子上完成所有工作（顺序执行，频繁进出仓库取料）；Version1 引入了分组装配（向量化加载，一次取多个零件）；Version2 建立了专用装配线（数据流流水线，多工序并行）；Version3 则是全自动JIT生产（完全展开循环，所有资源并行，零等待）。

四个版本的核心差异

版本 核心优化策略 HLS关键技术 目标瓶颈
Version0 基线实现，纯算法描述 无特殊指令 建立基准性能
Version1 内存访问向量化 ap_vector, memcpy优化 内存带宽利用率
Version2 循环展开与数据流 PIPELINE, UNROLL, DATAFLOW 计算并行度
Version3 全展开架构优化 完全展开+资源复用 II=1的理想吞吐量

数据流的心智模型

在NTT硬件加速器中，数据流动遵循**"内存→计算→内存"**的循环，但有特殊的蝴蝶网络拓扑：

内存 (系数数组)
    ↓ (加载阶段 - 可能伴随位反转重排)
蝴蝶单元 (Butterfly Unit): 执行 (a + b*w, a - b*w)
    ↓ (存储阶段)
内存 (变换后的系数)

在迭代式NTT中（本模块采用的方式），同一组硬件被重复使用 \(\log_2(n)\) 轮，每轮处理不同的"跨度"(stride)。在完全展开式NTT中（Version3接近），所有\(\log_2(n)\)级蝴蝶单元同时存在，数据流过一条长流水线。

架构与组件

模块结构

graph TD A[polynomial_vectorization_ntt_versions] --> B[Version0
基线NTT配置] A --> C[Version1
初始向量化配置] A --> D[Version2
中间优化配置] A --> E[Version3
最终向量化配置] B --> B1[hls_config.cfg
polyvec_ntt] C --> C1[hls_config.cfg
polyvec_ntt] D --> D1[hls_config.cfg
polyvec_ntt] E --> E1[hls_config.cfg
polyvec_ntt]

每个版本都是一个完整的Vitis HLS工作空间，包含：

  • hls_config.cfg: HLS编译配置文件
  • polyvec.cpp/polyvec.h: 核心算法实现（不同版本间的主要差异）
  • polyvec_tb.cpp: 测试平台

配置层次分析

所有版本共享相同的顶层函数签名 polyvec_ntt，但通过不同的polyvec.cpp实现和配置选项展示优化演进。

关键配置参数（所有版本通用）：

part=xcvp1202-vsva2785-1LP-i-L  # Versal Premium器件
flow_target=vivado
package.output.format=ip_catalog  # 生成IP目录格式
package.output.syn=false
syn.top=polyvec_ntt               # 顶层函数

版本间配置差异：

  • Version0: csim.code_analyzer=0 - 关闭代码分析，纯功能仿真
  • Version1-3: csim.code_analyzer=1 - 启用代码分析器，帮助识别优化机会
  • Version3额外配置: syn.csimflags=-Wall, tb.cflags=-Wall - 严格编译检查，确保优化代码的健壮性

设计权衡与决策

1. 优化策略：渐进式 vs. 一步到位

选择：使用4个增量版本展示优化过程，而非直接给出最终方案。

理由：

  • 教学价值：HLS优化的关键是理解"为什么"而非"是什么"。渐进式演进让学习者看到每步优化的具体收益。
  • 调试友好：当最终版本行为异常时，可以回退到前一版本快速定位是哪个优化引入的问题。
  • 可移植性：不同FPGA器件和应用对面积/吞吐量的权衡不同，基线版本允许用户根据资源约束重新选择优化路径。

代价：

  • 代码重复：4个版本有高度相似的文件结构
  • 维护开销：修改公共接口需要同步更新4个版本

2. 目标器件选择：Versal Premium (xcvp1202)

选择：配置文件中指定高端Versal器件。

理由：

  • AI引擎协同：Versal的AIE阵列与本模块的AIE教程生态紧密集成（见依赖关系）
  • 内存带宽：NTT是内存密集型，Versal的HBM支持满足高吞吐量需求
  • DSP资源：大量DSP58 slice支持并行蝴蝶操作

影响：

  • 代码使用了针对Versal优化的pragma（如特定ARRAY_PARTITION因子）
  • 在低端7系列器件上可能需要调整分区因子以避免BRAM耗尽

3. 接口抽象：IP目录输出 vs. 独立可执行文件

选择：package.output.format=ip_catalog 而非裸核或独立应用。

理由：

  • 系统集成：生成的IP可直接被Vivado IPI使用，与AIE/PL连接
  • 标准化：遵循Xilinx IP封装规范，保证工具链兼容性
  • 可配置性：IP封装允许通过GUI配置参数（如NTT大小、模数）

权衡：

  • 需要额外的Vivado步骤实例化IP，不能直接仿真整个系统
  • 依赖Vivado IP目录缓存，切换版本需要清理IP缓存

4. 代码分析器策略：Version0关闭，后续版本启用

选择：csim.code_analyzer在基线关闭，在优化版本启用。

理由：

  • 基线纯净性：Version0的目标是建立功能正确的黄金参考，关闭分析器避免任何工具特定的干扰
  • 优化指导：Version1+的分析器输出帮助识别流水线停顿、内存依赖等瓶颈，是渐进式优化的指南针

数据流与依赖关系

外部依赖分析

本模块虽然是独立的HLS教程，但依赖关系揭示了它在更大生态系统中的定位：

graph LR A[polyvec_ntt
HLS Kernel] --> B[AIE控制运行时
aie_control_xrt.cpp] A --> C[polyvec类型系统
K,N,Q,QINV,poly,polyvec] subgraph "Version0-3共享依赖" C --> D[格密码参数
K=4,N=256,Q=3329] end subgraph "AIE生态系统" B --> E[SSR FIR教程
Super Sampling Rate] end

关键依赖解读：

  1. AIE控制运行时 (aie_control_xrt.cpp): 本模块的HLS内核设计为与Versal AIE阵列协同工作。依赖路径指向AI_Engine_Development.AIE.Design_Tutorials.02-super_sampling_rate_fir，说明polyvec_ntt可能作为PL端预处理/后处理单元，与AIE端的SSR FIR滤波器形成完整信号处理链。

  2. 格密码参数系统: 所有版本共享相同的格密码参数定义（K, N, Q, QINV等），这些参数直接对应CRYSTALS-Kyber的标准参数集：

    • K=4: 多项式向量维度
    • N=256: 多项式次数（NTT点数）
    • Q=3329: 模数（支持NTT的原根存在条件）
    • QINV: Q的模逆元（用于Montgomery约减）

  3. 类型系统层次: 依赖关系显示从简单类型（K, N, Q标量）到复合类型（poly, polyvec）的层次，Version3可能涉及最复杂的类型向量化。

数据流架构

虽然具体实现代码未提供，但基于格密码NTT的标准数据流和HLS优化模式，可以推断四个版本的数据流演进：

graph TD subgraph "Version0: 基线顺序流" V0_A[加载a,b] --> V0_B[位反转重排] V0_B --> V0_C[NTT迭代N轮] V0_C --> V0_D[逐点乘] V0_D --> V0_E[INTT] V0_E --> V0_F[存储结果] end subgraph "Version1: 向量化加载" V1_A[向量加载
ap_vector] --> V1_B[位反转] V1_B --> V1_C[NTT迭代] V1_C --> V1_D[向量化乘] V1_D --> V1_E[INTT] V1_E --> V1_F[向量存储] end subgraph "Version2: 流水线并行" V2_A[数据流区域] --> V2_B[加载阶段
PIPELINE II=1] V2_B --> V2_C[NTT阶段
UNROLL因子N] V2_C --> V2_D[乘阶段] V2_D --> V2_E[INTT阶段] V2_E --> V2_F[存储阶段] end subgraph "Version3: 全展开架构" V3_A[全并行NTT
所有级同时] --> V3_B[蝴蝶网络
硬连线] V3_B --> V3_C[逐点乘阵列] V3_C --> V3_D[INTT网络] V3_D --> V3_E[输出寄存器] end

关键技术演进解析

Version0 → Version1: 内存带宽瓶颈突破

基线实现使用标量加载/存储，每次内存事务传输32位数据。Versal器件的PL端支持512位或更宽的AXI4-Stream总线，标量访问严重浪费带宽。

Version1引入ap_vector类型（或等效向量类型），一次加载8个32位系数（256位），使内存带宽利用率提升8倍。这要求：

  • 数据在内存中对齐到向量边界
  • 位反转重排改为向量粒度而非标量粒度
  • NTT蝴蝶操作的数据路径加宽

Version1 → Version2: 计算并行度释放

即使内存带宽充足，Version1的顺序执行仍使计算单元闲置。NTT具有内在的并行性：

  • 同一级内的所有蝴蝶操作相互独立
  • 不同级的计算可以流水线化（前一级的输出作为后一级的输入）

Version2使用#pragma HLS PIPELINE使循环迭代间隔(II)降为1，配合#pragma HLS UNROLL复制蝴蝶计算单元。这实现了：

  • 每个时钟周期启动新的NTT级计算
  • 多级NTT重叠执行（数据流架构）
  • 计算与内存访问并行（预取下一向量，同时计算当前向量）

Version2 → Version3: 空间并行架构

Version2仍使用时间复用：同一组蝴蝶硬件执行所有\(\log_2(N)\)级NTT。Version3完全展开，创建\(\log_2(N)\)级级联的蝴蝶网络：

输入 → [蝶形单元级0] → [蝶形单元级1] → ... → [蝶形单元级7] → 输出

这需要：

  • 大量DSP48资源（每级N/2个乘法器）
  • 大量布线资源（级间全连接）
  • 但延迟降到最低（\(\log_2(N)\)个时钟周期完成整个NTT）

Version3是面积换延迟的极致，适用于极低延迟场景（如实时加密流）。

子模块详解

本模块包含四个渐进式优化版本，每个版本展示不同的HLS优化策略：

Version0 - 基线NTT配置

纯算法实现，无硬件优化pragma。建立功能正确性黄金标准，作为后续版本性能比较的基准。

Version1 - 初始向量化配置

引入向量数据类型(ap_vector)，通过宽总线事务提升内存带宽利用率。展示数据级并行(DLP)的基础应用。

Version2 - 中间优化配置

启用流水线(PIPELINE)和循环展开(UNROLL)，释放指令级并行(ILP)。引入数据流(DATAFLOW)架构实现任务级并行(TLP)。

Version3 - 最终向量化配置

完全展开所有循环，创建空间并行架构。展示极致面积换延迟的硬件设计，实现每个时钟周期输出的理想吞吐量。

关键设计权衡

权衡1：迭代式NTT vs. 完全展开式NTT

问题：应该复用同一套蝴蝶硬件做\(\log_2(N)\)轮计算（面积小，时间长），还是为每级创建独立硬件（面积大，时间短）？

本模块的选择：

  • Version0-2使用迭代式（时间复用）
  • Version3探索完全展开式（空间并行）

决策逻辑：教程目标是展示HLS从软件到硬件的完整能力谱系，而非单一优化点。Version3的存在证明HLS可以描述完全空间并行架构，但实践中需在面积约束下选择迭代式。

权衡2：内存架构：乒乓缓冲 vs. 原地算法

问题：NTT需要蝶形操作的两输入来自不同内存位置。传统原地算法节省内存但破坏访问模式；乒乓缓冲使用双倍内存但保证连续访问。

推断的实现：

  • Version0可能使用单数组原地算法（缓存不友好）
  • Version1+引入乒乓缓冲配合向量加载（利用空间局部性）

影响：乒乓缓冲使内存带宽需求翻倍，但HLS的DATAFLOW允许计算与内存传输重叠，净吞吐量提升。

权衡3：模乘算法：Barrett约减 vs. Montgomery约减

问题：NTT蝴蝶操作核心是模乘 \(a \cdot b \mod q\)。硬件上除法昂贵，需用近似算法。

线索：配置文件中引用了QINV（Q的模逆元），这是Montgomery约减的标志。

决策：

  • 使用Montgomery域表示：系数保持"Montgomery形式" \(a \cdot R \mod q\)（\(R\)是2的幂）
  • 乘法自动完成Montgomery约减
  • 避免了运行时的除法或复杂Barrett预计算

权衡：Montgomery需要输入输出转换（乘以\(R^2\)或\(1\)），但NTT的线性性质允许吸收这些常数到旋转因子中，实现"免费"转换。

新贡献者必读：陷阱与最佳实践

🚨 常见陷阱

陷阱1：忽视位反转重排的内存访问模式

问题：NTT要求输入/输出进行位反转重排（bit-reversal permutation）。若实现为标量随机访问，HLS无法合成高效的AXI4-Full接口。

正确做法：

  • 使用查表法预计算位反转索引
  • 结合ARRAY_PARTITION将索引表分布式存储
  • 在向量加载阶段合并重排，避免单独遍历

陷阱2：混淆Montgomery域与普通整数域

问题：在Montgomery域中，数值\(x\)实际表示为\(x \cdot R \mod q\)。若在域外做比较或分支判断，结果会错误。

检测方法：

  • 检查是否所有模乘都通过montgomery_reduce函数
  • 验证常量（如旋转因子twiddle factors）是否预转换为Montgomery形式
  • 确认最终输出是否执行Montgomery逆变换（若需要普通整数结果）

陷阱3：循环展开因子与资源约束不匹配

问题：Version3完全展开所有循环，如果在小器件（如xc7z020）上综合，会因DSP或BRAM耗尽而失败。

建议：

  • 使用#pragma HLS ALLOCATION限制特定操作符（如乘法器）数量
  • 对UNROLL使用factor而非完全展开，找到吞吐/面积平衡点
  • 利用DATAFLOW替代完全展开，用时间复用换取空间节省

陷阱4：忽略HLS仿真与硬件语义差异

问题：CSim（C仿真）通过，但RTL仿真失败或硬件行为异常。

常见原因：

  • 未定义行为：C仿真中数组越界可能"工作"，但硬件产生随机值
  • 浮点精度：HLS综合可能改变浮点运算顺序（虽然NTT通常是定点）
  • 并发访问：DATAFLOW区域的并发调度在CSim中是顺序模拟的，可能掩盖竞争条件

防御措施：

  • 启用csim.sanitize_address=1（Version3配置中已启用）检测越界
  • 运行Co-Sim（联合仿真）验证RTL与C行为一致性
  • 对DATAFLOW使用hls::stream而非裸指针，利用其内置同步语义

✅ 最佳实践

实践1：版本间差异分析工作流

当需要理解某个优化技术的具体效果时：

# 1. 对比Version0和Version1的polyvec.cpp差异
diff -u Version0/polyvec.cpp Version1/polyvec.cpp > v0_to_v1.patch

# 2. 查看HLS综合报告中的关键指标
# 在Version0/build/sol1/syn/report/polyvec_ntt_csynth.rpt中查找：
# - Overall Latency (cycle)
# - Pipeline Initiation Interval (II)
# - Resource Estimates (DSP, BRAM, FF, LUT)

# 3. 分析Version3的完全展开循环计数
# 在HLS日志中查找UNROLL产生的副本数，验证等于循环边界

实践2：参数化设计验证

本模块硬编码了Kyber参数，但在实际应用中可能需要支持多参数集：

// 在polyvec.h中建议的模板化设计（概念性）
template<int K_VAL, int N_VAL, int Q_VAL>
class PolyVecNTT {
    static_assert(N_VAL == 256 || N_VAL == 512, "Unsupported N");
    // 使用K_VAL, N_VAL, Q_VAL替代硬编码宏
};

注意：HLS对C++模板支持良好，但需确保所有模板参数在综合时为常数（constexpr或宏定义）。

实践3：与AIE阵列的协同设计

从依赖关系看，本模块最终要与DualSSR16等AIE教程集成。在设计PL端的polyvec_ntt时，应预先考虑AIE-PL接口：

  • 数据格式：AIE使用cint16（16位实部+16位虚部），而NTT使用模整数。需要明确PL端是否应在传输前将系数打包为cint16格式，或保持原始整数由AIE端解释。

  • 同步机制：polyvec_ntt作为PL kernel应使用hls::stream或AXI4-Stream接口，与AIE的PLIO（Programmable Logic I/O）直接连接。避免使用m_axi（AXI4-Full）进行AIE-PL通信，因为AIE DMA引擎针对流式传输优化。

  • 缓冲区对齐：AIE要求512位对齐的缓冲区进行高效DMA。PL端的m_axi接口应配置为64字节（512位）突发长度，与AIE DMA的MM2S/S2MM引擎对齐。

总结

polynomial_vectorization_ntt_versions模块是一个精心设计的教学工具，其价值远超代码本身：

  1. 渐进式优化的活教材：四个版本形成一条清晰的优化路径，每一步都有明确的目标和可量化的收益。新成员可以通过对比不同版本，建立HLS优化的直觉。

  2. 理论到实践的桥梁：将NTT这一抽象数学算法映射到具体的FPGA硬件实现，展示了如何解决内存墙、数据依赖、资源约束等真实工程挑战。

  3. 更大系统的组件：虽然作为独立教程呈现，但其依赖关系揭示了它是Versal生态的一部分——与AIE阵列、DDR控制器、DMA引擎紧密集成，为完整系统的设计提供PL端基础。

对于新加入团队的工程师，建议的学习路径是：先理解Version0的数学逻辑，再对比Version1的内存优化，体会Version2的流水线艺术，最后研究Version3的空间并行设计。每一步都尝试修改参数（如改变UNROLL因子、调整ARRAY_PARTITION模式），观察综合报告的变化，建立对HLS工具链的深刻理解。

On this page