如何计算两种算法之间的并行加速比

Question

假设我有算法 1 和 2，它们的顺序执行时间为 ts1 和 ts2。 它们的并行执行时间为 TP1 和 TP2。

现在，在计算两种算法的速度时，以下哪项是正确的？

• 用于算法 1 的最小值(TS1，TS2(/TP1
• 算法 2 的最小值(TS1，TS2(/TP2

或

• 用于算法 1 的 TS1/TP1
• 用于算法 2 的 TS2/TP2

换句话说，对于分子，我应该使用最佳顺序时间还是它们自己的顺序时间？

Answer 1

简短版本：

以上都不是

---

图1：

a SPEEDUP
BETWEEN
a BLACK-BOX <PROCESS_2>
[START]                                             and
+-----------------------------------------+ a BLACK-BOX <PROCESS_1>
|                                         |
[T0]         [T0+ts1]             [T0+ts1+tp1] 
|                |                        |   
|                |                        |   
v                v                        v
|________________|R.0: ____.____.____.____| ~~ <PAR.1:1> == [SEQ]
|                |R.1? ____.____|         :
|                |R.2? ____|    :         :
|                |R.3? ____|    :         :
|                |         :    :         :
|<SEQ.1>>>>>>>>>>|         :    :         :
|                |<PAR.1:N>:    :         :
|         :    :         :
:    :         :
:    :         [FINISH] using 1 PAR-RESOURCE
:    [FINISH]        if using 2 PAR-RESOURCEs
[FINISH]             if using 4 PAR-RESOURCEs

_{(执行时间从左到右，从[T0]..到[T0 + ts1 + tp1]。[SEQ]的草图顺序，[PAR]部分在这里只是为了说明目的而选择的，可以相反，因为工艺流部分的持续时间顺序原则上是可交换的(}

---

一 TL;博士;版本：

对上述[SEQ]+[PAR]流程进行一些正式简化可能有助于回答和理解原因。

不用告诉任何HPC规划者，阿姆达尔定律规则(如果Amdahl的扩展形式更好，则使用开销+原子感知公式(。

我们看到，R.iPROCESS_1[PAR]部分使用的资源越多，tp1可能越短。这是[PAR]处理的强大功能。

给定一对元组( ts1, tp1 )和( ts2, tp2 )，没有人可以假设任何潜在的阿姆达尔定律 - 资源驱动(如图1所示( - 加速，但如果人们努力比较两个假设的实现，具有可能不同的内部处理，可能的加速S可以表述为：

max( [ ts1 + tp1 ], [ ts2, tp2 ] )
S =  ______________________________________
min( [ ts1 + tp1 ], [ ts2, tp2 ] )

Answer 2

你的问题有一个基本问题。这就是你被困住的原因。问题是加速是为处理器定义的，而不是算法。

在计算机体系结构中，加速是提高处理相同问题的两个系统之间的性能的过程。从技术上讲，它是在具有不同资源的两种类似架构上执行的任务的执行速度的提高。

^{定义取自维基百科。}