并行计算性能分析

并行计算性能的预测公式有：Amdahl定律、Gustafson-Barsis定律、Karp-Flatt度量以及等效加速比度量。以下公式中$\psi (n,p)$表示在p个处理器上解决问题为n规模问题的加速比，$\sigma (n)$表示计算中内在的串行部分，$\phi (n)$表示可以并行执行的计算，$\kappa (n,p)$表示并行计算开销所需的时间。加速比的表达式为：
ψ ( n , p ) ≤ σ ( n ) + φ ( n ) σ ( n ) + φ ( n ) / p + κ ( n , p ) \psi(n,p)\le \frac{\sigma(n)+\varphi(n)}{\sigma(n)+\varphi(n)/p+\kappa(n,p)} ψ(n,p)≤σ(n)+φ(n)/p+κ(n,p)σ(n)+φ(n)​
并行计算效率的定义为：
ε ( n , p ) ≤ σ ( n ) + φ ( n ) p σ ( n ) + φ ( n ) + p κ ( n , p ) \varepsilon(n,p) \le \frac{\sigma(n)+\varphi(n)}{p\sigma(n)+\varphi(n)+p\kappa(n,p)} ε(n,p)≤pσ(n)+φ(n)+pκ(n,p)σ(n)+φ(n)​
由于所有项都大于或等于0，所以$0\le \epsilon (n,p)\le 1$

1. Amdahl定律

• Amdahl定律
  f为计算中必须串行执行的部分所占的比例，$0\le f\le 1$。那么计算在p个处理器的并行计算上所达到的最大加速比为：
  ψ ≤ 1 f + ( 1 − f ) / p \psi\le \frac{1}{f+(1-f)/p} ψ≤f+(1−f)/p1​
• Amdahl 效应
  通常$\kappa (n,p)$比$\phi (n)$复杂度要低，对我们刚才所考虑的假象问题来说就是这样： κ ( n , p ) = Θ ( n l o g n + n l o g p ) , φ ( n ) = Θ ( n 2 ) \kappa(n,p)=\Theta(n log^n+nlog^p),\varphi(n)=\Theta (n^2) κ(n,p)=Θ(nlogn+nlogp),φ(n)=Θ(n2)。问题规模增加时计算时间的增长比通信时间要快。因此，对于固定数目的处理器来说，加速比往往是问题规模的增函数。这称为Amdahl效应。

2. Gustafson-Barsis定律

• Gustafson-Barsis定律
  给定一个并行程序在p个处理器上解决问题规模为n的问题，让s表示在总执行时间中串行代码的比例，则此程序可达到的最大加速比$\psi$为：
  $$\psi \le p+(1-p)s$$

3.Karp-Flatt度量

• Karp-Flatt度量
  给定一个在p个处理器上展示了加速比$\psi$的并行计算，其中$p>1$，那么实验确定的串行比例$e$定义为：
  e = 1 / ψ − 1 / p 1 − 1 / p e=\frac{1/\psi-1/p}{1-1/p} e=1−1/p1/ψ−1/p​

4.等效指标

• 等效关系
  假定一个并行系统具有效率$\epsilon (n,p)$，定义$C=\epsilon (n,p)/(1-\epsilon (n,p))$，并且 T 0 ( n , p ) = ( p − 1 ) σ ( n ) + p κ ( n . p ) T_0(n,p)=(p-1)\sigma(n)+p\kappa(n.p) T0​(n,p)=(p−1)σ(n)+pκ(n.p)。为了在处理器个数增加的情况下维持效率不变，n必须增加使下面的不等式成立：
  T ( n , 1 ) ≤ C T 0 ( n , p ) T(n,1)\le CT_0(n,p) T(n,1)≤CT0​(n,p)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！