MINUN: 微控制器上的精确机器学习推理

Jaiswal S, Goli R K K, Kumar A, et al. MinUn: Accurate ML inference on microcontrollers[C]//Proceedings of the 24th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems. 2023: 26-39.

摘要

在微型设备上运行机器学习推理（TinyML）是一个新兴的研究领域。这项任务需要生成节约使用内存的推理代码，而标准的机器学习框架并不适合这个任务。TinyML的部署框架必须满足以下要求：(a) 在数字表示上具有参数化能力，以利用像posit这样的新兴表示方法；(b) 仔细地为少数张量分配高精度，使大多数张量可以保持低精度，同时仍保持模型精度；© 避免内存碎片化。本文描述了MINUN，这是第一个全面解决这些问题的TinyML框架，为ARM微控制器（如Arduino Uno、Due和STM32H747）生成高效代码，性能超越了之前的TinyML框架。

1. 引言

尽管内存是最昂贵的资源之一，但广泛使用的机器学习框架如TensorFlow和PyTorch在推理过程中假设有充足的内存可用。内存约束是硬性的：超过可用内存一个字节就会导致崩溃。因此，这些依赖解释器的框架不适合在内存受限的设备上运行机器学习。例如，Arduino Uno只有2KB的RAM，没有任何机器学习解释器能够装入其中。在本文中，我们探索为在这些设备上运行机器学习推理的部署框架。

最近，TinyML领域出现了大量工作，旨在在低功耗嵌入式设备上运行机器学习。作为一个激励性的例子，考虑一个嵌入大脑中的低功耗芯片，可以检测癫痫发作的开始并警告用户。Neuralink已经在进行动物脑芯片测试。这样的芯片需要在设备上本地执行推理（用户可能在没有互联网连接的地方），并且需要低功耗（避免热耗散造成的组织损伤和更换电池的脑部手术）。由于维护大型RAM会消耗电池，这些微型设备需要小型RAM，从几个字节到几千字节不等。尽管Neuralink的技术规格在公共领域不可用，但作为参考，心脏起搏器中的微控制器的内存在16字节到10KB之间。因此，需要将机器学习模型编译为内存高效的代码的部署框架，这些代码可以在微型设备的指定RAM限制内运行。

图1：面部检测示例
该图展示了一个教室场景的图像，其中机器学习模型已经在图像中标记了多个人头。红色矩形框标出了检测到的每个人脸的位置。这个RNNPOOL模型提供了最先进的精度，仅消耗约600KB的RAM，这相比之前的模型是一个巨大的改进（例如，即使是大小优化的架构如MobileNetV2-SSDLite也需要超过3MB的RAM）。然而，这个RNNPOOL模型仍然超过了256KB设备的可用内存。

在微型设备上运行机器学习推理并非易事。卷积神经网络（CNN）有数百万个参数，需要MB或GB的内存，不适合在微型设备上运行。因此，我们对最近为微型设备设计的模型感兴趣，这些模型专门设计为提供良好的精度，同时只需要数千个参数和KB的内存，例如循环神经网络（RNN）。然而，即使在微型设备上运行这些模型也具有挑战性。所有这些机器学习模型都使用高精度的32位浮点数，我们希望通过进一步减少位宽将它们压缩到微型设备上。

例如，假设我们想在具有256KB RAM的标准ARM Cortex-M类微控制器上运行面部检测。RNNPOOL模型提供了最先进的精度，仅消耗约600KB的RAM，这相比之前的模型是一个巨大的改进。然而，这个RNNPOOL模型仍然超过了256KB设备的可用内存。

1.1 TinyML的三个子问题

在TinyML领域实现高效推理需要解决三个关键的技术挑战，每个挑战都有其独特的复杂性和权衡。

第一个子问题：数字表示的选择

我们需要使用能够用较少的位数很好地近似32位浮点数的数字表示，并且在硬件中高效实现其操作。最近出现了一波新的数字表示方法：TFLite的Zero-Skew、Google的BFloat16、NVIDIA的TensorFloat-32、Microsoft的MSFP、Tesla的CFP8和posit表示。

Posit特别具有吸引力，因为它们与浮点数相比具有更好的动态范围和精度。先前的TinyML框架与特定表示绑定，如zero-skew或定点。一个随着快速发展的数字表示而保持相关性的强大框架必须在数字表示上是参数化的。

第二个子问题：位宽分配

对于每个张量，我们需要决定是保持高精度还是低精度。将所有张量保持在低精度会导致巨大的精度损失，而将它们全部保持在高精度则在内存上是浪费的。因此，对于$N$个张量，我们有$2^N$种选择，需要一种启发式方法来选择一个好的位宽分配，以最小化内存使用，同时保持模型精度。

关键的是，决定张量是分配低精度还是高精度必须考虑张量的大小及其对精度的影响。没有先前的工作提供这样的技术来获得良好的位宽分配。请注意，TFLite和SeeDot对所有模型使用相同的位宽分配，而Shiftry专门使用精度来找到合适的位宽分配。

第三个子问题：内存管理

