BitNN：点云中K最近邻搜索的位序列加速器

摘要

基于点云的机器感知应用在各类场景中已取得巨大成功。在本工作中，我们聚焦于点云 k-Nearest Neighbor (kNN) 搜索，这是点云中的重要核心技术。现有的 kNN 加速技术忽视了欧氏距离计算过程中的操作级优化，由于存在大量不必要的计算和多样的数据精度需求，导致效率低下。我们从新的位序计算视角重新审视点云 kNN 搜索，并提出 BitNN，一种面向点云 kNN 搜索的位序架构。 BitNN 支持自适应精度处理和不必要计算的削减，显著提升了 kNN 搜索的性能和能效。为此，我们首先提出一种面向 kNN 搜索的位序计算方法，该方法推导出逐位计算欧氏距离的递归表达式。随后，提出了按维度的点云编码方法和按点的数据布局方法，以实现基于位序计算的自适应精度处理。此外，我们提出了一种位序 kNN 搜索的早停机制。通过根据少量位估计距离下界，可减少大量不必要的计算。最后，我们设计了一种高效的位序 kNN 加速器。该加速器利用大规模并行性来提升计算效率。我们用若干广泛使用的点云数据集评估了 BitNN。相较于同等规模的架构，BitNN 取得了最高 6.6 \times 的加速比和 3.6 \times 的能效提升。此外，BitNN 可轻松集成到现有的位并行 kNN 加速器中。我们用位序计算技术提升了最先进的 kNN 加速器 ParallelNN，获得最高 4.4 \times 的加速比和 2.9 \times 的能效

作者

Meng Han CCSE国家重点实验室，北京航空航天大学，北京，中国

Liang Wang CCSE国家重点实验室，北京航空航天大学，北京，中国

Limin Xiao CCSE国家重点实验室，北京航空航天大学，北京，中国

Hao Zhang CCSE国家重点实验室，北京航空航天大学，北京，中国

Tianhao Cai 北京航空航天大学计算机科学与工程学院, 北京, 中国

Jiale Xu 上海启智研究院上海交通大学, 上海, 中国

Yibo Wu 清华大学集成电路学院, 北京, 中国

Chenhao Zhang 北京航空航天大学计算机科学与工程学院, 北京, 中国

Xiangrong Xu CCSE国家重点实验室，北京航空航天大学，北京，中国

出版信息

期刊： 2024 ACM/IEEE 第51届国际计算机体系结构年会 (ISCA) 年份： 2024 页码： 1278-1292 DOI： 10.1109/ISCA59077.2024.00095 文章编号： 10609723

指标

总下载量: 1174

资助

中国国家自然科学基金

关键词

IEEE 关键词: 点云压缩, 布局, 计算机体系结构, 欧几里得距离, 最近邻方法, 并行处理, 硬件

Index Terms: K最近邻, 点云, 邻域搜索, K最近邻搜索, 能效, 距离计算, 计算操作, 精度要求, 不必要计算, 欧几里得距离计算, 点云数据集, 深度神经网络, 每周期, 3D 扫描, 线性加速器, 邻近点, 最近点, 计算单元, 平方欧几里得距离, 序列化, 查询点, KITTI 数据集, 芯片内存, 精确搜索, 最近邻点, 位宽, 区域开销, 同时定位与地图构建, 最高有效位, 关键操作

Author 关键词: k最近邻搜索, 位级序列化, 加速器, 点云

未定义

第 I 节. 引言

点云是一组直接表示物理对象或三维场景的点的集合。最近，随着基于三维几何的算法受到关注，点云已广泛应用于多种场景，例如自动驾驶、机器人和虚拟现实/增强现实（VR/AR）。k-最近邻（kNN）搜索是三维点云的关键基本操作，旨在为给定查询点找到 k 个最近邻。kNN 搜索往往位于基于点云的应用的关键路径，例如机器感知 [^1] ¹、三维重建 ²、同步定位与地图构建（SLAM） [^4] ³ [^6] 等。许多基准测试表明，kNN 搜索在最先进的实现中可占总运行时间的 80 \%，参考 ⁴ [^8] [^9]。这些应用往往在能源受限的环境中运行，对实时和节能处理提出了重大挑战。

目前，已有若干面向领域的 kNN 加速器被提出以应对这一挑战。其中，基于分区的 kNN 搜索加速器，如 QuickNN [^8] 与 ParallelNN ⁵，是最有效的 kNN 搜索加速架构。它们在时间效率与搜索精度之间取得了折衷。首先，将点云划分为多个小区域；随后，对于给定的查询点，仅在特定区域内选择性地搜索邻近点，显著减小搜索空间。还提出了多种优化技术以解决不规则内存访问问题。虽然现有加速器已广泛探索 kNN 搜索的算法与架构级优化，但在点云规模变大时，仍存在满足实时处理需求的性能差距。我们进行了案例研究，发现欧氏距离计算——点云 kNN 搜索中最基本的操作——在最先进实现 ⁶ 中占据了 80 \% 以上的运行时间。

执行 kNN 搜索时，现有加速器首先完整加载两点的坐标数据，然后计算两点之间的欧氏距离。然而，我们观察到对所有点进行精确距离计算并非必要。例如，考虑一个 1 NN 任务，目标是在 100 个参考点中寻找离 q（位于 [0,0,0]）最近的点。遍历 50 个参考点后，假设当前最近点的距离为 3.14。继续遍历下一个位于 ⁷ 的点。⁸、⁹。¹⁰、¹¹。¹² 的点时，我们发现距离计算实际上是多余的，因为粗略估算距离不可能小于 3.14。然而，现有加速器必须加载操作数并执行至少 8 次算术运算来进行精确距离计算。这导致高内存访问和计算成本。本文通过使用位串行方法，仅用点坐标的一小部分位来估算欧氏距离，可以将计算成本降低 90 \%，将内存访问降低 84 \%，显著提升 kNN 搜索的性能和能效。

与此同时，点云数据类型是 kNN 距离计算的另一个重要属性。通过对真实世界点云的广泛探索，我们发现点云所需的数值精度在不同场景下各不相同。例如，一台用于自动驾驶的典型 LiDAR ¹³ 具有 120 米范围和 0.01 米精度，而用于 3D 建模的 3D 扫描仪 ¹⁴ 的范围为 0.2 米，精度为 10^{-6} \mathrm{~m}。然而，现有实现采用 one-size-fits-all 方法，使用 worst-case 数据类型，对所有场景都适用，留下了显著的性能改进空间。

与其采用固定精度的点云处理并对所有点执行完整的欧氏距离计算，不如探索 Bit-Serial Computation (BSC) 技术，通过支持自适应精度处理和不必要计算的减少，实现更高的性能和能效。一般来说，BSC 将多比特数据切分为多个位数据，每个周期处理一位。目前，BSC 在加速深度神经网络 (DNNs) 上已取得显著成功 ¹⁵ ¹⁶ ¹⁷ [^20]。然而，位串技术无法直接用于加速 kNN 搜索，因为 kNN 搜索使用欧氏距离来识别邻近点。欧氏距离计算不同于 DNNs 内部的操作。关于欧氏距离的位串计算的理论和架构尚未被探索。

在本工作中，我们提出 BitNN，一种用于点云中 k-最近邻搜索的位串加速器，为提升 kNN 执行性能提供了新的维度。具体而言，我们提出了一系列创新机制和架构，包括位串计算、数据布局、提前终止和并行架构。据我们所知，这是首个将位串计算扩展到 3D 点云 kNN 的工作。本文的主要贡献总结如下。

我们提出了一种针对 kNN 搜索的新型位串计算方法，该方法推导出递归表达式，以位为单位计算欧氏距离。该方法为 kNN 加速器设计提供了理论基础。
我们提出了按维度的点云编码方法和按点的数据布局方法。这些方法可以压缩点云，进一步减少 40.2 \% 离芯片内存访问。
我们提出了一种位串 kNN 搜索的提前终止机制。通过基于少数位估计欧氏距离的下界，可减少大量不必要的计算。实验表明，该方法在某些情况下甚至可以实现高达 90 \% 的计算削减。
我们提出了一种高效的并行架构用于位串 kNN 搜索。该加速器集成了一组 Bit-serial Distance Units (BDUs)。BDU 消除了计算平方距离所需的乘法器。相较于基线架构，该加速器可实现高达 6.4 \times 的加速比和 3.6 \times 的功耗效率提升。

Fig. 1. -

Fig. 1. kNN 搜索与欧氏距离计算及 topK 操作的流水线执行示意图.

值得注意的是，本工作侧重于操作级优化，这与现有的利用算法级和架构级优化的技术是正交的。以最先进的 ParallelNN 加速器为例，我们用 BDU 数组和 topK 数组取代了执行距离计算和 topK 操作的架构。基于位串行的 ParallellNN 相比原始的 ParallelNN 实现，速度提升可达 4.4 \times，功率效率提升可达 2.9 \times。

第 II 节背景与动机

A. 点云

点云是一组点 P=\left\{p_{i}\right\}，其中每个点在笛卡尔坐标系中由 \langle x, y, z\rangle 表示。点云由诸如 LiDAR 和深度相机等 3D 扫描仪持续生成，以感知环境。随着传感器价格下降和体积缩小，点云已被广泛应用于许多场景，例如无人驾驶、机器人等。点云规模（点数）和生成频率（每秒帧数）是 3D 扫描仪最重要的两个属性。随着 LiDAR 技术的发展，点云以更高的频率和更大的规模生成，这对点云应用提出了更高的计算需求。最新的用于无人驾驶的 LiDAR 每 50 毫秒可生成多达 460,000 个点 [^21].

