并行计算基本概念

78 阅读 0 评论 52 点赞

我是靠谱客的博主典雅老师，最近开发中收集的这篇文章主要介绍并行计算基本概念，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

并行计算基本概念

加速比

绝对加速比
$S_N=frac{最优串行算法单机运行时间}{并行算法在N台处理机上运行的时间}$
相对加速比
$S_N=frac{并行算法在单机上运行的时间}{并行算法在N台处理机上运行的时间}$

Amdahl定律
$s=frac{W_s+W_p}{W_s+W_p/p}$
同时除以 $W=W_s+W_p$
$s = 1 f + ( 1 − f ) / p = P 1 + f ( p − 1 ) s=frac{1}{f+(1-f)/p}=frac{P}{1+f(p-1)}$
则
$limlimits_{prightarrowinfty}Srightarrow1/f$
该公式没有考虑并行计算引起的通信和额外的计算开销，但是仍然可以说明问题

考虑额外开销过后
$S=frac{W_s+W_p}{W_s+W_p/p+W_o}=frac{W}{fW+frac{W(1-f)}{p}+W_o} =frac{p}{1+f(p-1)+frac{W_op}{W}}$

$limlimits_{prightarrowinfty}S=frac{1}{f+frac{W_o}{W}}$

如果额外开销过大，还有可能造成“反向加速”

Gustafson定律(假设问题随规模的增大，并行部分增加)
$S^‘=frac{W_s+pW_p}{W_s+pW_p/p}=frac{W_s+pW_p}{W_s+W_p}=f+p(1-f)=p-f(p-1)$
这样最大加速比就不仅仅取决于串行部分

考虑额外开销
$S^‘=frac{W_s+pW_p}{W_s+W_p+W_o}=frac{f+p(1-f)}{1+W_o/W}$
$W_o$ 是p的函数，它可能会随着p的改变而改变。要到达一般化的Gustafson定律所描述的线性加速比，当p改变时，必须要控制额外开销的增长，这在实际中往往是非常困难的。