Course index · Previous: Virtual Memory

I/O Polling

轮询机制

以及这里的andi是按位与，就是判断末位是否为1，为0就一直循环

polling一个disk会占用非常多的cpu时钟周期，所以我们对于从disk读取数据不应采用polling 轮询的效率不高

I/O Interrupts

在 PIO 模式下，外部设备和主内存（Main Memory）之间是不能直接讲话的。每一个字节的数据搬运，都必须由 CPU 亲自执行 lw (Load Word) 和 sw (Store Word) 指令来完成。 CPU 先把数据从外设读到自己的寄存器里，然后再写到内存里。

缺点：

• 浪费 CPU 算力 (CPU has to execute all transfers…)
• 严重的速度不匹配 (Device speeds don’t align…)
• 极高的能耗代价 (Energy cost of using beefy general-purpose CPU…)

Direct Memory Access (DMA)

可以说DMA就是CPU雇的一个打工人，在上述过程中，CPU只会接受到两次Interrupt：开始传输、结束。在数据传输过程中，CPU可以做别的事情

Parallelism

Flynn Taxonomy（弗林分类法）

软件的设计方式与硬件的物理架构是完全独立的两个维度

硬件维度的并行：取决于物理上CPU有几个核心 软件维度的并行：取决于代码的写法

弗林分类法（Flynn’s Taxonomy）。

它根据指令流（Instruction Stream）和数据流（Data Stream）的数量，将计算机架构分为四类：

• SISD (单指令单数据 - 对应上图的 Pentium 4)
• SIMD (单指令多数据 - 比如 CPU 里的向量指令集 AVX，或者 GPU 的核心原理)
• MISD (多指令单数据)
• MIMD (多指令多数据 - 对应上图的 Core i7 等现代多核 CPU)

SIMD Architecture

当你的程序中有大量相同类型的数据，且需要对它们做一模一样的操作时，就存在数据级并行。(Data-Level Parallelism)

硬件将 4 个 32 位的数字（X0 到 X3）像装箱子一样“打包”装进这一个超长寄存器里

XMM register是一个大宽度寄存器

Multicore

为什么需要多核心？ 为了提升perfrormance，但是提升时钟频率已经到头了

Thread

Thread：顺序执行的一系列指令流

硬件线程：它是 CPU 中真正能够拉取并执行指令的物理实体。它包含了真实的硅片电路，如运算器、物理寄存器堆等。

• 数量限制：数量是非常有限且固定的。比如我们常说一台电脑是“8核16线程”（支持同步多线程/超线程技术），这就意味着这台机器在物理层面上，最多只能同时提供 16 个硬件线程。
• 类比：它们就像是共享办公室里真实存在的“办公桌”，只有坐在办公桌前才能干活。

软件线程：它是操作系统（或应用程序）创建的一系列指令

Multithreading

Physical CPU就是传统我们理解的物理硬件CPU核心 Logical CPU：硬件线程，一个cpu核心能有超过一个硬件线程，所以说Logical CPU > Physical CPU

logical threads就是上述的一个核心有多个硬件线程，因为它本质上是“填补物理核心的空闲时间”（比如等内存时切换线程），所以它不能让性能翻倍

OpenMP

一个C语言的扩展，用于处理

可以看到右侧的 `thread 0, i = 0` 之后紧跟着是 `thread 1, i = 3`。这正是多线程并发执行的经典现象。因为 4 个线程在物理核心上是独立且同时（或交替）运行的，它们谁先跑到 `printf` 这一行，谁就把字打在屏幕上。这种不可预测性提醒我们：**在多线程里，绝对不能依赖代码的物理顺序来假设执行顺序。**

Example： Computing $\pi$

为了避免上述的“更新丢失”，我们必须保证同一时刻只能有一个线程去修改 sum。如果程序员采用最原始的加锁机制（比如互斥锁 Mutex 或临界区 Critical Section）把 sum += ... 这行代码包起来：