B. kNN 搜索算法与加速器

点云 k 近邻（kNN）搜索是 3D 度量空间中 kNN 搜索的一种情况。对于给定的查询点，它在一组参考点中找到 k 个最近邻点。图 1(a) 说明了在八个参考点中对三个查询点 (Q 0, Q 1, Q 2) 的 kNN 搜索（R 0-R 7)，其中 k=3）。因此，R 0, R 1 和 R 3 被确定为 Q 0 的邻居点。一般而言，kNN 搜索涉及两个关键操作。如图 1(b) 所示，一个是 欧氏距离计算 操作，用于计算查询点与参考点之间的欧氏距离；另一个是 topK 操作，选择 k 个距离最小的参考点。特别地，为了避免在所有距离计算完成后才执行 topK，这会需要大量内存来存储距离结果，常见的优化 ¹⁸ [^8] [^22] 是构造一个包含 k 个最近点的临时列表，并在每处理完一个参考点后更新它。因此，在 kNN 搜索过程中，当前 k 近邻点的距离是可用的。

Fig. 2. -

图 2. 三者的延迟分解

Fig. 3. -

图 3. 基于 kNN 的应用 [51] [53] 在多平台、多规模 [46] 下的 kNN 搜索运行时间。点云。

KNN 搜索是点云应用执行的关键操作。例如，在自动驾驶场景的里程计估计任务 [^23] 中，算法每秒持续从 LiDAR 接收多帧点云。它利用 kNN 搜索在连续帧之间建立点对应关系，从而促进车辆运动估计。为满足实时处理需求，系统必须每秒处理数百万点。这个繁重的工作负载使 kNN 成为自动驾驶车辆操作中最耗时、最耗能的核心之一 ¹⁹。

目前已经提出了几种专用 kNN 加速器。其中，基于分区的 kNN 搜索加速器，如 QuickNN [^8] 和 ParallelNN ²⁰，是最有效的 kNN 搜索加速架构。这些加速器将 kNN 搜索分为两阶段：分区阶段和搜索阶段。在分区阶段，使用 kd-树或八叉树将大型点云划分为多个小区域。随后，加速器根据查询点的几何属性将其分配到特定区域。在搜索阶段，加速器利用多台计算单元同时执行欧氏距离计算和 top K 操作，仅在给定查询点的特定区域内寻找 k 最近邻点，从而得到近似结果。

C. 性能特性

我们对 kNN 搜索进行特征分析，以了解瓶颈并识别优化机会。为此，我们在多种平台和多规模点云上对性能进行剖析，包括 CPU、GPU 以及域特定点云 kNN 加速器。

延迟分解。 图 2 说明了 kNN 搜索在三个典型应用 [^6] [^25] [^1] 的延迟分解。kNN 搜索约占这些应用总运行时间的 60 \% 至 80 \%。鉴于这些应用通常部署在能源受限系统中，并需要与环境进行实时交互，低延迟和能效的 kNN 处理已成为关键挑战。

Fig. 4. -

图 4. 基于分区的 kNN 加速器上 kNN 搜索的运行时间分解及非连续 DRAM 访问占比 [36] [9]。

Fig. 5. -

Fig. 5. 本工作与先前邻居搜索加速器之间的关系 [36] [9] [15] [27] [52].

Runtime Analysis. 当前实现无法满足实时处理要求，因为点云规模不断增长。图 3 描述了不同平台和点云规模下 kNN 搜索的运行时间。CPU 和 GPU 的实现基于广泛使用的 FLANN 库 [^26]。一条水平虚线表示最新 LiDAR [^21] 的点云生成间隔，作为满足实时处理要求的参考。一个红点表示点云大小。2.8 \times 的性能差距仍然存在于最先进的加速器，凸显了加速 kNN 搜索的必要性。

Bottleneck Analysis of Partition-based KNN Accelerators. 图 4 量化了三种基于分区的 kNN 加速器的运行时间分解以及非流式 DRAM 访问率。当前基于分区的 kNN 加速器因两方面原因而产生高计算成本：(i) 基于分区的 kNN 操作需要大量的 GOP。例如，在流行的基于 LiDAR 的里程计基准 ²¹ 中，在典型的构建场景（约百万规模的点云）上运行 kNN 搜索大约需要 120 GOP。该计算占 ParallelNN 运行时间的 80 \% 以上。计算开销主要来自欧氏距离计算操作。(ii) 之前的工作 [^8] ²² ²³ ²⁴ [^22] 有效解决了不规则内存访问问题。SimpleKD [^8] 是基于分区的 kNN 搜索的基线架构。它执行基于 kd-tree 的标准 kNN 搜索，树遍历的不规则导致内存访问非连续且效率低下。内存访问主导了运行时间。之前的工作提出了多种优化技术来解决此问题，例如读写聚集缓存 [^8]，以及两阶段树遍历 ²⁵ 等。最先进的 kNN 加速器 ParallelNN ²⁶ 通过完全将 kNN 搜索适配至 HBM，利用高外部带宽进一步提升性能。因此，参考点的冗余 DRAM 访问被消除，所有 DRAM 访问变为流式。然而，计算，特别是欧氏距离计算操作，成为性能瓶颈。

进一步计算优化的必要性。 当点云大小超过200K时，现有kNN加速器无法满足实时处理需求。计算操作占据了大部分运行时间，尤其是欧几里得距离计算和topK操作。然而，增加计算单元的收益递减，需要投入大量额外计算单元，导致面积开销大、功耗效率降低 [^8]。与以前主要关注优化不规则内存访问的方法不同，我们的方法针对kNN操作级优化，如图5所示。该加速器通过在位级减少不必要的计算和内存访问，实现更高的性能和功耗效率。重要的是，这些技术与现有的算法-体系结构协同设计工作是正交的。将位串行计算技术与现有加速器结合，将进一步提升性能。

Fig. 6. -

图6. 点云kNN搜索的三条观察

D. 观察与关键思想

通过对现有实现的深入探索，我们得到三个关键观察，展示了kNN搜索性能提升的巨大空间，如图6所示。

Observation I: 欧几里得距离中的大多数计算是多余的。 图6(a)展示了一个kNN任务的例子（为简化假设为1D空间），该任务旨在找到k个最近点到位于153的查询点q。在当前迭代中，参考点r位于22，被判断是否能加入最近邻列表。在传统方法中，必须完成r与q之间完整的平方欧几里得距离计算。图6(a)显示，平方欧几里得距离为17161，远高于当前第k近邻的平方距离（示例中为16）。然而，我们观察到，仅凭最显著的2位就能推断出结果。换言之，q和r的最显著2位分别为‘ 10 ’和‘ 00 ’，可确保q \geq 128和r \leq 63成立，意味着平方欧几里得距离肯定大于16。其余6位不会影响最终结果，这些位的计算实际上是多余的。

关键思想: 我们提出一种按位串行的欧几里得距离计算机制以及一种提前终止机制。欧几里得距离按位计算，从坐标的最高有效位到最低有效位。距离的下界基于少量位估计。这样，当估计的下界超过当前的 k 阈值时，计算就可以提前终止。

观察 II：点云中的数据具有多种范围和精度。固定数据类型对点云的效率较低。 点云数值表示的精度要求随场景甚至维度而异。正如图 6(b) 所示，虽然 LiDAR 和 3D 扫描仪是常用的 3D 传感器，但它们的感知范围和精度差异很大。用于测量的 LiDAR ²⁷ 范围为 2000 m，精度为厘米级；而用于物体 3D 建模的 3D 扫描仪 ²⁸ 范围为 0.2 m，精度为微米级。此外，即使在单一场景中，三个维度之间的范围也不同。我们已对 Waymo 数据集 [^30] 中的点云坐标分布进行了分析，该数据集是自动驾驶的典型数据集。正如图 6(b) 中间所示，结果表明 X 和 Y 维度 (-75 m \sim 75 m) 的范围远高于 Z 维度 (0 \mathrm{~m} \sim 5 \mathrm{~m}) 的范围。然而，现有实现依赖于“一刀切”的方法，使用“最坏情况”数据类型来满足所有场景和所有维度。例如，绝大多数 CPU 和 GPU 实现使用浮点数据类型 ²⁹ ³⁰ ³¹，而最近的加速器则使用定点数据类型 ³² ³³。

关键思想: 基于按位串行计算，我们提出一种按维度点云编码方法。每个维度的数值精度可以根据其范围和精度自适应。

观察 III：位填充导致外部内存访问浪费。 现有实现将点云打包为点的数组。每个点由三个定点值或浮点值表示。此外，现有实现往往将点数据结构填充到 64 位 ³⁴ [^8] ³⁵ 以对齐到地址边界。例如，ParallelNN 加速器将一个点格式化为 64 位。如图 6(c) 所示，三个 15 位定点值存储点的坐标，其余 19 位用于 kNN 搜索 1。通过这种方式，实际外部内存访问量小于 75 \%。此外，位填充导致片上内存利用率低下，在处理大规模点云数据尺寸时产生冗余 DRAM 访问 ³⁶.

关键思路： 我们提出一种逐点数据布局方法来解决此问题。与将单个点存储在 64 位内不同，逐点方法将 64 个点的 1 位数据存储在 64 位空间内。这种映射方法可以很好地与位序计算结合，因为计算是每个点每个周期执行一位。

