Prev: High-bandwidth computing (hbc) wiki and mailing list
Next: Effects of Memory Latency and Bandwidth onSupercomputer,Application Performance
From: Robert Myers on 5 Aug 2010 14:55
On Jul 26, 1:33 am, Andy Glew <"newsgroup at comp-arch.net"> wrote:
> On 7/25/2010 8:12 PM, Robert Myers wrote:
>
> > I got stopped on Bill Dally's first slide, where he says
> > "efficiency=locality."
>
> > He claims that his slide tells you everything you need to know about
> > the future of computing, AND THAT BELIEF AND PROSELYTIZING FOR THAT
> > BELIEF IS WHY I HAVE USED UP SO MUCH SPACE HERE.
>
> > THE MOST INTERESTING PROBLEMS ARE NOT LOCAL, BECAUSE THE MOST
> > INTERESTING PROBLEMS ARE NOT LINEAR.
>
> > A problem is embarrassingly parallelIFFit is localIFFit is linear.
>
> > If a problem is linear, then there is a representation in which it is
> > both local and embarrassingly parallel.  If a problem is not linear,
> > then there is, in general, no such representation.  Does one need a
> > PhD from Cal Tech to understand this?
>
> (1) Is there a proof for this?  Not that there are non-linear systems
> that are not embarassingly parallel, but that there are no interesting
> non-linear systems that are not amenable to parallel solutions.
>
> E.g. the N-body problem, gravitational dynamics?
>
I ducked a direct answer to this question on the first pass.

A linear problem is one for which, if f and g are solutions, then f+g
is a solution. Since the previous statement is a definition of
linear, it's an if and only if property, as all definitions are. In
general, you can divide the problem up into many parallel problems and
add it all up at the end, so the problem is embarrassingly parallel.

As to the non-locality of nonlinear problems, imagine a Fourier space
representation. If you expand the nonlinearity in a power series, the
first nonlinear term will have a product of states h1*h2. If you
start out with h1 and h2 as pure states with spatial frequency f1 and
f2, then the non-linear term will produce mixed states at spatial
frequency f1+f2, and the interaction of those states will produce
still more states.

Sometimes there exists a transformation that will expose an apparently
non-linear problem as linear in some representation, but, in general,
no such transformation exists.

You ask about the n-body problem, which could be gravitation
(astrodynamics) or the coulomb force (molecular dynamics). You can
obtain a Poisson equation for the potential

div grad (potential) = charge density.

If you are willing to represent the second derivative by centered
differences, then you end up with a tridiagonal problem that is well-
suited to the linear library machines the Top500 list favors.

Once you have the potential, you can find the force on any particle as

force = grad (potential)

There is a name for this approximation in molecular dynamics, but
since the approach had already been thought of in many other contexts,
a separate name is hardly justified. As to the accuracy of the
approximation, that is another matter.

I assume that using the Poisson equation approach (with centered
differences) is how IBM managed to give Blue Gene the name it did, in
spite of the fact that, on the face of it, the machine is unsuited to
calculating long-range interactions like the Coulomb force because of
limited global bandwidth.

Robert.

First  |  Prev  | 
Pages: 1 2 3 4 5 6 7
Prev: High-bandwidth computing (hbc) wiki and mailing list
Next: Effects of Memory Latency and Bandwidth onSupercomputer,Application Performance