与现代CPU不同，微型设备没有虚拟内存的硬件支持。因此，碎片化会迅速使程序耗尽内存。程序是否能够适应给定的内存限制是一个NP完全的装箱问题。先前工作为这个内存管理问题提供的解决方案（即决定分配新张量的物理内存地址）是不令人满意的：TFLite要求程序员手动管理RAM，SeeDot使用浪费的静态分配，Shiftry使用减少碎片化的启发式方法，但没有最优性保证。虽然为不同变量重用内存具有寄存器分配的味道，但请注意寄存器不会受到碎片化的影响，这是这里的主要问题。

图3：碎片化示例
该图展示了内存碎片化如何发生的四个阶段：

1. 开始时有一个空的RAM（0-384字节）
2. 分配张量A、B、C和D，每个64字节，完全填充内存
3. 稍后，释放A和C，释放128字节但创建了两个不连续的64字节块
4. 然后尝试分配大小为128字节的E，由于碎片化失败
   碎片化的RAM使用：384字节，最优峰值RAM使用：256字节

1.2 我们的贡献

我们提供了一个框架MINUN，在所有三个子问题上都取得了重大进展。

参数化的数字表示：MINUN是第一个参数化于任意数字表示的TinyML框架，我们使用定点和posit表示评估了MINUN。我们设计MINUN在表示特定部分和表示独立部分之间有明确的分离。相比之下，先前的TinyML框架与它们使用的数字表示极其绑定。

位宽分配：对于位宽分配问题，我们提出了一种新颖的探索算法HAUNTER，它使用精度和大小来产生比Shiftry基于精度的启发式更好的分配，同时更加高效和可扩展。

内存管理：最后，对于RAM管理，MINUN将内存管理问题编码为装箱问题，并使用Knuth的算法X求解，该算法保证在指数时间内返回最优结果。在这里，我们的主要贡献是提出一个有效的编码并调整Knuth算法X的通用框架以确保实践中的可处理运行时间。

特别是，对于图1中的模型，MINUN将RAM消耗从约600KB减少到约180KB，从而使该模型能够在具有256KB RAM的设备上运行。尽管MINUN不是为大型模型设计的，但即使在ImageNet规模的CNN上，MINUN也优于先前的TinyML框架。

2. 编译器概述

图2：MINUN概述
该图展示了MINUN编译器的完整流程。输入是用Shiftry-DSL编写的程序，经过以下阶段：

1. 输入的TensorFlow/PyTorch模型通过ONNX转换器
2. 生成Shiftry DSL代码
3. AST（抽象语法树）生成
4. HAUNTER位宽分配探索
5. 最优内存管理
6. C++推理代码生成
7. 编译和执行，生成精度和内存使用图表

MINUN期望输入一个用Shiftry-DSL编写的程序，这是一种用于表达机器学习模型中常用操作和函数的简洁语法。模型的DSL代码可以手动编写，也可以通过将TensorFlow/PyTorch模型导出到ONNX并使用MINUN的ONNX前端自动获得。MINUN然后解析来自DSL的输入程序并生成HAUNTER（我们的位宽探索策略）所需的抽象语法树（AST）。HAUNTER然后返回程序中所有张量的合适位宽分配。这是通过选择初始位宽分配、为其生成相应的x86 C++推理代码、使用GCC编译它并执行代码以记录精度和内存使用，以及使用记录的信息来更改位宽分配来实现的。HAUNTER确保在位宽探索期间始终满足用户提供的内存约束，并返回最大化精度的合适分配。然后通过我们的最优内存管理策略，我们从RAM张量到全局暂存缓冲区中的索引获得内存映射，对应于给定的位宽配置。回想一下，MINUN的目标是最小化暂存的总大小，同时确保程序正确执行。

最终的设备特定C++代码使用AST上的代码生成过程生成，该过程还根据我们的内存映射将所有中间RAM张量替换为基于偏移的暂存访问。然后将这个最终的C++代码交叉编译（使用ARM GNU工具链或Arduino IDE）并在选择的微控制器上执行。

3. 技术细节

3.1 使用HAUNTER的位宽分配

HAUNTER算法在三阶段过程中工作，第一阶段依赖于所考虑的数字表示，其余两个阶段与表示无关。HAUNTER使用三个用户提供的信息——可用RAM的数量、探索要在其间开始的一对位宽（highBitwidth和lowBitwidth），以及作为调优参数的软限制因子，可用于通过选择软限制<1使探索过程更加节俭。我们使用$\rho$表示位宽分配，它将每个张量映射到两个可能的位宽$\{\text{lowBitwidth}, \text{highBitwidth}\}$。

3.1.1 预处理（阶段I）

这个阶段找到捕获输入和中间张量运行时范围的数据相关参数的值。这些参数的例子包括8位和16位posit的最合适的$es$值（因为这些位宽支持多个$es$选项），以及定点的各个张量的尺度。对于posit，我们简单地基于同质位宽配置获得的精度选择适当的$es$值。要确定定点的尺度，我们使用Shiftry的数据驱动尺度分配过程，该过程通过在给定输入集上运行代码的浮点版本来分析每个张量。这个分析信息包括每个张量观察到的最小值和最大值，用于为定点张量分配合适的尺度。

3.1.2 热图生成（阶段II）