E. 设计考虑

位序计算（BSC）将多位数据切分为多个位数据，并每周期处理一位。在与 DNN 量化技术 ³⁷ 结合后，BSC 已成功加速 DNN。通过将 DNN 模型量化为技术，算子是若干工作 [^20] ³⁸ ³⁹ 专注于内积运算，内积运算是 DNN 的核心操作。加速器可以利用位级稀疏性和 DNN 工作负载的可变精度来减轻不必要的计算，进一步提升性能和能效。然而，欧氏距离计算与 DNN 内部的运算差别很大。欧氏距离的计算相较于内积运算多了额外的减法运算。欧氏距离运算中乘法算子的操作数来自其减法运算结果。减法中的借位操作阻碍了使用内积方法进行欧氏距离计算的高效利用。现有 BSC 技术无法直接用于加速 kNN 搜索。位序 kNN 搜索的理论和体系结构尚未被探索。

Table I- N

表 I

本文从新的位序计算视角重新审视点云数据类型和 kNN 计算操作，为提升 kNN 执行性能提供了新的维度。具体而言，我们提出了一系列创新机制和架构，包括位序计算、数据布局、早停和并行架构。这些新方法和架构使加速器能够支持自适应精度处理和不必要计算的削减，显著降低计算成本和内存访问。这些技术与探索算法和架构层面优化的现有技术是正交的。将位序技术与现有加速器结合，将进一步提升性能。

第 III 节. 位序 KNN 搜索计算

本节介绍了欧氏距离的位序计算（见 III-A 节）。随后提出了按维度的点云编码方法（见 III-B 节）和按点的数据布局方法（见 III-C 节）来压缩点云。随后设计了一种有效降低不必要计算的早停机制（见 III-D 节）。最后提出了位序 kNN 搜索算法（见 III-E 节）。表 I 列出了本节中使用的符号。

A. 欧氏距离的位序计算

在笛卡尔坐标系中，两个点 q 与 r 之间的欧氏距离可以表示为 \sqrt{\sum_{d=1}^{3}\left(q_{d}-r_{d}\right)^{2}}。为了避免执行平方根操作，常见的优化是计算平方欧氏距离。

\begin{equation*}\operatorname{Dist}^{2}\left(q, r\right)=\sum_{d=1}^{3}\left(q_{d}-r_{d}\right)^{2} \tag{1}\end{equation*}

通过引入一些度量和一系列推导，公式 (1) 被转换为公式 (3)，说明欧氏距离可以从点坐标的最高有效位到最低有效位逐位计算。随后在公式 (4) 给出递归表达式，演示了位序计算中的操作。关键步骤如下。

我们定义了两个度量，分别称为 \operatorname{dist}_{m}^{2}(q, r) 和 f_{d, m}(q, r)。d i s t_{m}^{2}(q, r) 表示仅保留两点 q 与 r 坐标中最高 m 位时，它们之间的部分平方距离。根据此定义，最终的 \operatorname{Dist}^{2}(q, r) 等于 \operatorname{dist}_{B}^{2}(q, r)，其中 B 为点坐标的位宽。同样，f_{d, m}(q, r) 表示仅保留两点 q 与 r 坐标中最高 m 位时，在 d 维度上的坐标部分相减。

\begin{align*}{dist}_m^2(q, r) & =\sum_{d=1}^3\left[\sum_{b=B-m}^{B-1}\left(q_{d, b}-r_{d, b}\right) \times 2^{b+m-B}\right]^2 \\f_{d, m}(q, r) & =\sum_{b=B-m}^{B-1}\left[\left(q_{d, b}-r_{d, b}\right) \times 2^{b+m-B}\right] \tag{2}\end{align*}

经过公式推导，方程（2）中的 \operatorname{dist}_{m}^{2}(q, r) 可以重写为方程（3）。推导的细节见附录 B 的定理 1。

\begin{align*}& {dist}_{m}^{2}\left(q, r\right)=2^{2\left(m-B\right)} \sum_{b=B-m}^{B-1} 2^{2 b}\left[\sum _ { d = 1 } ^ { 3 } \left[\left(q_{d, b}-r_{d, b}\right)^{2}+\right.\right. \\ & \left.\left.4 \times\left(q_{d, b}-r_{d, b}\right) \times f_{d, B-b-1}\left(q, r\right)\right]\right] \tag{3}\end{align*}

如我们所见，\sum_{b-B-m}^{B-1} 2^{2 b} 位于方程（3）的最外层，意味着平方欧氏距离可以按位计算。具体来说，dist { }^{2}(q, r) 等于 m 项的和。在从 b=B-1 计算 \operatorname{dist}_{m}^{2}(q, r) 到 b=B-m 的过程中，每个项仅与最高显著的 b 位的值有关（在方程（3）中记为 q_{d, b}, r_{d, b}）以及部分减法值（在方程（3）中记为 f_{d, B-b-1}(q, r)）。我们进一步将方程（3）转换为递归表达式以便清晰展示。该转换的细节见附录 B 的推论 1。

\begin{align*}{dist}_{m}^{2}\left(q, r\right)= & \underset{{dist}_{m-1}^{2}\left(q, r\right)\lt \lt 2}{\sim}+\sum_{d=1}^{3}\left(q_{d, B-m}-r_{d, B-m}\right)^{2}+ \\ & \sum_{d=1}^{3}\left(\left(q_{d, B-m}-r_{d, B-m}\right) \times f_{d, m-1}\left(q, r\right)\right)\lt \lt 2 \\ f_{d, m}\left(q, r\right)= & f_{d, m-1}\left(q, r\right)\lt \lt 1+\left(q_{d, B-m}-r_{d, B-m}\right) \tag{4}\end{align*}

如我们所见，\operatorname{dist}_{m}^{2}(q, r) 可以按位递归计算。具体而言，\operatorname{dist}_{m}^{2}(q, r) 是三个部分的和：(1) 对 dist _{m-1}^{2}(q, r),(2) 的左移，求三维中 q 与 r 的最高显著 m 位差平方之和；(3) 对 \left(q_{d, B-m}-r_{d, B-m}\right) \times f_{d, m-1}(q, r) 的左移求和（适用于三维）。由于 q_{d, B-m}-r_{d, B-m} 的结果只能是 -1,0 或 1，乘法运算可以通过多路复用器实现。

因此，平方欧氏距离可以通过加法树、逻辑门和多路复用器按位计算。简化示例见图 7。位序计算从最高有效位到最低有效位进行，耗时 5 个周期即可得到最终结果 81。该结果与常规计算得到的结果相同：(18-9)^{2}=81，验证了位序欧氏距离计算机制。严格证明见附录 A 和 B。

Fig. 7. -

图 7. 两个一维点 q 与 r 的欧氏距离位序计算示例。q 为 18，r 为 9.

B. 按维度的点云编码

我们提出一种按维度的点云编码方法，能够适应可变精度需求。点云编码分为三步。

缩放与四舍五入。 点云的浮点坐标被放大并转换为整数。如第 II-D 节所述，3D 传感器的精度有限。因此，一个足够大的缩放因子不会影响 kNN 搜索结果 [^22] ⁴⁰ [^36]。对于点 p，缩放和向上四舍五入点云坐标的过程可表示为

\begin{equation*}p_{d}^{\prime}=\left\lceil p_{d} \times { scale }\right\rceil \tag{5}\end{equation*}

非负整数化。 点云的整数坐标被转换为 无符号整数。为点云计算包围盒，并根据公式 (6) 计算每个点的坐标平移，其中高 d_{d} 和低 d_{d} 表示包围盒在 d 维度上的上限和下限。若同时对两点加上相同偏移量，欧氏距离不变，因此转换不会影响搜索结果。与有符号二进制补码数据类型相比，使用无符号整数数据类型可以进一步简化 BDU 的设计，见第 IV-C 节。

\begin{equation*}p_{d}^{\prime \prime}=p_{d}^{\prime}+\left\lceil\frac{2^{\left\lceil\log _{2}\left({ high }_{d}-{ low }_{d}\right)\right\rceil}-{ high }_{d}-{ low }_{d}}{2}\right\rceil, \forall d=1,2,3\tag{6}\end{equation*}

按维度序列化 点的坐标被序列化为按维度的位流。序列化有两个步骤。首先，消除不必要的位。位消除后，坐标在三个维度上的位宽不同。具体而言，每个维度 d 使用 \left\lceil\log _{2}\left(high_{d}-l o w_{d}\right)\right\rceil 位。其次，点坐标值按维度方式序列化。图 8 展示了点 (17,10,4) 的序列化过程，它被序列化为 12 位流。每个维度有不同颜色。序列化从 MSB 开始到 LSB，按顺序在三个维度之间交替，这与按位距离计算的顺序相匹配。黑色箭头表示图 8 中的序列化顺序。此外，使用 维度码流 来识别该位所属的维度。具体而言，每个位需要 2 位 维度码，其中 2’b01、2’b10 和 2’b11 分别表示 X, Y 与 Z。在特定的 kNN 搜索核中，点云编码模式和数据宽度对查询点和参考点保持一致。因此，维度码流 在所有点之间共享，导致内存开销可忽略不计。

Fig. 8. -

图 8. 按维度序列化示例。一个点的位置为 (17,10, 4)。位消除后，坐标值的长度从 6 位降至 5 位、4 位、3 位，分别对应 \mathrm{X}, \mathrm{Y}, \mathrm{Z} 维度。按序列化后，生成 12 位点位流。

Fig. 9. -

