并行与多核

概念

前面几章都在讨论"一台机器怎么把一件事做快"：流水线让指令重叠、乱序让停顿被填掉、Cache 让访存变快。这一章换一个维度——同时做几件事。

先把两个从操作系统概论起就反复出现的词钉死：

	并发（concurrency）	并行（parallelism）
定义	宏观上同时，微观上串行	同一时刻真的同时在跑
需要多核吗	不需要，单核交替即可	必须多核（或多机、或多执行单元）
解决的问题	让程序"看起来"同时推进、不让 CPU 空转	缩短实际时间
典型例子	单核上的时间片轮转	4 个核同时算 4 段求和

"并发是结构，并行是执行"——一句话记住：并发关心的是"怎么组织"，并行关心的是"真的快了没有"。单核也能并发，但那不会让总时间变短。

原理

一、Amdahl 定律：固定问题规模，加核能快多少

假设一个程序里，必须串行的部分占 $s$ ，剩下 $1 - s$ 可以并行。用 $p$ 个处理器：

S (p) = \frac{1}{s + \frac{1 - s}{p}}

看一眼 $p \to \infty$ 的极限就明白了：

lim_{p \to \infty} S (p) = \frac{1}{s}

串行部分决定了天花板。 串行占比 5%，那么无论堆多少个核，加速比也超不过 20 倍。

算几档具体数字（ $s = 0.05$ ）：

$p$	1	2	4	8	16	64
$S (p)$	1.0000	1.9048	3.4783	5.9259	9.1429	15.4217
效率 $E = S / p$	1.0000	0.9524	0.8696	0.7407	0.5714	0.2410

注意效率那一行掉得有多快：16 核时效率只剩 0.5714，64 核时 0.2410。核越多越不划算。

再换几个 $s$ 看天花板：

$s$	0.5	0.1	0.05	0.01	0.001
天花板 $1 / s$	2.0	10.0	20.0	100.0	1000.0
$p = 16$ 时 $S$	1.8824	6.4000	9.1429	13.9130	15.7635

结论句：想扩核，先砍串行段。 把 $s$ 从 0.05 砍到 0.01，天花板一下从 20 倍抬到 100 倍——这比多买 4 倍的核有效得多。

二、Gustafson 定律：固定运行时间，能算多大的题

Amdahl 有个隐含前提：问题规模不变。但现实里我们常常是"同样的时间，想算更大的题"——核多了就把数据量加大，而不是等着更快出结果。

这时候串行部分不随规模增长，并行部分随核数放大：

S (p) = s + p (1 - s) = p - s (p - 1)

同一个 $s = 0.05$ ：

$p$	4	16	64	256
$S (p)$	3.8500	15.2500	60.8500	243.2500
效率	0.9625	0.9531	0.9508	0.9502

效率几乎不掉（一直贴在 0.95 附近）。

三、两定律为什么结论相反

同一个 $s$ ， $p = 16$ 时：

定律	回答的问题	$S (16)$
Amdahl	"同一道题能快多少"	9.1429
Gustafson	"同样的时间能算多大的题"	15.2500

差别不在数学，在提问方式。 Amdahl 的分母固定在"原来的总工作量"上，所以串行部分是被放大的瓶颈；Gustafson 让总工作量随核数长大，串行部分被摊薄了。

这两个数一起看，正好解释了现实中那句看似矛盾的话："多核没什么用"与"多核很有用"可以同时成立——取决于你的程序是"跑固定的题"还是"算更大的题"。

四、并行的四个层次

"并行"不只是"多核"。按粒度从小到大：

层次	硬件手段	一次能做多少	典型倍数	主线里的位置
位级	进位链、位片	一次处理 32 / 64 位	1	加法器
指令级 ILP	流水线、多发射、乱序	一周期发射 4~6 条	4~6	流水线
数据级 SIMD	SSE / AVX2 / AVX-512	一条指令 4 / 8 / 16 个 `float`	16	本章、`elec`
任务级	多线程 / 多进程 / 多机	数量由软件决定	看程序	`os`、`soft/30`

四条线合起来才是一个 CPU 的真实并行度：位级把加减法内部的进位并行起来，指令级让不同指令重叠，数据级让一条指令同时算一批数，任务级让多个核各干一份活。

这条表还有个用处：它解释了为什么"主频不变但每年都在变快"——光是 SIMD 从 4 位扩到 512 位，就是 128 倍的宽度，靠的全是"硬件替你把循环展开"。

五、为什么转向多核：功耗墙

2005 年前后，行业齐刷刷从"拉主频"转向"堆核"。原因不是技术做不快，而是做快了会烧掉。

