Quartz 4

并行计算基础理论

21 min read

CMU15418：

https://www.zhihu.com/column/c_1515272289578479616

https://djdongjin.github.io/15418-parallel-computing

https://doraemonzzz.com/categories/

并行的笔记：https://www.zhihu.com/people/zero-35-40/posts

cs 249 课程：https://zhuanlan.zhihu.com/p/710906705

https://zhuanlan.zhihu.com/p/7554656902

美国 hpc 教程：https://hpc-tutorials.llnl.gov/ https://hpc.llnl.gov/documentation/tutorials/introduction-parallel-computing-tutorial

并行计算基础

1 . 什么是并行计算

并行计算是一种通过将任务分解为多个子任务并同时在多个处理器或计算节点上执行的计算方式。它的主要目标是提高计算速度和效率，解决那些单一处理器难以快速处理的大规模问题。简而言之就是充分动用服务器硬件资源，将很大计算量的问题分解给不同的核心完成一部分，最终所有核心协作完成所有任务，以起到加速程序运行的效果。

  • 并行计算的核心内容：计算任务分解、内存访问模型、并行单元间的通信。

2 . 并行计算的基本概念

进程与线程

进程和线程是操作系统中管理程序执行的两个核心概念，二者的区别主要体现在资源管理、执行方式、开销等多个方面，具体如下：

  • 进程
    • 每个进程有自己独立的地址空间
    • CPU 在进程之间切换需要进行上下文切换
  • 线程
    • 一个进程下的线程共享地址空间
    • CPU 在线程之间切换开销较小
  • 超线程 (hyper-threading) 将单个 CPU 物理核心抽象为多个（目前通常为 2 个）逻辑核心，共享物理核心的计算资源

1. 定义与本质

  • 进程：是操作系统进行资源分配（如内存、文件描述符、CPU 时间片等）的基本单位，可以理解为一个 “正在运行的程序”。每个进程对应一个独立的地址空间，包含程序代码、数据、栈、堆等资源。
  • 线程：是进程内的执行单元，也是操作系统进行调度（CPU 执行的基本单位）。一个进程可以包含多个线程，这些线程共享进程的资源（如内存空间、文件句柄等），但拥有独立的栈和寄存器。

2. 资源占用

  • 进程：资源独立且占用多。每个进程有自己独立的地址空间、内存、文件描述符等，不同进程的资源不共享（除非通过特殊机制，如共享内存）。
  • 线程：资源共享且占用少。线程共享所属进程的全部资源（如代码段、数据段、堆等），仅拥有独立的栈（用于函数调用和局部变量）和寄存器（用于保存执行状态），因此内存占用远小于进程。

3. 切换开销

  • 进程切换：开销大。进程切换时，操作系统需要保存当前进程的所有资源状态（如内存映射、文件句柄、寄存器等），并加载新进程的状态，涉及大量数据交换，耗时较长。
  • 线程切换：开销小。线程共享进程资源，切换时只需保存和恢复线程的独立状态（栈、寄存器），无需处理资源的重新分配，因此切换速度远快于进程。

4. 通信方式

  • 进程间通信（IPC）：复杂且受限。由于进程资源独立，通信需通过操作系统提供的特殊机制，如管道、消息队列、共享内存、信号量、Socket 等，实现成本高。
  • 线程间通信：简单直接。线程共享进程的内存空间，可通过全局变量、静态变量等直接交换数据，但需通过锁（如互斥锁、条件变量）等同步机制避免 “资源竞争”。

5. 独立性与稳定性

  • 进程：独立性强。一个进程崩溃（如内存错误）通常不会影响其他进程，因为资源隔离。
  • 线程：依赖性强。线程是进程的一部分，若一个线程崩溃（如访问非法内存），可能导致整个进程崩溃（因为共享资源被破坏）。

6. 创建与销毁开销

  • 进程：创建 / 销毁开销大。需要分配独立的地址空间、初始化资源等，耗时较长。
  • 线程：创建 / 销毁开销小。只需初始化独立的栈和寄存器，无需分配新资源，因此更轻量。