图 9. 将 8 个点（点 A-H）位流存储到 SRAM 的示例。SRAM 的宽度为 8 位。

C. 逐点数据布局

传统方法将单个点封装在固定宽度的数据结构中，并使用填充位来确保边界对齐（即填充到 64 位）。然而，填充位会导致不必要的片上和片外内存访问。我们提出了一种逐点数据布局，避免了填充字段。如图 9 所示，多个点的位流被聚合。相反，点的位流被存储在 SRAM 的多列中，而不是将一个点存储在 SRAM 的一行中。这样，位流的可变长度就能在固定宽度的 SRAM 中存储，而不需要填充。此外，该映射方法适用于位序计算，因为它每周期为每个点计算一位。

D. 提前终止机制

位序欧几里得距离计算机制为终止不必要的计算提供了新的机会，显著降低了计算成本和片上内存访问量。具体而言，在位序欧几里得距离计算过程中，q 与 r 之间的部分距离 {dist}_{m}^{2}(q, r) 随着 m 从 1 增加到 B，逐渐达到完整值 {Dist}^{2}(q, r)。一旦确认 r 永远不会成为 kNN 的结果，就可以及时终止计算。通过这种方式，r 的剩余计算量被减少，并且无需加载 r 的其余比特流数据。

为实现此目标，我们提出了一种下界估计方法和提前终止机制。下界估计基于这样一个事实：在欧几里得距离结果中，高位（MSB）对结果的贡献大于低位（LSB）。对于给定的两点 q 与 r，平方欧几里得距离的下界，用 g_{b}^{2}(q, r) 表示为

\begin{align*} g_m^2(q, r)=\left({ dist }_m^2(q, r)-\sum_{d=1}^3 h_{d, m}(q, r)\right) \times 2^{2(B-m)} \\ h_{d, m}(q, r)= \begin{cases}2 \times\left|f_{d, m}(q, r)\right|-1, & f_{d, m}(q, r) \neq 0 \\ 0, & f_{d, m}(q, r)=0\end{cases} \tag{7}\end{align*}

正如我们所见，估计的下界仅与 d i s t_{m}^{2}(q, r), f_{d, m}(q, r) 和 2(B-m) 有关，它们可以从位序欧几里得距离计算中的变量轻松获得。附录 C 展示了详细的推导过程。

借助下界估计方法，提前终止机制如下：在执行位序距离计算时，下界被估计并与当前 k 最近点的距离进行比较。当下界超过 k 最近点的距离时，计算将被终止。

图 10 展示了一个例子，证明了位串欧氏距离计算机制，并说明了早期终止的优势。若没有早期终止机制，完整平方欧氏距离的计算需要 8 个周期。该平方欧氏距离为 466。然而，利用早期终止机制，q 与 r 之间的欧氏距离计算可在 3 个周期后停止，实现 62.5 \% 的运行时缩短。原因在于估计的下界 256 超过了当前第 k 个 d i s t^{2}，其值为 100。即使再计算完整距离 5 个周期，结果仍大于 100。因此，r 将不会被更新到 k 的最近邻列表中。

E. 位串 K 最近邻搜索

基于位串欧几里得距离计算机制和早停机制，提出了一种位串k近邻搜索算法。伪代码见算法 1。如第 1-4 行所示，对于给定的查询点 q，它与每个参考点计算欧几里得距离。bitSerialCompute 函数的细节见第 6-14 行。该函数首先初始化一些必要的变量。然后，它使用等式 (4) 和 (7) 按位串方式更新 dist2| 和 lowbound。该函数在每个循环中处理 q 和 r 的一位。当 lowbound 超过 kth_dist ⁴¹ 时，计算终止，如第 11-12 行所示。

第四节. 位串KNN 架构

本节介绍了一种面向领域的按位串行 kNN 加速器（Sec. IV-A）。该加速器利用 kNN 搜索的巨大并行性以提升性能（Sec. IV-B）。在加速器内部，按位串行距离单元（BDU）执行按位串行欧氏距离计算，并利用早停机制减少不必要的计算（Sec. IV-C）。此外，支持任意 k 的 topK 数组也被提出（Sec. IV-D）。最后，我们讨论将 BitNN 与现有的按位并行 kNN 加速器相结合（Sec. IV-E）。

Fig. 10. -

图 10。q 与 r 之间平方欧几里得距离的位串计算与下界估计示例。假设查询点 q 位于 x‑y 坐标系中的 (23,1)，参考点 r 位于 (2,6)。当前 q 的 k 号值为 100。x 维度使用 5 位编码，y 维度使用 3 位编码。在早停机制的帮助下，计算在 3 个周期内终止，减少了 62.5 \% 运行时间。

Algorithm

算法 1：位串 kNN 搜索（BKNS）

A. 加速器概述

BitNN 架构概览如图 11 所示。它主要由 BDU 数组、查询缓冲区、参考缓冲区、topK 数组以及控制单元、DMA 等组件组成。BitNN 有两个 AXI 接口：一个用于外部存储器访问，另一个用于加速器配置。该设计使 BitNN 能轻松集成到更大的系统中。

BDU 数组在欧几里得距离计算中起关键作用。它由一组位串距离单元（BDU）组成，排列成二维网格。每个 BDU 对给定的两点执行位串距离计算。尽管查询点和参考点被广播到多个 BDU，窄数据总线不会增加 ASIC 物理设计的难度，如布局与布线。当距离计算完成后，BDU 将计算得到的距离和对应参考点的坐标（参考点位流）以流水线方式传输到 topK 数组。

Fig. 11. -

图 11。BitNN 的架构概览。

Algorithm

算法 2：并行位串 kNN 搜索

topK 数组包含多个 topK 单元，每个单元执行基于迭代的排序，以找到任意 k 最近点（见 Sec. IV-D）。基于 FSM 的控制单元配置 DMA、BDU 和 topK 数组。DRAM 存储查询点、参考点、结果数据和元数据（即点云的维度编码）。

Fig. 12. -

图 12。BDU 组件。

B. 位串 kNN 搜索的并行执行

BitNN 加速器在并行执行模式下执行 kNN 搜索。并行搜索的伪代码如算法 2 所示。该算法包含四级循环。

在初始阶段，即算法2第1-2行所示，算法在片上缓冲区约束内计算查询点和参考点的容量。

在前两层循环中，正如算法2第3-6行所示，查询点 Q_{N} 通过 DMA 被加载到查询缓冲区。随后，所有参考点以 R_{N} 个为一批被加载到参考缓冲区。当所有参考点处理完毕后，下一个 Q_{N} 个查询点被加载到查询缓冲区。然后上述处理会重复进行，直至所有查询点被处理完。前两层循环使 BitNN 能够在片上缓冲区容量约束内高效处理任意尺寸的点云，这是硬件设计中的关键考虑因素。

在最后两层循环中，算法2第7-13行所示，BDU 数组和 topK 数组处理由前两层循环加载的查询点和参考点。BDU 数组同时利用查询点级并行性和参考点级并行性。它能够同时处理 N 个查询点和 M 个参考点。在算法2第7-10行，查询点被从查询缓冲区取回到本地查询寄存器，并在必要时将临时 topK 记录加载到 topK 数组。随后，在算法2第11-12行，参考点以 M 个并行方式送入 BDU 数组。参考缓冲区每周期只需提供 M 位，因为每个 BDU 仅在每周期处理 1 位参考点，并且位于同一行的 BDU 处理相同的参考点。处理完 N 个查询点与 R_{N} 个参考点后，临时 topK 记录以位流形式存储在查询缓冲区。下一次迭代中，获取后续 N 个查询点以重复上述处理，直至所有查询点处理完毕。

C. 位序距离单元

BDU 的架构如图12所示。它由三个组件组成：平方距离逻辑、下界逻辑和发射逻辑。等式 (4) 和 (7) 中的乘法操作可以通过左移逻辑和多路复用器实现，取代通用乘法器，从而降低面积和能耗。

Fig. 13. -

图13。topK 单元的架构

方差距离逻辑按照等式（4）计算平方欧氏距离。如图12所示，方差距离逻辑接受三个输入：查询点比特流（表示为 q, 1 位）、参考点比特流（表示为 p, 1 位）以及维度码流（表示为 code，2 位）。由于坐标采用 unsigned integer 数据类型，只使用一个取反块。方差距离逻辑产生 \operatorname{dist}_{b}^{2}(q, p), f_{1, b}(q, p), f_{2, b}(q, p) 和 f_{3, b}(q, p) 的值。这些结果分别存储在一个 32 位寄存器和三个 16 位寄存器中。

下限逻辑根据等式（7）计算 {dist}^{2}(q, p) 的下限。如图12所示，下限逻辑接受两个输入：来自方差距离逻辑的 32 位 k_{\text {th }} dist2| 以及来自控制单元的左移指示器（表示为 2(B-b)）。通过比较器检查下限是否超过当前 k t h dist2| 来实现早期终止。最终，比较结果（表示为 Terminate）返回给控制单元。

Issue logic 将平方距离和参考点的坐标（参考点比特流）以同步方式传输到 topK 单元。参考点比特流由移位寄存器重构。

D. 任意 K 映射

最近邻数量在不同应用之间各不相同。为支持任意 k 个最近邻，我们提出基于迭代的 topK 单元。如图13所示，topK 单元由一个过滤器和若干排序节点组成。这些排序节点执行基于插入的排序（类似于 [^38]），针对流式查询和参考点进行了优化，以实现高吞吐量。尽管单个 topK 单元每周期只能处理一个 BDU 的计算结果，但它很少成为性能瓶颈，因为大多数 BDU 在满足早期终止条件时不会传输结果。此外，topK 单元中集成了一个过滤器，可过滤掉平方距离小于等于边界值的输入。

