Polynomial Vectorization NTT Versions 子模块技术解析

一句话概括

这是一个渐进式 HLS 优化实验室，通过四个版本（Version0→Version3）展示如何将一个后量子密码学中常用的 NTT（Number Theoretic Transform，数论变换）多项式乘法算法，从"能跑的 C++ 代码"逐步优化为"高性能 FPGA 硬件"。每个版本都是一堂受控实验课，让你亲手测量每个优化 pragma 的物理效果。

核心问题：为什么需要四个版本？

教学的困境

传统的 HLS 教学要么太浅（只讲语法），要么太深（直接扔给你一个优化好的工程）。Polynomial Vectorization 解决了这个断层问题：

• Version0（Baseline）：你的起点，验证"算法在功能上是正确的"，但完全不考虑硬件效率。这是你的性能基线。
• Version1（Initial Vectorization）：引入最基本的 HLS 优化——流水线（PIPELINE）和循环展开（UNROLL）。你开始学会"让硬件并行工作"。
• Version2（Intermediate Optimization）：深入到内存架构——数组分区（ARRAY_PARTITION）。你学会"消除内存瓶颈"。
• Version3（Final Implementation）：最高级的优化——数据流（DATAFLOW）。你学会"让不同的处理阶段像流水线一样重叠执行"。

版本间的关键差异（预期）

虽然我们没有实际的源代码文件，但基于 Vitis HLS 的标准教学模式和配置文件的演进，我们可以推断每个版本的关键优化点：

数据结构：NTT 的核心数学抽象

多项式（poly）和多项式向量（polyvec）

基于外部依赖信息，我们可以推断数据结构的设计：

// 预期：单多项式（固定大小数组，适合 FPGA 存储）
typedef struct {
    // N 通常是 256（基于 Kyber 等后量子密码标准）
    int16_t coeffs[N];  // 系数数组，16-bit 有符号整数
} poly;

// 预期：多项式向量（多个多项式的集合）
typedef struct {
    // K 通常是 2, 3, 或 4（基于具体的安全等级）
    poly vec[K];  // K 个多项式
} polyvec;

关键数学参数（从依赖图推断）

基于外部依赖信息，每个版本的 polyvec 依赖于以下数学常量：

重要洞察：这些参数是密码学安全性的根基。在 HLS 优化时，绝对不能改变这些数学参数，否则会导致密码学安全性的破坏。所有的优化必须在这些约束下进行。

配置文件的演进：从 Version0 到 Version3

Version0 配置解析（Baseline）

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=0    # 关键差异：禁用代码分析器
csim.clean=true

关键特性：

• csim.code_analyzer=0：Baseline 版本专注于功能正确性，不启用静态分析。这是为了展示"最自然的 C++ 代码"，即使它包含一些 HLS 不推荐的写法。
• package.output.format=ip_catalog：输出 Vivado IP 目录格式，便于集成到更大的 Vivado 工程中。

Version1-3 配置解析（优化版本）

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

关键差异：

• csim.code_analyzer=1：从 Version1 开始启用代码分析器。这是因为优化版本的代码通常包含更多的 HLS pragma，需要静态分析来确保它们的正确性。

Version3 的额外配置（从提供的代码片段推断）：

# Version3 特有的额外配置
csim.sanitize_address=0
csim.sanitize_undefined=0
syn.csimflags=-Wall
tb.cflags=-Wall

解读：

• -Wall：启用所有编译器警告，帮助捕获潜在问题。
• sanitize_address=0：在最终版本中禁用 AddressSanitizer（为了更快的仿真速度），但在调试阶段可以启用。

HLS 优化技术深度解析（预期）

Version1：操作级并行（Operation-Level Parallelism）

核心 pragma：#pragma HLS PIPELINE 和 #pragma HLS UNROLL

预期代码模式：

// Version0: 顺序执行
for (int i = 0; i < N; i++) {
    result[i] = a[i] * b[i];  // 每次迭代 1 个周期
}
// 总延迟 = N 个周期

// Version1: 流水线 + 展开
#pragma HLS PIPELINE II=1  // 目标：每周期启动一次迭代
#pragma HLS UNROLL factor=4  // 展开 4 倍，复制硬件
for (int i = 0; i < N; i++) {
    result[i] = a[i] * b[i];
}
// 总延迟 ≈ N/4 个周期（理想情况）

关键洞察：

