ParallelNN: 一种基于平行八叉树的3D点云最近邻搜索加速器
摘要
随着激光雷达 (LiDAR) 越来越成为机器人导航和自动驾驶的核心组件，实时处理高吞吐量的 3D 点云已被广泛需求。本研究聚焦点云 k 最近邻 (kNN) 搜索，它是重要的 3D 处理核心。尽管在内部处理上应用细粒度并行化优化（例如使用多工作者）已展示高效率，但基于 DDR 外部存储的以往加速器在外部带宽瓶颈上受到根本限制。为打破此瓶颈，本文提出了一种高度并行的架构，即 ParallelNN，用于高效处理高吞吐量点云的 kNN 搜索。首先，我们基于高带宽内存 (HBM) 与片上内存优化多通道缓存，以提供更大的外部带宽。随后，提出一种新颖的并行深度优先八叉树构造算法，并将其映射到多条构造分支与追踪编码构造队列，能够规范化随机访问并高效执行多分支八叉树构造。此外，在搜索阶段，我们提出算法-架构协同优化，包括并行关键帧调度和多分支灵活搜索引擎，提供无冲突访问和最大重用机会给参考点，较基线架构实现 27.0 倍以上的加速。我们在 Virtex HBM FPGA 上原型化 ParallelNN，并在 KITTI 数据集上进行了广泛基准测试。结果表明 ParallelNN 在 CPU 与 GPU 实现上分别实现了高达 107.7 倍和 12.1 倍的加速，同时更节能，例如相较于 CPU 和 GPU 分别提升 73.6 倍与 31.1 倍。除此之外，凭借所提算法-架构协同优化，ParallelNN 相比最先进架构实现了 11.4 倍加速。
此外，ParallelNN 是可配置的，并且可以轻松推广到类似基于八叉树的应用程序。
作者
Faquan Chen 脑启发型应用技术中心 (BATC)，上海交通大学，上海，中国
Rendong Ying 脑启发型应用技术中心 (BATC)，上海交通大学，上海，中国
Jianwei Xue 脑启发型应用技术中心 (BATC)，上海交通大学，上海，中国
Fei Wen 脑启发型应用技术中心 (BATC)，上海交通大学，上海，中国
Peilin Liu 脑启发型应用技术中心 (BATC)，上海交通大学，上海，中国
出版信息
期刊: 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA) 年份: 2023 页码: 403-414 DOI: 10.1109/HPCA56546.2023.10070940 文章编号: 10070940 ISSN: Electronic ISSN: 2378-203X, Print on Demand(PoD) ISSN: 1530-0897
指标
论文引用: 12 总下载量: 2148
关键词
IEEE 关键词: 点云压缩, 三维显示, 八叉树, 图形处理单元, 带宽, 并行处理, 搜索问题
Index Terms: 点云, 3D 点, 3D 点云, 邻域搜索, 并行搜索, 并行加速, 能源效率, k 最近邻, 激光雷达, 高带宽, 随机存取, 并行算法, 机器人导航, 高云, KITTI 数据集, 搜索阶段, 外部存储, 点云处理, 芯片内存, GPU 实现, 查询点, 叶子节点, 树节点, 并行优化, 外部访问, 叶子大小, 同时定位与地图构建, 限制带宽, 高计算负载, 连续帧
未定义
第一节. 介绍
基于激光雷达 (LiDAR) 的 3D 感知 1, 2 已广泛成为帮助自动驾驶车辆和机器人通过 3D 点云感知环境的关键手段。正如图 1 所示，3D 检测是在高质量点云上完成的，并能实现轨迹预测和路径规划，以避免自动驾驶车辆碰撞。点云是无结构的，仅包含关于周围环境的几何属性 (X, Y, Z)。通常，点云的拓扑信息可以通过 k-最近邻(kNN) 搜索获得，并随后转换为场景理解线索。因此，kNN 搜索成为许多重要 3D 视觉任务中广泛使用的核心，例如轨迹规划 3、3D 目标检测与分割 4, 5, [^6], [^7]、姿态估计与校正 6, 7, [^10]、离群点剔除与去噪 8, [^12] 以及法向量估计 9，仅举几例。
图 1. 基于 LiDAR 的 3D 检测用于自动驾驶，其中高吞吐量的 3D 场景点云（典型情况下，每秒超过 100 万点）需要实时处理。该图改编自 [32]。
KNN 搜索旨在为给定查询点寻找最近邻。一般来说，基于划分的 kNN 搜索，例如基于八叉树的 10、11 以及基于 k 维（k‑d）树的 12，由于在效率和可扩展性方面的优势，优先于暴力 kNN 搜索。然而，随着 LiDAR 感知技术的持续进步，最新的 LiDAR 在高空间分辨率下以高帧率产生大量 3D 点，导致计算和内存访问负担沉重。满足自动驾驶所需的此类高吞吐量点云的实时处理，对基于划分的 kNN 搜索而言，甚至是一个巨大的挑战。例如，Velodyne HDL‑64E LiDAR 传感器在 10 Hz 的帧率下，在 120 m 范围内（[^17]）每秒可产生多达 130 万点，无法存储在芯片上，通常存储在外部 DRAM 内存中。基于划分的 kNN 搜索受内存限制。例如，先前最有效的点云 kNN 搜索加速器 QuickNN [^18] 在对每帧仅 30k 点进行帧‑帧查询时，报告外部带宽利用率为 76%。当拥有多达 2 条传统 DDR4 SDRAM 内存通道时，kNN 搜索处理器只能使用理论最大 38.4 GB/s [^19] 的带宽。DDR SDRAM 的这种有限外部通道和带宽仍然是将 3D kNN 搜索应用于低延迟需求应用中的根本障碍，因为 kNN 搜索通常随后跟随下游复杂且耗时的算法。
虽然之前使用 DDR4 内存的研究提出了各种架构和内存优化，例如异构协作 [^20] 和细粒度并行性 [^18]，但它们仍然难以满足实时需求，并且在点云尺寸不断增大时扩展性差。除此之外，基于划分的 kNN 搜索受到随机外部内存访问开销的影响，并且在架构并行性方面仍受限制。因此，有必要设计一种加速器，通过打破内存访问限制并尽可能利用并行性来加速基于划分的 kNN。
在本工作中，我们使用高带宽内存(HBM)1设计了一种高度并行的八叉树 kNN 搜索架构，该架构可提供最多 32 个并行外部通道，理论带宽高达 460 GB/s [^19]、[^21]。同时，我们从新的粗粒度并行视角重新审视 3D kNN 搜索，并提出算法-架构协同优化，以充分利用高外部带宽进行并行八叉树构建和搜索。本文的主要贡献总结如下。
我们开发了 ParallelNN，一种高度并行的基于八叉树的 3D 点云 kNN 搜索加速器，能够实现毫秒级实时性能和高能效。
为突破大规模点云搜索的带宽限制，我们在以下三个方面提出了算法-架构协同优化。
首先，为了解决有限的外部带宽问题，我们将 ParallelNN 与 HBM 结合，并使用多通道访问控制，配备多个 3 × 3 mini-crossbars、Flexible Direct Memory Access (FXDMA) 和硬件控制缓存。其次，为了解决访问不规律问题并提升点云的空间局部性，我们提出了一种并行八叉树构造方法，该方法在八个粗粒度分支中高效构建八叉树，并基于追踪编码的队列。最后，为了实现无冲突并行搜索并提升参考点的时间局部性，我们提出了一种基于关键帧的八叉树近似搜索算法。结合可配置的搜索引擎，ParallelNN 具有高度可扩展性，并能够最大化参考点的数据复用。
首先，为了解决有限的外部带宽问题，我们将 ParallelNN 与 HBM 结合，并实现多通道访问控制，使用多个 3 × 3 mini-crossbars、Flexible Direct Memory Access (FXDMA) 和硬件控制缓存。
其次，为了解决访问不规律问题并提升点云的空间局部性，我们提出了一种并行八叉树构造方法，在八个粗粒度分支中使用基于追踪编码的队列高效构建八叉树。
最后，为了实现无冲突并行搜索并提升参考点的时间局部性，我们提出了一种基于关键帧的八叉树近似搜索算法。结合可配置的搜索引擎，ParallelNN 具有高度可扩展性，并能最大化参考点的数据复用。
我们在 Virtex HBM FPGA 上原型化 ParallelNN 并进行广泛基准测试以评估其性能。ParallelNN 超越了最先进的架构，最高可实现 11.4*×* 速度提升和 1.9× 能源效率提升。此外，它可以推广到其他基于八叉树的应用，例如点云压缩 13, 14, [^24] 和 3D 地图构建 15。
本文其余部分的组织如下。第二节介绍背景和动机。第三节呈现并行八叉树构造与搜索算法优化，第四节描述 ParallelNN 的硬件架构。随后，第五节提供评估结果与讨论。接下来，在第六节介绍相关工作。最后，第七节给出结论。
第II节：背景与动机
A. 问题定义
点云 kNN 搜索是 3D 度量空间中 kNN 搜索的一种情况。设 P 表示 3D 点集合 {p0*, p1, …, pn−*1}，其中 {p_i} \in {\mathbb{R}^3} 并且 P 被称为参考点云。给定查询点 q \in {\mathbb{R}^3}，kNN 搜索核 \mathcal{K}(q,P,k) 在 P 中找到与度量距离 d:{\mathbb{R}^3} \times {\mathbb{R}^3} \to \mathbb{R} 相对的 k 最接近的元素，使得 \mathcal{K}(q,P,k) \subseteq P,|\mathcal{K}(q,P,k)| = k，且
\begin{align*} & d\left( {q,{p^\prime }} \right) \leq d\left( {q,{p^ \bullet }} \right) \\ & \forall {p^\prime } \in \mathcal{K}(q,P,k),\forall {p^ \bullet } \in P\backslash \mathcal{K}(q,P,k), \end{align*}
where d is typically the Euclidean distance. 为了展示 ParallelNN 在真实世界应用中的性能，我们的架构针对连续帧之间基于 kNN 搜索的运动估计。运动估计有广泛的应用，例如移动物体分割 [^26]、 [^7]、车辆姿态估计 16、 [^10]、使用 LiDAR Odometry And Mapping (LOAM) 算法进行车辆姿态校正 [^27]，等等。此类应用需要在每一帧对树进行更新和搜索，因而对内存和计算提出极大挑战。
B. KNN 搜索算法
通常，点云 kNN 搜索存在两种主要方法。其一为暴力搜索方法，其二为基于划分的方法。暴力搜索方法直接计算查询点与所有参考点之间的距离，然后对距离进行排序，找到对应于最小 k 距离的 k 个最近邻。该方法计算量大，且随着工作负载增加扩展性差。基于划分的方法可提升计算效率，其中文件结构预先构建以划分点云，减少搜索至局部区域。然而，基于划分的 kNN 搜索存在内存受限问题。作为一种知名的 3D 划分模型，octree 比 k-d tree 更适合稀疏且分布不均的点云的三维空间特性。此外，它能高效存储和索引大量点而不需要复杂排序。Fig. 2 说明了 octree 模型的基本结构和层级索引。
图 2. 一个两层八叉树划分示例，共 19 个点。 (a) 八叉树结构。 (b) 线性表示，从根（白色）到第 0 层（灰色）和第 1 层（橙色）。
本文考虑基于八叉树的 kNN 搜索，因为八叉树的简单划分在与多通道 HBM 访问相结合时可以促进粗粒度并行。然而，精确的基于八叉树的 kNN 搜索涉及不规则迭代和回溯，这会降低 kNN 搜索的效率。实际上，大多数应用，例如自动驾驶和机器人导航，对最近邻噪声具有一定的容忍度。基于此，我们提出了一种基于八叉树的近似 kNN 搜索方法（第 III 节），该方法是迭代式的，但不使用回溯。
C. 挑战与动机
在加速基于八叉树的 kNN 搜索任务中，外部内存访问面临三大主要挑战。
1) 大量访问但带宽有限
基于分区的 kNN 搜索受内存限制，同时其迭代分区和参考点检索需要大量外部访问。因此，有限的片外内存带宽会导致高访问延迟和性能下降。为了解决此问题，我们将所提出的加速器与 HBM 结合，通过多通道访问提供高带宽。为调度总计 32 条 HBM 通道的挑战，实施了 FXDMAs 和八个 3×3 mini-crossbars 来管理并行 HBM 访问。
2) 随机且不可预测的访问
基于划分的 kNN 搜索的内存访问是非规则的。八叉树构造需要根据每个点的位置迭代地将其放入相应的八分区，直到收敛。因此，某个点所属的八分区无法被预测。此外，对不同查询对应的候选邻居可能不同且随机。为了解决这个挑战，我们提出了并行深度优先八叉树构造以及基于关键帧的搜索优化，以缓解非规则性问题。
3) 有限的并行性
由于外部存储访问限制，现有加速器难以在基于划分的 kNN 搜索中利用粗粒度并行性。我们提出一种高效的 HBM 基础架构，在八个粗粒度分支中映射并行八叉树构造和搜索算法。此外，每个搜索分支利用可配置的引擎，为参考点提供最大的数据复用。
第三节. 算法优化
为了解决第二节中提到的挑战，我们提出基于多通道 HBM 的并行点云 kNN 搜索算法优化，具体如下。
A. 基于并行八叉树的 KNN 搜索算法
由于外部存储限制，八叉树构建通常被视为串行过程。我们提出了一种基于32个HBM并行通道的并行构建方法来解决这一难题。此外，自动驾驶应用通常可以容忍一定程度的噪声，这意味着我们可以使用近似搜索来显著降低因精确kNN搜索回溯而导致的处理延迟。算法1展示了所提出的基于并行八叉树的kNN搜索算法的细节，包括使用跟踪编码构建队列的深度优先并行构建方法。
算法 1:
为了在八叉树构建中实现粗粒度并行性，我们将生成的前八个子树视为新的根节点，然后通过不同的HBM通道独立构建这些子树，以避免访问冲突。相应地，八叉树构建被划分为并行种子阶段和并行八支分支构建阶段。在算法1中，轨迹被定义为层次索引序列。例如，图2(b)中叶节点#7的两层轨迹可表示为000_111。每一次迭代，每个分支都可以提取基于轨迹的编码，以确定哪些点应使用基地址和长度放置，以及这些点应放置在哪里，因为基于轨迹的编码可用于计算八个八分体的位置信息。
在最终的串行搜索阶段，叶节点中定位到给定查询点的那些点被视为候选邻居。随后，计算这些点与查询点之间的距离，并以此确定k最近邻。图 3 (a) 和 (b) 分别说明了算法 1 中引入的并行构造和串行搜索阶段。
图 3. 基于八叉树的构造和搜索阶段的示意图，（a）并行性种子和并行八分支构造；（b）串行搜索；（c）基于关键帧的并行搜索。
B. 并行关键帧八叉树基础 KNN 搜索算法
根据第 III-A 节，基于并行八叉树的 kNN 搜索算法被分为三个主要步骤。首先，原始八叉树被划分为 8 个子树。然后，分别在不同分支中的子树使用 16 条 HBM 通道构建。最后，获取候选邻居以确定 k 最近邻居。该方法确实降低了八叉树构造的延迟，但最终的串行搜索效率低下，外部内存带宽利用率也低。一般来说，双缓冲可以通过隐藏构造和搜索阶段的重叠时间，有效加速整个过程。为更好地介绍我们的方案，我们在 TABLE I 中定义了一些符号。
首先，算法 1 的时间模式如图 4 (a) 所示。我们可以表示每帧的平均时间成本为
\begin{equation*}{T_{Baseline}} = T_{PS}^i + T_{POC}^i + T_{SS}^i,\tag{1}\end{equation*}
其中
\begin{equation*}T_{POC}^i = \mathop {\max }\limits_{0 \leq j \leq 7} \left( {T_{PO{C_{{B_j}}}}^i} \right).\end{equation*}
显然，在同一帧中，平行八叉树构造与串行搜索之间没有数据依赖。通过使用通用双缓冲优化，我们可以将 T_{SS}^i 与 T_{POC}^i 重叠，以隐藏更小的时间开销。通常，由于大量重复的参考点访问，T_{SS}^i 大于 T_{POC}^i。因此，基线可以如图 4 (b) 所示进行优化，其时间开销变为
\begin{equation*}{T_{DB}} = T_{PS}^i + T_{SS}^i.\tag{2}\end{equation*}
双缓冲基线可以隐藏并行八叉树构建的时间开销，并使用多 8 条 HBM 通道来保证无冲突访问。此外，在串行搜索期间存在潜在的数据复用机会。在 [^18] 中提出的一种优化方案通过使用多种读取聚集缓存来重用对应不同查询点的参考点。然而，当查询点的分布无法索引相同的候选邻居时，该方法将失效。此外，其效率仍受限于外部存储器带宽。
表 I
图 4. （a）算法 1（基线）、（b）算法 1 双缓冲、（c）算法 2 的时间模式优化。
基于 HBM 的并行优势，我们考虑了一种新颖的搜索方法，以为参考点提供最大的数据复用机会。核心思路是将具有相同候选邻居的查询点重新排列在一起，从而候选邻居可完全复用，避免重复的外部访问。可行的方法是基于上一帧的结构确定当前点云帧的八叉树结构。然而，在这种情况下，参考结构是逐帧时间变化的，这导致每个点云帧需要构建两次，即在最后一帧用于搜索，直接用于参考。
为解决此问题，我们提出了一种并行关键帧基 kNN 搜索算法，受经典同时定位与映射（SLAM）框架的关键帧思想 17、18 影响，并在算法 2 中呈现。该算法背后的理由是相邻帧的八叉树结构相似，因此仅在关键帧上构建八叉树可以缓解重复树构建问题。在所提出的基于关键帧的方法中，我们将增量构建定义为在关键帧上构建八叉树，将重建定义为不使用关键帧的构建。与此同时，KF (•) 表征结构变化，用于决定是否更新关键帧。更重要的是，该方法还可以促进并行八叉树搜索，图 3 (c) 说明了这一点，图 4 (c) 显示了优化后的时间模式。通过基于关键帧的算法优化，32 通道 HBM 能被充分利用，整个 kNN 搜索具有较高的时空局部性。
从上述分析可知，假设 P_{IC}^i = T_{POC}^i 与 T_{POS}^i < \left( {T_{PS}^i + T_{POC}^i} \right)，则基于关键帧的 kNN 搜索的时间开销可表示为
\begin{align*} & T_{POS}^i = \mathop {\max }\limits_{0 \leq j \leq 7} \left( {T_{PO{S_{{B_j}}}}^i} \right), \\ & {T_{KF}} = \left( {2 - PR_{IC}^i} \right)*\left( {T_{PS}^i + T_{POC}^i} \right). \tag{3}\end{align*}
当 P_{IC}^i = 0 时，我们得到 {T_{KF}} = 2*\left( {T_{PS}^i + T_{POC}^i} \right)，这恰好对应重复八叉树构建的情况。 当 P_{IC}^i = 1 时，它可以相对于等式 (1) 节省搜索阶段的全部时间开销。 当 P_{IC}^i > 0 时，所节省的时间会随着 P_{IC}^i 的增大而增加，因为 T_{PS}^i + T_{POC}^i < < T_{SS}^i。
算法 2:
第四节. 硬件架构
A. 架构概述
ParallelNN 的整体架构如图5所示。它主要包括并行种子（PS）模块、八分支八叉树构造（OC）模块、八分支八叉树搜索（OS）模块、树和叶节点缓存组、两层堆叠 HBM 以及全局控制单元。此外，它还具备两个外部 AXI 接口（EXT AXI #0 和 #1），分别用于点云源和邻居写回。
图5. ParallelNN 架构概览.
PS 模块在整体加速中起关键作用，用于生成八个原始子树。随后，八分支 OC 模块以深度优先的迭代方式对子树进行划分。PS 模块的划分单元和点缓存以及构造分支 #0 采用时分复用，以节省硬件资源，因为 PS 与 OC 模块是串行执行的。随后，八分支 OS 模块能够将位于同一地址叶节点中的相应查询点和参考点取入计算与比较引擎（C2E）。C2E 接着高效地执行流式距离计算和排序。最后，查询点及其邻居的信息通过 EXT AXI #1 存储。
HBM 能为 ParallelNN 提供最多 32 个并行通道及大带宽，且在非全局寻址模式 [^21] 下配置，以避免地址与通道索引的复杂交错。ParallelNN 中有 4 种 HBM 通道，分别为用于并行八叉树构造的 8 个非临时通道和 8 个临时通道、用于参考点的 8 个通道，以及用于查询点的 8 个通道。与此同时，我们使用完全独立的树节点和叶节点缓存，以避免并行构造和搜索分支之间的访问冲突。相应地，需要 3（有效类型）× 8（分支）个树节点和叶节点缓存。
B. 八叉树构造映射
1) 数据结构
在通用软件实现中，八叉树节点通常使用多个嵌套结构体表示，常见的组成包括八个子结构体指针、节点大小、质心、点索引等 19。在 ParallelNN 中，我们也模仿这种表示，但对树和叶节点缓存进行了优化。基址与长度的组合可以显著减少因点索引存储导致的片上内存占用。
更重要的是，诸如质心和节点大小等冗余信息通过跟踪编码和深度得到优化。树节点和叶节点缓存的编码如图 6 (b) 所示。树节点缓存包括 3 位深度、24 位跟踪、10 位地址和 1 位叶标志，其中地址字段可索引叶节点或树节点。如果叶标志被置位，则启用叶索引以定位对应于 33 位叶基地址和 15 位长度的八分之一。如果叶标志未置位，则启用下一个树节点索引以定位第一个子节点。如上所述，简化示例见图 6 (a) 与 (c)。假设质心 (X, Y, Z) 与尺寸 S 直接存储在树节点缓存中，宝贵的片上内存将被浪费。当 X, Y , 和 Z 用 15 位定点数表示，且 S 用 14 位定点数表示时，所提出的基于跟踪的编码可将片上内存占用相较直接表示减少 45.7%。
图 6. 缓存索引示例： (a) 八叉树划分; (b) 树与叶节点缓存编码; (c) 树与叶节点缓存索引示例.
Fig. 7. 基于追踪编码队列的深度优先八叉树构建： (a) 对应于 Fig. 6 (a) 中树构建过程的队列行为； (b) 基于追踪的编码（85 位）。
2) 基于追踪的构造队列
构造队列存储有关哪些点以及它们如何被划分的关键编码。构造队列由 PS 模块初始化后，OC 模块生成基于追踪的编码并在每一次构造迭代中将其推入对应的构造队列。构造队列的基于追踪的编码包含 3 位深度、24 位追踪、33 位基地址、15 位长度和 10 位父节点索引，如图 7 所示。同样，所提出的基于追踪的构造队列编码也可以将芯片内存占用降低 27.4%，相比直接表示。节点缓存和队列的详细编码基于对内存占用和 KITTI 点云分布的综合评估。与此同时，我们关注未来工作负载的可扩展性，这意味着参数化架构可以通过直观地重置相关参数，例如追踪编码细节，来适应更大的点云。
Fig. 8. 使用八个 3 × 3 小型交叉点的 HBM 通道内存管理： (1) 参考通道； (2) 查询通道； (3) 非临时通道； (4) 临时通道。
3) 层次化缓存与多通道控制
ParallelNN 是一种基于数据驱动的架构，可以自适应地、迭代地为子节点生成基于轨迹的编码。然而，单个八分体的统计信息在所有父点处理完成之前无法确定，盲目投递可能导致 HBM 中出现大量空白。为了解决此问题，每个构造分支被分配了一个临时 HBM 通道，以便将每个八分体的点临时存储。所有点处理完毕后，子节点的基地址和长度可以确定，然后将相关点从临时通道读取回原始通道，以避免 HBM 中出现数据缺口。由于基地址和长度的优化，每个节点的点可以通过点缓存和 FXDMA 准确、高效地访问。点缓存可以缓冲点云以利用高效的 AXI burst。FXDMA 是自定义的 AXI 主机，支持自动计算 burst 地址和长度，并使用 ready-valid 握手机制确保硬件兼容性。与此同时，为了将算法 2 映射到 ParallelNN，正如图 8 所示，实施了八个 3 × 3 的迷你交叉总线。
4) 关键帧计算
KF (•) 在算法 2 中基于汉明距离和空间权重计算，可以表示为
\begin{equation*}KF( \cdot ) = \sum {{\mathcal{D}_{ham}}} \times {8^{{L_{\max }} - {L_{cur}}}},\tag{4}\end{equation*}
where Lmax 和 Lcur 分别表示八叉树的最大层数和当前层数。如图 9 所示，我们使用简单的硬件逻辑来优化 KF (•)。汉明距离 {\mathcal{D}_{ham}} 来源于关键帧和当前帧的两组 8 位编码，用来表示它们在八叉树结构上的差异，每个位编码表示当前节点是否为树节点（1）或非树节点（0）。同时，层权重可用于识别不同层的变化。具体而言，从 0（关键帧的叶节点）变为 1（当前帧的树节点）表示候选邻居数量增加，而这些候选邻居随后保持未分割状态，这通常会提升 kNN 搜索的精度。相反，从 1（关键帧的树节点）变为 0（当前帧的叶节点）意味着当前节点没有足够的点可进一步划分，但它仍根据关键帧被划分，导致精度下降。
图 9. KF 结果计算的模块图.
图 10. C2E 的插入排序架构.
C. Octree 搜索映射
Algorithm 2 中的关键帧旨在确保查询帧与参考帧之间的八叉树结构相同，这意味着具有相同候选邻居的查询可以一起获取，其参考点可以完全复用。实际上，这一过程受到 C2E 数量的影响。设有 N 个 C2E 和 M（M > N）个查询。首先，将 N 个查询点读入这 N 个 C2E。随后，参考点流入所有 C2E 以确定 N × k 个邻居。在下一轮迭代中，获取 min(N, M − N) 个查询点，以重复上述处理，直到所有查询点都被处理完毕。如果追求极致效率，N 可设为较大的值，但这会占用更多硬件资源。关于 C2E，我们提出了一种插入排序架构（类似于 [^30]），该架构针对流式查询和参考点进行了优化，以实现高效。 如图 10 所示，每个 C2E 都有一个 Dist2 计算模块和 k 个排序节点。这些 k 个排序节点通过将输入与本地结果和上一个排序节点的距离进行比较，维护最近邻列表。当参考点流结束后，查询点及其邻居通过 EXT AXI #1 存储。
第五节：仿真与原型验证
A. 评估设置
为了展示 ParallelNN 的高性能，考虑将为多核 CPU 和 GPU 开发的流行 C++ 库作为对比对象，其中包括点云库（PCL）[^31] 和近似最近邻快速库（FLANN）20、21。PCL_CPU 使用 PCL 1.8 库的八叉树 kNN 搜索 API 实现，而 FLANN_CPU 与 FLANN_GPU 则使用 FLANN 1.9 库实现。此外，单线程的 Octree_CPU 是不含并行构造分支的算法 1 的对应实现。PCL_CPU、FLANN_CPU 与 Octree_CPU 在配备 32GB DRAM 的 Intel i7 8700 CPU 上进行基准测试。FLANN_GPU 在 NVIDIA GTX 1080 GPU 上进行测试。ParallelNN 在 Vitex Ultrascale+ 128 FPGA 板 [^34] 上原型化，该板配备 8GB HBM、4.5GB DDR4 SDRAM 以及充足的可编程逻辑资源。ParallelNN 被优化至 300 MHz 的核心时钟运行。EXT AXI #0 与 #1 与对应 DDR4 SDRAM 控制器所提供的 AXI 接口连接，且该控制器亦运行在 300 MHz。此外，ParallelNN 完全使用 Verilog HDL 实现，我们依据 Xilinx Vivado 2021.1 工具链的后合成功耗报告 FPGA 的功耗。对于 Intel i7 8700 CPU，使用系统监测工具 s-tui 22。同时，GPU 的功耗通过 NVIDIA Management Library (NVML) 23，即 nvidia-smi 进行测量。
我们在 KITTI 数据集上进行评估。由于地面点无信息且可能产生不必要的负担 [^7]。预处理后，每帧平均约有 50k 个点。KITTI 数据集中使用的 LiDAR 范围约为 12,000 cm，精度为厘米级，几何信息 (X, Y, Z) 存储为三段 15 位定点数。因此，原始 3D 点总共占 64 位，分别为 45 位几何字段、8 位强度字段和 11 位保留字段。在 ParallelNN 内，我们将构造队列长度设置为 32，节点缓存深度设置为 1024。点缓存的宽度与输入点相同，其深度设为 128，以在效率与资源消耗之间取得平衡。此外，单个 C2E 实现了 5 个排序节点，以支持相同数量的最近邻。随后实验中将探讨 C2E 的数量以及叶子大小、八叉树深度、关键帧相关阈值等架构参数。
B. 叶子大小、准确性与延迟
首先，我们检查叶节点大小对八叉树构造和搜索的影响。当最大叶节点数和最小叶节点大小分别设为 16 和 1 cm 时，相对于所有查询，叶节点的平均深度约为 8。这就是构造队列和节点缓存使用 3 位深度字段以支持最多 23+1 层的原因。图 11 展示了不同叶节点大小下，Octree_CPU 的叶节点平均点数、构造和搜索时间开销。可以看出，随着叶节点大小的增大，构造时间减小而搜索时间增加。这是因为叶节点越小，构造八叉树所需的迭代次数越多，待搜索的候选邻居越少，反之亦然。同时，叶节点大小对 kNN 搜索的准确性具有关键影响。
图 11. 不同叶节点大小下 Octree_CPU 的时间开销与平均点数.
图 12. 基于近似八叉树的 kNN 搜索在 KITTI 数据集上的准确性.
我们评估精度时采用 top k + x 指标 [^18]，而不是由误差界 24 定义的程度，因为后者需要精心选择误差界。图 12 展示了搜索精度，即在最近 5*−*10 个邻居中，正确检索到真实 k 最近邻的概率，x ∈ [0, 5]。Top 1 表示 k = 1 且 x = 0 时的最近邻。从图 11 (b) 与图 12 可以看出，当叶子大小为 1024 时，平均精度可超过 95%，平均点数约为 582。随着叶子大小增大，叶子节点内候选邻居的平均数也随之增加，这直接提高了命中实际 k-最近邻的概率。与此同时，大多数应用可以容忍少数检索到的点不是绝对 k-最近邻，而是 k + x 最近邻（通常 x ≤ k）。在 top k + x 中增大 x 等价于增加对非 k 最近邻的容忍度。总体而言，我们可以得出结论：精度提升是以总时间开销增加为代价的。
从上述分析，我们的目标是平均前10名准确率达到80%，因此叶子大小设为128，以在准确率和时间开销之间取得平衡。随后，我们评估了不同叶子大小对ParallelNN在两个连续帧之间查询时的影响。结果如图13所示。我们将C2Es的数量设为20，以减少其对评估的影响，这个数量远小于叶子节点中最少的点数（即43）。显然，在图13(a)中可以观察到与图11相似的趋势，涉及八叉树构造和搜索时间开销。ParallelNN相比软件实现实现了显著的加速，尤其是在查询时间上。对于叶子大小为128，ParallelNN在构造和搜索方面相对于Octree_CPU分别实现了2.2*×*和183.9×的加速。
Fig. 13. ParallelNN不同叶子大小的时间开销和主节点平均点数.
Fig. 14. 不同C2E数量的时间开销和DSP利用率.
C. C2Es和搜索延迟
ParallelNN 的一个优势是其在查询时具有高效性，这得益于每个分支内的并行搜索分支和并发的 C2Es。直观上，C2Es 以相互矛盾的方式影响查询的效率和资源利用率。在图 14 中，我们评估了不同 C2Es 数量下 ParallelNN 的平均搜索延迟和 DSP 使用率。可以看到，随着 C2Es 数量的增加，搜索延迟呈单调递减，而 DSP 使用率呈线性递增。这是因为 C2Es 的数量决定了参考点复用的程度，过多的 C2Es 也可能导致硬件空闲。为了充分利用双缓冲技术，将 C2Es 的数量设置为 20，这样就可以为基于关键帧的优化所产生的额外查询开销预留 0.25 ms 的搜索裕度，即 0.71（构造）− 0.46（搜索）。
D. 关键帧选择
接下来，我们评估了连续点云帧中基于关键帧的 kNN 搜索。图 15 展示了叶节点中的平均点数以及重复构造方法和基于关键帧方法之间的准确率变化，并给出了以 \frac{{KF( \cdot )}}{{{8^8}}} \times 100\% 定义的 KF 结果。我们可以观察到点数和 KF 指数的单调增加，这基本上与连续帧结构的变化相吻合。同时，叶节点中的更多点数可以提升准确率。
*Fig. 15. 连续点云帧之间的关键帧相关变化。
*Fig. 16. 在不同帧间隔下基于关键帧方法的构建和搜索时间。
与重复构造方法相比，关键帧方法通常消耗更多时间，主要是因为帧级查询时叶节点中的点数增多。如图 16 所示，帧间隔从 0 变化到 7 时，查询时间从约 0.46 ms 增加到 0.64 ms，树构造延迟平均为 0.71 ms。我们基于关键帧的优化的最初意图是降低重复构造方法的时间成本，因此关键帧方法的额外时间成本必须小于不考虑精度变化的重复构造方法的时间成本。然而，为了在时间效率与数据相关性保留之间取得更好的折中，我们将查询时间上限调整为与构造延迟保持一致。为此，我们将 KF 的硬阈值设为 6.4%，并平均每 8 帧更新一次关键帧，从而使查询延迟受限，并完全隐藏在基于双缓冲调度的构造时间后面。
E. 协同优化方案的收益
TABLE II 步骤性展示了所提出的算法-架构协同优化方法的有效性。ParallelNN（使用算法 2）相较于软件对应实现以及无双缓冲和双缓冲的硬件基线，分别实现了约 107.7*×*, 28.0×, 和 × 27.3 的性能提升。结果与我们在 III‑B 节的理论分析高度一致，证明了并行算法-架构协同优化的高效性。
*表 II
*Fig. 17. 不同实现的时间开销。
F. 与软件实现的比较
TABLE III 比较了软件实现与 ParallelNN 在平均延迟、功耗和能效方面的表现。延迟的详细结果见 Fig. 17。作为 ParallelNN 的软件对应版本，Octree_CPU 明显无法满足实时需求，只能达到 11.6 f/s，表明需要定制硬件加速。与此同时，尽管 FLANN 和 PCL 库在算法上已针对点云 kNN 搜索进行了优化，但它们在延迟和能效方面仍被 ParallelNN 明显超越。在 GPU 平台上，FLANN_GPU 相较于基于 CPU 的实现实现了显著的性能提升，但仍无法与 ParallelNN 相提并论。ParallelNN 能实现约 12.1× 的加速和 31.1× 的能效提升（相较于 FLANN_GPU）。
在八叉树构建阶段，通用计算平台为了提升索引效率，使用缓存层级优势，但需要消耗大量内存来存储点的索引。尽管如此，ParallelNN 通过构建阶段的并行优化实现了 2.2× 的时间效率提升。 此外，离线内存与 C2Es 之间重复且不必要的数据移动会严重损害查询效率。通过基于关键帧的优化和 C2E 中的并行处理单元，ParallelNN 可以充分重用参考点，避免像 Oc-tree CPU 那样反复抓取。 同时，采用粗粒度双缓冲来隐藏搜索延迟，因此整体延迟主要由八叉树构建决定。
*表 III
*表 IV
G. 与相关工作比较
TABLE IV 将 ParallelNN 与几种现有加速器进行比较。现有实现无法适应高吞吐量任务。以 ICP‑based 3D‑registration 为例，通常需要约 1000‑fps（10（传感器 fps）×100（最大迭代次数））kNN 搜索 [^38]，其中 kNN 搜索通常占用多达 75% 的时间。ParallelNN 被优化为 300 MHz 核心时钟，能够在 50k × 50k 点云查询测试案例中达到 1250.0 fps。通过粗粒度并行和算法‑架构协同优化，ParallelNN 能够在 [^18] 所述的最先进加速器基础上实现 11.4 倍加速。与此同时，随着更高帧率和分辨率导致点云尺寸不断增长，kNN 搜索变得更具挑战性。之前的加速器在一定程度上受限于数据结构或外部带宽。ParallelNN 使用八叉树作为基本数据结构，可应用于分布不均的点云，其基于轨迹的架构具有优异的可扩展性。此外，ParallelNN 具备可配置性，并支持灵活的精度/效率折衷。不幸的是，ParallelNN 因使用八个并行分支来执行构造和搜索，导致比以前的实现消耗更多硬件资源。此外，由于 ParallelNN 与提供 32 个并行伪通道的 HBM 结合，功耗高于以前的加速器，其中静态功耗为 3.7 W，动态功耗为 24.7 W，包括 HBM 的功耗 17.5 W（61.6%）。然而，ParallelNN 仍然比最先进的加速器提升了 1.9 倍的能效。
H. 讨论
近来，近芯片内存（如 HBM）解决方案正成为从离芯片内存向内存计算过渡的有效形式，以缓解“内存墙”问题。在这种背景下，如何构建高效的并行计算架构和基于 HBM 的内存层次结构是一个重要问题。本文提出的算法-架构协同优化可以为此问题提供新的见解，并在架构上做出贡献。具体而言，在架构层面，我们提出了一种使用 FXDMA 和迷你交叉开关的灵活且无冲突的并行带宽管理方案，以充分利用 HBM。此外，我们探索了一种基于 HBM 层次的面向数据驱动的并行处理架构，以算法-架构协同优化的方式解决激光雷达行业中 kNN 搜索的基本问题，为需要高计算能力和内存带宽的 AI 加速器提供新的启示。
总体而言，我们主要关注 kNN 搜索的并行化优化，目标是实现高效率和可扩展性。因此，ParallelNN 并不追求可编程的通用性，例如带有 HBM 的 Nvidia GPU V100 25 和 Google TPU 26，而是专注于效率，这在某些应用（如自动驾驶）中是首要关注点。因此，我们的工作也能为此类应用提供新的见解。
此外，得益于其对分辨率的鲁棒性，基于八叉树的表示模型被广泛应用于其他激光雷达（LiDAR）应用任务，如点云压缩和三维地图构建。例如，基于八叉树的模型被用于将点云编码为紧凑的比特流，见 27, 28, [^24]。此外，流行的 OctoMap 29 也构建了基于八叉树结构的概率三维映射框架。这些算法的实现可受益于本文提出的并行八叉树构造和层次索引优化。
第六节. 相关工作
由于点云 kNN 搜索在机器人导航和自动驾驶应用中扮演重要角色，越来越多研究关注加速这一核心核，包括 CPU/GPU 加速 30, 31, 32, 33, 34, [^45] 以及定制硬件加速器 35, 36, [^18], [^20].
首先，已报道暴力计算的显著性能提升。 例如，高端GPU 37, 38 被用于加速距离计算和排序。 然而，随着点数的增加，该方法的能效和可扩展性受限。 因此，研究人员逐渐转向构建点云结构，主要包括八叉树 39, 40, k-d树 41, 基于网格的数据结构（GBDS） 42。 例如，工作 43 在通用平台上优化了八叉树的结构细节。 作者 [^45] 利用GPU并行性构建并行 k-d树，而工作 44 也引入了基于LBVH的构建和基于k-d树的层次遍历优化，使用GPU。 然而，GPU的并行性本质上适合计算受限的应用，而点云kNN搜索则受限于内存，需要高内存访问密度。 此外，一些近似方法已被提出用于加速kNN搜索，例如著名的FLANN库同时使用CPU和GPU 45, 46。
由于通用计算平台在定制架构方面的困难，FPGA 和 ASIC 正在逐步应用于加速 kNN 搜索，并报告了多种针对 3D 点云 kNN 搜索的定制加速器。该工作 [^18] 开发了一个基于 k-d 树的加速器，并对内存和内部并行性进行了优化，例如读/写聚合缓存和多工作器。同时，作者 [^20] 也提出了一个基于 GBDS 的结构，称为双分割体素结构 (DSVS) 以及异构加速方法。然而，这些之前的加速器在根本上受限于外部内存的限制，因此它们仍然无法实现令人满意的性能提升，并且无法扩展到未来的工作负载。
第七节 结论
本文提出了一种高并行的 3D 点云 kNN 搜索加速器，称为 ParallelNN。为突破关键的带宽瓶颈，我们将 ParallelNN 与最多 32 个并行通道的 HBM 结合起来。此外，我们从粗粒度并行性的角度重新审视 3D kNN 搜索问题，并提出了一种新颖的基于关键帧八叉树的并行 kNN 搜索算法，显著提升了内存受限 3D kNN 搜索核的效率。与此同时，实施了硬件优化方案以支持并行八叉树构建与搜索，包括双缓冲技术、精细的基于轨迹的缓存，以及 C2Es 中的插入排序和流水线优化。通过基于 HBM 的算法-架构协同优化，ParallelNN 能够相较于软件基线实现 107.7*×* 的加速和 73.6× 的能效提升。与 GPU 实现相比，ParallelNN 在时间和能效上分别实现了 12.1*×* 与 31.1*×* 的提升。更重要的是，ParallelNN 在最先进架构上实现了 11.4× 的加速，并能轻松推广到其他基于八叉树的应用。
脚注
查询点数 @ 参考点数。
基于 Virtex-7 的 ADM-PCIE-7V3 FPGA。
. 本文中，HBM 指代 Xilinx FPGA 的双堆叠 HBM2。