CS3210 Parallel Computing Note

第 1 部分：导论与并行计算基础 (Introduction to Parallel Computing)

1. 为什么我们需要并行计算？

在过去，程序员通常依赖硬件制造商提高单核 CPU 的时钟频率（例如从 800 MHz 升级到 1 GHz）来自动提升程序的运行速度。然而，由于功耗和散热的物理限制，单核时钟频率的增长已经停滞。当今，对于天气预报、机器学习、流体模拟等复杂问题，即使单线程代码在算法上已经做到了极致优化，其运行速度仍然无法满足需求。因此，“让程序变快”的唯一途径就是并行计算：利用更多的物理处理单元（Cores）同时处理任务。

功耗和散热的物理限制导致增长停滞

2. 并行化问题的核心步骤

将一个串行程序转化为并行程序，通常需要经过以下三个核心步骤（在后续章节中这也演变为了 Foster 的 PCAM 设计方法学）：

分解 (Decomposition / Partitioning)：将庞大的应用问题拆分成更小、更离散的部分，称为任务 (Tasks)。
调度 (Scheduling)：决定这些任务应该以何种顺序运行，必须严格遵守任务之间的数据依赖关系。
映射 (Mapping)：将调度好的任务分配到实际的物理处理单元（如 CPU 核心或 GPU 线程）上执行。

3. 不同层级的硬件并行架构

根据可用的计算资源，并行方法可以分为多个层级：

多核 CPU (Multicore)：利用单个机器上的多个处理器核心，通过共享内存系统（如 OpenMP 编程）进行多线程并行。
分布式系统 (Distributed)：将任务分发到由网络连接的多个独立计算节点（Node）上，通过消息传递（如 MPI 编程）进行通信，成本较高但扩展性极强。
图形处理器 (GPU)：采用成千上万个轻量级线程（如 NVIDIA H100 GPU 拥有海量线程）进行大规模数据并行计算，适合计算密集型任务。

第 2 部分：进程、线程与同步 (Processes, Threads & Synchronization)

为了在硬件上实现并行，我们需要依赖操作系统的抽象：进程和线程。

1. 进程 (Processes)

进程是正在执行的程序的实例。在 Unix 系统中，使用 fork() 系统调用可以创建一个新的子进程。

特点：子进程是父进程的精确副本，拥有自己独立的内存地址空间。
使用场景：非常适合子进程需要与父进程协作（如 Web 服务器处理客户端请求，父进程关闭套接字，子进程处理连接）。
缺点：由于进程间地址空间隔离，创建进程的开销很大；且进程间通信 (IPC) 必须通过操作系统（如共享内存机制需加锁，或使用消息传递），成本较高。

2. 线程 (Threads)

线程是进程内独立的执行流。一个进程中可以包含多个线程，它们共享相同的地址空间（堆、全局变量等），但每个线程拥有自己私有的栈 (Stack) 和寄存器（用于保存函数调用和局部变量）。

线程映射模型：
- 多对一 (Many-to-One)：用户级线程库管理多个用户线程并映射到一个内核线程。如果一个线程阻塞，整个进程都会阻塞，无法实现真正的多核硬件并行。
- 一对一 (One-to-One)：每个用户线程映射到一个内核线程。操作系统直接调度，支持真正的并行，是现代系统最常用的模型。
- 多对多 (Many-to-Many)：线程库将用户线程动态映射到一组内核线程池中，平衡了调度效率和并行能力。

3. 互斥与同步机制 (Synchronization)

由于线程共享内存，当它们同时读写共享变量时会导致数据竞争。我们需要同步机制来保护临界区 (Critical Section)。

竞争条件（Race Condition）：多个执行路径完成的顺序不确定，导致结果违背设计初衷。
锁 (Locks/Mutexes)：最基础的同步原语。为了防止上下文切换导致条件竞争，锁的 acquire (enter a critical session) 和 release (leave a critical session) 操作必须在硬件层面上保持原子性 (Atomic)。
- 自旋锁 (Spinlock)：锁的一种实现方式。线程在一个 while(lock->held) 循环中忙等待 (busy-wait)。虽然浪费 CPU 周期，但避免了线程挂起和恢复的上下文切换开销。
- 阻塞（Block）：通常指互斥锁（Mutex）。当锁不可用时，线程会进入睡眠或等待状态，交出 CPU 使用权。这里不需要CPU的原因是我们有中断控制器持续接收中断信号并发送给操作系统/timer也会定时发送信号让操作系统检查是否有ready。阻塞之后交出CPU会导致context switch。
Semaphores：由 Dijkstra 提出的高级机制，维护一个内部计数器。
- Wait() / P()：计数器减一，若小于0则线程阻塞。
- Signal() / V()：计数器加一，唤醒一个等待的线程。
- 信号量分为互斥信号量（二元信号量，类似于锁）和计数信号量（允许多个线程访问资源）。

5. Parallelization带来的问题

Deadlock：一组进程中的每个进程都在等待只能由该组中另一个进程引发的事件。

四个必要条件：互斥、占有且等待、不可剥夺、循环等待。
饥饿（Starvation）：进程因调度算法或资源竞争长期无法获得所需资源。例如高优先级线程一直占有CPU
活锁（Livelock）：进程状态不断改变但始终无法取得进展。

4. 经典同步问题

生产者-消费者 (Producer-Consumer)：生产者将数据放入缓冲区，消费者从中取出。需要使用 mutex 保护缓冲区，并使用计数信号量（如 items 和 spaces）来通知消费者有新数据，或通知生产者缓冲区有空位。
读者-写者 (Readers-Writers)：允许多个读者同时读取共享数据，但写者必须拥有独占访问权。
- 为了解决写者可能被源源不断的读者“饿死 (Starvation)”的问题，需要引入“旋转门 (Turnstile)”或“光开关 (Lightswitch)”设计，利用优先级来确保写者能够公平地获得锁。

第 3 部分：硬件架构与内存组织 (Architecture & Memory Organization)

为了写出高性能的代码，我们必须理解底层的硬件工作原理。

一、处理器的并行化演进

现代 CPU 性能的提升主要依赖于在硬件中实现多种形式的并行性。

概念区分：Concurrency vs Parallelism

concurrency指的是多个线程在同一时间短内交错/同时计算。parallelism指的是必须同时计算。

1. 单核并行性 (Single-Core Level)

位级并行 (Bit Level Parallelism): 通过增加字长 (Word Size) 来增加每秒处理的数据量。
- 历史趋势：从 16 位演进到目前的 64 位。
- Superword: 除了多核并行，在单一核心内，64 位处理器现在甚至配备了 512 位宽的 AVX-512 寄存器。这意味着只需一条指令，就可以同时执行 8 个 64 位浮点数的加法运算，极大地提升了密集型计算的吞吐量。
指令级并行 (Instruction Level Parallelism, ILP):
- Pipelining: 将指令执行分为 Fetch, Decode, Execute, Write-back 等阶段。流水线的最大敌人是分支指令 (Branch)（如 if-else）。如果分支预测器 (Branch Predictor) 猜错了路径，流水线就必须清空 (Flush) 错误的指令，造成极大的性能浪费。因此，优化代码的第一准则是：尽可能减少分支，或让分支变得可预测。
- Superscalar: 在流水线每个阶段提供多个“槽位”，支持在同一周期执行多条指令。
  
  上图的结构可以获得下图的运行方式：
线程级并行 (Thread Level Parallelism, TLP):
- 由于典型的程序只能在单核中实现 2-3 条指令的并行执行，因此引入了同时多线程 (SMT) 技术（如 Intel 的超线程）。
  概念区分：8核16线程就是超线程技术。但是我们仍然能开到32线程。16线程是硬件支持的，有16套register和counters等。如果我开到32线程，就必须让OS进行context switch了，剩下的线程context存在内存中。
