Alveo U250 FPGA 开发实战：向量加法与 Falcon 图向量检索

最近有了结合 FPGA 硬件做研究的想法，也在 Alveo U250 上做了一轮 Falcon 图向量检索的复现实验。这篇博客整理了开发流程、源码阅读和实验中遇到的问题，方便后续继续尝试自己的设计。

把已有的 CPU 算法搬到 FPGA 上，需要重新考虑数据如何流动：输入怎样进入板卡，计算能否连续接收数据，随机访存会在哪里造成等待，一次查询又有多少时间花在传输上。要回答这些问题，可以先跑通一个简单算子，完成结果校验和计时，再逐步修改计算与访存结构。

这篇文章以 Alveo U250 为开发平台，先用向量加法串起主机、板载 DDR 和计算单元，再结合 Falcon 图向量检索，讨论随机访存、候选队列和反馈流水线。示例使用 Linux、Vitis 2023.2 和配套 XRT，通过命令行完成构建与运行。

FPGA 的硬件结构与编程方式

FPGA 的全称是 Field-Programmable Gate Array，中文通常译为现场可编程门阵列。芯片中预先制造了可配置的逻辑单元、寄存器和互连，开发者通过配置数据决定这些单元实现什么逻辑，以及它们怎样连接。设计完成后，工具生成 bitstream，将配置加载到器件中，便建立了对应的数字电路。在 U250 的应用加速流程中，运行时通过 .xclbin 加载这些配置。

USTC Vlab 的《FPGA 原理》 从逻辑门讲起，介绍了查找表和可编程互连的工作原理。¹查找表 LUT 可以保存一个布尔函数的真值表，输入信号作为地址，选出对应的输出。例如，两输入与门只需要存储四种输入组合对应的四个结果。触发器则在时钟边沿保存状态，把组合逻辑连接成能够逐拍推进的电路。教程中的 Slice 和 CLB 结构以 Spartan-6 为例，本文使用的 U250 属于后续的 UltraScale+ 器件平台，具体资源结构应查对应器件文档。

实际设计还会使用专门的硬件资源。DSP 单元适合实现乘法、乘加等运算，BRAM 和 URAM 提供片上存储，LUT 和触发器则承担组合逻辑、控制状态和部分缓冲。在后文的图搜索中，距离计算、候选队列、Bloom filter 和 FIFO 都需要映射到这些资源上。队列容量增加会消耗更多存储或逻辑资源，数据访问的端口数与布局也会影响模块能否同时工作。阅读综合报告时，可以据此判断 LUT、FF、DSP、BRAM 和 URAM 用量为何发生变化。

计算在这些资源上的执行过程，可以用流水线来理解。假设一个计算包含读取输入、乘法、加法和写出结果，硬件可以把这些操作组织成若干流水级，让不同输入同时处于不同阶段。某个输入经过整条流水线需要的周期数称为 latency，相邻两次迭代能够启动的最小间隔称为 initiation interval，简称 II。例如，一条延迟为 20 拍、II 为 1 的流水线，在输入持续到达且下游没有阻塞时，可以每拍接收一份新输入；每份输入仍要经过 20 拍才产生结果。II 因而直接关系到循环持续处理数据的速率。

并行通道数决定同一时刻可以处理多少份工作。把一条加法通路复制成 16 条，可以让 16 对元素并行相加，同时也要求存储接口及时提供 16 对操作数并接收结果。流水化主要让不同迭代重叠，展开循环则允许多个迭代中的操作并行实现。两者都受数据依赖、运算资源和存储访问能力限制。²后面的向量加法会同时用到 PIPELINE、UNROLL 和 512 位接口，可以结合代码观察它们如何配合。

设计这条通路可以使用 Verilog、SystemVerilog 等硬件描述语言，直接描述寄存器及其逻辑关系，也可以使用高层次综合 HLS，从可综合的 C/C++ 生成寄存器传输级描述，即 RTL。AMD 的 Vitis HLS 2023.2 官方教程介绍了从 C/C++ 到 RTL，再导出 Vitis kernel 的过程。³HLS 会根据运算、依赖与约束安排执行周期、分配硬件资源，并生成控制逻辑。数组会映射到存储资源，函数参数会形成硬件接口，循环中的运算则按调度结果复用资源或并行执行。

HLS 适合用已有的 C/C++ 算法开始实验，但 kernel 代码需要满足综合约束。例如，硬件存储的规模通常需要在综合时确定，动态分配内存和任意递归等软件写法不能直接照搬。主机程序仍然可以使用常规 C++、动态内存、文件系统和运行时库。示例中的 host.cpp 负责组织数据和提交任务，vadd.cpp 定义 FPGA 上的计算逻辑。