• PIPELINE II=1 的目标是让循环的启动间隔（Initiation Interval）为 1 个时钟周期。这意味着每周期可以处理一个新的迭代。
• UNROLL factor=4 通过复制循环体硬件来实现 4 路并行。代价是资源用量增加 4 倍。
• 依赖关系限制：如果循环迭代间有数据依赖（如 a[i] = a[i-1] + b[i]），II=1 可能无法实现。

Version2：内存级并行（Memory-Level Parallelism）

核心 pragma：#pragma HLS ARRAY_PARTITION

问题背景： 在 Version1 中，即使你有足够的 DSP 来并行计算，内存端口可能成为瓶颈。一个 BRAM 通常只有 2 个读写端口，如果 4 个并行的运算单元同时请求数据，就会发生冲突（端口竞争）。

预期代码模式：

// Version1: 内存瓶颈
int a[N];  // 单端口 BRAM
#pragma HLS PIPELINE II=1
#pragma HLS UNROLL factor=4
for (int i = 0; i < N; i++) {
    // 问题：4 个并行单元同时读取 a[i]，BRAM 端口不足
    result[i] = a[i] * b[i];
}

// Version2: 数组分区消除瓶颈
int a[N];
// 将数组分为 4 个独立的 BRAM，每个有独立端口
#pragma HLS ARRAY_PARTITION factor=4 type=cyclic
#pragma HLS PIPELINE II=1
#pragma HLS UNROLL factor=4
for (int i = 0; i < N; i++) {
    // 现在 a[i] 被映射到 4 个 BRAM 之一，无端口竞争
    result[i] = a[i] * b[i];
}

分区策略详解：

关键洞察：

• factor 的选择：factor 应该与 UNROLL factor 匹配。如果你展开了 4 倍循环，但只分区了 2 倍，仍然有端口瓶颈。
• BRAM 容量的代价：每个分区都是一个独立的 BRAM 实例。ARRAY_PARTITION factor=16 意味着 16 倍的 BRAM 用量。当数组很大时，这可能迅速耗尽 FPGA 的 BRAM 资源。

Version3：任务级并行（Task-Level Parallelism）

核心 pragma：#pragma HLS DATAFLOW

问题背景： 在 Version2 中，我们优化了单个循环内的并行度。但一个典型的算法通常由多个顺序的阶段组成。例如：

1. 读取输入数据
2. 执行 NTT 变换（第一阶段）
3. 执行点乘运算
4. 执行逆 NTT 变换（第二阶段）
5. 写入输出数据

传统的顺序执行意味着：阶段 2 必须等阶段 1 完全完成才能开始。但硬件上，阶段 1 处理完第一批数据后，阶段 2 就可以开始处理，同时阶段 1 继续处理第二批数据。

预期架构（DATAFLOW 区域）：

// Version3: 任务级数据流
void polyvec_ntt(polyvec *r) {
    #pragma HLS INTERFACE m_axi port=r offset=slave bundle=gmem
    #pragma HLS INTERFACE s_axilite port=r bundle=control
    
    // 本地缓冲区（ping-pong 或 FIFO）
    int16_t buf1[N];
    int16_t buf2[N];
    int16_t buf3[N];
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=buf1
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=buf2
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=buf3
    
    // DATAFLOW 区域：内部函数并发执行
    #pragma HLS DATAFLOW
    
    // 阶段 1：读取输入
    // （可能通过 hls::stream 或 ping-pong 缓冲与下一阶段通信）
    stage1_read_input(r, buf1);
    
    // 阶段 2：NTT 变换（第一阶段）
    // 当 stage1 处理第 N+1 个数据块时，stage2 可以处理第 N 个数据块
    stage2_ntt_layer1(buf1, buf2);
    
    // 阶段 3：点乘运算
    stage3_pointwise_mul(buf2, buf3);
    
    // 阶段 4：逆 NTT 变换
    stage4_inv_ntt(buf3, buf1);
    
    // 阶段 5：写回输出
    stage5_write_output(buf1, r);
}

// 每个子函数内部也有自己的 PIPELINE 和 ARRAY_PARTITION
void stage2_ntt_layer1(int16_t *in, int16_t *out) {
    #pragma HLS PIPELINE II=1
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=in
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=out
    
    // NTT 蝴蝶运算实现
    for (int i = 0; i < N/2; i++) {
        #pragma HLS UNROLL factor=4
        butterfly(in[i], in[i+N/2], out[i], out[i+N/2]);
    }
}

DATAFLOW 的工作原理：

1. 通道通信：DATAFLOW 区域内的函数通过 hls::stream 或 ping-pong 缓冲（双缓冲）进行通信。生产者函数写入数据，消费者函数读取数据，无需等待整个数组处理完成。

