阿姆达尔定律的负加速?

Negative speed up in Amdahl's law?

阿姆达尔定律指出整个系统的加速是

an_old_time / a_new_time

其中 a_new_time 可以表示为 ( 1 - f ) + f / s’,其中 f 是通过某些修改增强的系统分数,s’ 是数量通过它增强了系统的那一部分。但是,在对 s’ 求解这个方程后,似乎有很多情况 s’ 是负数,这在物理上没有意义。

假设 s = 2(整个系统的速度提高 100%)和 f = 0.1(系统的 10% 受到一些速度提升的影响 s’ ),我们通过设置 an_old time = 1s’ = f / ( f + 1 / s - 1 ).

求解 s’

插入 fs 的值,我们发现:
s’ = 0.1 / ( 0.1 + 0.5 - 1 ) = 0.1 / -0.4
这意味着 s’值为负。

这怎么可能,这有什么物理意义?另外,在回答此类问题时如何避免负 s’ 值?

Amdahl 定律,也称为 Amdahl 论证,用于在仅改进流程的一部分时找到对整个流程的最大预期改进。


               1                 | where S is the maximum theoretical Speedup achievable
S =  __________________________; |       s is the pure-[SERIAL]-section fraction
                ( 1 - s )        | ( 1 - s )  a True-[PARALLEL]-section fraction
     s    +     _________        |       N is the number of processes doing the [PAR.]-part
                    N            |

由于代数问题,s + ( 1 - s ) == 1< 0.0 .. 1.0 > 中的任何值,这里没有机会获得负值。


Amdahl 论点的完整背景
和当代批评,
添加所有主要内容 add-on 开销 因素
&
更好地处理 atomicity-of-work


常用于领域,预测使用多处理器可达到的理论最大加速比。该定律以 Gene M. AMDAHL 博士(IBM 公司)的名字命名,并于 1967 年在 AFIPS Spring 联合计算机会议上提出。

他的论文是对先前工作的扩展,Amdahl 自己将其引用为“...当前发表的对相关计算机功能最彻底的分析之一 ...”,已发表1966 年 9 月由教授。 Kenneth E. KNIGHT,斯坦福大学工商管理学院。 本文对过程改进保持了总体看法。


图一:

                                                   a SPEEDUP
                                                     BETWEEN
                                                   a <PROCESS_B>-[SEQ.B]-[PAR.B:N]
 [START]                                             and
    [T0]                                  [T0+tsA] a <PROCESS_A>-[SEQ.A]-ONLY
       |                                         |
       v                                         v
       |                                         |
PROCESS:<SEQ.A>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>|
       |                                         |
       +-----------------------------------------+
       |                                         |
    [T0]         [T0+tsB]             [T0+tsB+tpB] 
       |                |                        |   
       v                v                        v
       |________________|R.0: ____.____.____.____|
       |                |R.1? ____.____|         :
       |                |R.2? ____|    :         :
       |                |R.3? ____|    :         :
       |                |R.4?     :    :         :
       |                |R.5?     :    :         :
       |                |R.6?     :    :         :
       |                |R.7?     :    :         :
       |                |         :    :         :
PROCESS:<SEQ.B>>>>>>>>>>|<PAR.B:4>:    :         :
       |                |<PAR.B:2>:>>>>:         :
                        |<PAR.B:1>:>>>>:>>>>>>>>>: ~~ <PAR.B:1> == [SEQ]
                                  :    :         :
                                  :    :         [FINISH] using 1 PAR-RESOURCE
                                  :    [FINISH]        if using 2 PAR-RESOURCEs
                                  [FINISH]             if using 4 PAR-RESOURCEs

( 执行时间从左到右,从[T0] ..到[T0 + ts1 + tp1]
[SEQ]的草图顺序,[PAR] 部分只是为了说明目的而选择,原则上可以相反,因为 process-flow 部分的持续时间排序原则上是可交换的)


{程序的加速|过程 },来自在并行计算中使用多个处理器,被导出为 (可能令听众感到惊讶)主要受限于非常小的部分处理的 non-improved 部分消耗的时间 ,通常是程序处理的顺序部分,仍然以纯粹的 [SERIAL] process-schedulling 方式执行(是它是由于没有被并行化 per-se,或 non-parallelisable 本质上)。

例如,如果一个程序需要使用单个处理器内核运行 20 小时,而程序中需要 1 小时执行的特定部分无法并行化(已在纯 [SERIAL] process-scheduling 方式),而剩余的 19 小时(95%)的执行时间可以并行化(使用 true-[PARALLEL] ( not a "just"-[CONCURRENT] ) process-scheduling ),那么毫无疑问最小可实现的执行时间不能小于那个(第一个)关键一小时,无论有多少处理器专门用于此程序其余部分的并行处理执行。

因此 Speedup 可实现的主要限制为 20 倍,即使 [= 使用了无限数量的处理器也是如此24=]-进程的分数。

See also:

  CRI UNICOS has a useful command amlaw(1) which does simple
  number crunching on Amdahl's Law.
              ------------

On a CRI system type: man amlaw.

                       1         1
     S =  lim    ------------ = ---
          P->oo        1-s       s
                  s +  ---
                        P

 S = speedup which can be achieved with P processors
 s (small sigma) = proportion of a calculation which is serial
 1-s = parallelizable portion

Speedup_overall

= 1 / ( ( 1 - Fraction_enhanced ) + ( Fraction_enhanced / Speedup_enhanced ) )

Articles to parallel@ctc.com (Administrative: bigrigg@ctc.com)
Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel


批评:

虽然 Amdahl 制定了 process-oriented 加速比较,但许多教育工作者不断重复该公式,就好像它是为多处理进程重新安排而假设的,而没有考虑以下主要问题:

  • 处理的原子性(处理的某些部分不可进一步分割,即使更多 processing-resources 可用且免费 process-scheduler -- ref. resources-bound, 进一步不可分割, 原子 processing-section 在上面的图 1 )
  • add-on 开销,主要存在并与任何新进程创建相关联,其调度程序 re-distribution,inter-process 通信,处理结果 re-collection 和 remote-process 资源的释放和终止(它对 N 的比例依赖性尚未得到广泛证实,参考 J. L. Gustafson 博士、Jack Dongarra 等,他们声称方法更好比线性缩放 N )

这组因素都必须纳入 overhead-strict、resources-aware 阿姆达尔定律 re-formulation,如果它应该很好地比较当代 parallel-computing 领域。 overhead-naive 公式的任何形式的使用都会产生教条式的结果,这是迄今为止 Gene M. Amdahl 博士在他的论文(参考上文)中没有提出的,并且将苹果与橙子进行比较从未带来任何积极的结果任何严格领域的任何科学话语。


Overhead-strict re-formulation 阿姆达尔定律加速 S:

               1
S =  __________________________; where s, ( 1 - s ), N were defined above
                ( 1 - s )            pSO:= [PAR]-Setup-Overhead     add-on
     s  + pSO + _________ + pTO      pTO:= [PAR]-Terminate-Overhead add-on
                    N               

Overhead-strict 和 resources-aware re-formulation:

                           1                         where s, ( 1 - s ), N
S =  ______________________________________________ ;      pSO, pTO
                    / ( 1 - s )           \                were defined above
     s  + pSO + max|  _________ , atomicP  |  + pTO        atomicP:= further indivisible duration of atomic-process-block
                    \     N               /

最大有效加速的交互式工具:

由于上述原因,一张图片可能值百万字。尝试 this,其中使用 overhead-strict 阿姆达尔定律的完全交互式工具是 cross-linked。