w wyl123ly 的博客
MD

计算机组成原理

40 KB 2026.10.11 原文件

计算机组成原理

这篇笔记讲什么

计算机组成原理(Computer Organization)回答一个最朴素的问题:你写的代码,最终是怎么变成电信号跑起来的。

本文按「数据表示 → CPU 执行 → 存储层次 → 总线与 IO → 性能度量」这条主线走一遍:

从原码反码补码与 IEEE 754 浮点,到指令周期、流水线与冒险,再到 Cache 映射方式与命中率计算,

最后用 CPI、MIPS、Amdahl 定律把「为什么这个优化有效、那个优化白费」算清楚。

读完你应该能:手算补码与浮点拆位、算出一道缓存题的平均访问时间、解释为什么循环里换一下遍历顺序性能差十倍。

一、这是什么

计算机组成原理研究的是硬件层面的功能部件与它们的协作方式,包含两个容易混淆的分支:

分支英文关注点例子
计算机组成Computer Organization对程序员可见的逻辑实现指令集里有几条加法指令、Cache 多大
计算机体系结构Computer Architecture对程序员可见的抽象属性指令集是 RISC 还是 CISC、地址位数

组成 vs 体系结构

经典判断法:这件事改变了程序员的编程模型吗? 改变了 → 体系结构;没改变 → 组成。

例如「把主频从 3.0 GHz 提到 3.5 GHz」不改变任何指令语义,属于组成;

「增加一条 SIMD 指令」改变了你能写的代码,属于体系结构。

现代计算机的基本模型是存储程序(Stored-Program)思想,也就是冯·诺依曼结构。

二、为什么需要它

很多「玄学」问题,答案都在这一层:

  1. 性能问题:同样的算法,for i for j 与 for j for i 遍历二维数组,耗时可能差 5~10 倍。这是 Cache 与局部性问题,不是语言问题。
  2. 正确性问题:0.1 + 0.2 != 0.3、int 溢出变成负数、float 比较需要容差。这是定点/浮点表示问题。
  3. 并发问题:为什么两个线程写同一个变量会丢更新?因为 i++ 不是一条指令,而是「读-改-写」三步,中间可能被打断。这直接通向 操作系统 的原子性与内存屏障。
  4. IO 瓶颈:为什么用 read() 逐字节读文件慢得离谱?因为每次系统调用都有用户态/内核态切换开销,牵涉到中断与 DMA 的协作方式。

一句话结论

上层的一切性能优化(缓存、批处理、对齐、并发),本质上都是在迎合硬件的存储层次与访问粒度。

三、冯·诺依曼结构与哈佛结构

3.1 两种结构的对比

对比项冯·诺依曼结构(von Neumann)哈佛结构(Harvard)
存储器指令与数据共用同一存储空间指令与数据物理分离
总线一套地址/数据总线(共享)两套独立总线
瓶颈存在「冯·诺依曼瓶颈」:取指与取数抢总线取指与取数可并行
地址空间统一编址,代码可当数据处理(自修改代码)分开编址,代码与数据地址可重叠
典型实现x86-64、ARM(外部)、几乎所有通用 CPU8051、AVR、DSP、ARM 的 TCM 局部
灵活性高(编译器、加载器、JIT 都受益)较低,但确定性带宽更好

现实是混合的

现代通用处理器在外部是冯·诺依曼(统一内存),在内部是哈佛(L1 指令 Cache 与 L1 数据 Cache 分离,即 Modified Harvard)。

所以「哈佛结构只存在于单片机」是过时的说法。

3.2 冯·诺依曼瓶颈的量化

设取指需要 ,取数需要 ,共用一条总线时:

这就是为什么要做 Cache:把指令与数据的访问在时间上错开(预取、流水线),或在空间上分离(分离 Cache)。

四、CPU 内部组成

CPU(Central Processing Unit)由三大件构成:

部件英文职责关键细节
运算器ALU(Arithmetic Logic Unit)算术与逻辑运算加减乘除、与或非、移位、比较;由组合逻辑构成
寄存器Register File / Registers存放操作数与中间结果速度最快(约 1 个时钟周期),数量极少(x86-64 有 16 个通用寄存器)
控制器Control Unit取指、译码、发出控制信号硬布线(快但难改)或微程序(灵活但慢)

此外还有两类「黏合剂」:

  • PC(Program Counter,程序计数器):指向下一条要取的指令地址。
  • IR(Instruction Register,指令寄存器):存放当前正在译码的指令。
  • PSW/FLAGS(Program Status Word):零标志 ZF、进位 CF、溢出 OF、符号 SF 等,条件跳转依赖它。

寄存器为什么这么快

寄存器在 CPU 核心里,用触发器(Flip-Flop)实现,访问延迟约 0.2~0.3 ns;

