🏠

CPU Reference Baseline Types: Traveling Salesperson Problem (TSP) 参考实现

想象一下，你是一位物流公司的调度员，手头有13个城市的送货点，需要规划一条从起点出发、经过所有城市恰好一次、最后回到起点的最短路线。这就是经典的旅行商问题（Traveling Salesperson Problem, TSP）。本模块提供了一个在CPU上运行的"黄金标准"（Gold Standard）参考实现，它采用暴力枚举所有可能路径的方式来精确求解TSP问题。这个实现的核心价值在于：它不是为了高效，而是为了正确——作为验证后续硬件加速（HLS/FPGA）实现正确性的基准。

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

想象你正在设计一个复杂的 FPGA 加速器来解决旅行商问题。在将算法映射到硬件之前，你必须回答一个关键问题："我的硬件实现算对了吗？"

这就是 cpu_reference_baseline_types 存在的意义。它不是追求性能最优的解决方案，而是一个可信赖的真理源——用简单、直接、易于验证的方式计算 TSP 的最优解，作为验证硬件实现的基准。

问题的复杂性

旅行商问题是经典的 NP-hard 组合优化问题：给定 \(N\) 个城市及其两两之间的距离，找到访问每个城市恰好一次并返回起点的最短环路。当 \(N=13\) 时，可能的路径数量为 \((N-1)! = 479,001,600\) 条（如果考虑固定起点），这已经是一个相当大的搜索空间。

为什么选择暴力枚举？

你可能会问：为什么不使用动态规划（Held-Karp算法，\(O(N^2 2^N)\)）、启发式算法（模拟退火、遗传算法）或近似算法？答案是确定性。硬件验证需要绝对的可重复性和可预测性：

  • 精确性：必须找到全局最优解，而非近似解
  • 可重现性：相同的输入总是产生相同的输出
  • 可审计性：算法逻辑简单透明，便于人工检查

暴力枚举虽然时间复杂度高，但保证了上述所有特性。对于 \(N=13\) 的规模，在现代 CPU 上运行仍然是可行的（几分钟到几十分钟），这使它成为理想的参考实现。

心智模型：如何理解这个模块

要真正理解这个模块，你需要建立以下心智模型：

1. "黄金标准"而非"生产工具"

想象你是一位金匠，正在打造一枚精密的戒指。在开始制作之前，你需要一个标准量块——一个已知精确尺寸的参照物，用来验证你的工具是否校准正确。这个模块就是硬件加速器设计的"标准量块"。

它不是要部署到数据中心的优化求解器，而是一个可信赖的参照系。硬件团队的HLS实现必须产生与它完全一致的结果（或在其容差范围内），否则硬件就是错的。

2. "确定性机器"而非"智能系统"

现代AI系统（如大语言模型）充满不确定性——同样的输入可能因随机种子、温度参数或内部状态而产生不同输出。这个模块正好相反——它是一个确定性机器。

给定相同的13个城市坐标，它总是产生相同的输出，执行相同数量的迭代，消耗相同的CPU周期（在相同硬件上）。这种确定性对于验证至关重要——你不会希望"黄金标准"本身是不稳定的。

3. "内存到内存的转换"而非"交互式系统"

想象数据通过这个模块的方式：它不是交互式的（不会问你问题或等待输入），而是一个纯函数——输入（城市坐标）进去，输出（最短距离）出来，没有副作用。

城市坐标数组 ──[计算距离矩阵]──> 距离矩阵 ──[枚举排列求最短]──> 最短距离值

这种**数据流（Dataflow）**思维对于理解模块的行为至关重要。数据从输入端流入，经过一系列转换阶段，最终从输出端流出，就像水通过管道系统。

架构与数据流

本模块采用单文件、自包含的设计哲学。整个TSP求解器——从城市坐标定义、距离矩阵计算、到全排列枚举——全部封装在一个.cpp文件中。这种设计 intentionally 牺牲了工程上的模块化，换取了绝对的透明性和可移植性：任何人都可以单步调试、验证每一行代码的逻辑，而不需要在头文件和实现文件之间跳转。

flowchart TD A[城市坐标定义
Coord数组] --> B[距离矩阵计算
欧几里得距离] B --> C[距离归一化
uint16范围] C --> D[TSP求解器
getShortestDistance] D --> E[全排列枚举
std::next_permutation] E --> F[路径长度计算
查表累加] F --> G[最小值更新
std::min] G --> H[最短路径长度]