2. 并发执行：当生产者函数处理第 N+1 批数据时，消费者函数可以同时处理第 N 批数据。这种函数级流水线与循环级流水线（PIPELINE）相结合，最大化整体吞吐量。

3. 死锁避免：HLS 工具会自动插入必要的握手信号（ap_start/ap_done/ap_ready/ap_idle）和 FIFO/双缓冲存储，确保数据流不会死锁。

关键洞察：

• DATAFLOW vs. PIPELINE：

  • PIPELINE 作用于单个循环或函数内部，让连续的迭代重叠执行。
  • DATAFLOW 作用于多个函数或循环之间，让不同的处理阶段重叠执行。
  • 两者可以（而且应该）结合使用：DATAFLOW 区域内的每个子函数内部可以有自己的 PIPELINE。

• 内存架构的权衡：

  • DATAFLOW 需要通道存储（channel storage）来在函数间传递数据。这可以是：
    • hls::stream（FIFO）：适合流式数据，容量有限但控制简单。
    • Ping-pong 缓冲（双缓冲）：适合块数据处理，容量大但需要 2 倍存储空间。
  • 选择哪种方式取决于数据访问模式：流式（stream）vs. 块（block）。

• 复杂度管理：

  • DATAFLOW 引入了大量的控制逻辑（调度、握手、流控）。当函数数量增加时，调试难度呈指数级增长。
  • 建议：从简单的 2-3 个函数的 DATAFLOW 开始，逐步增加复杂度。始终使用 HLS 的 Dataflow Viewer 工具可视化数据流。

实战指南：从 Version0 到 Version3 的迁移路径

步骤 1：建立测量基线（Version0）

目标：验证算法功能正确，建立性能基线。

操作：

1. 在 Version0 目录下运行：

   vitis_hls -f hls_config.cfg
   

2. 记录 C 仿真（C Simulation）的结果，确认输出与参考模型匹配。
3. 查看综合报告（Synthesis Report），记录：
   • 估计的时钟周期（Clock Period）
   • 总延迟（Total Latency，以时钟周期计）
   • 资源用量估计（BRAM、DSP、FF、LUT）

关键观察：Version0 的 Interval（启动间隔）可能非常大，因为它没有流水线优化，每个循环迭代必须等前一个完全完成。

步骤 2：引入操作级并行（Version1）

目标：使用 PIPELINE 和 UNROLL 提高单循环内的并行度。

代码修改示例：

// Version0：顺序执行
void ntt_butterfly_loop(int16_t *data) {
    for (int i = 0; i < N/2; i++) {
        butterfly(data[i], data[i+N/2]);  // 每次迭代 1 个周期
    }
}

// Version1：流水线 + 展开
void ntt_butterfly_loop(int16_t *data) {
    #pragma HLS PIPELINE II=1  // 目标：每周期启动一次迭代
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=data
    
    for (int i = 0; i < N/2; i++) {
        #pragma HLS UNROLL factor=4  // 同时处理 4 个蝴蝶运算
        butterfly(data[i], data[i+N/2]);
    }
}

验证步骤：

1. 重新运行 vitis_hls -f hls_config.cfg。
2. 对比综合报告：
   • Interval 应该从 N/2 降低到 N/8（理想情况，4 倍展开）。
   • 资源用量（DSP、LUT）应该增加约 4 倍。
3. 运行 C 协同仿真（Co-simulation），验证 RTL 行为与 C 模型一致。

常见问题：

• II 无法达到 1：检查是否有跨迭代依赖（read-after-write）。可能需要 dependence pragma 告诉 HLS 依赖不存在。
• 资源爆炸：UNROLL factor 太高，超出了 DSP 切片数量。降低 factor 或改用 PIPELINE 不展开。

步骤 3：优化内存架构（Version2）

目标：使用 ARRAY_PARTITION 消除内存端口瓶颈。

问题诊断： 在 Version1 中，即使有 UNROLL factor=4，如果 data 数组存储在单个 BRAM 中，它只有 2 个端口。4 个并行的蝴蝶运算同时请求读写时，3 个必须等待。

代码修改：

void ntt_butterfly_loop(int16_t *data) {
    // 关键优化：将 data 数组分区为 4 个独立的 BRAM
    // cyclic 模式：data[i] 映射到第 i%4 个 BRAM
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=data
    
    #pragma HLS PIPELINE II=1
    
    for (int i = 0; i < N/2; i++) {
        #pragma HLS UNROLL factor=4
        // 现在 4 个蝴蝶运算可以并行访问 4 个独立的 BRAM，无冲突
        butterfly(data[i], data[i+N/2]);
    }
}

