HopScotch：一种整体性的方法，用于在NPU上实现数据布局感知的映射，以提升高性能DNN推理的效率

《ACM Transactions on Architecture and Code Optimization》：HopScotch: A Holistic Approach to Data Layout-Aware Mapping on NPUs for High-Performance DNN Inference

针对NPUs中DNN层异质性导致的布局重排开销问题，提出HopScotch方法，结合微架构优化（三输入多路复用器、VLIW向量处理器）、混合搜索算法（Top-k策略）和成本建模，显著降低重排开销，实验表明在多个模型上实现1.13至2.62倍加速。

　　现代深度神经网络（DNNs）在多个领域得到了广泛应用，其规模迅速扩展，常常包含数百层，每层具有不同的类型和配置。为了加速DNN的执行，专门的硬件解决方案，即神经处理单元（NPUs），已被开发出来。然而，这种DNN模型的层异构性可能会导致在NPUs上的性能下降。例如，虽然某一层的执行或数据流通常与特定的数据访问顺序相关联，但芯片内存中的数据布局可能与之不匹配，从而引入布局重排的空周期。鉴于DNNs中的大量异构层，这种布局重排的开销为实现高效的端到端DNN推理提出了新的挑战。

为了解决这一问题，本文介绍了一种全面的数据布局感知映射方法，称为HopScotch，用于将DNN映射到NPUs上。首先，HopScotch采用了一种三输入多路复用器（multiplexer）作为芯片内存与OS数据流的 systolic array 之间的路由互连，同时配备了一种可编程的矢量处理器（vector processor）以在运行时管理任意的数据布局重排。此外，它还引入了一种定制的数据布局，以适应各种卷积配置。其次，HopScotch提出了一个新颖的布局映射求解器，该求解器采用基于束搜索（beam search）的top-k选择策略，从而在编译时高效地探索庞大的布局映射空间。第三，该布局映射求解器被集成到HopScotch映射框架（HMF）中，用于探索布局映射空间并评估最终的性能。实验结果表明，HopScotch可以将布局重排成本降低高达98.2%和90.3%，从而在端到端延迟方面实现2.62倍和1.64倍的速度提升。

DNNs的广泛应用表明，其在图像分类、目标检测和图像分割等任务中表现出色，因此被广泛应用于自动驾驶、监控和机器人等应用。随着计算能力和工作负载的扩展，DNNs从只有少数卷积层的模型（如AlexNet、VGG和MobileNet）发展到具有数百层的深度模型，如RepVGG、MNasNet、EfficientNet和ConvNeXt。这些新兴模型通常由复杂的网络架构搜索产生，导致包含多种类型的层。例如，除了传统网络中的3×3卷积和跳接层，MNasNet和EfficientNet等模型采用了深度可分离卷积（depthwise separable convolution）来减少参数数量，同时保持精度。此外，这些模型还引入了倒置瓶颈（inverted bottlenecks）和挤压-激励模块（squeeze-and-excitation modules），这些结构会改变层的配置，如张量形状和滤波器大小。ConvNeXt则结合了更大的卷积核和非卷积层，以提高准确性和效率。这种趋势对现代计算系统提出了更高的要求，以有效应对扩展DNN模型中的层异构性。

许多研究致力于设计高性能的DNN加速器，包括专用架构和通用架构。早期的加速器通常针对特定的DNN进行定制，使用预定义的数据流或计算模式。然而，随着新模型的不断涌现，商业级的DNN加速器，通常被称为神经处理单元（NPUs），已发展为统一架构，以支持广泛的网络。特别是，基于systolic array的架构在商业NPUs中变得流行，因为Google的Tensor Processing Unit（TPU）的引入。Systolic array非常适合执行卷积操作，通过多个处理元素（PEs）的并行处理和PE之间的本地数据重用来实现。此外，这些架构通常配备可编程的矢量处理器，以处理不执行在systolic array中的各种操作。

为了系统地探索DNN在NPUs上的高效映射，已开发了多种DNN框架。其中，XLA旨在优化对数据流敏感的层（如卷积层）的最佳布局，并将这些布局传播到相邻层，形成分区。然而，这种方法在分区边界切换时可能引入布局重排开销。另一个研究，GCD2，将整个DNN图划分为子图，并在每个子图中执行暴力搜索以找到局部最优布局。然而，由于每层可能有大量布局候选，GCD2会将模型划分为更小的子图以减少搜索时间。这增加了分区的数量，从而在分区边界引入了显著的布局重排开销。