假设 topK 单元具有 N 个排序节点。对于特定的 kNN 搜索任务，m 阶最近邻点的平方距离记为 Dist { }_{m}^{2}，其中 m \leq k。

当 k \leq N 时，topK 单元充当普通的 N 排序器。每个 TopK 单元接收流式的 \left\{\right. dist ⁴²、coord. \} 数据，执行基于插入的排序以更新当前 topK 结果，并将 k 阶 d i s t^{2} 值返回给 BDU 数组以实现早期终止。为在最后一个节点固定 k 阶 d i s t^{2}，第一个 N-k 节点的 dist2| 寄存器填充为 0。

当 k\gt N 时，topK 单元在 \left\lceil\frac{k}{N}\right\rceil 次迭代中识别出 k 个最近点。具体而言，在第一次迭代中，topK 单元充当普通的 N 排序器。迭代结束时，N 邻点（从 top1 到 topN）按从小到大顺序依次存储在这些 N 已排序节点中。随后，最后一个排序节点的 d i s t^{2} 值，即 D i s t_{N}^{2}，被写入过滤器中的边界寄存器。下一轮迭代中，参考点再次被流式送入 BDU 数组。第一次迭代中发现的邻点将被过滤掉，因为它们的距离值小于或等于边界值。当所有参考点都被处理完后，topK 单元识别出 (N+1) 阶到 (2 \times N) 阶的最小距离点。随后，最后节点的 dist ⁴³ 值，即 D_{i s t}^{2}，被写入边界寄存器。该迭代持续进行，直到找到所有 k 最近邻。

由于在点云应用中 k 的值通常很小（\leq 64)，topK 单元由 16 个排序节点组成，可在 4 次迭代 (k \leq 64) 内找到所需邻点），实验表明，平均而言，我们的设计比 PointAcc ⁴⁴ 中提出的基于归并排序的 topK 引擎在相同并行度下快 1.58 \times。理论上，当 k\gt N 时，基于迭代的 topK 机制可能会忽略一些实际邻点，若查询点与多个参考点之间的距离等于边界值。然而，这种情况的概率很低。实验结果表明，它导致的搜索精度下降不足 0.3 \%。

E. 与现有位并行加速器的结合

本文主要聚焦于操作层面的优化技术，这与现有的利用算法和体系结构层面优化的方法相互独立。现有的点云 kNN 加速器采用多个欧几里得距离计算单元作为计算阵列，完全可以用位序列计算架构替代。以最先进的加速器 ParallelNN ⁴⁵ 为例。该加速器主要由 8 个分支构造引擎和 8 个分支搜索引擎组成。前者通过基于八叉树的方法将点云划分为多个小区域，并为每个查询点分配到特定区域。后者为每个查询点执行欧几里得距离和 topK 运算。每个查询点仅在单一区域内搜索邻居点，从而得到近似搜索结果。正如图 14 所示，为将位序列技术融合到 ParallelNN 中，整体加速器被划分为两个区域：位并行构造区和位序列搜索区。此外，还采用了若干序列化和反序列化组件来连接这两个区域。具体而言，构造引擎保留不变，而搜索引擎被若干 BDU 阵列和 topK 阵列所取代。通过这种方式，现有的优化技术得以复用，例如搜索空间缩减、查询点聚合、细粒度流水线以及 HBM 内存映射。

此外，BitNN 架构还能有效用于其他基于欧几里得距离的应用，例如半径搜索 ⁴⁶、最远点采样 ⁴⁷。例如，半径搜索的目标是找到位于预定距离内的点（记为 r）。要执行半径搜索，BDU 的输入（k 第 dist ⁴⁸）被配置为 r^{2}。

Fig. 14. -

图 14. (a) 位序列 ParallelNN 的架构。位并行区域的细节见 [9]。 (b) 序列化器和反序列化器组件的架构。

Table II-

表 II

第五节实验

A. 评估设置

基准测试。 我们对四个广泛使用的点云数据集进行了评估。如表 II 所示，我们选择了 KITTI ⁴⁹、Waymo [^30]、增强的 ICL-NUIM ⁵⁰ 和 SemanticKITTI ⁵¹ 数据集。选定的数据集既全面又逼真，涵盖了输入点云在尺寸、精度和模态上的多样性。我们将 SemanticKITTI 数据集中的多份点云融合，生成一系列大型点云。平均点云大小为 460,000。该合并数据集用于模拟与最先进 LiDAR [^21] 相关的工作负载。正如第 III-B 节所述，基于传感器的精度，我们分别为 KITTI、Waymo、ICL-NUIM 和 SemanticKITTI 数据集设置了 100、1000、10000 和 100 的缩放比例。作为常见做法 ⁵² [^8]，KITTI、Waymo 和 SemanticKITTI 数据集的地面点被移除，因为它们无信息量。遵循先前工作 ⁵³ [^40] [^41]，k 设置为 5。

基线。 我们采用两种硬件作为评估基线：精确搜索和近似搜索。硬件参数如表 III 所示。

Linear: 对于精确 kNN 搜索，我们设置了一个线性搜索加速器来执行暴力搜索。它直接与所有参考点计算距离，找到 k 个邻居点。该加速器拥有 16 个计算单元，每个单元执行位并行平方距离计算和 topK 排序。该加速器在先前工作 [^8] [^41] 的基础上得到良好优化，例如 ping-pong 缓冲和查询级并行以实现公平比较。 DRAM 参数基于 Micron 的 8GB DDR4-2400，并按照其数据手册 ⁵⁴ 建模。该表示反映了嵌入式系统场景，例如新兴的移动 SoC。

ParallelNN: 对于近似 kNN 搜索，我们使用 ParallelNN ⁵⁵ 作为基线加速器，它是最先进的位并行 kNN 搜索架构。 ParallelNN 是一种高效的 HBM 基础架构。它将多通道 HBM 结合起来，以提供大型外部带宽。 ParallelNN 拥有 8 条并行分支，每条分支都有 16 个计算单元。如第 IV-E 节所述，对于给定的查询点，它仅在小区域内搜索邻居点，得到近似搜索结果。

硬件实现。 我们设计了两个硬件加速器，分别命名为 BitNN 和 Bit-serial ParallelNN，分别对应基线中的 Linear 和 ParallelNN 架构，以充分评估位串行技术。

BitNN：BitNN由1024个BDU组成，按16 \times 64的拓扑结构组织。BitNN可以同时处理16个查询点，这与Linear和ParallelNN的一条分支相同。在参考点并行度方面，BitNN的总并行度比基线多64 \times。然而，这是公平的，因为位并行计算单元每周期消耗一个参考点（64位）。相比之下，位串行计算单元每周期只消耗参考点的一个比特。topK数组由16个topK单元组成，每个单元包含10个排序节点。BitNN的片上SRAM总计256 KB。查询缓冲区和参考缓冲区各占128 KB。

Bit-serial ParallelNN：我们将位串行技术应用于ParallelNN，并构建了名为Bit-serial ParallelNN的加速器来评估位串行技术的工作量。ParallelNN与Bit-serial ParallelNN的主要区别在于搜索组件。在Bit-serial ParallelNN中，我们用BDU数组和topK数组取代ParallelNN加速器中的原始位并行搜索引擎，具体如第IV-E节所述。图14展示了Bit-serial ParallelNN加速器的架构。片上内存、频率、工艺和DRAM 2被配置为相同，以便公平比较。

实验方法。 我们使用Verilog实现加速器，并通过RTL仿真验证设计。硬件由Synopsys Design Compiler在45 nm工艺技术下合成。功耗使用Synopsys PrimeTimePX通过标注门级切换活动来估算。内存编译器生成SRAMs ⁵⁶。我们使用DRAMsim3 ⁵⁷来建模DRAM行为并测量DRAM能耗。我们使用OpenROAD ⁵⁸，一种开源的RTL-to-GDS工具，运行ASIC流程直到放样和布线（PnR）进行全面评估。

B. 性能和功耗效率

图15展示了BitNN在四个工作负载下，针对精确搜索和近似搜索的性能提升。具体而言，对于精确搜索，BitNN相对于位并行线性架构，在四个工作负载上分别实现了6.4 \times, 6.0 \times、3.7 \times和6.6 \times的加速比。对于近似搜索，Bit-serial ParallelNN相对于最先进的位并行ParallelNN，在四个工作负载上分别实现了4.4 \times, 3.0 \times、2.6 \times和4.1 \times的加速比。性能提升可归因于BitNN的BDU数组的强大并行性和提前终止机制，这将在第V-E节进一步分析。

Table III-

表III

Fig. 15. -

图15. 在四个工作负载上相对于基线的性能提升.

图16展示了BitNN在四个工作负载上的功率效率。相比于四个工作负载上的比特并行线性加速器，BitNN分别提升了 3.6 \times, 3.3 \times、2.1 \times 和 2.5 \times 的功率效率。比特串行 ParallelNN分别提升了 2.9 \times, 1.9 \times, 1.7 \times 和 2.7 \times 的功率效率，比较的是比特并行 ParallelNN。功率效率提升主要归因于轻量级的比特串行计算逻辑以及对芯片内/芯片外存储访问的减少。具体而言，BitNN在KITTI工作负载上将DRAM访问量降低了 66 \%，将SRAM访问量降低了 84 \%。这种减少是由于按维度的点云编码和提前终止机制造成的，后者将在V-D节进一步分析。