验证重点：

1. 查看综合报告的 Resource Estimates → Memory 部分。
   • Version1：应该显示 1 个 BRAM18 或 BRAM36。
   • Version2：应该显示 4 个 BRAM18/36（或等效的分区存储）。
2. 检查 Schedule Viewer（如果可用），确认内存访问没有冲突（无 Stall 标记）。

分区策略选择：

步骤 4：任务级并行（Version3）

目标：使用 DATAFLOW 实现函数级流水线。

架构演进：

Version0-2（函数内并行）：
输入 → [NTT Stage 1 → NTT Stage 2 → ... → Pointwise Mul → Inv NTT] → 输出
      └─────────────────────────────────────────────────────────────┘
                           顺序执行，无重叠

Version3（函数间并行，DATAFLOW）：
输入 → [NTT Stage 1] → [NTT Stage 2] → ... → [Pointwise Mul] → [Inv NTT] → 输出
      └─────────────┘ └─────────────┘      └─────────────┘ └───────────┘
       处理第 N+3 批    处理第 N+2 批         处理第 N+1 批   处理第 N 批
                           流水线执行，多批次重叠

预期代码架构：

void polyvec_ntt(polyvec *r) {
    #pragma HLS INTERFACE m_axi port=r offset=slave bundle=gmem
    #pragma HLS INTERFACE s_axilite port=r bundle=control
    
    // 本地缓冲区（DATAFLOW 区域使用的 ping-pong 缓冲或 hls::stream）
    int16_t buf1[N*K];
    int16_t buf2[N*K];
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=buf1
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=buf2
    
    // DATAFLOW 区域：内部函数并发执行
    #pragma HLS DATAFLOW
    
    // 阶段 1-6：分解的 NTT 处理流程
    // 每个阶段完成后，数据通过流或 ping-pong 缓冲传递到下一阶段
    stage1_forward_ntt_layer0(r->vec[0].coeffs, buf1);
    stage2_forward_ntt_layer1(buf1, buf2);
    stage3_forward_ntt_layer2(buf2, buf1);
    stage4_pointwise_multiplication(buf1, r->vec[1].coeffs, buf2);  // 与其他多项式点乘
    stage5_inverse_ntt(buf2, buf1);
    stage6_writeback(buf1, r->vec[0].coeffs);
}

// 每个子函数内部有自己的 PIPELINE 和 ARRAY_PARTITION
void stage2_forward_ntt_layer1(int16_t *in, int16_t *out) {
    #pragma HLS PIPELINE II=1
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=in
    #pragma HLS ARRAY_PARTITION factor=4 type=cyclic variable=out
    
    // NTT 蝴蝶运算实现
    for (int i = 0; i < N/2; i++) {
        #pragma HLS UNROLL factor=4
        butterfly(in[i], in[i+N/2], out[i], out[i+N/2]);
    }
}

关键概念：DATAFLOW 的通信机制

DATAFLOW 区域内的函数间通信有两种主要方式：

1. hls::stream（FIFO）：

   #include "hls_stream.h"
   
   void top(int *in, int *out) {
       hls::stream<int> fifo1("fifo1");
       hls::stream<int> fifo2("fifo2");
       #pragma HLS STREAM variable=fifo1 depth=16  // 设置 FIFO 深度
       #pragma HLS STREAM variable=fifo2 depth=16
       
       #pragma HLS DATAFLOW
       stage1(in, fifo1);
       stage2(fifo1, fifo2);  // fifo1 作为输入和输出的连接
       stage3(fifo2, out);
   }
   

   • 优点：自然的流式接口，自动处理反压（back-pressure）。
   • 缺点：FIFO 深度需要仔细选择，太深浪费 BRAM，太浅导致 stall。

2. Ping-Pong 缓冲（数组双缓冲）：

   void top(int *in, int *out) {
       int buf1[N], buf2[N];
       #pragma HLS ARRAY_PARTITION ...
       
       #pragma HLS DATAFLOW
       // 奇数次迭代写入 buf1，偶数次写入 buf2
       stage1(in, buf1);   // 写 buf1
       stage2(buf1, buf2); // 读 buf1，写 buf2
       stage3(buf2, out);  // 读 buf2
   }
   

   • 优点：适合块数据处理，可以利用 ARRAY_PARTITION 优化。
   • 缺点：需要手动管理缓冲区的切换逻辑，代码复杂度高。

调试 DATAFLOW 的常见问题：

1. 死锁（Deadlock）：

   • 症状：仿真挂起，或 HLS 报告 "DATAFLOW region may deadlock"。
   • 原因：FIFO 深度不足，或生产者/消费者速率不匹配。
   • 解决：增加 hls::stream 的 depth，或检查是否有未处理的流数据。

2. 单进程限制：

   • 限制：一个函数不能被多个下游函数同时调用（数据流图必须是单源单汇的有向图）。
   • 解决：如果需要广播，使用多个 hls::stream 分别连接。

3. 内存访问冲突：

   • 限制：DATAFLOW 区域内的数组如果同时被多个进程访问，必须是流接口或双缓冲。
   • 解决：将数组转换为 hls::stream，或明确分区为独立的缓冲区。

性能预期与优化检查清单

各版本性能指标（基于典型 NTT 实现的估算）

假设参数：N=256，K=2，目标时钟 300MHz，器件 Versal VP1202。

关键观察：

• Version0→Version1：延迟减少 4 倍，资源增加约 4 倍（UNROLL factor=4 的效果）。
• Version1→Version2：延迟再减半，BRAM 增加 4 倍（ARRAY_PARTITION factor=4 的效果）。
• Version2→Version3：延迟再减半，但控制逻辑和 FIFO 存储增加（DATAFLOW 的开销）。

注意：这些数字是基于典型 NTT 实现的估算。实际数值取决于具体的代码实现、HLS 版本、目标器件和约束设置。

优化检查清单（Checklist）

在提交最终设计前，确认以下各项：

功能正确性

• [ ] C 仿真（C Simulation）通过，输出与参考模型匹配。
• [ ] C 协同仿真（Co-simulation）通过，RTL 行为与 C 模型一致。
• [ ] 所有边界条件测试通过（空输入、最大尺寸输入、异常值）。

性能目标

• [ ] 启动间隔（II）达到目标值（通常是 1）。
• [ ] 总延迟（Latency）满足系统要求（如实时处理的帧率要求）。
• [ ] 吞吐量（Throughput）达到或超过目标（如 samples/second）。

资源约束

• [ ] BRAM 用量在器件容量内（通常留 20% 余量用于布局布线）。
• [ ] DSP 用量在器件容量内。
• [ ] FF 和 LUT 用量合理（过高的 LUT 使用率可能导致时序难以收敛）。

时序收敛

• [ ] 估计时钟频率（Estimated Clock Frequency）达到或超过目标时钟。
• [ ] 关键路径延迟（Critical Path Delay）在时钟周期内。
• [ ] 时序违例（Timing Violations）在可接受范围内（通常要求 WNS ≥ 0）。

代码质量

• [ ] 所有 HLS pragmas 有注释说明目的和理由。
• [ ] 无警告（Warnings）被忽略（特别是综合警告）。
• [ ] 代码符合团队编码规范（命名、缩进、文档）。

总结

Polynomial Vectorization NTT Versions 子模块是 Vitis HLS 教学的典范之作。它通过四个精心设计的版本，展示了从"功能正确的 C++"到"高性能 FPGA 硬件"的完整旅程。

关键收获：

1. 渐进式优化：不要试图一次做对所有优化。每个版本都是一个检查点，让你验证当前策略的效果。

2. 层次化并行：

   • 操作级并行（PIPELINE/UNROLL）：在一个循环内重叠执行。
   • 内存级并行（ARRAY_PARTITION）：消除存储器访问瓶颈。
   • 任务级并行（DATAFLOW）：在不同处理阶段间重叠执行。

3. 数据流思维：硬件设计是数据流设计。你的思考方式应该从"控制流"（指令顺序执行）转变为"数据流"（数据在功能单元间流动）。

4. 权衡无处不在：面积 vs. 速度、编译时间 vs. 优化程度、可调试性 vs. 性能。没有免费的午餐，每个选择都有代价。

下一步：当你掌握了这个子模块，你应该能够：

• 分析任何 C++ 算法，识别其性能瓶颈。
• 选择合适的 HLS 优化策略，系统地改进性能。
• 阅读和修改复杂的 HLS 代码，理解其设计意图。
• 向团队解释你的优化决策，包括权衡分析。

祝你在 HLS 优化的旅程中取得成功！

文档版本：1.0 最后更新：基于 Vitis HLS 2023.2 版本 维护者：FPGA 架构团队