Life After Moore's Law
|
Prev: Processors stall on OLTP workloads about half the time--almost no ?matter what you do
Next: Processors stall on OLTP workloads about half the time--almostno matter what you do
From: Robert Myers on 30 Apr 2010 08:45 On Apr 30, 5:49 am, Quadibloc <jsav...(a)ecn.ab.ca> wrote: > On Apr 29, 11:51 pm, Robert Myers <rbmyers...(a)gmail.com> wrote: > > > One possible (likely?) outcome is that we will ditch the Navier-Stokes > > equations (at least for computation) in favor of approaches like > > Lattice Boltzmann methods: > > >http://en.wikipedia.org/wiki/Lattice_Boltzmann_methods > > Ouch. I would have thought that a lattice Navier-Stokes method, > following the "relaxation" approach, would have been more efficient as > a parallel method than following individual particles around. Lots of ways of "solving" Navier-Stokes on huge clusters with limited bandwidth, but they entail considerable self-deception. LBM may prove to be little more than a new kind of self-deception, but it is naturally local and naturally parallel. Robert.
From: Daniel A. Jimenez on 30 Apr 2010 10:42 In article <06963ca1-d0fe-44a1-b6ff-eca82c563dac(a)e39g2000yqf.googlegroups.com>, Quadibloc <jsavard(a)ecn.ab.ca> wrote: >On Apr 29, 9:23=A0pm, "Del Cecchi" <delcec...(a)gmail.com> wrote: > >> Algorithms are not like rocks, laying around to be discovered. > >It's true that an algorithm is a series of steps, specified by a >human. > >But whether or not a certain algorithm achieves a desired result or >not is a mathematical fact. > >Thus, the fact that Goldschmidt division is effective, that this is a >possible way to do division efficiently, is indeed a fact of >mathematics. Or the algorithms based on equations by Ramanujan that >allow pi to be evaluated quickly to a high precision. Or the >algorithms for factoring, or for testing for primality. > >These things are considered to be discoveries, not just inventions. > >So it isn't an engineering problem, but a fundamental scientific >problem, to find an algorithm to do a fundamental task (like sorting) >faster than any previous algorithm has permitted. And nature and >mathematics get to say "no". > >Which means we won't always find algorithms as fast, as efficient, or >as parallelizable as we might like. Some tasks cannot be parallelized. This has been formalized. See for intsance http://en.wikipedia.org/wiki/P-complete . -- Daniel Jimenez djimenez(a)cs.utexas.edu "I've so much music in my head" -- Maurice Ravel, shortly before his death. " " -- John Cage
From: nmm1 on 30 Apr 2010 10:50 In article <hreq8v$dof$1(a)gina.cs.utexas.edu>, Daniel A. Jimenez <djimenez(a)cs.utexas.edu> wrote: >In article <06963ca1-d0fe-44a1-b6ff-eca82c563dac(a)e39g2000yqf.googlegroups.com>, >Quadibloc <jsavard(a)ecn.ab.ca> wrote: >> >>So it isn't an engineering problem, but a fundamental scientific >>problem, to find an algorithm to do a fundamental task (like sorting) >>faster than any previous algorithm has permitted. And nature and >>mathematics get to say "no". >> >>Which means we won't always find algorithms as fast, as efficient, or >>as parallelizable as we might like. > >Some tasks cannot be parallelized. This has been formalized. See for >intsance http://en.wikipedia.org/wiki/P-complete . Some mathematical problems cannot be parallelised, true, but there are two steps that precede that: Choosing the DETAILED physical (etc.) question to ask Choosing the mathematical approach to answering that In particular, slight variations of the form of accuracy required can change a problem from be provably intractable to trivial; e.g. changing the error from being deterministic to probabilistic. Regards, Nick Maclaren.
From: Quadibloc on 30 Apr 2010 10:53 On Apr 30, 6:45 am, Robert Myers <rbmyers...(a)gmail.com> wrote: > Lots of ways of "solving" Navier-Stokes on huge clusters with limited > bandwidth, but they entail considerable self-deception. But on a high-bandwidth cluster, a relaxation method could involve considerably less self-deception. John Savard
From: Quadibloc on 30 Apr 2010 10:55
On Apr 30, 8:50 am, n...(a)cam.ac.uk wrote: > Some mathematical problems cannot be parallelised, true, but there > are two steps that precede that: > > Choosing the DETAILED physical (etc.) question to ask > > Choosing the mathematical approach to answering that > > In particular, slight variations of the form of accuracy required > can change a problem from be provably intractable to trivial; e.g. > changing the error from being deterministic to probabilistic. This I have no problem with. We need to be aware of every possible way to solve problems in a parallel manner, now that this is the kind of tool we have most readily available. As long as we're not kidding ourselves into thinking this will always work, and so we don't give up efforts to improve serial performance as well. John Savard |