- 通过在单个物理核心内维护多个“执行上下文”（逻辑核心），当一个线程停顿时，另一个线程可以继续运行。

二、Flynn 的体系结构分类法

Flynn 根据指令流和数据流对计算机架构进行了分类：

SISD (单指令单数据)：传统的单核处理器。
SIMD (单指令多数据)：同一条指令被广播到多个算术逻辑单元 (ALU) 上，对不同的数据进行相同的运算。这是实现数据级并行的核心。现代 CPU 的 AVX/SSE 矢量指令以及 GPU 很大程度上依赖于 SIMD 思想。（一个核心中可能有很多个PU）
MISD (多指令单数据)：罕见的架构，主要用于容错系统。
MIMD (多指令多数据)：现代多核处理器的标准架构。每个核心有自己的指令流并操作独立的数据。

三、内存组织 (Memory Organization)

在现代计算中，带宽 (Bandwidth) 是关键资源。为了利用现代处理器的效率，程序必须减少对内存的访问频率。

1. 缓存系统 (Cache System)

层次结构: 包括 L1 (32 KB)、L2 (256 KB) 和共享的 L3 (8 MB) 。
作用: 处理器算术运算极快，而主存读取极慢。缓存通过存储常用数据来减少访问延迟。
缓存一致性 (Cache Coherence): 当同一数据的多个副本存在于不同缓存中时，硬件协议必须确保所有核心看到的数据是一致的。

2. 并行计算机内存架构

分布式内存 (Distributed-Memory): 每个节点拥有私有内存，数据必须在节点间显式发送。
共享内存 (Shared-Memory):

program is unaware of the actual hardware memory architecture. The 'shared memory provider' abstraction layer should handle cache coherence and memory consistency (covered in topic 6)

memory delay
- UMA (uniform memory access): 所有处理器访问主存的延迟相同，适用于少量处理器。
- NUMA (non-uniform memory access): 处理器访问本地内存比访问远程内存更快。
- COMA (Cache only memory architecture): 每个内存块都充当缓存，data migrates dynamically and continuously according to the cache coherence scheme.
CC/NCC
- 是否有local cache with cache coherence protocol。

第 4 部分：并行编程模型与 Foster 方法学 (Programming Models)

1. 数据并行 vs 任务并行

数据并行 (Data Parallelism)：对不同的数据块执行相同的操作（类似于 SIMD 或 SPMD）。例如将一个大矩阵切分为多个子块，分配给多个线程计算。
任务并行 (Task Parallelism)：独立执行不同的功能任务。例如一个气候模型，线程 1 算风速，线程 2 算温度，功能各异但可以并行推进。可以通过任务依赖图 (Task Dependence Graph) 来评估哪种分解策略最优。
形象理解：助教改卷子

数据并行：3个助教，每人分50份完整的实验报告进行批改。

任务并行：助教1改所有报告的第1-2题，助教2改3-4题，助教3改5-6题。

2. 任务依赖图 (Task Dependence Graph)

为了评估并行策略，我们会使用有向无环图 (DAG) ：

节点：代表任务，节点内的数值通常表示预期的执行时间（工作量）。
边：代表任务之间的依赖关系。
Key indices：
- Critical Path Length：完成任务所需的最长路径时间。
- Degree of Concurrency：Total_work / Critical_path_length，反映了平均可以同时进行的任务量。

3. Models of coordination

模型	原理	优点	缺点
共享地址空间	任务通过读写共享变量进行通信。	编程相对简单。	扩展性受限，需处理互斥（锁）。
消息传递	任务拥有私有空间，通过显式发送/接收消息通信。	适合大规模集群和超算。	编程复杂，有网络延迟。

2. Foster's methodology

当面对一个需要并行化的问题时，可以遵循这四个阶段：

Partitioning：尽可能将问题切分为Fine-grained的小任务。
1. Data centric: divide data into pieces of approximately equal size.
2. Task centric: divide computation into pieces of tasks.
Partitioning Rule of thumb:
- At least 10x more primitive tasks than core in target computer.
- Minimize redundant computations and redundant data storage
- Primitive tasks roughly of the same size
- Number of tasks as an increasing function of problem size
Communication (Coordination)：分析这些小任务之间如何交换数据。

Global communication is likely a limiting factor for parallelism because it is 1) centralised 2) sequential

Communication Rules of Thumb
- Communication operations balanced among tasks
- Each task communicates with only a small group of neighbors
- Overlap computation with communication
Agglomeration：如果细粒度任务通信过于频繁，将它们合并成较大的粗粒度任务，以降低通信开销。(tiling)
Mapping：将合并后的任务分配到具体的物理处理单元，目标是最大化利用率，最小化通信延迟（这两个目标是有一定冲突的）。

3. 常见并行设计模式

Fork-Join：主线程生成多个子线程去完成子任务，最后等待 (Join) 所有子线程结束，汇总结果。
Parbegin-Parend(SPMD)：所有线程在同一时间点产生并执行相同或相似的代码，执行完毕后在同一终点同步。OpenMP 中的并行为循环 #pragma omp parallel for 就是这种模式。
Master-Worker：一个Master进程负责初始化数据和分配任务，多个 Worker 进程死循环等待并处理任务。在 MPI 分布式编程中极其常见。
任务池 (Task Pools)：维护一个共享的任务队列。预先创建固定数量的线程，线程做完当前任务就去池中取下一个。非常适合每次任务耗时极度不均匀的动态负载平衡场景（需注意队列的锁同步开销）。
Producer-Consumer: 有一个或多个producer产出数据，给一个或多个consumer使用。
流水线 (Pipelining)：将处理过程划分为多个串行阶段，数据如同流水般经过各个处理单元（流并行），极大地提高了数据吞吐量。（不是datapath pipelining，是更宏观的pipelining）

第 5 部分：并行系统性能分析 (Performance of Parallel Systems)

(重要考点：在考试和作业中，性能瓶颈的分析和理论计算是重中之重。)

1. 核心性能指标

Latency/response time：完成单个任务所需的时间。
Throughput：单位时间内完成的工作量（例如：每秒完成的作业数）。大型超算中心通常更关心吞吐量。
Execution time, $T_p(n)$ ：Execution time on problem of size n with p threads. 包含实际计算时间、数据交换时间、同步时间以及等待（如负载不均或锁争用）的时间。
Speedup, $S_p$ ： $S_p = \frac{T_{seq}}{T_p}$ ，理论上限为处理器数量 $p$ 。当达到 $p$ 时称为线性加速比。实际上，可能由于例如cache不用重复搬运，可能 $S_p(n) > p$
Cost, $C_p(n)$ : $C_p(n) = p\times T_p(n)$ 可以认为是总计算量/时间
Efficiency, $E_p(n) = S_p(n) / p = T_*(n) / C_p(n)$ : How good the speed up is compared to theoretically maximum speedup.

2. Amdahl 定律 vs Gustafson 定律的较量

业界对并行系统潜力的两种截然不同的观点：

Amdahl 定律 (悲观视角)：假设计算问题的大小 (Problem Size) 固定不变。代码永远包含一部分无法并行的串行比例 ( $f$ )。根据公式： $S_p \leq \frac{1}{f + \frac{1-f}{p}}$ 。无论使用多少个核心（ $p \to \infty$ ），最大可能加速比永远被受限于 $\frac{1}{f}$ 。例如，哪怕代码只有 5% 是串行的 ( $f=0.05$ )，使用百万个核也最多只能加速 20 倍。这曾一度打击了业界研发大规模并行计算机的信心。

