并行计算基础

CMU 15-418

UCB CS267

编译优化基础

编译器以正确性为第一标准，不以性能为第一要务

优化方式

Copy Propagation (拷贝传递)

x = y;
z = 1 + x;
// ||
//\||/
// \/
x = y;
z = 1 + y;
// 没有数据依赖，增加指令集并行的机会

S1: A=1.0;
S2: B=A+3.14;
S3: A=1/3*(C-D);
S4: A=(B*3.8)/2.7

Flow dependence between S1 and S2

Anti dependence between S2 and S3

Output dependence between S3 and S4

Constant Folding (常数折叠)

把常数直接展开不通过变量运算

Dead Code Removal (死代码消除)

删除永远不可能执行到的指令

Strength Reduction

比如把 pow 换成乘法，要把“昂贵的计算”尽可能多换成简单的代码，再比如除法换乘法

Common Subexpression Elimination

消除公用的表达式

变量重命名

本来想复用的变量，可以用因变量名避免依赖

Loop Optimizations

Hoisting Loop Invariant Code

不在循环体内做完全重复计算

Unswitching

把可以放到外层循环的判断放到外层，减少应用程序分支判断次数

Iteration Peeling

讨厌在内循环体出现 if，因为打断了流水线和指令集并行

Index Set Splitting

比如在循环里对 i 中间某个值做判断，可以把循环拆开写成两个

Loop Interchange

比如二维数组，把连续的内存连着读取，连续访存

Unrolling

循环展开，可以把连续访存的循环中间连着的指令写出来，然后 i 步进大一点。我们期望非常少的访存，非常多的计算。

Loop Fusion

循环融合，原来可能多个循环重复使用变量，现在可以合并到一起

Loop Fission

循环展开，当一个循环里访存开销非常大容易 cache miss，不如拆开然后写成多个小循环

真正准确的办法去查看应该怎么办，就是 PMU，查看 cache miss 次数等等

Inlining

内联，把小函数变成内联函数，指令不用跳转到很远处，可以使用指令缓存，而且跳转还需要压栈解栈，但是要是都展开整个文件也可能非常大，主要取决于调用次数和函数的复杂程度

Intel 编译器

最合理的办法： 选择合适的编译器参数，调整编译器选项

最新版本 OneAPI 2025.3.1

多语言支持、多硬件架构支持
- C
- C++
- Fortran
- 多线程支持 OpenMP
GCC 兼容
多体系结构支持
多操作系统支持

Mac/Linux - -O1 优化可执行文件大小 - -O2 面向执行速度的优化 - -O3 O2+进一步的优化：主要面向以浮点运算为主的循环和大规模数据处理的程序 - -fast 集成优化 - -g 加入调试信息

Intel 编译器还提供对于特定处理器的优化，对于平台来说，用 -xHost 选项选择当前平台

还支持过程间优化（IPO）

-ip 源程序文件内部的过程间优化
-ipo 多程序文件的过程间优化

高级优化：指导优化（PGO）

icc -prof_gen prog.c 第一次编译然后运行拿到诊断信息 icc -prof_use prog.c 第二次编译使用诊断信息指导优化，但是有限制，输入数据如果和运行时不一样，那么运行时的诊断信息可能不准确所以执行信息的代表性很有必要

自动并行化

-parallel 只能处理简单并行（但是效果有限）

OpenMP 支持

编译优化的方法

性能优化的第一步
有方向感的 Try and Test（通用 -> 专用）
- 对编译器输出报告的分析
- Note: 不同编译选项对程序性能影响不独立
在性能提升的同时留意精度问题

例如可能有大量浮点运算，会做很多针对浮点数的优化，比如会打破精度来换性能

关于浮点精度扩展

能用单精度不用双精度，要注意基础库调用的文档不同，函数名和所在库可能有区分

编译器报告

Mac/Linux - -qopt-report[-n] -qopt-report-phase=...

设置不同的 Optimization Phase，串行程序用 vec 然后可能访存优化用 loop，还可以控制向量报告输出信息

Guided Auto-Parallelism (GAP)

-guide 给出并行优化的指导，有的时候合理有时不是