U250 是通过 PCIe 接入服务器的加速卡。CPU 负责准备输入，XRT 管理设备、缓冲区与任务提交。DMA 在主机内存和板载 DDR 之间搬运数据。FPGA 上的 kernel 从 DDR 读取输入，完成计算后将结果写回。板卡平台提供 PCIe、存储控制器等基础设施，应用 kernel 使用平台暴露的接口。在这个流程中，AXI 是模块之间传输数据和控制信息的接口协议；后文的 m_axi 用于让 kernel 主动读写存储，s_axilite 用于传递地址、标量参数和启动等控制信息。

从源码得到可加载的硬件还需要综合、布局和布线。综合将逻辑映射到器件资源，布局确定资源的位置，布线连接它们，时序分析检查信号能否在时钟周期内到达。一次完整硬件构建可能需要较长时间，因此开发通常先做功能仿真，再看 HLS 的调度与资源报告，最后进行实现和板上测量。图向量检索还需要处理随机读取、重复访问，以及候选队列与计算模块之间的依赖。可以先用简单算子熟悉开发流程，再到 Falcon 中观察这些问题。

U250 开发环境配置

U250 的板载存储是 DDR4。编写程序时，需要同时考虑主机与板卡之间的 PCIe 传输，以及计算单元与 DDR bank 之间的访问。增加并行计算通道会提高 DDR 带宽需求，而一次请求能缩短多少，还取决于 PCIe 传输占了多少时间。

开始编译前，需要确认 Vitis、XRT 和开发平台与板卡 shell 兼容。.xpfm 描述编译时的平台，.xclbin 则包含应用 kernel 及其连接等信息。平台与板卡 shell 的兼容关系应按该平台的发布说明确认。⁴AMD 的 Vitis 2023.2 hello_world 示例默认列出的 U250 平台是 xilinx_u250_gen3x16_xdma_4_1_202210_1⁵；可以据此查找平台包，并核对它是否与服务器上的 shell 匹配。

下面的命令采用以下工具与平台配置：

• 开发工具：Vitis/Vivado 2023.2。
• 运行时：XRT 2.16.204（2023.2 分支）。
• 开发平台：xilinx_u250_gen3x16_xdma_4_1_202210_1。

下面加载工具环境并检查设备，路径和 PCIe 总线／设备／功能地址（bus/device/function，BDF）按自己的服务器修改。xbutil validate 会运行板卡测试，应等设备空闲后执行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

source /path/to/Xilinx/Vitis/2023.2/settings64.sh
source /opt/xilinx/xrt/setup.sh

v++ --version
xbutil examine
export DEVICE_BDF=0000:01:00.1  # 按 xbutil examine 的输出填写
xbutil examine --device "$DEVICE_BDF" --report platform
xbutil validate --device "$DEVICE_BDF"

export PLATFORM=/opt/xilinx/platforms/xilinx_u250_gen3x16_xdma_4_1_202210_1/xilinx_u250_gen3x16_xdma_4_1_202210_1.xpfm
platforminfo --platform "$PLATFORM"

检查结果时，把 shell 标识、平台路径、Vitis/XRT 版本、驱动状态和 PCIe 链路状态一起保存。PCIe 插槽的物理长度无法说明实际协商出的速率与宽度；DMA 明显慢于预期时，可以先检查链路是否降速或降宽。后文示例主机程序选择设备索引 0，多卡服务器应修改为目标设备的索引，并核对它与 BDF 的对应关系。

向量加法的 HLS 与 XRT 实现

先计算 c[i] = a[i] + b[i]，元素类型为 32 位无符号整数，加法按模 $2^{32}$ 回绕。这个例子只需要读两个数组、写一个数组，容易核对计算结果，也便于观察不同访存配置带来的影响。

将下面代码保存为 vadd.cpp。一个 ap_uint<512> 容纳 16 个元素，外层循环处理一个宽字，内层循环展开为 16 路加法。三个 m_axi bundle 分别产生独立的 AXI 主接口，具体连接到哪块 DDR 由链接配置指定。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <ap_int.h>

extern "C" void vadd(const ap_uint<512>* a,
                     const ap_uint<512>* b,
                     ap_uint<512>* c,
                     unsigned int nwords) {
#pragma HLS INTERFACE m_axi port=a offset=slave bundle=gmem0
#pragma HLS INTERFACE m_axi port=b offset=slave bundle=gmem1
#pragma HLS INTERFACE m_axi port=c offset=slave bundle=gmem2
#pragma HLS INTERFACE s_axilite port=a bundle=control
#pragma HLS INTERFACE s_axilite port=b bundle=control
#pragma HLS INTERFACE s_axilite port=c bundle=control
#pragma HLS INTERFACE s_axilite port=nwords bundle=control
#pragma HLS INTERFACE s_axilite port=return bundle=control

    for (unsigned int w = 0; w < nwords; ++w) {
#pragma HLS PIPELINE II=1
        const ap_uint<512> aw = a[w];
        const ap_uint<512> bw = b[w];
        ap_uint<512> cw = 0;
        for (int lane = 0; lane < 16; ++lane) {
#pragma HLS UNROLL
            const ap_uint<32> av = aw.range(32 * lane + 31, 32 * lane);
            const ap_uint<32> bv = bw.range(32 * lane + 31, 32 * lane);
            const ap_uint<32> sum = av + bv;
            cw.range(32 * lane + 31, 32 * lane) = sum;
        }
        c[w] = cw;
    }
}