• 虽然答案算对了，但多线程每次循环到这里时，都必须排队，一个接一个地执行累加。
• 这就导致原本应该并行的代码，在这里变成了串行（顺序）执行，彻底抵消了多线程带来的性能优势。

修改后的代码如上图

pi += sum[id]这行代码会导致数据竞争，导致“更新丢失”，很多线程的 sum[id] 根本没被真正加进 pi 里，所以最终算出来的 π 值（3.1384…）比正确值小。

Synchronization

仅仅在C语言的层面上无法使用Lock解决数据竞争问题，比如下面这个例子：

（上图的代码y坐标表示时间，从上到下依次发生） 两个threads同时发现锁空闲，想要set lock，此时lock会被两个thread set

Hardware Synchronization

上述的amoadd指令的3个细分步骤，其实是一个原子指令，它拥有绝对的不可分割性

li t0, 1加载立即数：将1加载到register t0

在不可打断的一个 CPU 时钟周期内，硬件强行把 t0 里的 1 塞进内存的锁里，同时把内存里原本的值拔出来，放进了 t1 里。

这段代码的精妙之处在于它“先斩后奏”。它不管三七二十一，直接用原子操作把锁设为 1。判断自己是否抢锁成功的关键，全在那个被替换出来的旧值 t1 身上：

• 情况 A（抢锁成功）：如果被换出来的 t1 里面的值是 0。说明在这一瞬间之前，锁是空闲的。你成功把 0换成了 1。恭喜，你拿到了锁！
• 情况 B（抢锁失败）：如果被换出来的 t1 里面的值是 1。说明早有别的线程把锁占了。虽然你也霸道地往内存里写了个 1（把别人的 1 覆盖成了 1，状态没变），但通过检查换出来的旧值，你发现自己来晚了，获取锁失败。

上述critical action表述的就是对共享变量的读写

使用OpenMP创建lock来规避数据竞争，当然也有更简洁的语法：

• 这个函数返回的并不是一个绝对的标准时间戳（比如 1970年1月1日至今的秒数），而是从过去某个“任意参考点”开始计算的秒数（类似于电脑开机到现在的时间）。
• 用于测量墙钟时间

Shared Memory and Caches

SMP 架构选择让所有的处理器/核心共享同一个统一的物理内存地址空间。

上面的两张图引入了缓存一致性问题，cpu1,cpu2都需要用到address为1000的值（此处为20），因此他们从memory中获取，在cache中copy了一份。然后cpu0修改了address为1000的值为40，那么现在cpu1,cpu2里cache的值就是错的了

Cache Coherency

为啥把这个当一级标题，因为重要！

Big Idea：

• 读操作随便分享 (If only reading…)：如果大家都只是读取数据（比如 P1 和 P2 都读地址 1000 的值 20），那绝对安全。多个核心可以同时拥有同一个地址的副本。
• 写操作必须广而告之 (If a processor writes…)：一旦某个核心（比如 P0）想要修改这个数据，它绝不能偷偷摸摸在自己的 Cache 里改。它必须通过底层的互连网络（总线）通知其他所有人：“喂！我要改地址 1000 的数据了！”

Snoop缓存

• 架构师的工作: 共享内存 → 保持缓存值一致(coherent)

• 想法: 当任何处理器缓存缺失(miss)或写入(write)时，通过互连网络通知其他处理器 如果只是读，那么许多处理器都可以有副本(copies) 如果处理器写入，则使任何其他副本无效(invalid)

• 写入来自一个处理器的事务，其他缓存“snoopy”公共互连检查它们持有的标签 使在其他缓存中具有相同地址且修改过的任何副本无效

• Snoopy缓存标签是双端口的 (Dual-ported)” 这是这张PPT在硬件实现上强调的重点。为了让监听机制高效运作，缓存的标签和状态记录组（Tags and State）必须配备两个访问端口。

这两个端口的分工如下：

• 左侧端口（面向 Processor）： 这是常规的缓存工作端口。处理器（Processor）通过这里发送地址（A）、读写控制信号（R/W）和数据（D），进行日常的指令和数据存取。
• 右侧端口（面向共享总线）： PPT中标记为 Snoopy read port attached to Memory Bus。这是一个专门用于监听的只读端口。它连接到共享内存总线上，实时接收其他处理器发出的地址（A）和读写信号（R/W）。
• 上方输出（作为总线主控）： PPT中标记为 Used to drive Memory Bus when Cache is Bus Master。当当前的处理器遇到缓存未命中（Cache Miss），或者需要将修改后的数据写回主存时，这个缓存控制器就会接管总线（成为 Bus Master），向外发送地址和读写请求。此时，其他处理器的“右侧端口”就会监听到这个请求。

readmiss这里的意思：

• Read miss (读缺失)：CPU 需要读取某个数据，但在自己的缓存（Cache）里没找到。
• Dirty copy (脏副本)：在多核系统中，另一个 CPU 的缓存里有这个数据，并且它被修改过了。这意味着，那个 CPU 缓存里的数据是全系统最新的，而此时主存（内存）里的数据是没来得及更新的旧数据。
• Write back (回写)：把缓存里最新修改过的数据，同步写回到主存里。

MSI

• 工作机制： 当一个 CPU 要读数据时，数据被加载并标记为 S (共享)。如果要写数据，必须先通知所有其他拥有该数据的 CPU，让它们把状态变成 I (无效)，然后自己才能把状态变成 M (修改) 并写入。
• 致命痛点（为什么需要演进）： 假设 CPU A 读取了一个数据（状态为 S），并且只有 CPU A 读取了它。紧接着，CPU A 想要修改这个数据。在 MSI 协议下，即使只有 A 拥有这份数据，它从 S 变成 M 的过程中，也必须向总线发一次广播（Invalidate 信号）。这种无意义的广播严重浪费了总线带宽。

MESI

为了解决 MSI 中“单机读写还要发广播”的痛点，引入了 E (Exclusive, 独占) 状态。

• 工作机制： 当 CPU A 读取一个数据，如果系统发现只有 CPU A 读取了，就会把它标记为 E (独占)，而不是 S。
• 解决的痛点： 此时如果 CPU A 想要修改这个数据，因为它是 E 状态，CPU A 知道绝对没有别人在用它，所以它可以悄悄地把状态从 E 变成 M，直接写入，不需要在总线上发任何广播。这极大地减少了串行程序在多核环境下的总线压力。

MOESI缓存一致性协议：

对缓存的内存访问是： Modified (in cache) 修改 Owned (in cache) 拥有 Exclusive (in cache) 独占 Shared (in cache) 共享 Invalid (not in cache) 作废

兼容性矩阵： 我们可以把这个矩阵看作是多核 Cache 之间的“关系图谱”。假设我们探讨的是同一个内存地址（比如地址 1000），行代表当前核心（Core A）的状态，列代表其他任意核心（Core B）的状态。勾叉代表是否能够同时出现。

伪共享

伪共享 (False Sharing)：缓存一致性协议追踪和作废数据的最小单位，不是单个变量，而是一整个“缓存块 (Cache Block / Cache Line)”。

如上图，明明cpu0和cpu1用的是不同的地址，但是他们在一个缓存块内，其中一个cpu改了，另一个cpu就会任务自己cache中的那个缓存块作废了，因此需要经常访问内存并且总线通信

• P0 写入 X：P0 修改了变量 X。根据我们上一节学的缓存一致性协议，P0 必须在总线上大喊：“我改数据了，你们手里的这个 32 字节的块全部作废！”
• P1 躺枪：P1 的 Cache 收到了作废信号。虽然 P1 根本不关心 X，它只关心 Y，但因为 Y 跟 X 坐在同一条“32字节的船”上，P1 手里包含 Y 的整个缓存块被无情地标记为 Invalid（作废）。
• P1 写入 Y：轮到 P1 要修改 Y 了。它一查 Cache，发现数据作废了（Cache Miss）！P1 被迫去总线上重新请求最新的块。拿到块后，P1 修改了 Y，并大喊：“我改数据了，你们的块作废！”
• P0 躺枪：P0 手里包含 X 的块又被作废了。
• 当 P0 再次想要修改 X 时，它又得去总线上要数据，然后再把 P1 踢下线……

避免方法：减少缓存块大小

通信失效 (Communication misses)：真共享和伪共享都是

这里如果sun[0],sum[1]在同一个cache block/line里，就会产生伪共享 因此要让相邻两个线程操作的sum数组元素要在不同的block，选yellow：Constant for size of blocks in doubles - 块大小所包含的 double 数量

目录缓存

这一页说的是当处理器核心数目迅速增加之后，由于任何cpu cache miss 时，必须探测每一个其他缓存 当处理器核心数量增加（比如从 4 核增加到 64 核），这种“大喊大叫”的机制会遇到两个致命瓶颈：

• 总线通信带宽 (Bus Bandwidth)： 总线是一条公共通道。如果 64 个核都在频繁地广播请求，这条公共通道很快就会拥堵不堪。
• 标签带宽 (Tag Bandwidth)： 这是经常被忽略的一点。其他核心接收到广播后，必须去查询自己的 Cache Tag（标签阵列）来判断自己是否拥有该数据。如果每秒收到海量的监听请求，Cache Tag 就会被这些查询操作占满，导致该核心自己正常的读写操作被阻塞。

Idea：统计表明，当你向全网广播“谁有数据 X？”时，绝大多数核心的回答都是“我没有”。这意味着耗费了巨量带宽和 Tag 阵列资源的广播，99% 都是无效操作。既然大多数情况都找不到，那么“按需精确点对点通信”而不是“无脑全量广播”才是解决之道。

• 内存行中这个状态字段会记录比如：当前到底有哪几个 CPU 核心把这块数据读进了自己的 Cache 里，以及它们是只读状态（Shared）还是已修改状态（Modified）
• Cache miss的流程变为：step1. 找内存中负责该地址的 Directory 控制器; step2: Directory 查了一下自己的表格，看看哪些核心有这个数据; step3 : 不广播，只招特定的几个核心，使用点对点通信
• 网络事务 （点对点通信）： 在大规模众核处理器（如 64 核、128 核服务器 CPU）中，核心之间是通过类似互联网的 Mesh 网络（网格网络）连接的。查找目录、索要数据，都变成了网络中带有源地址和目的地址的数据包（Packets）。这就彻底摆脱了传统共享总线的物理限制。

所以，必须创造一个 Pending（瞬态）来充当“过渡锁”。 当 CPU A 发出请求的那一刻，它立刻给自己挂上 Pending 状态。这个状态的作用是：

1. 防自己： 告诉自己的处理器核心：“数据在路上了，你先暂停（Stall），别读老数据。”
2. 防别人（处理并发）： 如果这段时间有别的网络包（比如别人的失效请求）找上门来，CPU A 看到自己是 Pending，就知道遇到了“并发撞车”。它不会盲目回复，而是会根据协议规则，把别人的请求缓存起来，或者让对方稍后重试（NACK）。

“dir是一组节点”意思就是，dir里面是一组cpu核心编号 TR、TW两个瞬态分别是Transient Read -> Write（从R(dir)到W(id)之间的状态），和Transient Write -> Read/Write（从W(id)到R(dir)之间的状态），触发场景如下

• TR(dir) - 等待作废确认 (Transient Read -> Write):

• 场景： 数据本来是好几个节点在共享读取 R(dir)，突然节点 A 说：“我要独占这块数据并修改它！”

• 动作： 主目录为了保证一致性，必须向原来在读取的那些节点（dir 集合）发送“作废（Invalidate）”请求。

• 状态含义： 在所有的作废确认回复（ACK）收齐之前，主目录进入 TR(dir) 状态。意思是：“我正在等这帮老读者把手里的书撕掉，等他们全回复我了，我再把独占权交给 A。”

• TW(id) - 等待数据写回 (Transient Write -> Read/Write):

• 场景： 数据本来被节点 B 独占修改了 W(B)。这时节点 C 跑来跟主目录说：“我想读这块数据。”

• 动作： 主目录自己手里的数据是过期的，它必须给节点 B 发消息：“B，赶紧把你改好的最新数据交出来（写回/Writeback）！”

• 状态含义： 在节点 B 把最新数据传回来之前，主目录进入 TW(id) 状态。意思是：“我正在等那个独占了数据的家伙把最新版本还给我，拿到手之后我才能转发给 C。”

总结与对比snoop缓存和目录缓存

• 一个例子展示了read miss中，目录缓存是怎么工作的。
• 注意这里到达DRAM之后，发现时R状态，那么memory中的数据是新鲜可用的，就直接拿memory中的数据就行了，不需要向其他 CPU 索要数据。

类似于cache line的结构，但是Memory Line 是“物理上松耦合（甚至分离）”的： 虽然我们在画图时，会把 Directory 信息画在 Memory 旁边，好像它们是一个整体结构。但在真实的硬件主板上，负责存储目录信息的 SRAM 控制器，和负责存储真实数据的普通 DRAM 内存条，往往是分离的（或者存在内存的不同区域）。它们只是通过相同的“内存物理地址”在逻辑上被关联起来。

这里的序列化，本质就是“排队法则”。 因为在没有总线的分布式网络里，消息是满天飞且不按先后顺序到达的。为了保证大家看到的最终结果是一致的，无论在 Cache 端还是 Directory 端，都必须利用“瞬态 (Pending states)”充当交通信号灯，强行把那些因为网络原因超车、乱序到达的请求按在原地等待，迫使整个系统一步一个脚印地“按顺序（序列化）”处理事务。

强调瞬态的重要性

通常 L1 Cache Line、L2 Cache Line 以及 Memory Line 的大小都是完全一致的（目前业界绝对的主流标准是 64 字节）

• 这里就是算出来缓存总共只有2M行之后，只在内存里用2M个memory line的状态位和共享向量来维护活跃行。
• • 引入 Tag： 因为现在账本只有 200 万行了，没法跟 256GB 内存的物理地址一一对应了。所以每个账本条目必须加贴一个 8 字节的 Tag（标签），写明“我这行记录的是内存里哪个地址的状态”。
• 新的单行开销： 现在的目录项变成了 8字节(Tag) + 16字节(位向量) = 24字节。单行开销变大了（$24 / 64 = 37.5\%$）。
• 最后ppt算错了，应该是：$2097152 \times 24 = 50,331,648$ 字节，等于 $49152$ KB，也就是 $48$ MB

内存一致性模型(Memory Consistency Model)

加速和缩放的类型(Types of Speedups and Scaling)

A. 问题的限制 (Problem Constrained) -> 强扩展 (Strong Scaling) / Amdahl 定律

• 核心思想： 总工作量（问题规模）是固定不变的。
• 目标： 疯狂加机器，只为了把这个固定的任务完成得越快越好（缩短执行时间）。
• 增加处理器数量和内存大小

$$S_{PC} = \frac{Time(1\text{ processor})}{Time(p\text{ processors})}$$

B. 时间的限制 (Time Constrained) -> 弱扩展 (Weak Scaling) / Gustafson 定律

• 核心思想： 我们能容忍的等待时间是固定不变的。
• 目标： 随着机器的增加，我们不强求把旧问题算得更快，而是把问题规模同比例放大，在相同的时间内做更多、更复杂的事情。
• 目标是增加问题规模
• 增加了处理器数量和内存大小

$$S_{TC} = \frac{Work(p\text{ processors})}{Work(1\text{ processor})}$$