Gustafson 定律 (乐观视角)：在现实世界中，算力增强后，人们不会停留在固定的问题上，而是会扩大问题的规模。 $S_p(n) = \frac{f'T_p(n) + (1-f')T_p(n)p} {f'T_p(n) + (1-f')T_p(n)} = f' + (1 - f')p$ 。随着问题规模 $n \to \infty$ ，可并行部分的计算量急剧增加，而串行部分（如启动时间）基本保持不变（这里的假设和上面不同），因此串行比例 $f' \to 0$ 。根据公式：当 $n$ 足够大时，加速比仅受限于处理器的数量 $p$ ( $S_p = p$ )。这证明了超级计算机存在的合理性。

3. 性能建模与内存瓶颈

CPU time

如何精确估算一个程序的运行时间：

V1 版本：简单地将周期总数乘以周期时间。
V2 版本：考虑到现代 CPU 的Frequency Scaling(not constant clock rate)，改用平均周期时间。
V3 版本：引入 CPI（每条指令所需周期数） 。
- $Timeuser(A)=N_{instr}(A)×CPI(A)×Time_{avg_cycle}$

单纯的指令数计算模型是不够的，更精确的模型必须考虑Memory Stalls。现代计算中，带宽才是最致命的瓶颈。

memory models

Refinement with memory access time

$Time_{user}(A) = (N_{cycle}(A) + N_{mm\_cycle}(A)) \times Time_{avg\_cycle}$

$N_{mm\_cycle}(A) = N_{read\_cycles}(A) + N_{write\_cycles}(A)$

One-level cache with instant r/w hit

$N_{read\_cycles}(A) = N_{read\_ops}(A) \times R_{read\_miss\_rate}(A) \times N_{miss\_cycles}(A)$

$Time_{user}(A) = (N_{instr}(A)\times CPI(A)) + N_{rw\_op}(A)\times R_{miss}(A) \times N_{miss\_cycles} \times Time_{cycle}$ ( $R_{miss}(A)$ r/w miss rate)

One-level cache with avg memory access time

$T_{read\_access}(A) = T_{read\_hit} + R_{read\_miss}(A) \times T_{read\_miss}$

Two-level cache

$T_{read\_access}(A) = T^{L1}_{read\_hit} + R^{L1}_{read\_miss}(A) \times T^{L1}_{read\_miss}$

$T^{L1}_{read\_miss}(A)= T^{L2}_{read\_hit}(A) + R^{L2}_{read\_miss}(A) \times T^{L2}_{read\_miss}$
Global miss rate = $R^{L1}_{read\_miss}(A) \times R^{L2}_{read\_miss}(A)$

模型可能在特定情况下有用，但是他们（尤其是mental models）大概率是不准确的。

throughput metrics

Million-Instructions-Per-Second(MIPS): $MIPS(A) = N_{instr}(A) / (Time_{user}(A) \times 10^6)$

drawbacks: easily manipulated, considers only number of instructions
Million-Floating point-Operations-Per-Second(MFLOP/s)

$MFLOP/s(A) = N_{fl\_ops}(A) / (Time_{user}(A) \times 10^6)$

可以用于测试计算机速度，也可以测试程序运行速度

算术强度 (Arithmetic Intensity)：= amount of computation / amount of communication。算术强度越高，程序性能更Compute-bound；反之，如果数学计算很快但需要等待数据，程序性能更Memory-bound。

roofline model:

在同一台机器上，程序的throughput由这个曲线决定最大值。其中斜坡部分是memory bound，因为computation使用较少；roofline部分是computation bound。

内存优化策略：为了提升性能，必须利用好 CPU 缓存（Cache Block / Cache Line 机制）：

时间局部性 (Temporal Locality)：让同一个线程重用已经加载到 L1 缓存中的数据。
空间局部性 (Spatial Locality)：缓存是以块（Cache Line，通常为 64 字节）为单位加载的。因此，数据访问应该在内存地址上保持连续。如果跳跃访问，即使只需要 4 字节，也会强制加载 64 字节，造成带宽的极大浪费。
<span id="padding">数据填充 (Padding)</span>：多线程处理数组时，可能会由于不同线程的数据物理位置太近，落入同一个 Cache Line 中，从而导致后续的“伪共享”问题。通过在数据后添加无用的 Padding 字节，可以强行将不同线程操作的数据推开到不同的 Cache Line 里面。

4. takeaways

第 6 部分：Cache Coherence & Consistency)

1. 核心问题：共享内存真的那么简单吗？

在现代多核架构中，每个核心都有自己的私有缓存（L1/L2），而它们共享同一个主内存。这引出了两个关键挑战：

Cache Coherence： 多个核心同时读写同一个内存位置时，如何保持数据同步？
Memory Consistency： 多个核心读写不同内存位置时，如何定义事件发生的顺序？

2. Cache Coherence

一致性探讨的是：多个核心对同一个内存地址 (同一变量) 进行读写时的硬件保证。必须满足三大属性：

程序顺序 (Program Order)：单个核心内部，必定观察到自己按代码顺序发出的读写。
写入传播 (Write Propagation)：一个核心对变量 $A$ 的写入，最终必定能被其他核心观察到。
事务串行化 (Transaction Serialization)：所有核心对同一个变量 $A$ 的写入历史，必须达成一致。例如 $A$ 依次被写为 1、2，没有核心能先读到 2 再读到 1。

硬件实现与问题：

硬件通过一致性协议自动实现这些保证。

监听协议 (Snooping-based)： 控制器广播更新到共享总线，其他缓存监听总线来更新或失效自己的状态。总线会检测并serialize writes
目录协议 (Directory-based)： 使用中央目录记录每个数据块的状态，通过点对点通信避免广播，更适合大规模系统（如 NUMA）。

(controller属于snooping based；directory属于directory based)

但在编程中，如果不注意，会引发伪共享 (False Sharing) 导致缓存乒乓 (Cache Ping-Pong) 效应。当核心 1 修改变量 X，核心 2 修改变量 Y（且 XY 在同一个缓存行中）时，由于一致性协议的粒度是整个 Cache Line，硬件会认为这两者发生了冲突。导致该缓存行在核心 1 和核心 2 的 L1 缓存间疯狂失效和互相传输，使性能暴跌。使用 perf c2c 命令可以进行精准剖析。

(跨章节关联：这也就是为什么我们在 L05 中必须引入 Padding 填充优化的原因。)

2. 内存一致性模型 (Memory Consistency)

与缓存一致性不同，内存一致性约束的是：多个核心对不同内存地址 (不同变量) 的读写操作被观察到的顺序。由于硬件和编译器会为了隐藏延迟而激进地重排 (Reorder) 指令，这会打破程序员在写同步代码时的直觉预期。

Sequential Consistency, SC：最直观、最严格的模型。每个核心内部所有指令严格按程序代码的顺序执行，就好像所有核正在轮流排队访问一个单一的中央内存。绝不允许任何重排，极度安全但性能低下。
Total Store Ordering, TSO / x86架构常用：放宽了写 $\to$ 读的顺序。允许一个核心将数据写入非阻塞的 Store Buffer，然后立刻执行后面的读取操作。这可能导致它读到新数据，而其他核心还未观察到该写入。但保留了write atomicity（一旦写入全局可见，所有核心同时看到）。
Processor Consistency, PC：同样放宽写 $\to$ 读，并且break write atomicity。一个写入可能先被核心 2 看到，晚一点才被核心 3 看到。
Partial Store Ordering, PSO：进一步放宽了写 $\to$ 写的顺序。对不同内存地址的多次写入也能够在缓冲区里互相插队重排。极其自由且快速，但程序员如果不加屏障 (Barriers) 手动控制，很容易写出致命 Bug。

