并行计算
1 并行系统的性能分析
并行系统的性能分析
• 一个串行程序的性能通常用它的运行时间来衡量，表达为 它的输入规模（问题规模）的函数。而并行算法的执行时 间不仅与问题的规模有关，还与并行计算机的体系结构和 处理器的数目直接相关，因此，对并行算法性能的评价不 能脱离具体的并行体系结构。一个并行系统是并行算法以 及实现这个算法的并行体系结构的组合体。
运行时间
• 一个程序的串行运行时间是程序在一个串行计算机上开始 执行到执行完成之间所经过的时间段的长度。 • 并行运行时间则定义为并行计算开始到最后一个处理器完 成它的计算任务之间的时间段的长度。 • 定义Ts为串行部分的执行时间，Tp为并行部分的执行时 间
加速比
• 在评价一个并行系统时，人们通常关心的是对一个给定的 应用，它的并行化版本比串行实现有多大的性能提高。加 速比就是一个衡量并行解题过程中的相对收益的指 标。 简单的讲，并行系统的加速比是指对于一个给定的应用， 并行算法（或并行程序）的执行速度相对于串行算法（或 者串行程序）的执行速度加快了多少倍。
Sun和Ni定律
• Xian-He Sun和Lionel Ni于1993年曾将Amdahl和Gustafson定律一般 化，提出了存储受限的加速定律。他们的基本思想是：只要存储空间 许可，应该尽量增大问题规模以产生更好或更精确的解（执行时间可 能略有增加）。换句话说，假如有足够的存储容量，并且规模可扩展 的问题满足Gustafson定律规定的时间要求，那么 就有可能进一步增 大问题规模求得更好或更精确的解。
Amdahl定律
Amdahl定律
• 当处理器数目n=1024，加速比公式如下，
• Sn随α变化的情况如下图：
Amdahl定律
• 实际上并行加速比不仅受限于程序的串行分量的比例，而且也受并行 程序运行时的额外开销的影响。如果考虑到这部分因素的影响，令 Wo为额外开销，那么上面的公式应该修改为：
• 这种情形下的加速比极限为：
Gustafson定律
• 变问题规模的加速比模型：
• 当p充分大时，S'与p几乎成线性关系，其斜率为1-f，这就 是Gustafson加速比定律，它意味着随着处理器数目的增 加，加速比几乎与处理器数 目成比例的线性增加，串行 比例f不再是程序的瓶颈，这为并行计算系统的发展带来 了非常乐观的结论。
Gustafson定律
• 结论：并行程序中的串行分量比例和并行额外开销越大，则加速比越 小。
Gustafson定律
• Gustafson定律的基本出发点是： (1) 对于很多大型计算，精度要求很高，即在此类应用中精度是一个 关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大 计算量，相应的也必须增加处理器的数目来完成这部分计算，以保持 计算时间不变； (2) 除非学术研究，在实际应用中没有必要固定工作负载而使计算程 序运行在不同数目的处理器上，增多处理器必须相应的增大问题规模 才有实际的意义。因此研究在给 定的时间内用不同数目的处理器能够 完成多大的计算量是并行计算中一个很实际的问题。 (3) 对大多数问题，问题规模的改变只会改变计算中并行计算量，而 不会改变串行计算量。 • 从这些动机出发，Gustafson在1987年提出了变问题规模的加速比模 型：
加速比
• 通常由三种加速比性能定律：适用于固定计算负载的Amdahl定律， 适用于可扩展性问题的Gustafson定律和受限于存储器的Sun和Ni定律。 • 为讨论方便，定义以下的参数： – p是并行系统中处理器的数目； – W是问题规模（也常常叫做计算负载、工作负载，它定义为给定 问题的总计算量），Ws是应用程序中的串行分量，W中可并行化 部分为Wp ； – f是串行分量的比例，即f = Ws / W ，则1 - f 为并行分量的比例；
• Gustafson定律的几何意义可以清楚的用下面的图来表示：
Gustafson定律
• 当处理器数目n=1024，加速比Sn随α变化的情况如下： • 可以用图表示如下：
Gustafson定律
• 同样的，当考虑到并行程序运行时的额外开销时，Gustafson定律应 该修改为：
• 注意：Wo是p的函数，它可能会随着p的改变而改变。要到达一般化 的Gustafson定律所描述的线性加速比，当p改变时，必须要控制额外 开销的增长，这在实际中往往是非常困难的。
– Ts 为串行部分的执行时间，Tp 为并行部分的执行时间；
– S为加速比， – E为效率。
Amdahl定律
• Amdahl定律的基本出发点是： (1) 对于许多科学计算，实时性要求很高，即在这类应用中计算时间是个 关键性因素，而计算负载是固定不变的。为此，在一定的计算负载下，为满 足实时性的要求，可以通过增加处理器数目的方法来减少运行时间，提高计 算速度； (2) 因为固定的计算负载可以分布在多个处理器上，这样增加了处理器就 加快了执行速度，从而达到了加速的目的。 • 在这样的动机推动下，1967年Amdahl推导出了固定负载情况下的加速比公式：
Sun和Ni定律
• 给定一个存储受限问题，假定在单节点上使用了全部存储容量M并在 相应于W的计算时间内求解，此时工作负载W=fW+(1-f)W。在p个节 点的并行系统 上，能够求解较大规模的问题是因为存储容量可以增加 到pM。用因子G(p)来反映存储容量增加p倍时工作负载的增加量，所 以增加后的工作负载W=fW+ (1-f)G(p)W。那么，存储受限的加速比 公式为：
Amdahl定律
• 固定负载情况下的加速比公式：
• 由于W=Ws + Wp，上式右边分子分ቤተ መጻሕፍቲ ባይዱ同除以W，则有
• 当
时，加速比的极限为
Amdahl定律
• 这就是著名的Amdahl加速定律，它意味着随着处理器数目的无限增 大，并行系统所能达到的加速比存在上限，且为一个常数1/f，这个常 数只取决于应用本 身的性质。 • 这个结论在历史上曾经对并行系统的发展带来了一种悲观的影响。它 带来的两种影响是，一是劝阻并行计算机厂商生产更大规模的并行计 算机，二是促进 了并行编译计算的发展，以降低程序中串行部分的值。 • Amdahl定律的几何意义可以清楚的用下面的图来表示：