From: Bill Maniatty <maniattb@cs.rpi.edu>
Newsgroups: comp.parallel
Subject: Re: superlinear question
Date: 19 Oct 1998 17:24:22 GMT
Organization: Rensselaer Polytechnic Institute
Approved: bigrigg@cs.cmu.edu
Message-Id: <70fsk6$jpq$1@encore.ece.cmu.edu>
Originator: bigrigg@ece.cmu.edu


Randy Crawford wrote:
> @PUB:EMAIL.COM EMDIR wrote:
> > Is there anyone who can give us the SIMPLEST algorithm and codes to
> > achieve SUPERLINEAR speedup.  I am using MPI (Message Passing
> > Interface) and C to study the parallel algoritm.  Any help will be
> > appreciated.  Please send them straight to my e-mail

[Tricks involving hobbling the serial implementation and
	crippling parallel implementations on small numbers
	of processors deleted]

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

These kind of tricks which were suggested are a bit too obvious,
and are not what I usually think as a superlinear speedup (and
I suspect that other people in the parallel computing community
might agree with me on this).

A more typical cause is when a reduction in problem size per
processor improves the performance beyond the cost of the
associated communication.  I will refrain from providing a specific
algorithm, since it does sound like a homework problem, but I'll
give you a hint, look for architectural features which cause
performance to degrade nonlinearly as problem size increases.

Regards:

Bill Maniatty

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