自顶向下的软件优化指南

### 自顶向下的软件优化指南 #### 1. 应用层面的算法优化 在应用层面，软件很少由标准组件构成，其大部分功能都与其他软件不同，造成这种差异的关键在于所使用的算法及其实现方式。需要注意的是，优化并不意味着要进行大规模重写，不应改变整体算法。例如，有限差分程序应保持其原有形式，即便有限元方法可能更合适。我们要做的是优化现有的算法及其组成的众多小算法。 #### 2. 应对内存墙问题 现代高性能计算（HPC）系统的性能主要来源于单指令多数据（SIMD）向量化和并行化，这两个方面在应用层面都需要考虑。然而，一个核心问题是处理器和内存性能的差异。摩尔定律表明，固定硅片面积上的晶体管数量大约每两年翻一番，这在一定程度上也意味着性能的提升。例如，芯片上处理核心数量翻倍，可用空间就会增加一倍；即使核心数量不翻倍，额外的晶体管也可用于其他用途，如AVX1和AVX2指令集，它们能使每个周期处理的浮点运算数量翻倍。同时，速度更快、容量更大且效率更高的缓存也是这一发展的一部分。 但在处理器之外，动态随机存取存储器（DRAM）的性能增长速度仅为CPU性能增长速度的1.2倍。1994年，W. A. Wulf和S. A. McKee首次提出这会导致CPU“饥饿”的观点。不过，实际情况并没有那么糟糕，更多的缓存层级、更大的缓存容量、集成内存控制器以及更多的内存通道，再结合CPU硬件预取器，在一定程度上缓解了这一趋势。尽管如此，内存子系统的压力仍在增加，因此应用调优应重点关注这方面。 合理的数据管理影响可通过不同层级的缓存延迟与随机存取存储器（RAM）访问延迟的比率来估算： \[S = \frac{L_{RAM}}{L_{cache_n}}\] 该比率范围在2到5倍之间。 |影响因素|影响倍数| | ---- | ---- | |数据布局和访问性能|2 - 5x| #### 3. 向量的魔力 当数据在缓存中随时可用时，计算本身可能会成为瓶颈，此时SIMD向量就发挥作用了。SIMD指令可以同时对SIMD向量的不同元素执行相同的算术运算。通常，编译器即使在非常复杂的环境中也能很好地对代码进行向量化，但也可能存在无法向量化的情况。英特尔编译器有很有用的报告功能，能准确告知无法向量化特定循环的原因。 向量化对性能的影响可通过给定类型的向量元素可并行处理的数量来估算。对于双精度/AVX，可能的加速比为4倍；对于单精度，为8倍。 |向量化类型|性能影响| | ---- | ---- | |双精度向量化|4x| #### 4. 分布式内存并行化 HPC中最重要的并行化技术是分布式内存并行化，它能实现可能不共享公共地址空间的进程之间的通信。其好处显而易见，可跨物理不同的计算机进行通信，充分发挥大规模并行HPC集群的全部能力。 20世纪90年代初，研究人员设计并标准化了消息传递接口（MPI）。MPI标准定义了独立于语言的通信协议，以及用Fortran或C/C++编写可移植消息传递程序所需的例程的语法和语义，许多其他语言也有非标准绑定。MPI标准由MPI论坛管理，众多商业和开源库都实现了该标准。 随着共享内存架构的流行，MPI库也在不断发展。2012年9月发布的最新MPI - 3标准增加了快速远程内存访问例程、非阻塞和稀疏集体操作等与性能相关的扩展。不过，编程模型仍然是具有显式并行性的分布式内存模型，开发者负责正确识别并行性并使用MPI原语实现并行算法。 分布式内存并行化带来的性能提升大致与可用计算节点的数量成正比，对于常见的计算集群，范围在10到1000倍之间。 |并行化类型|性能影响| | ---- | ---- | |分布式内存并行化|10 - 1000x| #### 5. 共享内存并行化 共享内存并行化与分布式内存编程不同，分布式内存编程的并行化单元通常是具有自己唯一地址空间的进程，而共享内存编程处理的是公共地址空间中的并行执行流，一般在同一物理系统上执行。虽然进程也可参与共享内存通信，但通常考虑的是线程。 要让程序在共享内存系统中利用所有处理器，有多种提供应用程序编程接口（API）的库，如POSIX线程。但很多线程API要么特定于操作系统，不便于移植到其他操作系统；要么使用底层硬件的独特功能；要么过于底层。因此，HPC社区一直在为C、C++和Fortran等流行编程语言构建开放、可移植且与硬件无关的编程接口来实现线程支持。开发者对跨平台、易用的线程API的需求使得OpenMP成为目前最流行的线程API。 OpenMP由一组编译器指令、库例程和环境变量组成，可影响程序的运行时行为。OpenMP 4.0规范增加了对SIMD优化以及加速器和协处理器的支持。 共享内存并行化的性能提升大致与每个计算节点可用的核心数量成正比，在现代服务器架构中为10到20倍。 |并行化类型|性能影响| | ---- | ---- | |共享内存并行化|10x - 20x| #### 6. 其他方法 除了MPI和OpenMP这两种流行的并行编程模型外，还有其他一些方法值得关注： - **分区全局地址空间（PGAS）**：该模型假设存在一个逻辑上分区的全局内存地址空间，每个部分对每个进程或线程都是本地的。PGAS方法试图结合分布式内存系统的MPI编程风格优势和共享内存系统编程中使用的数据引用语义。它是统一并行C、联合数组Fortran（现在是Fortran标准的一部分）以及更多实验性接口和语言的基础。 -