便签存储器上的最优数据分配：让编译器替你决定变量放哪

这一篇在干嘛？

论文出自 ACM TECS 2002（Avissar / Barua / Stewart，马里兰大学），题为 An Optimal Memory Allocation Scheme for Scratch-Pad-Based Embedded Systems。它解决的是一类非常常见却少有人系统研究的问题：低端 MCU / DSP 芯片上没有缓存，片内 SRAM（便签存储器，Scratch-Pad Memory, SPM）、片内 DRAM、片外 DRAM、EEPROM 各自占据一段独立地址，软件必须自己决定每个变量放哪。作者把这个”放哪”的问题建模成 0/1 整数线性规划（0/1 Integer Linear Program），用商业求解器一次解出全局最优，并且第一次把程序栈拆散分布到多个存储体。在 Motorola M-Core 上的八个基准程序显示：SRAM 只给到数据总量 20% 时，分布式栈比统一栈快 44.2%，而线性规划比朴素贪心又快 11.8%；相对于全部丢进慢速 DRAM，总体运行时间下降 56%。

一、先问一个更根本的问题：为什么这些芯片没有缓存？

学嵌入式的人大多是从”计算机组成原理”那套体系走过来的：寄存器 → L1 → L2 → L3 → 主存 → 磁盘，一层层由**硬件缓存（cache）**自动管理，程序员几乎不用操心。于是第一次接触 STM32、MSP430、8051 这类芯片时，很多人会下意识地问：这玩意的 cache 在哪？

答案是：没有。

这不是厂商偷工减料，而是三个非常硬的约束共同导致的：

1. 面积与成本。 缓存不是只有数据存储阵列，还有标签（tag）阵列、比较器、状态机、替换逻辑。同样容量的便签存储器（SPM）相比缓存，面积小 34%（Banakar 等人 2002 年的实测对比）。在小批量、单价敏感、封装引脚都按分钱算的 MCU 上，这 34% 直接换算成芯片成本。

2. 功耗。 缓存每一次访问都要做标签比对，即使命中也要付出这份能量开销。同样容量下 SPM 的功耗比缓存低 40%。对靠纽扣电池工作五年、或者靠能量采集供电的节点来说，这是生死线。

3. 实时性。 这才是最致命的一条。缓存的行为是概率性的：命中就是几周期，缺失就是几十上百周期，而且缺失与否取决于历史访问序列。要给出最坏执行时间（Worst-Case Execution Time, WCET）的上界，你就必须能证明”这条指令这次一定命中”，这在有缓存的系统里极其困难，通常只能保守地假设全部缺失，于是算出来的 WCET 松得没法用。SPM 没有命中/缺失的概念——你放进去，就一定在那里，访问延迟是确定值。对硬实时系统而言，这个确定性比平均性能值钱得多。

Banakar 等人还测了一件更反直觉的事：即使用最简单的背包（knapsack）算法来管理 SPM，SPM 方案的运行周期数仍比同容量缓存好 18%。也就是说，即便在”性能至上”的高端场景，缓存也没有体现出优势。这基本宣告了在无缓存路线上继续深耕的合理性。

于是这类芯片的存储长这样：

一小块片内 SRAM（快、贵、小）
可能有一块片内 DRAM（比 SRAM 慢，比片外快）
一大块片外 DRAM（慢、便宜、大）
一块 ROM / EEPROM 存程序和常量

它们不是”多级层次结构”，而是地址空间里几段互不相交的区域。 没有谁自动把数据从慢的搬到快的。搬不搬、搬什么，全是软件的事。

图 1：整篇论文的方法流程图。 左边输入应用程序，经过profiling（剖析）得到每个变量的读写次数，再结合目标芯片上各存储体的”容量 + 延迟”参数，一起喂给编译器的分配分析模块。该模块把问题建成 0/1 整数线性规划并用求解器解出最优分配方案，最后把方案交给链接器（linker），由链接器插入汇编指示符把变量落到指定地址上。粗箭头是主流程，细箭头是辅助数据。

二、SPM 和缓存的本质区别：到底是谁在管

这一节值得单独讲，因为很多初学者把 SPM 理解成”手动挡的缓存”，这个类比对了一半，但错的地方恰恰是关键。

对比维度	硬件缓存 Cache	便签存储器 SPM
管理者	硬件（标签比较 + 替换算法）	软件（编译器或程序员）
地址空间	统一编址，一套地址	分段编址，各存储体占不同地址区间
访问延迟	不确定（命中快，缺失慢）	确定（在哪个体上就是哪个延迟）
数据是否重复	是（缓存里的副本 + 主存里的正本）	否（只有一份正本）
时机	运行时动态决定	编译时静态决定（本方案）
额外面积	标签阵列 + 比较器 + 控制逻辑	几乎只有存储阵列
WCET 分析	困难，通常极度保守	直接，延迟是常数

一句话概括：缓存是硬件在运行时猜你会用什么；SPM 是软件在编译时就规定好什么放哪。

由此带来的直接后果是——“放哪”这个决定，之前一直由程序员手工承担。

工业界常见做法是：在链接脚本（linker script）里手写几个段（section），然后用 __attribute__((section(".fast_data"))) 之类的语法把关键变量钉进去。这个做法有三个明显毛病：

费人力。 程序一大，变量成百上千，靠人脑判断”哪个变量热”完全不现实。
不可移植。 换一颗芯片，SRAM 大小从 8 KB 变成 4 KB，原来那套手工标注全部作废，得重来一遍。
大概率不是最优。 人只能凭直觉挑几个”看起来重要”的大数组，但真正的热点往往是那些小而频繁的标量——比如一个循环计数器、一个累加和，它们可能只有 4 字节，却被访问了几百万次。

论文想做的，就是把这三件事从人手里拿走，交给编译器，并且保证交出去之后结果不会变差（因为有最优性保证）。

三、“哪个变量放哪”为什么是个组合优化问题

先看论文给出的例子。

图 2(a)：示例源代码。 两个字节数组 A[100]（a）和 B[1000]，作为参数传给过程 foo()，在过程体内以形参 x[]、y[] 访问。目标芯片有 1 KB 快速片内 SRAM 和 8 KB 较慢的片外 DRAM。

图 2(b)：把 A[] 放进 SRAM 的分配方案。 图中浅色部分表示被分配到 SRAM 的数据。

图 2(c) - 上：分配方案对照示意（深色为较慢存储体）。

图 2(c)：把 B[] 放进 SRAM 的分配方案。 浅色部分表示被分配到 SRAM 的数据。

这两个数组单独看都能塞进 1 KB SRAM，但同时放就超了（100 + 1000 = 1100 字节 > 1024 字节）。所以必须二选一。选谁？

答案取决于运行时行为：

如果 while 循环实际迭代次数多（频繁访问 x[] 即 A[]），那应该放 A[]——对应图 2(b)。
如果 for 循环迭代次数多（频繁访问 y[] 即 B[]），那应该放 B[]——对应图 2(c)。

注意这里的坑：你没法在编译期知道答案。 循环上界往往是运行时的输入数据决定的；控制流本身也是数据相关的。静态预测（比如”内层循环执行 10 次”这类启发式）在真实程序上误差大得离谱。

这篇论文的做法是用 profiling 拿真实数据：拿一组有代表性的输入跑一遍，记录每个变量被读了多少次、写了多少次。这比静态预测准得多。

现在把问题一般化。假设有 $G$ 个全局变量、 $U$ 个存储体。每个变量都要选一个体，那么可能的分配方案总数是：

# 方案 = U^{G}

举个直观的数字： $G = 50$ 个变量、 $U = 3$ 个存储体，方案数是 $3^{50} \approx 7.2 \times 1 0^{23}$ 。宇宙中的原子总数也就 $1 0^{80}$ 量级，这个数字虽然比它小，但已经彻底超出任何穷举能力。

这就是所谓组合爆炸。而这个问题本身是 NP-完全（NP-complete） 的——你可以把它看成一个带容量的广义指派问题。NP-完全的意思是：不要指望找到一个”对所有输入都很快”的精确算法。

那怎么办？两条路：

启发式 / 贪心：快，但不保证最优。
精确求解：用整数规划求解器，理论上最坏情况指数时间，但实践中几千个变量往往几十秒内就解完（论文里说从没超过一分钟，通常几秒）。

论文选了后者，并且因此拿到了一个宝贵的性质：在”静态分配”这一类方法里，这个解是可证明最优的。换句话说，任何程序员手写标注、任何未来的编译器算法，都只能和它打平或更差。

顺带说一个论文里的工程细节：怎么知道一次内存访问访问的是哪个变量？