鼓励下载 Intel OneAPI Base Toolkit

Intel Parallel Studio XE 不仅有编译器，很多计算都有对应的高性能库

性能分析方法

Profiling是指一个应用程序执行行为的统计信息，比如每个函数的执行时间、指令的类型分布

Tracing 指按照程序执行的时间顺序记录每条事件详细信息。例如：程序访问内存的序列、指令访问序列

具体工具

插装 Subroutine profiling

统计 Hardware performance Counter sampling

手动插装

程序执行时间是指用户程序的响应时间（访问磁盘和访问存储器的时间，CPU时间和操作系统的开销）

自动插装：gprof

编译的时候需要 icc -O -g -p ...

运行新编译的程序生成 .out 文件，然后 gprof <executable>

Top-down 分析法

性能工具

General Purpose Timing Library

GPTL 是一个和计时有关的 C，C++，Fortran 库

Perf

Linux Performance Observability Tools

VTune

https://software.intel.com/en-us/vtune/features/single-threaded

Intel Advisor

分析访存瓶颈和计算瓶颈

访存优化

读取的粒度影响测量性能，往往需要确定最小的带宽打顶的粒度

访存连续性是有效利用内存的关键

具体方法

通过把数据存到缓存里减少访问内存次数，短时间内复用数据（temporal locality）
连续访存（spatial locality）
预取（prefetch）

Prefetch

编译器选项控制 -qopt-prefetch -qopt-prefetch-issue-excl-hint
编译指导语句 #pragma prefetch
__builtin_prefetch
Intrinsics: _mm_prefetch

Alignment

Static memory: _attribute_((aligned(n))) in variable declaration
Dynamic memory: _mm_malloc(size, alignment_bytes); _mm_free()
通过 __assume_aligned(pointer, n) 告知后面用这种方式访存 pointer 代表的变量
采用 #pragma vector aligned 通知后面 loop 所有变量都是对齐访问

指令优化

SIMD (single instruction, multiple data) 处理，编译器会自动做，不要手动展开为了所谓的 better SIMD

代码变换

避免分支结构和函数调用，避免循环迭代之间的依赖，对于 C 语言，使用数组下标而不是指针

内存布局转换

结构体的数组（Array of Structure, AOS） 和 数组的结构体（Structure of Array, SOA）

内存中，AOS 的同种成员变量有距离，而 SOA 则是相邻的，也就是说 AOS 会影响 SIMD 效率，但是 SOA 会影响原来数据结构的连续性

Intrinsics 支持向量化

Intrinsics 函数和使用单行汇编的效果相同，现在的 Intrinsics 指令支持读取处理器状态和管理内存、向量化、半精度支持、简短的向量数学库操作

指导语句控制

#pragma ivdep 告诉编译器循环里没有向量之间的依赖，可以放心向量化

#pragma vector aligned/unaligned 告诉编译器使用对齐/非对齐的内存指令

编译优化

-qopt-report=n -qopt-report-phase=vec

Level 0: No vectorization report
Level 1: Reports when vectorization has occurred
Level 2 (default): Add diagnostics why vectorization did not occur
Level 3: Add vectorization loop summary diagnostics
Level 4: Additional detail, e.g. on data alignment
Level 5: Add detailed data dependency information

没能向量化的原因： 向量间依赖、访存时不连续、数据类型不统一等等

使用对齐的内存访问和连续的内存访问

性能模型

性能模型使用数学近似方法模拟不同用户和系统的载荷，这比性能测试成本更低廉并且结果准确

Roofline Model

Roofline Model 以吞吐量为导向，追踪吞吐率而不是时间，独立于指令集和处理器架构

并行程序模型

并行处理

多个任务在多个处理单元上同时执行，这样同一个任务算得更快，利用的计算资源更多，提供并发性

向量化计算单元
多核处理，同时支持多条指令流运行，提速核数倍，前提是压低并行开销（协同开销、资源竞争开销）
单机多处理器（涉及到缓存、内存带宽的并行，不单单是处理器和核心）
多机并行

并行程序模型

并行程序抽象的运行行为，虚拟层的抽象描述包含如何建立并行，如何控制操作次序，如何进行数据管理和通信，如何协调并行或者是原子化操作