而内存走总线,动辄 60~100 ns,差了两个数量级。这是存储层次存在的物理原因。

五、指令周期与指令流水线

5.1 指令周期

一条指令的执行被划分为若干阶段,经典 RISC 五级流水:

阶段全称做什么
IFInstruction Fetch按 PC 取指令,PC 自增
IDInstruction Decode译码,读寄存器堆
EXExecuteALU 运算 / 计算地址
MEMMemory Access访存(load/store)
WBWrite Back结果写回寄存器

顺序执行时,每条指令耗时 。

5.2 流水线加速比

理想情况下(无冒险、阶段完全平衡), 级流水线执行 条指令:

流水线的极限

理想加速比的上限就是流水线级数 。级数越深,单级逻辑越短、频率越高,

但冒险代价和寄存器开销也越大(Pentium 4 的 31 级流水线就是反面教材)。

5.3 流水线冒险(Hazard)与解决

冒险类型英文成因解决手段
结构冒险Structural Hazard部件冲突,如 IF 与 MEM 同时访存指令/数据 Cache 分离、增加端口、停顿
数据冒险Data Hazard后一条指令要用前一条还没写回的结果数据前推(Forwarding/Bypassing)、停顿(Stall)、编译期指令调度
控制冒险Control Hazard分支导致不知下一条取哪分支预测、延迟槽(Delay Slot)、预测执行 + 冲刷

数据冒险细分:

  • RAW(Read After Write,写后读):真相关,必须处理。
  • WAR(Write After Read,读后写):反相关,乱序执行时用寄存器重命名消除。
  • WAW(Write After Write,写后写):输出相关,同样用重命名消除。

下面这段 C 代码在流水线视角下是典型的 RAW 链(a 依赖前一条结果):

/* 编译:gcc -O2 -S demo.c -o demo.s  然后观察汇编里的依赖链 */
#include <stdio.h>

int main(void) {
    long a = 1, b = 2, c = 3;

    /* 三条语句彼此依赖:典型的 RAW 链
     * 现代 CPU 用数据前推 + 乱序执行把这三条尽量重叠执行
     * 若改为 a=1; b=2; c=3; 三条相互独立,则能真正并行发射
     */
    a = a + b;   /* 依赖 b */
    b = b * c;   /* 依赖 c,且与上一条争用 ALU */
    c = c - a;   /* 依赖上一条算出的 a */

    printf("%ld %ld %ld\n", a, b, c);   /* 输出 3 6 -1 */
    return 0;
}

常见误解

「加流水线就一定更快」是错的。若程序充满不可预测的分支(如解释器的主分发循环),

分支预测失败率飙升,流水线越深,每次冲刷浪费的周期越多。

六、存储层次结构

6.1 层次总览

层级典型容量典型访问延迟相对成本由谁管理
寄存器几百字节~几 KB0.2~0.5 ns(<1 周期)最贵编译器
L1 Cache32~64 KB/核约 1~2 ns(约 4 周期)很贵硬件
L2 Cache256 KB~2 MB/核约 4~7 ns(约 12 周期)贵硬件
L3 Cache8~64 MB(共享)约 15~25 ns(约 40 周期)较贵硬件
主存 DRAM8~256 GB约 60~100 ns中等硬件 + OS
SSD(NVMe)256 GB~4 TB约 20~100 μs便宜OS
HDD1~20 TB约 5~15 ms最便宜OS

延迟是分层量级差异,不是倍数差异

从寄存器到 HDD,延迟跨越了 7 个数量级。用「CPU 1 周期 = 1 秒」的经典类比:

L1 约 1 分钟,内存约 2 天,SSD 约 1 个月,HDD 约 1~2 年。

这解释了一切:为什么数据库要缓冲池、为什么文件系统要预读、为什么算法要讲究访存模式。

层次结构的有效性完全依赖局部性原理。

6.2 局部性原理(Principle of Locality)

类型含义表现被谁利用
时间局部性Temporal Locality刚访问过的数据很可能再次被访问Cache、缓冲池
空间局部性Spatial Locality地址相邻的数据很可能被一起访问Cache Line、预取、磁盘块
/* 空间局部性的经典演示:按行 vs 按列遍历 */
#include <stdio.h>
#include <time.h>

#define N 4096
static int a[N][N];

int main(void) {
    clock_t t0 = clock();
    long sum = 0;

    /* 方式 A:按行访问 —— 内存中行是连续的,命中整条 Cache Line,快 */
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            sum += a[i][j];

    clock_t t1 = clock();

    /* 方式 B:按列访问 —— 每次跨 N*4 字节,几乎每次都是 Cache Miss,慢得多 */
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            sum += a[i][j];

    clock_t t2 = clock();
    printf("row-major: %.3f s, col-major: %.3f s, sum=%ld\n",
           (double)(t1 - t0) / CLOCKS_PER_SEC,
           (double)(t2 - t1) / CLOCKS_PER_SEC, sum);
    return 0;
}