C. 区域与能耗分解

BitNN 与 Linear 架构使用 45 nm 设计库进行建模，以保持一致性。图17展示了 BitNN 的 ASIC 布局。所需总面积为 7.21 \mathrm{~mm}^{2}，相比 Linear 架构的 5.41 \mathrm{~mm}^{2}，产生了 33.2 \% 的面积占用。面积分解如表IV所示。片上缓冲区是面积占用的主要贡献者。就计算组件而言，综合报告显示 BitNN 中的1024个BDU相较于 Linear 的16个距离单元将面积增加了 218.6 \%。虽然BDU阵列提升了面积占用，但整个芯片面积的总体增长仅为 33.2 \%，因为片上存储占据了芯片面积的大部分。与此同时，Bit-serial ParalelNN 的序列化器和反序列化器组件分别占用了 0.026 \mathrm{~mm}^{2} 和 0.011 \mathrm{mm}^{2} 的面积，导致的面积占用不足 1 \%。

Fig. 16. -

图16. 在四个工作负载上相对于基线的功率效率提升.

Table IV-

表IV

图 18 细分了 BitNN 在 KITTI 数据集上运行 5 NN 的能耗。BitNN 总共消耗 16.45 mJ。计算逻辑占总能量的 64.5 \%，而 SRAM 和 DRAM 访问成本分别占总能量的 20.7 \% 和 14.1 \%。单个 topK 单元 (388 \mu \mathrm{W}) 的功耗超过单个 BDU（189 \mu W），但 topK 数组的整体能耗仍然很小。该差异的原因是 topK 数组中的 topK 单元数量仅为 BDU 数量的 1/64。尽管每个 topK 单元每周期只能处理一个 BDU 的计算结果，但由于 BDU 的早期终止条件，它很少成为性能瓶颈，防止满足条件时结果的传输。阻塞 topK 单元导致的延迟在 KITTI 基准测试中仅为 0.13 ms（0.3 \% 的总运行时间）。

D. 内存访问

BitNN 同时减少了片上和片外内存访问。图 19 描绘了在精确搜索期间四个工作负载的内存访问情况。平均而言，BitNN 在片上内存访问上减少了 70.6 \%，在外部内存访问上减少了 55.4 \%，从而进一步降低了能耗。内存访问的减少归因于两个因素。

首先，按维度的点云编码方法有效地压缩了点云。与传统的点云 kNN 加速器通常为每个点使用固定的 64 位表示不同，BitNN 在每个维度上动态调整位宽。例如，KITTI 点云的几何信息使用 14、14 和 9 位对三维进行编码，导致总位宽为 37，点云大小减少了 42.2 \%。该编码方法消除了在片外内存中存储不必要填充位的需求，从而提高了昂贵片外内存带宽的利用率。

图 17. BitNN 的后期 PnR 平面图（无 RAM）。

Fig. 18. -

图 18. BitNN 在 KITTI 基准测试中的能量分解。

Fig. 19. -

图 19. 四个工作负载的片上和片外内存访问。

其次，早期终止机制用于减少片上内存访问。点数据逐位加载到 BDU 数组中。当所有 BDU 满足终止条件时，当前点的剩余位被跳过，从而显著减少了 SRAM 访问。

E. 消融研究

图20展示了所提方法在四个数据集上对精确搜索和近似搜索的有效性。该加速器仅使用位序列计算，相比基线实现1.54 \times和2.18 \times的加速比。若没有早期终止机制，执行时间随点云编码位长度线性增长。

此外，早期终止机制显著提升了性能。图21是四个数据集计算周期百分比的直方图。正如我们所见，大多数点不需要完整计算。平均而言，BitNN在四个数据集上的精确搜索每点周期分别为10.1、10.7、17.4和9.7，显著降低了计算成本。具体而言，分布呈现两个显著峰值。第一个峰值位于3-18周期范围内，表明这些点满足早期终止条件，因此不需要进一步访问剩余点位。特别是，4.5 \% 的欧氏距离计算在KITTI数据集上在4周期内终止，减少了约90 \% 个计算周期。第二个峰值出现在横坐标末端。这是因为需要BDU加载整个点数据来完整计算欧氏距离以更新k最近邻点。我们拆分BitNN的运行时间，观察到BDU数组在大部分执行时间内保持活动，而topK数组仅在不到5 \% 的执行时间内激活。

F. 硬件敏感性分析

最近邻数量。 图22显示了最近邻点数变化时的延迟。将1 NN增加到10 NN，BitNN的运行时间略微上升2 \%。这是因为更大的k随后会提高早期终止阈值，使满足早期终止条件更加困难。

Fig. 20. -

图20. 四个工作负载的性能敏感性分析.

Fig. 21. -

图21. 四个工作负载的计算周期分布.

BDU数量。 图23说明了BitNN在不同数量和形状的BDU下的评估。将BDU从64增加到4096，运行时间从729毫秒降至14.5毫秒。最初，BDU数量的增加导致性能几乎线性提升。随着更多BDU的使用，趋势减弱，因为在所有BDU中满足早期终止条件变得更加困难。

第六节。相关工作

**点云kNN搜索。**点云kNN搜索是点云处理的重要核心。先前的工作已经为CPU ⁵⁹ 和GPU ⁶⁰ ⁶¹ ⁶² 提出了多种优化。为了实现高性能和能效，人们越来越关注在定制硬件加速器上加速kNN。最近，提出了若干基于划分的加速器，例如QuickNN [^8]、ParallelNN ⁶³。它们通过KDtree [^8] [^9] ⁶⁴、octree ⁶⁵ 和 voxel [^45] 将点云划分为多个桶。然后，它们设计了近似搜索算法，通过仅搜索在小范围内的邻居点来降低搜索空间。Saikia等人 [^46] 与 Mu 等人 [^47] 利用基于PIM的kNN加速器。ParallelNN ⁶⁶ 与 CHIP-KNNv2 ⁶⁷ 将架构与HBM内存耦合。Kaul等人 ⁶⁸ 提出了具有自适应精度的能效kNN加速器。然而，它仅支持最多128个候选点，并且在自适应精度乘法之前必须执行位并行减法。K-D Bonsai ⁶⁹ 是一种ISA扩展，能够压缩点云，降低半径搜索期间的内存使用。PointAcc ⁷⁰ 提出了可编程流水线架构。然而，现有工作以位并行方式计算欧氏距离。数据类型和数据宽度是固定的。与以前的加速器不同，BitNN 提出了位串行计算方式，并利用大规模位级并行和早期终止机制来提升性能。据我们所知，这是第一项将位串行计算扩展到3D点云kNN的工作。

Fig. 22. -

图22. 随着最近邻数目变化，BitNN架构的延迟增加。

Fig. 23. -

图23. 在KITTI数据集下，不同BDU数组尺寸对性能和功耗的敏感性

位序计算。 BSC 是一种在可变精度应用中占主导地位的计算方法。数个工作使用 BSC 处理 DNN，利用位级稀疏性 [^20] ⁷¹ ⁷² 以及可变神经元精度 ⁷³ [^50] [^51]。然而，现有的位序 DNN 加速器聚焦于内积计算操作，无法直接应用于 3D 点云的欧几里得距离。最近，位序 SIMD 在存储器内处理（Processing-In-Memory）受到相当多关注 [^52] [^53] ⁷⁴ [^54]。然而，它们仅支持合成基本逻辑运算（如 AND/OR/NOT）。

SECTION VII. 结论

本文提出一种位序加速器，以提升 3D 点云 kNN 搜索的性能效率。我们扩展了位序计算技术以实现欧几里得距离计算。此外，我们提出了一个早停机制，以消除位级的不必要计算。为进一步优化硬件，我们引入了多种方案，包括位级并行和任意 k 映射。BitNN 相比当前最先进架构实现了 4.4 \times 倍速度提升和 2.9 \times 的功耗效率提升。

附录

关于位序欧几里得距离计算的关键引理、定理和推论如下面所示。详细版本可在 Zenodo 上获取：https://doi.org/10.5281/zenodo.10948272.

SECTION A. Definition of {dist}_m^2(q, r) \text { and } f_{d, m}(q, r)

引理 1.

对于两个点 (q 和 r) 在 m\gt0 时，f_{d, m}(q, r) 可以基于 f_{d, m-1}(q, r) 计算。

\begin{equation*}f_{d, m}\left(q, r\right)=2 \times f_{d, m-1}\left(q, r\right)+q_{d, B-m}-r_{d, B-m} \tag{8}\end{equation*}

SECTION B. 位序平方欧几里得距离的计算

引理 2.

对于 P 的自然数，P 的平方等于 \sum_{b=0}^{B-1} P_{b}^{2}+2 \times \sum_{b=0}^{B-1} \sum_{b^{\prime}=b+1}^{B-1} P_{b} \times P_{b^{\prime}} \times 2^{b+b^{\prime}}，其中 B 是 P 的位宽。

定理 1.

d i s t_{m}^{2}(q, r) 可以按位序方式计算

\begin{align*}{dist}_{m}^{2}\left(q, r\right)= & 2^{2\left(m-B\right)} \sum_{b=B-m}^{B-1} 2^{2 b}\left[\sum _ { d = 1 } ^ { 3 } \left[\left(q_{d, b}-r_{d, b}\right)^{2}+\right.\right. \\ & \left.\left.4 \times\left(q_{d, b}-r_{d, b}\right) \times f_{d, B-b-1}\left(q, r\right)\right]\right] \tag{9}\end{align*}