总结

  • 进程是 “资源容器”，负责资源分配，独立性强但开销大；
  • 线程是 “执行单元”，共享进程资源，开销小但依赖进程存在。

实际应用中，多进程适合隔离性要求高的场景（如浏览器的每个标签页），多线程适合任务协作紧密、资源共享频繁的场景（如服务器处理并发请求）。

并行性与并发性

  • 并行性（Parallelism）：并行性指的是多个任务在同一时间同时执行。并行性通常依赖于多核或多处理器系统，在物理上允许多个任务在不同的处理器或计算核心上并行运行。
    • 关键点：实际同时执行多个任务。
    • 硬件要求：需要多核处理器或多个处理器。
    • 示例：边洗澡边听歌
  • 并发性（Concurrency）：并发性指的是多个任务在系统中交替进行，但这些任务并不一定同时运行。并发性侧重于任务之间的逻辑交替，而非物理上的同时运行。操作系统通过任务调度器快速切换任务，使它们看起来好像是同时运行的，虽然它们实际上在不同的时间片被执行。
    • 关键点：多个任务在逻辑上交替进行，但不一定是同时执行的。
    • 硬件要求：单核处理器也能支持并发，因为并发主要依赖于操作系统的任务调度机制。
    • 示例：边玩手机边看电视

任务划分

负载均衡：确保任务均匀地分配到所有处理器或核心，避免某些处理器过载而其他处理器闲置。

任务粒度：选择适当的任务粒度，以平衡任务的管理开销和计算效率。粒度过细可能导致管理开销过高，粒度过粗可能导致负载不均。

通信开销：尽量减少处理器之间的数据交换，优化数据局部性，以降低通信开销。

同步开销：减少不同任务之间的同步需求，避免不必要的等待和阻塞。

可扩展性：确保任务划分策略能够适应处理器数量的增加，保持系统性能的可扩展性。

并行架构（共享内存与分布式内存）

共享内存架构（对应 OpenMP）：所有处理器共享同一块物理内存。处理器可以直接访问和修改共享的数据。数据共享和同步机制较为直接，不需要显式通信操作。

分布式内存架构（对应 MPI）：每个处理器或计算节点有独立的内存空间。处理器之间通过消息传递进行数据交换。数据交换和通信需要显式管理。

内存访问模式

在多处理器系统架构中，内存访问模式对性能有着至关重要的影响。UMA（统一内存访问）和 NUMA（非一致内存访问）是两种主要的内存架构设计，下面将详细介绍它们的特点、优缺点及适用场景。

一、统一内存访问（UMA）

1. 核心概念

  • 共享单一内存池：所有处理器访问同一个物理内存地址空间，内存被视为统一资源。
  • 均等访问延迟：每个处理器访问任何内存位置的延迟基本相同（忽略缓存效应）。
  • 总线架构：处理器通过共享总线（如前端总线）连接到内存控制器。

2. 架构示意图

         ┌───────────┐
         │  共享内存   │
         └─────┬─────┘
               │
      ┌────────┼────────┐
      │        │        │
┌─────┴───┐ ┌───┴─────┐ ┌───┴─────┐
│ 处理器1  │ │ 处理器2  │ │ 处理器N  │
└─────────┘ └─────────┘ └─────────┘

3. 典型实现

  • 对称多处理（SMP）系统：如早期的 Intel Xeon MP 服务器，多个处理器共享内存和 I/O 系统。
  • 缓存一致性协议：通过 MESI 等协议保证各处理器缓存的一致性。

4. 优缺点

  • 优点：
    • 编程模型简单：无需关心内存位置，代码可移植性高。
    • 数据共享高效：内存访问透明，适合频繁数据交换的场景。
  • 缺点：
    • 扩展性瓶颈：总线带宽成为瓶颈，处理器数量增加时性能下降。
    • 内存争用：多处理器同时访问同一内存区域时会产生竞争。

二、非一致内存访问（NUMA）

1. 核心概念

  • 分布式内存架构：内存被划分为多个 “节点”（Node），每个节点附属于特定处理器。
  • 访问延迟差异：处理器访问本地内存（所属节点）更快，访问远程内存（其他节点）延迟较高。
  • 互联网络：处理器与内存节点通过高速互联网络（如 QPI、HyperTransport）连接。

