[科普中国]-全局程序优化理论

程序优化是指改进程序，使之节省存储空间，提高执行效率，这个过程称为优化。优化的目标是从执行的结果程序中消除重复计算。程序优化的基础：控制分析，数据流分析。程序优化可以分类为局部或全局的，依赖于机器或不依赖于机器的，依赖于语言或不依赖于语言的。全局程序优化理论是指编译阶段对整个程序执行语句和数据流指令进行优化的方法，最终生成的程序代码短，时空效率优化。

简介全局程序优化理论是指用于提高程序执行效率和降低程序执行代价的有关理论，包括程序编译阶段，对程序的语义语法优化和中间代码的优化。程序设计阶段中，程序模块的设计和有关函数库的选择，程序的有关语句和循环结构选择，即代码优化，代码优化是指对程序代码进行等价变换。等价的含义是使得变换后的代码运行结果与变换前代码运行结果相同。全局程序优化理论主要目的是提高软件性能。软件性能是软件的一种非功能特性，它关注的不是软件是否能够完成特定的功能，而是在完成该功能时展示出来的及时性，是指一个软件系统正确提供其服务的能力和效率，是软件对用户请求响应速度在响应时间、 吞吐量、资源利用率和可用性等方面的度量。

优化策略提高程序的数据局部性

程序员编程喜欢用结构体去抽象对象类型，即在结构体中定义一组与对象相关的数据的类型。例如，如果编写一个学籍管理系统程序，程序员往往把学号姓名、性别、联系方式等信息用结构体组合在一起，来描述学生：个学生对应一个这样的结构体对象。显然，使用结构体编程思维可以更加容易的编写程序而且使程序有更好的可读性。但是如果程序中存在大量的结构体，特别是结构体数组，会降低了程序的数据局部性，降低程序的性能。例如，如果在上面学籍管理系统的例子中，有一段代码只是频繁访问学生的联系方式信息，但是程序运行时，会把整个学生这个结构体数据载入的缓存中，即把不相关的姓名、性别等信息也载入了缓存。这样会降低缓存的利用率，增加从而使得程序的性能下降。结构体数组分拆能够把结构体数组分拆成其各个域的数组，提高程序的数据局部性。使用结构体数组分拆工具，程序员可以继续使用结构体编程思维编程而不影响程序的性能1。

程序存储管理需要的信息支撑

存储管理是程序优化一个重要手段。当前研究对于稠密数组的内存管理能取得不错的性能提高，但是对于堆内存对象的性能提高不够理想。一个重要原因是因为获取其结构信息比较困难。例如像这样的语言，由于允许使用指针，程序员可以构造出任意深度的链状堆内存对象，其往往有着复杂的结构。对程序进行分析时，堆内存对象的具体结构无法直接通过指向它的指针或者指针指向的顶层节点获得。而如果得不到堆内存对象的结构信息，存储管理就无法判断它打算分离两个堆内存对象的结构是否独立，就无法它们进行分离、分别进行存储优化。所以堆内存对象的结构信息是程序存储管理需要的一个重要信息支撑。

调用高性能库

充分利用已有的高性能程序库是提高应用程序实际性能最有效的途径之一。许多著名的高性能数学程序库如优化的 BLAS、FFTW等，由于经过厂商或第三方针对特定处理机进行的专门优化，其性能一般大大优于用户自行编写的同样功能的程序段或子程序。合理地调用这些高性能库中的子程序，可以成倍、甚至成数量级地提升应用程序的性能，达到事半功倍的效果。

并行程序性能优化

并行程序的性能优化相对于串行程序而言更加复杂，其中最主要的是选择好的并行算法及通信模式。在并行算法确定之后，影响并行程序效率的主要因素是通信开销、由于数据相关性或负载不平衡引起的进程空闲等待、以及并行算法引入的冗余计算。在设计并行程序时，可以采用多种技术来减少或消除这些因素对并行效率的影响。

通信、计算的重叠

通过让通信与计算重叠进行，利用计算时间来屏蔽通信时间，是减少通信开销的非常有效的方法。实现通信与计算重叠的方法一般基于非阻塞通信，先发出非阻塞的消息接收或发送命令，然后处理与收发数据无关的计算任务，完成这些计算后再等待消息收发的完成。通信与计算的重叠能否实现，除了取决于算法和程序的实现方式之外，还取决于并行机的通信网络及通信协议。

负载平衡

负载不平衡是导致进程空闲等待的另外一个重要因素。在设计并行算法时应该充分考虑负载平衡问题，必要时使用动态负载平衡技术，即根据各进程计算完成的情况动态地分配或调整各进程的计算任务。动态调整负载时要考虑负载调整的开销及由于负载不平衡而引起的空闲等待对性能的影响，寻找最优负载调整方案

全局通信尽量利用高效聚合通信算法

当组织多个进程之间的聚合通信时，使用高效的通信算法可以大大提高通信效率、降低通信开销。对于标准的聚合通信，如广播、归约、数据散发与收集等，尽量调用 MPI 标准库中的函数，因为这些函数往往经过专门优化。但使用标准库函数的一个缺点是整个通信过程被封装起来，无法在通信的同时进行计算工作，此时，可以自行编制相应通信代码，将其与计算过程结合起来，以达到最佳的效果。

代码优化代码优化是指对程序代码进行等价（指不改变程序的运行结果）变换。程序代码可以是中间代码（如四元式代码），也可以是目标代码。等价的含义是使得变换后的代码运行结果与变换前代码运行结果相同。优化的含义是最终生成的目标代码短（运行时间更短、占用空间更小），时空效率优化。原则上，优化可以在编译的各个阶段进行，但最主要的一类是对中间代码进行优化，这类优化不依赖于具体的计算机。在不改变程序运行效果的前提下，对被编译的程序进行等价变换，使之能生成更加高效的目标代码。

本词条内容贡献者为:

宋春霖 - 副教授 - 江南大学