FlexNN_Efficient_and_Adaptive_DNN_Inference_on_Memory_Constrained_Edge_Devices
FlexNN: Efficient and Adaptive DNN Inference on Memory-Constrained Edge Devices
题目：FlexNN：基于内存约束边缘设备的高效自适应深度神经网络推理
出处：ACM MobiCom
时间：2024.11
作者：Xiangyu Li，Institute for AI Industry Research(AIR), Tsinghua University Beijing, China
摘要
由于深度神经网络（DNN）的普及以及对网络开销、数据隐私和推理延迟的考虑，近年来人们对将DNN部署到边缘设备越来越感兴趣。然而，有限的内存成为设备上DNN部署的主要瓶颈，因此减少DNN的内存占用至关重要。主流的模型定制解决方案需要大量的部署工作，并且可能导致严重的精度下降，并且现有的深度学习（DL）框架没有优先考虑内存。此外，由于层间内存占用不平衡、不可避免的内存管理开销和内存预算动态性等问题，近年来对内存管理方案的改进还不能直接应用。为了应对这些挑战，我们引入了FlexNN，这是一种高效且自适应的内存管理框架，用于在内存受限的设备上进行DNN推理。FlexNN使用切片-加载-计算联合规划方法，以实现最佳的内存利用率和最小的内存管理开销。我们在NCNN的基础上实现了FlexNN，并在各种设备上使用通用模型架构进行了全面的评估。结果表明，我们的方法能够适应不同的内存约束，并具有最佳的延迟-内存权衡。例如，与智能手机上的原始NCNN相比，FlexNN可以减少93.81%的内存消耗，而延迟仅增加3.64%。
结论
在本文中，我们设计并实现了FlexNN，这是一种高效且自适应的内存管理框架，用于内存受限的设备上DNN推理。FlexNN通过切片-加载-计算联合规划方法实现了最佳内存利用率和最小内存管理开销。我们的评估结果表明，FlexNN能够适应不同的内存预算，具有最佳的延迟-内存权衡和最小的适应开销。
研究背景
为什么要从内存的角度考虑DNN推理？
与基于强大GPU集群的云部署DNN模型不同，设备上DNN部署的主要瓶颈是内存。因此，减少DNN推理的内存占用至关重要，这直接决定了一个模型是否可以在许多移动/边缘应用中使用。现有移动深度学习框架不把内存作为优先考虑的问题。在过去的十年中，移动/边缘设备上内存容量的增长明显落后于计算能力的进步，而DNN模型的计算和内存需求通常随着模型能力线性增加。
研究人员提出了各种技术来增强内存管理方案。典型的做法是将非紧急数据交换到存储中，以减少内存占用。然而，将这些技术直接应用于设备上推断面临着几个挑战，如下所述。A.DNN跨层内存占用不平衡。B.不可避免的内存管理开销。（一些额外的操作）C.内存预算动态（使用按需内存管理策略可能会导致可用内存的碎片化和利用率不足，而动态调整静态内存管理策略并进行提前规划可能会导致巨大的适应成本）。
为了弥补边缘设备有限的内存预算与深度神经网络模型不断增长的内存需求之间的差距，需要设计一个以内存优化为第一优先级的推理框架。
当前DNN推理存在什么内存问题？
对DNN推理进行了深入的内存分析，有以下结果：
A.不平衡的分层内存分布。例如，在ResNet-152中，79.6%的层消耗不超过5MB的内存，99.4%的层消耗不超过20MB的内存，而只有0.6%的层消耗超过70MB的内存。
B.内核选择中的延迟-内存权衡。“核”指的是DNN中一个层的不同实现。当推断同一层时，具有较低延迟的内核倾向于消耗更多内存。
C.不同层和内核之间的内存瓶颈不同。层的内存占用由三个主要部分组成：激活（即层的输入和输出）、权重（即模型参数）和中间体（即计算层输出时的临时结果）。具体来说，权重和平坦化的输入（flattened input）是两个主要的层内内存瓶颈。
优化DNN推理的可行性
DNN推理工作负载的独特特性为内存交换提供了更好的设计空间。首先，与传统软件相比，DNN推理的控制流程具有确定性，可以通过提前规划来减少执行时间管理开销。其次，DNN推理过程中张量的大小和生命周期表现出一定的模式，这为优化内存布局提供了机会。
研究目的
对于DNN部署到内存受限的边缘场景，存在不同层内存占用不平衡的问题。通过切片等技术，来减少DNN的内存开销，完成DNN在内存受限设备上的部署。
论文贡献
FlexNN，这是一种高效且自适应的设备上深度神经网络推理框架，适用于内存受限的场景。FlexNN通过切片-加载-计算联合规划方法解决了上述挑战。关键见解包括：(1)通过模型执行计划和内存管理计划的细粒度协同设计实现最佳内存利用率；(2)通过密集的离线准备来抑制运行时内存管理开销。
我们总结了我们的主要贡献如下：
(1)我们设计了FlexNN，一个高效和自适应的内存管理框架，用于内存受限的设备DNN推理。
(2)我们提出了一种切片-加载-计算联合规划方法，可以在最小的运行时延迟增加的情况下减少DNN推理的内存消耗。
(3)提出了一种预负载感知的内存规划方案，可以有效减少推理过程中的内存碎片和I/O等待时间。
(4)我们在NCNN之上实现了FlexNN，并在各种边缘设备和DNN模型上进行了广泛的实验。结果表明，FlexNN能够适应不同的内存预算，具有最佳的延迟-内存权衡和最小的开销。
相关工作
系统支持内存约束推理。
内存约束推理的模型定制。
论文方法
如图所示，FlexNN包括两个阶段：离线规划阶段，根据内存预算和给定模型进行切片-加载-计算联合规划；在线执行阶段，根据离线生成的计划进行模型推理。
离线规划阶段包括两个主要模块：瓶颈感知层切片和预负载感知内存规划。在分析了面向张量的内存大小和生命周期之后，进行层切片以减少面向层的内存占用。除了权值切片和输入切片这两种切片方法外，层切片模块还包括核选择和权值预变换，以减少运行时开销。在层切片之后进行预加载感知内存规划，提供详细的内存规划。它使用轻量级算法，减少了运行时的片段和I/O等待时间，并避免了大量的适应开销。当内存预算足够大时，FlexNN还会在内存中固定一部分模型权重，以进一步降低I/O成本。
在在线执行阶段，FlexNN利用离线生成的计划和预转换的权值高效地进行模型推理。具体来说，FlexNN使用基于依赖的同步方案和基于类型的分配器来确保运行时并行执行的正确性。虽然在初始化时需要完整的规划，但在随后的适应中通常会跳过层切片部分，以避免开销。当内存预算发生变化时，FlexNN首先检查先前的切片模型是否满足新的内存预算。如果是这样，FlexNN将绕过层切片，只进行内存规划。否则，层切片仍然需要满足新的内存预算。
瓶颈感知层切片
瓶颈层切片的目标是通过细粒度分区减少每一层的内存消耗，从而降低峰值内存消耗。并且在考虑运行时延迟的情况下执行逐层峰值内存减少。它涉及3个步骤：(1)选择最合适的内核实现的内核选择，(2)基于所选内核执行分区的权重/输入切片，以及(3)避免运行时处理开销的权重预转换。
因为扁平的输入和权重是分层内存占用的两个主要瓶颈。为了解决层和内核的不同内存瓶颈，我们引入了两种具有不同延迟-内存权衡的层切片方法：权重切片和输入切片：
权重切片将层权重划分为几个片，每次加载一个片以减少内存占用。如图，FC权重按行划分，而输入保持不变。切片权重被加载并与输入切片相乘，得到输后合并在一起。通过将计算图中的一层划分为几个子层来实现权值切片，每个子层携带一个权值切片。并且权重切片的片数应该最小化，来调度开销。
输入切片对平坦的输入进行分区，并且每次在内存中保留一个切片以减少内存占用。如图，输入通过平坦的通道进行分割，而不改变权重。将输入平面化并与权重切片相乘得到部分输出，合并得到最终输出。与权重切片不同，输入切片中的切片数应在平台相关阈值内最大化，因为输入切片是生成的一部分而不是与磁盘交换来实现的，没有额外的I/O调度开销（延迟），这对片的最大数量施加了一个平台相关的约束。
这两种方法之间的选择取决于目标层的瓶颈。权重切片更适合权重主导层，如FC和Winograd Conv，而输入切片更适合中间主导层，如Im2col+GeMM Conv。
内核选择是在实际分区过程之前进行的，因为切片方法的选择取决于所选的内核。由于在同一层的内核选择中存在延迟-内存权衡，因此具有最佳延迟的内核可能无法满足内存约束。因此，FlexNN在切片后首先计算节省延迟的内核的预期内存占用，如果节省延迟的内核不能满足内存约束，则切换到内存高效的内核。
在核选择和输入/权值切片之后进行权值预变换，在执行前对特定权值进行变换。转换不仅包括重塑或重新格式化，还包括像Winograd Conv这样的内核的矩阵乘法，这会导致不可忽略的开销。预转换允许FlexNN在运行时直接加载转换后的权重，从而避免了运行时处理开销。
预加载感知内存规划
由于缺乏全局内存信息，传统DL框架中的动态（如按需）内存管理策略可能会受到碎片增加的影响，而现有作品中的静态内存管理策略没有考虑预加载，导致次优计划。为了解决这两个问题，FlexNN采用静态内存管理和预负载感知的内存规划，从而减少了碎片和I/O等待时间。我们将首先制定预负载感知的内存规划问题，然后介绍我们的轻量级规划算法。
3.3.1问题表述。存储器布局规划通常被表述为具有固定时间坐标的2D Bin Packing （2DBP）问题。在这个图中，每个张量被抽象为内存地址（y轴）和时间（x轴）的二维平面上的一个矩形（张量块）。张量块的值域范围表示张量的生命周期，值域范围表示其占用的内存空间。目标是为已知生命周期和内存大小的给定张量集找到最优布局。
我们的预负载感知内存规划问题也可以表述为2DBP问题的一个变体。主要的不同之处在于，在上述公式中，所有张量都有已知的生命周期，因此唯一的目标是确定它们的内存地址。然而，在我们的问题中，权重的分配地址和分配时间（即开始预加载的逻辑时间）都需要由规划结果确定。
给定：(1)具有已知属性的𝑛张量列表：未预加载的分配时间、去分配时间，内存大小和内存类型，其中包括权值，激活值和中间体。具体来说，激活指的是所有层的输入和输出，中间体指的是各个层内的计算中间体，这与激活不同。我们通过将层划分为子层来实现权值切片，我们将每个子层视为内存规划中的单个层，因此子层具有不同的层id。(2)内存预算𝑀max
目的：找到一个最优的内存计划，使推理延迟最小化，同时满足约束。该计划表示为时间-地址对的列表Ω ={⟨𝑡𝑚𝑒，𝑎𝑑𝑑𝑟⟩}，其中𝑡𝑚𝑒是张量的预加载分配的时间，𝑎𝑑𝑑𝑟是分配的内存地址。
约束：(1)生命周期约束：对于所有权重张量（允许预加载），1≤𝑡i𝑚𝑒i≤si，对于所有其他类型的张量，𝑡i𝑚𝑒i=𝑠i。
(2)内存使用约束:为所有时间𝜏𝑙从𝜏1𝜏𝐿,𝐿时间步骤的数目,也就是说,层数, Σ𝑡𝑖𝑚𝑒𝑖≤𝜏𝑙≤𝑒𝑖 mi<𝑀𝑚𝑎𝑥。
(3)内存地址约束:0≤𝑎𝑑𝑑𝑟𝑖≤𝑀𝑚𝑎𝑥−𝑚𝑖,。
(4)内存重叠约束:要么(𝑡𝑖𝑚𝑒𝑖≥𝑒𝑗)∨(𝑡𝑖𝑚𝑒𝑗≥𝑒𝑖)(生命周期重叠)或(𝑎𝑑𝑑𝑟𝑖+𝑚𝑖≤𝑎𝑑𝑑𝑟𝑗)∨(𝑎𝑑𝑑𝑟𝑗+𝑚𝑗≤𝑎𝑑𝑑𝑟𝑖)(内存地址不重叠的)。
3.3.2规划算法。我们采用轻量级算法1，它利用DNN推理的内存访问模式，以最小化内存碎片和I/O等待时间。该算法将统一缓冲区中的内存规划分解为基于不同张量类型（权重、激活和中间）的几个步骤。如图8所示，该算法涉及以下关键步骤：
计划激活。FlexNN优先规划激活，因为它们的生命周期很长。激活比其他类型的张量具有更长的生命周期，因为它们通常作为一个层的输出和一个或多个层的输入。例如，在图7中，层1的输出是层2的输入，标记为“1,2”。如图7所示，激活优先规划首先将所有激活放置在内存缓冲区的两端，从而在中间保持一个连续的内存块，从而有效地避免了碎片化。
使用预加载计划权重（按层划分）。对于每一层，FlexNN在中间体之前规划权重。它贪婪地搜索可用内存，使权重分配时间最小化，从而尽可能减少I/O等待时间。
计划中间层（按层划分）。对于每一层，在权值布局确定后，FlexNN贪婪地用中间值填充剩余的内存。
重新规划权重和中间体，不需要预加载（分层）。贪心权值预加载策略也可能产生碎片，导致中间规划失败。因此，对于每一层，当预加载感知规划失败时，FlexNN将在没有预加载权重的情况下重新规划该层的权重和中间体。
在线执行设计
在线执行阶段的目的是在正确执行离线规划阶段确定的计划的同时，进行实际的模型推理。它主要需要解决计划结果和实际执行之间的两个差距，如下所述。
张量规划和分层执行之间的差距。内存计划确定张量之间的细粒度依赖关系，但运行时进行相对粗粒度的分层推理。由于一个层的执行涉及多个具有不同生命周期的张量，如果层的加载和计算顺序没有仔细控制，可能会出现张量内存冲突。
逻辑时间和实际执行时间之间的差距。该计划仅确定每个张量分配和释放内存的逻辑时间，但实际时间未知。这种不确定性可能改变张量的实际分配顺序，从而导致错误的分配结果。因此，引入了一种基于依赖的同步方案来调度层的加载和计算，以及一个基于类型的静态分配器来确保分配的正确性。
基于同步。FlexNN捕获层之间的内存依赖关系，将张量式内存计划转换为层式执行计划。具体来说，我们将一个层的执行分为加载任务和计算任务，然后通过层依赖关系来管理任务的执行顺序。
一个层的执行通常包括三个步骤：权重加载、准备和计算。由于FlexNN在线下规划阶段进行预改造，可以跳过准备步骤。我们进一步将层的权重加载和计算过程抽象为只进行权重加载的“加载”任务和执行所有其他计算的“计算”任务。计算线程和加载线程都伴随着一个任务队列，即加载任务队列和计算任务队列，它们贪婪地获取可用的任务。计算和加载线程通过任务队列管理同步，以满足层依赖关系。
具体来说，在任务级别有两种类型的依赖关系。我们将层的加载和计算任务分别表示为“𝑙𝑜𝑎𝑑（离别离别）”和“𝑐𝑜𝑚𝑝（离别离别）”，用>和<表示任务之间的依赖关系，例如𝑙𝑜𝑎𝑑（离别离别）<𝑐𝑜𝑚𝑝（离别离别）表示第一层的计算依赖于第一层的加载。(1)计算前的加载，表示为𝑙𝑜𝑎𝑑（）<𝑐𝑜𝑚𝑝（）：层的计算依赖于层的加载。(2)加载前的计算，记为𝑐𝑜𝑚𝑝（）<𝑙𝑜𝑎𝑑（𝑗）：层𝑗的加载依赖于层𝑗的计算，如果它们有内存地址的交集。依赖关系(1)自然适用于所有层，而依赖关系(2)可以通过简单的后处理从内存规划结果中解决。图9展示了我们的同步方案如何通过层依赖确保执行顺序的示例。
基于类型的静态分配。在运行时确保正确的内存分配结果的关键是定义分配的顺序，这在多线程执行中可能具有挑战性。幸运的是，我们观察到每个线程只会为特定类型的张量分配内存。具体来说，权重的内存空间只在加载线程中分配，而激活和中间的内存空间只在计算线程中分配。因此，每种张量的内存分配顺序是固定的。因此，我们通过其类型和类型内的计数（例如，Weights-5）唯一地标识每个张量，以确保正确的分配顺序。分配的张量ID与分配的地址之间的映射关系可以通过对内存规划结果的轻量级后处理得到。
实验与结果
论文基于NCNN实现，在六个DNN模型和三个设备上评估了FlexNN，以证明其在受限内存下实现高效和自适应DNN推理的能力。端到端评估涵盖了3种边缘设备和6种不同类型的DNN模型。
峰值内存减少，FlexNN支持比NCNN-Default和NCNN-Direct更低的内存预算，在大多数情况下比on - demand更低。
减少延迟，除了有效地减少内存使用外，FlexNN还实现了可接受的推理延迟。相同的内存预算下，FlexNN始终能够实现比基线更低或至少相当的延迟，特别是在低内存预算下。
模型和设备之间的差异。FlexNN在不同模型尺寸的cnn上取得了很好的性能，但在基于 transformer的模型上的改进并不显著。
延迟和内存权衡。与基线相比，FlexNN除了实现更好的总体延迟和内存之外，还展示了延迟和内存的权衡。这种权衡来自两个方面：(1)有了更大的内存预算，FlexNN可以使用更大获得分层加速。(2)对于给定的切片策略和内核选择，更大的内存预算允许FlexNN预加载更多权重，从而导致模型加速。的切片大小和更快的计算内核。
FlexNN的开销包括两个主要部分：离线规划开销和运行时预加载开销。
离线规划开销。离线规划开销包括转换权重的存储、分析的时间、层切片的时间和内存规划的时间。在大多数边缘设备上，有足够的存储容量（通常从几十到几百GB不等）来容纳转换后的权重，这满足了大多数场景。然而，当切片结果不能满足新的内存预算或存在分配错误时，需要重新切片和重新规划的额外成本，这种情况应该很少发生，因为我们的方法有效地控制了内存使用。
运行时I/O开销。FlexNN的运行时开销主要来自加载模型权重的额外I/O。FlexNN的峰值功耗与NCNN相似，但FlexNN的推断延迟更大，导致总功耗更高。具体来说，FlexNN在ResNet-152上使Pixel 6 Pro的能耗增加了1.02%，在VGG-19上增加了28.39%。考虑到存储器的高度限制，额外的能源成本是可以接受的。
讨论
作者在这部分给出了一些问题，值得讨论与探索：
不同的内存瓶颈。FlexNN自适应地处理权重或输入是分层内存瓶颈的情况，这在大多数模型中都很常见。当激活成为主要的内存瓶颈时，它的有效性可能会受到限制，因为我们目前的设计不支持激活切片。
不同的模型。由于cnn在移动设备上的主导地位，我们目前的实现主要集中在减少典型cnn（如VGG， ResNet和MobileNet）的内存占用。虽然我们已经在基于变压器的模型（包括ViT和GPT-2）上测试了FlexNN，但它们的结果并不显著。主要有两个原因。(1)基于transformer的模型中对多头注意（MHA）的层切片支持不如卷积层，这需要在未来的工作中进行非简单的工程改进。(2)与cnn相比，基于transformer模型的推理需要更密集的权值加载，这在基于流的推理中带来了更大的I/O开销。因此，将内存交换机制应用于这些模型更具挑战性。然而，我们的切片和内存管理设计适用于所有类型的模型。
不同的精度。虽然我们现在只使用基于fp32的模型来实现和评估FlexNN，但FlexNN的设计与数据精度无关。它不需要修改整体框架来增加对其他精度的支持，而操作符的移植仍然需要一定数量的工程努力。一般来说，FlexNN具有与压缩模型兼容的能力。
不同的硬件。由于FlexNN在移动/嵌入式AI应用中占据主导地位，目前的实现仅针对移动CPU，但由于FlexNN的切片和联合规划设计是通用的，不依赖于CPU等特定硬件，因此可以将实现迁移到不同的后端，包括移动GPU， NPU， DSP和Tensor Cores。但是，对于迁移和实际部署，应该考虑以下因素。
(1)我们的方法涉及细粒度内存管理，这可能需要低级api来支持实现。(2)由于基于流的推理设计带来了模型权重的额外I/O，因此需要考虑利用异构硬件的额外数据移动成本。(3) FlexNN较高的能耗可能是电池供电设备的限制因素。
引用内容（自用）
@inproceedings{10.1145/3636534.3649391,
author = {Li, Xiangyu and Li, Yuanchun and Li, Yuanzhe and Cao, Ting and Liu, Yunxin},
title = {FlexNN: Efficient and Adaptive DNN Inference on Memory-Constrained Edge Devices},
year = {2024},
isbn = {9798400704895},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
url = {https://doi.org/10.1145/3636534.3649391},
doi = {10.1145/3636534.3649391},
pages = {709–723},
numpages = {15},
keywords = {edge device, deep learning, DNN inference, memory management},
location = {Washington D.C., DC, USA},
series = {ACM MobiCom ‘24}
}