在对特定数据点进行推理期间，"值映射"存储键值对，其中键是张量名称，值是该张量在提供的数据点上执行期间持有的浮点值。HAUNTER从初始配置开始，其中所有张量都保持在lowBitwidth。

在第一阶段，我们同时将每个可提升的张量设置为highBitwidth，然后编译并执行代码以获得"高位宽值映射"。我们重复相同的过程，通过同时将每个张量设置为lowBitwidth，编译并执行以获得类似的"低位宽值映射"。基于这两个映射，我们在第二阶段尝试创建一个"热图"，其中我们简单地计算每个张量在highBitwidth和lowBitwidth情况之间的代表性浮点值的绝对偏差。由于跟踪大型张量是不可行的，我们简单地按升序对逐元素偏差进行排序，并将第95百分位偏差作为每个张量的代表性误差偏差。我们将可提升性分数定义为：

$$\text{Promotability} = \frac{\text{第95百分位误差偏差}}{\text{张量基数}}$$

这里，张量基数指张量的大小或张量中的元素数量。按可提升性分数降序对张量进行排序，提供了一个称为promotionOrder的有序排名，它优先考虑具有大误差偏差的较小张量首先被提升。

3.1.3 提升算法（阶段III）

提升算法本身分三个阶段运行。第一阶段旨在累积提升所有张量，同时保持在memoryLimit内，并确定哪些张量可能超出提供的限制。第二阶段单独考虑这些"超限"张量，首先提升它们，然后开始基于promotionOrder的探索。最终阶段在同时提升所有这些"超限"张量后开始探索。最终的位宽配置选择为最小化与浮点代码输出不一致计数的配置，并作为位宽探索的输出返回。

3.2 复杂度分析

位宽探索通过HAUNTER是MINUN计算最昂贵的部分，由于对不同位宽分配的重复代码生成和编译以及执行调用来测量精度。虽然前者取决于模型程序文本的大小，但后者由模型的运行时间和所考虑的数据集大小决定。

我们将每次代码生成调用所需的时间量表示为$T_{codegen}$，并将其视为不同位宽配置所需的代码生成和编译时间的上限。我们对执行调用延迟（每个示例）也遵循相同的术语，称之为$T_{execution}$。

对于$N$个张量的模型，提供$D$个样本的数据集，Shiftry产生的位宽探索延迟为：

$$O(N \times D \times T_{execution} + N \times T_{codegen})$$

HAUNTER改进为：

$$O(\log N \times D \times T_{execution} + N \times \log N \times T_{codegen})$$

这种改进来自于HAUNTER智能地减少了需要评估的配置数量，同时仍然找到高质量的位宽分配。

3.3 最优内存管理

一旦计算出位宽分配，MINUN必须在物理内存地址分配张量，以通过最大化RAM位置的重用来保持峰值RAM消耗低。有几种方法可以进行这种内存管理。

静态分配：当张量进入作用域时将其推入程序栈，当它们以后进先出（LIFO）顺序离开作用域时弹出。这种方法导致高RAM消耗，因为张量$X$不能在稍后实例化的张量被释放之前被释放，即使$X$不再活跃。

动态分配：张量在程序堆上分配内存，不再需要时释放。这种方法将内存管理委托给运行时，对于资源受限的设备来说，由于其运行时开销，这可能不是首选。这种方法已知容易发生碎片化。

将内存管理委托给编译器：给定具有固定大小输入的机器学习模型，张量大小和活跃范围（张量被使用并需要内存的指令范围）可以在编译时知道。从张量到连续数组（暂存）上的内存位置（或索引）的映射可以在代码生成过程中计算。这重用了不再活跃的张量的内存来分配新张量。计算这样的映射是一个NP难的装箱问题，可以通过次优贪婪启发式解决。

静态和动态分配方法无法使FASTGRNN和RNNPOOL模型适应微控制器可用的典型RAM预算。因此，我们采用第三种方法，但与先前的工作不同，我们不使用贪婪启发式。相反，我们将装箱问题作为精确覆盖问题处理。

定义1（精确覆盖）：设$\mathcal{P}(X)$表示集合$X$的幂集。给定集合$X$和$S \subset \mathcal{P}(X)$，$X$的精确覆盖是集合$S^* \subset S$，使得：

• $s_i \cap s_j = \emptyset, \forall s_i, s_j \in S^*, i \neq j$
• $\bigcup_{s_i \in S^*} s_i = X$

考虑一个大小为$M \times I$的2D画布（其中$M$是沿y轴的字节内存预算，$I$是沿x轴的程序中的指令数）。画布的最小单个元素$c_i$是单位面积的正方形，语义上表示仅对单个指令活跃的字节大小的张量。对于在指令$i_{start}$和$i_{end}$之间活跃并在内存中占用$b_i$字节的张量$v_i$，我们可以在此画布上映射由$b_i \times (i_{end} - i_{start})$个连续单元组成的矩形，出现在$i_{start}$和$i_{start}$之间。

图4：示例画布与潜在内存映射
该图展示了一个5×5的画布，其中$I$（指令）沿x轴从1到5，$M$（内存）沿y轴从0到5。彩色区域显示了在指令2和4之间活跃的2字节张量的潜在内存映射。每个这样的映射将形成给定$v_i$的$C_{v_i}$中的唯一元素。图中显示了多个可能的位置（$c_1$-$c_{25}$），其中张量可以被放置。

