这一篇在干嘛？
论文出自 ACM Transactions on Embedded Computing Systems 13(2s), Article 72（2014），作者 Anup Das、Akash Kumar、Bharadwaj Veeravalli（新加坡国立大学）。核心问题是：在异构多核片上系统（MPSoC）上，某个处理核发生永久故障（permanent fault）之后，任务该怎么重新摆放，才能在仍然满足应用吞吐量（throughput）要求的前提下把能耗压到最低？ 方法思路是两段式——设计阶段（offline）为「所有可能的故障场景」各算好一张最优映射表并编码存储，运行阶段一旦检测到故障就查表解码、执行任务迁移；映射生成用梯度式启发式搜索（gradient-based heuristic）同时优化计算能耗与通信能耗，并引入布图规划感知（floorplan-aware）的核选择；调度层面则采用自定时执行（self-timed execution），只存映射与 firing 顺序而不存完整时刻表。主要结论：相比当时最好的反应式容错技术，总能耗降低 22%，每单位能量吞吐量（throughput per unit energy）提升 30%；设计空间探索时间相对穷举法缩短 100 倍（14 个 actor 的问题从 54 天降到 2 小时以内）；调度的运行时构造时间下降 95%、存储开销下降 92%（10 倍）。
一、背景：多核嵌入式系统的能耗与可靠性为何互相打架
先从一个具体场景进入。你手上的手机要在 30 fps 下解码 1080p 视频。单核跑不动，于是芯片里塞了若干处理单元（PE, Processing Element）——通用处理器 GPP、数字信号处理器 DSP、可重构区域 RA、专用集成电路 ASIC——用片上网络（NoC, Network-on-Chip）以 mesh 拓扑连起来，这就是异构多核片上系统（MPSoC）。TI 的 OMAP、ST 的 NOMADIK、Philips 的 Nexperia 都是这类架构。
现在问题来了。这类芯片上有三个需求天然互相拉扯：
第一，性能。 视频解码有硬指标，每秒必须出这么多帧，少一帧就是卡顿。在流处理语境下，我们把吞吐量的倒数——应用周期（application period）——作为性能指标，它必须小于某个约束值。
第二，能耗。 电池容量是有限的。动态功耗的基本公式后面会展开，这里只需记住一点：动态功耗正比于频率与电压平方的乘积。想省电，最直接的手段就是把电压和频率降下来，这就是动态电压频率调节（DVFS, Dynamic Voltage and Frequency Scaling）。
第三，可靠性。 晶体管尺寸越缩越小、供电电压越压越低、工作频率越提越高，这三件事共同把芯片的失效率推了上去。故障分三类：瞬时故障（transient）、间歇故障（intermittent）、永久故障（permanent）。瞬时故障最常见，靠重执行或检查点（checkpoint）就能恢复；但永久故障意味着那个核物理上废了，上面的任务必须搬到别的核上去，此后再也不能回来。本文关注的正是永久故障。
关键认知：省电和可靠，在本文的语境里不是「DVFS 降频导致软错误率上升」那种关系
很多初学者的直觉是「降频省电 → 时序裕量变小 → 软错误率上升」，那是另一类论文的主题。本文的冲突点在别处：当你为了省电，把任务精心地摆放在若干低频核上，并让负载尽量均衡时，一旦某个核挂掉，幸存核就得接手它的活儿。此时你被迫做两件都费电的事——（a）把故障核上的任务搬到远处的核，通信距离变长、通信能耗上升；（b）为满足吞吐量约束，不得不把幸存核的频率往上抬，而计算能耗大致随频率平方增长。换句话说，你省下来的电，会在故障发生的那一刻以更贵的代价被追回去。
这就引出了本文想解决的核心矛盾：能耗优化不能只在「无故障」那一个场景上做，而必须在「所有可能的故障场景」上一起做。 只优化无故障场景的映射，是最优的；但在故障发生后的漫长余生里（对手机而言可能是两三年），系统跑的是一个临时拼凑的次优映射，长期能耗反而更高。
1.1 主动容错 vs 反应式容错
容错技术分两大流派：
主动容错（proactive fault tolerance）：想办法阻止或推迟故障发生。典型做法是控制芯片温度、均衡老化（aging）压力，让 NBTI（负偏置温度不稳定性）、电迁移这类老化效应慢一点到来，从而延长寿命。
反应式容错（reactive fault tolerance）：承认故障迟早会来，提前准备好故障发生后的应对方案。等故障真的出现了，按预案执行任务迁移。
本文属于后者，且是**设计阶段（design-time）**的反应式容错。为什么强调设计阶段？因为运行阶段的迁移算法必须极简——芯片上一个核刚废掉，系统正处在混乱状态，你没时间跑一个复杂优化。所以正确姿势是：把昂贵的计算全部挪到设计阶段，为每一种故障场景预先算好一张映射表，运行时只做「查表 + 解码 + 迁移」这三件廉价的事。
代价是存储开销。这一点本文用自定时调度巧妙地化解了，后面第六节详述。
二、应用建模：同步数据流图 SDFG
要谈任务怎么放，先得说清楚「任务」长什么样。本文用同步数据流图（SDFG, Synchronous Dataflow Graph）建模流处理应用，这是 Lee 和 Messerschmitt 在 1987 年提出的模型，至今仍是 DSP 与多媒体系统的主流建模工具。
图 1：SDFG 模型示例
SDFG 里有几个基本概念：
- Actor（执行体）：图的顶点，代表一个计算函数（比如「做一次 8×8 逆 DCT」）。actor 的一次执行叫做一次 firing（点火）。
- Port（端口）与 Rate（速率）：actor 通过输入端口读 token、通过输出端口写 token。端口速率是常量——每次 firing 产生和消费的 token 数固定不变，这正是「同步」二字的含义，也正是 SDFG 能被静态分析的根本原因。图 1 中 输入速率 3、输出速率 4。
- Channel（通道）：图的边，代表 actor 之间的数据依赖。边上可以带初始 token（图中用圆点表示），用来建模缓冲区大小或流水线初始状态。
- 就绪条件（ready）：一个 actor 只有在「所有输入边上有足够 token」且「所有输出边上有足够缓冲空间」时才能 firing。
形式化定义如下。
定义 1（Actor） actor 是一个四元组 ： 是输入端口集合， 是输出端口集合，两者不相交； 是执行周期集合 ，表示 在第 类核上执行所需的 CPU 周期数——异构性就体现在这里，同一个 actor 在不同类型的核上耗时不同； 是状态空间（程序与数据内存大小），后面算迁移开销时会用到。同构系统里 ，所有核上执行周期相同。
定义 2（SDFG） 有向图 ， 是 actor 的有限集合， 是通道集合。通道 的源是 的输出端口、目的是 的输入端口。
2.1 重复向量与吞吐量
定义 3（重复向量 Repetition Vector） 是一个向量，指明 SDFG 完成**一次迭代（iteration）**时集合 中每个 actor 各执行多少次。一次迭代定义为「使图回到原始状态的最小非零执行序列」。图 1 的例子中 。
定义 4（应用周期 Application Period） 是 SDFG 平均完成一次迭代所需的时间。吞吐量就是它的倒数，这是本文使用的性能指标。
重复向量为什么重要？因为不同 actor 的 firing 频率不一样（图 1 里 每迭代跑 2 次， 只跑 1 次），所以计算总能耗时必须按各自的执行次数加权——后面公式 (7) 里的 就是干这个的。
从 传到 的数据量为：
其中 是一个 token 的比特数。 与 之间双向总通信量是 。这个量会直接乘进通信能耗公式，是后面映射优化的关键输入。
2.2 缓冲区怎么建模
SDFG 用一个巧妙的技巧建模缓冲区：把缓冲区大小表示成一条带初始 token 的反向边。图 1(b) 中， 到 的通道缓冲大小为 2，就画一条从 回到 的边，上面放 2 个 token。 要执行，必须先从这条反向边消费 1 个 token（预留 1 个输出缓冲位）； 执行完，向反向边释放 2 个 token（腾出 2 个缓冲位）。
注意时序细节：输出缓冲在 actor 开始执行时就被占用，输入 token 空间只在 firing 结束时才释放。这个设计保证了 actor 执行的原子性——不会出现「读到一半被别人改了」的情况。
2.3 自定时执行与两个引理
SDFG 在多核上的调度，最常用的是自定时策略（self-timed execution）：设计阶段用最坏情况执行时间（WCET）算出 actor 在哪个核上、以什么顺序执行；然后把具体时刻信息丢掉，只保留「分配关系」和「执行顺序」；运行时，actor 就按设计阶段定好的顺序 firing，实际耗时随运行时情况浮动。
这个做法的价值在于鲁棒性：完全静态的时刻表一旦遇到实际执行时间和 WCET 不一致就全盘崩溃，而自定时调度天然吸收这种动态性。本文第六条大节正是靠它把存储开销压下来的。两个支撑性引理：
引理 1 对于一致且强连通的 SDFG，自定时执行由一个瞬态阶段（transient phase）后接一个周期性稳态阶段（steady-state phase）组成。
引理 2 对于一致且强连通的 SDFG，actor 的吞吐量由其在稳态阶段中单位时间内的平均 firing 次数给出。
这两个引理给了本文一个极大的便利：只需要优化稳态阶段每个迭代的能耗，瞬态阶段可以忽略。因为对视频解码这类应用，稳态迭代次数 是个天文数字（每一帧就是一次迭代），瞬态那点能耗完全不重要。本文后面提到的「计算能耗」「通信能耗」如无特别说明，都指稳态阶段每迭代的能耗。
顺带一提
本文虽以 SDFG 为主，但明确说明所提技术对 SDFG 和 DAG（有向无环图）都适用，需要区别对待的地方文中会单独标出。所以如果你面对的是非流式的 DAG 任务图，这套思路依然可用。
三、体系结构建模与布图规划：为什么核的「坐标」很重要
(a) mesh 拓扑的多核架构
(b) 对应的布图规划（floorplan）
(c) 布图无关映射 vs 布图感知映射的通信能耗对比
图 2：概念性架构模型
架构被建模为图 ： 的节点是处理核， 的边是核间通信通道。每个核 是一个二元组 ，其中 是核的异构类型（homogeneity/heterogeneity type）， 是该核支持的频率档位集合。这两个参数就是后面优化的决策变量。
3.1 布图规划感知：一个被长期忽略的能量杠杆
图 2(c) 展示了本文的一个小而实在的贡献：此前所有反应式容错研究都只考虑核的「类型」，不考虑核的「坐标」。这为什么会出问题？
看图 2(c) 的例子：actor 需要 0 型核，actor 需要 1 型核。图 2(b) 的布图里，0 型核占据一个区域、1 型核占据另一个区域，同区域内核同构。
- 布图无关（floorplan-unaware）映射：随便挑了一个 0 型核 和一个 1 型核 ，两者在 mesh 上相距 4 跳（hop）。
- 布图感知（floorplan-aware）映射：挑了 和 ，相距只有 2 跳。
在 NoC 上，每多跳一跳就多经过一个路由器和一段链路，能耗线性增加。同样的应用、同样的核类型选择，仅仅因为挑了不同坐标的同型核，通信能耗就翻了倍。 而且随着故障增多、可选核越来越少，「挑哪个同型核」的自由度越来越小，这个效应会被放大。
本文在映射生成时把核的实际坐标纳入考虑，算是补上了这个漏洞。这个细节的工程启发很直接：做多核映射时，别只把核当作「带类型的槽位」，它的物理位置本身就是一个优化维度。
四、能耗模型：三部分加总
本文把总能耗拆成三块：计算能耗、通信能耗、迁移能耗。下面逐一展开。
4.1 计算能耗：为什么是频率的平方
电路总功率 = 动态功率 + 泄漏功率。本文聚焦动态功率（明确说明与各种泄漏功耗优化技术正交，可叠加使用）。动态功耗：
其中 是活动因子（activity factor）， 是工作频率， 是有效负载电容， 是供电电压。
频率与供电电压的关系由 α-Sakurai 定律给出：
其中 是常数， 是建模速度饱和的工艺相关参数， 是 CMOS 阈值电压。论文进一步引用 Meijer 与 de Gyvez 的结论：在 65nm 低功耗 CMOS 工艺下，频率随供电电压近似线性变化，于是：
现在做一次关键推导。actor 在核 上以频率 运行的动态能耗是「功率 × 时间 × 执行次数」：
而执行时间可以写成执行周期除以频率，即 。代入上式，并用 把电压项换成频率项，得到：