From: Jerry Leichter <leichter@smarts.com>
Newsgroups: comp.parallel
Subject: Re: superlinear question
Date: 19 Oct 1998 17:26:48 GMT
Organization: System Management ARTS
Approved: bigrigg@cs.cmu.edu
Message-Id: <70fsoo$js6$1@encore.ece.cmu.edu>
Originator: bigrigg@ece.cmu.edu


| Superlinear speedup == (perpetual motion machine || perverse serial
| implementation).

Most of the examples given (e.g., using a bubble sort serially and some
decent sort in parallel) are reasonable.  However, there is a third,
sort-of-legitimate, disjunct to the above:  Use more memory for the
parallel implementation than for the serial one.  This usually happens
without anyone noticing when tests get run in the typical way:  First,
run on one of the processors in your parallel system; then, run in N of
them.  Assuming all your processors are equivalent, the parallel run
will have N times as much memory.  If your test needs more memory than
it gets in one processor - at the extreme, if it thrashes in that much
memory; or if it adapts to the amount of available memory, and does
better for its own internal reasons when there's plenty of it; then you
can see way-superlinear speedup simply because of the extra memory. 
(You might even see it with the actual algorithm running serially on one
processor, with the rest simply acting as "memory servers"!)

In one sense, a "fair" test would use N processors with M bytes of
memory, or one processor with NM bytes (and equal access parameters, of
course).  Then it's impossible to get superlinear speedup because of
memory effects.  But this is a notion of "fairness" that may not be very
fair.  In practice, you may not be able to put that much memory in one
processor - parallelization may be your only way to access that much.  
If you have a real problem to solve on real hardware, who cares *why*
the N-processor implementation speeds up (even superlinearly!) as long
as it does so?  Of course, if someone is trying to sell you on such
approach, you need to understand why it works so you'll know what
changes to the problem will make it *stop* working!
							-- Jerry

--
Articles to bigrigg+parallel@cs.cmu.edu (Admin: bigrigg@cs.cmu.edu)
Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel