🏠

traveling_salesperson_hls_and_reference_flow 模块深度解析

一句话概括

本模块是一个完整的参考设计流程（Reference Flow），展示了如何将一个计算密集型的组合优化问题——旅行商问题（TSP）——从CPU软件实现映射到FPGA硬件加速。它通过对比CPU黄金参考模型与HLS综合后的RTL内核，为开发者提供了算法验证、性能优化和硬件实现的全套方法论。

问题空间与设计动机

为什么是TSP？

旅行商问题（Traveling Salesperson Problem）是计算机科学中最经典的NP-hard组合优化问题之一：给定\(N\)个城市及其两两之间的距离，寻找一条访问每个城市恰好一次并返回起点的最短环路。

对于\(N\)个城市，可能的路径数为\((N-1)!/2\)（排除旋转和反向对称）。当\(N=13\)时，需要评估超过\(3.1 \times 10^9\)种排列；当\(N=5\)时，仅需\(12\)种排列。

为什么选择暴力搜索？

你可能会问：既然TSP有动态规划（Held-Karp算法，\(O(N^2 2^N)\)）和众多近似算法，为什么要用最笨的穷举法？

答案在于这是一个硬件设计教程，而非算法优化竞赛。

  1. 内存访问模式可预测：暴力搜索对距离矩阵的访问是确定性的，适合流式处理
  2. 并行度极高：每个排列的评估完全独立，天然适合FPGA的大规模并行架构
  3. 控制逻辑简单：无需复杂的分支预测或递归栈管理，适合HLS工具生成高效流水线
  4. 结果可验证：黄金参考模型（CPU实现）与硬件实现的结果必须完全一致，便于验证

设计目标

本模块的核心教育目标是展示从算法到硅片的完整设计流程：

  1. 功能验证：建立可信的黄金参考模型（Golden Reference）
  2. 接口抽象：定义硬件友好的数据流接口（AXI4-Stream）
  3. 综合优化：展示如何从基线实现（Baseline）到优化实现（Optimized）的演进
  4. 构建自动化：提供可复现的Vitis HLS构建脚本

心智模型与核心抽象

想象你正在设计一条工业流水线来处理定制产品（TSP路径评估）：

类比：汽车装配线与定制路线评估

CPU黄金参考模型就像一位技艺精湛的工匠在工作台前手工组装汽车：

  • 他能处理极其复杂的车型（\(N=13\)），因为他有无限的耐心和时间
  • 他按顺序评估每一条可能的装配顺序（排列），记录下最高效的方案
  • 工作速度较慢，但结果绝对可靠，是检验其他方法的最终标准

HLS硬件内核则像一条高度自动化的装配流水线：

  • 流水线专为特定车型设计（\(N=5\)），每个工位（流水线阶段）只负责一小部分工作
  • 工人（硬件逻辑）不能思考，但动作极快，且多个工位可以同时处理不同的汽车（并行）
  • 原材料（距离矩阵）通过传送带（AXI4-Stream）连续送入，成品（最短距离）从末端流出

核心抽象层

抽象层 职责 关键技术
算法层 TSP问题的数学建模与求解 排列生成、路径长度计算、最小值追踪
黄金参考层 提供可信的软件基线 C++标准库、std::next_permutation、浮点精度管理
硬件抽象层 定义硬件友好的接口与数据类型 hls::stream、定点数/整数距离、ap_uint
微架构层 HLS制导下的流水线与并行化 DATAFLOW、PIPELINE、UNROLL、ARRAY_PARTITION
系统集成层 与Vitis流程的对接 Tcl脚本构建、IP打包、时序约束

架构全景与数据流

系统架构图

graph TB subgraph "Software Domain" A[CPU Golden Reference
main_gold.cpp] -->|Generates| B[Distance Matrix
uint16_t array] A -->|Computes| C[Reference Shortest Distance
Ground Truth] end subgraph "Hardware Abstraction Layer" B -->|Streamed via| D[hls::stream uint16_t
AXI4-Stream Interface] E[HLS Kernel tsp] -->|Produces| F[Shortest Distance Result
unsigned int] end subgraph "HLS Build System" G[hls.tcl
Baseline Build] -->|Synthesizes| H[Baseline RTL
IP Catalog] I[hls_opt.tcl
Optimized Build] -->|Synthesizes| J[Optimized RTL
DATAFLOW/UNROLL] end E -.->|Instantiated by| G E -.->|Instantiated by| I D -.->|Input to| E F -.->|Output from| E

数据流详解

1. 距离矩阵的生成与表示（CPU侧）