数据流说明：程序从硬编码的美国城市经纬度坐标开始，首先计算所有城市对之间的欧几里得距离，然后将这些浮点距离归一化到16位无符号整数范围以模拟硬件的定点数约束。随后进入核心求解循环：使用C++标准库的std::next_permutation按字典序生成13个城市的所有排列（共62亿种），对每种排列计算路径总长度，并跟踪最小值。整个过程是一个纯函数式的计算管道——除了进度输出外没有任何副作用。

核心抽象与组件详解

城市坐标：二维平面上的点

struct Coord
{
    float x, y;
};

这个结构体代表地理坐标系中的城市位置。采用 float 而非 double 是有意为之——它既保留了足够的精度来计算相对距离，又与后续硬件实现中常用的定点数或单精度浮点数保持一致。

距离矩阵：预计算的查询表

代码中最关键的洞察是距离矩阵的预计算和量化：

// 伪代码示意
for each city pair (i, j):
    preciseDistances[i][j] = sqrt((x_i - x_j)² + (y_i - y_j)²)
    
// 归一化到 uint16_t 范围
quantizedDistance = (preciseDistances[i][j] / maxDist) * UINT16_MAX

这里的设计意图非常精妙：

  1. 欧几里得距离：使用标准的平面几何距离公式
  2. 归一化量化：将所有距离缩放到 16 位无符号整数范围（0~65535）
  3. 整数运算优势：后续的距离累加可以完全使用整数运算，避免浮点开销

这种量化策略是连接软件参考实现与硬件实现的桥梁——FPGA 和 AI Engine 通常更擅长整数运算。

排列生成：字典序遍历

std::array<uint8_t, N> perm{0,1,2,3,4,5,6,7,8,9,10,11,12};

for (uint64_t i = 0; i < factorial(N); ++i) {
    // 评估当前排列...
    std::next_permutation(perm.begin(), perm.end());
}

这里使用 C++ 标准库的 std::next_permutation 来生成所有可能的排列。这是一个优雅的选择：

  • 字典序：保证以确定性的顺序遍历所有排列
  • 原地修改：无需额外的内存分配
  • 终止条件明确：factorial(N) 次迭代后必然覆盖全部搜索空间

路径评估：线性扫描

对于每个排列，计算路径长度是一个简单的线性操作：

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

注意这里只计算了 \(N-1\) 条边（城市间的连接），因为 TSP 的环路特性意味着从最后一个城市回到第一个城市的距离可以通过排列的循环移位来等效表示——实际上，代码评估的是路径而非完整环路，这在寻找最短路径时是等价的。

数据流全景

flowchart TD A[城市坐标定义
Coord数组] --> B[距离矩阵计算
欧几里得距离] B --> C[距离归一化
uint16范围] C --> D[TSP求解器
getShortestDistance] D --> E[全排列枚举
std::next_permutation] E --> F[路径长度计算
查表累加] F --> G[最小值更新
std::min] G --> H[最短路径长度]

数据流说明：程序从硬编码的美国城市经纬度坐标开始，首先计算所有城市对之间的欧几里得距离，然后将这些浮点距离归一化到16位无符号整数范围以模拟硬件的定点数约束。随后进入核心求解循环：使用C++标准库的std::next_permutation按字典序生成13个城市的所有排列（共62亿种），对每种排列计算路径总长度，并跟踪最小值。整个过程是一个纯函数式的计算管道——除了进度输出外没有任何副作用。

核心抽象与组件详解

struct Coord

struct Coord
{
    float x, y;
};
属性 说明
目的 表示二维平面上的城市地理位置
字段 x: 经度或横坐标；y: 纬度或纵坐标
类型选择 float 提供约 7 位有效数字，足以表示 GPS 坐标的精度需求，同时与硬件实现的定点数格式兼容

这是一个 POD（Plain Old Data）结构体，遵循 Rule of Zero——没有自定义构造函数、析构函数或赋值操作符，完全依赖编译器生成的默认行为。这意味着它可以安全地进行逐字节复制、在数组中连续存储，并且没有隐式的资源管理开销。

constexpr long int factorial(const int N)

