Lecture 10: Interconnection Networks
Lecture 10: Interconnection Networks
1. 章节标题与概述
Lecture 10: Interconnection Networks（互连网络）
本讲核心问题：当处理器核数从 4 个涨到 64、72 甚至上千个节点时，“谁和谁怎么连、消息怎么走、消息在网里存多少” 就成了整个系统的性能天花板。本讲要回答三件事：(1) 为什么共享总线（shared bus）不能扩展，必须换成由链路（link）和交换机（switch/router）组成的互连网络（interconnection network）；(2) 各种拓扑（topology）——总线、crossbar、ring、mesh、torus、tree/fat tree、hypercube、多级对数网络（multi-stage logarithmic / Omega）——在成本、延迟、二分带宽（bisection bandwidth） 上如何权衡；(3) 消息以什么粒度（message / packet / flit） 在网络里传输、用什么流控（flow control） 机制缓冲（circuit switching vs packet switching，store-and-forward vs cut-through vs wormhole，以及虚通道 virtual channel 如何对付 head-of-line blocking）。
- 涉及的主要硬件/软件机制：
- 硬件侧：网络节点（network node）、网络接口（network interface）、交换机/路由器（switch/router）、链路（link）；
Request bus（cmd + address）与Response bus（256 bit 数据 + 3 bit response tag）构成的总线协议；Intel Sandy Bridge 起引入的环形互连（ring interconnect，四条环：request / snoop / ack / 32 B data） 与 L3 slice；Intel Xeon Phi（Knights Landing）的 6×6 tile mesh 与 YX routing；Tilera GX、Oracle/Sun SPARC T2/T5（crossbar CCX）等真实芯片；包格式（header / payload / tail）、flit（flow control digit）、credit 流控、虚通道、escape VC。 - 软件侧：程序员无法直接”编程”互连网络，而是通过通信模式间接决定它是否成为瓶颈：消息大小（决定 α 还是 β 主导）、消息数量、通信的局部性（邻居交换 vs 全对全）、通信与计算的重叠（非阻塞 MPI）、以及分片（sharding）/ 局部性 是否让访问落在离自己近的 slice 上。
- 硬件侧：网络节点（network node）、网络接口（network interface）、交换机/路由器（switch/router）、链路（link）；
在并行计算知识体系中的角色：本讲直接建立在前几讲的一致性（cache coherence / directory coherence / snooping 的实现）之上——一致性协议的所有”监听请求、失效消息、数据回传”都要占用互连网络；也是后面”同步（synchronization）与无锁（lock-free）”的前置知识——一个被 64 个核抢的原子计数器，本质是人为在网络里造了一条总线。它把前几讲的”缓存层次（cache hierarchy）”从”抽象的一层一层”落实到”物理上靠什么线连起来”，也是异构计算（heterogeneity）、GPU 内的 shared memory/L2 通信、以及多机 MPI 通信的共同底层模型。
- 配套材料：
lectures/14_interconnects.pdf（抽取文本extracted/14_interconnects.txt，共 48 页 / 约 21 KB）：已公开，可在 https://www.cs.cmu.edu/~418/lectures/ 公开下载。讲义首页写的是 “Lecture 14: Interconnection Networks” 与 “CMU 15-418/15-618, Spring 2024”：这是讲义沿用历史学期版本的正常现象（讲次编号与学期字样会随年度重排），不是错误。按 Fall 2026 日程表（https://www.cs.cmu.edu/~418/schedule.html），本讲排在 Sep 16，为第 10 讲。本笔记的术语、示例与数字均以这份 48 页讲义为准。- 讲课录像（Panopto / YouTube）：Fall 2026 日程表中被注释隐藏，属未发布。
- Ed 讨论区、Autolab、Canvas：需登录，非公开。
- 部分讲座在 Fall 2026 尚未发布公开讲义（Performance Analysis / Profiling、Transactional Memory、AI in System Design 等）；其历史学期 PDF 位于
/afs/cs/academic/class/15418-*/public/之下，需要 CMU 登录，属未公开。 - Fall 2026 授课教师为 Brian Railing 与 Dimitrios Skarlatos；课程由 Kayvon Fatahalian 创建。
- 本笔记中用到的额外背景（α-β 延迟模型、Little’s law、KNL 网频假设等）均已显式标注为”本笔记补充”，与讲义原文区分。
2. 核心概念与硬件/软件架构图解
2.1 出发点：共享总线为什么会先赢后输
定义与目的：讲义 slide 2 给出了前几讲的基本系统设计——若干”处理器 + 私有 cache”节点，全部挂在同一条共享总线（shared bus） 上：一条 request bus 传
cmd + address（例如 40 bit），一条 response bus 传数据（例如 256 bit），外加 3 bit 的 response tag；总线上还有一个总线仲裁器（bus arbitrator） 决定这一周期谁说话。它的目的很朴素：用一套线把所有节点连起来，并且让”监听式一致性（snooping coherence）”变得极其容易实现——因为所有一致性消息天然广播到了所有节点。直观解释（”它是什么？”）：把总线想成一条只有单车道、还没有红绿灯的乡村公路。村子里只有两三户人家时，这条路又便宜又好用：谁要出门，喊一声（广播）所有人都听得到，不用挨家挨户通知（这正是 snooping 便宜的原因）。但车一多，问题就来了：(1) 所有车必须排队（contention）；(2) 整条路的通行能力是固定的，不随住户增加而增加（带宽不 scale）；(3) 路上挂的”负载”（电气负载 = 电容）随节点数增多而变大，于是时钟频率只能降下来、功耗还得上去（high electrical load = low frequency, high power）。
图 1：总线互连（slide 2 的基线设计）与它的三个致命伤
（A）共享总线
+---------+ +---------+ +---------+ +---------+
| Proc 0 | | Proc 1 | | Proc 2 | | Proc 3 |
| + Cache | | + Cache | | + Cache | | + Cache |
+----+----+ +----+----+ +----+----+ +----+----+
| | | |
===========+=============+=============+=============+==========> Request bus
| | | | (cmd + addr, 40b)
| | | | + 3b response tag
===========+=============+=============+=============+==========> Response bus
| | | | (data, 256b)
| | | |
+----+-------------+-------------+-------------+----+
| Bus Arbitrator | <- 每周期只有一对
+-------------------------+-------------------------+ 节点能说话
|
+-------+-------+
| Memory |
+---------------+
致命伤 1 争用 (contention) 所有节点抢同一组线，一次只能一对通信
致命伤 2 带宽上限 带宽固定，与节点数 N 无关（不 scale）
致命伤 3 电气负载 线越长、挂的节点越多 -> 频率下降、功耗上升
- 性能特征（关键操作与量化后果）：设总线时钟为
f、宽度为W字节、每次事务固定开销T_ovh，则总线能提供的总带宽 ≈ W·f，与 N 无关；N 个节点各自想要b字节/秒时，只有在N·b ≤ W·f时才可能满足，且每个节点的有效带宽是总带宽除以 N。这就是”总线不 scale”的量化表述。于是 slide 3 的转折点出现：把共享总线换成互连网络（interconnection network），而”今天这些历史上面向机柜、主板、多 socket 的互连问题，全部在片内重演”——讲义把它叫做 network-on-a-chip。
2.2 互连网络用来连什么、为什么重要
定义与目的（slide 4、5）：互连网络用于连接：(a) 处理器核与其他核；(b) 处理器与内存；(c) 核与 cache；(d) cache 与 cache；(e) I/O 设备。它重要，是因为它同时决定两件事：可扩展性（system scalability）——系统能做多大、加节点有多容易；以及性能与能效（performance & energy efficiency）——核/缓存/内存之间能多快通信、访存延迟有多长、通信本身花掉多少能量。
直观解释（”它是什么？”）：把多核芯片想成一座城市，核是工厂，cache 是仓库，内存是港口，互连网络就是道路系统。工厂再快，货送不出去也没用；而道路的造价（面积、功耗）与通行能力（带宽）往往互相矛盾，城市规划（拓扑选择）决定了这座城能长到多大。
slide 6 的现实证据：随着核数上升，片上互连的可扩展性越来越关键——从 Intel Core i7（4 个 CPU 核 + GPU）、NVIDIA Tegra K1（4+1 ARM 核 + GPU 核）、Tilera GX（64 核）、Intel Xeon Phi（72 核 x86），节点数一路涨上去，网络从”配角”变成”主角”。
能耗数量级（slide 47）：MIT RAW 研究处理器的实测中，互连能占到整颗芯片功耗的约 35%。这说明”通信是昂贵的（communication is expensive）”不只是延迟问题，还是能量问题——这也是今天 bufferless network、区域关断（turn on/off regions）、快慢双网（fast and slow networks）、光子片上网络（photonic NoC）等研究的动机。
2.3 术语（slide 8）
- 定义与目的：讲义先把四个基本名词钉死，后面的所有讨论都建立在它们之上：
| 术语 | 定义（slide 8） | 典型例子 | 直观类比 |
|---|---|---|---|
| Network node（网络节点） | 连到路由器/交换机上的网络端点 | processor cache、memory controller | 城市里的工厂/仓库（货物起点终点） |
| Network interface（网络接口） | 把节点接进网络的那层适配逻辑 | NI、网卡、片上网络端口 | 工厂的装卸货月台 |
| Switch / Router（交换机/路由器） | 把固定数量的输入链路连到固定数量的输出链路 | 5 端口片上路由器（N/S/E/W/Local） | 十字路口 |
| Link（链路） | 一束传输信号的线（bundle of wires） | 32 B 宽的数据环、片间 SerDes 通道 | 连接路口的一条马路（车道数 = 位宽） |
直观解释（”它是什么？”）：一个消息的旅程是：”节点产生请求 → 网络接口打包 → 进入路由器 → 沿链路一跳一跳前进 → 到达目的节点的网络接口 → 送到目的 cache/内存”。路由器不产生消息，只做转发（forwarding）和仲裁（arbitration）；网络接口负责”把节点内部的总线语言翻译成网络语言”。
性能特征：链路的带宽 = 位宽 × 频率（例如 32 B × 3.4 GHz = 108.8 GB/s）；路由器的吞吐受限于端口数和每周期能交换的 flit 数（通常 1 flit/端口/周期）；延迟则为”每跳的路由延迟 × 跳数 + 串行化时间”。
2.4 三个设计问题：拓扑、路由、缓冲与流控（slide 9）
- 定义与目的：设计一个互连网络，就是回答三个问题：
- Topology（拓扑）：交换机之间怎么用链路连。它影响路由（routing）、吞吐、延迟、实现复杂度与成本。
- Routing（路由）：一个消息如何从源走到目的。可以是静态的（static，预定路径） 或自适应的（adaptive，依据负载选路）。
- Buffering & flow control（缓冲与流控）：网络里存什么（整包？部分包？单个 flit？）、以及如何管理缓冲空间（无缓冲 vs 缓冲、credit 还是 on/off）。
直观解释（”它是什么？”）：把网络想成寄快递：拓扑 = 城市路网图；路由 = 快递员的选路规则（永远走”先南北后东西”？还是看哪条路堵就绕？）；缓冲与流控 = 中转站有多少货架、以及”货架满了还能不能收货”的规则。三者互相牵制：拼命加缓冲能提高吞吐但增加延迟和面积；自适应路由能绕开拥塞但可能引入死锁；拓扑越”富”（crossbar）延迟越低但 O(N²) 的成本直接压垮芯片面积。
- 性能特征（图 2）：延迟-负载曲线（slide 14）——本讲最重要的一张图
延迟 (latency)
^
| 饱和吞吐
| ____/ (saturation
| ____/ throughput)
| ____/ ^
| ____/ <-- 接近饱和后，
| ____/ 延迟急剧上升（缓冲耗尽、
| ____/ HOL 阻塞、反压传播）
| 零负载延迟 _______/
| (zero-load / idle latency =
| 拓扑 + 路由 + 流控 共同决定)
+---|------------------|----------------------------|-----------> 负载
| | (offered traffic, bits/s)
| |
拓扑决定的最小延迟 路由决定的吞吐上限 流控决定的饱和吞吐点
一般规律（讲义原话）：latency increases with load（延迟随负载上升）。
推论：只报一个"平均带宽"或"空载延迟"都是不完整的——
必须同时给出 (零负载延迟, 饱和吞吐) 两个数字，才算描述了这张网。
2.5 拓扑度量：用什么指标挑拓扑（slide 10–13）
- 定义与目的：
- Routing distance（路由距离）：两个节点之间路径上的链路数（跳数 hops）。
- Diameter（直径）：所有节点对之间路由距离的最大值（最坏情况延迟的依据）。
- Average distance（平均距离）：所有合法路径上路由距离的平均值（平均延迟的依据）。slide 的例子里
diameter = 6。 - Direct vs. Indirect（直接/间接网络）：直接网络中端点”坐在网络内部”，每个节点既是端点又是交换机（mesh 就是直接网络）；间接网络中端点只挂在网络边缘，中间全是专用交换机（crossbar、多级网络）。
- Bisection bandwidth（二分带宽）：把网络切成两个等大的部分，所有被切断链路的带宽之和（取最小割）。它是递归式拓扑最常用的性能指标。
- Blocking vs. Non-blocking（阻塞/非阻塞）：如果任意节点对都能同时连通而不冲突，就是非阻塞，否则是阻塞。
- 讲义对二分带宽的警告（务必记住）：”can be misleading as it does not account for switch and routing efficiencies“——它忽略了交换机内部竞争与路由效率，不是可达带宽的保证。
直观解释（”它是什么？”）：二分带宽想度量的是”把城市切成两半，两半之间所有跨城道路的总车道数“。它是判断”全对全通信能不能撑住”的关键：如果两半之间有 100 万居民却只有两条小路，那么任何”所有人都要和对面说话”的应用都会堵死。而”阻塞/非阻塞”则是问：”任意两个人同时出发，能不能都直达、不用让路？”
- 图 3：阻塞 vs 非阻塞（slide 13）——同一个网络，换个配对就阻塞
8 节点网络（左列与右列是同一批节点的两种画法，便于看路径）
slide 13 的两个场景：
场景 A：0->1 与 3->7 同时发送
0 ---\ /--- 1
1 ----\ /---- 2
2 -----[ SW-a ]----[ SW-b ]------ 3
3 -----/ \ \---- 4
... \ ...
两个连接走的是相互独立的开关 => 不冲突
场景 B：1->6 与 3->7 同时发送
0 ---\ /--- 1
1 ----\====> [ SW-a ] ==X== [ SW-b ] ====> 6 <-- 冲突！同一个开关上
2 -----/ \---- 3 要同时服务两个连接
3 ---------------------[ SW-a ]------+---- 7
^
两台不同的输入要同一个输出资源
=> 结论：这个网络是 BLOCKING（阻塞）的。
判据：非阻塞要求"任意配对都能通过独立开关连通"；
只要存在某个配对组合必须在同一个开关（或同一条链路）上相撞，就是阻塞网络。
2.6 拓扑家族：六种主干设计（slide 16–32）
- 直观解释总览：把拓扑想象成六种不同的城市路网规划：
- Bus（总线）：一条单车道村道（最简单、最便宜、最不 scale）；
- Crossbar（交叉开关）：超级立交枢纽，任意入口到任意出口都有独立匝道（最快、最贵，O(N²)）；
- Ring（环）：环城单环地铁线（便宜、简单，但坐半圈要坐 N/2 站）；
- Mesh（网格）：棋盘式方格街道（片上最容易画，跳数 O(√N)）；
- Torus（环面）：把棋盘卷起来成轮胎形，边界也连通（跳数、二分带宽都更好，但物理布线难）；
- Tree / Fat Tree（树 / 胖树）：树状分级的快速路，越靠根车道越多（对数延迟，可做到全二分带宽）；
- Hypercube（超立方体）：编号相差一个 bit 就能直达 → 对数延迟、对数度；
- Multi-stage logarithmic（多级对数网络，Omega/Butterfly）：像机场行李分拣系统，中间几级换乘，成本 O(N lg N)、延迟 O(lg N)。
- 各拓扑的要点（slide 17–31）：
- Bus：好——设计简单、节点少时性价比高、用监听实现一致性很容易；坏——争用、带宽受限（同一时刻只有一次通信）、电气负载高导致频率低/功耗高。
- Crossbar：每个节点与每个节点之间都有独立通路（非阻塞、间接网络）；好——O(1) 延迟与高带宽；坏——O(N²) 个开关，不可 scale、成本高、大规模仲裁困难。讲义明确指出”crossbar 的调度算法与高效硬件实现至今仍是活跃研究领域”，并追问”这个开关是什么？”——它本质是每个输入/输出交叉点上的小型选择开关。真实例子：Sun SPARC T2（8 核 + 8 个 L2 bank）与 Oracle SPARC T5（16 核 + 8 个 L3 bank），其中 crossbar（CCX）占用的芯片面积与一个核相当——这是”互连很贵”的最直观证据。
- Ring：好——简单、O(N) 成本；坏——延迟 O(N)、二分带宽是常数（每加节点都不增加，这是它的 scalability 硬伤）。真实例子：Intel Sandy Bridge 起的环形互连（四条环：request / snoop / ack / 32 B data；六个互连节点：四个 2 MB 的 L3 slice + system agent + graphics；每个 L3 bank 接环两次；3.4 GHz 下核到 L3 的理论峰值带宽约 435 GB/s——前提是每个核访问自己的本地 slice），以及 IBM CELL Broadband Engine（9 核）。
- Mesh：直接网络；呼应网格类应用的局部性；O(N) 成本；平均延迟 O(√N)；在芯片上容易布局（链路等长）；路径多样性（path diversity） 好（一个消息有很多条路可以走）。真实例子：Tilera 处理器与 Intel 原型芯片。KNL 的具体形态是 72 核、6×6 的 tile 网格（每 tile 2 核），采用 YX 路由：先在 Y 方向移动，然后”转弯”，再在 X 方向移动。
- Torus：相比 mesh，”节点在边缘还是在中间”的性能差异不再存在（新增绕回的链路避免了这个不公平）；仍然 O(N) 成本但比 2D 网格贵；路径多样性与二分带宽都更高；代价是复杂度更高——片上难以布局、链路长度不等。
- Trees：平面、层次化拓扑；像 mesh/torus 一样在流量有局部性时表现好；延迟 O(lg N)；用 fat tree（胖树） 缓解”根部带宽瓶颈”（越靠近根，链路带宽越高）。
- Hypercube：延迟 O(lg N)、度（radix）O(lg N)、链路数 O(N lg N)；历史上的例子是 80 年代 Caltech 的 64 核 Cosmic Cube（6 维超立方体） 与 SGI Origin。
- Multi-stage logarithmic：间接网络，终端之间要经过多级交换机；成本 O(N lg N)、延迟 O(lg N)；变体很多：Omega、butterfly、Clos 网络等。
- 图 4：拓扑画廊（讲义 slide 16–32 里的六种主干网络）
(1) BUS (2) CROSSBAR (N=8, 非阻塞，间接)
n0--n1--n2--n3 n0 ──┬──┬──┬──┬──┬──┬──┬── 0
| | | | │ │ │ │ │ │ │
+===+===+===+==== 共享线 ├──┼──┼──┼──┼──┼──┼── 1
每对 (in,out) 一个交叉点开关
成本 O(1) 线, 延迟/带宽 = 常数 成本 O(N^2) 交叉点, 延迟 O(1)
(3) RING (N=4) (4) 2D MESH (4x4, 直接网络)
0 --- 1 0--1--2--3
| | | | | |
3 --- 2 4--5--6--7
| | | |
成本 O(N), 延迟 O(N) 8--9-10-11
二分带宽 = 2 条链路 (常数!) | | | |
12-13-14-15
成本 O(N), 平均延迟 O(sqrt(N))
二分带宽 = k 条链路 (k=4)
(5) 2D TORUS（把 mesh 的边界卷起来） (6) FAT TREE (8 叶)
+--0--1--2--3--+ [root 层, 带宽最大]
| | | | | | =========
+--4--5--6--7--+ / \
| | | | | | [中间层] [中间层]
+--8--9-10-11--+ / \ / \
| | | | | | 0 1 2 3 4 5 6 7
+-12-13-14-15--+ 延迟 O(lg N), 可做 full bisection
每行每列首尾相连 越靠根链路越"胖"（更高带宽）
(7) 3 维 HYPERCUBE (N=8) (8) OMEGA / 多级对数网络 (N=8)
000 ----- 001 0 --\ /-- ... --\ /-- 0
| \ / | 1 --/ \-- ... --/ \-- 1
010 -- 011 | [lg N 级 2x2 开关]
| | | 成本 O(N lg N), 延迟 O(lg N)
100 -- 101 ...
编号只差 1 bit 的节点直连 变体: Omega / butterfly / Clos
延迟 O(lg N), 度 O(lg N), 链路 O(N lg N)
- 图 5：KNL 的 6×6 tile mesh 与 YX 路由（slide 27）
Intel Xeon Phi (Knights Landing)：72 核 = 6x6 tile 网格（每 tile 2 核）
外圈是 EDC / iMC（内存控制器）/ MCDRAM / OPIO / PCIe 等
+----+----+----+----+----+----+
|Tile|Tile|Tile|Tile|Tile|Tile| 消息路由: YX routing
+----+----+----+----+----+----+ (1) 先在 Y 方向走
|Tile|Tile|Tile|Tile|Tile|Tile| (2) "转弯" (turn)
+----+----+----+----+----+----+ (3) 再在 X 方向走
|Tile|Tile|Tile|Tile|Tile|Tile|
+----+----+----+----+----+----+ 例如 (x=1,y=4) -> (x=4,y=1):
|Tile|Tile|Tile|Tile|Tile|Tile| 先向上走 3 跳 (Y: 4->1)
+----+----+----+----+----+----+ 再向右走 3 跳 (X: 1->4)
|Tile|Tile|Tile|Tile|Tile|Tile|
+----+----+----+----+----+----+
|Tile|Tile|Tile|Tile|Tile|Tile| 维度顺序路由 (dimension-order)
+----+----+----+----+----+----+ 的通道依赖图无环 => 不会死锁
性能含义：平均跳数 ≈ 2k/3 = 4 跳 (k=6)，每跳约 1~2 个网络时钟；
路由确定性 => 路径唯一 => 热点流量无法绕行（无自适应能力）
2.7 拓扑对照表（slide 32 的复习表 + 本笔记补充列）
下表的前四列与 slide 32 的”Review: network topologies”表一致，后三列是本笔记为量化分析补充的（N = 节点数，k = √N，B = 单条链路带宽）：
| 拓扑 Topology | Direct/Indirect | Blocking | 成本 Cost | 延迟 Latency | 链路数 / 二分带宽 | 真实系统 |
|---|---|---|---|---|---|---|
| Bus | —（共享介质） | Blocking | O(1) 组线 | O(1) 但随 N 恶化 | 二分带宽 = 总带宽（且不随 N 增长） | 早期多核 front-side bus |
| Crossbar | Indirect | Non-blocking | O(N²) | O(1) | 二分带宽 = (N/2)·B | Sun SPARC T2 / T5（CCX） |
| Multi-stage log.（Omega/butterfly） | Indirect | Blocking（课堂讨论的那种；其他变体不一定） | O(N lg N) | O(lg N) | (N/2)·B | 大型交换机内部、CMOS 交换网络 |
| Ring | Direct | Blocking | O(N) | O(N) | 2·B（常数！不 scale） | Intel Sandy Bridge 起的 ring、IBM CELL |
| 2D Mesh (k×k) | Direct | Blocking | O(N)（2N−2k 条链路） | 平均 O(√N) | k·B | Tilera、KNL 6×6、Intel 原型 |
| 2D Torus (k×k) | Direct | Blocking | O(N)（2N 条链路，比 mesh 贵） | O(√N) | 2k·B | 部分 HPC 与片上研究原型 |
| Fat Tree (N 叶) | Indirect | 可做 Non-blocking | O(N lg N) | O(lg N) | 可做到 (N/2)·B（full bisection） | 大型机群/数据中心网络 |
| Hypercube | Direct | Blocking | O(N lg N) | O(lg N)，度 O(lg N) | (N/2)·B（成本效率最高） | Caltech Cosmic Cube、SGI Origin |
（表中 Bus / Ring / Mesh / Torus / Hypercube 的成本与延迟数量级均取自讲义；Crossbar 的”非阻塞、O(1)、O(N²)”与 Multi-stage 的”阻塞、O(N lg N)、O(lg N)”直接对应 slide 32 的复习表。）
2.8 通信粒度：message / packet / flit（slide 35–36）
- 定义与目的：
- Message（消息）：网络客户端（核、内存）之间传输的单位，可以用多个 packet 传。
- Packet（包）：网络的传输单位，可以用多个 flit 传。
- Flit（flow control digit）：包被切成的更小单位，是网络中流控与缓冲的最小粒度。
- Packet format（包格式）：Header（头） 含路由与控制信息，放在包开头以让路由器尽早开始转发；Payload/body（载荷） 是要传的数据；Tail（尾） 含控制信息（如错误校验码），放在末尾是因为发送方可以”边发边算校验和，最后追加”。
- 直观解释（”它是什么？”）：把”寄一整套书”想成：message = 一整套书、packet = 一个纸箱、flit = 箱子里的一本书。为什么不直接整箱整箱地搬？因为中转站的货架（buffer）有限，按”本”流转（flit 级流控）才能把有限的货架用出最大通行量。
| 粒度 | 谁的单位 | 类比 | 决定什么 |
|---|---|---|---|
| Message | 网络客户端（core/memory） | 一整套书 | 软件可见的通信单元（MPI 消息） |
| Packet | 网络传输单元 | 一个纸箱 | 路由决策的边界、校验的单位 |
| Flit | 流控/缓冲最小粒度 | 箱中的一本书 | 缓冲容量、流控开销、能效 |
- 图 6：包格式与卡片式布局
+----------------+---------------------------+----------------+
| HEADER | PAYLOAD / BODY | TAIL |
| 路由 + 控制 | 要传输的数据 | 控制信息(校验) |
+----------------+---------------------------+----------------+
^ ^
| |
放在最前：路由器读到头部就可以 放在最后：发送方"边发边算"
"提前转发"(start forwarding early) checksum，最后追加到包尾
一个 message 被切成多个 packet；一个 packet 被切成多个 flit：
MESSAGE [ pkt0 ][ pkt1 ][ pkt2 ] ...
PACKET [ H ][ B0 ][ B1 ][ B2 ][ T ] <- 例如 4 个 flit
FLIT ^ 单个 flit 是网络中缓冲/流控的最小单位
2.9 交换方式：circuit switching vs. packet switching（slide 34、38）
- 定义与目的：
- Circuit switching（电路交换）：发送前先建立完整通路（获取全部资源）——先”探测/建立路由”（reserve links），再发送全部数据。
- Packet switching（包交换）：为每个包单独做路由决策，每个包可能走不同的链路。
- 对比（讲义 slide 34 的原话归纳）：
| 维度 | Circuit switching | Packet switching |
|---|---|---|
| 建立阶段 | 需要 setup（probe），还需 teardown 释放资源 | 不需要 setup/teardown |
| 传输期带宽 | 高（没有逐包的链路管理开销） | 有动态交换逻辑的传输期开销 |
| 链路利用率 | 低（两条消息不能共用同一条预留链路，即使路径上某些资源已闲置） | 高（链路一空闲就能拿来传包） |
| 争用处理 | 预分配后传输期无争用，不需要缓冲 | 需要缓冲/丢弃/绕行等机制 |
| 消息大小 | 任意大小（通路建好后一直传） | 受包大小与缓冲约束 |
| 直观类比 | 打电话：先拨号接通（占线就等），通了就一直说 | 寄快递：每个包裹单独择路，随时可寄 |
| 代价 | setup 与 tear-down 的开销、低利用率 | 每包的交换开销、需要缓冲 |
- 讲义的处理方式（slide 38）：电路交换的要点被总结为”高粒度的资源分配“——沿整条网络路径预分配所有资源（跨多个交换机的链路）来为一条消息”建立一条流”；好处是传输期无争用因而无需缓冲、且消息大小任意；代价是建立/拆除开销与低链路利用率。本讲后续只考虑缓冲式（buffered）网络，但讲义也指出：近期研究在探讨无缓冲网络 + deflection routing（偏转路由） 作为更省电的片上互连。
2.10 缓冲式流控三兄弟：store-and-forward / cut-through / wormhole（slide 37、39–43）
- 定义与目的：当两个包同时要同一条输出链路时（slide 37 的争用场景），有三种选择：缓冲一个包晚点再发、丢弃一个包、改道一个包（deflection）。本讲只考虑缓冲。而”在哪里缓冲、缓冲到什么粒度”，就分出了三种流控：
- Store-and-forward（存储转发，以包为单位）：包被完整复制进交换机后才能走向下一节点；流控单位是整个包；因此每个路由器都要有容纳整包的缓冲。同一消息的不同包可以走不同路由，但同一个包内的所有数据必须走同一条路由。特征是每包延迟极高：
延迟 = 包在一条链路上的传输时间 × 网络距离（跳数）。 - Cut-through（直通，仍以包为单位）：交换机一收到包头就开始在下一段链路上转发（包头携带”这个包需要多少链路带宽 + 往哪走”的信息）；结果是传输延迟下降；但在高争用时 cut-through 会退化成 store-and-forward（因为下游被堵，整个包最终还是要被吸进缓冲）。
- Wormhole（虫洞）：包被切成更小的 flit，并以 flit 为缓冲与流控的最小粒度——这与前两者”包既是传输粒度又是流控/缓冲粒度”形成对比。规则是：路由信息只在 head flit 里；body flit 跟着 head 走；tail flit 收尾；head flit 一旦被阻塞，整个包就停下来；传输是完全流水化（completely pipelined） 的——对长消息而言，延迟几乎与网络距离无关。
- Store-and-forward（存储转发，以包为单位）：包被完整复制进交换机后才能走向下一节点；流控单位是整个包；因此每个路由器都要有容纳整包的缓冲。同一消息的不同包可以走不同路由，但同一个包内的所有数据必须走同一条路由。特征是每包延迟极高：
- 直观解释（”它是什么？”）：
- store-and-forward = 中转站必须把整辆集装箱卡车卸完、再装到下一辆车才发车；
- cut-through = 车头一到，就先让车头开上下一段路，车身随后跟进；
- wormhole = 一列火车：车厢（flit）排成一列前进，车头一停，整列车都停在轨道上——但也正因为如此，缓冲只需容纳几节车厢（flit），而不是整列车（整包）。
- 图 7：三种流控的时间-空间图（用讲义 slide 40 的单位模型：3 跳、包长 4 单位、每跳路由延迟 1 单位）
每格 = 1 个 flit 在一条链路上传输所需时间；包 = 4 flits
路径 = Src -> R1 -> R2 -> Dst（3 跳）；路由器延迟 = 1 格
t = 0 1 2 3 4 5 6 7 8 9 10 11 12
(a) STORE-AND-FORWARD（整包缓冲后再转发）
Src -> R1 [##][##][##][##] . . . . . . . .
R1 -> R2 . . . . [##][##][##][##] . . . .
R2 -> Dst . . . . . . . . [##][##][##][##]
完成于 t = 12 <=> 3 跳 x 4 单位 = 12 单位（每跳都要把整包传完）
(b) CUT-THROUGH（包头一到就开始转发）
Src -> R1 [##][##][##][##] . . . . . . . .
R1 -> R2 . [##][##][##][##] . . . . . . .
R2 -> Dst . . [##][##][##][##] . . . . . .
完成于 t = 6 <=> 3（流水填充）+ 3（其余 flit 跟进）= 6 单位
=> 比 store-and-forward 快 2 倍
(c) WORMHOLE（flit 级缓冲/流控；定时与 (b) 相同，但缓冲只需 flit 大小）
Src -> R1 [H ][B0][B1][T ] . . . . . . . .
R1 -> R2 . [H ][B0][B1][T ] . . . . . . .
R2 -> Dst . . [H ][B0][B1][T ] . . . . . .
^
t=2 快照：H 已到 R2，B0 在 link1 上，
B1/T 还在 Src 的缓冲里 —— 完全流水化
长消息时：T ≈ L/b + D * t_r，当 L/b >> D * t_r 时
=> 延迟几乎与网络距离 D 无关（讲义 slide 43 的思考题）
- 性能特征小结：
- store-and-forward 的延迟与距离成正比（
~D × L/b）； - cut-through 把延迟降到
~D × t_r + L/b，但坏情况下退化为 store-and-forward； - wormhole 在延迟上等价于 cut-through，但缓冲面积小得多（flit 而非整包），代价是head-of-line blocking（下一节）。
- store-and-forward 的延迟与距离成正比（
2.11 Head-of-line blocking 与虚通道（slide 44–46）
定义与目的：Head-of-line blocking（队头阻塞） 指：一个输入缓冲里排在队头的包因为它的目标输出链路忙而被堵住，导致排在它后面、本来可以去空闲链路的包也被一起堵住。Virtual channel（虚通道，VC） 的解法是：把一条物理通道上的输入缓冲切成多个独立缓冲（multiple buffers sharing a single physical channel），从而减少 head-of-line blocking——即”在单条物理通道上复用多个操作“（讲义引 Dally, ISCA 1990 的《Virtual Channel Flow Control》）。
直观解释（”它是什么？”）：想象超市只有一条结账队伍，队头顾客的会员卡出了问题要等经理（他的”输出链路”被占），后面所有只想刷卡走人的顾客也一起被卡住——这就是队头阻塞。虚通道就是把这排队伍分成几排（VC0 / VC1 …），队头卡住时，另一排的人可以先去空闲的收银台。注意收银台（物理链路）本身还是那几个，VC 只是让缓冲和仲裁解耦。
图 8：head-of-line blocking 与虚通道的对比（slide 44 / 45）
场景：某路由器的西向输入端口收到两个包
灰包（先到）要去东向链路 —— 但东向链路当前被别的包占用（busy）
蓝包（后到）只想去北向链路 —— 北向链路当前空闲
(a) 无虚通道：1 个输入缓冲 (b) 2 条虚通道：VC0 / VC1
+---------------------------+ +---------------------------+
| In(W) Buf: [灰灰灰] | <- 队头 | VC0 Buf: [灰灰灰] | 灰包仍等东向
| [蓝蓝蓝] | 卡住 | VC1 Buf: [蓝蓝蓝] | 蓝包可走北向
+-------------+-------------+ +------+--------------+-----+
| | |
只有队头能被仲裁 东向(忙: 灰包等) 北向(空闲: 蓝包走)
|
东向链路(忙) -> 灰包阻塞
北向链路(空闲) -> 白白浪费 结果：空闲链路被利用起来，
结果：吞吐损失、延迟上升 吞吐上升、延迟下降
- 虚通道的其他用途（slide 46）：
- 避免死锁（deadlock avoidance）：用来打破资源的循环依赖——例如让请求（request）与响应（response）走不同的虚通道以避免成环；“escape” VC 的做法是保留至少一条使用无死锁路由的虚通道（其余通道可以更激进）。
- 流量类别优先级（prioritization of traffic classes）：提供服务质量（QoS）保证，让某些虚通道的优先级高于其他（例如让同步消息/中断快过批量数据传输）。
- 图 9：死锁的环依赖与用虚通道打破它
(a) 通道依赖图出现环 => 可能死锁 (b) 两个 VC 拆环
VC0: 只允许 东 -> 北
VC 东向 ──────▶ VC 北向 VC1: 只允许 北 -> 东
▲ │ （两条 VC 是相互独立的资源）
│ ▼ 每个 VC 内部的依赖图无环
VC 南向 ◀────── VC 西向 => 不会形成循环等待
2.12 软件执行模型：程序员如何”感受”到互连网络
定义与目的：互连网络不暴露任何编程接口，程序员是通过通信模式与它打交道的。同一个网络面对两种截然不同的流量会给出完全不同的性能：邻居交换（stencil halo exchange） 只用到局部链路（mesh 上平均 1 跳），全对全（all-to-all / allreduce） 则要求把二分带宽吃满。
直观解释（”它是什么？”）：程序里的通信模式就是给网络下的”订单”：要多少条消息、每条多大、发给谁。网络对”少量大消息”和”海量小消息”的答复完全不同（这正是下一节 α-β 模型的含义），对”邻居通信”和”全局通信”的答复也完全不同（这正是二分带宽的含义）。
图 10（软件执行模型）：3D 7 点 stencil 的 halo 交换如何映射到网络
(A) 进程/线程网格映射到互连拓扑（8x8x8 = 512 ranks 映射到 8x8 的 2D 片间网络）
每个 rank 拥有 64^3 的局部子域；每步需要与 6 个邻居交换 1 层 halo
+-------+-------+-------+ 每个 rank 的局部子域 64^3
| rank | rank | rank | 需要 halo: 6 个面,
| (0,1)| (1,1)| (2,1)| 每面 64x64 个 double
+-------+-------+-------+ = 64*64*8 = 32 KB
| rank | rank | rank | 6 面合计 192 KB / rank / 步
| (0,0)| (1,0)| (2,0)|
+-------+-------+-------+ <-- 通信量正比于"表面积"
<--- 邻居交换只走 1 跳 ---> 计算量正比于"体积"
(表面-体积比 ∝ 1/L)
(B) 一个迭代步的时间轴：先发射通信，再算内部，最后算边界（重叠）
t=0 t=1 t=2 t=3 t=4
|-- pack 发送缓冲 --|
|-- MPI_Isend x 6 (把消息注入网络) --|
|-- 计算内部区域 inner --|
|-- MPI_Waitall --|
|-- 计算边界 halo --|
要点：网络在"计算内部区域"的那些周期里是忙碌的（overlap），
如果先 Waitall 再算，就把通信延迟完整暴露在关键路径上（Span 变长）
- 性能特征：邻居交换模式下，网络只需提供
6 × 每 rank 消息大小 / 每步时间的注入带宽，且绝大部分流量横跨的二分带宽需求 = 网格切面 × 带宽；全对全模式下，需求变成N/2 × 每节点注入率，二分带宽立刻成为硬约束。同一个网络，两种模式的可达性能可以差一个数量级。
3. 代码示例与性能分析
3.1 示例 1：实测网络的 α（零负载延迟）与 β（渐近带宽）—— MPI ping-pong 与 ring 邻居交换
/* ============================================================================
* mpi_net_probe.c —— 互连网络的 alpha / beta 实测
* 1) ping-pong : 一对 rank 互发，测出往返延迟 RTT(n)，拟合 RTT = alpha + n/beta
* 2) ring : 所有 rank 同时与左右邻居交换，给网络真正加载
*
* 编译（release）:
* mpicc -O3 -march=native -DNDEBUG -std=c11 mpi_net_probe.c -o mpi_net_probe
* 运行:
* mpirun -np 8 --bind-to core ./mpi_net_probe
* ==========================================================================*/
#include <mpi.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* ---------- ping-pong：只有 rank 0 与 rank 1 在通信，返回一次往返时间 ---------- */
static double pingpong_once(int iters, int bytes)
{
int rank;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
char *sbuf = (char *)malloc((size_t)bytes);
char *rbuf = (char *)malloc((size_t)bytes);
memset(sbuf, rank, (size_t)bytes);
memset(rbuf, 0, (size_t)bytes);
/* 预热：让网络接口与内存路径进入稳态，否则第一次测量混入冷启动开销 */
for (int i = 0; i < 10; i++) {
if (rank == 0) {
MPI_Send(sbuf, bytes, MPI_BYTE, 1, 0, MPI_COMM_WORLD);
MPI_Recv(rbuf, bytes, MPI_BYTE, 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
} else if (rank == 1) {
MPI_Recv(rbuf, bytes, MPI_BYTE, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
MPI_Send(sbuf, bytes, MPI_BYTE, 0, 0, MPI_COMM_WORLD);
}
}
MPI_Barrier(MPI_COMM_WORLD);
double t0 = MPI_Wtime();
for (int i = 0; i < iters; i++) {
if (rank == 0) {
MPI_Send(sbuf, bytes, MPI_BYTE, 1, 0, MPI_COMM_WORLD);
MPI_Recv(rbuf, bytes, MPI_BYTE, 1, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
} else if (rank == 1) {
MPI_Recv(rbuf, bytes, MPI_BYTE, 0, 0, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
MPI_Send(sbuf, bytes, MPI_BYTE, 0, 0, MPI_COMM_WORLD);
}
}
double dt = MPI_Wtime() - t0;
free(sbuf); free(rbuf);
double worst = dt; /* 取所有 rank 的最大值，含启动偏差 */
MPI_Reduce(&dt, &worst, 1, MPI_DOUBLE, MPI_MAX, 0, MPI_COMM_WORLD);
return worst / (double)iters; /* 单位: 秒 / 往返 */
}
/* ---------- ring：所有 rank 同时与左右邻居交换（真正的网络负载测试） ---------- */
static double ring_step(int iters, int bytes)
{
int rank, size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
char *sbuf = (char *)malloc((size_t)bytes);
char *rbuf = (char *)malloc((size_t)bytes);
memset(sbuf, rank, (size_t)bytes);
int right = (rank + 1) % size;
int left = (rank + size - 1) % size;
MPI_Barrier(MPI_COMM_WORLD);
double t0 = MPI_Wtime();
for (int i = 0; i < iters; i++) {
/* 同时收发的邻居交换：网络上出现 size 条并发的消息流 */
MPI_Sendrecv(sbuf, bytes, MPI_BYTE, right, 0,
rbuf, bytes, MPI_BYTE, left, 0,
MPI_COMM_WORLD, MPI_STATUS_IGNORE);
}
double dt = MPI_Wtime() - t0;
free(sbuf); free(rbuf);
double worst = dt;
MPI_Reduce(&dt, &worst, 1, MPI_DOUBLE, MPI_MAX, 0, MPI_COMM_WORLD);
return worst / (double)iters;
}
int main(int argc, char **argv)
{
MPI_Init(&argc, &argv);
int rank, size;
MPI_Comm_rank(MPI_COMM_WORLD, &rank);
MPI_Comm_size(MPI_COMM_WORLD, &size);
if (size < 2) {
if (rank == 0) fprintf(stderr, "need >= 2 ranks\n");
MPI_Finalize();
return 1;
}
const int nsz = 7;
const int sizes[7] = {8, 64, 512, 4096, 32768, 262144, 1048576};
double rtt[7];
if (rank == 0)
printf("== ping-pong (rank 0 <-> rank 1) ==\n%10s %12s %12s %12s\n",
"bytes", "RTT[us]", "1-way[us]", "BW[GB/s]");
for (int i = 0; i < nsz; i++) {
int iters = (sizes[i] <= 4096) ? 2000 : (sizes[i] <= 65536 ? 500 : 50);
rtt[i] = pingpong_once(iters, sizes[i]);
if (rank == 0)
printf("%10d %12.3f %12.3f %12.3f\n",
sizes[i], rtt[i] * 1e6, rtt[i] * 5e5,
(double)sizes[i] / rtt[i] / 1e9);
}
if (rank == 0) {
/* 最小二乘拟合 RTT(n) = alpha + n / beta */
double sx = 0, sy = 0, sxx = 0, sxy = 0;
for (int i = 0; i < nsz; i++) {
double n = (double)sizes[i];
sx += n; sy += rtt[i]; sxx += n * n; sxy += n * rtt[i];
}
double k = (nsz * sxy - sx * sy) / (nsz * sxx - sx * sx); /* = 1/beta */
double a = (sy - k * sx) / nsz; /* = alpha */
double beta = 1.0 / k;
printf("\nfit : RTT(n) = %.3f us + n / %.2f GB/s\n", a * 1e6, beta / 1e9);
printf(" zero-load RTT alpha = %.3f us ; asymptotic BW beta = %.2f GB/s\n",
a * 1e6, beta / 1e9);
printf(" crossover n* = alpha*beta = %.1f KB "
"(消息小于它时，延迟主导；大于它时，带宽主导)\n", a * beta / 1024.0);
}
if (rank == 0)
printf("\n== ring neighbor exchange (all ranks active) ==\n"
"%10s %12s %14s\n", "bytes", "step[us]", "aggregate[GB/s]");
for (int i = 0; i < nsz; i++) {
int iters = (sizes[i] <= 4096) ? 2000 : (sizes[i] <= 65536 ? 500 : 50);
double st = ring_step(iters, sizes[i]);
if (rank == 0) {
/* 每一步全网有 2*size 条消息（每个 rank 各收、各发一条） */
double agg = 2.0 * size * (double)sizes[i] / st / 1e9;
printf("%10d %12.3f %14.3f\n", sizes[i], st * 1e6, agg);
}
}
MPI_Finalize();
return 0;
}
【代码做什么？】
pingpong_once()：只让 rank 0 与 rank 1 交替MPI_Send/MPI_Recv。关键点是”依赖链”——rank 0 必须等到 rank 1 回来的数据才能发下一轮，因此测得的RTT是纯粹的延迟，几乎不含带宽成分。先跑 10 次预热，再进主循环，最后用MPI_Reduce(MPI_MAX)取所有 rank 中最大的耗时（避免某个 rank 被 OS 调度干扰而低估）。- 主循环对 8 B 到 1 MiB 的 7 个尺寸各测一轮，打印 RTT、单向延迟、以及
n/RTT得到的有效带宽。你会看到 8 B 时有效带宽只有几 MB/s（延迟主导），1 MiB 时才逼近 β（带宽主导）。 - 用最小二乘在
(n, RTT)平面上拟合RTT(n) = α + n/β：斜率k = 1/β，截距α，并算出交叉点n* = α·β（超过它传输时间才超过启动延迟）。 ring_step()：让所有 rank 同时与左右邻居用MPI_Sendrecv交换。此时网络上同时存在size条并发消息流，测得的单步时间与2·size·n / step给出聚合带宽——它才是”网络能扛多少”的答案，并且会被二分带宽（以及每节点的注入带宽）封顶。
【并行机制与性能解说】
- 并行如何在硬件上发生：
ping-pong模式只有 2 个进程参与，网络上只有 1 条消息在飞，网络内部的 router 流水线全部空转——测到的是”延迟”，不是”吞吐”。ring模式里，每个 rank 的发送被送到本地网络接口，网络接口把消息切成 packet/flit 注入路由器，size条消息在路由器上并行转发（每个路由器每周期可以对多个不同输出端口各推进一个 flit）。 - Work / Span / 并行度：
- ping-pong（
I次迭代）：Work =2I次消息传递，每次代价α + n/β；Span（关键路径） =I·(α + n/β)（每一轮往返都依赖上一轮返回的数据）；并行度 = Work/Span = 2。结论：这个模式最多只能利用 2 个端点的带宽，无论机器多大都只测出延迟。 - ring（
I次迭代、P个 rank）：Work =2PI次消息传递（每个 rank 每轮各收、各发一条）；Span =I·(α + n/β)（邻居交换的每一步都要等对端发来，形成一条跨迭代的依赖链）；并行度 = 2PI / (I(α+n/β)) = 2P。结论：可扩展性上限 = 2P，但真实上限还要被二分带宽二次封顶：二分带宽BW_bisect决定P·2n/step ≤ BW_bisect，即step ≥ 2Pn/BW_bisect。
- ping-pong（
- 瓶颈：(a) 小消息时完全是
α主导——n=8 B、α=1.5 µs时有效带宽只有 ~5.3 MB/s，只有 β 的 0.04%；(b) ring 模式下若P很大且每节点注入率之和超过二分带宽，网络进入饱和区（图 2 曲线的陡升段），此时增加消息大小不会线性提升聚合带宽，反而可能因队头阻塞与缓冲耗尽而恶化；(c) 若消息切分过大，还会引入串行化延迟（n/β）暴露在关键路径上——这就是为什么大消息 + 重叠通信才是正解。
3.2 示例 2：4×4 mesh 上三种流控策略的周期级模拟（store-and-forward / wormhole / wormhole+VC）
/* ============================================================================
* mesh_flowctl.c —— 4x4 二维 mesh 上三种流控策略的周期级并行模拟
* MODE_SF : store-and-forward（输入缓冲必须收满整包才能开始转发）
* MODE_WH : wormhole（flit 级缓冲/流控，1 条虚通道）
* MODE_VC : wormhole + 2 条虚通道（缓解 head-of-line blocking）
* 路由: YX（先在 Y 方向走，再转弯，再在 X 方向走）—— 与 KNL 一致
*
* 编译（release）:
* gcc -O3 -march=native -fopenmp -std=c11 mesh_flowctl.c -o mesh_flowctl
* 运行:
* OMP_NUM_THREADS=8 ./mesh_flowctl
* ==========================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <omp.h>
#define RX 4
#define RY 4
#define NR (RX * RY) /* 16 个路由器 */
#define NLEN 4 /* 每个包 = 4 个 flit */
#define CAP 8 /* wormhole 下每个输入缓冲的 flit 容量 */
#define NVC 2 /* 每条物理通道上的虚通道数 */
#define NPKT 128 /* 总包数 */
#define MAXCYC 40000
enum { MODE_SF = 0, MODE_WH = 1, MODE_VC = 2 };
/* 端口编号: 0=N, 1=S, 2=E, 3=W, 4=LOCAL(注入/弹出) */
typedef struct { int pkt; int dst; int tail; } flit_t;
typedef struct {
flit_t q[CAP];
int head, count;
int route; /* 该缓冲中当前包的输出端口；-1 表示空 */
int pkt; /* 该缓冲中当前包的 id；-1 表示空 */
int draining; /* SF: 整包已收齐、正在发出（发出期间不再要求缓冲为"满"） */
} ibuf_t;
static ibuf_t ib[NR][5][NVC]; /* 当前状态 */
static flit_t nb_f[NR][5][NVC]; /* 本周期到达的 flit（写者唯一） */
static int nb_v[NR][5][NVC];
static int nb_r[NR][5][NVC];
static int nb_p[NR][5][NVC];
static int snap_c[NR][5][NVC]; /* 周期开始时的信用快照（count） */
static int snap_p[NR][5][NVC]; /* 周期开始时的信用快照（pkt） */
static unsigned rr[NR][5]; /* 输出端口上的 VC 轮转指针（防 VC0 饿死） */
static int g_mode = MODE_WH, g_nvc = 1;
static int pkt_src[NPKT], pkt_dst[NPKT], pkt_left[NPKT];
static long long inj_cyc[NPKT], done_cyc[NPKT];
static long long g_cycle;
static const int DX[4] = {0, 0, 1, -1}; /* N,S,E,W */
static const int DY[4] = {-1, 1, 0, 0};
static int neighbor(int r, int p)
{
if (p == 4) return r;
int x = r % RX, y = r / RX;
int nx = x + DX[p], ny = y + DY[p];
if (nx < 0 || nx >= RX || ny < 0 || ny >= RY) return -1;
return ny * RX + nx;
}
static int opposite(int p) { return (p == 0) ? 1 : (p == 1) ? 0 : (p == 2) ? 3 : (p == 3) ? 2 : 4; }
static int cap_of(void) { return (g_mode == MODE_SF) ? NLEN : CAP; }
/* YX 路由：先 Y 后 X，与讲义 slide 27 的 KNL 路由一致 */
static int route_of(int x, int y, int dst)
{
int dx = dst % RX, dy = dst / RX;
if (dy < y) return 0; /* N */
if (dy > y) return 1; /* S */
if (dx < x) return 3; /* W */
if (dx > x) return 2; /* E */
return 4; /* LOCAL：目的就是本节点 */
}
static void bpush(ibuf_t *b, flit_t f) { b->q[(b->head + b->count) % CAP] = f; b->count++; }
static flit_t bpop(ibuf_t *b)
{
flit_t f = b->q[b->head];
b->head = (b->head + 1) % CAP;
b->count--;
return f;
}
static void reset_state(void)
{
memset(ib, 0, sizeof ib);
memset(nb_v, 0, sizeof nb_v);
memset(rr, 0, sizeof rr);
for (int r = 0; r < NR; r++)
for (int p = 0; p < 5; p++)
for (int v = 0; v < NVC; v++) { ib[r][p][v].pkt = -1; ib[r][p][v].route = -1; }
for (int k = 0; k < NPKT; k++) { pkt_left[k] = NLEN; inj_cyc[k] = -1; done_cyc[k] = -1; }
g_cycle = 0;
}
/* 生成流量：hotspot 时 25% 的包全部打向 router 5，制造队头阻塞 */
static void gen_traffic(unsigned seed, int hotspot)
{
unsigned s = seed;
for (int k = 0; k < NPKT; k++) {
s = s * 1103515245u + 12345u;
int src = (int)((s >> 16) % NR);
int dst;
if (hotspot && (k % 4) == 0) dst = 5;
else { s = s * 1103515245u + 12345u; dst = (int)((s >> 16) % NR); }
if (dst == src) dst = (src + 1) % NR;
pkt_src[k] = src;
pkt_dst[k] = dst;
}
}
/* ---------- 阶段 0：信用快照（本周期所有仲裁都基于这份只读快照） ---------- */
static void snapshot_phase(void)
{
#pragma omp parallel for schedule(static)
for (int r = 0; r < NR; r++)
for (int p = 0; p < 5; p++)
for (int v = 0; v < NVC; v++) {
snap_c[r][p][v] = ib[r][p][v].count;
snap_p[r][p][v] = ib[r][p][v].pkt;
}
}
/* ---------- 阶段 1：注入（每路由器每周期最多 1 个 flit） ---------- */
static void inject_phase(void)
{
#pragma omp parallel for schedule(static)
for (int r = 0; r < NR; r++) {
for (int k = 0; k < NPKT; k++) {
if (pkt_src[k] != r || pkt_left[k] <= 0) continue;
ibuf_t *b = &ib[r][4][0]; /* Local 输入端口, VC0 */
if (b->count >= cap_of()) break;
if (b->count > 0 && b->pkt != k) break; /* 被别的包占着 */
flit_t f;
f.pkt = k;
f.dst = pkt_dst[k];
f.tail = (pkt_left[k] == 1);
if (pkt_left[k] == NLEN) inj_cyc[k] = g_cycle; /* head flit 注入时刻 */
if (b->count == 0) { b->pkt = k; b->route = route_of(r % RX, r / RX, f.dst); b->draining = 0; }
bpush(b, f);
pkt_left[k]--;
break; /* 每周期只注入 1 个 flit */
}
}
}
/* ---------- 阶段 2：仲裁 + 过链路（先查信用再选包，物理链路每周期 1 个 flit） ---- */
static void arbitrate_phase(void)
{
#pragma omp parallel for schedule(static)
for (int r = 0; r < NR; r++) {
for (int o = 0; o < 5; o++) {
int served = 0;
for (int k = 0; k < g_nvc && !served; k++) {
int v = (int)((rr[r][o] + (unsigned)k) % (unsigned)g_nvc);
for (int p = 0; p < 5 && !served; p++) {
ibuf_t *b = &ib[r][p][v];
if (b->count == 0) continue;
if (b->route != o) continue;
/* SF: 整包收齐才能开始转发；一旦开始（draining）就把剩余 flit 发完 */
if (g_mode == MODE_SF && b->count < NLEN && !b->draining) continue;
flit_t f = b->q[b->head];
int tv = v;
if (o == 4) { /* 弹出到本地：总能成功 */
bpop(b);
if (b->count == 0) { b->pkt = -1; b->route = -1; b->draining = 0; }
else if (g_mode == MODE_SF) b->draining = 1; /* SF：包已开始送出 */
if (f.tail) done_cyc[f.pkt] = g_cycle + 1; /* tail 弹出即完成 */
served = 1;
continue;
}
int n = neighbor(r, o);
int opp = opposite(o);
if (g_nvc > 1) { /* 虚通道分配：优先沿用原 VC */
int pick = -1;
if (snap_c[n][opp][tv] == 0 || snap_p[n][opp][tv] == f.pkt) pick = tv;
else {
int w = 1 - tv;
if (snap_c[n][opp][w] == 0 || snap_p[n][opp][w] == f.pkt) pick = w;
}
if (pick < 0) continue; /* 两条 VC 都被别的包占用 */
tv = pick;
}
/* credit 检查（用只读快照，避免同周期读写竞争）*/
int room = (snap_c[n][opp][tv] < cap_of()) &&
(snap_c[n][opp][tv] == 0 || snap_p[n][opp][tv] == f.pkt);
if (!room) continue; /* 下游无信用：本包这周期不被选中 */
bpop(b); /* 被选中才真正搬走 flit */
if (b->count == 0) { b->pkt = -1; b->route = -1; b->draining = 0; }
else if (g_mode == MODE_SF) b->draining = 1;
nb_f[n][opp][tv] = f; /* 写者唯一：只有 r 能写这个入口 */
nb_v[n][opp][tv] = 1;
nb_r[n][opp][tv] = route_of(n % RX, n / RX, f.dst);
nb_p[n][opp][tv] = f.pkt;
served = 1;
rr[r][o] = (unsigned)((v + 1) % g_nvc);
}
}
}
}
}
/* ---------- 阶段 3：把到达的 flit 并入输入缓冲（空缓冲时确定该包的输出端口） ---- */
static void merge_phase(void)
{
#pragma omp parallel for schedule(static)
for (int r = 0; r < NR; r++)
for (int p = 0; p < 5; p++)
for (int v = 0; v < NVC; v++) {
if (!nb_v[r][p][v]) continue;
ibuf_t *b = &ib[r][p][v];
if (b->count == 0) { b->pkt = nb_p[r][p][v]; b->route = nb_r[r][p][v]; b->draining = 0; }
bpush(b, nb_f[r][p][v]);
nb_v[r][p][v] = 0;
}
}
static void run_mode(int mode, const char *name, int hotspot)
{
g_mode = mode;
g_nvc = (mode == MODE_VC) ? 2 : 1;
reset_state();
gen_traffic(20260916u, hotspot);
long long cyc = 0;
for (; cyc < MAXCYC; cyc++) {
g_cycle = cyc;
snapshot_phase();
inject_phase();
arbitrate_phase();
merge_phase();
int all_done = 1;
for (int k = 0; k < NPKT; k++) if (done_cyc[k] < 0) { all_done = 0; break; }
if (all_done) { cyc++; break; }
}
double lat = 0; long long worst = 0, t0 = 0, t1 = 0; int done = 0;
for (int k = 0; k < NPKT; k++) {
if (done_cyc[k] < 0) continue;
long long L = done_cyc[k] - inj_cyc[k];
lat += (double)L; done++;
if (L > worst) worst = L;
if (t0 == 0 || inj_cyc[k] < t0) t0 = inj_cyc[k];
if (done_cyc[k] > t1) t1 = done_cyc[k];
}
double flits = (double)NPKT * NLEN;
printf("%-18s | %6d/%d | %9.2f | %7lld | %8lld | %9.3f\n",
name, done, NPKT, lat / (done ? done : 1), worst, cyc,
done ? flits / (double)(t1 - t0 + 1) : 0.0);
}
int main(void)
{
/* 模拟器的并行度上限 = 路由器数，线程再多只会付屏障开销 */
if (omp_get_max_threads() > NR) omp_set_num_threads(NR);
printf("4x4 mesh, %d packets x %d flits, buffer=%d flits, %d thread(s)\n",
NPKT, NLEN, CAP, omp_get_max_threads());
printf("%-18s | %7s | %9s | %7s | %8s | %9s\n",
"flow control", "done", "avg lat", "max lat", "cycles", "flit/cyc");
printf("-------------------+---------+-----------+---------+----------+----------\n");
printf("[traffic: uniform random]\n");
run_mode(MODE_SF, "store-and-forward", 0);
run_mode(MODE_WH, "wormhole", 0);
run_mode(MODE_VC, "wormhole + 2 VC", 0);
printf("[traffic: 25%% hotspot at router 5]\n");
run_mode(MODE_SF, "store-and-forward", 1);
run_mode(MODE_WH, "wormhole", 1);
run_mode(MODE_VC, "wormhole + 2 VC", 1);
return 0;
}
【代码做什么？】
- 建立 4×4 的二维 mesh：16 个路由器、每个 5 个端口（N/S/E/W + Local 注入与弹出）、每条物理通道
NVC条虚通道、每条缓冲CAP个 flit 的位置。包长固定 4 个 flit（head + 2 body + tail，用tail标志标记尾 flit）。每个周期分成四个阶段，阶段之间是隐式的全局屏障：- 阶段 0 信用快照：把每个缓冲的
count/pkt拷进snap_c/snap_p。仲裁阶段只读这份快照，因此”读邻居状态”与”邻居改自己状态”不会变成同周期数据竞争。 - 阶段 1 注入：每个源路由器每周期往自己的
Local输入端口塞 1 个 flit（受缓冲空间与”同一缓冲只容纳一个包”的限制——这就是注入反压）。 - 阶段 2 仲裁 + 过链路：对每个输出端口，在
NVC条虚通道上轮转着找第一个可以走的包：检查它的路由方向是否等于该输出端口、SF 模式下是否已收满整包（draining标志允许把已开始的包发完）、以及下游缓冲是否有信用（用快照检查空间与”同包”）。三者都满足才真正搬走 flit；不满足就整个包这周期不被选中，输出端口让给别的包——这正是”先查信用再仲裁“的真实路由器做法，也是避免把 flit 卡在共享输出锁存里造成死锁的关键。 - 阶段 3 合并：把本周期到达的 flit 并入输入缓冲；当缓冲由空变非空时，用接收方自己的坐标算出该包的输出端口（YX 路由：先 Y 后 X，与 KNL 一致）。
- 阶段 0 信用快照：把每个缓冲的
- 三种模式：
MODE_SF：缓冲容量 = 整包（cap_of()返回NLEN），必须收满NLEN个 flit 才能开始转发（draining标志允许把已经开始的包发完）；对端缓冲必须能为整包腾出空间。MODE_WH：缓冲容量 =CAP（8 个 flit），队头 flit 一到就可以转发，但一个缓冲同一时刻只装一个包（这正是 wormhole 的 head-of-line blocking 来源）。MODE_VC：在 WH 之上把每个输入端口切成 2 条虚通道：被堵住的包占一条，可走的包用另一条继续前进。
- 两种流量：均匀随机与 25% 打向同一热点 router 5（专门制造队头阻塞）。输出平均包延迟、最坏包延迟、总周期数与吞吐（flit/周期）。
【并行机制与性能解说】
- 并行如何在硬件/软件上发生：这段代码同时演示两种”并行”。
- 被模拟的网络本身是并行的：同一个周期里，16 个路由器各自独立地做路由查找与仲裁（
#pragma omp parallel for的最外层），路由器之间通过链路（数组元素） 通信。写者唯一性是刻意设计的——nb_f[n][opp][tv]只可能由”输出端口正好连到该输入端口”的那唯一一个路由器写，因此每个阶段内所有写操作无数据竞争、不需要锁。实测在 1/2/4/8/16 线程下结果逐位相同（见下表），这就是”片上网络靠消息传递而非共享变量通信“的软件体现。 - 模拟器自身是并行的：外层
parallel for把 16 个路由器分给多个 OpenMP 线程（schedule(static)），每周期 4 次并行区域（快照 → 注入 → 仲裁 → 合并），即每周期一个全局同步点。
- 被模拟的网络本身是并行的：同一个周期里，16 个路由器各自独立地做路由查找与仲裁（
- Work / Span / 并行度：
- Work =
Σ_(cycles) (路由器数 × 端口数 × 虚通道数)≈cycles × 16 × 5 × NVC次”信用检查 + 仲裁”尝试。以 wormhole+VC 的 75 个周期为例：75 × 16 × 5 × 2 = 12,000次仲裁尝试，另有128 × 4 = 512次 flit 搬运。 - Span（关键路径） =
cycles × 4（每周期内部 4 个严格串行的阶段，阶段之间必须同步——这是同步并行模拟的典型结构）。单个包穿越n跳的关键路径是n × t_r（本模型t_r = 1周期/跳）。 - 并行度 = Work/Span = (16 × 5 × NVC) / 4。WH 模式为 20，VC 模式为 40。也就是说，这个模拟器只有 20~40 路并行：
OMP_NUM_THREADS调到 64 毫无意义，屏障开销只会让结果变坏（代码因此把线程数自动夹到 ≤ 路由器数）。这与真实网络的规律完全一致——网络的并行度约等于”能同时推进的独立链路数”，与包数无关。
- Work =
- 实测结果（本笔记用 gcc 12.2 /
-O3 -march=native -fopenmp跑出的输出，8 线程，与 1 线程逐位相同）：
| 流量 | 流控 | 完成 | 平均延迟（周期） | 最大延迟 | 总周期 | 吞吐（flit/周期） |
|---|---|---|---|---|---|---|
| 均匀随机 | store-and-forward | 128/128 | 22.93 | 63 | 161 | 3.30 |
| 均匀随机 | wormhole | 128/128 | 11.99 | 40 | 94 | 5.63 |
| 均匀随机 | wormhole + 2 VC | 128/128 | 9.80 | 35 | 75 | 7.11 |
| 25% 热点 | store-and-forward | 128/128 | 27.51 | 136 | 223 | 2.52 |
| 25% 热点 | wormhole | 128/128 | 19.58 | 128 | 186 | 2.93 |
| 25% 热点 | wormhole + 2 VC | 128/128 | 21.20 | 145 | 178 | 3.14 |
- 怎么读这张表（与讲义的结论一一对应）：
- store-and-forward 的平均延迟约为 wormhole 的 2 倍（22.93 vs 11.99），这正是 “每一跳都要把整包收完” 的代价——对应 slide 40 的
3 × 4 = 12单位（store-and-forward）vs3 + 3 = 6单位（cut-through/wormhole）。 - 均匀随机流量下，虚通道明显改善延迟：平均延迟 11.99 → 9.80、最大延迟 40 → 35、总周期 94 → 75。队头阻塞确实被”另一条虚通道继续前进”缓解了——对应 slide 44/45 的两张图。
- 热点流量下 VC 的表现不同：平均延迟升高（19.58 → 21.20），但总周期下降（186 → 178）。原因是虚通道让更多包被接收入网（有效负载上去了），排队的包更多 → 平均延迟上升；而瓶颈已经转移到”热点 router 5 的弹出端口”（每周期只能弹出 1 个 flit），虚通道增加不了这个端口的带宽。这是”VC 减少队头阻塞，但不能创造带宽“的实测证据，也对应图 2 的延迟-负载曲线：工作点被推到了更靠近饱和区的位置（用延迟换吞吐）。
- store-and-forward 的平均延迟约为 wormhole 的 2 倍（22.93 vs 11.99），这正是 “每一跳都要把整包收完” 的代价——对应 slide 40 的
- 瓶颈：(a) 热点端口的串行化（
o == 4每周期仅 1 个 flit）——全对全/热点流量的天花板；(b) 队头阻塞——一个缓冲只装一个包，被堵的包会让路由空闲的包一起停下；(c) 注入反压——源缓冲满后源节点只能干等；(d) 同步开销——每周期 4 个并行区域的屏障，在 16 个路由器的小网络上，屏障本身就是可观的固定开销（这也是”模拟器并行度只有 20~40”的直接后果）。
3.3 示例 3：共享总线争用 vs 分片网络 / 伪共享 —— 用 OpenMP 量化”互连争用”
/* ============================================================================
* bus_vs_shards.cpp —— 共享总线式争用 vs 分片(sharded)访问 vs 伪共享
* MODE 0 shared : 所有线程对一个全局原子计数器做 RMW -> 等价于共享总线
* MODE 1 unpacked : 每线程一个计数器，但都挤在同几条 cache line -> 伪共享
* MODE 2 padded : 每线程一个 64B 对齐的计数器 -> "本地 slice" 访问
* MODE 3 remote : 每线程更新"邻居的"计数器 -> 跨 slice 通信
*
* 编译（release）:
* g++ -O3 -march=native -fopenmp -std=c++17 bus_vs_shards.cpp -o bus_vs_shards
* 运行:
* OMP_NUM_THREADS=16 ./bus_vs_shards
* ==========================================================================*/
#include <omp.h>
#include <atomic>
#include <cstdio>
struct alignas(64) Padded {
std::atomic<long> v;
char pad[64 - sizeof(std::atomic<long>)];
};
static const char *MODE_NAME[4] = {
"0 shared counter (bus-like)",
"1 per-thread, unpadded (false sharing)",
"2 per-thread, 64B padded (local slice)",
"3 per-thread, remote slice (cross-slice)"
};
/* 跑一轮，返回耗时（秒）。内部先预热，再取 REPS 次里最快的一次。 */
static double bench(int mode, int P, long iters)
{
const int REPS = 3;
std::atomic<long> *plain = (mode <= 1) ? new std::atomic<long>[P] : nullptr;
Padded *pad = (mode >= 2) ? new Padded[P] : nullptr;
if (plain) for (int i = 0; i < P; i++) plain[i].store(0, std::memory_order_relaxed);
if (pad) for (int i = 0; i < P; i++) pad[i].v.store(0, std::memory_order_relaxed);
double best = 1e30;
for (int rep = 0; rep < REPS + 1; rep++) { /* 第 0 次当预热，不计入 */
double t0 = omp_get_wtime();
#pragma omp parallel num_threads(P)
{
int tid = omp_get_thread_num();
switch (mode) {
case 0:
for (long i = 0; i < iters; i++) plain[0].fetch_add(1, std::memory_order_relaxed);
break;
case 1:
for (long i = 0; i < iters; i++) plain[tid].fetch_add(1, std::memory_order_relaxed);
break;
case 2:
for (long i = 0; i < iters; i++) pad[tid].v.fetch_add(1, std::memory_order_relaxed);
break;
default:
for (long i = 0; i < iters; i++) pad[(tid + 1) % P].v.fetch_add(1, std::memory_order_relaxed);
break;
}
}
double dt = omp_get_wtime() - t0;
if (rep > 0 && dt < best) best = dt;
}
delete[] plain;
delete[] pad;
return best;
}
int main(void)
{
const long iters = 500000;
int maxp = omp_get_max_threads();
if (maxp > 16) maxp = 16; /* 采样到 16 线程即可看出趋势 */
printf("atomic fetch_add, %ld iterations per thread (best of 3), up to %d threads\n\n",
iters, maxp);
printf("%-38s | %4s | %10s | %9s | %10s\n",
"mode", "P", "Mops/s", "speedup", "GB/s line traffic");
printf("---------------------------------------+------+------------+-----------+----------\n");
for (int mode = 0; mode < 4; mode++) {
double base = 0.0;
for (int P = 1; P <= maxp; P *= 2) {
double dt = bench(mode, P, iters);
double mops = (double)P * (double)iters / dt / 1e6;
if (P == 1) base = mops;
/* 每次争用的原子 RMW 至少牵动一条 64B cache line 的迁移 */
double gbs = mops * 64.0 / 1000.0;
printf("%-38s | %4d | %10.1f | %9.2fx | %10.2f\n",
MODE_NAME[mode], P, mops, mops / base, gbs);
}
printf("---------------------------------------+------+------------+-----------+----------\n");
}
printf("\n提示: 模式 0 的 Mops/s 在 P>1 后基本不涨，甚至下降 —— 这是共享总线的串行化点；\n");
printf(" 模式 1 明显差于模式 2 —— 伪共享把无效的一致性流量灌进了互连网络。\n");
return 0;
}
【代码做什么？】
- 四种模式共用同一个
fetch_add微基准，只是”摆放方式”不同：- 模式 0（shared）：所有线程对一个全局原子计数器做读-改-写。任何时刻只有一个线程能拿到该 cache line 的独占权，硬件层面被强制串行化——这就是共享总线 / 单一仲裁点的软件复现。
- 模式 1（unpacked）：每线程一个
std::atomic<long>，但紧挨着放在同一批 cache line 里 → 伪共享（false sharing）：每次fetch_add都会让整条 64 B 行在核之间来回迁移。 - 模式 2（padded）：每线程一个 64 B 对齐（
alignas(64)+ padding）的计数器 → 各自独占一行，等价于”每个核访问自己的本地 L3 slice“。 - 模式 3（remote）：每线程更新邻居的计数器 → 一个置换（permutation）访问模式：每条 cache line 依然只被一个核独占，只是”拥有者”和”使用者”不是同一个核。
- 每个 (模式, 线程数) 组合先预热一轮，再取 3 次里最快的一次，算出
Mops/s、相对P=1的加速比，以及互连流量下界Mops/s × 64 B（每次争用的原子 RMW 至少要搬一条 cache line）。
【并行机制与性能解说】
- 并行如何在硬件上发生：
fetch_add在 x86 上编译成lock xadd。独占一条 cache line 的所有权是所有原子 RMW 的共同前提——这条行必须在核之间”搬家”，而搬家要占用片上互连（ring/mesh）与一致性协议消息（请求、失效、响应）。所以这个微基测量的是互连与一致性协议的争用程度，而不是 ALU 快慢。 - Work / Span / 并行度：
- 模式 0：Work =
P·iters次 RMW；Span =P·iters次（全部串行地作用在同一个变量上，临界区长度 = 一次独占访问的时间）；并行度 = 1（无论多少线程）。这是”并行度被一个共享资源封顶“最纯粹的例子。 - 模式 2：Work =
P·iters；Span =iters（每个线程独立做完自己那份，互不相干）；并行度 = P。这才是”分片网络 + 本地 slice”应有的样子。 - 模式 1：Work =
P·iters，但每次操作都要把一条整行搬来搬去，Span 里混入了Θ(P)次行迁移，并行度被”每行能容纳几个原子量”卡死（16 核写 2 个原子量时，串行度极高）。 - 模式 3：Work =
P·iters；Span ≈iters（每个计数器仍只被一个核独占）。所以它能像模式 2 一样扩展——说明杀死性能的是”争用”，而不是”距离”本身。
- 模式 0：Work =
- 实测结果（本机 gcc 12.2 /
-O3 -march=native -fopenmp，每线程 50 万次 RMW，best of 3）。注意：这张表是一次代表性运行，绝对数值随机器（核数、NUMA、频率）与当前负载变化，但趋势与量级差异非常稳定：
| 模式 | P=1 | P=2 | P=4 | P=8 | P=16 | 16 线程加速比 |
|---|---|---|---|---|---|---|
| 0 共享计数器（总线式） | 490.1 Mops/s | 168.3 | 161.3 | 163.5 | 39.9 | 0.08×（负加速） |
| 1 每线程但未填充（伪共享） | 456.9 | 206.3 | 170.3 | 345.8 | 80.8 | 0.18×（负加速） |
| 2 每线程 64 B 对齐（本地 slice） | 467.7 | 853.8 | 1676.0 | 3303.9 | 6510.4 | 13.92× |
| 3 每线程访问邻居的片（置换） | 486.7 | 851.2 | 1649.2 | 3290.3 | 6590.1 | 13.54× |
- 怎么读这张表：
- 模式 0 是”负加速”：线程数从 1 加到 2，吞吐直接掉到 1/3（490 → 168 Mops/s），加到 16 线程只剩 0.08×。多出来的核全部在排队等同一条 cache line，这正是共享总线的结局，也是”全局计数器 / 全局任务队列”这类写法的下场。
- 模式 1 比模式 2 差约 80 倍（80.8 vs 6510.4 Mops/s）：16 个线程挤在同几条 cache line 上，每次写都要把整行迁移一次，等价于把互连网络塞满了无效的一致性流量。这是最容易被误诊为”内存带宽不够”的性能杀手。
- 模式 2 近乎线性（16 线程 13.92×）：分片 + 对齐之后，每个核只碰自己的行，网络里几乎没有额外流量。
- 模式 3 与模式 2 相当，这是一个重要的反直觉结论：置换访问不伤吞吐，共享同一行才伤。跨 slice 的距离只有在”多个核争同一行”或”链路带宽被占满”时才变成瓶颈。
- 瓶颈：(a) 串行化（模式 0/1）：增加线程只会增加争用，吞吐到顶后反而下降；(b) 伪共享（模式 1）：破坏力可达两个数量级；(c) 一致性流量的带宽：把
Mops/s × 64 B读成”互连上的流量下界”，模式 2 在 16 线程时是 416 GB/s（本地行，不经网络），而模式 0 的 2.56 GB/s 全部是跨核行迁移的无效流量——两者相差 160 倍。
4. 性能模型与复杂度分析
4.1 拓扑的定量指标（N = 节点数，k = √N，B = 单条链路带宽）
| 拓扑（N=64, k=8） | 链路数 | 直径（hops） | 平均距离（hops） | 二分带宽（链路数） | 成本 / 单位二分带宽 |
|---|---|---|---|---|---|
| Ring (N=64) | 64 | 32 | 16 | 2 | 64/2 = 32（最差） |
| 2D Mesh (8×8) | 2N−2k = 112 | 2(k−1) = 14 | 2(k²−1)/(3k) = 5.25 | k = 8 | 112/8 = 14 |
| 2D Torus (8×8) | 2N = 128 | k = 8 | k/2 = 4 | 2k = 16 | 128/16 = 8 |
| Multi-stage log (Omega) | N·lg N = 384 | lg N = 6 | lg N = 6 | N/2 = 32 | 384/32 = 12 |
| Fat Tree (64 叶) | O(N lg N) ≈ 384 | 2·lg N = 12 | ~12 | 32（可做 full bisection） | 12 |
| Hypercube (n=6) | N·n/2 = 192 | 6 | n/2 = 3 | N/2 = 32 | 192/32 = 6（最好） |
| Crossbar (N=64) | 交叉点 N² = 4096 | 1 | 1 | N/2 = 32 | 4096/32 = 128（最贵） |
读表要点：ring 是唯一”二分带宽不随 N 增长”的拓扑（永远只有 2 条链路跨切面），这是它只能用于几十个节点的根本原因；mesh 用 112 条链路买到 8 条链路的二分带宽（效率 14），torus 用绕回链路把效率提到 8；hypercube 的成本效率最高（6），代价是每个节点的度（radix）随 lg N 增长，硬件上难以实现大端口数路由器——这就是为什么实际的芯片用 mesh/ring，而机群/超级计算机多用 fat tree（可用多级小交换机拼出 full bisection）。
4.2 数值算例 A：Intel ring 互连的理论峰值带宽（讲义 slide 25 的数字复算）
假设：数据环宽 32 B、时钟 3.4 GHz、共有 4 条环（request / snoop / ack / data）。
- 单条环单向理论带宽：
32 B × 3.4 GHz = 108.8 GB/s - 四条环合计：
4 × 32 B × 3.4 GHz = 435.2 GB/s≈ 讲义给出的 “约 435 GB/s” ✔ - 前提条件（讲义原文）：这个峰值是”当每个核都访问自己的本地 slice 时“才成立的。
- 反例（本笔记补充的算例）：若 4 个核全部打向同一个 2 MB L3 slice，那么瓶颈变成该 slice 到环的那一条链路：
- 可用带宽 =
32 B × 3.4 GHz = 108.8 GB/s - 平摊到 4 个核：
27.2 GB/s / 核，比”访问本地 slice”时低 3.7 倍（435.2/4 = 108.8 vs 27.2） - 这解释了为什么”把数据按核分片（sharding）“在 ring 机器上如此重要——与示例 3 的模式 2 vs 模式 0 完全对应。
- 可用带宽 =
- 成本直观量：讲义指出 crossbar（CCX）占用的芯片面积与一个核相当（Sun SPARC T2 / Oracle SPARC T5）。在 16 核的 T5 上，等于用”一个核的面积”买”任意两核 O(1) 通信”，这已是 O(N²) 网络在 N=16~32 时的现实上限。
4.3 数值算例 B：零负载延迟模型 T0 = D · t_r + L / b
假设（KNL 6×6 mesh，取自讲义 slide 27 的形态 + 本笔记补充的合理参数）：k = 6（36 个 tile）、网络时钟 f = 1.5 GHz、每跳路由延迟 t_r = 2 个网络时钟、链路宽度 b = 32 B/cycle、消息长度 L = 64 B。
- 平均跳数：
D_avg = 2(k²−1)/(3k) = 2×35/(3×6) = 3.89跳 - 每跳时间：
t_r / f = 2 / 1.5 GHz = 1.33 ns→ 路由部分 =3.89 × 1.33 = 5.19 ns - 串行化时间：
L / (b·f) = 64 B / (32 B × 1.5 GHz) = 64 / 48 GB/s = 1.33 ns - T0 ≈ 5.19 + 1.33 ≈ 6.5 ns（片上），相比跨 socket 的 UPI/QPI（数十到上百 ns）与 InfiniBand（µs 级），片上网络的空载延迟小 2~3 个数量级。
- 但这不是性能保证：按图 2 的延迟-负载曲线，当注入率接近饱和点时延迟会急剧上升。用一个粗模型说明饱和：
- 网络总注入能力 =
36 tile × 32 B × 1.5 GHz = 1728 GB/s - 二分带宽（6×6 mesh 的最小切面 = 6 条链路）=
6 × 48 GB/s = 288 GB/s - 两者之比 = 288/1728 = 1/6：即”全局随机通信”只能拿到”本地通信”带宽的 1/6。任何全对全或跨全局的数据交换都必须按这个比例打折——这就是”局部性”在互连层面的量化含义。
- 与片外对比：4 通道 DDR4-3200 ≈
4 × 25.6 = 102.4 GB/s，片上二分带宽（288 GB/s）约为它的 2.8 倍——片上很好，但绝不是无限。
- 网络总注入能力 =
4.4 数值算例 C：α-β 模型与消息大小的”生死线”
假设（典型的 InfiniBand/以太网级别的网络）：α = 1.5 µs（零负载启动延迟），β = 12 GB/s（渐近带宽）。消息传输时间 T(n) = α + n/β：
| 消息大小 n | 传输时间 T = α + n/β | 有效带宽 n/T | 相对 β 的比例 | 判断 |
|---|---|---|---|---|
| 8 B | 1.5 µs + 0.7 ns ≈ 1.500 µs | 5.3 MB/s | 0.044% | 完全被延迟主导 |
| 1 KiB | 1.5 + 0.085 = 1.585 µs | 0.661 GB/s | 5.5% | 依然延迟主导 |
| 18 KB（交叉点） | 1.5 + 1.5 = 3.0 µs | 6.0 GB/s | 50% | 交叉点 n* = α·β |
| 1 MiB | 1.5 + 87.4 = 88.9 µs | 11.8 GB/s | 98% | 带宽主导 |
- 交叉点公式：
n* = α · β = 1.5 µs × 12 GB/s = 18 KB。消息小于 18 KB 时，启动延迟比传输时间还长；小于它的消息再怎么优化协议也没用，唯一出路是消息聚合（message aggregation）：把 1000 条 8 B 的消息合成一条 8 KB 的消息，时间从1000 × 1.5 µs = 1.5 ms降到1.5 µs + 0.68 µs ≈ 2.2 µs，快了约 680 倍。 - Little’s law（本笔记补充的解释）：要在延迟
L下维持带宽BW，必须让BW × L字节”在路上”。以BW = 12 GB/s、L = 1.5 µs计，每条流必须有 18 KB 在飞。若消息只有 64 B，则每个 rank 需要18 KB / 64 B = 288条同时在途的消息才能填满管道——这正是”要重叠（overlap）、要深流水、要用非阻塞通信“的定量理由。
4.5 数值算例 D：halo 交换的算术强度与通信/计算平衡
假设：全局 512³ 的三维 7 点 stencil（每点 13 flops），512 个 rank 排成 8×8×8，每个 rank 拥有 64³ 的局部子域，halo 厚度 1 层（double，8 B），每 rank 峰值算力 50 GFLOPS（本笔记假设值），网络每 rank 注入带宽 12 GB/s，fat tree 二分带宽 2 TB/s。
- 每 rank 每步的通信量：
6 面 × 64×64 点 × 8 B = 196,608 B ≈ 192 KiB - 每 rank 每步的计算量：
64³ × 13 = 262,144 × 13 = 3.41 MFLOP - 算术强度 =
3.41e6 flops / 1.966e5 B =17.3 flops/byte - 计算时间 =
3.41 MFLOP / 50 GFLOPS = 68.2 µs - 通信时间（按每 rank 注入带宽）=
192 KiB / 12 GB/s = 16.4 µs - 通信时间（按最坏情况：全部流量跨越二分切面，这是全对全/置换类通信的下界） =
512 × 196,608 B / 2 TB/s = 100.66 MB / 2 TB/s = 50.3 µs - 结论：
T_comm/T_comp = 50.3/68.2 = 0.74→ 若通信完全不重叠，效率上限 ≈1/(1+0.74) = 57%。 - 两个改进方向（都有定量依据）：
- 重叠（overlap）：用
MPI_Isend/Irecv+MPI_Waitall把 6 个面的发送藏进”内部区域”的计算里（见 §2.12 图 10B）。理想情况下把 50.3 µs 的通信压在 68.2 µs 的计算之下，效率回到接近 100%。 - 放大子域：通信量 ∝ 表面积 ∝
L²，计算量 ∝ 体积 ∝L³，所以算术强度 ∝ L。把子域从64³换到128³（rank 数从 512 降到 64），算术强度翻倍到 34.6 flops/byte，通信占比直接减半。这就是”最小化通信（minimize communication）”这条课程主线的可量化版本。
- 重叠（overlap）：用
4.6 Amdahl 定律在互连上的应用
设一次运行的 20% 时间花在”等待网络”上，若把网络二分带宽翻倍（其余不变），整体加速比：
Speedup = 1 / ((1 - 0.20) + 0.20/2) = 1 / (0.80 + 0.10) = 1 / 0.90 = 1.111 -> 11%
解读：当并行程序的瓶颈已经转移到网络之外（计算、DRAM 带宽、同步），单纯升级互连只能拿到 11%。反过来说，当网络占比达到 50% 时，翻倍带宽能带来 1/(0.5+0.25) = 1.33×。先测量、再决定要不要动网络——这与课程”性能优化（performance optimization）”部分的方法论一致。
5. 关键要点
总线不 scale，网络是必然选择，而且”机柜级的问题”今天全在片内重演。 共享总线只有三个优点——简单、便宜、snooping 一致性容易实现；但它同时带来争用、带宽与 N 无关、电气负载压低频率抬高功耗。从 4 核到 72 核（KNL 6×6 mesh），互连已经从配角变成整颗芯片性能与功耗（MIT RAW：约占 35% 功耗）的主角。
拓扑的选择是”成本 / 延迟 / 二分带宽 / 布线复杂度”的四角权衡，没有全能赢家。 用 diameter（最坏延迟）与 average distance（平均延迟） 描述延迟，用 bisection bandwidth 描述”全局通信的容量”，再叠加 direct/indirect、blocking/non-blocking、成本 O() 一起判断。ring 的致命伤是二分带宽恒为常数；mesh 好布线但边缘/中心不公平；torus 用绕回链路修复公平性却难布线；hypercube 成本效率最高但端口数随 lg N 增长；crossbar 延迟 O(1) 却要 O(N²) 面积（T2/T5 上 CCX 面积约等于一个核）。并且要记住讲义的警告：二分带宽不等于实际可达带宽，它忽略了交换机与路由效率。
网络的性能必须用”两个数字”来描述：零负载延迟与饱和吞吐。 零负载延迟由拓扑 + 路由 + 流控共同决定，饱和吞吐由流控决定；一般规律是 延迟随负载上升，接近饱和时会陡增（缓冲耗尽 + 队头阻塞 + 反压传播）。工程上要同时盯 α（启动延迟）与 β（带宽）：消息小于
n* = α·β时延迟主导，此时唯一的解药是聚合消息与增加在途消息数（Little’s law: BW × L 字节必须在路上）。流控的粒度决定了延迟与缓冲面积的取舍：粗粒度缓冲换来简单，细粒度 flit 换来低延迟但引入队头阻塞。 store-and-forward 每跳都要收全包（延迟 ∝ 跳数 × 包长，需要整包缓冲）；cut-through 头到即转（高争用时退化为 store-and-forward）；wormhole 把缓冲/流控降到 flit 粒度，长消息的延迟几乎与网络距离无关，但引入 head-of-line blocking，于是需要虚通道（VC） ——它同时还能打破死锁环（escape VC） 与提供 QoS 优先级。
对软件而言，能做的只有三件事：把消息做大做少、把通信与计算重叠、把访问局部化。 消息做大做少 = 赢得 α；重叠 = 把通信从 Span（关键路径）里挪到 Work 的并行部分（非阻塞通信 + 分块计算）；局部化 = 让访问落在本地 slice/本地 tile，避免”全对全”去撞那 1/6 的二分带宽。一个被所有线程争用的原子计数器，就是在网络里人为造了一条总线——它的并行度是 1。
6. 常见陷阱与注意事项
- 把 bisection bandwidth 当作”可达带宽”。 讲义明确警告：二分带宽不考虑交换机与路由效率。一个二分带宽 32 条链路的网络，在真正的置换（permutation）流量下可能只能拿到一半甚至更低；评估时要用实测的置换/全对全微基准（如示例 1 的 ring 测试），而不是拓扑图上的数字。
- 只测带宽、不测延迟（或反过来）。 只报 β 会掩盖大规模下小消息的崩塌（8 B 消息有效带宽只有 5.3 MB/s，是 β 的 0.044%）；只报空载延迟会掩盖饱和后的陡增。必须同时给出 (α, 饱和吞吐)，并且在接近饱和的工作点上测量。
- 误以为 wormhole 网络永远不需要整包缓冲。 讲义 slide 41 说得很清楚：“需要交换机具备整包缓冲，和 store-and-forward 一样”——因为一旦 head flit 被下游堵住，整个包最终会被吸进开关的缓冲里（cut-through 在高争用下退化为 store-and-forward）。设计缓冲面积时按最坏情况算，否则拥塞下会丢包/死锁。
- 忽略 head-of-line blocking 就做不出正确的延迟预测。 一个热点链路可以把一个输入缓冲排满，让后面路由完全空闲的包也一起停摆（slide 44）。热点流量（如 allreduce 的根节点、热点计数器）下，实测延迟会比”平均跳数 × 每跳延迟”的估算高一个数量级。诊断信号：吞吐远低于二分带宽推算值，同时个别端口的缓冲占用长期饱和。
- 路由算法引入循环依赖 → 死锁。 自适应路由很有吸引力（能绕开拥塞），但通道依赖图一旦成环就可能死锁。安全做法：使用维度顺序路由（如 KNL 的 YX routing，其依赖图无环）、或用虚通道拆环（请求/响应分 VC、escape VC 保留一条无死锁路径）。另外要区分死锁（deadlock） 与 活锁（livelock，包一直在绕但到不了）——讲义明确说 QoS、优先级、可靠性、死锁、活锁都属于”本课不深入、但值得继续学”的内容。
- 把”片上网络很快”当成”通信免费”。 6×6 mesh 的二分带宽只有注入带宽的 1/6；跨 socket 再降 2~3 个数量级。任何”每个线程都去写全局共享结构”的写法（全局计数器、全局栈、全局任务队列）都会把并行度压到接近 1，和共享总线的结局完全一样。
- 忽略伪共享带来的额外互连流量。 相邻的小变量被不同线程写时，每次写都要让整条 64 B cache line 在核之间迁移——这是往互连网络上灌无效的一致性流量。它对性能的破坏经常比”内存带宽不足”更严重，而且往往在
P跨过某个阈值（超过一条行能放的变量数）时突然出现。修法：alignas(64)填充、每线程独立累加最后再归并（示例 3 的模式 2）。
7. 思考题（带答案）
思考题 1：把一个 256 节点的系统分别做成 ring 与 16×16 的 2D mesh，请给出链路数、直径、平均跳数与二分带宽，并说明各自适合什么应用。
【答案】
| 指标 | Ring (N=256) | 2D Mesh (16×16) |
|---|---|---|
| 链路数 | N = 256 | 2N − 2k = 512 − 32 = 480 |
| 直径（最坏跳数） | N/2 = 128 | 2(k−1) = 30 |
| 平均跳数 | N/4 = 64 | 2(k²−1)/(3k) = 2×255/48 = 10.6 |
| 二分带宽 | 2 条链路 | k = 16 条链路 |
结论与适用性：mesh 的平均跳数只有 ring 的 1/6（10.6 vs 64），二分带宽是 ring 的 8 倍，代价是链路数多 1.9 倍。因此：ring 只适合”流量高度局部”或节点数很少的场合——例如 Intel Sandy Bridge 那样 4~16 个核 + 几个 slice，且每个核主要访问本地 slice（此时 435 GB/s 的峰值才成立）；一旦出现”所有核抢同一个 slice”或需要全局通信，ring 的常数二分带宽会立刻成为死结。mesh 适合网格型/局部性好的计算（stencil、邻域通信、图像分块），因为跳数只随 √N 增长、布线等长、且有多条可选路径；它的缺点是边缘节点与中心节点的延迟不公平（这正是 torus 用绕回链路要解决的问题），以及最坏情况（对角通信）仍有 30 跳。
思考题 2：讲义 slide 43 问”对长消息而言，wormhole 的延迟几乎与网络距离无关，为什么？”请给出定量解释，并说明这个结论在什么情况下失效。
【答案】 因为 wormhole 是完全流水化（completely pipelined） 的：head flit 在前方建立路径，body flit 与 tail flit 紧跟着一个 flit 一个 flit 地推进，包的各个部分同时分布在不同链路上。设消息长度 L、链路带宽 b、跳数 D、每跳路由延迟 t_r，则最后一个 flit 的到达时间为
T ≈ D · t_r + L / b
其中串行化项 L/b 与跳数无关，只有 D · t_r 部分与距离成正比。对比 store-and-forward 的 T_SF ≈ D · (L/b)（延迟与距离和包长都成正比），当 L/b ≫ D·t_r（长消息）时，wormhole 的 D·t_r 相对 L/b 可以忽略，于是 T 几乎与 D 无关。讲义给的例子正是这个比例：3 跳、包长 4 单位、每跳路由 1 单位 → store-and-forward 为 3 × 4 = 12 单位，cut-through/wormhole 为 3 + 3 = 6 单位，快 2 倍且随距离增长的部分从 L/b 项转移到了 t_r 项。
失效条件：(1) 短消息——当 L/b 与 D·t_r 同量级时，”与距离无关”就不成立，延迟重新变成 ≈ D·t_r；(2) 高争用——一旦 head flit 在下游被阻塞，整包停在原地（head-of-line blocking），实际延迟退化为 store-and-forward 量级，并且缓冲需求也退化到整包；(3) 死锁/反压——环形依赖或下游缓冲长期无信用时，流水线被完全打断。
思考题 3：一个 16 节点系统，每个节点想持续注入 4 GB/s 的随机流量，网络是一条 16 节点的 ring，每条链路带宽 8 GB/s。问：通信能否满足？如果换成 4×4 的 mesh（链路带宽同为 8 GB/s）呢？请给出计算过程与设计准则。
【答案】
Ring 的情形：
- 总注入需求 =
16 × 4 GB/s = 64 GB/s。 - 随机（均匀）通信时，约一半流量要跨越任意一个二分切面，因此跨切面需求 ≈
64/2 = 32 GB/s。 - ring 的二分带宽 = 2 条链路 × 8 GB/s = 16 GB/s（与 N 无关）。
32 GB/s > 16 GB/s→ 网络饱和。饱和后二分切面只能提供 16 GB/s，均分给 16 个节点，每个节点实际只能拿到 ≈ 1 GB/s（只有期望的 1/4），并且按图 2 的曲线，延迟会急剧上升，应用性能远低于”1/4 带宽”的线性估计（还要叠加队头阻塞与缓冲耗尽）。- 结论：ring 在这个负载下不合格。
换成 4×4 mesh 的情形：
- 二分带宽 =
k 条链路 × B = 4 × 8 GB/s = 32 GB/s。 - 跨切面需求 = 32 GB/s，恰好等于二分带宽 → 理论上”刚刚够”，但没有任何余量：一旦流量分布有偏斜（热点）、或者路由效率损失（讲义警告的”交换机与路由效率”）、或者出现突发，就会立刻进入饱和区，延迟上升、吞吐下降。工程上要求
二分带宽 ≥ 1.3 ~ 2 × 跨切面需求，所以这个配置偏紧、需要加余量（例如提高链路带宽到 16 GB/s，或改成 torus 得到 8 条切面链路 = 64 GB/s）。
设计准则（可推广）：
总注入带宽 = N × 每节点注入率
跨切面需求(均匀) ≈ 总注入带宽 / 2 （全对全/置换类流量取 1.0）
设计要求 = 二分带宽 ≥ 1.3 ~ 2 × 跨切面需求
推论：任何”每个节点都要和所有其他节点通信”的应用（allreduce、全对全、全局同步/全局原子操作），其可扩展性上限直接由二分带宽除以 N 决定——这就是为什么大规模并行机普遍采用可做到 full bisection 的 fat tree，而不是 ring 或 mesh。