设$C = \{c_1, c_2, ..., c_{M \times I}\}$表示画布中所有单元元素的集合，$V = \{v_1, v_2, ..., v_N\}$表示程序中所有张量的集合。另外，对于每个张量$v_i$，我们定义一个新集合$C_{v_i} \subset \mathcal{P}(C)$，包含$C$中所有可以成为张量潜在内存映射的单元元素子集。因此，$C_{v_i}$中的每个单独集合形成跨越$v_i$活跃范围的连续内存块，并且具有至少$b_i$单元的高度。

设$X = C \cup V$，$S \subset \mathcal{P}(X)$具有以下约束：$\forall s_k \in S, v_i \in V [v_i \in s_k \Rightarrow s_k \setminus v_i \in C_{v_i}]$

给定这些集合，我们使用指数时间的回溯搜索算法（称为算法X）解决精确覆盖问题，并进行以下优化以加速探索：

• 我们使用Dancing Links算法高效地分配和取消分配张量矩形到特定内存位置
• 我们按矩形面积降序访问张量，作为快速剪枝导致张量之间冲突的分配的启发式方法
• 我们做出粗化假设：所有张量假设具有某个粗化常数$k$的倍数大小

我们的最优内存管理机制旨在为最小可行值$M$找到精确覆盖。在每个指令处，我们可以通过紧密堆叠该指令处活跃的张量来找到执行所需的最小内存预算，在y轴上没有间隙和重叠，并查看堆栈的高度。为所有$I$个指令计算此高度，并从中选择最高值，给我们这个最小预算。

一旦为最小$M$找到精确覆盖，我们可以通过取其最小y坐标并将其用作暂存起始位置的偏移，将张量从画布映射到暂存。请注意，由于$M$表示画布的最小可行高度，它也表示暂存的总大小。由于精确覆盖在最小可行预算内找到合适的分配，它有效地解决了碎片化问题。

4. 实施细节

我们的框架建立在Shiftry之上，已在19K行Python代码和12K行C/C++代码中实现。此外，我们使用以下库集来获得不同数字表示的算术例程：

• BFloat：TensorFlow库中实现的独立C++仅头文件子库，允许在Float32和BFloat16类型之间转换
• SoftPosit：提供posit算术例程，用于使用C++在基于x86的平台上进行模拟。该库包含Posit标准中期望的所有函数。对于8位posit，支持$es = 0$和$es = 2$，对于16位posit，支持$es = 1$和$es = 2$
• gemmlowp：矩阵乘法库，设计用于"低精度"8位定点类型。这是TFLite的zero-skew数字表示使用的库

对于大型模型的评估，我们从公共ONNX模型动物园下载预训练的ONNX模型，并实现了一个Python前端，用于自动将ONNX模型编译为MINUN作为输入的DSL程序。在某些算术函数对给定数字表示不可用的情况下（即BFloat16算术和SoftPosit中的$\exp(x)$函数），我们简单地将给定表示转换为Float32，回退到内部Float32算术进行计算，并将生成的输出转换为原始类型。

内存管理的超时设置为2小时。对于RNNPOOL模型，我们使用粗化参数$k = 64$，对于其余模型，我们使用粗化参数$k = 1$。

5. 评估

我们将参数化了posit表示和定点表示的MINUN分别称为MINUN-POSIT和MINUN-FIXED。我们还将vanilla Shiftry称为SHIFTRY-FIXED，将我们对Shiftry的posit适配称为SHIFTRY-POSIT。

5.1 分类模型和数据集

我们在为资源受限设备开发的三个最先进的TinyML分类模型上进行评估，即PROTONN、BONSAI和FASTGRNN。这些适合在Arduino类设备上运行，支持最少2KB的SRAM和40KB的Flash。为了评估的公平性，我们涵盖了Shiftry评估的整个数据集套件。这些包括CIFAR、字符识别（CR）、USPS、Curet、Letter、Ward和MNIST用于PROTONN和BONSAI，以及DSA、Google、HAR、MNIST、USPS、Industrial和Wakeword用于FASTGRNN。

5.2 定位模型和数据集

RNNPOOL是一种为减少卷积输出大小而开发的新池化层，同时保留足够的信息用于下游任务，从而节省计算并减少内存占用。使用RNNPOOL，我们设计了三个面部检测模型（Face-A、Face-B和Face-C）用于教室/会议设置，它们将$320 \times 240 \times 1$单色QVGA图像作为输入。Face-C模型是Saha等人介绍的RNNPOOL-Face-M4模型的直接复制。

这些模型的架构总结在表7中（见附录）。这些基于RNNPOOL的模型设计用于ARM Cortex-M类设备，支持最少256KB的SRAM和1MB的Flash。我们在WIDER FACE数据集上训练这些模型，并在SCUT-HEAD数据集上进行微调。对于模型精度，我们在SCUT-HEAD Part-B的20%验证分割（405张图像）上评估生成的代码，并报告MAP分数。

5.3 与8位基线的比较