2. 架构示意图

节点0                节点1                节点N
┌───────────┐      ┌───────────┐      ┌───────────┐
│ 处理器0    │      │ 处理器1    │      │ 处理器N    │
│ 本地内存0  │      │ 本地内存1  │      │ 本地内存N  │
└─────┬─────┘      └─────┬─────┘      └─────┬─────┘
      │                   │                   │
      └────────┬───────────┬───────────┬───────┘
               │           │           │
            ┌───────────────────────┐
            │    高速互联网络        │
            └───────────────────────┘

3. 典型实现

  • 现代服务器系统：如 AMD EPYC、Intel Xeon Scalable 系列，支持多插槽 NUMA 架构。
  • 操作系统支持：Linux 通过 numactl 工具、Windows 通过内存节点 API 管理 NUMA。

4. 内存访问机制

  • 本地优先：处理器优先访问本地内存，提升性能。
  • 远程访问：当访问其他节点内存时，数据需通过互联网络传输，延迟显著增加（通常 2-3 倍）。

5. 优缺点

  • 优点：
    • 高扩展性：支持更多处理器和更大内存容量（突破总线带宽限制）。
    • 局部性优化：将数据和计算放在同一节点，减少远程访问。
  • 缺点：
    • 编程复杂度高：需手动管理数据放置（如通过 numactl 或 OpenMP 的 proc_bind）。
    • 内存碎片问题：跨节点内存分配可能导致碎片，影响性能。

三、UMA Vs NUMA：关键对比

特性UMANUMA
内存访问延迟一致（所有处理器相同）不一致（本地快，远程慢）
扩展性受总线限制，适合少量处理器支持大量处理器（数十至数百核）
编程模型简单（无需关心内存位置）复杂（需优化数据放置）
典型应用场景中小规模服务器、桌面系统大规模数据中心、高性能计算（HPC）
代表硬件双核 / 四核桌面 CPU、早期服务器AMD EPYC、Intel Xeon Scalable

四、适用场景与优化建议

1. UMA 适用场景

  • 处理器数量较少（≤8 核）。
  • 应用对内存访问延迟敏感且数据共享频繁（如数据库事务处理）。
  • 代码未针对 NUMA 优化，需保持兼容性。

2. NUMA 适用场景

  • 大规模并行计算（如科学模拟、AI 训练）。
  • 内存密集型应用（如内存数据库 Redis、分布式缓存）。
  • 多插槽服务器（如 2P/4P 服务器）。

3. NUMA 优化技巧

  • 数据本地化：将数据和处理它的线程放在同一节点。

    # Linux示例：绑定进程到特定NUMA节点
numactl --cpunodebind=0 --membind=0 ./application

  • 内存预分配：提前在本地节点分配内存。

  • 线程亲和性：使用 pthread_setaffinity_np 固定线程到特定 CPU。

  • 避免跨节点锁竞争：减少不同节点线程对共享资源的争用。

五、总结

  • UMA 以简单性和一致性为核心，适合小规模、延迟敏感的应用。
  • NUMA 通过分布式设计突破扩展性瓶颈，但需更复杂的优化策略。

现代服务器架构普遍采用 NUMA 设计，开发者需根据应用特性选择合适的内存访问模式，并通过系统工具和编程技巧充分发挥其性能潜力。

并行计算

要系统性地掌握并行计算（Parallel Computing），需要构建一个横跨硬件、操作系统、编程语言、算法设计和应用领域的多层知识体系。并行计算不是单一技术，而是一个完整的计算范式。

下面为你梳理一个清晰、结构化的并行计算知识系统，适合从入门到进阶的学习路径。

🌐 一、并行计算知识体系总览

