On Thu Oct 15 08:01:29 EDT 2009, w...@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