图5：针对Float32黄金标准的精度/MAP下降
该条形图显示了不同8位表示（Fixed8、Posit8、Zero-Skew8）和MINUN-Posit在四个模型（FASTGRNN、PROTONN、BONSAI、RNNPOOL）上的精度下降。Y轴显示精度下降百分比（越低越好）。图表清楚地显示，8位表示遭受了不可接受的精度损失，特别是对于FASTGRNN和RNNPOOL模型，其中一些配置显示超过60%的精度下降。MINUN-Posit通过谨慎使用高位宽16位posit，在所有模型上的精度下降都很低。我们的目标是通过比较不同8位数字表示的模型精度与Float32黄金标准的精度来证明我们的第一个声明。图5显示8位表示的精度很差。在8位posit（POSIT8）的情况下，我们简单地选择在数据集上经验性地导致更好精度的$es$。8位定点（FIXED8）给出最差的精度，TFLite的8位zero-skew表示（ZERO-SKEW8）表现更好，POSIT8在8位表示中表现最好。然而，即使POSIT8的精度损失对于FASTGRNN和RNNPOOL也是不可接受的。通过谨慎使用高位宽16位posit，MINUN-POSIT的精度下降对所有模型都很低。

5.4 与16位基线的比较

图6：相对于Float32黄金标准的RAM压缩
该条形图比较了Float32、Fixed16/BFloat16和MINUN-Posit在四个模型上的RAM压缩因子。Y轴显示RAM压缩因子（越高越好）。MINUN-Posit在所有模型上都实现了显著的RAM减少，压缩因子从$2.9\times$到$5.1\times$不等。特别是对于BONSAI模型，MINUN-Posit实现了超过$5\times$的压缩，而对于其他模型也保持了$3-4\times$的压缩率。

我们比较MINUN-POSIT与黄金标准Float32基线的精度和RAM消耗。由于16位表示在某些模型上也提供了与Float32相当的精度，RAM消耗约为$2\times$更少，我们也与16位定点（FIXED16）和BFLOAT16进行比较。我们生成MINUN-POSIT结果，同时确保获得的精度保持在每个数据集相应Float32结果的0.2%以内。

图6总结了我们的实验，即使与FIXED16或BFLOAT16相比，我们在峰值RAM消耗方面实现了$2.9\times$-$5.1\times$的显著减少，同时与Float32相比只观察到可忽略的精度差异。

5.5 位宽分配

我们在定点和posit中比较MINUN的位宽分配机制与Shiftry的机制以及其他专门基于精度和专门基于大小的机制。

在基于大小的基线中，我们将所有张量提升到更高的位宽。然后，重用Shiftry的累积降级过程，我们按张量大小的顺序单独降级张量，直到我们达到满足所考虑的内存约束的位宽配置。类似地，对于基于精度的基线，我们向Shiftry的降级过程添加相同的内存约束。在这里，我们按降序排列张量的单独降级精度，并启动降级过程，当我们达到满足限制的位宽配置时停止。

表1总结了我们对定点表示的实验，每个模型基础上针对MINUN-FIXED提到了每个探索策略的平均精度下降。我们在大多数模型和基线上观察到更好的平均精度数字，同时严格保持在相同的RAM约束内。

特别值得关注的是定点RNNPOOL，其中MINUN相对于Shiftry显示出23.3%的MAP分数改进，导致推理质量的显著改进。

图7和图8：Face-C模型上的示例对比
这两个图并排展示了同一教室场景图像上SHIFTRY-FIXED（图7）和MINUN-FIXED（图8）的输出。在图7中，SHIFTRY-FIXED检测到许多误报，红色框散布在整个图像中，包括许多不包含面部的区域。相比之下，图8中的MINUN-FIXED产生了更清晰、更准确的检测，正确识别了场景中的实际面部，误报显著减少。这种视觉比较清楚地展示了MINUN改进的位宽分配如何转化为更好的实际推理质量。

5.6 推理延迟和编译时间

请注意，RAM使用和模型精度独立于底层硬件，它们的改进对使用的微控制器是不可见的。然而，推理延迟取决于微控制器，MINUN为各种微控制器生成代码。表13提供了在Arduino Uno（具有2KB RAM的设备）上运行MINUN生成的定点分类模型的推理延迟。

此外，表3比较了MINUN和Shiftry的推理延迟。正如预期的那样，MINUN在内存使用方面的改进对微控制器上的执行延迟影响可忽略不计。对于分类和定位模型，延迟分别在Arduino Due（84 MHz，96 KB SRAM，512 KB Flash）和STM32H747（240 MHz，1 MB SRAM，2 MB Flash）板上测量。

我们还比较了MINUN和Shiftry的编译时间。对于编译时间在位宽分配和内存管理之间的分解，请参阅附录中的表12。

5.7 ImageNet上的评估

表4在SqueezeNet上评估MINUN-POSIT - 这是一个ImageNet规模的CNN，在具有$50\times$更小尺寸的同时匹配AlexNet的精度。尽管SqueezeNet不是为在微型设备上部署而设计的，但我们通过这个实验展示了我们框架在为大型模型实现显著RAM使用减少方面的多功能性。请注意，对于像ResNet50和MobileNets这样的更大CNN，将所有张量保持在低位宽可以保持精度，这使得位宽分配变得微不足道。为了测量精度，我们在分布在1000个类别的48,000张RGB图像上评估生成的代码。