推论 1.

对于两个点 (q 和 r) 的坐标值位宽为 B。当 m\gt0 时，{dist}_{m}^{2}(q, r) 等于：

\begin{align*} & {dist}_{m}^{2}\left(q, r\right)={dist}_{m-1}^{2}\left(q, r\right)\lt \lt 2+\sum_{d=1}^{3}\left[\left(q_{d, B-m}-r_{d, B-m}\right)^{2}\right]+ \\ & \sum_{d=1}^{3}\left[\left(q_{d, B-m}-r_{d, B-m}\right) \times f_{d, m-1}\left(q, r\right)\right]\lt \lt 2 \\ & f_{d, m}\left(q, r\right)=f_{d, m-1}\left(q, r\right)\lt \lt 1+\left(q_{d, B-m}-r_{d, B-m}\right) \tag{10}\end{align*}

SECTION C. 平方欧几里得距离的下界

两单维数值之间平方欧氏距离的下界在引理 3 中给出两点之间平方欧氏距离的下界在推论 2 中给出。

引理 3.

对于单维度，当 m\gt0 时,

\begin{equation*}{dist}_{B}^{2}\left(q-r\right) \geq\left[f_{1, m}\left(q, r\right)^{2}-h_{1, m}\left(q, r\right)\right]\lt \lt 2\left(B-m\right)\end{equation*}

其中

\begin{align*}h_{d, m}\left(q, r\right)= \begin{cases}2 \times\left|f_{d, m}\left(q, r\right)\right|-1, & f_{d, m}\left(q, r\right) \neq 0 \\ 0, & f_{d, m}\left(q, r\right)=0\end{cases} \tag{11}\end{align*}

推论 2.

对于两个给定点 q 和 r，{dist}_{B}^{2}(q, r) 的下界是每个维度下界之和。当 m\gt0，

\begin{align*}{dist}_{B}^{2}\left(q, r\right) & \geq \sum_{d=1}^{3}\left(f_{d, m}\left(q, r\right)^{2}-h_{d, m}\left(q, r\right)\right)\lt \lt 2\left(B-m\right) \\ & =\left(d i s t_{m}^{2}\left(q, r\right)-\sum_{d=1}^{3} h_{d, m}\left(q, r\right)\right)\lt \lt 2\left(B-m\right) \\ & =g_{m}^{2}\left(q, r\right) \tag{12}\end{align*}

脚注

8 位用于强度字段，另外保留 11 位。强度在欧氏距离计算中未被使用。
我们假设 HBM2 可用，因为该加速器正在集成到本来会有 HBM2 的 SoC 中。

参考文献

附加参考文献