静态上，编译器会进行一轮OoO重排；动态上，runtime也会进行store buffer优化，即CPU不进行等待，而是将指令放到store buffer中让store buffer更新cache

第 7 部分：GPU 架构与 CUDA 编程 (GPU Programming & Architecture)

面对 Amdahl 定律，既然提高串行性能已经见顶，我们只能增加极大量的处理器（ $p$ ）来突破极限。由于 CPU 为了保持单核极速和复杂的控制流（如深度缓存体系和分支预测）变得非常庞大，我们无法在一个芯片上塞入几千个 CPU 核心。这就是 GPU (图形处理器) 诞生的背景。

1. GPU 架构原理 (以 Hopper 架构为例)

GPU 的哲学是：用巨量的并行计算来掩盖延迟，而不是用缓存来减少延迟。

流多处理器 (SM - Streaming Multiprocessor)：GPU 的核心构建块。一个 GPU（如 H100）包含多达上百个 SM。
流处理器 / CUDA核心 (SP - Streaming Processor)：每个 SM 内包含数百个 SP，专门执行数学运算（FP32, FP64, Tensor Core）。它们共享一个极其快速的 L1 数据缓存 / 共享内存模块。

细致讲解：

1 SM consists of 4 SMSP's.

1SMSP has 1 set of processing units, dispatch unit, scheduler, etc.

1SMSP can only run 1 warp simultaneously.

一个SMSP有多个warp槽，这样有延迟的时候可以换一个运行。如果一个SM有16个warp,那么每个SMSP会被分到4个。

一个SMSP能承载的上限由register使用决定，如果每个thread要用128个register,那么一个SMSP可以承载16384/128/32=4个warp。不过如果每个thread用很少register，并不代表一个SMSP可以有很多很多warp，而是由warp槽数量决定上限。

一个block可能使用50个thread，这种情况下有14个thread会被闲置，因为每个warp必须运行相同指令。block实际上利用了programmer所认为的locality。一个SM有承载的block数量上限，同时SM的maximum也由每个block占据的shared memory决定。

所以bottle neck可以分为下面四个：

场景	限制因素 (Bottleneck)	结果
Block 很大 (如 1024 线程/Block)	最大线程数	每个 SM 只能放 2 个 Block (2 * 1024 = 2048)。
Block 很小 (如 32 线程/Block)	最大 Block 数	每个 SM 只能放 32 个 Block，即便总线程才 1024 个 (没满 2048)。
寄存器用量极高	寄存器堆大小	哪怕 Block 很少，寄存器不够分了，也无法增加更多 Warp。
Shared Memory 用量极高	共享内存大小	内存被分光了，剩下的空间塞不下新的 Block。

2. CUDA 编程与内存层次模型

NVIDIA 开发了 CUDA 让开发者能编写 C++ 代码在 GPU 上运行。代码分为 Host (CPU端) 和 Device (GPU端)，运行在 GPU 上的核心函数用 __global__ 修饰。

线程分层机制：

Thread：最基础执行单元，极轻量级。
Block (线程块)：一组线程。核心规则：一个 Block 一旦被分配给某个 SM，就会一直在该 SM 上执行直到结束，无法迁移。（block不能超出一个SM所能承载的thread数量）在同一个 Block 内的线程可以访问超高速的共享内存 (Shared Memory) 并且可以通过 __syncthreads() 实现屏障同步。
Grid (网格)：一个 Kernel 函数启动产生的所有 Block 构成一个 Grid。Block 之间是相互独立的，通常无法安全地跨 Block 同步。

CUDA 内存模型设计：

Registers (寄存器)：每个线程独享，速度极快（每个线程最多 255 个）。GPU 没有上下文切换开销，因为所有状态都保存在这庞大的寄存器文件中。
Shared Memory (共享内存)：分配给整个 Block，速度媲美 L1 缓存，程序员手动管理。
Global Memory (全局内存)：GPU 的 VRAM 主存。容量大但极其缓慢。所有优化都围绕着减少对全局内存的访问展开。

3. SIMT 执行模型与性能优化陷阱

Warp 与 SIMT 执行：

当一个 Block 被分配到 SM 后，线程会被打包成每 32 个线程 一组的单位，称为 Warp。
GPU 采用 SIMT (单指令多线程) 模式。在一个 Warp 内，调度器在每一个时钟周期发射一条指令，这 32 个线程同时对各自的寄存器数据执行这同一条指令。
延迟掩盖：如果 Warp A 停顿等待内存返回，调度器会瞬间无缝切换，把空闲的计算单元交给准备好执行运算的 Warp B。

Warp Divergence (Warp 分化)：如果你的代码写了 if-else 分支。由于一个 Warp 内的 32 个线程必须在同一个时钟周期执行同一条指令，当一部分线程进入 if，另一部分进入 else 时，硬件无法同时执行这两条路径。结果是：GPU 会先把 else 线程强制挂起闲置（Mask off），让 if 线程串行执行完；然后再挂起 if 线程，去执行 else 逻辑。这种分化会极大地拖慢吞吐量。永远要避免在一个 Warp 内产生逻辑分化。

Coalesced Memory Access (合并内存访问)： GPU 访问缓慢的全局内存时，硬件总是以 32 字节或 128 字节的区块 (Chunk) 为单位进行加载。

Good (合并访问)：Warp 内的线程 0 访问地址 0，线程 1 访问地址 1... 访问呈现完美的空间连续性。硬件一次取回的 128 字节全是这 32 个线程立刻需要用的数据。内存利用率 100%。
Bad (非合并访问)：线程 0 访问地址 0，线程 1 访问地址 8（跳跃跨度很大）。这会导致 32 个线程分散在广泛的内存区域中。硬件为了满足这 32 个线程，不得不去主存里取回 32 个互相不相干的 128 字节块，其中绝大部分加载的字节都是废弃不用（无用带宽）的。内存利用率暴跌至 12.5% 甚至更低。

Bank Conflicts (共享内存 Bank 冲突)：即使使用了高速的 Shared Memory 也要小心。Shared Memory 被划分为多个 Bank。如果 Warp 内的不同线程去访问同一个 Bank 里的不同地址，硬件无法并发处理，只能将请求强制串行化处理（这称为 Bank Conflict），导致成倍的性能损失。

memory model

variables other than arrays首选register，也有可能被spill到local memory里面。

4. 优化 CUDA 的核心准则

最大化throughput：使用轻量级运算，对于不重要的数学计算可以“牺牲精度换取速度”（如优先使用单精度浮点），避免极其昂贵的integer division和modulo用bitwise operation代替。
充分利用 Shared Memory：如果全局内存中的某个数据块需要被反复使用（例如矩阵乘法），先让 Block 中的线程协作将其从全局内存载入到 Shared Memory，执行完所有密集计算后再写回全局内存。
保持高 Occupancy (占用率)：确保 SM 上的活跃 Warp 数量足够大，才能利用零成本上下文切换掩盖任何延迟。但是occupancy太大会导致warp太多，register无法承载只能用local memory
使用 Streams 实现数据传输 (cudaMemcpyAsync) 与 GPU 计算的并发重叠。

第 8 部分：消息传递与 MPI

1. 引入与动机 (Introduction & Motivation)

单节点系统的局限性： 单个节点（即使配备强大的 CPU/GPU）在内存容量和内存带宽上会遇到瓶颈。
大规模并行问题： 对于串行比例足够小或问题规模极大的情况（例如，大型流体模拟、全球气候建模、参数量庞大的分布式机器学习模型），单节点系统无法满足需求。
编程范式的转变：
- 共享地址空间（以往范式）： 在分布式节点上，由于远程内存访问速度远慢于本地内存（如网络传输需要 1000ns - 30000ns+），共享内存模型不再适用。
- 分布式地址空间（新范式）： 数据被显式地划分给每个进程。所有的数据交互都需要发送方和接收方的共同参与。这种范式下没有数据竞争（Data Races），因为内存空间是独立的，但程序员需要显式地表达并行性。

