把关键循环搬到硬件上：能省多少电、快多少倍？

这一篇在干嘛？

论文出自 ACM TECS 2004（Stitt / Vahid / Nematbakhsh，加州大学河滨分校），题为 Energy Savings and Speedups from Partitioning Critical Software Loops to Hardware in Embedded Systems。它做的是软硬件划分（hardware/software partitioning）中一个非常具体也非常实用的分支：不去搜索成千上万种划分方案，而是先用 profiling 找出那几个”吃掉大部分执行时间”的关键循环（critical loop），只把这几个循环搬进硬件（片上可重构逻辑 CSL 或 ASIC 定制逻辑），然后实测能快多少、省多少电。核心结论：基准程序平均把 80% 的执行时间花在仅 3% 的代码上（约 200 字节）；搬走这些循环后平均加速 3 到 5 倍、平均省电 35% 到 70%，而硬件代价只有 5000 到 10000 门。

一、软硬件划分到底在”划”什么

1.1 一句话定义

软硬件划分：把一个应用拆成两部分——一部分继续跑在微处理器（microprocessor）上当软件，另一部分做成定制硬件（协处理器 / 可重构逻辑 / 定制指令），两者协同完成同一个任务。

初学者最容易误解的一点是：这不是”用 FPGA 实现一个 CPU”那种宏大工程，而是非常局部的手术——可能只是把程序里一个 20 字节的内层循环换成一块几百门的电路。

1.2 两类划分：多进程 vs 单程序

论文明确区分了两种不同问题：

多进程划分：应用由许多并发进程构成，把不同进程分配到不同处理单元。这是 90 年代软硬件协同设计的主流研究对象。
单程序划分：就一个顺序执行的程序，把其中某些函数/循环搬进定制硬件。

本文做的是后者，而且特别强调一个前提条件：嵌入式系统里的程序往往是”出厂即固定”的，一辈子不变。这带来一个巨大的自由度——你可以为一个特定循环定制一块电路，而不用担心”下次程序变了这块电路就不适用了”。通用计算机不敢这么干，嵌入式系统敢。

1.3 搬过去的三种落地形态

论文主要讨论后面两种，但对初学者来说，把三种一起看会更清楚：

形态	做法	粒度	典型代价
定制指令（custom instruction）	在处理器指令集里加一条专用指令，执行时走专用数据通路	极细（一条表达式）	需改处理器核，工具链支持有限
协处理器（coprocessor）	挂一个从处理器，处理器发命令给它，它算完返回结果	中（一个函数/循环）	需总线接口、握手逻辑
片上可重构逻辑 / 定制逻辑（CSL / ASIC）	把循环直接综合成一块专用电路，放在芯片上	中到粗（若干循环）	面积（门数）、可能需共享内存

论文用的术语是 CSL（Configurable System Logic，可配置系统逻辑）。这是一个比 FPGA / CPLD / PLA 更泛化的说法——因为不同厂商的片上可编程结构技术路线不同，用 CSL 统称。

1.4 为什么硬件会更快：细粒度并行

处理器是指令流机器：一条指令做一个小动作，一个周期（或几个周期）走一条。硬件电路是空间机器：只要你有足够的门，所有可以同时算的东西就同时算。

论文给的这个例子很传神：

if (a + b < c + d)
    x = y + z;
else if (a * b > e - f)
    y = x + z * 5;

在 8 位单片机上，这段代码可能要几十个周期：a+b、c+d、比较、a*b、e-f、比较、赋值、乘法 z*5……一条条排着来。

而在定制硬件里，a+b 和 c+d 可以用两个加法器同时算，a*b 和 e-f 也可以同时算，比较用一个比较器，最后用一个多路选择器根据条件挑结果。整个块可以一个周期出结果。

这就是所谓的细粒度并行（fine-grained parallelism）——不是多核那种”任务级并行”，而是”表达式内部的并行”。

二、80/20 法则：先找到那几个该搬的循环

2.1 Amdahl 定律给出的上限

在动手之前，先要回答一个问题：值得搬哪个循环？

答案是 Amdahl 定律（Amdahl’s Law）。如果某部分占总执行时间的比例为 $f$ ，把这部分加速到瞬间完成（时间为 0），那么整体加速比的上限是：

S_{m a x} = \frac{1}{1 - f}

论文用的等价写法更直观（把总时间记成 100）：

S_{m a x} = \frac{100}{100 - f %}

手算两组：

一个循环占 60% 时间： $S_{m a x} = 100/ (100 - 60) = 2.5$
一个循环占 5% 时间： $S_{m a x} = 100/ (100 - 5) = 1.05 \approx 1.1$

结论极其尖锐：把那个占 60% 的循环搬到硬件，最多能快 2.5 倍；而把 8 个各占 5% 的循环全部搬走（工作量可能大十倍），最多也就：

S_{m a x} = \frac{100}{100 - 40} \approx 1.7

搬一个热点，胜过搬一堆温点。 这就是整篇论文方法论的基石：既然收益如此集中，那就根本不需要去搜索成千上万种划分组合——找前两三个循环就够了。

