嵌入式SPM优化：量化长分支开销的动态规划分配策略-平芜编程栈

1. 项目概述与核心挑战

在嵌入式系统，尤其是那些对功耗极其敏感的物联网终端、可穿戴设备或电池供电设备中，内存子系统的能量消耗常常是系统总功耗的“大头”。传统上，片上缓存（Cache）是弥合CPU与片外慢速内存速度鸿沟的利器，但其复杂的硬件逻辑（如Tag比较、替换策略）带来了不可忽视的静态和动态功耗。于是，一种更简单、更“可控”的片上存储方案——Scratch-Pad Memory（SPM，或称便签式内存）进入了我们的视野。SPM本质上就是一段软件管理的片上SRAM，它的地址映射是静态的，由编译器或程序员显式决定哪些代码或数据放进去。没有硬件自动管理的开销，SPM在面积和功耗效率上通常优于同等大小的Cache。

听起来很美好，对吧？但魔鬼藏在细节里。当我们试图将程序中的“热点”（频繁执行的代码块、常用全局变量）从片外SDRAM搬到片上SPM时，一个在RISC架构（如ARM、MIPS）中普遍存在但常被忽略的问题浮出水面：寻址模式限制。很多RISC处理器的分支（B, BL）和加载存储（LDR, STR）指令，其目标地址的寻址范围是有限的（例如，基于PC的相对偏移）。当你把一段代码从原来的地址A搬到了SPM中的地址B，原来那条从地址X跳转到A的指令可能就无法直接跳到B了，因为偏移量超出了指令编码的限制。为了解决这个问题，编译器或链接器不得不插入一段额外的指令序列，通常是“LDR PC, [PC, #offset]”配合一个存储目标地址的数据常量（DCD）。这被称为长分支指令集（Long Branch Instruction Set, LBIS）。

这个LBIS就是问题的核心。它不仅是几条额外的指令，占用了宝贵的程序空间，更重要的是，每次执行到这些被修改的分支点时，CPU都需要多执行指令、多访问内存，从而产生了额外的、非预期的能量开销。传统的SPM优化算法，无论是基于贪心、背包问题还是整数线性规划，大多只考虑了将热点搬入SPM带来的收益（减少了对慢速、高功耗的片外内存的访问），却忽略了因搬迁而引入的“搬家成本”——即这些LBIS带来的开销。在热点密集、函数调用频繁的程序中，这种开销可能相当可观，甚至可能抵消掉SPM带来的部分收益。

因此，我们面临的不是一个简单的“选哪些热点放进SPM”的问题，而是一个更复杂的“选哪些热点放进SPM，同时考虑它们之间的调用/跳转关系所带来的额外开销，使得净收益最大”的问题。这就像装修时不仅要考虑把最常用的家具（热点）放进小房间（SPM），还要考虑因为挪动了家具，你在房间里走动（程序执行流）的路径会不会变长、变复杂（LBIS开销）。本文介绍的方法，正是为了精准地量化并优化这个“装修方案”。

2. 核心思路：从程序结构到数学模型

要解决上述问题，我们需要一套系统性的方法，将模糊的程序行为转化为可计算的数学模型。整个过程可以分解为四个关键步骤：程序分解、开销量化、问题建模和优化求解。

2.1 程序分解与关系建模：扩展控制流图（ECFG）

第一步是把完整的程序二进制映像“打散”，分解成一个个可以独立考虑是否搬入SPM的基本单元，我们称之为节点（Node）。一个节点可以是一段连续的指令（基本块）、一个全局变量或一个栈帧区域。这比以整个函数为单位更精细，允许我们只搬移函数中最热的那部分循环，而不是整个函数。

仅仅有节点列表还不够，我们必须知道节点之间是如何交互的。这是通过**扩展控制流图（Extended Control Flow Graph, ECFG）**来实现的。ECFG在传统控制流图（CFG，描述基本块间的跳转）的基础上进行了扩展，增加了对函数调用和数据访问的建模。具体来说，它定义了五种节点间的关系边：

无条件分支边（R_BF）：例如B Label指令，执行流必然从源节点跳转到目标节点。
条件分支边（R_BC）：例如BEQ Label指令，执行流可能从源节点跳转到目标节点。
顺序执行边（R_T）：表示两个节点在内存中连续，执行完上一个自然进入下一个。这通常发生在没有分支的基本块之间。
函数调用边（R_C）：BL Function指令，从调用者节点跳转到被调用函数节点。
数据访问边（R_D）：一条加载/存储指令（LDR R0, [R1, #offset]）访问了某个全局数据节点。

通过静态分析二进制文件，我们可以构建出整个程序的ECFG。这张图清晰地描绘了所有可能的执行路径以及节点间的依赖关系，是后续量化分析的基础。

实操心得：构建精确的ECFG需要可靠的反汇编和静态分析工具。对于ARM架构，objdump配合自定义脚本是入门选择，但处理间接跳转（函数指针）和动态链接时会比较棘手。在实际工程中，可能需要结合编译时插桩（如LLVM Pass）来获取更精确的控制流和数据流信息，特别是在优化级别较高、编译器进行了激进优化的场景下。

2.2 开销的精确量化：关系矩阵（Relation Matrix）

有了ECFG，我们就可以精确计算移动一个节点到SPM所产生的“连锁反应”开销了。核心思想是：移动一个节点产生的能量和面积变化，不仅取决于这个节点本身，还取决于所有与它有关系的节点当前所在的位置（SPM或SDRAM）。

我们引入两个关键的n x n矩阵（n为节点总数）：

能量关系矩阵（ERM）：ERM[i][j]表示当仅节点i被放入SPM，并且节点i和节点j之间存在某种关系时，所产生的能量变化。注意，这个值是针对i和j这一对关系计算的。
面积关系矩阵（SRM）：SRM[i][j]表示当仅节点i被放入SPM，并且节点i和节点j之间存在某种关系时，节点i自身需要增加的代码大小（主要是LBIS占用的空间）。

如何计算这些值？我们以最常见的**无条件分支（R_BF）**为例，分两种场景：

场景一：源节点i被移入SPM，目标节点j留在SDRAM。
- 面积开销：源节点i的末尾需要将原来的B Label替换为LDR PC, [PC, #offset_to_DCD]和一条DCD指令（存储目标地址j）。这通常增加4字节（假设32位系统）。
- 能量开销：每次执行这个分支，CPU需要从SPM中多读一条DCD指令（读SPM能耗），并且跳转目标在SDRAM，这相比原来两者都在SDRAM的跳转，多了一次从SPM到SDRAM的访问模式切换开销。具体公式为：ΔE = 执行次数 * (读SPM能耗 + (SPM到SDRAM跳转能耗 - SDRAM到SDRAM跳转能耗))。
场景二：目标节点j被移入SPM，源节点i留在SDRAM。
- 面积开销：同样，源节点i需要替换为LBIS，增加4字节。
- 能量开销：此时DCD指令在SDRAM中，CPU需要先从SDRAM读取DCD，然后再跳转到SPM中的目标。能量变化为：ΔE = 执行次数 * (读SDRAM能耗 + (SDRAM到SPM跳转能耗 - SDRAM到SDRAM跳转能耗))。

论文中的表2总结了五种关系在不同场景下的开销公式。这些公式的系数（如2, 5）来源于对特定处理器内存子系统（如SDRAM的激活、预充电、行缓冲命中/未命中）和总线模型的精细建模。

构建矩阵的意义在于将动态的程序执行特征（关系、执行次数）和静态的硬件能耗参数（读SPM、读SDRAM、模式切换能耗）结合，预先计算好任意节点移动对任意相关节点产生的“影响值”。这样，在后续的优化选择中，我们不需要每次都重新模拟程序，只需查表并累加这些影响值即可。

2.3 问题建模：带依赖的改进背包问题

现在，我们可以将SPM分配问题形式化。假设SPM的总容量为C。每个节点i有两个基础属性：S(i)（节点自身大小）和E_sd(i) - E_sp(i)（若单独放入SPM的净能量收益，即放在SDRAM的能耗减去放在SPM的能耗，未考虑关系开销）。

但是，正如前面所述，一个节点的实际收益和实际占用空间是动态的，取决于已经有哪些节点被选入了SPM。我们用选择向量I（一个0/1数组，I[k]=1表示节点k已被选中）来记录当前的选择状态。

那么，在已有选择I的前提下，考虑将节点i加入SPM：

实际能量收益PE(i, I)=(E_sd(i) - E_sp(i))-∑(对所有j, I[j]*ERM[i][j])-∑(对所有j, I[j]*ERM[j][i])。这里减去的两项分别代表了：因i的移动对已选节点j的影响（ERM[i][j]），以及已选节点j对i的影响（ERM[j][i]）。注意，ERM矩阵是不对称的，ERM[i][j]和ERM[j][i]含义不同。
实际占用空间PS(i, I)=S(i)+∑(对所有j, I[j]*SRM[i][j])。增加的空间来自因i移动而需要添加到i自身的LBIS。

于是，我们的优化目标就变成了：从所有节点中选出一个子集，使得在它们实际占用空间之和不超过SPM容量C的前提下，它们的实际能量收益之和最大。这是一个经典的0/1背包问题的变体：物品（节点）的重量（占用空间）和价值（能量收益）不是固定的，而是会随着背包里已有物品的选择状态（向量I）而动态变化。这大大增加了问题的复杂度。

3. 优化求解：动态规划算法精解

面对这个“动态重量和价值”的背包问题，暴力枚举所有2^n种组合在节点数稍多时（n>30）就不可行了。我们需要更聪明的算法。论文采用了动态规划（Dynamic Programming, DP），这是解决经典背包问题的利器，但需要针对我们的问题进行巧妙改进。

3.1 状态定义与递推关系

我们定义m(i, j)为：从前i个节点（假设节点已编号）中做选择，在考虑节点间关系影响后，所能获得的最大净能量收益，且此时已选节点的实际占用空间不超过虚拟容量j。这里的j是DP表格中的索引，代表一种“容量预算”。

关键递推在于如何计算选择第i个节点的情况。假设我们正在计算m(i, j)，并且考虑选择节点i。

首先，我们需要一个“子问题解”：m(i+1, j')。它表示在不选节点i的情况下，从i+1到n的节点中，在容量预算j'下能获得的最大收益。注意，这个解对应一个具体的选择向量I'。
然后，计算选择节点i的代价与收益：在已有选择I'的基础上，加入节点i。
- 节点i的实际占用空间变为PS(i, I')（依赖于I'）。
- 节点i的实际能量收益变为PE(i, I')（依赖于I'）。
- 因此，选择i后的总收益是m(i+1, j') + PE(i, I')。
- 选择i后的总占用空间是j'_real + PS(i, I')，其中j'_real是子问题解m(i+1, j')实际占用的空间（可能小于预算j'）。
状态转移：为了计算m(i, j)，我们需要遍历所有可能的子问题容量预算j'（0 ≤j'≤j - S(i)，S(i)是节点i的基础大小，这是一个宽松上界），并检查在对应子问题解I'下，加入节点i后的总空间是否真的不超过j（即j'_real + PS(i, I')≤j）。在所有满足条件的j'中，取m(i+1, j') + PE(i, I')的最大值，记为m'(i, j)。
最终决策：m(i, j)的值就是不选i（继承m(i+1, j)）和选择i（m'(i, j)）两者中的最大值。公式如下：
```
m(i, j) = max{ m(i+1, j), m'(i, j) }
```
其中，m'(i, j) = max_over_j'{ m(i+1, j') + PE(i, I_{j'}) }，且满足j'_real + PS(i, I_{j'}) ≤ j。

3.2 算法实现细节与挑战

这个DP算法听起来清晰，但实现起来有几个难点：

状态I的存储与传递：m(i+1, j')不仅是一个数值，还关联着一个具体的选择方案I'。我们需要在递推过程中，为每个(i, j)状态同时存储最大收益值和达到该收益的选择向量。这显著增加了空间复杂度。
收益PE(i, I')的动态计算：每次计算PE(i, I')都需要根据当前的I'去查询和累加ERM矩阵中相关的行和列。这是一个O(n)的操作，如果嵌套在DP的双重循环里，会使整体复杂度达到O(n^3 * C)，对于大规模问题难以承受。
空间PS(i, I')的动态计算：同上，计算PS(i, I')也需要O(n)的查询。

性能优化技巧：

预计算与增量更新：不能每次都从头计算PE和PS。可以利用ERM和SRM矩阵的特性。注意到PE(i, I') = PE(i, ∅) - ∑_{k in I'} (ERM[i][k] + ERM[k][i])。其中PE(i, ∅)是节点i单独放入SPM的收益（可预计算）。因此，如果我们维护一个数组delta_E[i]，记录当前选择集I'对节点i的收益影响总和，那么当I'增加一个节点k时，可以快速更新所有其他节点i的delta_E[i] -= (ERM[i][k] + ERM[k][i])。PS的计算同理。这样，更新操作是O(n)，而不是每次计算都是O(n)。
剪枝：由于PS(i, I')总是大于等于S(i)，如果S(i) > j，那么节点i在当前容量j下根本不可能被选中，可以直接跳过。
近似算法：对于节点数很多（n > 100）的复杂程序，精确DP可能仍然太慢。可以考虑启发式方法，如先忽略关系影响用经典背包算法得到一个初始解，然后基于这个解局部调整；或者使用元启发式算法（如遗传算法、模拟退火）来搜索近似最优解。

注意事项：动态规划表格的容量维度j的粒度选择很重要。如果以字节为单位，j的范围可能很大（例如8KB=8192），导致表格巨大。实践中，通常会将节点大小和SPM容量按某个单位（如4字节、16字节）进行对齐和量化，以减少状态数，牺牲一点精度来换取速度和内存的可行性。

4. 实验验证与结果分析

理论再完美，也需要实验的检验。论文搭建了一个基于SystemC的硬件仿真平台，对几个典型的嵌入式基准程序（Dijkstra最短路径、JPEG编码、MP3解码、冒泡排序、CRC校验）进行了测试。

实验设置关键点：

硬件模型：定义了SPM和SDRAM的具体能耗参数（如表1所示），包括读写能量、激活/预充电能量、模式切换能量等。这些参数通常通过芯片数据手册或电路级仿真（如CACTI工具）获得。
对比基线：
1. 无SPM方案：所有代码数据均在片外SDRAM运行。
2. 传统SPM优化方案：使用不考虑关系开销的经典背包算法进行分配。
SPM大小：论文重点考察了8KB这一典型配置，这在许多微控制器（如ARM Cortex-M系列）中是合理的片上SRAM大小。

核心结果解读（参照表3）：

节能效果显著：与传统方案相比，本文方法平均降低了19.5%的能耗，最高在MP3解码 benchmark 中降低了58.6%。这直观地证明了忽略关系开销的传统方法会做出次优的、有时甚至是“亏本”的分配决策。例如，它可能把两个频繁相互调用的热点函数都搬进SPM，却没想到因此引入了大量的长分支开销，净收益很低。而本文方法会识别出这种“高耦合”的节点对，可能只选择其中一个，或者都不选，转而选择其他收益更净的节点。
性能无损甚至提升：优化目标是能量，但实验结果也显示执行周期数（性能）平均提升了28.5%。这是因为减少了对慢速SDRAM的访问次数，尽管增加了少量指令，但整体访存延迟下降了。这实现了“能效”（Energy Efficiency）的提升，即用更少的能量完成相同的任务。
MP3案例的深度分析：MP3解码程序表现出最大的优化收益（58.6%）。这很可能是因为其内部存在多个紧密耦合的、高频执行的小型循环或函数（如反量化、哈夫曼解码、IMDCT变换）。传统方法将这些热点全部塞进SPM，导致了密集的、开销巨大的长分支网络。本文方法通过关系矩阵识别出这些“高开销关系”，可能选择了将这些热点合并成更大的、内部调用使用短分支的超级块后再放入SPM，或者放弃了部分相互调用频繁的热点，从而大幅削减了LBIS开销。

对工程实践的启示：

“热点”不等于“必选”：在SPM分配中，访问频率最高的代码块不一定是最优选择，必须结合其调用上下文综合评估。
代码布局（Code Layout）的重要性：本文方法本质上是选择一组节点并决定其位置（SPM或SDRAM）。这启发我们，在编译链接阶段，可以通过优化代码布局，让高频相互调用的函数在地址空间上尽量靠近，从而减少甚至避免长分支的产生，这能与SPM分配协同优化。
工具链支持的必要性：这套方法需要精细的程序剖析（Profiling）来获取节点执行次数、构建ECFG，以及后续的二进制重写（插入LBIS）。这必须集成到编译工具链（如LLVM/ GCC的后端）中才能实现自动化，是学术成果走向工业应用的关键。

5. 方案局限性与未来扩展

尽管该方法取得了显著效果，但在实际应用中仍需考虑其局限性和扩展方向：

静态分配的局限：本文研究的是静态（编译时）SPM分配。对于动态行为复杂、输入数据相关性强的大型程序，运行时热点可能变化。动态（运行时）SPM管理技术（如根据阶段切换SPM内容）是研究热点。本文方法可以作为一个强大的静态分析基础，为动态管理器提供高质量的初始分配方案或候选集。
多级存储层次：现代嵌入式SoC可能包含多级Cache和多块SPM。如何协同优化数据在L1 Cache、L2 Cache、SPM和主存之间的分布，形成一个全局最优解，是更复杂的问题。本文的“关系开销”思想可以扩展到多级层次中，建模数据在不同层级间移动的迁移成本。
与编译器优化的交互：本文假设代码是固定的。但实际上，编译器会进行各种优化（如函数内联、循环展开），这些优化会彻底改变ECFG的结构和节点间的调用关系。理想的框架应该与编译器协同工作，在中间表示（IR）层面就进行SPM分配的评估与指导，形成“优化-评估-再优化”的循环。
开销模型的精确性：能量关系矩阵ERM依赖于精确的硬件能耗模型。在实际芯片中，能耗与访问模式、数据模式、工艺角、温度等都有关联。使用一个固定的、简化的模型可能会引入误差。可以采用更精细的周期精确模拟器，或使用机器学习方法从实际芯片测量数据中学习出一个开销预测模型。

6. 总结与工程落地思考

回顾整个方案，其核心贡献在于将嵌入式系统底层硬件的约束（RISC寻址限制）与软件层面的优化（SPM分配）通过严谨的数学模型（ECFG、关系矩阵、改进背包问题）联系起来，并给出了高效的动态规划求解方法。它纠正了传统优化中一个“想当然”的误区：搬移热点必然省钱。

对于一名嵌入式软件工程师或编译器开发者而言，这项工作的启示在于：做系统优化，必须有全局观和成本意识。任何一个优化决策都可能带来意想不到的副作用。在动手之前，尽可能建立量化的模型去评估“收益”和“成本”。

在实际项目中，完整实现这套流程可能较重，但我们可以吸收其思想：

在手动管理SPM时，有意识地去检查热点函数之间的调用距离，如果它们频繁交叉调用且地址相距甚远，考虑调整链接脚本将它们放在相邻区域，或者评估将它们作为一组整体放入SPM的性价比。
在开发性能/功耗分析脚本时，不仅统计函数/基本块的访问次数，也统计跨一定地址范围的跳转指令数量，将其作为一个重要的优化指标。
在选择编译器优化选项时，关注那些会影响代码布局和分支生成的选项（如-freorder-blocks-and-partition），它们可能间接影响SPM优化的效果。

最终，这项研究指向了一个趋势：嵌入式系统的软硬件协同设计需要越来越精细的建模和更紧密的耦合。SPM不再仅仅是一块快速的存储区，而是需要与处理器架构、指令集、编译工具链共同设计的、可编程的重要资源。掌握像本文这样从问题本质出发进行建模和优化的方法，是应对未来更复杂、更苛刻的嵌入式设计挑战的关键能力。