一种考虑数据稀疏性的自主路径规划加速器，采用硬件/软件协同设计及多级数据流优化技术

《ACM Transactions on Architecture and Code Optimization》：A Sparsity-Aware Autonomous Path Planning Accelerator with HW/SW Co-Design and Multi-Level Dataflow Optimization

FPGA平台上的路径规划加速框架通过ADMM与PCG优化，结合稀疏矩阵专用存储和运算单元设计，以及多级数据流优化策略，显著提升QP求解性能，平均速度达现有FPGA方案1.48倍，CPU方案2.89倍，并优化能效比。

　　在自动驾驶领域，路径规划是一项至关重要的任务，其核心目标是基于输入的感知和定位信息，生成一条平滑、无碰撞且可执行的路径。由于路径规划既要求高实时性又需要大量计算资源，这对资源受限的自动驾驶硬件提出了严峻的挑战。本文提出了一种面向FPGA平台的端到端路径规划加速框架，该框架专注于加速二次规划（QP）求解，因为QP求解是基于优化的路径规划方法的核心，且计算量最大。通过将问题结构化，我们设计了一种具有自适应稀疏特性的硬件友好的交替方向乘子（ADMM）方法，同时采用高度可并行的预条件共轭梯度（PCG）方法来求解相关的线性系统。我们深入分析了QP中矩阵运算的稀疏模式，并设计了定制化的存储方案以及高效的稀疏矩阵乘法和稀疏矩阵-向量乘法单元，显著减少了数据存储和计算的资源消耗，同时大大提高了矩阵运算的速度。此外，我们提出了一种多级数据流优化策略。在单个运算器内部，我们通过并行化和流水线技术实现了加速；在不同运算器之间，我们分析运算间的数据依赖性，以实现细粒度的流水线优化；在系统级别，我们将路径规划的不同阶段映射到CPU和FPGA，并通过流水线技术提高整体吞吐量。我们将在AMD ZCU102平台进行实现和验证，结果显示我们的设计在延迟和能效方面均优于现有方案，包括平均比最佳FPGA方案快1.48倍，比Intel i7-11800H CPU上的最佳QP求解器快2.89倍，比ARM Cortex-A57嵌入式CPU快5.62倍，比NVIDIA RTX 3090 GPU上的最佳GPU实现快1.56倍。此外，我们的设计还比现有最佳FPGA方案提升了2.05倍的吞吐量。

传统的路径规划计算方法面临着两个主要挑战：满足实时处理需求和处理复杂的、数据密集型计算。这些挑战突显了需要创新解决方案来实现速度与精度的平衡。为了解决这些需求，本文引入了一种基于FPGA的新型加速框架，以提升自动驾驶车辆的路径规划能力。

路径规划通常从给定的全局路径开始，该路径连接起点和终点，形成一个粗略的曲线，不考虑详细的运动学特性。随后，路径规划器会进行多次路径优化迭代，调整该路径以优化目标函数，同时满足所有约束条件。在这个过程中，路径会被平滑处理，并且所有的机械和运动学约束都会被考虑。图1展示了路径规划的一个示例。

商业路径规划解决方案的主要限制来自多个方面。首先，在算法层面，快速、容易计算的贪婪方法可能会牺牲规划质量。在路径规划质量和计算时间之间找到良好平衡是一个挑战。其次，在库和工具层面，当前解决方案通常依赖于通用的线性代数和优化库和工具，这些库和工具是为通用问题设计的。这些通用库调用忽略了领域特定（路径规划）的信息和启发式方法，因此无法充分利用领域特定的优化机会。第三，在硬件和系统层面，现有解决方案通常假设通用计算平台作为底层计算平台，并忽略了不同平台之间的差异和系统定制的机会。

本文提出的框架利用了任务和平台特定的信息，包括稀疏性、问题规模、数据类型和每个模块的计算强度等，以设计高效的稀疏感知存储方案和计算单元。我们还提出了一种细粒度的多级数据流优化策略，以最大化端到端性能。在运算器之间，我们分析不同运算器之间的数据依赖性，以实现细粒度的流水线优化。在系统层面，我们将路径规划的不同独立阶段映射到CPU和FPGA上的多个线程，并对这些线程进行流水线处理，以提高端到端吞吐量。

为了实现这一目标，我们采用了ADMM算法，这是一种适合处理复杂约束问题的优化方法。在应用ADMM算法之前，我们对涉及的矩阵（P和A）进行了预处理，以增强数值稳定性。ADMM算法依赖于迭代求解线性方程组，但为了避免使用传统的矩阵分解方法，我们选择了PCG方法来解决这些线性方程组。PCG方法特别适合处理大规模、稀疏的线性系统，且其主要操作包括矩阵-向量乘法、向量标量乘法（AXPY）和点积，这些操作在FPGA的并行计算能力下可以被高效并行化。

我们对矩阵P和A的稀疏模式进行了深入分析，并基于这些模式设计了定制化的存储方案。通过将矩阵分解为多个块，并在这些块中采用特定的稀疏模式，我们能够显著减少存储和计算的资源消耗。此外，我们还设计了高效的稀疏矩阵-向量乘法（SpMV）单元，利用FPGA的并行计算能力，实现高效的计算。

在系统层面，我们通过多级数据流优化策略来提高路径规划的整体性能。在单个运算器内部，我们实现了并行化和流水线处理；在不同运算器之间，我们通过分析数据依赖性，实现了细粒度的流水线优化。同时，我们将路径规划的不同阶段映射到CPU和FPGA上，并通过流水线处理提高整体吞吐量。这种多级优化策略不仅减少了资源消耗，还提高了计算效率。

我们的实验结果显示，通过使用自适应稀疏存储方案和高效的SpMV单元，我们能够显著提高路径规划的计算效率。此外，通过采用PCG方法，我们能够在不牺牲精度的情况下，有效加速线性系统求解。我们还对算法参数进行了优化，以提高收敛速度，从而进一步减少计算时间。

为了验证我们的设计，我们使用了实际收集和模拟的数据集。结果表明，我们的框架在路径规划任务中取得了显著的性能提升。通过采用多级数据流优化策略，我们能够实现更高的计算吞吐量，同时保持较低的资源消耗。

总的来说，本文提出的框架在路径规划任务中实现了显著的性能提升。通过结合稀疏感知的硬件设计和多级数据流优化，我们的设计在延迟和能效方面均优于现有方案，同时在计算时间和资源消耗之间实现了良好的平衡。这为自动驾驶系统提供了一种高效且可靠的路径规划解决方案，有助于提高自动驾驶的安全性和实时性。