+---------------------+
|   应用领域           |  ← 机器学习、科学计算、大数据、图形渲染
+---------------------+
|   并行算法与模型     |  ← MapReduce, BSP, Dataflow, Task Parallelism
+---------------------+
|   编程模型与框架     |  ← MPI, OpenMP, CUDA, Spark, TBB
+---------------------+
|   操作系统与运行时   |  ← 进程/线程调度、内存管理、同步原语
+---------------------+
|   计算架构与硬件     |  ← CPU多核、GPU、TPU、分布式集群
+---------------------+
|   数学与理论基础     |  ← 并行复杂度、Amdahl定律、负载均衡理论
+---------------------+

二、核心知识模块详解

1. 数学与理论基础（底层支撑）

主题重要性内容
并行计算模型⭐⭐⭐PRAM（并行随机存取机）、BSP（块同步并行）、Dataflow 模型
加速比理论⭐⭐⭐Amdahl 定律、Gustafson 定律：
Speedup = 1 / (S + P/N)
理解并行瓶颈
复杂度分析⭐⭐并行时间复杂度、通信开销、可扩展性分析
负载均衡⭐⭐静态 vs 动态分配、任务窃取（Work-Stealing）

✅ 掌握这些理论，才能判断“并行是否值得”、“能加速多少”。

2. 计算架构与硬件（物理基础）

架构类型特点典型代表
共享内存系统多核 CPU，共享主存多核服务器、NUMA 架构
分布式内存系统多节点，通过网络通信集群、HPC 超算
SIMD/SIMT 架构单指令多数据/线程GPU（CUDA, OpenCL）
异构计算CPU + GPU/TPU/FPGA 协同深度学习训练平台

关键概念：

  • NUMA（非统一内存访问）：内存访问延迟不一致
  • 缓存一致性（Cache Coherence）：MESI 协议
  • 互联网络：InfiniBand、RoCE、NVLink

✅ 理解硬件是优化性能的前提。

3. 操作系统与运行时系统（资源管理者）

主题内容
进程与线程管理创建、调度、上下文切换
内存管理虚拟内存、共享内存、mmap
同步原语互斥锁、条件变量、信号量、原子操作
IPC 机制管道、消息队列、套接字、共享内存
调度器CFS、实时调度、负载均衡

✅ 并行程序的性能瓶颈常在 OS 层（如锁竞争、上下文切换）。

4. 编程模型与框架（核心工具）

模型适用场景主要工具
共享内存并行多核 CPUpthread, OpenMP, C++ std::thread, TBB
分布式内存并行集群MPI（Message Passing Interface）
GPU 并行计算高吞吐数据并行CUDA, OpenCL, HIP
大数据并行批处理/流处理Apache Spark, Flink
任务并行异构任务调度Cilk, Go routines, Ray

5. 并行算法与设计模式（思维方法）

模式说明示例
数据并行（Data Parallelism）相同操作作用于不同数据图像处理、矩阵运算
任务并行（Task Parallelism）不同任务并行执行Web 服务器处理多个请求
流水线（Pipeline）任务分阶段，流水执行编译器、视频编码
分治并行（Divide and Conquer）递归分解任务并行快速排序、归并排序
MapReduce映射 → 归约大数据统计、词频统计
Work-Stealing空闲线程“偷”任务TBB、Go 调度器

✅ 掌握这些模式，才能设计高效的并行算法。

6. 性能分析与优化（实战能力）

工具用途
gprof, perfCPU 性能剖析
Valgrind (Callgrind, Helgrind)内存泄漏、数据竞争检测
nvprof, NVIDIA NsightGPU 性能分析
Intel VTune深度性能调优
MPI_PcontrolMPI 通信分析

优化方向：

  • 减少通信开销
  • 避免负载不均
  • 提高数据局部性（缓存友好）
  • 减少同步等待
  • 利用向量化（SIMD）

7. 应用领域（落地场景）

领域并行技术
科学计算气象模拟、流体力学 → MPI + OpenMP
机器学习深度学习训练 → CUDA + 分布式 SGD
大数据处理日志分析、推荐系统 → Spark/Flink
图形与游戏渲染、物理引擎 → GPU 并行
金融计算风险模拟、期权定价 → Monte Carlo + GPU
生物信息基因序列比对 → 分布式 BLAST

✅ 选择一个领域深入，能更快看到并行计算的价值。

Graph View

Backlinks