2. MPI 基础概念 (MPI Basics)

什么是 MPI？ MPI (Message-Passing Interface) 是一种标准化的消息传递库规范，定义了函数签名、行为等。常见的实现包括 OpenMPI、MPICH 和 Intel MPI 。
语言支持： 作为库调用提供（如 MPI_Send, MPI_Recv），可直接在 C 和 Fortran 中调用，也通过绑定支持 Python, C++, Java 等语言。
执行模型：
- 采用 SPMD (Single Program Multiple Data) 模型，即所有进程运行相同的程序，但处理不同的数据。
- 进程间属于松散同步（Loosely synchronous），仅在需要通信时同步，其余时间独立运行。
基本程序结构： 任何 MPI 程序都必须以 MPI_Init 初始化，并以 MPI_Finalize 结束。异常终止可使用 MPI_Abort 。

3. 点对点通信 (Point-to-Point Communication)

点对点通信用于一个特定发送进程向一个特定接收进程传递数据。

3.1 消息的组成 (Message Format)

Data（数据部分）： 包括数据的起始地址 (start-address)、数据元素的数量 (count) 以及数据类型 (datatype) 。
Envelope（信封部分）： 决定数据如何路由，包含目标或源进程的 rank (destination/source)、用于区分消息的标签 (tag) 以及通信子 (communicator) 。

3.2 通信语义分类 (Communication Semantics)

在处理大量数据传输时，发送和接收的底层行为有以下重要区分：

阻塞 (Blocking) vs 非阻塞 (Non-blocking)：
- 阻塞： 当函数返回时，程序员可以安全地重用调用中使用的资源（例如发送缓冲区可以被覆盖）。例如：MPI_Send, MPI_Recv 。
- 非阻塞： 函数返回时，资源可能尚未被安全地发送或复制，不能立即重用。优势在于可以利用等待的时间执行其他计算工作，掩盖通信延迟。需要结合测试/等待函数（如 MPI_Test, MPI_Wait）来确认操作是否完成。例如：MPI_Isend, MPI_Irecv 。
缓冲 (Buffered) vs 非缓冲 (Non-buffered)：
- 缓冲调用： 将用户数据复制到内部系统缓冲区后，立即将控制权交还给用户。这是一种用空间换取时间的策略。
- 非缓冲调用： 发送方必须等待接收方准备好接收数据，这可能导致显著j的空闲等待时间（Idling overheads）。

同步 (Synchronous) vs 异步 (Asynchronous)：

同步发送： 必须等待匹配的接收操作开始执行后才能完成，具有非本地（Non-local）行为特性。
异步发送： 不需要与接收进程协调，自身即可完成，具有本地（Local）行为特性。

blocking async：等到数据搬移到buffer才结束blocking。注意async if buffered，如果没有buffer退化成sync。

non-blocking：我们要用send/recv 返回的 MPI_Request handle 手动 MPI_Wait。

#include <mpi.h>
#include <iostream>

int main(int argc, char** argv) {
    // 初始化 MPI 环境
    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) std::cerr << "该范例需要至少 2 个进程。" << std::endl;
        MPI_Abort(MPI_COMM_WORLD, 1);
    }

    int send_data = rank + 10; // 准备发送的数据
    int recv_data = -1;        // 接收缓冲区
    int target = (rank == 0) ? 1 : 0; // 确定对方的 Rank

    // 声明请求句柄 (Handle)
    MPI_Request send_request, recv_request;
    MPI_Status status;

    // 1. 发起非阻塞接收：先“挂号”，告诉系统我想收谁的数据
    MPI_Irecv(&recv_data, 1, MPI_INT, target, 0, MPI_COMM_WORLD, &recv_request);

    // 2. 发起非阻塞发送：把数据交给系统，函数立即返回
    MPI_Isend(&send_data, 1, MPI_INT, target, 0, MPI_COMM_WORLD, &send_request);

    // --- 此时通信正在后台进行 ---
    // 你可以在这里执行不依赖 recv_data 的复杂计算 
    std::cout << "Rank " << rank << " 已发起通信，正在执行后台任务..." << std::endl;
    // --- ----------------- ---

    // 3. 显式同步：必须确保通信完成后才能使用数据
    // 等待发送请求完成：此时可以安全重用/修改 send_data 缓冲区
    MPI_Wait(&send_request, &status); 
    
    // 等待接收请求完成：此时 recv_data 中才真正存入了对方发来的数据
    MPI_Wait(&recv_request, &status);

    std::cout << "Rank " << rank << " 成功接收到来自 Rank " << target 
              << " 的数据: " << recv_data << std::endl;

    // 结束 MPI 环境
    MPI_Finalize();
    return 0;
}

3.3 死锁与消息顺序 (Deadlocks & Ordering)

死锁原因：
- 收发顺序错误： 如果两个进程都先执行阻塞接收（或阻塞发送），会导致循环等待，产生死锁。解决方式如采用逻辑环，错开奇偶进程的收发顺序。也可以MPI_Isend (立即返回) -> MPI_Recv (阻塞等待进程 1)
- 依赖系统缓冲： 如果运行时系统不使用缓冲区，或者发送的数据量超出了系统缓冲区的大小，原本看似合理的收发代码也会死锁。
消息顺序： MPI 保证非抢占属性 (Non-overtaking property)，即同一个发送方发送给同一个接收方的多条消息，将按照发送顺序到达。但对于涉及三个及以上进程的消息，送达顺序是未定义的。

4. 进程组与通信子 (Process Groups and Communicators)

将进程逻辑上分离，有助于针对特定任务的进程子集执行集合通信，并建立虚拟拓扑。

进程组 (Process Groups)： 是进程的有序集合。组内每个进程从 0 开始拥有一个唯一的 rank 。一个进程可以属于多个组，并在不同的组中拥有不同的 rank 。
通信子 (Communicators)： 是进程用于互相通信的handle 。
- Intra-communicators： 支持单个进程组内的点对点和集合通信（例如默认的 MPI_COMM_WORLD，包含所有进程）。
- Inter-communicators： 支持两个不同进程组之间的通信操作。
虚拟拓扑 (Virtual Topologies)： 将进程组织成特定的逻辑结构，如网格（笛卡尔拓扑，Cartesian）或图结构（Graph），使得相邻进程更容易被寻址。

5. 集合通信 (Collective Communication)

集合通信指涉及通信子中所有进程的操作。

硬性规定： 通信子内的每一个进程都必须调用该集合通信函数，否则（尤其是使用阻塞调用时）会导致死锁或未定义行为。
同步操作： MPI_Barrier。这是唯一没有数据移动的集合操作，所有进程阻塞，直到通信子内所有进程都到达此屏障。
常见数据移动操作：
- 单点广播 (Single Broadcast)： MPI_Bcast。根进程将相同的数据块发送给所有其他进程。
  
  count：Root 进程发送给每一个进程的元素个数。
- 多点广播 (Multi-Broadcast)： MPI_Allgather。没有根进程，每个进程将自身的数据块发送给其他所有进程，数据按 rank 顺序收集。
  
  sendcount：每个进程贡献出的元素个数。
  
  recvcount：从每一个进程处接收到的元素个数。
