delp@udel.EDU (Gary Delp) (09/14/87)
I have heard the following observation attibuted to Gene Amdahl, but
have not been able to find it in the literature. If you have seen it,
and have some hard information on it, I would appreciate it if you
would let me know directly. I will report back on the results.
The "Law" as I understand it states that there is a fundamental limit
to the speedup that can be acheived by taking a serial task and
running it on a parallel processor. This limit is set by the portions
of the task that still be serialized. the formula is:
S + P S = time required by serial portion of task
speedup = --------- , where P = total time required by parallel portion
S + P/N N = Number of Processors
This obviously ignores such factors as communication overhead and
latency, but is meant to provide a fundamental limit, not a firm
prediction of performance.
Harold Stone's new book "High-Performance Computer Architecture",
which is, by the way, a fine addition to the choices of textbooks in
the field, covers the issues in this area without mentioning the
fundamental limit.
Gary Delp ARPA: delp@udel.edu
123 Evans Hall BITNET: delp@udel.edu
EE U of D CSNET: delp%udel.edu@relay.cs.net
Newark, DE 19716eugene@pioneer.arpa (Eugene Miya N.) (09/14/87)
%A Gene M. Amdahl %T Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities %J AFIPS Conference Proceedings (SJCC) %V 30 %D 1967 %P 483-485 If you get a chance to here him speak, I highly recommend it. John Backus is another IBMer (developed FORTRAN) who gives good lectures. This paper is not great, it's a top of the head paper rather than an academic paper. Required reading (my opinion) for any person thinking about parallel processing (but I'll mention that Wednesday). --eugene
lindsay@k.gp.cs.cmu.edu (Donald Lindsay) (09/18/87)
[Xref: hubcap comp.hypercube:85] There are several answers to Amdahl's Law. To recap: he said that a parallel computation cannot run any faster than its inherently sequential portion. Some people with multiprocessors ignore the Law. They feel that they replicate, not parallelize. Just do other problems too ! The counter-argument is that some people only have one problem (like, the weather). The phrase THEY use is "time to solution". Cleve Moler at Intel Scientific Computers argues that as a problem increases in size, the fraction of it which is sequential will decrease. He defines an "effective" algorithm to be one for which this is true, and claims that there are many effective algorithms. Multiflow has another answer. They find more parallelism in programs than had previously been suspected. This doesn't defeat the Law, but gives many problems another chance. For example, Multiflow claim that a Monte Carlo benchmark ran faster on their machine than the customer had ever seen it go before - even on Crays. (An atypical case, of course.) On a MIMD machine such as a hypercube, it can happen that a program runs faster on 2**5 nodes than on 2**6 nodes. On a Multiflow, it can happen that a program takes the same time on 7 functional units as on 14 funtional units. Or, you can win! Exciting times. -- Don lindsay@k.gp.cs.cmu.edu CMU Computer Science
swh@hpsmtc1.HP.COM (Steve Harrold) (09/18/87)
Re: Amdahl's Law If there is some dispute as to how accurate Amdahl's "Law" is, shouldn't it be more properly labelled "Amdahl's Theorem"?? --------------------- Steve Harrold ...hplabs!hpsmtc1!swh HPG200/13 (408) 447-5580 ---------------------
fpst@hubcap.UUCP (Steve Stevenson) (09/21/87)
in article <11370002@hpsmtc1.HP.COM>, swh@hpsmtc1.HP.COM (Steve Harrold) says: > If there is some dispute as to how accurate Amdahl's "Law" is, shouldn't > it be more properly labelled "Amdahl's Theorem"?? Properly, it isn't a theorem unless done with some axioms, etc. How about "conjecture" or "thesis." -- Steve Stevenson fpst@hubcap.clemson.edu (aka D. E. Stevenson), fpst@clemson.csnet Department of Computer Science, comp.hypercube Clemson University, Clemson, SC 29634-1906 (803)656-5880.mabell
daveb@geac.UUCP (Brown) (09/22/87)
In article <483@hubcap.UUCP> fpst@hubcap.UUCP (Steve Stevenson) writes: >in article <11370002@hpsmtc1.HP.COM>, swh@hpsmtc1.HP.COM (Steve Harrold) says: >> If there is some dispute as to how accurate Amdahl's "Law" is, shouldn't >> it be more properly labelled "Amdahl's Theorem"?? > >Properly, it isn't a theorem unless done with some axioms, etc. How >about "conjecture" or "thesis." Er, I think Gene was stating an emperically verifiable fact. In sicence, these are usually called "laws" (like the law of gravity) and theories and/or conjectures about them are called "theories" (like the Newtonian theory of mass attraction, aka gravitation). Darned if I know what a Theorem would be in science... maybe a theory without a law, but with a rigorous proof? --dave (terminological inexactitude) c-b -- David Collier-Brown. {mnetor|yetti|utgpu}!geac!daveb Geac Computers International Inc., | Computer Science loses its 350 Steelcase Road,Markham, Ontario, | memory (if not its mind) CANADA, L3R 1B3 (416) 475-0525 x3279 | every 6 months.