阿姆达尔定律中的负加速? [英] Negative speed up in Amdahl's law?

问题描述

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

Amdahl’s law states that a speed up of the entire system is

an_old_time / a_new_time

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

where the a_new_time can be represented as ( 1 - f ) + f / s’, where f is the fraction of the system that is enhanced by some modification, and s’ is the amount by which that fraction of the system is enhanced. However, after solving this equation for s’, it seems like there are many cases in which s’ is negative, which makes no physical sense.

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

Taking the case that s = 2 (a 100% increase in the speed for entire system) and f = 0.1 (a 10% of the system is impacted by some speed enhancement s’), we solve for s’ by setting an_old time = 1 and s’ = f / ( f + 1 / s - 1 ).

插入 f 和 s 的值，我们发现:
s' = 0.1/( 0.1 + 0.5 - 1 ) = 0.1/-0.4
表示s'值为负.

Plugging on the values for f and s, we find that :
s’ = 0.1 / ( 0.1 + 0.5 - 1 ) = 0.1 / -0.4
which means that the s’ value is negative.

这怎么可能，它的物理意义是什么?另外，在回答此类问题时如何避免负 s' 值?

How can this be possible, and what is the physical meaning of this? Also, how can I avoid negative s’ values when answering questions like these?

推荐答案

Amdahl's Law，也称为 Amdahl's 论证，用于在仅改进过程的一部分时找到对整个过程的最大预期改进.

Amdahl's Law, also known as Amdahl's argument, is used to find the maximum expected improvement to an overall process when only a part of the process is improved.

>

---

Due to the algebra, the s + ( 1 - s ) == 1, s being anything from < 0.0 .. 1.0 >, there is no chance to get negative values here.

由于代数的原因，s + ( 1 - s ) == 1, s 是来自 < 的任何东西.0.0 .. 1.0 >，这里没有机会得到负值.

It is often applied in the field of parallel-computing to predict the theoretical maximum speedup achievable by using multiple processors. The law is named after Dr. Gene M. AMDAHL ( IBM Corporation ) and was presented at the AFIPS Spring Joint Computer Conference in 1967.

常应用于论文对过程改进保持了总体看法.

His paper was extending a prior work, cited by Amdahl himself as "... one of the most thorough analyses of relative computer capabilities currently published ...", published in 1966/Sep by prof. Kenneth E. KNIGHT, Stanford School of Business Administration. The paper keeps a general view on process improvement.

                                                   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] 部分的选择只是为了说明目的，原则上可以相反，因为流程部分的持续时间顺序是可交换的原则)}

_{( Execution time flows from left to right, from [T0] .. to [T0 + ts1 + tp1].
The sketched order of [SEQ], [PAR] sections was chosen just for illustrative purpose here, can be opposite, in principle, as the process-flow sections' durations ordering is commutative in principle )}

{ 程序的加速 |进程}，来自在并行计算中使用多个处理器，被推导出为(可能让观众感到惊讶)主要受限于消耗的时间的一小部分对于处理的非改进部分，通常是程序处理的顺序部分，仍然以纯 [SERIAL] 进程调度方式执行(可能是由于未并行化本身，或本质上不可并行).

The speedup of a { program | process }, coming from using multiple processors in parallel computing, was derived to be ( maybe to a surprise of audience ) principally limited by the very fraction of time, that was consumed for the non-improved part of the processing, typically the sequential fraction of the program processing, executed still in a pure [SERIAL] process-schedulling manner ( be it due to not being parallelised per-se, or non-parallelisable by nature ).

例如，如果一个程序需要 20 个小时使用单个处理器内核，并且程序中需要一个小时才能执行的特定部分无法并行化(已在纯[SERIAL] 进程调度方式)，而剩余的 19 小时(95%)的执行时间可以并行化(使用真正的-[PARALLEL](不是一个只是"-[CONCURRENT])进程调度)，那么不可能达到的最小执行时间不能小于(首先) 关键的一小时，无论有多少处理器专门用于该程序其余部分的并行进程执行.

For example, if a program needs 20 hours using a single processor core, and a particular portion of the program which takes one hour to execute cannot be parallelized ( having been processed in a pure-[SERIAL] process-scheduling manner ) , while the remaining 19 hours (95%) of execution time can be parallelized ( using a true-[PARALLEL] ( not a "just"-[CONCURRENT] ) process-scheduling ), then out of the question the minimum achievable execution time cannot be less than that ( first ) critical one hour, regardless of how many processors are devoted to a parallelized process execution of the rest of this program.

因此，即使 [PARALLEL] 使用了无限数量的处理器，可实现的 Speedup 主要限制在 20 倍以内-过程的一部分.

Hence the Speedup achievable is principally limited up to 20x, even if an infinite amount of processors would have been used for the [PARALLEL]-fraction of the process.

另见:

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

在 CRI 系统类型上:man amlaw.

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 ) )

文章到[e-mail](管理员:[e-mail])
存档:http://www.hensa.ac.uk/parallel/互联网/usenet/comp.parallel

Articles to [e-mail] (Administrative: [e-mail])
Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel

---

批评:

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

---

Criticism:

While Amdahl has formulated process-oriented speedup comparison, many educators keep repeating the formula, as if it were postulated for the multiprocessing process rearrangement, without taking into account also the following cardinal issues:

• 处理的原子性(处理的某些部分不能进一步分割，即使有更多处理资源可用并且对流程调度程序免费——参考资源绑定，进一步不可分割，上面图1中的原子处理部分)
• 附加开销，主要存在并与任何新进程创建、调度程序重新分配、进程间通信、处理结果重新收集和远程进程资源释放相关联和终止(它对 N 的比例依赖性尚未得到广泛证实，参考 JL Gustafson 博士、Jack Dongarra 等人声称在 N 中具有优于线性缩放的方法)

• atomicity of processing ( some parts of the processing are not further divisible, even if more processing-resources are available and free to the process-scheduler -- ref. the resources-bound, further indivisible, atomic processing-section in Fig. 1 above )
• add-on overheads, that are principally present and associated with any new process creation, scheduler re-distribution thereof, inter-process communication, processing results re-collection and remote-process resources' release and termination ( it's proportional dependence on N is not widely confirmed, ref. Dr. J. L. Gustafson, Jack Dongarra, et el, who claimed approaches with better than linear scaling in N )

如果在当代并行计算领域将苹果与苹果进行比较，这两组因素都必须纳入开销严格、资源感知型的阿姆达尔定律重新制定.任何类型的开销天真公式的使用都会导致教条式的结果，到目前为止，Gene M. Amdahl 博士在他的论文(参考上文)中还没有提出这一点，并且将苹果与橙子进行比较从来没有给任何人带来任何积极的影响.任何严格领域的科学话语.

Both of these group of factors have to be incorporated in the overhead-strict, resources-aware Amdahl's Law re-formulation, if it ought serve well to compare apples to apples in contemporary parallel-computing realms. Any kind of use of an overhead-naive formula results but in a dogmatic result, which was by far not formulated by Dr. Gene M. Amdahl in his paper ( ref. above ) and comparing apples to oranges have never brought anything positive to any scientific discourse in any rigorous domain.

               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               

---

开销严格和资源感知重新制定:

                           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               /

---

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

由于上述原因，一张图片可能价值百万字.试试这个，其中交叉链接了一个完全交互式的工具，用于使用开销严格的阿姆达尔定律.

---

Interactive Tool for a maximum effective speedup :

Due to reasons described above, one picture might be worth million words here. Try this, where a fully interactive tool for using the overhead-strict Amdahl's Law is cross-linked.

这篇关于阿姆达尔定律中的负加速?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！