同一份数据、同样的加法次数,只因为访问顺序不同,按列的版本通常慢 3~10 倍。

七、Cache 映射方式与命中率计算

7.1 三种映射方式

设地址长度为 位,块大小 字节,Cache 总容量 。

映射方式英文结构地址划分优点缺点
直接映射Direct Mapped每个主存块只能放到唯一一行标记 + 行号 + 块内偏移硬件最简、比较器最少冲突缺失(Conflict Miss)严重
全相联Fully Associative任意块可放任意行标记 + 块内偏移冲突缺失最少需并行比较所有行,硬件昂贵
组相联Set Associative组间直接映射、组内全相联标记 + 组号 + 块内偏移折中, 路组相联最常用组索引冲突仍可能发生

地址划分公式:

拆位实例

设 32 位地址、Cache 4 KB、块大小 64 B。

- 偏移位数

- 直接映射:行数 ,行号 6 位,标记 位

- 4 路组相联:组数 ,组号 4 位,标记 位

若地址为 0x00001A2C:低 6 位 101100 = 偏移 44;直接映射下第 6~11 位 001000 = 行号 8;其余 20 位为标记。

7.2 命中率与平均访问时间

多级 Cache 时逐级展开(缺失代价包含下一级的 AMAT):

下面这段 Python 直接算上面的公式,可直接运行:

"""cache_amat.py —— 计算 AMAT 与多级 Cache 的平均访问时间"""

def amat_single(hit_ns: float, miss_rate: float, miss_penalty_ns: float) -> float:
    """单级 Cache:AMAT = 命中时间 + 缺失率 * 缺失代价"""
    assert 0.0 <= miss_rate <= 1.0, "缺失率必须在 [0, 1] 内"
    return hit_ns + miss_rate * miss_penalty_ns


def amat_multi(levels) -> float:
    """多级 Cache 逐级递推求 AMAT

    levels: [(本级的命中时间, 本级向下一级的缺失率), ...],从最内层到最外层,
            最后一项的缺失是指「到内存」的缺失。

    递推式(自外向内):
        AMAT_n = t_hit(n)                                   # 最外层,缺失即访问内存
        AMAT_i = t_hit(i) + miss_rate(i) * AMAT_(i+1)        # 内层
    """
    total = levels[-1][0]                       # 最外层:命中时间即内存访问时间
    for hit_time, miss_rate in reversed(levels[:-1]):
        total = hit_time + miss_rate * total
    return total


if __name__ == "__main__":
    # 例:L1 命中 1ns,缺失率 5%,L2 命中 4ns,L2 缺失率 20%,内存 80ns
    l2 = amat_single(4.0, 0.20, 80.0)          # L2 层 AMAT = 4 + 0.2*80 = 20ns
    l1 = amat_single(1.0, 0.05, l2)            # L1 层 AMAT = 1 + 0.05*20 = 2ns
    print(f"L2 AMAT = {l2:.2f} ns")
    print(f"整体 AMAT = {l1:.2f} ns")          # 2.00 ns

    # 三级 Cache 版本:(本级命中时间, 本级向下一级的缺失率)
    # L1: 1ns / 5% -> L2: 4ns / 20% -> L3: 15ns / 40% -> 内存: 90ns
    total = amat_multi([(1.0, 0.05), (4.0, 0.20), (15.0, 0.40), (90.0, 0.0)])
    print(f"三级 Cache 整体 AMAT = {total:.2f} ns")   # 1 + .05*(4 + .2*(15 + .4*90)) = 2.96 ns

    # 若把 L1 缺失率从 5% 降到 2%,AMAT 变为 1 + 0.02*20 = 1.4ns,提升约 30%
    print(f"优化后 AMAT = {amat_single(1.0, 0.02, l2):.2f} ns")

优化谁更划算

AMAT 是乘积结构,所以「降低缺失率」和「降低缺失代价」的收益要分别乘上系数看。

缺失率 5%、缺失代价 20 ns 时,把缺失代价砍半(省 0.5 ns)远不如把缺失率砍半(省 0.5 ns)——

两者恰好相同时,优先选硬件上更便宜的那个。

7.3 三种缺失(3C)

名称英文原因对策
强制缺失Compulsory / Cold第一次访问,必然缺失预取(Prefetching)
容量缺失CapacityCache 装不下工作集增大 Cache、分块(Blocking/Tiling)
冲突缺失Conflict多个块映射到同一组提高相联度、随机化索引

八、主存与地址译码

主存由存储阵列 + 地址译码器 + 读写控制构成。给定地址位数 ,可寻址单元数为:

用 8K×8 位的芯片组成 64K×8 位的存储器

- 需要芯片数 片

- 地址线共 16 根():低 13 根()接所有芯片的片内地址线

- 高 3 根()送 3-8 译码器,产生 8 个片选信号

- 每片只有被选中的那一片才会响应读写,其余处于高阻态

字扩展 vs 位扩展:

方式场景连接方式
位扩展字数够、位数不够(8K×4 → 8K×8)地址线全并联,数据线分别接高低位,片选并联
字扩展位数够、字数不够(8K×8 → 64K×8)地址线低位并联,高位译码产生片选

九、总线与 IO

9.1 总线

总线(Bus)是多个部件共享的传输通道,分为:

类型传输内容方向
数据总线数据双向
地址总线地址单向(CPU → 外设)
控制总线读写、中断、时钟双向/单向混合

总线带宽(Bandwidth):

计算

32 位(4 字节)数据总线、总线时钟 100 MHz、每个时钟传一次:

带宽 MB/s。若改为每 2 个时钟传一次,则减半为 200 MB/s。

现代总线是分层的:CPU 侧有快速通道(如 Intel 的 DMI/UPI、AMD 的 Infinity Fabric),外设侧有 PCIe、USB、SATA/NVMe。

9.2 中断(Interrupt)

对比项中断方式程序查询方式(Polling)
CPU 参与外设主动通知,CPU 响应CPU 反复读状态寄存器
效率高,可与其他工作重叠低,纯忙等
实时性依赖优先级与响应时间取决于轮询周期
适合场景键盘、网卡、磁盘完成通知极简嵌入式、超低延迟轮询

中断处理流程:外设发中断请求 → 中断控制器(如 APIC)汇总 → CPU 在当前指令边界响应 → 保存现场(PC/PSW 入栈)→ 查中断向量表跳转 ISR → 执行服务程序 → 恢复现场返回。

中断上下文里不能做的事

ISR 运行在中断上下文,不能被睡眠:不能拿可能阻塞的锁、不能做会引发调度的操作、

要尽量短(把重活丢给下半部/工作队列)。这条规则在 操作系统 里会反复出现。

9.3 DMA(Direct Memory Access,直接存储器访问)

对比项中断驱动 IODMA
数据通路外设 → CPU 寄存器 → 内存外设 ↔ 内存(CPU 不参与搬运)
CPU 开销每字节/每块都要中断一次传输只中断一次(完成后)
适用规模少量数据(串口)大批量(磁盘、网卡、GPU)
关键机制中断向量DMA 控制器 + 周期窃取(Cycle Stealing)

十、性能指标与公式

10.1 核心公式

其中 ,多类指令时按比例加权:

MIPS 不能跨指令集比较

MIPS 高只说明「每秒执行了很多条指令」,如果指令集本身更弱(一条指令干的活更少),

实际性能可能更差。MIPS 是机器相关的指标,只能用于同一指令集内部比较。

10.2 Amdahl 定律

设某部分占总执行时间的比例为 ,该部分被加速的倍数为 ,则整体加速比:

当 时上界为:

"""amdahl.py —— Amdahl 定律与 CPI 计算,可直接运行"""

def amdahl(p: float, s: float) -> float:
    """p: 可优化部分占比; s: 该部分的加速倍数"""
    if not 0.0 <= p <= 1.0:
        raise ValueError("p 必须在 [0, 1] 内")
    if s <= 0:
        raise ValueError("s 必须为正")
    return 1.0 / ((1.0 - p) + p / s)


def cpi_weighted(classes) -> float:
    """classes: [(该类指令占比, 该类 CPI), ...],占比之和应为 1"""
    total_share = sum(share for share, _ in classes)
    if abs(total_share - 1.0) > 1e-9:
        raise ValueError(f"指令占比之和必须为 1,当前为 {total_share}")
    return sum(share * cpi for share, cpi in classes)


def cpu_time(inst_count: float, cpi: float, freq_hz: float) -> float:
    """返回秒;inst_count 为动态指令条数"""
    return inst_count * cpi / freq_hz


if __name__ == "__main__":
    # 示例 1:60% 的时间花在可并行化部分,把该部分加速 4 倍
    print(f"整体加速比 = {amdahl(0.6, 4.0):.3f}")       # 1/(0.4+0.15) = 1.818
    print(f"理论上限   = {1/(1-0.6):.1f}x")              # 2.5x

    # 示例 2:程序由 50% 整数(CPI=1)、30% 浮点(CPI=4)、20% 访存(CPI=2) 构成
    cpi = cpi_weighted([(0.5, 1.0), (0.3, 4.0), (0.2, 2.0)])   # 0.5+1.2+0.4 = 2.1
    t = cpu_time(1e9, cpi, 3.0e9)                              # 1e9*2.1/3e9 = 0.7 s
    print(f"加权 CPI = {cpi:.2f}, CPU 时间 = {t:.3f} s")

    # 示例 3:把浮点 CPI 从 4 降到 2(浮点硬件优化),再看整体加速比
    cpi_new = cpi_weighted([(0.5, 1.0), (0.3, 2.0), (0.2, 2.0)])  # 1.5
    print(f"优化后 CPI = {cpi_new:.2f}, 加速比 = {cpi/cpi_new:.3f}x")  # 2.1/1.5 = 1.4x

Amdahl 定律的冷酷之处

它告诉你:优化不可优化(或被忽略)的部分是浪费。

若某优化把浮点部分加速了 100 倍,但浮点只占 10% 时间,整体提升不超过 倍。

所以性能优化第一步永远是先测量、找出热点,而不是猜。

十一、数据表示

十一.1 原码、反码、补码

以 8 位为例(,最高位为符号位):

编码正数负数0 的表示范围( 位)
原码 Sign-Magnitude符号位 0 + 绝对值符号位 1 + 绝对值有两个 0(0000_0000、1000_0000)
反码 Ones' Complement同原码原码除符号位外按位取反有两个 0
补码 Two's Complement同原码反码 + 1只有一个 0

补码的关键性质:

为什么计算机用补码:把减法变成加法(),ALU 只需一个加法器;0 的表示唯一,方便判零。

/* twos_complement.c —— 观察补码与溢出 */
#include <stdio.h>
#include <limits.h>

int main(void) {
    signed char a = 127;              /* 8 位有符号最大值 */

    /* 有符号溢出在 C 标准中是未定义行为(UB),这里只是演示位模式
     * 实际工程中不要依赖它,应显式检查边界
     */
    printf("127 + 1 (as int) = %d\n", a + 1);   /* 提升为 int,不溢出:128 */

    signed char b = (signed char)(a + 1);       /* 强制截断回 8 位 */
    printf("截断后 = %d\n", b);                  /* 位模式 1000_0000 = -128 */

    /* 用无符号溢出(定义良好,按模 2^n 回绕)演示同样的位模式 */
    unsigned char u = 255;
    printf("255 + 1 = %u\n", (unsigned char)(u + 1));  /* 0 */

    /* 补码取反加一验证:-5 的补码 */
    signed char x = 5;
    printf("-5 的位模式 = 0x%02X\n", (unsigned char)(~x + 1));  /* 0xFB */

    printf("INT_MIN = %d, INT_MAX = %d\n", INT_MIN, INT_MAX);
    /* 常见坑:-INT_MIN 溢出;应改用更宽类型或先判断 */
    printf("-(long)INT_MIN = %ld\n", -(long)INT_MIN);
    return 0;
}

无符号数的陷阱

for (unsigned i = n; i >= 0; i--) 是死循环:无符号数永远不小于 0,减到 0 后再减就是 UINT_MAX。

另外 sizeof 返回 size_t(无符号),if (x - 1 < 0) 之类的写法在有符号/无符号混用时会被隐式转换为无符号,导致判断失效。

十一.2 定点数与浮点数

对比项定点数(Fixed-Point)浮点数(Floating-Point)
表示小数点在固定位置符号 + 阶码 + 尾数
范围小极大/极小
精度绝对精度均匀相对精度均匀(有效数字固定)
硬件简单、快、省电复杂,需对齐、规格化、舍入
典型用途DSP、金融(用整数分表示)、嵌入式科学计算、图形学、机器学习

十一.3 IEEE 754 拆位分析

单精度(binary32,共 32 位)与双精度(binary64,共 64 位):

项目单精度 float双精度 double
总位数3264
符号位 11
阶码位 8(偏置 Bias = 127)11(偏置 Bias = 1023)
尾数位 2352
有效精度24 位(隐含前导 1)53 位
十进制有效位约 7 位约 15~16 位
最大阶码 254 − 127 = 1272046 − 1023 = 1023
规格化范围

规格化数的真值公式:

阶码 尾数 含义
非规格化数(Subnormal),真值
任意规格化数
全 1
全 1NaN(Not a Number)
"""ieee754.py —— 手动拆解 IEEE 754 单/双精度,并演示精度陷阱"""
import struct


def decode_float32(value: float) -> dict:
    """把 Python float 截断为单精度后拆位"""
    bits = struct.unpack(">I", struct.pack(">f", value))[0]
    sign = (bits >> 31) & 0x1
    exp = (bits >> 23) & 0xFF
    frac = bits & 0x7FFFFF

    if exp == 0:
        mantissa, exponent, kind = frac / (1 << 23), 1 - 127, "subnormal" if frac else "zero"
    elif exp == 0xFF:
        mantissa, exponent, kind = (1 + frac / (1 << 23)) if frac else 0.0, 128, "inf/nan"
    else:
        mantissa, exponent, kind = 1 + frac / (1 << 23), exp - 127, "normal"

    return {"bits": f"0x{bits:08X}", "sign": sign, "exp_raw": exp,
            "exp": exponent, "frac": frac, "mantissa": mantissa,
            "kind": kind, "value": (-1) ** sign * mantissa * 2.0 ** exponent}


if __name__ == "__main__":
    for v in (0.15625, -2.5, 0.1, 1e-45):
        d = decode_float32(v)
        print(f"{v!r:>10} -> bits={d['bits']} sign={d['sign']} e={d['exp']} "
              f"1.f={d['mantissa']:.6f} kind={d['kind']} 还原={d['value']!r}")

    # 经典陷阱:0.1 + 0.2 != 0.3
    print("\n0.1 + 0.2 =", repr(0.1 + 0.2))            # 0.30000000000000004
    print("0.1 + 0.2 == 0.3 ?", 0.1 + 0.2 == 0.3)      # False
    print("容差比较:", abs((0.1 + 0.2) - 0.3) < 1e-9)  # True

    # 大数吃小数:数量级差超过有效位就会丢
    big = 1e16
    print("\n1e16 + 1.0 - 1e16 =", repr(big + 1.0 - big))   # 0.0(1.0 被吃掉)

    # 累加顺序影响结果
    total_a = sum([0.1] * 10)
    total_b = sum(sorted([0.1] * 10, reverse=True))
    print("累加 0.1 十次 =", repr(total_a), repr(total_b))

浮点的三个必知坑

1. 不要用 == 比较浮点数,用相对/绝对容差,例如 。

2. NaN 不等于自身:nan != nan 为真,判 NaN 要用 math.isnan。

3. 浮点不满足结合律:,所以并行归约(如多线程求和、GPU 求和)结果与单线程不一定逐位相同。

十一.4 溢出(Overflow)判定

对补码加法 (同号相加才可能溢出),设 为符号位进位、 为最高数值位进位:

另一等价判据:两正数相加得负数,或两负数相加得正数,即

十二、怎么用:把知识落到工程

目标具体做法背后的原理
提高缓存命中率用连续内存容器(数组/std::vector)、减少指针跳转空间局部性
减少分支惩罚用无分支写法或让分支高度可预测控制冒险与分支预测
减少浮点误差用 Kahan 求和、整数分表示货币IEEE 754 舍入
避免对齐问题结构体成员按大小从大到小排列内存对齐与填充
批量 IO 更快一次读大块而不是逐字节DMA 与系统调用开销
判断优化值不值先 profile 得 ,再套 Amdahl 定律Amdahl 定律
# 在 Linux 上查看真实硬件参数(这些数字决定了你的优化空间)
lscpu                      # CPU 型号、核心数、频率、各级 Cache 大小
cat /proc/cpuinfo | head -30
getconf LEVEL1_DCACHE_LINESIZE   # L1 数据 Cache 行大小,通常是 64
getconf LEVEL1_DCACHE_SIZE
lscpu | grep -i cache

# 查看内存与 NUMA 拓扑(多路 CPU 时跨 NUMA 访存延迟翻倍)
numactl --hardware
free -h

# 用 perf 看真实的 Cache Miss(需要 root 或调整 perf_event_paranoid)
perf stat -e cache-references,cache-misses,cycles,instructions ./your_program

# 用 dd 感受磁盘顺序/随机性能差异(注意:会写文件,确认目标路径)
dd if=/dev/zero of=/tmp/testfile bs=1M count=1024 oflag=direct   # 顺序写
dd if=/dev/zero of=/tmp/testfile bs=4k  count=256000 oflag=direct # 小块写,明显更慢

编译器也会用这些知识

-O2 会做循环展开(利用指令级并行)、循环分块(利用局部性)、自动向量化(利用 SIMD)。

当你手写「优化」反而更慢时,先看 gcc -O2 -fopt-info-vec 输出的向量化报告,或对比反汇编。

十三、注意事项与常见坑

十个高频错误

1. 把「主频高」等同于「性能好」。iPhone 的 3 GHz 与服务器的 3 GHz 性能可以差几倍,取决于 IPC(每周期指令数)。

2. 用 MIPS 跨架构比较。MIPS 对 RISC 天然有利,没有任何跨平台可比性。

3. 忽略缺失率与缺失代价的乘积关系。AMAT 里两项是相乘的,只优化一项可能毫无感觉。

4. 以为增加 Cache 一定提速。工作集远超容量时只会增加「容量缺失」的代价,还可能拉长命中时间。

5. 以为流水线级数越多越快。深流水线在分支密集代码上会因冲刷而变慢,且功耗飙升。

6. 有符号溢出当正常回绕用。C/C++ 中有符号溢出是 UB,编译器可能据此做任意优化,务必改用无符号或显式检查。

7. 用 float 存金额。二进制浮点无法精确表示 0.1,多次累加后误差累积,应使用定点整数分或 decimal。

8. 忘记 Cache Line 是 64 字节。两个线程各自写同一 Cache Line 中的不同变量会引发伪共享(False Sharing),性能骤降。

9. 忘记内存对齐。某些架构(老 ARM、部分 DSP)不允许非对齐访问,直接触发异常。

10. 不看硬件就谈优化。没有 profile 数据的优化都是猜测,Amdahl 定律会毫不留情地惩罚猜错的人。

/* false_sharing.c —— 伪共享演示:两个线程写同一 Cache Line 里的不同变量 */
#include <pthread.h>
#include <stdio.h>

typedef struct { long value; } shared_counter_t;

/* 加 padding 把两个变量隔开到不同 Cache Line(典型 64 字节) */
typedef struct { long value; char pad[64 - sizeof(long)]; } padded_counter_t;

static shared_counter_t   s_shared[2];
static padded_counter_t   s_padded[2];

static void *bump_shared(void *arg) {
    long *p = arg;
    for (long i = 0; i < 100000000L; i++) __atomic_fetch_add(p, 1, __ATOMIC_RELAXED);
    return NULL;
}

int main(void) {
    pthread_t t1, t2;

    pthread_create(&t1, NULL, bump_shared, &s_shared[0].value);
    pthread_create(&t2, NULL, bump_shared, &s_shared[1].value);
    pthread_join(t1, NULL); pthread_join(t2, NULL);

    pthread_create(&t1, NULL, bump_shared, &s_padded[0].value);
    pthread_create(&t2, NULL, bump_shared, &s_padded[1].value);
    pthread_join(t1, NULL); pthread_join(t2, NULL);

    /* padded 版本通常明显更快:两个变量不再共享同一 Cache Line */
    printf("shared=%ld, padded=%ld\n", s_shared[0].value + s_shared[1].value,
                                       s_padded[0].value + s_padded[1].value);
    return 0;
}

十四、练习题

基础题

1. 用 8 位补码计算 ,写出二进制过程并判断是否溢出。

(答案:、,相加得 ,舍去最高进位后为 ;

两个负数相加结果仍为负数,未溢出。 位补码范围为 , 在范围内)

2. 某机器主频 2.5 GHz,程序共 条指令,平均 CPI 为 1.6。求 CPU 时间与 MIPS。

(答案: s;

)

3. 将十进制 表示为 IEEE 754 单精度浮点的十六进制形式(写出拆位过程)。

(答案:,符号位 ,阶码 ,

尾数 ,

合并为 1 10000001 10010000000000000000000,即 0xC0C80000)

进阶题

4. 32 位地址,Cache 容量 32 KB,块大小 64 B。

(a) 直接映射时行号、标记、偏移各多少位?

(b) 8 路组相联时组号、标记、偏移各多少位?

(c) 若 L1 命中时间 1 ns、缺失率 4%、内存 90 ns,求 AMAT;若把缺失率降到 3%,AMAT 改善百分之几?

(答案:(a) 偏移 6 位、行号 位、标记 位;

(b) 组数 ,组号 6 位、标记 20 位、偏移 6 位;

(c) ns;降为 3% 后 ns,

改善 )

5. 五级流水线,各阶段耗时分别为 2、1、2、2、1 ns。

(a) 时钟周期由什么决定?

(b) 执行 1000 条指令时,流水线相对顺序执行的加速比是多少?

(c) 若 20% 的指令是分支且预测准确率 80%,每次预测失败冲刷 2 个周期,重新估算加速比。

(答案:(a) 由最慢阶段决定, ns;

(b) 顺序执行 ns,流水线 ns,加速比 ;

(c) 预测失败 次,额外冲刷 个周期,

流水线时间 ns,加速比 ——分支预测失败吃掉了约 7% 的收益)

思考题

6. 某程序 40% 时间在做可以完美并行化的计算,其余 60% 必须串行。用 8 核并行后整体加速比是多少?要拿到 2 倍加速,最多允许多少串行比例(假设并行部分无限快)?

(答案: 倍;

由 得 ,即串行比例不能超过 50%)

7. 为什么现代 CPU 既要分离 L1 指令/数据 Cache,又要共享 L3?分别从「结构冒险」与「多核通信」两个角度解释。

