并行计算.3性能.

《并行计算.3性能.》由会员分享，可在线阅读，更多相关《并行计算.3性能.（67页珍藏版）》请在金锄头文库上搜索。

1、并行计算 1 并行系统的性能分析 并行系统的性能分析 一个串行程序的性能通常用它的运行时间来衡量，表达为 它的输入规模（问题规模）的函数。而并行算法的执行时 间不仅与问题的规模有关，还与并行计算机的体系结构和 处理器的数目直接相关，因此，对并行算法性能的评价不 能脱离具体的并行体系结构。一个并行系统是并行算法以 及实现这个算法的并行体系结构的组合体。 运行时间 一个程序的串行运行时间是程序在一个串行计算机上开始 执行到执行完成之间所经过的时间段的长度。 并行运行时间则定义为并行计算开始到最后一个处理器完 成它的计算任务之间的时间段的长度。 定义Ts为串行部分的执行时间，Tp为并行部分的执行时

2、间 加速比 在评价一个并行系统时，人们通常关心的是对一个给定的 应用，它的并行化版本比串行实现有多大的性能提高。加 速比就是一个衡量并行解题过程中的相对收益的指 标。 简单的讲，并行系统的加速比是指对于一个给定的应用， 并行算法（或并行程序）的执行速度相对于串行算法（或 者串行程序）的执行速度加快了多少倍。 加速比 通常由三种加速比性能定律：适用于固定计算负载的Amdahl定律， 适用于可扩展性问题的Gustafson定律和受限于存储器的Sun和Ni定律 。 为讨论方便，定义以下的参数： p是并行系统中处理器的数目； W是问题规模（也常常叫做计算负载、工作负载，它定义为给定 问题的总计算量），

3、Ws是应用程序中的串行分量，W中可并行化 部分为Wp ； f是串行分量的比例，即f = Ws / W ，则1 - f 为并行分量的比例； Ts 为串行部分的执行时间，Tp 为并行部分的执行时间； S为加速比， E为效率。 Amdahl定律 Amdahl定律的基本出发点是： (1) 对于许多科学计算，实时性要求很高，即在这类应用中计算时间是个 关键性因素，而计算负载是固定不变的。为此，在一定的计算负载下，为满 足实时性的要求，可以通过增加处理器数目的方法来减少运行时间，提高计 算速度； (2) 因为固定的计算负载可以分布在多个处理器上，这样增加了处理器就 加快了执行速度，从而达到了加速的目的。

4、在这样的动机推动下，1967年Amdahl推导出了固定负载情况下的加速比公式 ： Amdahl定律 固定负载情况下的加速比公式： 由于W=Ws + Wp，上式右边分子分母同除以W，则有 当 时，加速比的极限为 Amdahl定律 这就是著名的Amdahl加速定律，它意味着随着处理器数目的无限增 大，并行系统所能达到的加速比存在上限，且为一个常数1/f，这个常 数只取决于应用本 身的性质。 这个结论在历史上曾经对并行系统的发展带来了一种悲观的影响。它 带来的两种影响是，一是劝阻并行计算机厂商生产更大规模的并行计 算机，二是促进 了并行编译计算的发展，以降低程序中串行部分的值 。 Amdahl定律的

5、几何意义可以清楚的用下面的图来表示： Amdahl定律 Amdahl定律 当处理器数目n=1024，加速比公式如下， Sn随变化的情况如下图： Amdahl定律 实际上并行加速比不仅受限于程序的串行分量的比例，而且也受并行 程序运行时的额外开销的影响。如果考虑到这部分因素的影响，令 Wo为额外开销，那么上面的公式应该修改为： 这种情形下的加速比极限为： 结论：并行程序中的串行分量比例和并行额外开销越大，则加速比越 小。 Gustafson定律 Gustafson定律的基本出发点是： (1) 对于很多大型计算，精度要求很高，即在此类应用中精度是一个 关键因素，而计算时间是固定不变的。此时为了提高

