Re: [9fans] Barrelfish

[erik quanstrom <quanstro@quanstro.net>]

On Thu Oct 15 08:01:29 EDT 2009, wbh@conducive.org wrote:
> Richard Miller wrote:
> >> It's easy to write good code that will take advantage of arbitrarily many
> >> processors to run faster / smoother, if you have a proper language for the
> >> task.
> >
> > ... and if you can find a way around Amdahl's law (qv).
> >
> >
> >
>
> http://www.cis.temple.edu/~shi/docs/amdahl/amdahl.html

the author is hard to search for.  http://en.wikipedia.org/wiki/Yuanshi_Era

perhaps i misread the paper,  but i think it boils down to
chopping up a O(n^2) can give you super-linear speedups—
no big surprise.  and there might be better algorithims.
(no examples given.)  but you're still going to fall of a cliff when
you run out of processors.  and you don't get rid of the
sequential part.

the problem i see with this approach is (a) you need a lot
of processors to do this.  if p is the number of processors then
the speedup for a quadratic algorithm would be

	 n^2 / (sum_{1 .. p} (n/p)^2
		= n^2 / p(n/p)^2
		= p

so if you want a order of magnitude speedup *for a given n*
you need 10 processors.  but of course the number of processors
needed goes as O(n^2).  bummer.  oh, and we haven't considered
communication overhead.

and (b) the paper claims that all network communication is worst
case O(n) §3¶8.  we know this to be false.  consider n+1 computers with
an ethernet connection connected by a switch.  suppose that
computers 0-n are ready to send a result back to n and each
blast away at the network's limit.  it's going to take more time
to get the data back in n -> 1 configuration than it would to
get the same data back in an 1:1 configuration because the
switch will drop packets.  even assuming pause frames, the
switching time can't be zero.

- erik