- 分发 (Scatter) 与收集 (Gather)：
  - MPI_Scatter：根进程将一段连续的数据分割，分配给自己和其他进程。
    
    sendcount：Root 发送给每一个进程的元素个数。
    
    recvcount：每个进程接收到的元素个数。
  - MPI_Gather：根进程收集所有进程发送的数据块。
    
    sendcount：每个进程发送给 Root 的元素个数。
    
    recvcount：Root 从每一个进程收到的元素个数。
- 单点归约 (Single-accumulation / Reduce)： MPI_Reduce。在收集数据的同时应用特定的规约操作（如求和），结果存放在根进程。
  
  count：每一个进程参与规约的元素个数。
- 多点归约 (Multi-accumulation)： MPI_Reduce_scatter。每个进程为其他进程提供不同的数据块，相同接收者的数据被组合归约，没有根进程。
- 全交换 (Total Exchange)： MPI_Alltoall。每个进程向其他每个进程提供不同的数据块，相当于每个进程都执行了一次 Scatter 操作。
  1. 它是随机的吗？ (Is it random?)
  绝对不是随机的。 它的分发逻辑极其严格：
  - 每个进程执行的都是一次确定性的 Scatter 。
  - Rank 0 的发送缓冲区中：
    - 第 1 块数据发给 Rank 0（自己）。
    - 第 2 块数据发给 Rank 1 。
    - 第 $i$ 块数据发给 Rank $i-1$ 。
  - 最终结果是：每个进程都从其他所有进程那里拿到了属于自己的那一块，并按发送者的 Rank 顺序排好。
  1. sendcount 和 recvcount 怎么写？
  这是 MPI 初学者最容易写错的地方。这两个参数指的不是“总数”，而是“发给（或来自）每一个进程的数量”。
  
  参数定义：
  - sendcount：发送给单个目标进程的元素个数。
  - recvcount：从单个源进程接收的元素个数。
  举个例子：
  
  假设你有 4 个进程（ $P=4$ ），每个进程想给其他每个进程发 2 个整数。
  - 你的 sendbuf 总大小应该是 $4 \times 2 = 8$ 个整数。
  - 你的 recvbuf 总大小也应该是 $4 \times 2 = 8$ 个整数。
  - 但是，在 MPI_Alltoall 调用中：
    - sendcount = 2
    - recvcount = 2

第 9 部分：互连网络与数据分布 (Interconnection Networks and Data Distribution)

1. 引言与背景

在分布式内存编程（如使用 MPI）中，主要面临两个核心问题：

数据分布：我们应该如何在多个处理单元（PUs）之间拆分和分配问题？
硬件互连：底层硬件如何连接？这些物理连接方式是否会影响并行计算的效率？

2. 数据分布 (Data Distribution)

并行计算问题通常基于一维、二维到 n 维的数组。研究如何分解这些数组并将其分布到多个处理器节点上（即数据分布、工作分布或分区），有助于最大化数据并行性。

2.1 一维数组的数据分布

假设有 $p$ 个相同的处理器和 $n$ 个数组元素，常见的分布模式包括：

块状分布 (Blockwise Distribution)：
- 计算块大小 $B = \lceil\frac{n}{p}\rceil$ 。
- 每个处理器最多获取 $B$ 个连续元素，起始索引为 $((j-1)\times B+1)$ 。
- 适用场景：适合经常对空间相邻元素进行操作的程序。
循环分布 (Cyclic Distribution)：
- 处理器 $P_{j}$ 采用轮询方式获取元素。
- 适用场景：适合需要跨处理器平衡负载的程序。

2.2 二维数组的数据分布

对于二维数组，可以在一个或两个维度上结合使用块状或循环分布：

块-循环分布 (Block-Cyclic)：先将元素分成大小为 $b$ 的块，然后进行循环（轮询）分配。
棋盘式分布 (Checkerboard)：处理器在逻辑上组织成 $R \times C$ 的二维网格，并应用块状或循环分布。

2.3 边界通信与权衡

在实际问题中（例如金属板热传导模拟），即使数据被很好地分布，通信往往也是不可避免的。

处理器在每个时间步后，需要向相邻的处理器请求边界数据的最新值。
在固定的问题规模下，增加处理器数量会导致每个处理器的计算任务更细化，但同时也会增加每步所需的通信量。
关键结论：根据处理器需要访问的数据仔细选择分布模式，并时刻留意数据边界处的通信开销。

3. 互连网络基础 (Interconnection Networks)

互连网络解决了系统中不同组件（如处理器内部核心、缓存、内存、甚至物理分离的计算节点）之间如何连接的问题。

主要分为两大类：

直接互连 (Direct Interconnection)：由点对点的直接连接构成，也称为静态互连。
间接互连 (Indirect Interconnection)：通过交换机（Switches）动态形成连接。

4. 直接互连网络 (Direct Interconnects)

直接互连拓扑可以建模为图 $G = (V, E)$ ，其中顶点 $V$ 代表处理器，边 $E$ 代表连接电缆。

4.1 关键网络指标 (Key Metrics)

直径 (Diameter, $\delta(G)$ )：网络中任意两节点间最短路径的最大值。较小的直径意味着消息传输在最坏情况下的距离更短，延迟更低。
度数 (Degree, $g(G)$ )：图中单个节点拥有的最大直接邻居数量。度数越小，节点间链路越少，硬件成本越低。
对分宽度 (Bisection Width, $\beta(G)$ )：将网络划分为两个相等部分时，必须移除的最少边数。它反映了网络在最坏情况下的通信容量和瓶颈带宽。
连通性 (Connectivity)：分为节点连通性和边连通性，代表必须发生多少次节点或边故障才会导致网络断开连接，用于衡量网络的鲁棒性。

4.2 常见拓扑结构

线性阵列与环形 (Linear Array & Ring)：线性阵列适合流水线算法（也称脉动阵列）。如果将其首尾相连，则构成环形网络。
网格与环面 (Mesh & Torus)：在二维网格中，角落的节点只有2条链路；如果将边缘节点环绕连接，所有节点都有4条链路，这就是 Torus (环面) 。
超立方体 (Hypercube)：具有 $n=2^k$ 个节点，其节点度数和直径均为 $\log_2 n$ ，对分宽度为 $n/2$ 。
立方体连接环 (Cube-Connected-Cycles, CCC)：通过将超立方体中的每个节点替换为一个循环环，将网络节点的度数固定为 3 。
2-D Mesh and Torus:
Complete Binary Tree:

5. 间接互连网络 (Indirect Interconnects)

为了降低硬件成本，系统通过共享交换机和链路来提供间接连接。

5.1 总线与交叉开关 (Bus & Crossbar)

总线网络 (Bus Network)：通过共享导线传输数据，一次只能有一对设备进行通信，通常由总线仲裁器协调，适用于少量处理器。
交叉开关 (Crossbar Network)：一个 $n \times m$ 的交叉开关可以在输入和输出之间提供任意连接，状态分为直通或转向。硬件成本高（需要 $n \times m$ 个开关）。

5.2 多级交换网络 (Multistage Switching Network)

通过多个中间级交换机（通常使用 $2 \times 2$ 交叉开关）构建，目标是用较低的成本缩短输入和输出之间的距离。

Omega 网络：一个 $n \times n$ 的 Omega 网络有 $\log n$ 个阶段。每个阶段有 $n/2$ 个开关。stage i 控制了第(i + 1)个MSB是否要flip。

成本对比：连接 8 个处理器和 8 个内存节点，交叉开关需要 64 个开关，而使用 $2 \times 2$ 开关的 Omega 网络仅需 12 个开关。
Butterfly Network (蝴蝶网络)

在 Butterfly Network 中，每一阶段的选择代表了对目标地址二进制位中特定某一位的确定。

连接逻辑：节点 $(\alpha, i)$ 在第 $i$ 阶段会连接到下一阶段的两个节点：

