并行计算 第四章复习提纲

并行算法性能解析基础

并行算法的执行时间不仅依赖于输入数据大小，还依赖于所用的处理器的数目，及它们相关的计算速度和进程间的通信速度

开销类型

• 进程间通信：并行系统中 进程之间的通信，通常是并行程序开销的 最重要来源。
• 空闲时间：由于负载不平衡、同步问题或执行串行部分程序造成的空闲时间。
• 额外计算：在某些情况下，最优的串行算法可能无法并行化，这时我们需要使用较慢但容易并行化的算法，从而带来额外的计算开销。

性能评估指标

• 执行时间: 从程序开始到结束所使用的时间
• 总并行开销: 所有处理器使用的总时间
• 加速比: 在单个处理器上求解问题所花的最短时间与用p个相同处理器并行计算机求解同一问题所花时间之比。

加速比上限

理论上，加速比不可能超过处理器数p

如果超出,则称为 超线性加速比

通常在 串行算法执行的任务大于并行形式，或由于 硬件特性使得任务不适合用串行实现 时发生。

高速缓存以及搜索分解都存在超线性效果

效率

加速比与处理器数目的比率，即E= S/p。E的理想值应该小于等于1

当给定处理器数目p后，加速性能随着任务数n增加而下降！

粒度对于性能的影响

有的时候使用更少的处理器可以提高并行系统的性能

如果使用少于最大可用处理器数量来执行一个并行算法的方法被称为按处理器数目***缩小（scaling down）***一个并行系统

Scaling down的方法

将原始情况下的每个处理器视为一个虚拟处理器，并将虚拟处理器平等地分配给缩减后的处理器。

可拓展性

具备同时增加处理器数目和问题规模来保持效率为固定值的特性的系统称为 可扩展并行系统

并行系统的可扩展性是与处理器数目成比例增加加速比能力的度量，它反映一个并行系统有效利用（可变数量的）处理资源的能力。

对于给定的问题规模，当增加处理器数目时并行系统的总效率下降。这种现象在所有并行系统是常见的。

在很多情况下，如果问题规模增加而处理器数目不变，并行系统的效率增加。