6、精度，必须加大 计算量，相应的也必须增加处理器的数目来完成这部分计算，以保持 计算时间不变； (2) 除非学术研究，在实际应用中没有必要固定工作负载而使计算程 序运行在不同数目的处理器上，增多处理器必须相应的增大问题规模 才有实际的意义。因此研究在给 定的时间内用不同数目的处理器能够 完成多大的计算量是并行计算中一个很实际的问题。 (3) 对大多数问题，问题规模的改变只会改变计算中并行计算量，而 不会改变串行计算量。 从这些动机出发，Gustafson在1987年提出了变问题规模的加速比模 型： Gustafson定律 变问题规模的加速比模型： 当p充分大时，S与p几乎成线性关系，其斜率为1-

7、f，这就 是Gustafson加速比定律，它意味着随着处理器数目的增 加，加速比几乎与处理器数 目成比例的线性增加，串行 比例f不再是程序的瓶颈，这为并行计算系统的发展带来 了非常乐观的结论。 Gustafson定律 Gustafson定律的几何意义可以清楚的用下面的图来表示 ： Gustafson定律 当处理器数目n=1024，加速比Sn随变化的情况如下： 可以用图表示如下： Gustafson定律 同样的，当考虑到并行程序运行时的额外开销时，Gustafson定律应 该修改为： 注意：Wo是p的函数，它可能会随着p的改变而改变。要到达一般化 的Gustafson定律所描述的线性加速比，当p

8、改变时，必须要控制额外 开销的增长，这在实际中往往是非常困难的。 Sun和Ni定律 Xian-He Sun和Lionel Ni于1993年曾将Amdahl和Gustafson定律一般 化，提出了存储受限的加速定律。他们的基本思想是：只要存储空间 许可，应该尽量增大问题规模以产生更好或更精确的解（执行时间可 能略有增加）。换句话说，假如有足够的存储容量，并且规模可扩展 的问题满足Gustafson定律规定的时间要求，那么 就有可能进一步增 大问题规模求得更好或更精确的解。 Sun和Ni定律 给定一个存储受限问题，假定在单节点上使用了全部存储容量M并在 相应于W的计算时间内求解，此时工作负载W=f

9、W+(1-f)W。在p个节 点的并行系统 上，能够求解较大规模的问题是因为存储容量可以增加 到pM。用因子G(p)来反映存储容量增加p倍时工作负载的增加量，所 以增加后的工作负载W=fW+ (1-f)G(p)W。那么，存储受限的加速比 公式为： Sun和Ni定律 Sun和Ni定律的几何意义可以清楚的用下面的图来表示： Sun和Ni定律 如果考虑到并行程序运行时的额外开销Wo，则上面的公 式应该作相应的修改： Sun和Ni定律 当G(p)=1时，它变为 这就是Amdahl定律 当G(p)=p时，它变为f+p(1-f)，这就是Gustafson定律 当G(p)p时，它相应于计算负载比存储 要求增加

10、得快， 此时Sun和Ni定律指出的加速比比Amdahl和Gustafson定 律指出的都要高。 有关加速比的讨论 在实际应用中，可供参考的加速比经验公式为： 可以达到线性加速比的应用问题有矩阵相加、内积运算等等，这一类 问题几乎没有通信开销，而且单独的计算之间几乎没有什么关系；对 于分治类的应用问题，它类似于二叉树，处于树上的同级节点上的计 算可并行执行，但越靠近根，并行度将逐渐减少，此类问题可能可以 达到p/logp的加速比；对于通信 密集型的应用问题，它的加速比经验 公式可以参考下面的式子： S=1/C(p) 其中，C(p)是p个处理器的某一通信函数，或者为线性的或者为对数 的。 有关加速

11、比的讨论 严格的线性加速比对大多数应用问题来说，是难以达到的，更不用说 超线性加速比。但在某些算法或者程序中，可能会出现超线性加速比 现象，比如，在某些并行搜索算法中，允许不同的处理器在不同的分 支方向上同时搜索，当某一处理器一旦迅速的找到了解，它就向其余 的处理器发出中止搜索的信号，这就 会提前取消那些在串行算法中所 做的无谓的搜索分枝，从而出现超线性加速比现象；在大多数的并行 计算系统中，每个处理器都有少量的高速缓存，当某一问题执行 在大 量的处理器上，而所需要的数据都放在高速缓存中时，由于数据的复 用，总的计算时间趋于减少，如果由于这种高速缓存效应补偿了由于 通信造成的额外开销， 就有可