PIPELINE II=1 给出了每拍启动一次外层迭代的目标。综合报告会说明实际达到的 initiation interval；外部存储的停顿还会影响板上吞吐。这个 kernel 的运行频率为 300 MHz，可用 xclbinutil --info --input build/hw/vadd.xclbin 查看。若每拍处理一个 64 字节宽字，单端口的理论带宽为 $64\times300\times10^6=19.2$ GB/s，与一条 DDR4-2400 通道的理论带宽相当；三个端口合计为 57.6 GB/s。访存停顿会降低实际吞吐。

将下面配置保存为 connectivity.cfg。这里假设平台暴露了 DDR[0]、DDR[1] 和 DDR[2]，应先用平台信息核对这些名称。

1
2
3
4
5

[connectivity]
nk=vadd:1:vadd_1
sp=vadd_1.a:DDR[0]
sp=vadd_1.b:DDR[1]
sp=vadd_1.c:DDR[2]

独立的 bundle 为三路访问提供了各自的 AXI 接口，映射到不同 bank 则进一步分散存储控制器的负载。后续可以只修改这份配置，将三个参数都放入 DDR[0]，比较同一份计算逻辑在两种映射下的运行时间。这个实验能直接说明应用是否受到 bank 争用影响。

主机为尾部不足 16 个元素的输入补零，并分配完整宽字所需的空间。kernel 的 nwords 参数表示宽字数，输入数组长度则表示元素数。这两个单位一旦混用，就可能出现越界访问，或者只处理了输入的一小部分。

将下面代码保存为 host.cpp。程序接收 .xclbin 路径、元素数和重复次数；每次执行后校验全部有效元素，并输出每一轮的计时。输入中加入较大的无符号整数，使校验覆盖加法回绕。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

#include <xrt/xrt_bo.h>
#include <xrt/xrt_device.h>
#include <xrt/xrt_kernel.h>

#include <chrono>
#include <cstddef>
#include <cstdint>
#include <exception>
#include <iostream>
#include <stdexcept>
#include <string>

std::size_t positive_count(const char* arg, std::size_t limit) {
    const std::string text(arg);
    if (text.empty() || text.find_first_not_of("0123456789") != std::string::npos)
        throw std::invalid_argument("expected a positive integer");
    const auto value = std::stoull(text);
    if (value == 0 || value > limit)
        throw std::out_of_range("argument outside supported range");
    return static_cast<std::size_t>(value);
}

int main(int argc, char** argv) {
    try {
        if (argc != 4) {
            std::cerr << "usage: ./host kernel.xclbin elements repetitions\n";
            return 1;
        }
        const auto n = positive_count(argv[2], std::size_t{1} << 24);
        const auto repetitions = positive_count(argv[3], 10000);
        const auto nwords = static_cast<unsigned int>((n + 15) / 16);
        const auto padded = static_cast<std::size_t>(nwords) * 16;
        const auto bytes = padded * sizeof(std::uint32_t);

        auto device = xrt::device(0);
        const auto uuid = device.load_xclbin(argv[1]);
        auto kernel = xrt::kernel(device, uuid, "vadd");
        auto a = xrt::bo(device, bytes, kernel.group_id(0));
        auto b = xrt::bo(device, bytes, kernel.group_id(1));
        auto c = xrt::bo(device, bytes, kernel.group_id(2));
        auto* pa = a.map<std::uint32_t*>();
        auto* pb = b.map<std::uint32_t*>();
        auto* pc = c.map<std::uint32_t*>();
        for (std::size_t i = 0; i < padded; ++i) {
            pa[i] = i < n ? std::uint32_t{0xfffffff0u} +
                               static_cast<std::uint32_t>(i) : 0;
            pb[i] = i < n ? static_cast<std::uint32_t>(3 * i + 7) : 0;
        }

        using Clock = std::chrono::steady_clock;
        const auto ms = [](auto begin, auto end) {
            return std::chrono::duration<double, std::milli>(end - begin).count();
        };
        std::cout << "iteration,h2d_ms,submit_wait_ms,d2h_ms,request_ms\n";
        // Iteration zero warms up the execution path and is excluded from output.
        for (std::size_t rep = 0; rep <= repetitions; ++rep) {
            const auto t0 = Clock::now();
            a.sync(XCL_BO_SYNC_BO_TO_DEVICE);
            b.sync(XCL_BO_SYNC_BO_TO_DEVICE);
            const auto t1 = Clock::now();
            auto run = kernel(a, b, c, nwords);
            run.wait();
            const auto t2 = Clock::now();
            c.sync(XCL_BO_SYNC_BO_FROM_DEVICE);
            const auto t3 = Clock::now();
            for (std::size_t i = 0; i < n; ++i) {
                const auto expected = static_cast<std::uint32_t>(pa[i] + pb[i]);
                if (pc[i] != expected)
                    throw std::runtime_error("mismatch at element " + std::to_string(i));
            }
            if (rep != 0)
                std::cout << rep << ',' << ms(t0, t1) << ',' << ms(t1, t2)
                          << ',' << ms(t2, t3) << ',' << ms(t0, t3) << '\n';
        }
        return 0;
    } catch (const std::exception& e) {
        std::cerr << e.what() << '\n';
        return 1;
    }
}

