The power of parallel computation

Imagine looking at an algorithm literature full of papers competing for
the best computation times on a 1-tape Turing machine. ``I can sort in
time n^2 log^3 n!'' ``I can do even better: time n^2 log^2 n!''

What would you think? You'd laugh. Turing-machine price-performance
ratios have very little to do with real-world price-performance ratios;
they don't even get the _exponent_ right. Turing-machine optimization
might be an amusing mathematical exercise, but it's no substitute for
serious algorithm analysis.

Well, that's what future algorithm designers are going to think of
today's RAM-dominated algorithm literature. RAM price-performance ratios
have very little to do with real-world price-performance ratios; they
don't even get the _exponent_ right. RAM optimization might be an
amusing mathematical exercise, but it's no substitute for serious
algorithm analysis.

Do you think that RAM _does_ get the exponent right? In particular, do
you think that parallel computation can't improve the price-performance
ratio? http://cr.yp.to/talks.html#2005.06.11-1 tackles your confusion
head-on, and shreds the notion that RAM is a good architecture.

---D. J. Bernstein, Associate Professor, Department of Mathematics,
Statistics, and Computer Science, University of Illinois at Chicago
.

Relevant Pages

  • Re: The power of parallel computation
    ... > the best computation times on a 1-tape Turing machine. ... > serious algorithm analysis. ... RAM price-performance ratios ...
    (comp.theory)
  • Re: SortMerge avoids thrashing (was: Baileys "two pass" FFT algorithm question)
    ... For the algorithm used, one makes n/2 merge runs, where n is the ... But if you're using RAM, there's no need to bother with that, you ... cache would thrash. ... to fit within the fast cache at all times, ...
    (comp.programming)
  • Re: out of memory
    ... read only the smaller file into a hash. ... the smaller file will fit into RAM. ... Depending upon the sorting algorithm this would be Ologor ... put your relevant data into a database and use ...
    (comp.lang.perl.misc)
  • Re: out of memory
    ... the smaller file will fit into RAM. ... Depending upon the sorting algorithm this would be Ologor ... put your relevant data into a database and use ...
    (comp.lang.perl.misc)
  • Re: External sorting
    ... Something which cannot fit in RAM. ... you need to have four physical disk drives (or one ... Then the algorithm you want is building up whatever size merge-runs ...
    (comp.programming)