加速比

(重定向自加速倍率

并行计算领域,加速比用于表示当并行算法与对应的顺序执行算法相比较时,速度快了多少。

定义

编辑

加速比以如下公式定义:

 

其中:

  •  指CPU数量
  •  指顺序执行算法的执行时间
  •  指当有p个处理器时,并行算法的执行时间

 时, 便可称为“线性加速比”(英语:linear speedup,又名“理想加速比”)。当某一并行算法的加速比为理想加速比时,若将处理器数量加倍,执行速度也会加倍,即如“理想”之意,有“优秀的可扩展性”。

“效率”

编辑

由加速比派生出的效率(英语:efficiency)则是量度性能的指标,并如下定义:

 .

效率 的值一般介于0~1之间,用于表示在解决问题时,相较于在通信与同步上的花费,参与计算的处理器得到了什么程度的充分利用。由定义易见,拥有线性加速比的算法与在单处理器上执行的算法的效率为1。

超线性加速比

编辑

并行计算过程中,有时会遇到加速比 比处理器数 更大的情况,此时求得的加速比即称超线性加速比(英语:superlinear speedup)。超线性加速比很少出现,且由于初学者常以为理论上加速比的最大值应与参与计算的处理器的总数 相等,这一情况常使初学者迷惑不已。

超线性加速比有几种可能的成因,如现代计算机的存储层次不同所带来的“高速缓存效应”;具体来说,较之顺序计算,在并行计算中,不仅参与计算的处理器数量更多,不同处理器的高速缓存也集合使用。而有鉴于此,集合的缓存便足以提供计算所需的存储量,算法执行时便不必使用速度较慢的内存,因而存储器读些时间便能大幅降低,这便对实际计算产生了额外的加速效果[1]

参考资料

编辑
  1. ^ John Benzi; M. Damodaran. Parallel Three Dimensional Direct Simulation Monte Carlo for Simulating Micro Flows. Parallel Computational Fluid Dynamics 2007: Implementations and Experiences on Large Scale and Grid Computing. Parallel Computational Fluid Dynamics. Springer: 95. 2007 [2013-03-21]. 
  • Frank Dehne. Scalable Parellel Computational Geometry. Michel Cosnard, Afonso Ferreira, Joseph Peters (编). Parallel and Distributed Computing. Springer. 1994-06-10 [2013-03-20].