直通边 (Straight edge)：连接到 $(\alpha, i+1)$ 。

交叉边 (Cross edge)：连接到 $(\alpha', i+1)$ ，其中 $\alpha'$ 与 $\alpha$ 的区别仅在于从左数第 $(i+1)$ 位不同。

选择的含义：在该网络中，第 $i$ 级的交换机选择实际上是在处理目标地址二进制表示中的第 $i+1$ 位。通过选择“直通”或“交叉”，路由路径能够逐步“修正”当前地址位，使其最终与目标地址完全匹配。

Baseline Network (基准网络)

Baseline Network 采用了一种递归的构造方式，其各阶段的选择涉及到对剩余地址位的循环移位和变换。

连接逻辑：节点 $(\alpha, i)$ 到下一阶段节点 $(\beta, i+1)$ 的连接遵循以下规则：

1. 第一种选择： $\beta$ 等于 $\alpha$ 最后 $(k-i)$ 位的循环右移（其中 $k$ 是总位数）。

2. 第二种选择：先将 $\alpha$ 的最低有效位 (LSBit) 取反，然后再对最后 $(k-i)$ 位进行循环右移 。

选择的含义：与蝴蝶网络类似，这里的“选择”（通过 $2\times2$ 交换机的直通或转向状态）代表了在当前拓扑约束下，为了将消息送往正确的目标端口而对地址位进行的排列组合。Baseline 网络的特点是其连接模式随阶段增加而逐渐收缩（最后 $k-i$ 位），每一级的选择都在缩小数据包最终落点的范围。

6. 路由算法 (Routing Algorithms)

路由算法负责确定消息从源节点到目标节点的路径。

分类：基于路径长度可分为最小路由（始终选择最短路径）与非最小路由；基于适应性可分为确定性路由（固定路径）与自适应路由（根据网络拥塞等状况动态调整）。

6.1 经典确定性路由示例

XY 路由 (适用于 2D Mesh)：消息先沿 X 轴方向移动直到 $X_{src}==X_{dst}$ ，然后再沿 Y 轴方向移动直到 $Y_{src}==Y_{dst}$ 。
E-Cube 路由 (适用于超立方体)：利用源地址和目标地址的二进制位表示，从最高有效位（MSB）到最低有效位（LSB）依次查找不同的位，每次将消息转发给该位已纠正的相邻节点，最多需要 $k$ 跳。
XOR-Tag 路由 (适用于 Omega 网络)：设定 $T$ = 源地址 XOR 目标地址。在第 k 级阶段，如果 $T$ 的第 k 位为 0，则走直通路径；如果为 1，则走交叉路径。

7. 行业现状与发展趋势 (Current Trends)

通信标准：在 TOP500 超级计算机榜单中，以太网（Ethernet）目前的性能份额已经主导并超越了 Infiniband（NVIDIA/Mellanox 专有标准）。
链路速度：以太网和 Infiniband 标准的单向链路速度已经向 800 Gb/s 甚至更高迈进。
高性能计算 (HPC) 拓扑：目前流行 Dragonfly（组内与组间都是全互连，直径低）和 Fat Tree（越靠近根节点带宽越高）拓扑。例如，新加坡国家超算中心的 ASPIRE 2A 采用了基于以太网的 HPE Cray Slingshot 10 互连架构。

第 10 部分：高能效计算 (Energy-efficient Computing)

1. 为什么我们需要关注高能效？

现代计算设施面临着巨大的能耗挑战，这不仅带来了高昂的成本，也对环境产生了深远影响：

宏观能耗趋势：人工智能和数据中心的快速发展导致耗电量飙升。例如，爱尔兰的数据中心消耗了全国超 21% 的计费电力。预计到 2028 年，美国数据中心的耗电量可能占全国总用电量的 12% 。目前，全球数据中心已消耗了超过 3% 的电力供应。
成本问题：运行高性能硬件非常昂贵。以一台运行现代 LLM 推理模型的机器（8张 B200 GPU）为例，其单日电费可能高达 57.6 美元。
散热问题 (Heat)：计算机消耗的电能几乎 100% 会转化为热能。一颗 300W 的处理器就会产生 300W 的热量，这要求极度复杂的散热技术（如液冷、浸没式冷却）来维持系统运行。

2. 核心物理概念：能量与功率

为了更好地理解能效，我们需要区分以下两个基本概念：

能量 (Energy, $E$ )：做功的能力，单位为焦耳 (Joules, J) 。计算机的每一步操作（如加法、乘法）都会消耗一定的能量（例如 32位浮点乘法约消耗 4.00 pJ）。
功率 (Power, $P$ )：单位时间内转移或消耗的能量，公式为 $E \div t$ ，单位为瓦特 (Watts) 或焦耳/秒。高功率处理器通常能提供更高的性能（每秒执行更多操作），但也会带来更大的能耗和热量。

3. 功耗墙 (The Power Wall) 与登纳德缩放定律

Dennard Scaling：由 Robert Dennard 在 1974 年提出。该理论指出，随着晶体管尺寸的缩小，单位面积上的功耗应保持不变。这意味着在不增加整体功耗的情况下，我们可以在同一面积内塞入更多晶体管，从而提升性能。
定律失效与功耗墙：大约在 2005 年左右，登纳德缩放定律走向终结。在极小的纳米尺度下，晶体管开始出现“漏电 (current leakage)”等电子物理现象。这导致更小的晶体管反而需要更高的单位面积功耗。
核心矛盾：我们无法在不增加功耗的前提下继续增加晶体管密度，但同时又受限于散热能力（热力学约束），无法无限制地增加处理器的总功耗。这就是所谓的“功耗墙”。

4. 单处理器能效 (Per-Processor Efficiency)

4.1 核心评估指标：每瓦性能 (Performance-per-watt)

公式：测试分数 (Score) ÷ 处理器功耗 (Power) 。
注意：所谓的“性能分数”高度依赖于所运行的特定基准测试（如线性代数测试 HPL、渲染测试 POV-Ray 等）。

4.2 影响处理器功耗的因素

现代处理器的功耗主要由动态功耗和静态功耗组成，可以用简化公式表示： $P_{total} = P_{dynamic} + P_{static}$ 。其中，动态功耗的公式为： $P_{dynamic} = k \times V^2 \times f$ 。

$V$ (电压)：电压对功耗的影响最为显著（呈平方关系 $V^2$ ）。
$f$ (频率)：频率对功耗有线性影响，但提高频率是获得性能增益的主要方式。（频率也会影响电压的最小值，现代处理器电压会随着频率改变）
边际收益递减：虽然提高时钟频率能提升性能，但这通常要求超线性地提高电压（以保证处理器稳定运行），从而导致功耗呈指数级剧增。因此，性能的提升与功耗的增加并不是线性的。

4.3 提升处理器能效的技术

动态电压与频率调节 (DVFS)：现代处理器能够根据当前任务的负载情况，动态地降低（或升高）时钟频率和电压。例如在系统空闲或运行简单后台任务时，降低电压和频率以减少能耗和发热。
异构核心架构 (Heterogeneous Cores)：与其依赖单一类型的核心，不如将不同特性的核心混合使用。
- 原理：某些核心在高频下性能极佳但极其耗电，而另一些核心在低频下效率极高。
- 案例：ARM 的 big.LITTLE 架构（高性能 A15 核心 + 高能效 A7 核心）；Intel 的 P-core（性能核）与 E-core（能效核）；以及苹果 M4 处理器的异构设计（10个性能核 + 4个能效核）。

5. 数据中心与超算能效 (Datacenter / HPC Efficiency)

将计算资源集中在数据中心有利于统一管理电源（UPS）、散热（集中冷却）以及实现高速的网络互联。但数据中心每年消耗超 460 TWh 的电力，占全球碳排放的重要部分。

5.1 数据中心能效指标

Green500 (每瓦 GFLOPs)：衡量超算集群单纯在计算上的能效表现。近年来，集成加速器（如 NVIDIA Grace Hopper GH200 或 AMD MI300A）极大地推动了这一指标的突破。GH200 通过提供高达 900 GB/s 的高带宽 CPU-GPU 互联（取代了传统的 PCIe 瓶颈），在数据传输上节省了 5 倍的功耗。
PUE (电源使用效率, Power Usage Effectiveness)：衡量数据中心整体基础设施的能效。
- 公式： $PUE = \frac{\text{数据中心总能耗}}{\text{IT 设备总能耗}}$ 。
- 解读：PUE 越接近 1，说明越多的电力被真正用于计算（IT设备），而非浪费在散热、照明等辅助设施上。
- 局限性：PUE 存在一定缺陷。例如，炎热地区的 PUE 天生吃亏（如新加坡的 Google 数据中心 PUE 相对较高）。此外，由于公式的数学性质，数据中心如果单纯增加 IT 设备的绝对耗电量，即使总能耗上升，PUE 的数值反而可能会“改善”，这会导致错误的激励导向。

5.2 数据中心散热技术 (Cooling Techniques)

冷热通道隔离 (Hot/Cold Aisle Containment)：将服务器机架面对面或背对背排列。冷空气从一侧进入（冷通道），带走热量后从另一侧排出（热通道）。通过物理隔离将热通道封闭，可以更高效地收集并冷却热空气，防止冷热空气混合，大幅提升冷却效率。
温水冷却 (Warm-Water Cooling)：传统的空气冷却效率较低。新加坡国家超级计算中心 (NSCC) 使用了温水液冷技术——直接将 40°C 的温水送入节点冷却 CPU 和 GPU（回水温度约为 45°C）。即使水温在 40°C 左右，也足以有效压制 60-80°C 的计算节点，且冷却温水所需的能量远低于制造冷水。

PYP notes

the degree of a node in CCC is always constant 3
Cloud computing is a data center with layer of software over it. The cloud can offer services at different levels (platform, software, infrastructure), while the data centers offer the infrastructure service only. Cloud services are pay-per-use model, while data centers are a huge investment in the beginning.
atomic operations are faster than mutex operations (locks)
Performance metrics:

investigate the time spent waiting; the only waiting happens for lock contention
check IPC – if low, it is likely that the atomic instructions are contended
check cache misses or page faults
check the call stack using perf

This is a classic false-sharing situation. Assuming the threads iterate through the array at equal rates (that is, they are on the same loop iteration at about the same time), both threads will be writing to elements on the same cache line at about the same time. The cache line will bounce back and forth between the caches of the two processors. In the worst case, every write is a miss.
Metrics, such as utilization of the processes, resource utilization, idle time, etc, were accepted. Speedup was not accepted as a metric
MergeSort用MPI优化只能是master-worker，没法做到fork and join

Point B:

int row_per_rank = Nx / size;
int rows = row_per_rank + 2;

Point C: blank

Point D:

calls to MPI_Send and MPI_Recv between yourself (rank) and neighbours (rank - 1, rank + 1)
Sends: temp[1] and temp[rows - 2] (the rows you computed)
Receives: temp[0] and temp [rows - 1]  (the rows received become the new boundary rows)

Point A:

start_i = 1;     // skip top row
end_i  = rows - 1;  // skip bottom row
// include all columns (except boundaries)
start_j = 1; 
end_j  = Ny - 1;

Point E: Gather everything back into one big global grid (call to MPI_Gather)

MPI_Gather(&temp[Ny], rows_per_rank * Ny, MPI_DOUBLE, final_grid, rows_per_rank * Ny, MPI_DOUBLE, 0, MPI_COMM_WORLD);

CS3210 Parallel Computing Note

CS3210 Parallel Computing Note

第 1 部分：导论与并行计算基础 (Introduction to Parallel Computing)

1. 为什么我们需要并行计算？

2. 并行化问题的核心步骤

3. 不同层级的硬件并行架构

第 2 部分：进程、线程与同步 (Processes, Threads & Synchronization)

1. 进程 (Processes)

2. 线程 (Threads)

3. 互斥与同步机制 (Synchronization)

5. Parallelization带来的问题

4. 经典同步问题

第 3 部分：硬件架构与内存组织 (Architecture & Memory Organization)

一、 处理器的并行化演进

1. 单核并行性 (Single-Core Level)

二、Flynn 的体系结构分类法

三、 内存组织 (Memory Organization)

1. 缓存系统 (Cache System)

2. 并行计算机内存架构

第 4 部分：并行编程模型与 Foster 方法学 (Programming Models)

1. 数据并行 vs 任务并行

2. 任务依赖图 (Task Dependence Graph)

3. Models of coordination

2. Foster's methodology

3. 常见并行设计模式

第 5 部分：并行系统性能分析 (Performance of Parallel Systems)

1. 核心性能指标

2. Amdahl 定律 vs Gustafson 定律的较量

3. 性能建模与内存瓶颈

CPU time

memory models

throughput metrics

4. takeaways

第 6 部分：Cache Coherence & Consistency)