要静态地回答，需要过程间指针分析（interprocedural pointer analysis），既慢又可能给出”不确定”的结果（比如 foo() 被调用两次，两次传的数组不同）。论文绕开了这条路：在 profile 运行时做地址检查——每次访问的地址，去查一张”变量地址区间表”，落在哪个区间就是哪个变量。这给出的是精确统计，而不是指针分析给出的保守估计。

四、0/1 整数线性规划：把”放哪”写成求解器能吃的公式

这一节是全文的核心。我们一步步把自然语言问题翻译成数学。

4.1 先定义符号

符号	含义
$U$	异构存储体的数量
$T_{r j}$	读存储体 $j$ 的延迟（周期数）
$T_{w j}$	写存储体 $j$ 的延迟（周期数）
$M_{j}$	存储体 $j$ 的容量（字节）
$G$	全局变量个数
$v_{i}$	第 $i$ 个全局变量
$N_{r} (v_{i})$	$v_{i}$ 被读的次数（来自 profiling）
$N_{w} (v_{i})$	$v_{i}$ 被写的次数（来自 profiling）
$S (v_{i})$	$v_{i}$ 的大小（字节）

4.2 决策变量：一个变量只能落在一个体上

对每个 (存储体 $j$ , 变量 $v_{i}$ ) 组合，定义一个只能取 0 或 1 的整数变量：