2.2 什么叫”关键循环”

论文的定义很实用：占任务执行时间约 7% 以上的循环，就叫关键循环（critical loop）。

定义里有两个容易忽略的细节：

有时它其实是子程序（函数），不是循环。但那个子程序之所以关键，通常是因为它被循环调用，或者它内部含循环，所以仍用”循环”这个词。极少数情况是因为它在程序各处被频繁调用。
每个基准的关键循环数量通常只有 2 到 4 个。

2.3 怎么找：工具链与实测数据

找关键循环的流程是：

把 C 源码编译成目标架构的二进制（论文用了三种：Intel 8051 八位单片机、MIPS 32 位嵌入式处理器、SimpleScalar 模拟的 MIPS 扩展）
在周期精确的指令集模拟器（instruction-set simulator）上跑，输出指令 trace
写一个工具解析二进制，列出所有循环和子程序的位置
用作者自己开发的 LOOAN 工具读 trace，统计每个循环/子程序的访问次数、迭代次数（含最小/最大/平均）

一个很真实的工程教训

论文提到 LOOAN 生成的 trace 文件有几个 GB 那么大，某些情况下直接撑爆磁盘。这不是理论问题，是实打实的工程障碍。作者的对策是把统计逻辑直接做进模拟器，在运行时累计，而不是事后处理 trace。这个教训到今天依然适用：profiling 的开销和 I/O 往往比算法本身更麻烦。

2.4 实测数据：50-2 法则与 80-3 法则

下表是论文 Table I 的节选（PS = PowerStone、MB = MediaBench、NB = NetBench 三个基准集；Arch 是编译目标；Size 是编译后静态代码大小，单位字节）：

基准	架构	程序大小	L1 大小	L2 大小	L1 占时	L2 占时	L1 理想累积加速	L2 理想累积加速
PS_g3fax	I8051	8,270	24	—	55%	—	2.2	—
PS_crc	I8051	810	58	—	62%	—	2.6	—
PS_brev	I8051	2,406	1,710	—	93%	—	14.3	—
PS_matmul	I8051	836	212	—	85%	—	6.7	—
PS_g3fax	MIPS	4,452	24	—	31%	—	1.4	—
PS_adpcm	MIPS	7,640	88	64	17%	13%	1.2	1.4
PS_crc	MIPS	4,288	68	—	65%	—	2.9	—
PS_des	MIPS	6,116	360	—	52%	—	2.1	—
MB_g721	SS	11,878	31	594	45%	10%	1.8	2.2
MB_adpcm	SS	9,302	153	—	99.9%	—	1000.0	—
MB_pegwit	SS	24,990	62/62/64/31	—	35%/35%/4%/3%	—	1.5 → 3.3 → 3.8 → 4.3	—
NB_dh	SS	21,678	100/77/73	—	40%/18%/17%	—	1.7 → 2.4 → 4.0	—
NB_url	SS	13,526	17	—	80%	—	5.0	—
平均			占程序大小 2%	3%	47%	62%

表底部两行平均数是全文最常被引用的数字：

关键循环 L1 平均只占程序大小的 2%，却吃掉 47% 的执行时间
加上 L2（累计 3% 的代码），吃掉 62%
加上 L3（累计 3% 的代码），吃掉 80%

大家常说的”80-20 法则”（80% 的时间在 20% 的代码里）在这批基准上远远不够夸张。作者幽默地给出了新的说法：

“50-2 法则”：50% 的时间在 2% 的代码里
“80-3 法则”：80% 的时间在 3% 的代码里

换算成绝对量：大约 200 字节的关键代码，吃掉 80% 的执行时间。

看几个极端例子：

MB_adpcm：一个 153 字节的循环占了 99.9% 的时间，理想累积加速 1000 倍。这种程序几乎是为硬件加速而生的。
PS_brev（位反转）：1,710 字节循环占 93%，理想加速 14.3。
NB_url：只要 17 字节的循环就占 80%，理想加速 5.0。

“理想累积加速”这一列要理解清楚：它假设某个循环执行时间为 0，且前面几个循环也已经为 0。所以 L2 那列的 1.4 表示”L1 和 L2 都变成 0 时间”的加速比。这解释了为什么它是”理想”——真实硬件不可能做到 0 时间。

2.5 由此得出的三个推论

大部分加速来自 1 到 3 个极小的循环。 不需要大规模搜索划分空间。
硬件代价可能很小。 只要 2~3 倍加速的话，几百到几千门可能就够了；某些情况下用极少的硬件就能拿到极高加速。
有了这些加速，省电也就顺理成章了。 ——但这句话有陷阱，见下一节。

三、能耗模型：为什么”快”不自动等于”省”

这是初学者最容易踩的坑，也是这篇论文的核心贡献之一。

3.1 基本关系：能量 = 时间 × 功率

E = T \times P

能量（焦耳）= 时间（秒）× 功率（瓦特）。

软硬件划分降低能耗的唯一途径是缩短执行时间。但问题在于——

3.2 陷阱：硬件会把功率顶上去