group_id() 根据 kernel 参数的连接信息选择 buffer 所在的存储组，使主机分配与链接结果对应。map() 返回主机侧映射地址；写完映射区域后调用 sync(TO_DEVICE)，FPGA 才能读取同步后的输入。kernel 执行完成后再调用 sync(FROM_DEVICE)，主机随后读取输出。这里通过 XRT 对象的生命周期管理设备和缓冲区资源。⁶

主机程序将输入规模限制为 $2^{24}$ 个元素，以控制内存用量。换成实际数据集时，应检查元素计数的类型范围、三个 buffer 的总容量和每个 bank 的可用空间，再调整上限。

编译、仿真与板上运行

先在工程目录编译主机程序，再为软件仿真构建 kernel。v++ -c 生成 .xo，v++ -l 按平台与连接配置生成 .xclbin。不同 target 使用不同目录，避免误用旧产物。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

g++ -std=c++17 -O2 -Wall -Wextra host.cpp \
  -I"$XILINX_XRT/include" -L"$XILINX_XRT/lib" \
  -Wl,-rpath,"$XILINX_XRT/lib" -lxrt_coreutil -pthread -o host

export TARGET=sw_emu
mkdir -p "build/$TARGET"
v++ -c -t "$TARGET" --platform "$PLATFORM" -k vadd \
  --temp_dir "build/$TARGET/compile" \
  -o "build/$TARGET/vadd.xo" vadd.cpp
v++ -l -t "$TARGET" --platform "$PLATFORM" \
  --config connectivity.cfg --temp_dir "build/$TARGET/link" \
  -o "build/$TARGET/vadd.xclbin" "build/$TARGET/vadd.xo"
emconfigutil --platform "$PLATFORM" --od "build/$TARGET"

export EMCONFIG_PATH="$PWD/build/$TARGET"
XCL_EMULATION_MODE=sw_emu ./host "build/$TARGET/vadd.xclbin" 1003 2

1003 这个长度会触发尾部补齐。接着测试 1、15、16、17、1024 等长度，分别覆盖不足一个宽字、宽字边界和连续访问。软件仿真用于核对主机参数、数据编码和算法输出；板上运行用于测量吞吐和延迟。

然后把 TARGET 改成 hw_emu，重新执行上面的编译、链接和 emconfigutil 命令，将运行时的 XCL_EMULATION_MODE 改成 hw_emu。硬件仿真包含 RTL 行为，适合检查接口和数据流阻塞。先用较短输入；长数据集会显著增加仿真时间。加入 FIFO 和反馈环后，还应检查通道占用和停顿，查找可能的阻塞。

最后把 TARGET 改成 hw，重新执行编译和链接。硬件 target 不需要 emconfigutil。确认设备空闲后执行：

1
2

unset XCL_EMULATION_MODE
./host build/hw/vadd.xclbin 1048576 100 > timings.csv

加载 .xclbin 会改变设备上运行的应用，需要与服务器上的其他任务错开。构建可以在独立开发机上完成，加载和测量则等板卡空闲后进行。

综合完成后，先读循环的 achieved II、接口宽度和资源占用，再看布局布线后的时序报告。HLS 给出时钟估计，布局布线后的报告反映实现时序。若 II=1 没有达到，报告通常会指出依赖、存储端口或运算资源方面的限制；若 II 达到但实现频率降低，则继续检查关键路径和布局拥塞。

性能测量与访存优化

主机代码把一次请求拆成主机到设备传输（host-to-device，H2D）、提交并等待、设备到主机传输（device-to-host，D2H）三段。读计时结果时，需要区分以下范围：

• submit_wait_ms：从提交 kernel 到等待其完成的耗时，包含 kernel 执行时间，以及 XRT 提交和主机等待的开销。
• 设备侧 kernel 时间：通过带相应监测配置的 Vitis 分析结果获取。
• request_ms：从输入同步开始，到输出同步结束，排除了设备初始化、加载 bitstream、分配内存、生成输入和正确性校验。