在main_gold.cpp中，距离矩阵的生成是一个精心设计的归一化过程：

// 真实世界坐标（美国城市经纬度）
const Coord cities[] = {{40.7127837, -74.0059413},  // New York
                        {34.0522342, -118.2436849}, // Los Angeles
                        ...};

// 欧几里得距离计算
float dist = sqrt(pow(cities[i].x-cities[j].x, 2) 
                + pow(cities[i].y-cities[j].y, 2));

// 关键：归一化到uint16_t范围
ret[i] = (preciseDistances[i]/maxDist) * numeric_limits<uint16_t>::max();

为什么这样做？ 这是**定点化（Fixed-point Conversion）**的关键步骤。硬件实现通常避免浮点运算（面积大、延迟高），而是使用定点数或整数。通过将距离归一化到16位无符号整数范围（0-65535），我们：

  • 保留了足够的精度（16位足以区分路径长度差异）
  • 使硬件可以使用整数加法和比较（而非浮点）
  • 确保了CPU黄金参考与硬件实现之间的位精确一致性（Bit-exact Consistency）

2. AXI4-Stream数据流（硬件接口侧）

在tsp.h中定义的硬件接口使用了Vitis HLS的流式抽象：

void tsp(hls::stream<uint16_t>& streamDistances, 
         unsigned int& shortestDistance);

这对应硬件层面的AXI4-Stream协议：

  • TDATA：16位距离数据（映射到uint16_t）
  • TVALID/TREADY：握手机制，由HLS工具自动生成
  • TLAST：标识最后一笔数据（矩阵传输结束）

数据流顺序是**行优先（Row-major）**的：矩阵的第0行所有元素，然后是第1行，依此类推。这种顺序与排列评估时的访问模式相匹配（评估一个排列时，需要访问perm[0]→perm[1], perm[1]→perm[2]等边）。

3. 排列评估流水线（内核微架构侧）

虽然tsp.cpp的实现代码未提供，但从上下文可以推断其微架构采用嵌套流水线结构：

外层循环：遍历所有排列（N! 次迭代）
    ↓ 启动间隔（II）目标：尽可能低
内层循环：计算当前排列的总距离（N-1 次累加）
    ↓ 完全展开（UNROLL）或流水线化（PIPELINE）
    读取距离矩阵[perm[i]][perm[i+1]]
    累加到路径长度
比较并更新最小值（带条件执行）

DATAFLOW的应用：在优化版本（tsp_opt.cpp）中，可能将算法分解为三个并发阶段：

  1. 排列生成器：产生下一个排列的索引序列
  2. 距离计算引擎：接收索引，查询距离矩阵，累加路径长度
  3. 最小值追踪器：接收路径长度，维护全局最小值

这种分解允许三个阶段以流水线方式并发执行：当计算引擎在处理排列\(i\)时，生成器已经在准备排列\(i+1\)，而追踪器在处理排列\(i-1\)的结果。

关键设计决策与权衡

1. \(N=13\)（CPU）vs \(N=5\)（硬件）

决策：CPU黄金参考使用13个城市（39亿种排列），而HLS内核使用5个城市（120种排列）。

权衡分析：

  • 正确性验证：\(N=13\)的CPU实现可以运行数小时生成可信的参考结果。这个结果用于验证硬件实现的算法正确性（即使硬件只用\(N=5\)，其算法逻辑与\(N=13\)一致）。
  • 硬件可行性：\(N=5\)意味着距离矩阵是\(5\times5=25\)个元素，可以全部存储在片上BRAM（块RAM）中，访问延迟为1个时钟周期。如果\(N=13\)，矩阵有169个元素，虽然也能放入BRAM，但排列评估的复杂度（阶乘增长）会使硬件处理时间过长，失去实时加速的意义。
  • 教学清晰度：\(N=5\)足够小，可以手动验证所有120种排列的结果，便于调试和理解。\(N=13\)则展示了算法在真实数据集上的表现。

2. 距离归一化：浮点→定点

决策：将欧几里得距离从浮点（float）转换为16位无符号整数（uint16_t），通过除以最大距离并缩放至65535。

权衡分析：

  • 精度损失：浮点32位有~24位有效精度，定点16位只有16位。但城市间距离的相对差异通常不需要24位精度；16位足以区分不同路径的长度差异。
  • 硬件资源：在Xilinx FPGA上，浮点加法/比较需要专用的DSP48单元和大量LUT，且延迟通常为3-5个时钟周期。16位整数加法可以使用LUT进位链，延迟为1个周期，且逻辑资源消耗仅为浮点的1/10。
  • 一致性保证：归一化确保了CPU和硬件使用完全相同的数值表示，消除了因浮点舍入差异导致的"假阴性"（硬件结果正确但被误判为错误）。

