并行计算

两学分的水课…

[课程主页]:Parallel computing - structures, algorithms, programming

并行计算结构

将并行计算结构抽象为图，节点为计算节点，不同的结构有着不同的通信复杂度。

• 一维线性阵列：对剖宽度为2（对剖宽度是将一个并行结构拆分为两个大小接近的部分所切断最小的链路；sparest cut！我草）
• 二维网孔结构：
• 二叉树：会在根节点产生通信阻塞
• Fat-tree:胖树

嵌入

并行计算性能评测

并行计算时间开销，三项时间分别表示为计算开销，并行开销（进程调度），通信开销。

测量点到点的通信开销：节点0发送m比特到节点1，节点1收到后迅速发回给节点0，节点0收到后计算时间差/2，为通信开销。

通信开销函数：,m为消息的长度，表示渐进带宽（消息无限长时的通信速率，单位为比特/秒）

半峰值长度：表示接近一半渐近带宽时的消息长度；特定性能表示短消息带宽

解得

加速比性能定律

Amdahl定律

适用于固定负载（总计算量）为的情况下，其中串行计算部分为,并行计算部分为

加速比记为：

当趋近于正无穷时，加速比趋近于

引入为额外开销，则加速比趋近于,所以当并行计算的比例更大时，加速比更大。

Gustafuson定律

该定律的出发点是：必须加大处理器的数量从而提高精度，但是整体计算时间保持不变

Sun和Ni定律

只要存储空间许可，尽可能增大问题的规模从而求得更精确的解。用反应存储量增加倍后负载的增加，那么加速比可以表示为

当，则退化为Amdahl定律，若，则退化为Gustafuson定律。

可扩放性评测标准

可扩放性表示：随着处理器增加，程序速度的提升的程度（如果一个程序只能串行那么没有任何前途。。。）

研究可扩放性：问题规模+算法+计算体系结构

等效率度量标准

设为第个处理器上的有用计算时间和额外开销时间，,即为是串行计算的计算量，令记为个处理器上并行算法的运行时间，对于任意显然有，显然

则加速记为

效率记为

因此为了维持一定的效率，在增加处理器数量的时候伴随着计算额外开销的增加，需要增加问题的规模。

等速度衡量标准

处理器数量为,为问题的工作量，表示并行执行时间，则并行计算的速度,个处理器的平均速度为。