I_{j} (v_{i}) = {1, 0, 若变量 v_{i} 被分配到存储体 j 否则

一共 $U \times G$ 个这样的 0/1 变量。这就是”0/1 整数”这个名字的由来——变量不是连续的实数，只能取 0 或 1。

4.3 目标函数：最小化总访存时间

要最小化的目标，是整个程序所有访存操作花掉的周期数总和：

min j = 1 \sum U i = 1 \sum G I_{j} (v_{i}) [T_{r j} N_{r} (v_{i}) + T_{w j} N_{w} (v_{i})]

读法是这样的：

内层括号 $T_{r j} N_{r} (v_{i}) + T_{w j} N_{w} (v_{i})$ —— 假如把 $v_{i}$ 放到体 $j$ ，访问它要花多少周期。
乘上 $I_{j} (v_{i})$ —— 如果真的放在 $j$ （值为 1），这一项就计入；否则（值为 0）整项归零。
对 $i$ 求和 —— 累加所有变量，得到”落在体 $j$ 上的那些变量”的访问总时间。
对 $j$ 求和 —— 累加所有存储体，得到全程序访存总时间。

注意这个式子关于 $I_{j} (v_{i})$ 是线性的（只有一次乘法，乘的是常数）。这至关重要——线性目标 + 线性约束 = 可以用成熟的整数规划求解器（论文用的是 Matlab）高效求解。

4.4 约束一：互斥约束（一个变量只能放一处）

j = 1 \sum U I_{j} (v_{i}) = 1 (\forall i \in [1, G])

对每个变量 $v_{i}$ ，它在所有存储体上的 $I_{j} (v_{i})$ 加起来必须恰好等于 1——也就是有且只有一处。不能放两处（重复），不能一处都不放（丢数据）。

4.5 约束二：容量约束（放进去的不能超）

i = 1 \sum G I_{j} (v_{i}) \cdot S (v_{i}) \leq M_{j} (\forall j \in [1, U])

对每个存储体 $j$ ，所有被分配到它上面的变量大小之和，不能超过它的容量 $M_{j}$ 。

4.6 手算一个小例子：贪心是怎么输的

目标函数 + 上面两条约束，就构成了完整的优化问题。为了看清”为什么非得用求解器”，我们手算一个 3 变量、2 存储体的例子。

场景设定：

存储体 1 = SRAM，容量 $M_{1} = 250$ 字节，读写延迟均为 1 周期
存储体 2 = DRAM，容量 8 KB（充裕），读写延迟均为 10 周期
三个全局变量，profiling 得到的访问次数与大小如下：

变量	大小 $S$	总访问次数 $N$ （读+写）	放 DRAM 的代价	放 SRAM 的代价	收益
$v_{1}$	60 B	1,000	$1000 \times 10 = 10, 000$	$1000 \times 1 = 1, 000$	9,000
$v_{2}$	100 B	5,000	$5000 \times 10 = 50, 000$	$5000 \times 1 = 5, 000$	45,000
$v_{3}$	150 B	4,000	$4000 \times 10 = 40, 000$	$4000 \times 1 = 4, 000$	36,000

全部放 DRAM 的基线总时间： $10, 000 + 50, 000 + 40, 000 = 100, 000$ 周期。

贪心策略（按大小从小到大塞）——这是非常符合人类直觉的做法：“先塞小的，多塞几个”：

$v_{1}$ （60 B）→ SRAM，剩余 190 B
$v_{2}$ （100 B）→ SRAM，剩余 90 B
$v_{3}$ （150 B）→ 放不下了，丢 DRAM

结果：总时间 $= 1, 000 + 5, 000 + 40, 000 = 46, 000$ 周期。相比基线省了 54,000。

最优解（枚举一下，一共只有 $2^{3} = 8$ 种）：

方案	占用	是否可行	总时间
全 DRAM	0 B	✓	100,000
${v_{1}}$	60 B	✓	91,000
${v_{2}}$	100 B	✓	55,000
${v_{3}}$	150 B	✓	66,000
${v_{1}, v_{2}}$	160 B	✓	46,000 ← 贪心选中
${v_{1}, v_{3}}$	210 B	✓	51,000
${v_{2}, v_{3}}$	250 B	✓	19,000 ← 最优
${v_{1}, v_{2}, v_{3}}$	310 B	✗ 超容量	—

最优方案是 ${v_{2}, v_{3}}$ ，总时间 19,000 周期。

对比：

贪心：46,000 周期
最优：19,000 周期
贪心比最优慢 2.4 倍（论文里线性规划相对贪心的平均优势是 11.8% —— 平均来看差距没这么夸张，但个别程序上这种量级的差距是存在的）

贪心错在哪？ 它用”大小”做排序键，但真正该排序的键是收益密度，也就是”每字节能省多少周期”：

收益密度 (v_{i}) = \frac{N ( v _{i} ) \times ( T _{slow} - T _{fast} )}{S ( v _{i} )}

算一下：

$v_{1}$ ： $9000/60 = 150$ 周期/字节
$v_{2}$ ： $45000/100 = 450$ 周期/字节
$v_{3}$ ： $36000/150 = 240$ 周期/字节

密度排序是 $v_{2} > v_{3} > v_{1}$ ，贪心按大小排序得到 $v_{1} > v_{2} > v_{3}$ ——恰好把最没价值的 $v_{1}$ 排在了第一位，而它占掉的 60 字节刚好卡死了后续组合。

这里有个更深的水

就算你改成”按收益密度贪心”，依然不是最优。这是背包问题的经典结论：分数背包可以贪心，0/1 背包不行。因为物品不能切分，密度最高的东西可能刚好留下一个填不满的空隙。真正的最优必须靠搜索（整数规划求解器内部就是分支限界 + 割平面）。这也正是这篇论文坚持用 ILP 而非更花哨的启发式的理由。

4.7 这个模型什么时候不成立

论文很诚实地指出了边界。目标函数假设每个周期最多发起一次访存。这在低端 MCU 和多数 VLIW（超长指令字）架构上成立。

但高端 VLIW 允许一周期发多次访存，此时这些访存的延迟会重叠，总延迟应该是同一周期内各访存延迟的最大值，而不是和。麻烦来了：

max (x, y) 不是线性函数

一旦引入 $max$ ，目标函数就不再线性，整数线性规划那套工具就用不上了，只能退回启发式。这部分论文明确说”本工作未评估”。

description	在没有缓存的嵌入式芯片上，把全局变量和栈分配到哪一个存储体，是一个组合优化问题。这篇论文用 0/1 整数线性规划给出可证明最优的静态解，并首次把栈拆开分布到多个存储体，实测运行时间降低 44.2%。
tags	acm-旗舰期刊, 便签存储器最优分配

嵌入式开发之路

探索

便签存储器上的最优数据分配：让编译器替你决定变量放哪

一、先问一个更根本的问题：为什么这些芯片没有缓存？

二、SPM 和缓存的本质区别：到底是谁在管

三、“哪个变量放哪”为什么是个组合优化问题

四、0/1 整数线性规划：把”放哪”写成求解器能吃的公式

4.1 先定义符号

4.2 决策变量：一个变量只能落在一个体上

4.3 目标函数：最小化总访存时间

4.4 约束一：互斥约束（一个变量只能放一处）

4.5 约束二：容量约束（放进去的不能超）

4.6 手算一个小例子：贪心是怎么输的

4.7 这个模型什么时候不成立

五、栈变量：难度陡增，以及”分布式栈”这个点子