3. AXI4-Stream vs AXI4-Full接口

决策：使用hls::stream（映射到AXI4-Stream）而非m_axi（AXI4-Full）传输距离矩阵。

权衡分析：

  • 数据局部性：距离矩阵在TSP求解过程中会被反复访问（每个排列需要N-1次查找）。如果使用m_axi，每次查找都需要访问外部DRAM，延迟高达数十到数百个时钟周期，成为性能瓶颈。
  • 流式读取：通过hls::stream，主控（Host）可以将矩阵一次性"推送"给内核，内核将其存储到片上BRAM（通过HLS工具推断的本地数组）。后续所有访问都在片上完成，延迟为1周期。
  • 协议复杂性：AXI4-Stream是单向的、无地址的，逻辑简单，适合数据流传输。AXI4-Full需要地址生成、突发长度计算、应答处理，增加了内核控制逻辑的复杂性。
  • 局限性：选择AXI4-Stream意味着矩阵大小必须在编译时确定（或至少受限于BRAM容量），且内核在启动前必须接收完整矩阵。对于需要随机访问外部存储的超大规模问题，这种接口不适用。

4. 基线（Baseline）vs 优化（Optimized）构建流程

决策：提供hls.tcl（基线）和hls_opt.tcl（优化）两套构建脚本。

权衡分析：

  • 教学渐进性：基线版本使用最直接的C++代码，HLS工具生成的硬件逻辑简单但效率低（可能II较大，面积较大）。这为学习者提供了一个"起点"，让他们理解算法如何映射到硬件。
  • 优化策略展示：优化版本（tsp_opt.cpp）应用了DATAFLOW、PIPELINE、UNROLL、ARRAY_PARTITION等HLS指令，展示了如何通过代码重构和编译制导提升吞吐率。两套脚本的QoR（Quality of Results）对比是HLS教学的核心。
  • 验证负担：维护两套实现意味着任何算法变更都需要在基线和优化版本中同步更新，且两者必须与CPU黄金参考产生相同结果。这是为了教学清晰性而接受的维护成本。

新贡献者必读：陷阱与隐式契约

1. 硬编码常量的隐蔽依赖

模块中存在两个不同的N定义：

  • main_gold.cpp中的constexpr int N = 13;
  • tsp.h中的const int N = 5;

陷阱：如果你在main_gold.cpp中修改了N但没有同步修改code/tsp.cpp中的实现（未提供但隐含存在），距离矩阵的生成和使用将不一致。更重要的是，tsp.h中的N决定了硬件内核的接口契约——主控程序必须准确发送\(N \times N\)个uint16_t数据，否则内核将挂起或产生未定义行为。

隐式契约：任何修改N的操作必须同步更新以下所有位置：

  • main_gold.cpp中的N和cities数组大小
  • tsp.h（及其实现文件）中的N
  • 距离矩阵的生成逻辑（确保缩放因子maxDist正确计算）
  • 主机端的数据发送循环（确保发送恰好\(N^2\)个元素）

2. 定点数缩放的精度边界

距离归一化公式为：

ret[i] = (preciseDistances[i]/maxDist) * numeric_limits<uint16_t>::max();

陷阱：当preciseDistances[i]远小于maxDist时，除法结果很小，乘以65535后可能产生下溢（Underflow），多个小距离被量化为相同的整数值，导致信息损失。这在城市分布极不均匀时（例如所有城市聚集在一个小区域，只有一个城市很远）会导致硬件计算的最短路径与浮点参考不一致。

隐式契约：输入的城市坐标应满足相对均匀分布，确保最大距离与最小距离的比值不超过\(2^{16}\)（约65536），这在地理坐标表示的城市间距离中通常成立，但如果使用自定义坐标系，需验证此条件。

3. HLS数据流的阻塞语义

tsp函数的签名使用了hls::stream引用：

void tsp(hls::stream<uint16_t>& streamDistances, unsigned int& shortestDistance);

陷阱：在HLS生成的RTL中，对streamDistances的读取是阻塞式的——如果FIFO为空，内核将停滞等待数据。如果主机端发送的数据量不等于\(N \times N\)（例如由于软件bug少发了一个元素），内核将永远挂起在等待状态，表现为系统"死锁"。

隐式契约：

  • 主机必须在启动内核前准备好完整的数据流，或在数据流模式下确保生产速率匹配消费速率
  • 测试平台（Testbench）必须使用完全相同的N值生成激励数据
  • 在仿真阶段，应监控streamDistances.empty()信号，确保不会出现意外的空读