1. 核心问题：共享内存真的那么简单吗？

2. Cache Coherence

2. 内存一致性模型 (Memory Consistency)

第 7 部分：GPU 架构与 CUDA 编程 (GPU Programming & Architecture)

1. GPU 架构原理 (以 Hopper 架构为例)

2. CUDA 编程与内存层次模型

3. SIMT 执行模型与性能优化陷阱

4. 优化 CUDA 的核心准则

第 8 部分：消息传递与 MPI

1. 引入与动机 (Introduction & Motivation)

2. MPI 基础概念 (MPI Basics)

3. 点对点通信 (Point-to-Point Communication)

3.1 消息的组成 (Message Format)

3.2 通信语义分类 (Communication Semantics)

3.3 死锁与消息顺序 (Deadlocks & Ordering)

4. 进程组与通信子 (Process Groups and Communicators)

5. 集合通信 (Collective Communication)

第 9 部分：互连网络与数据分布 (Interconnection Networks and Data Distribution)

1. 引言与背景

2. 数据分布 (Data Distribution)

2.1 一维数组的数据分布

2.2 二维数组的数据分布

2.3 边界通信与权衡

3. 互连网络基础 (Interconnection Networks)

4. 直接互连网络 (Direct Interconnects)

4.1 关键网络指标 (Key Metrics)

4.2 常见拓扑结构

5. 间接互连网络 (Indirect Interconnects)

5.1 总线与交叉开关 (Bus & Crossbar)

5.2 多级交换网络 (Multistage Switching Network)

6. 路由算法 (Routing Algorithms)

6.1 经典确定性路由示例

7. 行业现状与发展趋势 (Current Trends)

第 10 部分：高能效计算 (Energy-efficient Computing)

1. 为什么我们需要关注高能效？

2. 核心物理概念：能量与功率

3. 功耗墙 (The Power Wall) 与 登纳德缩放定律

4. 单处理器能效 (Per-Processor Efficiency)

4.1 核心评估指标：每瓦性能 (Performance-per-watt)

4.2 影响处理器功耗的因素

4.3 提升处理器能效的技术

5. 数据中心与超算能效 (Datacenter / HPC Efficiency)

5.1 数据中心能效指标

5.2 数据中心散热技术 (Cooling Techniques)

PYP notes

Comments

一、处理器的并行化演进

三、内存组织 (Memory Organization)

3. 功耗墙 (The Power Wall) 与登纳德缩放定律