对 $N$ 个元素，算法的有效读写量为 $12N$ 字节，实际搬运还包含最后一个宽字的补齐。用设备侧时间 $T_k$ 计算 $12N/T_k$，得到 kernel 的有效吞吐；用请求时间 $T_r$ 计算 $N/T_r$，得到完整请求的元素处理速率。这里 GB/s 按 $10^9$ 字节每秒计算。小输入下启动开销容易占较大比例，增大输入后，可以逐步观察持续访存的吞吐。

测试使用 Vitis 2023.2 和 XRT 2.16.204，运行时独占一块 U250。三个参数分别连接三个 bank，以及全部连接 DDR[0] 的两种配置，都通过了 1003、1、15、16、17、1024 六种输入长度的结果校验，覆盖了尾部补齐和宽字边界。

下面是主机端的计时结果，单位为 ms。各列为均值，括号内为最小值和最大值；两组大输入分别重复 100 次和 20 次，单元素输入重复 2 次；统计均不含首次预热运行。

按有效读写量 $12N$ 除以“提交加等待”时间计算，有效带宽如下：

这组对照可以看出三个现象：

• bank 争用会限制吞吐。约 1600 万元素时，全部放入 DDR[0] 的提交加等待时间是三个 bank 的约 2.7 倍。三个 bank 的合计有效带宽为 43.3 GB/s，平均每端口约 14.4 GB/s，达到三端口理论带宽的约 75%。
• 数据传输占据了完整请求的大部分时间。同一规模下，三个 bank 的请求耗时 27.628 ms，其中 H2D 与 D2H 合计约 23 ms，占 83%。按两个输入数组和一个输出数组的字节数换算，H2D 约为 8.4 GB/s，D2H 约为 9.6 GB/s。
• 小请求受固定开销影响明显。只处理 1 个元素时，提交加等待仍耗时约 48 µs，整次请求约 108 µs。增大输入后，这部分开销被更多元素分摊。

完成 bank 映射的对照后，可以继续测试多个计算单元。增加 CU 时，核对每个 CU 的输入输出映射、主机是否同时提交工作，以及 DDR 是否已经饱和。如果两个 CU 共用已经繁忙的 bank，资源增加后仍可能得到接近的总吞吐。观察到这个现象后，可以进一步测量 bank 流量和各 CU 的活跃时间。

当应用重复使用同一份索引或模型时，可以在初始化阶段把它上传一次，在查询循环中只发送查询并取回结果。实验记录应同时保留初始化时间与稳态查询时间。对于多个独立数据块，还可以使用多组 buffer，让下一块的传输与当前块的计算重叠；主机要为每组 buffer 跟踪传输和执行是否完成，并在时间线上确认重叠已经发生。

将 kernel 拆成读取、计算和写回三个函数后，DATAFLOW 可以让它们以 stream 连接并重叠执行。FIFO 深度用来吸收各阶段速率的短时差异。如果消费者持续跟不上生产者，FIFO 最终仍会填满，此时需要提高较慢阶段的吞吐。反馈流水线还需要终止协议：最后一个请求、最后一个结果和查询结束信号必须有一致的含义，否则部分模块可能已经退出，其他模块仍在等待数据。Falcon 的图搜索包含这样的反馈流水线，可以结合它的实现继续分析。

Falcon 查询流程与源码分析

Falcon 是论文 Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal 提出的 FPGA 图向量检索系统。⁷仓库中的 FPGA_single_DDR 保留了开发阶段的实现，适合先用来理解各个模块；多 DDR 的 inter-query v1.3 和 intra-query v1.5 用于本地实验，后面会以其中的查询内并行版本演示复现流程。

图向量检索把向量作为节点，用边连接相近的向量；查询时，从入口节点出发，按距离选择候选并扩展邻居，逐步找到靠近查询的节点。HNSW（Hierarchical Navigable Small World，分层可导航小世界图）通过多层图组织这一搜索过程。后文使用的 Recall@10 表示返回的前 10 个结果中包含多少个真实近邻：每条查询与真实前 10 个近邻的重合数除以 10，再对查询集合取平均。