4. 构建脚本中的外部依赖

hls.tcl和hls_opt.tcl中包含以下外部依赖声明：

# 隐含的依赖关系
External deps: AI_Engine_Development.AIE.Design_Tutorials.02-super_sampling_rate_fir.DualSSR16_hw.sw.Makefile.aie_control_xrt.cpp

陷阱：虽然这些Tcl脚本本身是自包含的（使用open_project、set_top等标准命令），但模块树中显示的外部依赖暗示了在某些集成场景下，可能需要与AI Engine开发教程中的XRT控制代码兼容。如果你在移植此设计到非Vitis环境（例如纯Vivado流程），可能需要手动替换这些依赖。

隐式契约：

  • 构建脚本假设标准Vitis HLS 202x.x环境可用
  • 设备型号xcvu9p-flga2104-2-i（Virtex UltraScale+）是硬编码的，移植到其他器件需要修改set_part
  • 时钟周期3.0ns（333MHz）是针对该器件的保守估计，优化版本可能尝试更高频率

5. 排列算法的数值稳定性

在main_gold.cpp中，排列通过std::next_permutation生成，这是一个基于字典序的算法。距离累加使用uint32_t：

uint32_t distance = 0;
for (int j = 0; j < N-1; ++j)
    distance += distances[perm[j]*N+perm[j+1]];

陷阱：虽然使用uint32_t对于N=13和最大距离65535是安全的（最大路径长度\(12 \times 65535 = 786420 < 2^{32}\)），但如果未来扩展N或改变定点数范围，可能发生整数溢出。溢出将导致距离比较错误，产生完全错误的"最短路径"。

隐式契约：任何对N或距离数据类型的修改必须重新验证：

最大路径长度 = (N-1) * max_distance_value < 距离累加器的数据类型上限

对于当前配置：\((13-1) \times 65535 = 786420 \ll 4294967295\)（uint32_t上限），安全余量充足。

子模块架构与导航

本模块被划分为三个逻辑子模块，每个子模块负责设计流程的不同阶段：

子模块 职责 核心文件
cpu_reference_baseline_types 提供算法黄金参考模型，定义基础数据结构（Coord、距离矩阵类型），实现基于排列穷举的精确求解器 main_gold.cpp
tsp_kernel_interface_data_types 定义硬件内核的接口契约，包括流式数据类型（hls::stream）、定点距离表示，以及硬件优化的算法版本 tsp.h
hls_synthesis_and_optimized_build_flows 提供Vitis HLS的构建自动化脚本，支持基线（功能正确）和优化（性能调优）两种综合策略，包含时序约束、IP打包和实现流程配置 hls.tcl, hls_opt.tcl

跨模块依赖关系

graph LR A[cpu_reference_baseline_types] -->|提供算法spec与验证数据| C[hls_synthesis_and_optimized_build_flows] B[tsp_kernel_interface_data_types] -->|定义硬件接口与数据类型| C C -->|生成| D[RTL IP Core] D -->|集成到| E[Vitis System Design] F[AI_Engine_Design_Tutorials
Super_Sampling_Rate_FIR] -.->|XRT控制代码参考| E

注意：模块树显示本模块对外部AI Engine开发教程存在间接依赖。这通常意味着在完整的系统集成场景中，可能需要复用该教程中的XRT（Xilinx Runtime）主机代码框架来控制TSP内核的执行（数据搬运、内核启动、结果回收）。对于纯HLS学习和仿真阶段，此依赖可忽略。

总结：写给新加入的开发者

这个模块不仅仅是一个TSP求解器——它是硬件设计方法论的教学载体。当你阅读这些代码时，不要只关注"它计算了什么"，而要思考"为什么这样组织"：

  1. 为什么有两个N？ 因为硬件设计首先要解决"能不能放下"和"能不能算完"的问题，其次才是"算得多快"。

  2. 为什么用流接口？ 因为在FPGA的世界里，数据是像水流一样连续流动的，而不是像CPU那样随机访问内存。学会用流的思维思考，是成为FPGA工程师的关键一步。

  3. 为什么要定点化？ 因为硬件资源是有限的，每一比特都要精打细算。定点化是算法工程师与硬件架构师之间的桥梁。

当你准备好深入代码细节时，从cpu_reference_baseline_types开始，理解算法如何工作；然后阅读tsp_kernel_interface_data_types，观察接口如何抽象；最后研究hls_synthesis_and_optimized_build_flows，掌握从C++到比特流的魔法。

欢迎来到硬件加速的世界。

On this page