Skip to content
Gains Summary
Main Navigation 首页 / Home
C++ 编程 / C++ Programming
系统与高性能 / Systems & Performance
Web 开发 / Web Development
人工智能 / Artificial Intelligence
工业软件 / Industrial Software
其他内容 / Other Topics
C++ 编程 / C++系统与性能 / SystemsWeb 开发 / Web人工智能 / AI工业软件 / Industrial

外观

Sidebar Navigation

← 系统与高性能 / Systems & Performance

计算系统 / Computing Systems

1. 计算系统：计算机如何执行与加速程序

2. 从 C++ 源码到 CPU 执行

3. CPU 流水线、乱序执行与分支预测

4. Cache、一致性、伪共享与 NUMA

5. GPU、SM、Warp 与显存

6. 计算执行模型：程序怎样映射到机器

7. SIMD 与编译器向量化

8. C++ 多线程与 OpenMP

9. CUDA 平台与编程模型

10. CUDA Kernel、内存与性能

11. CPU-GPU 异构流水线

12. MPI 与分布式并行

13. 并行算法模式

14. 性能模型与工具

15. 递进学习项目：从单线程到集群

历史完整正文 / Original Deep Dives

1. 历史完整正文：统一前文章逐篇保留

原体系结构与硬件 / Original Architecture

1. 硬件编程与高性能计算：一张可走通的学习地图 / A Practical Learning Map for Hardware Programming and HPC

2. 计算机体系结构：CPU、内存与 GPU / Computer Architecture: CPUs, Memory, and GPUs

3. 计算机架构基础——为什么 GPU 比 CPU 更快 / Computer Architecture Fundamentals: Why GPUs Outperform CPUs

4. 并行计算理论——30 天训练能优化到多快？ / Parallel Computing Theory and the Limits of Training Acceleration

5. GPU 架构深入——上万个核心如何分工协作 / GPU Architecture and Massive Parallel Execution

6. CUDA 编程模型——把矩阵乘法映射到 GPU / The CUDA Programming Model for Mapping Matrix Multiplication to GPUs

7. CUDA 内存管理——百亿参数如何装进显存 / CUDA Memory Management for Large Models

8. CUDA 性能优化——从 30 天缩短到 10 天 / CUDA Performance Optimization

9. CPU 并行编程——OpenMP 与 SIMD 向量化 / CPU Parallel Programming with OpenMP and SIMD

10. HPC 集群与 MPI——多节点分布式训练 / HPC Clusters and MPI for Distributed Training

11. 异构计算——CPU 与 GPU 如何协同工作 / Heterogeneous Computing with CPUs and GPUs

12. 深度学习训练优化实战——从 30 天到 3 天 / Deep Learning Training Optimization from Thirty Days to Three

13. 性能分析工具——找到真正的瓶颈 / Performance Analysis Tools for Finding Real Bottlenecks

14. NPU 全景——昇腾/寒武纪/TPU/苹果生态 / The NPU Landscape: Ascend, Cambricon, TPU, and Apple

15. 未来趋势——2030 年的计算机会是什么形态 / Future Computing Trends Toward 2030

16. 硬件与高性能计算：从“程序为什么慢”开始 / Hardware and HPC Starting from Why Programs Are Slow

原并行计算 / Original Parallel Computing

1. 并行计算：从 SIMD 到 MPI / Parallel Computing from SIMD to MPI

2. 并行计算全景：从晶体管、CPU、GPU 到计算集群 / Parallel Computing from Transistors, CPUs, and GPUs to Clusters

3. 并行计算基础：任务分解、加速比与可扩展性 / Parallel Computing Fundamentals: Decomposition, Speedup, and Scalability

4. 处理器体系结构：从指令流水线到多核芯片 / Processor Architecture from Instruction Pipelines to Multicore Chips

5. CPU 并行：多线程、SIMD、Cache 一致性与 NUMA / CPU Parallelism with Threads, SIMD, Cache Coherence, and NUMA

6. 内存层次：Cache、带宽、局部性与一致性 / Memory Hierarchies, Bandwidth, Locality, and Coherence

7. GPU 体系结构：SIMT、Warp、SM 与吞吐优先设计 / GPU Architecture with SIMT, Warps, and Streaming Multiprocessors

8. CUDA 编程模型：Thread、Block、Grid 与内存协作 / CUDA Threads, Blocks, Grids, and Cooperative Memory Access