生产者与消费者

在现代高性能硬件上，这段代码是错误的（或者说是不安全的）

• 寄存器 (Registers) - 存“值”的地方：
• xflag: 寄存器，存储 flag 的值（0 或 1）。
• xdata: 寄存器，存储 data 的值（你需要传输的具体数据）。
• 指针/地址 (Pointers) - 存“内存位置”的地方：
• xflagp: 寄存器，存储 flag 变量在内存中的地址。
• xdatap: 寄存器，存储 data 变量在内存中的地址。 生产者 (Producer)

1. sw xdata, (xdatap): 把我们要传的数据存入共享内存的 data 位置。
2. li xflag, 1: 把 1 这个数字存进 xflag 寄存器。
3. sw xflag, (xflagp): 把 1 写入共享内存的 flag 位置。

• 逻辑： 我先写数据，写完后再把 Flag 置为 1，告诉消费者“数据准备好了”。

消费者 (Consumer)

1. spin: lw xflag, (xflagp): 从共享内存的 flag 地址读出值，存入 xflag 寄存器。
2. beqz xflag, spin: 检查 xflag 是否为 0。如果是 0，说明生产者还没写完，跳转回 spin 处继续读。如果不是 0（即读到了 1），继续往下执行。
3. lw xdata, (xdatap): 既然 Flag 变 1 了，说明数据好了，从内存读取 data。

核心维度	Cache Coherence (缓存一致性)	Memory Consistency (内存一致性模型)
作用范围	单个内存位置（局部）	多个不同内存位置（全局）
解决的痛点	所有的处理器对同一个数据的修改顺序达成共识。	所有的处理器对所有数据的读写操作顺序达成共识。
底层实现/代表	Snoopy (总线监听), Directory (目录协议)	SC (顺序一致性), TSO, 弱一致性 (Relaxed)

顺序一致性 (Sequential Consistency, 简称 SC)。

Lamport 的原话非常严谨，我们可以把它翻译并拆解为两条必须同时满足的铁律：

• 铁律一（全局串行化）： “the result of any execution is the same as if the operations of all the processors were executed in some sequential order” 不管这些处理器在物理上是怎么并行的，它们最终的执行结果，必须看起来像是所有操作都被排成了一个全局的单步队列，大家排队一个接一个地执行。
• 铁律二（局部不乱序）： “and the operations of each individual processor appear in the order specified by its program” 在这个全局队列中，如果我们只挑出某一个特定处理器（比如 P1）的操作来看，P1 操作的先后顺序，必须和程序员在代码里写的一模一样。绝对不允许硬件擅自把 P1 的第二行代码提到第一行代码前面去执行。

大多数真正的机器都不是SC

存储缓冲区优化与TSO

Store Buffer 是一把双刃剑。它通过“异址重排”极大地提升了 CPU 性能，但也彻底粉碎了顺序一致性（SC）的美好幻想。正是因为它的存在，程序员才被迫发明了“内存屏障（Memory Fence）”去强行清空这个 Buffer，以保证多线程同步的正确性。

TSO（完全存储排序）模型的核心特征，就在 PPT 最上面那句话：允许按处理器对存储区进行本地缓冲 (Store Buffer)。

• 上图属于写后读 (Store-Load) 乱序。 这个命名规则是以“程序员写代码的顺序（Program Order）”为基准的，而不是以硬件偷偷改变后的实际执行顺序为准。上图是先sw再lw，所以是写后读
• TSO只允许写后读

• 强模型就是类似于SC，一致性强，对程序员极其友好。你写的代码是什么顺序，它就是什么顺序。；
• 弱模型就是顺序一致性弱，硬件段各种重排乱序，芯片可以设计得更简单、功耗更低、极限性能更高。代价是软件端写代码很难

---

Course index · Previous: Virtual Memory

Backlinks

• 6 Jul 2026
  Computer Organization Notes
• 6 Jul 2026
  Computer Organization: Virtual Memory