并行算法第二章 并行计算性能测评

1、1 第二章 并行计算性能测评 2 Questions 1 对自己的计算机(手机)有 没有不满意的地方？ 3 有没有评价是否值得升级？ 2 有没有升过级？ 机器 性能 3 主要内容 1 2 4 3 什么是并行计算机的基本性能？什么是并行计算机的基本性能？ 为什么要研究机器的性能测评？为什么要研究机器的性能测评？ 如何测评计算机的性能？如何测评计算机的性能？ 如何提高并行系统的性能？如何提高并行系统的性能？ 4 计算机的性能 ?Performance: 通常是指机器的速度，它是程 序执行时间的倒数 ?程序执行时间：是指用户的响应时间 (访问磁 盘和访问存储器的时间， CPU 时间， I/O 时 间

2、以及操作系统的开销 ) ?CPU时间：它表示CPU的工作时间，不包括 I/O等待时间和运行其它任务的时间 5 为什么要进行并行机性能评测？ ?对管理人员来说：对管理人员来说： ?发挥并行机长处，提高并行机的使用效率发挥并行机长处，提高并行机的使用效率 ?对用户来说对用户来说 ?减少用户购机盲目性，降低投资风险减少用户购机盲目性，降低投资风险 ?对架构师和设计人员来说：对架构师和设计人员来说： ?改进系统结构设计，提高机器的性能改进系统结构设计，提高机器的性能 ?促进软/硬件结合，合理功能划分硬件结合，合理功能划分 ?优化 “结构结构-算法算法-应用应用”的最佳组合的最佳组合 ?对市场人士来说：

3、对市场人士来说： ?提供客观、公正的评价并行机的标准提供客观、公正的评价并行机的标准 如何进行并行机性能评测 CPU与存储器 并行和通信开销 机器的性价比 Linpack测试标准 机器级性机器级性 能测评能测评 算法级性 能测评 程序级性 能测评 加速比 效率 可扩放性 性能 测评 7 CPU的某些基本性能指标 ? 工作负载工作负载 ?执行时间 ?浮点运算数 ?指令数目 ? 并行执行时间 T comput 为计算时间，T paro 为并行开销 时间，T comm为相互通信时间 T n = T comput + T paro + T comm 8 算法级性能评测 1 加速比性能定律 Amdahl

4、定律 Gustafson定律 Sun和Ni定律 2 可扩放性测评标准 等效率测评标准 等速度测评标准 平均延迟度量标准 9 2.1 加速比定律 ?并行系统的加速比并行系统的加速比:对于一个给定的应用， 并行算并行算 法（或并行程序）的执行速度 相对于串行算法 （或 串行程序）的串行程序）的执行速度加快了多少倍执行速度加快了多少倍 。 ?相关定律： ?Amdahl定律：定律： ?Gustafson定律： ?Sun和Ni定律： 固定计算负载 固定计算时间 受限于存储器 10 一、Amdahl 定律-固定计算负载 ?出发点出发点应用于实时性要求较高的科学计算应用于实时性要求较高的科学计算 ?固定不变

5、的计算负载固定不变的计算负载 ?固定的计算负载分布在多个处理器上的固定的计算负载分布在多个处理器上的 ?增加处理器加快执行速度，从而达到了加速的增加处理器加快执行速度，从而达到了加速的 目的目的 11 1.相关参数 ? P：处理器数 ? W：问题规模（计算负载、工作负载，给定问题的总计算量） ?Ws：应用程序中的串行分量，f是串行分量比例（f = Ws/W， W s=W1 ） ?WP：应用程序中可并行化部分，1-f 为并行分量比例 ?Ws+W p=W ? Ts=T 1 ：串行执行时间，Tp ：并行执行时间； ? S：加速比，E：效率； 12 2.加速比公式 ?固定负载的加速公式：固定负载的加速