constexpr long int factorial(const int N)
{
    return (N == 1 ? 1 : N * factorial(N-1));
}

这是一个编译期递归函数，利用 C++11 引入的 constexpr 关键字。

为什么用递归而非迭代？ 在这个场景下，递归的深度最多为 13，不会造成栈溢出。更重要的是，constexpr 强制要求函数可以在编译期求值，编译器会将 factorial(13) 直接替换为常量 6227020800，运行时完全没有函数调用开销。

返回值类型 long int：在大多数 64 位平台上，这是 64 位有符号整数，可以容纳 \(13!\)（约 62 亿）。但如果 \(N\) 增大到 21，21! 将超过 64 位有符号整数的范围（约 \(9.2 \times 10^{18}\)），导致未定义行为。

getShortestDistance()

这是模块的核心算法函数。

参数：

  • distances: 预计算的 \(N \times N\) 距离矩阵，以 std::array 扁平化存储

返回值：

  • uint32_t: 最短路径的总距离（量化后的整数值）

内部状态：

  • perm: 当前的城市访问顺序排列
  • ret: 截至目前找到的最短距离

复杂度分析：

  • 时间复杂度：\(O(N! \times N)\) —— 遍历 \(N!\) 个排列，每个排列计算 \(N-1\) 条边的距离和
  • 空间复杂度：\(O(N)\) —— 仅需要一个长度为 \(N\) 的排列数组

进度指示器的巧妙设计：

if (i % (factorial(N)/500) == 0) 
    std::cout << i*1000/factorial(N)/10.0 << "%\r" << std::flush;

这段代码每完成 0.2% 的进度就更新一次终端输出：

  • \r 是回车符，将光标移回行首，实现"原地更新"效果
  • std::flush 确保立即输出，而不是缓冲等待
  • 百分比计算通过整数运算避免浮点精度问题

依赖关系与架构角色

本模块的依赖

头文件 用途
<vector> （实际未使用，可能是历史遗留或未来扩展预留）
<array> std::array —— 固定大小的栈分配数组，零开销抽象
<cmath> std::sqrt, std::pow —— 数学运算
<algorithm> std::next_permutation, std::min
<iostream> std::cout, std::flush —— 进度输出

谁依赖本模块？

根据模块树分析，本模块位于：

Hardware_Acceleration_Design_Tutorials
└── traveling_salesperson_hls_and_reference_flow
    └── cpu_reference_baseline_types (本模块)

同级模块包括：

架构角色：本模块是整个 TSP 教程的软件黄金参考（Software Golden Reference）。它的输出将被用于验证 HLS 实现的正确性。任何硬件实现的输出如果与本模块的结果不一致，就说明存在 Bug。

设计决策与权衡

1. 整数量化 vs 浮点运算

决策：将浮点距离量化为 16 位无符号整数。

权衡：

  • ✅ 性能：整数加法比浮点加法更快，尤其在 FPGA 上
  • ✅ 确定性：整数运算完全可预测，没有浮点舍入误差的累积问题
  • ❌ 精度损失：归一化过程引入了量化误差，但对于 TSP 的排序性质影响极小

为什么可以接受精度损失？ TSP 关心的是路径长度的相对排序，而非绝对数值。只要量化保持距离的单调性（即如果 \(d_1 < d_2\)，则 \(q(d_1) < q(d_2)\)），最优路径的选择就不会改变。

2. 栈分配 vs 堆分配

决策：大量使用 std::array 和固定大小数组，避免动态内存分配。

std::array<uint8_t, N> perm;           // 栈分配
std::array<unsigned int, N*N> distances; // 栈分配（N=13 时为 676 个整数，约 2.7KB）

权衡：

  • ✅ 确定性延迟：没有 malloc 的不确定性，适合实时系统参考
  • ✅ 缓存友好：栈数据通常已在 L1/L2 缓存中
  • ❌ 栈空间限制：如果 \(N\) 显著增大，可能导致栈溢出

3. 暴力枚举 vs 启发式算法

决策：使用 \(O(N!)\) 的暴力枚举。

权衡：

  • ✅ 正确性保证：找到全局最优解
  • ✅ 实现简单：不到 50 行核心代码
  • ❌ 可扩展性差：\(N=15\) 时计算量将是 \(N=13\) 的 210 倍