动态功耗的简化式：

P \propto C V^{2} f

而电压 $V$ 通常与频率 $f$ 大致同步（想拉高频，就得加压），于是近似 $P \propto f^{3}$ ——频率涨 10%，功耗涨约 33%。

反过来用：把频率降到 0.8 倍，单核功耗只剩 0.512。

单核频率	单核功耗比	双核总功耗比	双核吞吐比
1.00 f	1.0000	2.0000	2.00
0.90 f	0.7290	1.4580	1.80
0.80 f	0.5120	1.0240	1.60
0.70 f	0.3430	0.6860	1.40

读第 3 行：频率降 20%，一个核的功耗掉到 0.512；两个核加起来 1.024，和原来一个核几乎一样，吞吐却从 1.0 涨到 1.6。

同样的一块热预算，堆核比拉主频划算——这就是多核时代到来的物理原因。它不是"想多核"，而是"只能多核"。

六、多核的三种组织方式

形态	结构	通信方式	特点
SMP（对称多处理）	所有核平等，共享同一内存	读写共享内存	编程简单；核多了总线成瓶颈
NUMA（非一致内存访问）	每个核有自己的近端内存	访本地快、访远端慢	现代多路服务器标配；"内存离谁近"变成性能变量
消息传递（MPP / 集群）	各自独立内存	显式收发消息	可扩到上万节点；没有共享变量

从 SMP 到 NUMA 的变化，本质是"存储墙"：核越多，共享总线的争用越严重，只能把内存"分块靠近"。于是"访问哪个变量"这件事，第一次和地址布局挂上了钩——这也正是下一章要展开的问题。

七、超线程（SMT）不是"多出一个核"

SMT（同步多线程，Intel 叫超线程）在一个物理核里塞进两套架构状态（寄存器、PC），但共用一套执行单元。

对操作系统：看起来是 2 个逻辑处理器。
实测增益：通常在 30% 上下，绝不是 100%。

为什么不是 100%：因为两条线程抢的是同一批执行单元。它填的是"某个线程因访存停顿、执行单元闲着"的窟窿，而不是凭空多出算力。

这条也解释了一个实践现象：计算密集型的程序开超线程几乎没增益，访存密集型的程序增益明显。前者执行单元本来就排满，没有窟窿可填。

八、并行要面对的三堵墙

墙	内容	应对
功耗墙	$P \propto f^{3}$ ，主频上不去	堆核、降频、专用加速器
存储墙	核多了，访存带宽不够分	多级 Cache、本地化数据、NUMA 亲和
通信墙	核间同步与通信有固定开销	减少共享、增大粒度、无锁结构

三堵墙里最难的是第三堵：它不是"不够快"，而是"加得越多，协调成本涨得越快"。这就是第五节"效率随核数下降"的物理来源——Amdahl 定律描述的不是硬件缺陷，而是协调成本。

示例

例 1：Amdahl 表与功耗账（C）

#include <stdio.h>

/* Amdahl：串行占比 s，p 个处理器 */
static double amdahl(double s, int p) {
    return 1.0 / (s + (1.0 - s) / p);
}

int main(void) {
    double s = 0.05;
    int ps[6] = {1, 2, 4, 8, 16, 64};

    printf("%-8s %-12s %-12s %s\n", "p", "S(p)", "E=S/p", "note");
    for (int i = 0; i < 6; i++) {
        double sp = amdahl(s, ps[i]);
        printf("%-8d %-12.4f %-12.4f %s\n", ps[i], sp, sp / ps[i],
               ps[i] == 1 ? "no parallel"
                          : (sp / ps[i] < 0.5 ? "efficiency below 0.5" : ""));
    }
    printf("串行占比 s = %.2f，加速比天花板 1/s = %.1f 倍\n", s, 1.0 / s);

    /* 功耗：P 正比于 f^3 */
    printf("\n功耗对比（P 正比于 f^3）：\n");
    double fr[4] = {1.0, 0.9, 0.8, 0.7};
    for (int i = 0; i < 4; i++) {
        double r = fr[i];
        printf("  频率 %.2f f -> 单核 %.4f，双核 %.4f，双核吞吐 %.2f\n",
               r, r * r * r, 2 * r * r * r, 2 * r);
    }
    return 0;
}

c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

p        S(p)         E=S/p        note
1        1.0000       1.0000       no parallel
2        1.9048       0.9524       
4        3.4783       0.8696       
8        5.9259       0.7407       
16       9.1429       0.5714       
64       15.4217      0.2410       efficiency below 0.5
串行占比 s = 0.05，加速比天花板 1/s = 20.0 倍

功耗对比（P 正比于 f^3）：
  频率 1.00 f -> 单核 1.0000，双核 2.0000，双核吞吐 2.00
  频率 0.90 f -> 单核 0.7290，双核 1.4580，双核吞吐 1.80
  频率 0.80 f -> 单核 0.5120，双核 1.0240，双核吞吐 1.60
  频率 0.70 f -> 单核 0.3430，双核 0.6860，双核吞吐 1.40

两点：

p 从 8 到 16，加速比只从 5.9259 涨到 9.1429——多花一倍的核，只多拿 54% 的加速。收益递减是常态，不是意外。
第五行那个 0.5120 是整个多核时代的起点：频率降两成、功耗砍一半，正好够再放一个核。

例 2：两定律摆在一起，再算一遍并行四层次（Python）

C 段只算了 Amdahl 与功耗。这里补上 Gustafson——同一个 $s$ ，两个定律给出的答案完全不同。

def dw(s):
    """显示宽度：中文算 2 列"""
    return sum(2 if ord(c) > 0x2000 else 1 for c in str(s))


def pad(s, w):
    return str(s) + " " * max(0, w - dw(str(s)))


def table(head, rows, gap=2):
    data = [[str(c) for c in r] for r in rows]
    w = [max([dw(head[i])] + [dw(r[i]) for r in data]) + gap for i in range(len(head))]
    print("  " + "".join(pad(head[i], w[i]) for i in range(len(head))))
    for r in data:
        print("  " + "".join(pad(r[i], w[i]) for i in range(len(head))))


def amdahl(s, n):
    """固定问题规模：串行占比 s，n 个处理器"""
    return 1.0 / (s + (1.0 - s) / n)


def gustafson(s, n):
    """固定运行时间：串行占比 s，n 个处理器（问题规模随核数放大）"""
    return s + n * (1.0 - s)


print("=== 1. Amdahl 定律：固定问题规模 ===")
print("  串行部分占 s，剩下 (1-s) 可以并行；加速比上限 = 1/s")
rows = []
for n in [1, 2, 4, 8, 16, 64, 1000000]:
    tag = "1e6（近似无穷）" if n == 1000000 else str(n)
    rows.append([tag, "%.4f" % amdahl(0.05, n), "%.4f" % (amdahl(0.05, n) / n)])
table(["--p", "S(p)（s=0.05）", "效率 E=S/p"], rows)
print("  s=0.05 的加速比天花板 = 1/0.05 = %.1f 倍；p 到 100 万也超不过它。" % (1 / 0.05))
print()
rows = []
for s in [0.5, 0.1, 0.05, 0.01, 0.001]:
    rows.append(["%.3f" % s, "%.1f" % (1.0 / s), "%.4f" % amdahl(s, 16)])
table(["串行占比 s", "天花板 1/s", "p=16 时的 S"], rows)
print("  s 从 0.05 降到 0.01，天花板从 20 倍抬到 100 倍 —— 想扩核，先砍串行段。")
print()

print("=== 2. Gustafson 定律：固定运行时间 ===")
rows = []
for n in [4, 16, 64, 256]:
    rows.append([str(n), "%.4f" % gustafson(0.05, n), "%.4f" % (gustafson(0.05, n) / n)])
table(["--p", "S(p)（s=0.05）", "效率"], rows)
print("  同一个 s=0.05：Amdahl 在 p=16 给 %.4f，Gustafson 给 %.4f。"
      % (amdahl(0.05, 16), gustafson(0.05, 16)))
print("  差别不在数学，在于问的是两个不同的问题：")
print("  Amdahl 问'同一道题再快多少'，Gustafson 问'同样的时间能算多大的题'。")
print()

print("=== 3. 功耗墙：为什么不再拉主频，而是堆核 ===")
print("  简化模型：动态功耗 P ∝ C V^2 f，而降压常与降频同步，于是近似 P ∝ f^3")
rows = []
for r in [1.0, 0.9, 0.8, 0.7]:
    p1 = r ** 3
    rows.append(["%.2f f" % r, "%.4f" % p1, "%.4f" % (2 * p1), "%.2f" % (2 * r)])
table(["单核频率", "单核功耗比", "双核总功耗比", "双核吞吐比"], rows)
print("  降到 0.8 f 时单核功耗只剩 0.512，两个核加起来 1.024 —— 功耗几乎不变，")
print("  吞吐却从 1.0 涨到 1.6。这就是 2005 年前后行业齐刷刷转向多核的原因。")
print()

print("=== 4. 并行有四个层次，别只说'多核' ===")
rows = [
    ["位级", "进位链 / 位片", "一次处理 32、64 位", "1"],
    ["指令级 ILP", "流水线、乱序、多发射", "一周期发射 4~6 条", "4~6"],
    ["数据级 SIMD", "SSE / AVX2 / AVX-512", "一条指令 4 / 8 / 16 个 float", "16"],
    ["任务级", "多线程 / 多进程 / 多机", "数量由软件决定", "看程序"],
]
table(["层次", "硬件手段", "一次能做多少", "典型倍数"], rows)
print("  超线程（SMT）是特例：一个核塞两条线程，共用执行单元，")
print("  实测增益通常在 30% 上下 —— 它填的是'执行单元闲着'的窟窿，不是真多出一个核。")

python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行

预期输出：

=== 1. Amdahl 定律：固定问题规模 ===
  串行部分占 s，剩下 (1-s) 可以并行；加速比上限 = 1/s
  --p              S(p)（s=0.05）  效率 E=S/p  
  1                1.0000          1.0000      
  2                1.9048          0.9524      
  4                3.4783          0.8696      
  8                5.9259          0.7407      
  16               9.1429          0.5714      
  64               15.4217         0.2410      
  1e6（近似无穷）  19.9996         0.0000      
  s=0.05 的加速比天花板 = 1/0.05 = 20.0 倍；p 到 100 万也超不过它。

  串行占比 s  天花板 1/s  p=16 时的 S  
  0.500       2.0         1.8824       
  0.100       10.0        6.4000       
  0.050       20.0        9.1429       
  0.010       100.0       13.9130      
  0.001       1000.0      15.7635      
  s 从 0.05 降到 0.01，天花板从 20 倍抬到 100 倍 —— 想扩核，先砍串行段。

=== 2. Gustafson 定律：固定运行时间 ===
  --p  S(p)（s=0.05）  效率    
  4    3.8500          0.9625  
  16   15.2500         0.9531  
  64   60.8500         0.9508  
  256  243.2500        0.9502  
  同一个 s=0.05：Amdahl 在 p=16 给 9.1429，Gustafson 给 15.2500。
  差别不在数学，在于问的是两个不同的问题：
  Amdahl 问'同一道题再快多少'，Gustafson 问'同样的时间能算多大的题'。

=== 3. 功耗墙：为什么不再拉主频，而是堆核 ===
  简化模型：动态功耗 P ∝ C V^2 f，而降压常与降频同步，于是近似 P ∝ f^3
  单核频率  单核功耗比  双核总功耗比  双核吞吐比  
  1.00 f    1.0000      2.0000        2.00        
  0.90 f    0.7290      1.4580        1.80        
  0.80 f    0.5120      1.0240        1.60        
  0.70 f    0.3430      0.6860        1.40        
  降到 0.8 f 时单核功耗只剩 0.512，两个核加起来 1.024 —— 功耗几乎不变，
  吞吐却从 1.0 涨到 1.6。这就是 2005 年前后行业齐刷刷转向多核的原因。

=== 4. 并行有四个层次，别只说'多核' ===
  层次         硬件手段                一次能做多少                  典型倍数  
  位级         进位链 / 位片           一次处理 32、64 位            1         
  指令级 ILP   流水线、乱序、多发射    一周期发射 4~6 条             4~6       
  数据级 SIMD  SSE / AVX2 / AVX-512    一条指令 4 / 8 / 16 个 float  16        
  任务级       多线程 / 多进程 / 多机  数量由软件决定                看程序    
  超线程（SMT）是特例：一个核塞两条线程，共用执行单元，
  实测增益通常在 30% 上下 —— 它填的是'执行单元闲着'的窟窿，不是真多出一个核。

四条结论：

两段代码算的是同一个 $s$ ，却给出 9.1429 与 15.2500 两个数——这不是矛盾，是两个不同的问题。
E = S/p 那一列是"该不该继续加核"的判据：效率跌破 0.5（本表在 64 核）之后，再加核就是浪费电。
p=1e6 的效率是 0.0000：加速比封在 19.9996，无限多的核分下去，每个核几乎没活干。这就是 Amdahl 的天花板。
四个层次加起来才是 CPU 的真实并行度，而且它们的量级差得很远——SIMD 的 16 倍远比"多塞一个核"容易拿到。

考点

1. 并发与并行的分界

并发 = 宏观同时、微观串行，单核即可；并行 = 同一时刻真同时，必须多核。
并发解决"让程序都能推进"，并行解决"缩短实际时间"。

2. Amdahl 与 Gustafson（两个公式都要能写）