6、公式： ?W s+ W p可相应地表示为 可相应地表示为f+（1-f ） ?p时，上式极限为：时，上式极限为： S= 1 / f pWWs WpWs S P /? ? ? )1(1 1 )1( ? ? ? ? ? ? pf p p f f ff S 并行系统所能达到的 加速比上限为1/f，在 历史上起悲观的作用。 13 3.Amdahl定律的几何意义 不论PE个数有多 少，可并行计算量 是不变的。 14 Amdahl定律的几何意义 随着随着PE的增大，Tp可能可能 会越来越小，但T1不会 改变 15 Amdahl定律的几何意义 16 4. 修改后的加速比考虑额外开销 ? W o为额外开销 ?

7、p时，上式极限为时，上式极限为 ? 串行分量和并行额外开销的比例越大，则加速比越小。 WpWpf p W p fW fW W W p W W WW S P S PS /) 1(1 )1 ( 0 00 ? ? ? ? ? ? ? ? ? wwf S / 1 0 ? ? 17 例题 在不考虑通信开销的情况下，若达到（不小于） 50%的加速效率（加速比与 p的比值），串行 计算部分f和所使用的处理器数目 p之间应该存 在怎么样的不等式关系？ 若 f=0.5, 则p只能取多少？ 18 二、Gustafson定律 ? 出发点：出发点： ?对于很多大型计算，对于很多大型计算，精度要求很高，即在此类应用，即

8、在此类应用 中精度是个关键因素，而计算时间是固定不变的。 此时为了提高精度，必须此时为了提高精度，必须加大计算量，相应地亦必 须增多处理器数须增多处理器数才能维持时间不变； ?除非学术研究，在实际应用中没有必要固定工作负 载而计算程序运行在不同数目的处理器上，增多处增多处 理器必须相应地增大问题规模才有实际意义。 19 1. 加速比公式 ?Gustafson加速定律 : ?说明： ?当f很小时，S与P斜率为1-f ?当p 时，S随着PE的增加而增加，几乎与 处理器数成比例的线性增加 ，f不再是程序的 瓶颈 PS S S S WW pWpW pWppW pWpW S ? ? ? ? ? ? /

9、f -f) p (S ?1 20 2. Gustafson定律几何意义 处理器的增多，是为了 增加计算量，将同等大 小问题在各PE上求解 21 增加增加PE的同时，问题规的同时，问题规 模也增大，所以TP不变 2. Gustafson定律几何意义 22 2. Gustafson定律几何意义 23 3. 修改后的加速比 ?并行开销W o ： ?注意： ?W0是P的函数，可能随着P增大、减小或不变 ?要达到线性加速，必须使 W0随P减少，但一般 比较困难 ? WW fpf WWW pWW S OOPS PS /1 1 ? ? ? ? ? ? 24 三、Sun 和 Ni定律 ?Xian-He Sun

10、和和Lionel Ni于于1993将将Amdahl定定 律和律和Gustafson定律一般化，提出了定律一般化，提出了 存储受限存储受限的的 加速定律。加速定律。 25 Sun 和 Ni定律 ? 基本思想： ?只要存储空间许可，应尽量增大问题规模以产生更好和 更精确的解（此时可能使执行时间略有增加）。 ?假定在单节点上使用了全部存储容量M并在相应于W的 时间内求解之，此时工作负载W= fW + （1-f ）W。 ?在p 个节点的并行系统上，能够求解较大规模的问题是 因为存储容量可增加到pM。令因子G（p）反应存储容 量增加到p倍时并行工作负载的增加量，所以扩大后的 工作负载W = fW + （

11、1-f ）G（p）W。 26 1. 加速比公式 ?G（p）：存储容量增加到p倍时并行工作负载的增加 情况 ?扩大存储容量后的工作负载 W =fw+(1-f)G(p)W ? ? ? ? ? ?pWpGffW WpGffW S /1 1 ? ? ? ? ? ? ? ? ?ppGff pGff /1 1 ? ? ? 27 Sun 和 Ni定律 ? G（p）=1 时； ? G（p）=p 时： ? G（p）p 时：计算机负载比存储要求增加得快，此时 Sun 和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高。 ? ? ? ? ? ?ppGff pGff S /1 1 ? ? ? ?

12、pff SS /1 1 ? ? -Amdahl 加速定律 )1 ( fpfSS?- Gustafson 加速定律 28 Sun 和 Ni定律 29 Sun 和 Ni定律 30 修改后的加速比 ?并行开销并行开销W o: ? ? ? ? ? ? ? ? ? ? ? ?WWppGff pGff WpWpGffW pWGffW S OO /1 1 /1 1 ? ? ? ? ? ? 31 四、加速比讨论 ? 参考的加速经验公式： p/log pSP ?线性加速比：很少通信开销的矩阵相加、内积运算等 ?p/log p的加速比：分治类的应用问题 ? 通信密集类的应用问题 ：S = 1 / C （ p ）

13、? 超线性加速 ：SP ? 绝对加速：最佳并行算法与串行算法 ? 相对加速：同一算法在单机和并行机的运行时间 科学研究 者使用 工程实用者 32 2.2 可扩放性评测标准 ?并行计算的可扩放性（ Scalability ） 评价并行计算性能的又一指标 计算机系统（或算法或程序等）性能随处理 器数的增加而按比例提高的能力 反映并行算法能否有效利用可扩充 PE数的能 力 33 一、并行计算的可扩放性 ?加速比：加速比：由由3个定律可知，增加个定律可知，增加PE和求解问题的和求解问题的 规模可以提高加速比 ?影响加速比的因素：处理器数与问题规模影响加速比的因素：处理器数与问题规模 ?求解问题中的串行

14、分量 ?并行处理所引起的 额外开销（通信、等待、 竞争、冗余操作和同步等） ?加大的处理器数超过了算法中的 并发程度 34 一、并行计算的可扩放性 ?增加规模有利于提高加速比的因素：增加规模有利于提高加速比的因素： ?较大的问题规模可以 提高较高的并发度 ?额外开销的增加可能 慢于有效计算的增加 ?算法中的串行分量比例不是固定不变 的（因 问题规模增加而缩小） 35 可扩放性评测标准 ?增加处理器数，会增大额外开销和降低处理器增加处理器数，会增大额外开销和降低处理器 利用率，所以对于一个特定的并行系统（算法利用率，所以对于一个特定的并行系统（算法 或程序），它们或程序），它们能否有效利用不断增

15、加的处理能否有效利用不断增加的处理 器的能力应是受限的器的能力应是受限的 ，而度量这种能力就是，而度量这种能力就是 可 扩放性这一指标。这一指标。 36 1.可扩放性的内涵 ?可扩放性:调整什么和按什么比例调整调整什么和按什么比例调整 ?并行计算要调整的是 处理数p和问题规模W ?两者可按不同比例进行调整，此比例关系两者可按不同比例进行调整，此比例关系 （可能是线性的，多项式的或指数的等）就 反映了可扩放的程度 37 可扩放性评测标准 ? 可扩放性研究的主要目的：可扩放性研究的主要目的： ?确定解决某类问题用何种并行算法与何种并行体系 结构的组合，可以有效地利用大量的处理器； ?对于运行于某种

16、体系结构的并行机上的某种算法当 移植到大规模处理机上后运行的性能； ?对固定的问题规模，确定在某类并行机上最优的处 理器数与可获得的最大的加速比； ?用于指导改进并行算法和并行机体系结构，以使并 行算法尽可能地充分利用可扩充的大量处理器。 38 2.2.1 等效率度量标准 ? 令tie ：并行系统上第i个处理器的有用计算时间 ? t io：第i个处理器的额外开销时间（包括通信、同步和空 闲等待时间等） ? T p ：p个处理器系统上并行算法的运行时间 ? W：串行算法所完成的计算量 ? 对于任意i，显然有T p = tie + t io ，且 T e+ T o= pT p ? 问题的规模W为最

17、佳串行算法所完成的计算量W=Te ? ? ? ? 1 0 p i i ee tT ? ? ? ? 1 0 p i i oo tT 39 等效率度量标准 W T p T T p p TT T T T S o e ooe e p e ? ? ? ? ? ? 11 W T T T P S E o e o ? ? ? ? 1 1 1 1 ?说明： ?如果问题规模W 保持不变，处理器数p增加，开 销To增大，效率E下降。 ?为了维持一定的效率（介于 0与1之间），当处理 数p增大时，需要相应地增大问题规模 W的值。 W随P按什么比例 增加 40 等效率度量标准 ?曲线1表示算法具有很好的扩放性； ?曲线

18、2表示算法是可扩放的； ?曲线 3表示算法是不可扩放的。 处理器数 P 工 作 负 载 W 曲线 3 曲线 2 曲线 1 41 等效率度量标准 ?优点：通过少量的参数可计算出等效率函数 ?缺点：如果To无法计算出（在共享存储并行机中） 42 2.2.2 等速度度量标准 ?等效率度量标准的缺点等效率度量标准的缺点 ：T0不能方便地计算出来 ?1994 年两位学者提出试验测试为主要手段的两种 标准：等速度、平均延迟等速度、平均延迟 43 为什么用等速度度量标准为什么用等速度度量标准 ? 速度是一个重要的参数，一般可以明确指出，单位 Mflops，因此用速度来度量可扩放性，应更加方便。 ? 在并行系统中，增加P可以提高速度，如果速度能随着 P的增加而增加，即意味着平均速度不变 ? p个处理器的并行系统的平均速度定义为并行速度V除 以处理器个数 p： 44 等速度度量标准等速度度量标准 ?p 表示处理器个数 ?W表示要求解问题的工作量或称问题规模（在 此可指浮点操作个数） ?T为并行执行时间 ?并行计算的速度V: V=W/T ?p个处理器的并行系统的 平均速度 定义为: pT W p V V? V 45 等速度度量标准等速度度量标准 ? W是使用p个处理器时算法的工作量，令W表示当处理 数从p增大到p时，为了保持整个系统的平均速度不变 所需执行的工作量，则可得