9. 并行算法模式：Map、Reduce、Scan、Stencil 与任务图 / Parallel Patterns: Map, Reduce, Scan, Stencil, and Task Graphs

10. 异构计算：CPU、GPU、NPU 如何协同工作 / Heterogeneous Computing with CPUs, GPUs, and NPUs

11. 分布式并行：MPI、集合通信、RDMA 与多机多卡 / Distributed Parallelism with MPI, Collective Communication, and RDMA

12. 性能工程：测量、Roofline、瓶颈定位与优化闭环 / Performance Engineering with Measurement, Roofline, and Bottleneck Analysis

13. 并行计算实战：AI、CAE、图像与科学计算 / Parallel Computing for AI, CAE, Imaging, and Scientific Computing

14. 并行计算实践路线：从单核优化到多机多卡 / A Parallel Computing Project Path from Single-Core to Multi-Node GPUs

本页目录

并行计算基础：任务分解、加速比与可扩展性 / Parallel Computing Fundamentals: Decomposition, Speedup, and Scalability ​

📅 创建时间：2026-07-20 🏷️ 标签：#并行计算 #Amdahl定律 #Gustafson定律 #性能模型 📚 前置知识：[[00-parallel-computing-overview]] 📚 相关知识：[[/02-systems-and-performance/02-computer-architecture-and-hardware/02-parallel-computing-theory]]

1. 并行之前先判断“能否拆分” ​

假设程序由以下步骤组成：

text
读取数据 → 预处理 → 核心计算 → 汇总结果 → 写入文件
1

只有相互独立的部分能够同时执行。任务之间常见依赖包括：

  • 数据依赖：后一步需要前一步的结果
  • 控制依赖：是否执行由前一步判断决定
  • 资源依赖：多个任务竞争同一文件、锁或设备

数据并行与任务并行 ​

text
数据并行：同一种操作处理不同数据
例：多个线程分别处理图像的不同行

任务并行：不同任务同时处理同一流程的不同阶段
例：一个线程读取、一个线程解码、一个线程推理
1
2
3
4
5

GPU 主要擅长数据并行，CPU 更容易同时承载数据并行和任务并行。

2. 衡量并行性能 ​

加速比 ​

text
S(p) = T(1) / T(p)
1

如果单线程需要 100 秒，8 线程需要 20 秒，则加速比为 5，而不是 8。

并行效率 ​

text
E(p) = S(p) / p
1

上例的并行效率是 5 / 8 = 62.5%。剩余能力消耗在串行部分、同步、调度和负载不均上。

吞吐与延迟 ​

  • 延迟：完成单个任务需要多久
  • 吞吐：单位时间能完成多少任务

GPU 往往提高吞吐，但单个小任务不一定比 CPU 延迟更低。

3. Amdahl 定律：固定问题规模的上限 ​

如果程序中可并行比例为 P，使用 N 个处理器：

text
S(N) = 1 / ((1 - P) + P / N)
1

当 95% 可以并行时，即使处理器无限多：

text
最大加速比 = 1 / (1 - 0.95) = 20
1

这说明优化串行路径可能比继续增加核心更重要。

可并行比例理论最大加速比
50%2 倍
90%10 倍
95%20 倍
99%100 倍

4. Gustafson 定律：问题规模也会增长 ​

现实中获得更多计算资源后，通常不是只想更快完成原问题，而是希望处理更大的网格、更高分辨率或更大的模型。

text
S(N) = N - α(N - 1)
1

其中 α 是串行部分比例。Gustafson 定律解释了为什么超级计算机仍然有价值：资源增加后，可以扩大并行工作规模。

5. 强扩展与弱扩展 ​

强扩展 ​

保持总问题规模不变，增加处理器数量。

text
固定 1 亿个网格单元：1 核 → 8 核 → 64 核
1

处理器越多，每个处理器分到的工作越少，通信占比最终会上升。

弱扩展 ​

每个处理器的工作量保持不变，处理器增加时同步扩大问题规模。

text
每核处理 100 万个网格单元：1 核 100 万 → 64 核 6400 万
1

弱扩展更能反映大型科学计算系统的容量能力。

6. 粒度、调度与负载均衡 ​

并行粒度 ​

  • 粗粒度：任务大、调度少，但可能不均衡
  • 细粒度：任务均衡机会多，但调度和同步成本高