12、能造成超线性加速比。 有关加速比的讨论 最后值得指出的是，加速比的含义对科学研究者和工程实用者可能有 所不同。对一个给定的问题，可能会有不止一个的串行算法，它们的 运行时间也不会完全相同，这就带来了不同的加速比的定义。 研究者们使用绝对加速比的定义，即对于给定的问题，加速比等于最 佳串行算法所用的时间除以同一问题的并行算法所用的时间。 有关加速比的讨论 对最佳串行算法有几个说明。因为最佳串行算法也是通过实际运行测 出来的，按照串行算法运行平台的不同，绝对加速比也可以分成两种 。一种与具体的机器有关， 即串行计算机采用与并行计算机一样的处 理器；一种与具体的机器无关，此时的串行算法运行时间是串行

13、计算 机上的最短执行时间。但有的时候，对一个特定的问 题，它的最佳串 行算法是未知的，或者，它的串行算法所需要的运行时间太长，实际 运行它是不太现实的，在这些情况下，经常用已知的最优串行算法来 代替最佳串 行算法； 而工程中使用相对加速比的定义，即对于给定的问题，加速比等于同 一个算法在单处理器上运行的时间除以在多处理器上的运行时间。显 然，相对加速比的定义是比较宽松和实际的。 效率 只有理想的具有p个处理器的并行系统的加速比能够达到p，在实际中 ，这种理想情形是不可能达到的，因为在执行并行算法时，处理器不 可能把它们100%的时间都用来执行算法。比如，在计算n个数据和的 时候，一部分的时间被

14、用来进行通信了。 效率被用来衡量一个处理器的计算能力被有效利用的比率。在一个理 想并行系统中，加速比等于p，而效率等于1，而在实际系统中，加速 比小于p，而效率在0到1之间取值，它描述了处理器被有效利用的程 度，用E来表示效率，它可以用下面的公式来计算： E=S/p 效率 在n个处理器的超立方体上完成n个数的加法：开始时，每个处理器都 存放了一个待加的数据，算法结束时，其中的一个处理器中已经存放 了n个数累加的结果。 根据前面的讨论结果，可以知道，在超立方体上完成n个数的加法的 并行算法的效率为 开销 开销定义为一个并行系统在解一个问题的时候，并行运行时间与所用 的处理器的乘积。开销反映了在解

15、一个问题时，系统中投入运行的处 理器所耗费的总的时间。效率也可以表示成已知的最快的串行算法的 运行时间与在一个p处理器的并行系统上运行对应的并行算法的开销 的比值。 在单处理器上解一个题的开销被定义为已知的最快的串行算法的运行 时间，如果对一个特定的问题，一个并行系统的开销与单处理器上的 已知最快的串行算法的运行时间成比例，那么，就称这个系统是开销 最优的。由于效率可以表示成串行开销与并行开销的比值，所以，一 个开销最优的并行系统的效率为 o(1) 开销有的时候也被称为工作或处理器-时间积，一个开销最优的并行 系统也被称为pTp最优系统。 开销 在n个处理器的超立方体上完成n个数的加法：开始时，每 个处理器都存放了一个待加的数据，算法结束时，其中的 一个处理器中已经存放了n个数累加的结果。 根据前面的讨论结果，可以知道，在超立方体上完成n个 数的加法的并行算法的处理器-时间积为 ，而串 行运行时间为 ，所以这个并行系统并不是开销最优 的。在计算效率的时候也指出，这个并行系统的效率比1 要低，这也说明这个并行系统并不是开销最优的。 粒度和数据映射 在n个处理器的超立方体结构的并行计算机上完成n个数据累加不是一 个开销最优的并行系统，这个并