定律	前提	公式	极限
Amdahl	问题规模固定	$S = 1 / (s + (1 - s) / p)$	$1 / s$
Gustafson	运行时间固定，规模随核放大	$S = s + p (1 - s)$	随 $p$ 线性增长

3. 效率与加速比

$E = S / p$ 。 $p$ 越大 $E$ 越小； $E < 0.5$ 之后继续加核基本是浪费。

4. 功耗与多核

$P \propto C V^{2} f$ ，近似 $P \propto f^{3}$ 。频率降 20%，单核功耗降到 0.512，同样热预算可以放两个核，吞吐 1.6 倍。这是多核时代的物理起点。

5. 并行的四个层次

位级（进位链，1 倍）→ 指令级（流水线/多发射/乱序，4~6 倍）→ 数据级（SIMD，4/8/16 倍）→ 任务级（线程/进程/多机，看程序）。

6. 超线程（SMT）

一个物理核 + 两套架构状态，共用执行单元。
增益典型值 约 30%，不是 2 倍。
访存密集的程序受益大（填访存停顿的窟窿），计算密集的程序受益小。

7. 三堵墙

功耗墙（ $f^{3}$ 限制主频）、存储墙（带宽不够分，靠 Cache 与局部性）、通信墙（同步与通信开销随核数上升——这才是效率下降的真正来源）。

8. 三种多核组织

SMP（平等共享内存）→ NUMA（近端/远端内存，访存不均）→ 消息传递（各自内存，显式通信）。核越多越往右走。

9. 易错点清单

把"并发"当"并行"：单核并发不会让总时间变短。
记成"Amdahl 的极限是 $p$ "：极限是 $1 / s$ ，与核数无关。
用 Amdahl 的公式去算"规模随核放大"的场景：那要用 Gustafson。
以为超线程等于核数翻倍：约 30%，且计算密集型几乎无收益。
把"串行段占比 $s$ "与"不可并行部分的比例"混用： $s$ 是时间占比，不是代码行数占比。
忘了效率：加速比涨 ≠ 划算，要看 $E = S / p$ 。

小结

并发是结构，并行是执行；单核能并发，但只有多核能真正缩短时间。
Amdahl 回答"同一道题能快多少"（天花板 $1 / s$ ），Gustafson 回答"同样时间能算多大的题"（随核线性长）——同一个 $s$ 给两个答案并不矛盾。
功耗 $\propto f^{3}$ 逼出了多核：降频 20% 换两个核，同样的电换 1.6 倍吞吐。
超线程填的是"执行单元闲着"的窟窿，约 30%，不是翻倍。
加核的收益递减，根源是通信与同步这些"协调成本"，不是硬件不够好。

回到主线：本章讲的是"真的同时做几件事"这件事的宏观账。可还有一层更细的并行藏在一个核里面——同一个核里，指令也可以不按程序写的顺序执行。这需要硬件同时保证"打乱顺序但不改变结果"。下一章就讲这件事：乱序执行与推测执行。

下一篇：乱序执行与推测执行

并行与多核

概念

原理

一、Amdahl 定律：固定问题规模，加核能快多少

二、Gustafson 定律：固定运行时间，能算多大的题

三、两定律为什么结论相反

四、并行的四个层次

五、为什么转向多核：功耗墙

六、多核的三种组织方式

七、超线程（SMT）不是"多出一个核"

八、并行要面对的三堵墙

示例

例 1：Amdahl 表与功耗账（C）

例 2：两定律摆在一起，再算一遍并行四层次（Python）

考点

小结

我的笔记

评论（0）

并行与多核 ​

概念 ​

原理 ​

一、Amdahl 定律：固定问题规模，加核能快多少 ​

二、Gustafson 定律：固定运行时间，能算多大的题 ​

三、两定律为什么结论相反 ​

四、并行的四个层次 ​

五、为什么转向多核：功耗墙 ​

六、多核的三种组织方式 ​

七、超线程（SMT）不是"多出一个核" ​

八、并行要面对的三堵墙 ​

示例 ​

例 1：Amdahl 表与功耗账（C） ​

例 2：两定律摆在一起，再算一遍并行四层次（Python） ​

考点 ​

小结 ​

我的笔记

评论（0）

并行与多核

概念

原理

一、Amdahl 定律：固定问题规模，加核能快多少

二、Gustafson 定律：固定运行时间，能算多大的题

三、两定律为什么结论相反

四、并行的四个层次

五、为什么转向多核：功耗墙

六、多核的三种组织方式

七、超线程（SMT）不是"多出一个核"

八、并行要面对的三堵墙

示例

例 1：Amdahl 表与功耗账（C）

例 2：两定律摆在一起，再算一遍并行四层次（Python）

考点

小结