下面列出阅读和运行时会用到的主要文件，注释标明各自的作用：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Falcon-accelerate-graph-vector-search/
├── FPGA_single_DDR/
│   └── FPGA_single_DDR_single_layer_v1.3_opt_queue/
│       └── src/
│           ├── host.cpp                          # 主机端数据加载与任务提交
│           ├── vadd.cpp                          # kernel 入口与顶层数据流
│           ├── per_channel_processing_wrapper.hpp # 连接单通道处理模块
│           ├── scheduler.hpp                     # 候选调度与在途任务管理
│           ├── DRAM_utils.hpp                    # 图邻接表与向量访存
│           ├── bloom_fetch_compute.hpp           # 连接去重、读取与距离计算
│           ├── priority_queue.hpp                # 优先队列实现
│           └── constants.hpp                     # 维度、队列容量等综合参数
├── FPGA_multi_DDR/
│   └── FPGA_intra_query_v1.5_support_batching_longer_FIFO/
│       ├── Makefile                              # 主机与 kernel 构建
│       ├── connectivity.cfg                      # DDR bank 连接与时钟配置
│       └── src/
│           ├── host.cpp                          # 多通道数据加载、运行与校验
│           ├── vadd.cpp                          # 查询内并行的 kernel 入口
│           ├── DRAM_utils.hpp                    # 按节点 ID 计算通道与地址
│           └── constants.hpp                     # 通道数、维度与队列容量
├── vector_search_baselines/
│   └── scripts_hnsw/
│       ├── README_hnsw.md                        # 索引构建与转换说明
│       ├── construct_and_search_hnsw.py           # 构建与搜索 CPU HNSW 索引
│       └── hnsw_to_FPGA.py                        # 导出 FPGA 使用的索引格式
└── perf_test_scripts/
    ├── README.md                                 # 实验脚本使用说明
    ├── perf_test_throughput.py                    # 吞吐实验
    ├── perf_test_latency.py                       # 延迟实验
    └── utils.py                                  # 读取报告与整理结果

先打开 FPGA_single_DDR/FPGA_single_DDR_single_layer_v1.3_opt_queue/src/vadd.cpp。函数名沿用了 vadd，参数已经包括查询、入口节点、图边、数据库向量和搜索队列配置。顶层以 DATAFLOW 连接 read_queries、per_channel_processing_wrapper 和 write_results。查询批次进入计算模块，输出 ID、距离与调试信息；写回模块通过 s_finish_batch 通知读取模块继续工作。⁸

在 per_channel_processing_wrapper.hpp 中，可以顺着候选节点的流向找到各个处理模块。scheduler.hpp 管理待扩展候选与在途任务；DRAM_utils.hpp 读取邻接表；bloom_fetch_compute.hpp 将去重、向量读取和距离计算连接起来；结果队列再把新候选与阈值送回调度器。画出这条反馈路径后，可以在每条 stream 旁标记它传输的记录类型、数量与结束信号。这些约定决定了上下游如何配合，以及何时结束一次查询。

下图分别展示查询间并行与查询内并行。图中还包含网络接入模块；本文本地工程通过 PCIe 与主机通信，对应图中的查询处理流水线与存储通道部分。

图搜索每轮会根据已经计算出的距离决定接下来访问哪些节点。若每次只发出一个候选，然后等它的邻居全部处理完再继续，存储和计算之间会出现等待。Falcon 的调度器可以成组发出候选，并允许多个组同时处于处理过程中。多 DDR 主机把相应参数暴露为 max_cand_per_group 和 max_group_num_in_pipe。调大这两个参数可以增加在途工作量，也会改变候选的扩展顺序和搜索工作量，因此需要同时观察运行时间、距离计算次数与 Recall。

Bloom filter 位于向量读取之前，用来过滤已经访问的候选。它的误判会把某些尚未访问的节点判为已访问，因此容量与哈希配置可能影响搜索质量。读取源码时，应追踪每个查询开始时的状态初始化以及结束时的排空过程，再修改其大小。调整后同时测量过滤请求数和 Recall。

接着看 FPGA_multi_DDR/FPGA_intra_query_v1.5_support_batching_longer_FIFO。当前 constants.hpp 默认设置 N_CHANNEL=4、D=128，结果队列上限为 64，候选队列上限为 32；connectivity.cfg 请求 200 MHz kernel 时钟，并把四组向量和邻接表端口分别连接到四个 DDR bank。⁹实际时序和资源占用可以在构建报告中查看。

这里的四通道采用按节点 ID 分片的布局。在 DRAM_utils.hpp 中，低 CHANNEL_ADDR_BITS 位决定通道，右移后的 ID 决定通道内位置。当通道数为 4 时，地址计算可以写成：

1
2
3

channel_id = node_id & 3
local_id   = node_id >> 2
vector_word_offset = local_id * (ceil(D / 16) + 1)

公式中额外增加的一个宽字是每个节点的 64 字节 visited 区。按 hnsw.py 的导出格式，前 4 字节是初始化为 −1 的 int32 标记，后 60 字节补零。以 D=128 为例，向量本身占 8 个 512 位字，记录步长为 9 个字，即 576 字节。读取向量时取其中的有效数据，寻址时却必须使用完整步长。改变维度、通道数或者索引格式时，主机文件读取、kernel 地址计算和导出脚本需要采用同一约定。