C. Chen, G. Li, R. Xu, T. Chen, M. Wang, and L. Lin, “Clusternet: Deep hierarchical cluster network with rigorously rotation-invariant representation for point cloud analysis,” in Proceedings of the IEEE/CVF conference on computer vision and pattern recognition (CVPR), 2019, pp. 4994–5002. IEEE Google Scholar ↩︎
P. J. Besl and N. D. McKay, “Method for registration of 3-d shapes,” in Sensor fusion IV: control paradigms and data structures, vol. 1611, 1992, pp. 586–606. IEEE Google Scholar ↩︎
H. Men, B. Gebre, and K. Pochiraju, “Color point cloud registration with 4d icp algorithm,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2011, pp. 1511–1516. IEEE Google Scholar ↩︎
Y. Feng, B. Tian, T. Xu, P. Whatmough, and Y. Zhu, “Mesorasi: Architecture support for point cloud analytics via delayed-aggregation,” in Proceedings of the 53rd Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2020, pp. 1037–1050. IEEE Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
S. Choi, Q.-Y. Zhou, and V. Koltun, “Robust reconstruction of indoor scenes,” in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015. IEEE Google Scholar ↩︎
A. 3D, “Artec 3d micro ii 3d scanner,” https://www.artec3d.com/portable-3d-scanners/artec-micro, 2023. Google Scholar ↩︎
N. Hajinazar, G. F. Oliveira, S. Gregorio, J. D. Ferreira, N. M. Ghiasi, M. Patel, M. Alser, S. Ghose, J. Gomez-Luna, and O. Mutlu, “Simdram: a framework for bit-serial simd processing using dram,” in Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOPS), 2021, pp. 329–345. DOI Google Scholar ↩︎
R. J. Barrientos, J. I. Gomez, C. Tenllado, M. P. Matias, and M. Marin, “knn query processing in metric spaces using gpus,” in Proceedings of the 17th European Conference on Parallel Processing (Euro-Par), 2011, pp. 380–392. DOI Google Scholar ↩︎
H. Men, B. Gebre, and K. Pochiraju, “Color point cloud registration with 4d icp algorithm,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2011, pp. 1511–1516. IEEE Google Scholar ↩︎
J. Behley, M. Garbade, A. Milioto, J. Quenzel, S. Behnke, C. Stachniss, and J. Gall, “Semantickitti: A dataset for semantic scene understanding of lidar sequences,” in Proceedings of the IEEE/CVF international conference on computer vision (ICCV), 2019, pp. 9297–9307. IEEE Google Scholar ↩︎
A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for autonomous driving? the kitti vision benchmark suite,” in Proceedings of Conference on Computer Vision and Pattern Recognition (CVPR), 2012. IEEE Google Scholar ↩︎
A. 3D, “Artec 3d micro ii 3d scanner,” https://www.artec3d.com/portable-3d-scanners/artec-micro, 2023. Google Scholar ↩︎
J. Albericio, A. Delms, P. Judd, S. Sharify, G. O’Leary, R. Genov, and A. Moshovos, “Bit-pragmatic deep neural network computing,” in Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2017, pp. 382–394. IEEE Google Scholar ↩︎
A. Delmas Lascorz, P. Judd, D. M. Stuart, Z. Poulos, M. Mahmoud, S. Sharify, M. Nikolic, K. Siu, and A. Moshovos, “Bit-tactical: A software/hardware approach to exploiting value and bit sparsity in neural networks,” in Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2019, pp. 749–763. DOI Google Scholar ↩︎
P. Judd, J. Albericio, T. Hetherington, T. M. Aamodt, and A. Moshovos, “Stripes: Bit-serial deep neural network computing,” in Proceedings of the 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2016, pp. 1–12. IEEE Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
P. H. Becker, J. M. Arnau, and A. Gonzlez, “Demystifying power and performance bottlenecks in autonomous driving systems,” in Proceedings of IEEE International Symposium on Workload Characterization (IISWC), 2020, pp. 205–215. IEEE Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for autonomous driving? the kitti vision benchmark suite,” in Proceedings of Conference on Computer Vision and Pattern Recognition (CVPR), 2012. IEEE Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
Y. Feng, G. Hammonds, Y. Gan, and Y. Zhu, “Crescent: taming memory irregularities for accelerating deep point cloud analytics,” in Proceedings of the 49th Annual International Symposium on Computer Architecture (ISCA), 2022, pp. 962–977. DOI Google Scholar ↩︎
Y. Lin, Z. Zhang, H. Tang, H. Wang, and S. Han, “Pointacc: Efficient point cloud accelerator,” in Proceedings of the 54th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2021, pp. 449–461. DOI Google Scholar ↩︎
Y. Feng, G. Hammonds, Y. Gan, and Y. Zhu, “Crescent: taming memory irregularities for accelerating deep point cloud analytics,” in Proceedings of the 49th Annual International Symposium on Computer Architecture (ISCA), 2022, pp. 962–977. DOI Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
LSLiDAR, “Lslidar ms03 user manual v1.0.1,” https://www.manualslibcom/manual/2843960/Lslidar-Ms03.html, 2023. Google Scholar ↩︎
A. 3D, “Artec 3d micro ii 3d scanner,” https://www.artec3d.com/portable-3d-scanners/artec-micro, 2023. Google Scholar ↩︎
S. Li and N. Amenta, “Brute-force k-nearest neighbors search on the gpu,” in Proceedings of the 8th Similarity Search and Applications (SISAP), 2015, pp. 259–270. DOI Google Scholar ↩︎
J. Elseberg, D. Borrmann, and A. Nchter, “One billion points in the cloud-an octree for efficient processing of 3 d laser scans,” ISPRS Journal of Photogrammetry and Remote Sensing, vol. 76, pp. 76–88, 2013. DOI Google Scholar ↩︎
P. H. E. Becker, J.-M. Arnau, and A. Gonzlez, “Kd bonsai: Isaextensions to compress kd trees for autonomous driving tasks,” in Proceedings of the 50th Annual International Symposium on Computer Architecture (ISCA), 2023, pp. 1–13. DOI Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
Y. Lin, Z. Zhang, H. Tang, H. Wang, and S. Han, “Pointacc: Efficient point cloud accelerator,” in Proceedings of the 54th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2021, pp. 449–461. DOI Google Scholar ↩︎
Y. Lin, Z. Zhang, H. Tang, H. Wang, and S. Han, “Pointacc: Efficient point cloud accelerator,” in Proceedings of the 54th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2021, pp. 449–461. DOI Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
Y. Feng, G. Hammonds, Y. Gan, and Y. Zhu, “Crescent: taming memory irregularities for accelerating deep point cloud analytics,” in Proceedings of the 49th Annual International Symposium on Computer Architecture (ISCA), 2022, pp. 962–977. DOI Google Scholar ↩︎
A. Gholami, S. Kim, Z. Dong, Z. Yao, M. W. Mahoney, and K. Keutzer, “A survey of quantization methods for efficient neural network inference,” in Low-Power Computer Vision, 2022, pp. 291–326. DOI Google Scholar ↩︎
J. Albericio, A. Delms, P. Judd, S. Sharify, G. O’Leary, R. Genov, and A. Moshovos, “Bit-pragmatic deep neural network computing,” in Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2017, pp. 382–394. IEEE Google Scholar ↩︎
A. Delmas Lascorz, P. Judd, D. M. Stuart, Z. Poulos, M. Mahmoud, S. Sharify, M. Nikolic, K. Siu, and A. Moshovos, “Bit-tactical: A software/hardware approach to exploiting value and bit sparsity in neural networks,” in Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2019, pp. 749–763. DOI Google Scholar ↩︎
X. Feng, C. Tang, Z. Zhang, W. Sun, and Y. Liu, “Semantic guided finegrained point cloud quantization framework for 3d object detection,” in Proceedings of the 28th Asia and South Pacific Design Automation Conference (ASP-DAC), 2023, pp. 390–395. DOI Google Scholar ↩︎
T. Ajayi, D. Blaauw, T. Chan, C. Cheng, V. Chhabria, D. Choo, M. Coltella, S. Dobre, R. Dreslinski, M. Fogaa et al., “Openroad: Toward a self-driving, open-source digital layout implementation tool chain,” Proc. GOMACTECH, pp. 1105–1110, 2019. Google Scholar ↩︎
T. Ajayi, D. Blaauw, T. Chan, C. Cheng, V. Chhabria, D. Choo, M. Coltella, S. Dobre, R. Dreslinski, M. Fogaa et al., “Openroad: Toward a self-driving, open-source digital layout implementation tool chain,” Proc. GOMACTECH, pp. 1105–1110, 2019. Google Scholar ↩︎
T. Ajayi, D. Blaauw, T. Chan, C. Cheng, V. Chhabria, D. Choo, M. Coltella, S. Dobre, R. Dreslinski, M. Fogaa et al., “Openroad: Toward a self-driving, open-source digital layout implementation tool chain,” Proc. GOMACTECH, pp. 1105–1110, 2019. Google Scholar ↩︎
Y. Lin, Z. Zhang, H. Tang, H. Wang, and S. Han, “Pointacc: Efficient point cloud accelerator,” in Proceedings of the 54th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2021, pp. 449–461. DOI Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
P. H. E. Becker, J.-M. Arnau, and A. Gonzlez, “Kd bonsai: Isaextensions to compress kd trees for autonomous driving tasks,” in Proceedings of the 50th Annual International Symposium on Computer Architecture (ISCA), 2023, pp. 1–13. DOI Google Scholar ↩︎
M. Han, L. Wang, L. Xiao, H. Zhang, C. Zhang, X. Xu, and J. Zhu, “Quickfps: Architecture and algorithm co-design for farthest point sampling in large-scale point clouds,” IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 2023. IEEE Google Scholar ↩︎
T. Ajayi, D. Blaauw, T. Chan, C. Cheng, V. Chhabria, D. Choo, M. Coltella, S. Dobre, R. Dreslinski, M. Fogaa et al., “Openroad: Toward a self-driving, open-source digital layout implementation tool chain,” Proc. GOMACTECH, pp. 1105–1110, 2019. Google Scholar ↩︎
A. Geiger, P. Lenz, and R. Urtasun, “Are we ready for autonomous driving? the kitti vision benchmark suite,” in Proceedings of Conference on Computer Vision and Pattern Recognition (CVPR), 2012. IEEE Google Scholar ↩︎
S. Choi, Q.-Y. Zhou, and V. Koltun, “Robust reconstruction of indoor scenes,” in Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015. IEEE Google Scholar ↩︎
J. Behley, M. Garbade, A. Milioto, J. Quenzel, S. Behnke, C. Stachniss, and J. Gall, “Semantickitti: A dataset for semantic scene understanding of lidar sequences,” in Proceedings of the IEEE/CVF international conference on computer vision (ICCV), 2019, pp. 9297–9307. IEEE Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
Inc. Micron Technology, “8Gb: x4, x8, x16 DDR4 SDRAM,” https://www.micron.com/products/dram/ddr4-sdram/part-catalog/mt40a512m16ly-062e, 2021. Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
M. R. Guthaus, J. E. Stine, S. Ataei, B. Chen, B. Wu, and M. Sarwar, “Openram: An open-source memory compiler,” in Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD), 2016, pp. 1–6. IEEE Google Scholar ↩︎
S. Li, Z. Yang, D. Reddy, A. Srivastava, and B. Jacob, “Dramsim3: A cycle-accurate, thermal-capable dram simulator,” IEEE Computer Architecture Letters, vol. 19, no. 2, pp. 106–109, 2020. IEEE Google Scholar ↩︎
T. Ajayi, D. Blaauw, T. Chan, C. Cheng, V. Chhabria, D. Choo, M. Coltella, S. Dobre, R. Dreslinski, M. Fogaa et al., “Openroad: Toward a self-driving, open-source digital layout implementation tool chain,” Proc. GOMACTECH, pp. 1105–1110, 2019. Google Scholar ↩︎
P. H. E. Becker, J.-M. Arnau, and A. Gonzlez, “Kd bonsai: Isaextensions to compress kd trees for autonomous driving tasks,” in Proceedings of the 50th Annual International Symposium on Computer Architecture (ISCA), 2023, pp. 1–13. DOI Google Scholar ↩︎
R. J. Barrientos, J. I. Gomez, C. Tenllado, M. P. Matias, and M. Marin, “knn query processing in metric spaces using gpus,” in Proceedings of the 17th European Conference on Parallel Processing (Euro-Par), 2011, pp. 380–392. DOI Google Scholar ↩︎
J. Elseberg, D. Borrmann, and A. Nchter, “One billion points in the cloud-an octree for efficient processing of 3 d laser scans,” ISPRS Journal of Photogrammetry and Remote Sensing, vol. 76, pp. 76–88, 2013. DOI Google Scholar ↩︎
S. Li and N. Amenta, “Brute-force k-nearest neighbors search on the gpu,” in Proceedings of the 8th Similarity Search and Applications (SISAP), 2015, pp. 259–270. DOI Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
Y. Feng, G. Hammonds, Y. Gan, and Y. Zhu, “Crescent: taming memory irregularities for accelerating deep point cloud analytics,” in Proceedings of the 49th Annual International Symposium on Computer Architecture (ISCA), 2022, pp. 962–977. DOI Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
F. Chen, R. Ying, J. Xue, F. Wen, and P. Liu, “Parallelnn: A parallel octree-based nearest neighbor search accelerator for 3d point clouds,” in Proceedings of IEEE International Symposium on High-Performance Computer Architecture (HPCA), 2023, pp. 403–414. IEEE Google Scholar ↩︎
K. Liu, A. Lu, K. Samtani, Z. Fang, and L. Guo, “Chip-knnv2: A configurable and high-performance k-nearest neighbors accelerator on hbm-based fpgas,” ACM Transactions on Reconfigurable Technology and Systems, 2023. DOI Google Scholar ↩︎
H. Kaul, M. A. Anders, S. K. Mathew, G. Chen, S. K. Satpathy, S. K. Hsu, A. Agarwal, and R. K. Krishnamurthy, “14.4 a 21.5 m-queryvectors/s 3.37 mathrmnj / vector reconfigurable k-nearest-neighbor accelerator with adaptive precision in 14 nm tri-gate cmos,” in Proceedings of the IEEE International Solid-State Circuits Conference (ISSCC), 2016, pp. 260–261. IEEE Google Scholar ↩︎
P. H. E. Becker, J.-M. Arnau, and A. Gonzlez, “Kd bonsai: Isaextensions to compress kd trees for autonomous driving tasks,” in Proceedings of the 50th Annual International Symposium on Computer Architecture (ISCA), 2023, pp. 1–13. DOI Google Scholar ↩︎
Y. Lin, Z. Zhang, H. Tang, H. Wang, and S. Han, “Pointacc: Efficient point cloud accelerator,” in Proceedings of the 54th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2021, pp. 449–461. DOI Google Scholar ↩︎
J. Albericio, A. Delms, P. Judd, S. Sharify, G. O’Leary, R. Genov, and A. Moshovos, “Bit-pragmatic deep neural network computing,” in Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2017, pp. 382–394. IEEE Google Scholar ↩︎
A. Delmas Lascorz, P. Judd, D. M. Stuart, Z. Poulos, M. Mahmoud, S. Sharify, M. Nikolic, K. Siu, and A. Moshovos, “Bit-tactical: A software/hardware approach to exploiting value and bit sparsity in neural networks,” in Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2019, pp. 749–763. DOI Google Scholar ↩︎
P. Judd, J. Albericio, T. Hetherington, T. M. Aamodt, and A. Moshovos, “Stripes: Bit-serial deep neural network computing,” in Proceedings of the 49th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), 2016, pp. 1–12. IEEE Google Scholar ↩︎
N. Hajinazar, G. F. Oliveira, S. Gregorio, J. D. Ferreira, N. M. Ghiasi, M. Patel, M. Alser, S. Ghose, J. Gomez-Luna, and O. Mutlu, “Simdram: a framework for bit-serial simd processing using dram,” in Proceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOPS), 2021, pp. 329–345. DOI Google Scholar ↩︎