设计意图：这是一个教学用的参考实现，不是生产环境的产品。它的价值在于可验证性，而非可扩展性。

4. 编译期计算 vs 运行期计算

决策：使用 constexpr 进行阶乘计算。

constexpr long int factorial(const int N);  // 编译期求值
constexpr int N = 13;                       // 编译期常量

权衡：

  • ✅ 零运行时开销：factorial(N) 直接被替换为常量
  • ✅ 类型安全：编译器可以在编译期捕获某些错误
  • ❌ 灵活性降低：\(N\) 必须在编译期确定，无法运行时配置

使用指南与注意事项

如何修改城市数量

修改 constexpr int N 的值即可：

constexpr int N = 10;  // 改为 10 个城市

注意：

  • 确保 cities 数组至少有 \(N\) 个元素
  • \(N\) 增大时，运行时间呈阶乘增长，请谨慎调整
  • \(N > 20\) 时，factorial(N) 将超出 64 位整数范围

如何更换城市坐标

直接修改 cities 数组：

const Coord cities[] = {
    {latitude_1, longitude_1},
    {latitude_2, longitude_2},
    // ... 至少 N 个城市
};

坐标使用 (x, y) 格式，其中 x 通常对应经度，y 对应纬度。

如何解读输出

程序输出一个整数，代表最短路径的量化距离总和。要转换为实际距离：

actual_distance = output * maxDist / UINT16_MAX;

注意 maxDist 是初始化阶段计算的原始最大距离。

边缘情况与潜在陷阱

1. 整数溢出风险

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

每条边的距离最大为 65535（uint16_t 最大值），\(N-1=12\) 条边的累加最大值为 \(786,420\)，远低于 uint32_t 的上限（约 42 亿）。但如果：

  • 修改量化方案使用更大的范围
  • 或者 \(N\) 显著增大

则需要考虑升级到 uint64_t。

2. 排列总数的整数类型

for (uint64_t i = 0; i < factorial(N); ++i)

factorial(13) = 6,227,020,800，这在 32 位有符号整数范围（约 21 亿）之外，但在 64 位无符号整数范围内。如果误用 uint32_t，将导致无限循环。

3. next_permutation 的前提条件

std::next_permutation 要求输入序列是已排序的（升序），才能生成完整的排列集合。代码中：

std::array<uint8_t, N> perm{0,1,2,3,4,5,6,7,8,9,10,11,12};  // 已排序

如果初始排列不是有序的，某些排列将永远不会被生成。

4. 浮点比较与量化

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

这里涉及浮点除法和乘法。虽然现代 IEEE 754 实现通常很稳定，但在极端情况下（如所有距离几乎相等），浮点舍入可能导致不同的距离被量化为相同的整数值。这在 TSP 中通常不是问题，但在其他应用中可能需要更精细的量化策略。

5. 硬编码的城市数量

代码中有 15 个城市坐标定义，但只使用 \(N=13\) 个。如果减小 \(N\)，没有问题；但如果增大 \(N\) 超过 15，将访问数组越界，导致未定义行为。

与硬件实现的关联

本模块的设计充分考虑了向硬件移植的需求：

  1. 整数运算主导：量化后的距离矩阵使核心计算完全基于整数加法，FPGA 的 DSP48 单元可以高效处理

  2. 固定数据结构：std::array 的语义与硬件中的 BRAM/URAM 块存储相对应，大小在编译期确定

  3. 确定性执行：没有动态内存、没有异常、没有虚函数——这些都是在 HLS 中难以高效实现的 C++ 特性

  4. 模块化接口：getShortestDistance 函数接受扁平化的距离矩阵，这种数据布局便于 DMA 传输到 FPGA

后续 HLS 实现通常会：

  • 保留相同的距离量化方案，确保比特级一致的结果
  • 将排列生成并行化（例如使用分支定界或遗传算法的硬件版本）
  • 使用流水线技术加速距离累加

总结

cpu_reference_baseline_types 是一个精心设计的教学参考实现。它不追求算法上的创新，而是通过简洁、确定、可验证的实现，为复杂的硬件加速设计提供可靠的 correctness baseline。

理解这个模块的关键不在于掌握 TSP 算法本身，而在于领会其工程哲学：在异构计算系统设计中，软件参考实现是连接算法理论与硬件实现的桥梁，它的价值在于可信度而非性能。

On this page