查询内并行把同一次查询的工作分散到多个通道，适合研究单次搜索的推进速度。查询间并行让多个查询使用并行的处理路径，适合研究持续输入时的吞吐。比较这两种设计时，固定查询集合、Recall 目标和请求负载，再报告各自的 batch 大小与并发方式。

Falcon 的数据准备与运行

下载源码后，进入查询内并行工程：

1
2
3
4

git clone https://github.com/fpgasystems/Falcon-accelerate-graph-vector-search.git
cd Falcon-accelerate-graph-vector-search
git switch --detach 34bcc0aabd04939dce72fd3c257febcf5b8089d2
cd FPGA_multi_DDR/FPGA_intra_query_v1.5_support_batching_longer_FIFO

这个工程的主机使用 OpenCL，Makefile 链接 xilinxopencl。前面的向量加法使用 XRT native API，复现 Falcon 时可以沿用它原有的主机接口。复现时需要修改主机的数据路径、设备选择和计时位置。SIFT10M 的 intra-query 版本带性能监视器时曾出现时序不收敛，移除链接配置中的 [profile] data=all:all:all 后完成了构建。性能监视器也会消耗硬件资源，调整监测配置后应重新检查实现时序。

仓库提供的 Python 示例从 SIFT1M 开始，它与当前 D=128 对应。vector_search_baselines/scripts_hnsw/README_hnsw.md 给出构建 HNSW 和转换索引的流程。¹⁰构建脚本依赖 Python 的 hnswlib、NumPy 和仓库数据读取工具，内部仍有作者机器的数据路径；先准备对应的 base、query 与 ground truth 文件，再修改脚本的数据目录。安装依赖后保留包版本及索引生成参数。

按仓库示例准备数据时，进入 vector_search_baselines/scripts_hnsw，执行索引构建与转换：

1
2
3
4
5
6
7
8

python construct_and_search_hnsw.py \
  --dbname SIFT1M --ef_construction 128 --MD 64 \
  --hnsw_path ../data/CPU_hnsw_indexes

python hnsw_to_FPGA.py \
  --dbname SIFT1M \
  --CPU_index_path ../data/CPU_hnsw_indexes/SIFT1M_index_MD64.bin \
  --FPGA_index_path ../data/FPGA_hnsw/SIFT1M_MD64

我在复现中使用了另一条数据准备流程：用基于 hnswlib v0.8.0 的 C++ 程序读取 big-ann-benchmarks 数据并建图，设置 M=32、ef_construction=128，再将索引转换为 Falcon 的 FPGA 格式。M=32 对应 HNSW 底层最大度 64。转换程序在一个 2 万节点的小图上与仓库原转换脚本的输出逐字节比对，结果完全一致；随后用 hnswlib 搜索原图，确认 Recall。

转换脚本调用 save_as_FPGA_format(..., num_channels=[1, 2, 4])，生成不同通道数对应的文件。四通道主机读取 ground_vectors_4_chan_0.bin 至 ground_vectors_4_chan_3.bin，以及对应的 ground_links_4_chan_*.bin，同时使用元数据和 label 映射。原始查询也需要按代码预期读取和转换。先用少量节点检查导出结果：任取一个物理 ID，依据通道和局部地址读回向量，核对维度、数值和邻居 ID 范围，再对照 label 映射找到原始数据集中的对象。

Falcon 的 src/host.cpp 也写有作者机器上的索引、查询和 ground truth 路径，需要改成自己的路径。运行前检查文件存在、大小正确，并检查 fopen、fread 等操作是否成功，读取失败时应先排查文件和路径。对 HNSW，输出 ID 还会经过 labels_base 映射后再计算 Recall；改变图的物理排序时，这一步也要同步核对。

确认数据路径和配置后，回到多 DDR 工程目录构建。Makefile 的 kernel 依赖只列出 src/vadd.cpp，修改 constants.hpp 等头文件后，普通增量构建可能沿用旧 .xo。这里用 -B 强制重建，使修改后的头文件和连接配置生效。

1

make -B all TARGET=hw PLATFORM="$PLATFORM" > build-hw.log 2>&1

开发阶段可以先将 TARGET 改成 hw_emu。主机默认处理 10000 条查询；若要做短仿真，应同时调整查询数量、相关数组长度与校验循环。命令行最后的 batch_size 控制查询批次大小，主机仍会处理设定的总查询数。

硬件构建完成并检查过数据文件后，等板卡空闲时运行：

1

./host xclbin/vadd.hw.xclbin 1 4 64 HNSW SIFT1M 64 10000

.xclbin 后的七个参数按命令行顺序对应如下：

• 1 4：每组候选数为 1，允许 4 个候选组在途。
• 64：搜索参数 ef=64，与当前硬件结果队列上限对应。
• HNSW SIFT1M：图类型为 HNSW，数据集为 SIFT1M。
• 64 10000：图的最大度为 64，查询 batch 大小为 10000。