任务耗时只有几百纳秒时，放进线程池可能比直接执行更慢。

静态调度与动态调度 ​

  • 静态调度：提前分工，开销低，适合任务耗时相近
  • 动态调度：运行时领取任务，均衡好，但有额外竞争

负载不均衡 ​

text
线程 A：100 ms
线程 B：102 ms
线程 C：98 ms
线程 D：300 ms  ← 所有人都要等它
1
2
3
4

并行阶段耗时由最慢参与者决定。

7. 同步不是免费的 ​

互斥锁、原子操作、Barrier 和消息通信都会带来等待。常见优化方向：

  • 减少共享可变状态
  • 批量处理，降低同步频率
  • 使用线程局部数据，最后统一归并
  • 让通信与计算重叠
  • 通过无锁结构降低阻塞，但不要默认无锁一定更快

历史并行基础补充 ​

本页保留合并前的并行理论入门。

当前版本增加 DAG、Work/Span、正确性和实验方法。

DAG ​

任务是节点，依赖是边。

Ready Task 的前置依赖已经完成。

Work ​

Work 是全部任务成本。

减少 Work 通常是算法优化。

Span ​

Span 是最长依赖路径。

更多资源不能短于 Span。

并行度 ​

text
parallelism = Work / Span
1

它给出可利用并行度的粗略上限。

真实依赖 ​

由算法读写关系决定。

不能通过忽略同步消除。

伪依赖 ​

由共享容器、全局锁和实现顺序造成。

分片和线程局部状态可以减少。

粒度 ​

细任务调度多。

粗任务并行度低且尾部大。

静态调度 ​

规则任务使用固定分块。

行为可预测，开销小。

动态调度 ​

不规则任务使用队列。

Chunk 在开销和均衡之间选择。

Work Stealing ​

空闲 Worker 从其他队列窃取。

改善不均，增加调度与局部性成本。

串行区 ​

初始化、I/O、提交、锁和归约可能串行。

通信 ​

通信含延迟、字节、协议、拥塞和同步。

同步范围 ​

线程、Block、进程和节点具有不同范围。

范围越大，协调成本通常越高。

数据竞争 ​

共享写缺少同步导致错误。

死锁 ​

循环等待造成无进展。

统一顺序和结构化协议降低风险。

活锁 ​

线程持续重试但没有完成工作。

饥饿 ​

任务长期无法获得资源。

调度公平性需要设计。

浮点 ​

并行归约改变舍入顺序。

使用容差或确定性树。

Amdahl ​

固定规模的串行比例限制加速。

Gustafson ​

资源增加时可以扩大问题规模。

强扩展 ​

固定总工作，观察效率。

弱扩展 ​

固定每资源工作，观察全局成本。

基线 ​

串行版本必须正确且合理。

Profile ​

分解计算、移动、同步、等待、I/O 和不均衡。

正确性 ​

  • 结果；
  • 容差；
  • 数据竞争；
  • 内存安全；
  • 取消；
  • 资源释放。

实验记录 ​

  • 输入；
  • 算法；
  • 硬件；
  • 编译器；
  • 资源数；
  • 调度；
  • 样本；
  • 原始数据；
  • 正确性。

历史边界 ​

旧线程和节点结论不能直接外推。

当前平台重新建立基线。

当前课程映射 ​

当前版本增加：

  • DAG；
  • Work/Span；
  • 调度；
  • 正确性；
  • 强弱扩展；
  • Profile；
  • 完成标准。

章节测试 ​

  1. 为什么 16 核程序通常无法获得 16 倍加速？
  2. 图像逐像素处理更接近数据并行还是任务并行？
  3. 固定网格规模增加节点属于强扩展还是弱扩展？
  4. 为什么任务拆得过细也会降低性能？

参考答案 ​

  1. 存在串行部分、同步、调度、访存和负载不均。
  2. 数据并行。
  3. 强扩展。
  4. 调度、通信和同步成本可能超过任务本身。

下一篇：[[02-processor-architecture]]

最后更新于:

Pager
上一篇2. 并行计算全景：从晶体管、CPU、GPU 到计算集群 / Parallel Computing from Transistors, CPUs, and GPUs to Clusters
下一篇4. 处理器体系结构：从指令流水线到多核芯片 / Processor Architecture from Instruction Pipelines to Multicore Chips

持续记录，持续成长

Copyright © Tidenflow