| 2011年12月17日 07:00 | |
多线程并行程序性能分析方法综述
[引言] 本章主要介绍关于多线程并行程序性能分析方法的一些原则。并介绍如何利用一些Intel的软件工具来辅助进行多线程并行程序的性能调优。
2.1 性能调优周期：
性能调优周期指的是软件开发过程的一个螺旋式前进周期。其主要前进动力是数据驱动式的。如图2.1所示：
图2.1 性能调优周期示意图
在这个性能调优周期螺旋式上升循环中，在一次循环（迭代）中获得的数据、结果将直接推动下一次循环（迭代）的产生与前进。因此，在性能调优周期每次向前移动的时候，程序开发人员都必须要能够正确理解当前所得到的结果及其对下一步的推动作用。
在程序开发人员开始任何对程序调优的努力之前，必须要知道为什么，以及更重要的，什么时候应该开始对程序进行调优努力。促进程序开发人员对程序性能进行调优的原因可能有很多，比如，用户需求，软件开发公司对产品的性能要求，等等。所有的这些需求，无论来自哪方面，最好都写入程序开发文档。但无论如何，最好在一个新的软件开发项目的最开始阶段就为性能调优预留出时间并制定合理计划。
当你被说服你的程序需要在性能上进行调优时，你必须知道在什么时候开始这样的工作。需要被性能调优的程序必须处在开发的适当阶段（至少是在BETA测试版阶段）并且必须具备如下特性：
- 程序必须是稳定的：在进行性能调优之前，程序必须是稳定可靠的，能够正确执行程序所有预定功能。并且，最好程序能够内建一些性能调优的辅助手段，比如计数器、计时器等等。
- 程序必须是有代表性的：进行性能调优的程序必须已经实现了用户对程序的所有需求。
- 程序必须使用了最新的技术：进行性能调优的程序必须包括了所有的最新技术。对一个正在进行系统化的重新设计，其中某些功能可能会在将来被取消的程序进行性能优化是没有多大意义的。在这方面，唯一需要注意的是对最新技术的使用不应该影响程序的稳定性。
虽然性能调优一般是在程序完成BETA测试版后再进行，但是在软件产品开发的每一阶段（包括客户需求搜集，设计，测试各阶段），都应该将性能考虑进程序设计的目标。
而且性能调优工作越早做越容易获得性能的提升，而利用一些比较好的软件工具，比如Intel VTune Analyzer，也可以成倍的提高工作效率。最好的性能提升一般是在软件项目开发的恰当阶段，对所要解决的问题使用恰当工具的结果。
知道什么时候开始性能调优，同时也得知道什么时候结束。性能调优工作并不是，也不需要无限制的做下去。在开始性能调优工作之前，你必须对整个程序进行一个基准测试（baseline measurement），并且知道在所使用的计算平台上的该程序可能达到的理论峰值为多少。只有知道了这两个数值，才有可能制定出一个合理的性能优化目标：比如比基准测试的性能提高多少，或者达到理论峰值的百分之多少等。
但如果在性能优化中要以牺牲程序的可移植性（Portability）、可读性（Readability）、可维护性（Maintainability）、可靠性（Reliability）为代价的话，就必须谨慎小心了。不成熟的优化是程序设计与开发中几乎所有错误的根源（Donald Knuth）。所以也有了如下的Jackson优化定律：
Jackson的优化定律：
定律1：不要进行优化。
定律2：（仅针对专家）“除非你已经有了一个相当清晰可靠的非优化版本的实现，否则你不要试图对程序进行优化”。
2.1.1 搜集性能数据
性能调优周期的第一阶段就是搜集性能数据。首先，必须通过对所开发程序进行基准测试检查该程序是否需要进行性能调优。然后，使用一些软件工具，比如Intel VTune Analyzer来搜集性能数据。或许，你会首先想到对那些已知的的领域，或者仅凭猜测对程序进行性能调优。然而，对于性能调优来说，一个理性的方法的是让数据驱动。因为程序中真正的性能瓶颈必须依靠真正的测试数据来发现，而这些瓶颈往往和你所预期的不一样。
获得性能数据的方法可以有：采用一些程序内建的计数器、计时器来获得墙上时间，其结果精确且代价较小；或者，利用Intel® VTune™性能分析器中的：Profiler搜集整个程序中的代码执行信息，性能监视器（Performance Monitor）来搜集程序对系统平台资源的使用状况。
为了搜集性能数据，一个好的测试数据集是必不可少的。一个好的测试数据集必须要具备以下一些特点：
- 可衡量性（Measurable）：该测试数据集运行后必须要能有一些性能指标，并且这些性能指标必须是可以量化比较的。
- 可重复性（Reproducible）：对该测试数据集的重复运行必须要能产生相同、一致的结果。
- 静态的（static）：该测试数据集不会随着时间的变化而变化。
- 有代表性（Representative）：该测试数据集必须能够代表你的程序在典型计算环境下的典型应用。
2.1.2 分析数据并定位性能瓶颈
在性能调优周期的第二阶段必须要能够分析搜集到的性能数据。你必须要能够理解并解释测试所得到的数据。在一开始，首先首先要能够找到那些与预期不符的结果。必须要能够在数据的指引下找到需要优化的路径以及不需要优化的路径，避免在不需要优化的路径上浪费时间。在进行数据分析时，必须要时刻问自己这个问题“这些数据有没有清晰的指出性能问题所在？”
意大利经济学家Vilfredo Pareto曾经用一个数学公式描述了他的国家财富分配的不均：占人口比例20%的富人却占有了整个国家80%的财富。这个公式通常被称为80/20定律。80/20定律在软件性能领域也是同样适用的。在大多数程序中，往往仅有那么一小部分代码占用了整个程序执行时间的80%以上。因此，你需要把你的主要精力集中在这20%的性能瓶颈上，而忽略掉其它大部分的小的地方。这样的性能瓶颈往往包含循环为主要程序结构。对于那些没有显著性能瓶颈的程序，我们可以检查其数据的内存布局（Memory Layout），对异常（Exception）的处理，以及对编译器的使用情况等等。
2.1.3 加速比性能定律
要衡量性能调优工作的好坏，就需要一些基本的判定方法。本节所要介绍的Amdahl定律，就是为了帮助程序员能够量化地判定其性能调优工作的好坏。以下为了讨论方便，定义如下参数：令 p 是程序可能被优化的最大加速比；W 是问题规模（也被称作计算负载、工作负载，定义为给定问题的总计算量）， Ws 是程序中无法，或很难被优化的计算负荷，W 中可被优化部分为 Wp （显然 Ws + Wp = W ）； f 是不可优化部分与整体程序的比例（ f = Ws/W , Ws = W1 ）， 1 - f 为可优化部分占程序总体比例（显然 f + (1 - f) = 1 ）； Ts = T1 为不可优化部分的执行时间， Tp 为可优化部分的执行时间； S 为加速比， E 为效率。
2.1.3.1 Amdahl定律
Amdahl加速定律的基本出发点是：对于整个程序优化后可能达到的加速比取决于程序可优化部分占程序执行时间总体的比例。在此意义下，1967年Amdahl定义了如下固定负载的加速公式：
为了归一化， Ws + Wp 可相应的表示为 f + (1 - f) ，所以
当 p → ∞ 时，上式极限为：
这就是著名的Amdahl定律，它意味着即使对程序的可优化部分进行最高限度的性能改进，其对程序整体性能的改进仍然受限于可优化部分占程序总体的比例，而并不随所用优化手段的提高而提高。其可能达到的加速上限为 1/f ，这是一个悲观的结论。
Amdahl定律告诉程序员，如果要使得程序获得更高的性能，就要对程序中更大的部分进行性能调优。Amdahl定律也告诉我们，无论你花费多大的时间对程序进行性能优化，总有一部分程序，其性能是很难被提高的。而整个程序可能达到的性能上限却恰恰受制于这一小部分。换句话说，你的程序的性能受限于程序中性能最差的部分。
2.1.3.2 性能优化过程中的一些其它考虑因素
大O量级的优化。在计算机科学及数值计算领域，我们通常使用大O来描述一个程序或算法的复杂度（包括时间复杂度与空间复杂度），比如线性查找（Linear Search）的复杂度为 O(n) ，折半查找（Binary Search）的复杂度为 O(log)n ，冒泡排序的复杂度为 O(n2) ，快速排序的复杂度为 O(nlogn) 等。同样的，我们也可以利用大O来确定程序中的性能瓶颈。比如说，你可以将一个循环运行10，100，1000次，然后将其所花费时间画成一条曲线，看该性能曲线的增长趋势。如果该曲线呈线性增长，那么你就可能需要考虑一个替代算法了。
性能调优工作包括了改进系统平台的资源利用率，提高有效性，减少延迟，增加并发度，改进吞吐量，减少可能的性能瓶颈。
一个程序对系统平台的资源利用率指的是某一个设备忙且用于服务该程序的时间。从数学上，利用率可以表示成一个设备忙的时间除以整个的时间：。比如，在Windows操作系统上，如果要确定CPU的利用率，就可以使用Windows性能监视程序——Perfmon。Perfmon可以检测并报告CPU的空闲时间，将空闲时间从总的CPU时间中扣除，我们就很容易得到CPU的利用率。
有效性指的是程序执行时间中用于做实际工作的时间的比例。粗看起来，似乎程序对系统资源的利用率可以在一定程度上决定有效性。但实际上，各种各样的因素都可能影响到性能。有效性是一个主观性很强的度量，因此很难给出量化的指标，也不存在一个有效性计数器之类的东西可以来客观的评估。作为程序员，只能间接的决定一个系统或程序是否是有效的。对于被优化程序行为的了解往往就是衡量有效性的最佳手段。
延迟指的是完成一个特定任务所需花费的时间。决定延迟最重要的两个因素是内存存取时间以及I/O时间。延迟又常常被称作响应时间。如果可以将一个主任务分割为若干子任务的画，那么延迟又可以定义为完成最长（最慢）子任务的时间。这样的一个例子是对磁盘进行一个写操作，但这一个写操作在硬件级别上可能可以分成若干个小的写操作，最后总的延迟可以被度量为这若干小的写操作中最慢的一个的完成时间。
多处理（Multi-Processing）指的是在一个单一系统上同时执行多个进程或多个程序的能力。多处理能力带来的最大好处是能够改进吞吐量（throughput）。多处理不等同于多线程，事实上，一个多线程程序的运行只需要一个单处理器系统即可。多处理器系统的优点主要在于优化吞吐量，这里的一个典型例子是多用户操作系统。
多线程（Multi-threading）指的是在同一个地址空间内同时执行多个线程的一个过程。这些在相同地址空间内同时执行的线程一般具有不同的执行路径和不同的堆栈结构。当然，不同的线程执行相同的路径但对不同的数据进行操作也是可能的。一个使用多线程技术改进并发性（concurrency）的例子是一个线程在计算，另一个同步的输出计算结果。或者，让多个线程同时对一个矩阵的不同部分进行计算。
并发性（Concurrency）指的是同时执行多个结构不同的程序或任务。并发性既可以指对单个程序使用多任务处理，也可以指对多个程序使用多任务处理，比如说，一个系统同时进行诸如计算、磁盘存取、网络I/O等多个任务。并发性可以改进有效性（efficiency），减少延迟，提高吞吐量。高并发性可以显著减少一个程序的空闲等待时间。在Intel®解决方案服务（Intel ® Solution Services）中一共提出了三个指标，就是：并发性，延迟，以及吞吐量。
吞吐量（Throughput）衡量的是系统在单位时间内可以完成的工作总量。系统中每一个资源都有自己描述吞吐量的方法。比如说，对于内存系统，吞吐量就可以定义为单次的内存存取中最多可以有多少个字节从cache传递到CPU中。当然，吞吐量一般都会有一个上界。比如再以内存系统为例，内存带宽，前端总线带宽往往就是限制内存系统吞吐量的物理上界。
关于吞吐量有个著名的Little等式（Little’s Equation）：
NumberOfTasks = ArrivalRate × ResponseTime
在Little等式中的ArrivalRate指的是系统中客户需求到达的速率。当一个系统中，需求完成的速率大于达到的速率时，则称该系统时稳定的、平衡的。ResponseTime指的是系统对客户需求的平均响应时间，这包括了客户需求在系统队列中的等待时间。
瓶颈（Bottleneck）指的是程序运行过程中性能最差的地方。程序中最容易造成性能瓶颈的地方主要有：串行I/O，磁盘存取，内存单元分配，网络存取等。一般而言，一个程序总会存在若干性能瓶颈。因此，对性能瓶颈的处理只能是尽力改进，而很难完全消除。改进性能瓶颈的过程往往是个迭代的过程，经常性的，一个瓶颈的消除会引导程序员在系统的另一个地方发现另一个完全不同的瓶颈。
可扩展性（Scalability）指的是一个程序或系统中蕴涵的通过增加可使用的资源的数目而增加性能的能力。比如说，一个可扩展性好的程序会随着所使用处理器数目的增多而自动获得较高的性能提升。可扩展性是在对称多处理器系统（SMP）上一个经常被用来衡量一个程序能否充分利用到多处理器优势的指标。
循环中每次迭代所需要的内存存、取次数（loads/stores per calculation）：当两个程序的计算复杂度相同时，衡量它们之间性能差异的一个重要方面就是它们的内存存取复杂度，而内存存取复杂度既包括了每计算出一个有效结果所需的内存存、取次数，也包括了这些内存存、取之间相隔的跨度（stride），以及计算工作集大小（Working Set Size）。
对于Fermi’s Calculation，计算其计算复杂度大O，综的内存使用状况，loads/stores，及其与浮点计算操作数目之比。
2.1.4 解决性能瓶颈
通过搜集性能数据，并进行分析定位性能瓶颈所在后，下一步所要做的就是采取合理的优化措施来解决发现的性能瓶颈。当然，为了能够更有效率的工作，在着手解决发现的性能瓶颈之前，必须对所有可能的优化措施根据其实现的复杂度以及其可能取得的性能提升作出一个评价排名，并根据此排名做出该如何优化的决定。当做出决定后，每次只对一个性能瓶颈进行优化，不要分散工作焦点，要集中精力逐一攻克性能瓶颈。在对程序进行优化时，必须经常性的问自己这样一个问题“什么样的优化措施对这个具体的性能瓶颈是最有效的？”
对一个具体的问题做优化可以在如下许多不同的层次上进行：
- 问题定义：用户的问题究竟是什么？用户是否真的需要这样一个功能？
- 系统结构：整个程序的软件架构？各模块之间是如何交互的？
- 算法和数据结构：这也是快速排序和冒泡排序的区别。
- 代码调优：代码调优的工作就是调整代码，使之能充分利用好底层的系统软件和硬件的特性。
- 系统软件：调整系统参数。
- 硬件：将系统的关键硬件升级以改进系统的性能。
对一个具体的问题做性能优化时，可以同时在这多个层次上考虑可能的优化手段。一般来说，在越高的层次上进行优化，可能获得的效益越高；而在越低的层次上进行优化工作则相对越容易实现。当然，也需注意，某些优化手段可能会使在其它层次上所做的优化工作一下子化为零。
一般来说，本书以及Intel®性能工具（Intel ® Performance Tools）主要专著于在代码调优这一层次进行性能优化工作。然而，其它层次的优化也不容忽视。
一个能将多个层次上的优化工作结合起来的优化工作往往是最有成效的。有这样一个例子，通过使用多层次结合的优化手段将应用程序的性能提高了400倍。
至于在某个层次上究竟该如何进行优化，这在很多时候往往取决于其它层次上所做的一些优化措施。比如，如果决定将程序在多处理器系统上运行，那么就不应该选择快速排序算法，因为快速排序算法在多处理器系统上不是最优的。又比如，如果在问题定义层次上发现用户事实上并不需要将最后结果排序，只是要一个结果的汇总的话，那么，在系统结构这一层次取消排序才是最优的。
在系统结构这一层次主要需要考虑
在每个模块的层次上，每个模块的功能描述是否清楚，每个模块的可靠性如何？如果某些模块在系统中被重复调用，那么这样的模块更容易成为性能的瓶颈。
在整个系统软件架构的层次上，需要考虑整体的数据工作集是否充分利用了cache的特性，是否充分利用了处理器微体系结构上的特性，等等？
比如某些图像生成算法每次只对一个象素（pixel）进行操作，如果能把这些算法改成每次对整个数据集进行操作，那么，无疑的，整个算法的性能将有一个大的飞跃。又比如，Intel数学核心库并不适用于小规模的几何变换，在小规模应用里，调用Intel核心数学库的开销将超过其所能带来的性能提升。
在算法及数据结构这一层次主要需要考虑数据布局（Data Layout），以及如何在一些已有的算法中寻找一个最合适的算法。
在数据布局上需要考虑所定义的数据结构是否足够紧凑，是否充分利用了底层计算平台体系结构上的特性。对于数据布局两种最常用的手段为数据压缩（在不引入太多的额外数据处理的前提下，尽量不定义和使用占用内存较多的数据结构），和数据对齐（数据定义尽量沿底层计算平台的cache结构进行边界对齐，并避免造成过多的空间浪费）。特别的，当对一个服务器程序或者一个具有许多复杂条件分支的程序进行性能调优时，最好每次只对一个地方进行性能调优避免将情况复杂化。
在代码调优这一层次，可以考虑选择对汇编代码、内部调用、C++类库、多线程、循环转换、Intel® 编译器选项，高性能的Intel库函数等层次上进行优化。在这些层次中越往上越难实现和维护，越往下则实现、可维护性、可移植性也越好。在代码调优这一层次，如果所调优的程序是一个并行程序，则需要能够将算法很好的在集群系统（分布式内存体系结构）、单节点、多处理器系统（SMP）上进行分割、优化。
2.1.5 实现优化措施
在决定了如何进行代码调优后，下一步需要做的就是实现。在实现时，最重要的是一定要记住每一次只改动一个地方。如果一次对代码的多处进行修改，那么这些修改之间取得的效果很可能互相抵消，而且也不利于在必要的时候进行错误追踪或由原路退回（back track）。在做某些代码级变换，比如循环转化，SIMD，向量化等等时，首先查阅编译器手册或硬件手册，以确定编译器或硬件并没有自动进行这样的优化再进行实际的实现工作。
2.1.6 测试
性能调优周期（图chap:PerfCycle）的最后一步就是测试。测试首先试药保证整个程序正确运行，能够满足用户所有既定需求（主要通过回归测试）。对于使用了性能优化的部分，需要将其测试数据与开始的基准测试数据进行比较，如果性能有所改变，要能够理解为什么会发生这样的改变，这样的改变是否符合预期？如果不符合预期，则需要花费时间研究为什么？可能是优化措施的具体实现出了问题，也可能是测试方法有问题。测试时，必须时刻问自己这个问题“这样的结果是否就是我想要的？”。如果得到的结果与预期的相差甚大，则必须要能够分析原因，必要时还要将所做的优化原样退回（backtrack）。这也是之所以在做优化时必须每一时间只进行一种优化的原因。