我们在MINUN-POSIT的标准首次适配启发式的内存管理生成的代码上观察到1.44 MB的峰值RAM消耗，使用我们的最优内存管理进一步减少到1.16 MB，提供了近20%的改进。如表4所示，我们实现了高达$3.81\times$的峰值RAM消耗减少，相对于Float32黄金标准的精度损失最小，而现有的TinyML框架（TFLite和Shiftry）无法在不导致显著精度损失的情况下提供可比的减少。特别是，MINUN的RAM消耗比Shiftry减少$1.9\times$，同时获得6.5%更高的精度。

6. 讨论

6.1 允许溢出

对于定点，HAUNTER以排除整数溢出的方式分配位宽。然而，这种策略并不总是实现高分类精度的最佳选择。特别是，Shiftry允许值在某些输入上溢出以在其他输入上实现更高的精度，从而整体分类精度很高。虽然这种优化在定点表示的情况下效果很好（其中溢出更好理解），但在其他任意数字表示的情况下，其效果难以预测。由于HAUNTER不允许溢出，它错过了这种权衡。这种限制最好通过HAR-6数据集上的FASTGRNN模型捕获，其中生成的模型相比其他策略损失了近2%，这是表1中FASTGRNN模型平均精度下降为负的唯一原因。

6.2 推广到更多位宽选项

HAUNTER在两个位宽lowBitwidth和highBitwidth之间决定。如果有更多位宽选项，HAUNTER可以生成更好的代码是合理的。有$k$个位宽选项导致总共$k^N$个可能的位宽分配，其中$N$是程序中的张量数。一般来说，直接向算法添加更多位宽选项会爆炸搜索空间并导致许多代码执行，使MINUN变得痛苦地缓慢。我们用三个位宽（8、12和16）对posit进行了实验，但与两个位宽选项（8和16）或（8和12）或（12和16）的情况相比，在我们的实验中没有发现任何明显的精度优势，具体取决于特定模型。因此，我们在表9中选择了一个更简单的策略。给定$B = \{8, 9, 10, 12, 16\}$位宽选项，我们生成$|B|$个同质位宽代码（每个选项一个），并按其相应代码获得的精度/MAP对位宽进行排序。在这些排序的位宽中，我们简单地选择32位浮点精度所在的两个选项，分别作为lowBitwidth和highBitwidth。

附录A：数学基础和推导

A.1 定点表示

在标准定点算术中，实数$r$存储为$b$位有符号整数$\lfloor r \times 2^s \rfloor$，其中$s$是预定的整数，称为尺度，$b$称为表示的位宽。

考虑实数$r = 1.6181$的详细推导：

$$r = 1.6181 = 1.6181 \times \frac{2^{14}}{2^{14}} \approx \frac{\lfloor 1.6181 \times 2^{14} \rfloor}{2^{14}} = \frac{26510}{2^{14}} = 26510 \times 2^{-14}$$

要在定点算术中表示1.6181，我们存储16位整数26510，关联尺度为14。解释的实际值将是：

$$26510 \times 2^{-14} = \frac{26510}{16384} \approx 1.61804$$

这是原始值的近似。

对于任何实数和给定位宽，定点表示有一个最优尺度。在上面的例子中，给定16位整数表示，14是1.6181的最优尺度，因为：

• 使用尺度15或以上会导致整数溢出：$\lfloor 1.6181 \times 2^{15} \rfloor = 53020 > 2^{15} - 1$
• 使用尺度13或以下会导致更不精确的结果：$\lfloor 1.6181 \times 2^{13} \rfloor \times 2^{-13} \approx 1.6176$

A.2 Posit表示的数学推导

Posit是一种新的实数表示，设计为IEEE-754浮点的替代品。posit表示由4个部分组成：符号位$(s)$、regime位$(r)$、指数位$(e)$和分数位$(f)$。

对于给定位宽，$es$值表示指数部分可用的最大位数。一旦考虑了符号、regime和指数位，只有剩余的位被解释为分数位。

要找到posit表示中数字的值，我们定义一个参数称为useed：

$$\text{useed} = 2^{2^{es}}$$

具有符号位$s$的posit的值是：

$$(-1)^s \times (\text{useed})^k \times 2^E \times 1.F$$

其中：

• $E$是指数位$(e)$表示的指数值
• $k$是regime位$r$表示的值
• $F$是分数位$f$表示的分数

例如，假设$es = 2$且位宽为8位，位串01101101将被解释为：

• 符号位（$s = 0$）
• Regime位（$r = \{110\}$）。因此$k = 1$
• 指数位（$e = \{11\}$）。因此$E = 2^3 = 8$
• 分数位（$f = \{01\}$）。因此$1.F = 1.25$

由于$\text{useed} = 2^{2^{es}} = 16$，因此我们的位串表示的实数是：

$$1 \times 16^1 \times 8 \times 1.25 = 160$$

A.3 HAUNTER复杂度分析

Shiftry的复杂度

Shiftry的位宽分配机制遵循一个探索阶段，其中每个张量发生两次代码生成、编译和执行：一次在单独张量降级期间，一次在累积张量降级期间。