搬一块定制电路上去，系统在执行时多了一块活跃电路，功率是上升的。所以：

省电的必要条件是：速度提升带来的时间缩短，必须足以抵消功率的上升。

写成式子。设原方案时间 $T_{o}$ 、功率 $P_{o}$ ，新方案时间 $T_{n}$ 、功率 $P_{n}$ ：

\frac{E _{n}}{E _{o}} = \frac{T _{n} \times P _{n}}{T _{o} \times P _{o}} = \frac{1}{S} \times \frac{P _{n}}{P _{o}}

其中 $S = T_{o} / T_{n}$ 是加速比。要省电，需要 $E_{n} / E_{o} < 1$ ，即：

S > \frac{P _{n}}{P _{o}}

加速比必须大于功率上升的倍数，才能省电。

3.3 手算两个例子

例 A：加速明显，省电成功

原方案： $T_{o} = 100$ 单位时间，系统功率 $P_{o} = 1.0$ → $E_{o} = 100$
划分后：软件段 $T_{s w} = 40$ ，该段系统功率 $1.15$ （处理器 + 空闲硬件 + 互连）；硬件段 $T_{h w} = 10$ ，该段系统功率 $1.6$ （空闲处理器 + 硬件 + 互连）
新总时间 $= 40 + 10 = 50$ → 加速比 $S = 100/50 = 2.0$
新总能量 $= 40 \times 1.15 + 10 \times 1.6 = 46 + 16 = 62$

E_{sav} = \frac{100 - 62}{100} = 38%

省了 38%。加速比 2.0 > 功率上升倍数约 1.2，所以成立。

例 B：加速太少，反而费电

同上，但加速比只有 1.1（循环占比低，或者硬件没跑多快）
软件段 $T_{s w} = 88$ ，硬件段 $T_{h w} = 3$ ，总时间 $= 91$ → $S = 100/91 \approx 1.10$
新总能量 $= 88 \times 1.15 + 3 \times 1.6 = 101.2 + 4.8 = 106$

E_{sav} = \frac{100 - 106}{100} = - 6%

亏了 6%。 加速比 1.10 小于功率上升的倍数，于是”更快了但更费电”。

这不是假想——论文 Table III 里 PS_jpeg 在 MIPS 上的能耗节省是 $- 1%$ ，正是这种情形的真实案例。

3.4 论文的能量公式

论文的公式把上面的思想精确化了，而且关键地区分了”谁在干活”时的系统功率：

E = Time_{s w} \times (P_{s w} + 0.125 \times P_{h w} + P_{i}) + Time_{h w} \times (0.85 \times P_{s w} + P_{h w} + P_{i})

逐项说明：

$Time_{s w}$ ：处理器活跃期间的周期数 × 处理器时钟周期
$Time_{h w}$ ：CSL 活跃期间的周期数 × CSL 时钟周期
$P_{s w}$ ：处理器活跃时的功率
$P_{h w}$ ：硬件（CSL）活跃时的功率
$P_{i}$ ：互连（interconnect）和内存的功率——不管谁在干活，这部分都在耗电，论文通过在 Triscend 器件上实测得到
$0.125 \times P_{h w}$ ：处理器干活时，空闲 CSL 仍消耗的功率。论文实测 Triscend 器件得出空闲 CSL 约为活跃时的 12.5%
$0.85 \times P_{s w}$ ：CSL 干活时，空闲处理器仍消耗的功率。论文实测为空闲态约为活跃时的 85%

这两个系数是全文最”接地气”的地方。 它们说明了一个常被忽略的事实：你多加一块硬件上去，即使它闲着也在漏你的电。 而且处理器空转的代价（85%）远比 CSL 空转（12.5%）昂贵——这也解释了为什么让处理器进入低功耗待机状态（下节会讲）很重要。

description	把嵌入式软件里最耗时的几个小循环搬到可重构硬件或定制逻辑上执行，到底值不值？这篇 ACM TECS 论文用 20 个基准程序、四种目标架构给出了实测答案：平均加速 3~5 倍、平均省电 35%~70%，代价只有 5000~10000 门电路。
tags	acm-旗舰期刊, 关键循环软硬件划分

嵌入式开发之路

探索

把关键循环搬到硬件上：能省多少电、快多少倍？

一、软硬件划分到底在”划”什么

1.1 一句话定义

1.2 两类划分：多进程 vs 单程序

1.3 搬过去的三种落地形态

1.4 为什么硬件会更快：细粒度并行

二、80/20 法则：先找到那几个该搬的循环

2.1 Amdahl 定律给出的上限

2.2 什么叫”关键循环”

2.3 怎么找：工具链与实测数据

2.4 实测数据：50-2 法则与 80-3 法则

2.5 由此得出的三个推论

三、能耗模型：为什么”快”不自动等于”省”

3.1 基本关系：能量 = 时间 × 功率

3.2 陷阱：硬件会把功率顶上去

3.3 手算两个例子

3.4 论文的能量公式

四、怎么搬：目标架构、握手协议与互斥执行

4.1 目标架构一：单芯片微处理器 + 可重构逻辑