Re: [9fans] GCC/G++: some stress testing

["Roman V. Shaposhnik" <rvs@sun.com>]

On Sun, 2008-03-02 at 12:34 -0800, Paul Lalonde wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> CSP doesn't scale very well to hundreds of simultaneously executing
> threads (my claim, not, as far as I've found yet, anyone else's).

I take it that you really do mean "simultaneous". As in: you actually
have hundreds of cores available on the same system. I'm actually
quite curious to find out what's the highest number of cores available
of a single shared memory systems that you, or anybody else has
experienced in practice so far (mine would be 32 == 8 CPUs x 4 cores AMD
Barcelona)? Now even more important question is -- what are the
expectations for, this number in 5 years from now?

> Programming the memory hierarchy is really a specific instance of
> programming for masking latency.  This goes well beyond inserting
> prefetches in an optimization stage,

In fact the more I think about it, the more it seems like having
a direct way of manipulating L1/L2 caches would be more of a benefit
than a curse at this point. Prefetches are nothing but a patchwork
over the fundamental need for programming memory hierarchy in an
efficient way. But, I guess, there's more to it on the hardware side
than just crafting additional opcodes.

> presenting itself as problem
> decompositions that keep the current working set in cache (at L3, L2,
> or L1 granularity, depending), while simultaneously avoiding having
> multiple processors chewing on the same data (which leads to vast
> amounts of cache synchronization bus traffic).  Successful algorithms
> in this space work on small bundles of data that either get flushed
> back to memory uncached (to keep more cache for streaming in), or in
> small bundles that can be passed from compute kernel to compute
> kernel cheaply.  Having language structures to help with these
> decompositions and caching decisions is a great help - that's one of
> the reasons why functional programming keeps rearing its head in this
> space.  Without aliasing and global (serializing) state it's much
> easier to analyze the program and chose how to break up the
> computation into kernels that can be streamed, pipelined, or
> otherwise separated to allow better cache utilization and parallelism.

Very well said, indeed! I can't agree more, especially on the issue
of functional programming being very well suited for parallelism.
In fact, here at Sun we've had a curious little experiment run by
Tim Bray:
   http://www.tbray.org/ongoing/When/200x/2007/09/20/Wide-Finder
with a very unexpected result as to what would be the ideal
language for what seems to be an embarrassingly parallel problem.

> Currently, the best performing programs I know for exploiting the
> memory hierarchy are C and C++ programs written in a  "kernel
> composition" kind of model that the language supports poorly.  You
> can do it, but it feels more like coding in assembly than like
> expressing your algorithms.  Much of the template metaprogramming is
> about taking measures of cache spaces and data sets and turning out
> code (statically) tuned to those sizes.  There's a huge opportunity
> for a JIT language to allow better adaptability to changing data sets
> and numbers of active threads.

These techniques help. No doubt about it. Still, I don't think that we
have much of choice when the # of compute units hits hundreds of
thousands -- at that level shared state  and side effects propagated
through it will be just too much to stomach. We clearly need a very
different way of thinking about programming and also the way of
expressing our ideas. None of the mainstream languages seem to fit
the bill. And as far as I can tell this makes it one of the hottest
research areas in the industry. Everybody wants to hit that jackpot
by inventing C for the parallel world.

Thanks,
Roman.

P.S. We had Don Knuth lecturing at Sun Labs a couple of days ago and he
gave us all a real scare when he officially proclaimed that he could NOT
see any way of how his reasoning about computation and algorithms
could be applied to parallelism. In fact, in his latest volume he has
an explicit disclaimer to that effect.