Path: utzoo!attcan!uunet!ncrlnk!ncrcae!hubcap!vera
From: vera@portia.stanford.edu (James Vera)
Newsgroups: comp.parallel
Subject: Re: Superlinear(?) speedups
Message-ID: <3905@hubcap.UUCP>
Date: 15 Dec 88 14:03:56 GMT
Sender: fpst@hubcap.UUCP
Lines: 34
Approved: parallel@hubcap.clemson.edu


In article <3881@hubcap.UUCP> mcvax!cs.exeter.ac.uk!sru@uunet.UU.NET (Steve Rush) writes:
> [...]
>OR "You could have the 4 linked lists per scanline on the single
>processor". This is cheating by running different algorithms on the two
>systems, in this case I should have 4 lists per scanline on every
>processor, which takes you back to the case above.)
> [...]
>                                             Steve R
>
>---
>Steve Rush			JANET: sru@uk.ac.exeter.cs 
>Computer Science Dept.		UUCP:  ukc!expya!sru
>University of Exeter

No, this would not be cheating.  It is you who is running different
algorithms. In the multiprocessor case you are running an algorithm
which says "search 4 linked lists simultaneously", and in uniprocessor
case you are running a different global algorithm, which says "search
1 linked list".

It does not seem possible that n processors could run faster than n
times one processor for a given global algorithm.  One need only time
slice the runs of the n processors on the 1 processor, ignoring the
very real effects of cache effectiveness, etc ...




-- 
James S. Vera      |      Internet	     |Standard Disclaimers
Stanford University|vera@portia.stanford.edu |Blah Blah Blah Blah
Bellcore           |vera2%mruxb@bellcore.arpa|vvv My Cutesy Quote vvv
"When I was young it seemed that life was so wonderful..." - Supertramp