对于$N$个张量和$D$个数据样本：

• 单独降级：$N$次代码生成 + $N \times D$次执行
• 累积降级：$N$次代码生成 + $N \times D$次执行
• 总计：$O(2N \times T_{codegen} + 2N \times D \times T_{execution}) = O(N \times T_{codegen} + N \times D \times T_{execution})$

HAUNTER的复杂度

HAUNTER的核心观察是大多数机器学习模型在张量大小上表现出不对称的多样性。经验上，张量大小似乎遵循指数分布。

假设常数参数$\alpha > 1$，$\text{memoryLimit} = C$，对于某个正标量$C = \Theta(N^\alpha) \ll \alpha^N$，我们观察到可以安全累积提升到更高位宽的最大张量数是：

$$\lfloor \log(\text{memoryLimit}) \rfloor = \lfloor \log C \rfloor = O(\log N)$$

因此，无论提升顺序和overshootingVars集合的大小如何，只有$O(\log N)$个张量可以在累积提升期间进行超过第10行，导致平均$O(\log N)$次执行调用，从而显著减少探索延迟。

热图生成需要$O(N)$次操作来计算所有张量的可提升性分数，排序需要$O(N \log N)$。

因此，HAUNTER的总复杂度：

• 热图生成：2次代码生成 + $2 \times D$次执行
• 提升算法：$O(\log N)$次代码生成 + $O(\log N) \times D$次执行
• 排序：$O(N \log N)$操作
• 总计：$O(\log N \times D \times T_{execution} + N \times \log N \times T_{codegen})$

A.4 内存管理的数学形式化

精确覆盖问题的形式化

给定：

• 画布$C = \{c_1, c_2, ..., c_{M \times I}\}$（所有单元元素）
• 张量$V = \{v_1, v_2, ..., v_N\}$
• 对于每个$v_i$，潜在映射$C_{v_i} \subset \mathcal{P}(C)$

构造：

• $X = C \cup V$
• $S \subset \mathcal{P}(X)$，约束：$\forall s_k \in S, v_i \in V [v_i \in s_k \Rightarrow s_k \setminus v_i \in C_{v_i}]$

目标：找到$S^* \subset S$使得：

1. $s_i \cap s_j = \emptyset, \forall s_i, s_j \in S^*, i \neq j$（互斥性）
2. $\bigcup_{s_i \in S^*} s_i = X$（完整性）

最小内存预算的计算

对于指令$i$，所需内存为：

$$M_i = \sum_{v \in \text{alive}(i)} \text{size}(v)$$

其中$\text{alive}(i)$是指令$i$处活跃的张量集合。

最小内存预算：

$$M_{\text{min}} = \max_{i=1}^{I} M_i$$

碎片化度量

碎片化可以量化为：

$$\text{Fragmentation} = \frac{\text{Actual Peak RAM} - M_{\text{min}}}{M_{\text{min}}} \times 100\%$$

例如，在图3的例子中：

• 最小理论峰值RAM = 256字节
• 实际碎片化RAM使用 = 384字节
• 碎片化 = $(384 - 256) / 256 \times 100\% = 50\%$

A.5 位宽分配的优化问题形式化

位宽分配可以形式化为以下优化问题：

目标函数：

$$\min_{\rho} \sum_{i=1}^{N} \text{size}(v_i) \times \text{bitwidth}(\rho(v_i))$$

约束条件：

1. 精度约束：$\text{Accuracy}(\rho) \geq \text{Accuracy}_{\text{target}}$
2. 内存约束：$\text{PeakRAM}(\rho) \leq \text{MemoryLimit}$
3. 位宽约束：$\rho(v_i) \in \{\text{lowBitwidth}, \text{highBitwidth}\}, \forall i$

其中$\rho$是从张量到位宽的映射函数。

A.6 可提升性分数的统计推导

对于张量$v_i$，设：

• $X_i^{\text{high}}$：高位宽下的值分布
• $X_i^{\text{low}}$：低位宽下的值分布
• $\varepsilon_{ij} = |X_{i,j}^{\text{high}} - X_{i,j}^{\text{low}}|$：第$j$个元素的误差

第95百分位误差定义为：

$$P_{95}(\varepsilon_i) = \inf\{x : P(\varepsilon_{ij} \leq x) \geq 0.95\}$$

可提升性分数：

$$\text{Promotability}(v_i) = \frac{P_{95}(\varepsilon_i)}{\text{cardinality}(v_i)}$$

这个分数平衡了精度影响（通过误差）和内存成本（通过基数），优先考虑具有高相对误差的小张量。

附录B：工作示例

考虑过程1中的线性分类器，让我们详细推导位宽分配过程。

B.1 初始设置

给定：

W1 = [-2.139562  1.885351]
X1 = [1.185109  -2.206466]^T
B1 = [0.146048]

计算：

t1 = W1 × X1 = -2.139562 × 1.185109 + 1.885351 × (-2.206466)
   = -2.536207 - 4.159040 = -6.695247
t2 = t1 + B1 = -6.695247 + 0.146048 = -6.549199

B.2 同质16位posit代码分析

内存使用：

• W1：$1 \times 2 \times 2$字节 = 4字节（Flash）
• X1：$2 \times 1 \times 2$字节 = 4字节（Flash）
• B1：$1 \times 1 \times 2$字节 = 2字节（Flash）
• t1：2字节（RAM）
• t2：2字节（RAM）
• 总RAM：4字节 > 3字节限制

B.3 HAUNTER探索过程

步骤1：生成值映射

高位宽（16位）值：

• $W_1 = (-2.13965, 1.88525)$
• $X_1 = (1.18506, -2.20605)$
• $B_1 = 0.146057$
• $t_1 = -6.69531$
• $t_2 = -6.54883$

低位宽（8位）值：

• $W_1 = (-2.25, 1.875)$
• $X_1 = (1.125, -2.25)$
• $B_1 = 0.140625$
• $t_1 = -7$
• $t_2 = -7$

步骤2：计算可提升性分数

提升顺序：$[t_2, t_1, X_1, B_1, W_1]$

步骤3：累积提升

从所有张量为8位开始：

1. 提升$t_2$到16位：RAM = 3字节（$t_1$:1字节 + $t_2$:2字节）✓
2. 提升$t_1$到16位：RAM = 4字节 > 3字节 ✗
3. 继续$t_2$为16位，提升$X_1$：RAM = 3字节 ✓
4. 提升$B_1$：RAM = 3字节 ✓
5. 提升$W_1$：RAM = 3字节 ✓

最终配置：$t_2$使用8位，其余使用16位。

B.4 内存映射

使用暂存数组：

char8[3] scratch;
scratch[0:1] = posit16(W1 × X1)  // t1占用字节0-1
scratch[2] = posit8(scratch[0:1] + B1)  // t2占用字节2

这确保峰值RAM使用保持在3字节限制以下。

附录C：算法伪代码

算法4：通过精度确定es

def Preprocess(lowBitwidth, highBitwidth):
    if lowBitwidth == 8:
        es8 = 2
        ρ = {var → 8 for var in allVars}
        
        accuracyES0 = Compile&Execute(es=0, ρ)
        accuracyES2 = Compile&Execute(es=2, ρ)
        
        if accuracyES0 > accuracyES2:
            es8 = 0
            
    if highBitwidth == 16:
        es16 = 2
        ρ = {var → 16 for var in allVars}
        
        accuracyES1 = Compile&Execute(es=1, ρ)
        accuracyES2 = Compile&Execute(es=2, ρ)
        
        if accuracyES1 > accuracyES2:
            es16 = 1
            
    return es8, es16

算法5：为每个位宽生成值映射

def CreateValueMaps(lowBitwidth, highBitwidth):
    ρ = {var → highBitwidth for var in allVars}
    ClearLogs()
    accHigh = Compile&Execute(ρ)
    varsValueMapHigh = Log&SaveValues()
    
    ρ = {var → lowBitwidth for var in allVars}
    ClearLogs()
    accLow = Compile&Execute(ρ)
    varsValueMapLow = Log&SaveValues()
    
    SaveAcc&Bitwidth(accLow, ρ)
    return varsValueMapLow, varsValueMapHigh

算法6：生成热图

def CreateHeatMap(varsValueMapLow, varsValueMapHigh):
    heatMap = {}
    
    for var in allVars:
        lowValues = varsValueMapLow[var]
        highValues = varsValueMapHigh[var]
        errors = []
        
        for lowValue, highValue in zip(lowValues, highValues):
            absError = |highValue - lowValue|
            errors.append(absError)
            
        heatMap[var] = (
            Get95thPercentileValue(errors) / 
            varsToSizeMap[var]
        )
        
    promotionOrder = DecreasingArgSort(heatMap).keys()
    return heatMap, promotionOrder

算法8：HAUNTER提升算法

def PromotionAlgorithm(promotionOrder, memoryLimit, softLimitFactor):
    ρ = {var → lowBitwidth for var in allVars}
    
    # 阶段1：识别超限张量
    overshootingVars = PromoteWithinMemoryLimit(
        promotionOrder, memoryLimit, softLimitFactor
    )
    accuracy = Compile&Execute(ρ)
    SaveAcc&Bitwidth(accuracy, ρ)
    
    # 阶段2：单独考虑超限张量
    for promotable in overshootingVars:
        ρ = {var → lowBitwidth for var in allVars}
        ρ[promotable] = highBitwidth
        
        memoryUsage = GetMemoryUsage(ρ)
        if memoryUsage > memoryLimit × softLimitFactor:
            continue
            
        PromoteWithinMemoryLimit(
            promotionOrder, memoryLimit, softLimitFactor
        )
        accuracy = Compile&Execute(ρ)
        SaveAcc&Bitwidth(accuracy, ρ)
    
    # 阶段3：同时提升所有超限张量
    ρ = {var → lowBitwidth for var in allVars}
    for var in overshootingVars:
        ρ[var] = highBitwidth
        
    PromoteWithinMemoryLimit(
        promotionOrder, memoryLimit, softLimitFactor
    )
    accuracy = Compile&Execute(ρ)
    SaveAcc&Bitwidth(accuracy, ρ)
    
    ρ = FindBitwidthConfigWithBestAccuracy()
    return ρ