共享存储模型（Shared Memory）

并行程序由一组进程/线程构成

数据驻留在单一地址空间，不用显式分配数据
每个进程/线程有局部变量和共享变量
通讯通过读取共享变量隐式完成
进程/线程异步执行
显式同步控制正确的执行顺序
线程可以动态产生和消亡

均匀存储访问（Uniform Memory Access, UMA）：所有处理器访问未缓存的内存地址开销相同，可以认为内存地址相对于处理器们一样远

非均匀存储访问（Non-uniform Memory Access, NUMA）：不同处理器访问相同内存的开销不同，因为内存被分割，不同内存和不同的处理器距离不一样，这样可能访存时间有长有短（相对于 UMA）

全局内存访问（Compute Express Link, CXL）

SMP 面临的挑战：缓存的一致性，如果其他的处理器改变了内存但是另一个处理器的缓存没有及时同步，会出问题，但是维持这种同步需要显著的硬件资源和开销

同时也有对于共享资源的竞争，可以通过互斥锁，但是这样开销巨大

共享存储编程更多使用线程，主要是线程默认共享内存，共享文件描述符，共享文件系统上下文，共享信号处理

编程环境：

Posix threads (Potable Operating System Interface)，通过函数库调用，面向 C 语言
共享存储并行程序标准 - OpenMP，采用指导语句的方式，编程需要编译器支持

消息传递模型（Message Passing）

并行程序由命名进程构成，拥有分开的地址空间，即没有共享数据，数据和负载显式分配，进程间通信采用显式的 send/receive 组，显式同步确保执行顺序，多进程异步并行，进程数多在启动时确定

与其相适应的并行系统：分布式存储系统（e.g. 并行系统），每个处理器有自己的内存缓存，不能访问其他处理器的数据，每个节点通过网络接口完成通信和同步

分布式存储系统：内存随着处理器数而等量扩展，每个处理器对于自己对应的内存访问不受阻碍，不用处理缓存同步，开销更低（使用现成的处理器和网络）

消息传递模型特点：普遍适用（多机和单机），广泛采用但是会增加消息传递程序本身的开发复杂性

基本的通信形式：

阻塞式通信
非阻塞式通信

性能问题：资源利用率低，并行成本高

消息通信并行编程标准（Message Passing Interface, MPI）：实现是一个库，和特定语言组合

全局地址空间（Global Address Space）

命名线程构成，通常线程数在运行之前固定，本地和共享的内存，但是共享的数据在本地进程之间分布，远处数据的开销很大，这个模型相当于在共享内存模型和消息传递模型之间寻求平衡

适应的系统：使用的 Infiniband 的集群，网络接口支持 RDMA (Remote Direct Memory Access)

即不需要 CPU 中断就可以访问内存，读写只需要单侧操作，内存读写操作不会阻塞计算，远程数据通常不缓存

数据并行（Data Parallel）

单线程模式：并行操作于聚合数据结构上，一般是数组，隐式相互作用，不需要显式同步隐式数据分配，但是缺乏严格的计算结构要求

相适应的并行系统：SIMD（单指令多数据系统），多为面向科学计算的专用系统，编程模型通过编译器实现

Hybrid Programming Model

MPI at the top level with shared memory within a node is common

Global Address Space Model can also be used in a hybrid mode

并行计算基础

编译优化基础

优化方式

Copy Propagation (拷贝传递)

Constant Folding (常数折叠)

Dead Code Removal (死代码消除)

Strength Reduction

Common Subexpression Elimination

变量重命名

Loop Optimizations

Intel 编译器

编译优化的方法

关于浮点精度扩展

编译器报告

Guided Auto-Parallelism (GAP)

性能分析方法

具体工具

手动插装

Top-down 分析法

性能工具

访存优化

Prefetch

Alignment

指令优化

代码变换

Intrinsics 支持向量化

指导语句控制

编译优化

性能模型

Roofline Model

并行程序模型

并行处理

并行程序模型

共享存储模型（Shared Memory）

消息传递模型（Message Passing）

数据并行（Data Parallel）

Hybrid Programming Model

并行编程原则