(要点:L1 分离是为了让取指与访存在同一周期内并行,消除结构冒险,且指令流与数据流可各自优化

——指令流看重顺序与预取,数据流看重局部性;L3 共享则让多核之间的数据传递不必走到内存,

一个核写入的数据能被另一个核在 L3 命中,它也是 MESI 等缓存一致性协议的工作场所,共享还提高了容量利用率)

8. 如果让你给一个「遍历 1000 万条记录的链表」的程序做优化,你会先做什么测量?为什么单纯提高 CPU 主频可能完全没有效果?

(要点:先用 perf stat 看 cache-misses 与 cycles、用 perf record 找热点。

链表节点分散在堆上,每次 next 几乎必然 Cache Miss,瓶颈是内存延迟而不是计算,

CPU 大部分时间在等内存,提高主频只增加空转的周期数而不缩短等待时间。

有效优化是改数据结构:用连续数组、按访问顺序重排节点、把 AoS 改成 SoA,或加软件预取,

把「随机访问」变成「顺序访问」以利用空间局部性)

十五、常见问题 FAQ

Q1:学组成原理对写业务代码有什么用?

三个立刻可用的收益:① 知道为什么批量操作比逐条快(IO 与网络往返开销);② 知道为什么并发写共享变量会出错(读-改-写非原子);③ 知道为什么数据结构选型会影响性能(局部性与 Cache Line)。

具体到 数据结构-哈希表 的装载因子、数据库原理 的页大小,背后全是同一套存储层次逻辑。

Q2:Cache 和虚拟内存是一回事吗?

不是。Cache 由硬件自动管理,对程序员完全透明,粒度是 Cache Line(64 B);

虚拟内存由操作系统 + MMU 管理,粒度是页(4 KB 常见),解决的是地址空间隔离与容量扩展问题。

二者都用「局部性 + 分块 + 映射表」的同一套思想,是同一个设计范式在不同层级的体现。详见 操作系统 的内存管理章节。

Q3:为什么 i++ 在多线程下不安全?

因为 i++ 对应「load → add → store」三条(或更多)指令,两个线程可能都读到旧值再各自写回,导致更新丢失。

这属于组成原理层面的非原子操作问题,解决方案(互斥锁、原子指令、CAS)属于 操作系统 的并发范畴。

硬件提供了 lock 前缀、LDREX/STREX、CAS 等原子原语,上层同步机制都建立在其上。

Q4:为什么推荐「按大小降序排列结构体成员」?

因为编译器要保证每个成员按自身对齐要求存放,会在成员间插入填充字节(Padding)。

把大成员放前面、小成员放后面,能把填充降到最少,减少内存占用,也让数组中的对象更紧凑、更利于 Cache 命中。

Q5:学习顺序上,先看组成原理还是先看操作系统?

建议先看本篇前六章(数据表示、CPU、存储层次),建立「硬件怎么跑代码」的直觉,

然后读 操作系统,会顺畅很多。反过来先读操作系统的内存管理,容易觉得「页表为什么这么设计」没有动机。

相关笔记

  • 操作系统:本篇的进程、线程、内存管理、IO 模型在操作系统层如何落地
  • 计算机网络:网卡、DMA、中断在收包路径上的完整协作
  • 数据结构-哈希表:装载因子与哈希冲突的硬件代价(Cache 不友好的随机访问)
  • 算法-复杂度分析:大 描述的是指令数,真实时间还要乘上 CPI 与访存代价
  • 数据库原理:页、缓冲池、B+ 树设计本质上是在迎合存储层次
  • 00-索引、学习路线图:不知道下一步学什么时看这里

参考来源

  • Intel® 64 and IA-32 Architectures Software Developer's Manual(指令集与架构权威手册):<https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html>
  • Arm Architecture Reference Manual 与开发者文档(RISC 流水线、异常模型):<https://developer.arm.com/documentation>
  • Linux 内核文档(内存管理、DMA、CPU 缓存相关文档目录):<https://www.kernel.org/doc/html/latest/>
  • lscpu(1) / perf-stat(1) 手册页,用于实测各级 Cache 与性能计数器:<https://man7.org/linux/man-pages/man1/lscpu.1.html>、<https://man7.org/linux/man-pages/man1/perf-stat.1.html>
  • IEEE 754-2019 浮点算术标准(IEEE Standard for Floating-Point Arithmetic):<https://standards.ieee.org/ieee/754/6210/>
  • Patterson & Hennessy, Computer Organization and Design(流水线、Cache、Amdahl 定律的经典教材依据)

版本提示

各级 Cache 容量、流水线深度、总线频率等属于硬件实现细节,不同代际产品差异很大,

具体数字请以厂商官方最新文档与 CPU 数据手册为准。