调大 ef 前要检查综合时的队列容量；改变 D、N_CHANNEL 或队列容量则需要重新构建硬件。改变通道数时，还应同步选择连接配置并确认相应分片文件已经生成。

第一次运行先检查 Recall、输出 ID 范围和距离值。然后固定索引与查询，分别扫描每组候选数和在途组数，例如从 (1,1)、(1,4) 到 (2,4)，逐项检查是否落在硬件队列容量与调度器允许的范围内。每组参数都记录 Recall@10、设备侧耗时、主机侧耗时，以及能够采集到的搜索工作量。若更高并发增加了距离计算次数，时间变化就需要结合这些额外工作解释。

复现时遇到的第一个问题是计时混入了输入传输。原主机先调用 enqueueMigrateMemObjects 异步上传输入，随后就开始计时；kernel 和结果回传都排在上传之后，最后的 q.finish() 会等待整条队列完成。因此，打印的 Duration (including memcpy out) 会包含尚未完成的上传。

在开始计时前调用 q.finish()，等待输入上传完成，便可将索引加载与查询执行分开计时。修正后的主机计时包括一次 kernel 提交、执行、输出和调试缓冲区回传，以及主机等待。设备上的纯 kernel 时间通过 profiling event 或分析报告获取。关闭 xrt.ini 的对照运行仍出现了输入传输混入计时的现象，计时位置才是这里需要修改的地方。

Falcon 作者的性能脚本读取 profiler 报告中的 kernel Total Time，仓库中作者的测试脚本和保存的结果（perf_test_scripts/saved_df）采用这一计时口径。上述修正针对 host 打印的 Duration，不改变作者脚本使用的内核时间。¹¹

仓库的 perf_test_throughput.py 从 summary.csv 读取 kernel 的 Total Time (ms)，保存为 time_ms_kernel，并据此计算性能。使用这个脚本前，检查 utils.py 读取了报告中的哪一行、采用什么单位，并保留原始报告。脚本还使用固定输出文件名、调用 DataFrame.append，并在末尾执行 rm *csv。运行时应为每组实验准备独立目录，调整清理逻辑以保留原始数据，并核对 pandas 版本或将追加操作迁移到当前 API。仓库 README 也明确指出，共用这些输出文件的实验不能并发执行。¹¹

Falcon 主机的一次 kernel 调用会处理设定的全部查询，batch_size 控制 kernel 内部的查询批次。即使 batch_size 设为 1，主机打印的每查询耗时也是总时间除以查询数，一次提交与结果回传的开销会摊入其中。测量单请求端到端延迟时，应逐请求记录提交和完成时间。

论文实验设计

完成第一次 Falcon 运行后，可以围绕一个变量组织实验，例如比较 1、2、4 个 DDR 通道，或者研究候选组大小对延迟和搜索工作量的影响。每次改变硬件配置，都保存源码提交、修改补丁、编译命令、平台信息、.xclbin 的 SHA-256，以及 achieved II、实现时序和 LUT、FF、BRAM、URAM、DSP 占用。这些记录将性能数据与对应的硬件版本关联起来。

向量检索的性能比较需要同时考虑 Recall。固定数据集、距离度量、ground truth 定义和查询集合，扫描搜索参数，形成 Recall 与吞吐或延迟的曲线。在相近 Recall 下比较 CPU、GPU 和 FPGA，并记录各自的线程数、并发、batch、精度与数据驻留方式。如果使用不同索引结构，也要报告索引构建参数、内存占用和构建成本。

用专门的调参查询选择配置，在保留的测试查询上测量最终结果。不同实验需要保存的记录包括：

• 吞吐：稳态完成的查询数与总时间。
• 延迟：用每条请求的开始和完成时间计算响应延迟，报告分位数和请求负载。
• 运行波动：重复运行的结果、预热方式和板卡温度。
• 功耗：传感器来源、采样周期和统计范围，并区分板卡功耗与整机功耗。

以 Falcon 为例，增加在途候选可能掩盖部分存储等待，也可能让搜索扩展更多节点。可以结合通道利用率、队列等待、距离计算次数和 Recall，判断两种变化各自带来了什么影响。修改自己的算子或索引时，也可以沿着这条思路，逐步解释性能变化的原因。

小结

从向量加法到 Falcon，U250 上的开发逐渐涉及数据布局、存储通道和查询调度之间的配合。向量加法的实测展示了 bank 争用、PCIe 传输和启动开销各自对耗时的影响；Falcon 则把这些问题带入带有反馈的图搜索流水线，还需要结合 Recall 和搜索工作量理解性能变化。后续将自己的算法搬到 FPGA 上时，可以从一个能校验结果、能分段计时的小实现开始，通过对照实验找到瓶颈，再决定如何安排并行计算与数据访问。