本文提出的HopScotch方法针对上述挑战，提供了一种全面的数据布局感知映射方案。在微架构方面，HopScotch引入了基于三输入多路复用器的路由互连，以支持卷积操作，并结合了可编程的矢量处理器，以在运行时处理任意的数据布局重排。在搜索算法方面，HopScotch采用了基于top-k选择策略的束搜索方法，以在编译时高效地探索庞大的布局映射空间。在成本建模方面，HopScotch提供了一个矢量处理器的分析模型，以快速而精确地估计性能，包括布局重排成本。通过将这些组件集成到HMF中，HopScotch能够系统地探索布局映射空间并评估端到端DNN性能。

HopScotch的主要贡献包括：（1）提出了一种支持多种卷积配置的微架构，结合了三输入多路复用器和可编程矢量处理器；（2）引入了基于束搜索的top-k选择策略，以在编译时高效地探索布局映射空间；（3）提供了一个精确的矢量处理器分析模型，以快速评估性能，包括布局重排成本。实验结果表明，HopScotch在多个DNN模型上显著降低了布局重排成本，并在端到端延迟方面实现了显著的速度提升。

在微架构设计中，HopScotch采用了三输入多路复用器作为芯片内存与OS数据流systolic array之间的路由互连。这使得每个PE可以访问多个缓冲区通道，从而支持各种卷积配置。通过合理设计多路复用器，HopScotch能够在不同卷积操作之间实现高效的布局重排。此外，HopScotch还引入了一种定制的数据布局，以适应不同卷积配置，同时减少硬件成本。这种数据布局基于循环数据布局，并通过两个关键原则进行设计：内维固定展开和外维折叠。内维固定展开确保了多个通道中输入片段的相对位置保持一致，而外维折叠则允许外维在通道方向上按步长扩展，从而支持各种卷积配置。

在布局重排方面，HopScotch利用矢量处理器来实现不同数据布局之间的灵活重排。布局重排被分解为两个嵌套循环，利用芯片缓冲区的入口级访问特性。外层循环遍历数据所在的入口，而内层循环则在每个入口内重新排列元素。在入口内，每个元素根据其源布局和目标布局之间的差异进行移动。通过利用矢量处理器的SIMD特性，入口内具有相同移动量的元素可以并行重排。

在搜索算法方面，HopScotch采用了基于束搜索的top-k选择策略。这种策略类似于自然语言处理（NLP）中的序列生成，其中早期的决策会显著影响后续的选择。在布局映射过程中，每个节点的映射成本不仅取决于其计算成本，还取决于与前驱节点的布局重排成本。HopScotch通过维护当前迭代中的top-k解决方案，实现了高效的布局映射探索。这种策略能够有效减少分区边界处的布局重排成本，同时保持每个分区内的局部最优布局。

在系统集成和评估方面，HopScotch将上述组件集成到一个系统框架中，以评估DNN在NPUs上的执行性能。通过分析不同布局映射方法在多个DNN模型上的性能，HopScotch展示了其在减少布局重排成本和提升端到端推理效率方面的优势。实验结果表明，HopScotch在多个模型上显著降低了布局重排成本，并实现了显著的速度提升。

HopScotch的微架构设计通过三输入多路复用器和可编程矢量处理器的结合，实现了对各种卷积配置的支持。矢量处理器能够灵活地处理不同数据布局之间的重排，而多路复用器则确保了数据在缓冲区中的高效传输。这种设计不仅减少了硬件复杂度，还提高了系统的灵活性和性能。

在搜索算法中，HopScotch采用了一种基于束搜索的top-k选择策略，以高效地探索庞大的布局映射空间。通过维护当前迭代中的top-k解决方案，HopScotch能够在保持性能的同时，减少计算开销。这种策略特别适用于处理DNN中的大规模布局映射问题，因为它能够有效平衡搜索空间的广度和深度。

在成本建模方面，HopScotch提供了一个矢量处理器的分析模型，以快速而精确地估计性能，包括布局重排成本。该模型通过模拟矢量处理器的执行过程，能够准确预测布局重排对整体性能的影响。实验结果表明，HopScotch的分析模型与周期精确的模拟器之间的误差率低于10%，验证了其准确性。

通过将这些组件集成到HMF中，HopScotch能够系统地探索布局映射空间，并评估不同映射策略对DNN推理性能的影响。实验结果表明，HopScotch在多个DNN模型上显著降低了布局重排成本，并在端到端延迟方面实现了显著的速度提升。这种高效的方法不仅适用于当前的NPUs，还具有良好的扩展性，能够适应未来的DNN架构和计算需求。

HopScotch的提出为DNN在NPUs上的高效执行提供了新的思路。通过结合微架构设计、搜索算法和成本建模，HopScotch能够在复杂的数据流和层配置中找到最优的布局映射方案。这种方法不仅提高了DNN的执行效率，还减少了硬件资源的消耗，为未来的神经网络加速器设计提供了重要的参考。