Re: [9fans] Barrelfish

[Sam Watkins <sam@nipl.net>]

On Sat, Oct 17, 2009 at 07:45:40PM +0100, Eris Discordia wrote:
> Another embarrassingly parallel problem, as Sam Watkins pointed out, arises
> in digital audio processing.

The pipelining + divide-and-conquer method which I would use for parallel
systems is much like a series of production lines in a large factory.

I calculated roughly that encoding a 2-hour video could be parallelized by a
factor of perhaps 20 trillion, using pipelining and divide-and-conquer, with a
longest path length of 10000 operations in series.  Such a system running at
1Ghz could encode a single 2-hour video in 1/100000 second (latency), or 2
billion hours of video per second (throughput).

Details of the calculation: 7200 seconds * 30fps * 12*16 (50*50 pixel chunks) *
500000 elementary arithmetic/logical operations in a pipeline (unrolled).
7200*30*12*16*500000 = 20 trillion (20,000,000,000,000) processing units.
This is only a very rough estimate and does not consider all the issues.

The "slow" latency of 1/100000 second to encode a video is due to Ahmdal's Law,
assuming a longest path of 10000 operations.  The throughput of 2 billion hours
of video per second would be achieved by pipelining.  The throughput is not
limited by Ahmdal's Law, as a longer pipeline/network holds more data.

Ahmdal's Law gives us a lower limit for the time taken to perform a task with
some serial components; but does not limit the throughput of a pipelining
system, the throughput is simply one data unit per clock cycle.

In reality, it would be hard to build such a system, and one would prefer a
system with much less parallelization.  However, the human brain does contain
100 billion neurons, and electronic units can be smaller than neurons.

My point is, one can design systems to solve practical problems that use almost
arbitrarily large numbers of processing units running in parallel.

Sam