Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!gatech!hubcap!lindsay
From: lindsay@k.gp.cs.cmu.edu (Donald Lindsay)
Newsgroups: comp.hypercube,comp.arch
Subject: Re: Amdahl's Law
Message-ID: <470@hubcap.UUCP>
Date: Fri, 18-Sep-87 08:07:29 EDT
Article-I.D.: hubcap.470
Posted: Fri Sep 18 08:07:29 1987
Date-Received: Sun, 20-Sep-87 01:58:43 EDT
Sender: fpst@hubcap.UUCP
Lines: 28
Keywords: amdahl, speedup, parallel
Approved: hypercube@hubcap.clemson.edu
Xref: mnetor comp.hypercube:90 comp.arch:2231

[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