Re: [9fans] Barrelfish

[Sam Watkins <sam@nipl.net>]

I wrote:
>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

On Tue, Oct 20, 2009 at 03:16:22AM +0100, matt wrote:
> I know you are using video / audio encoding as an example and there are
> probably datasets that make sense but in this case, what use is it?

I was using it to work out the *maximum* extent to which a common task can be
parallelized.  20-trillion-fold is the answer I came up with.  Someone was
talking about Ahmdal's Law and saying that having large numbers of processors
is not much use because Ahmdal's Law limits their utilization.  I disagree.

In reality 10,000 processing units might be a more sensible number to have than
20 trillion.  If you have ever done H264 video encoding on a PC you would know
that it is very slow, even normal mpeg encoding is barely faster than real time
on a 1Ghz PC.  Few people like having to wait 2 hours for a task to complete.

This whole argument / discussion has come out of nowhere since it appears Ken's
original comment was criticising the normal sort of multi-core systems, and he
is more in favor of other approaches like FPGA.  I fully agree with that.

> You can't watch 2 hours of video per second and you can't write it to disk
> fast enough to empty the pipeline.

If I had a computer with 20 trillion processing units capable of recoding 2
billion hours of video per second, I would have superior storage media and IO
systems to go with it.  The system I described could encode 2 BILLION hours of
video per second, not 2 hours per second.

> You've got to feed in 2 hours of source material - 820Gb per stream, how?

I suppose some sort of parallel bus of wires or optic fibres.  If I have
massively parallel processing I would want massively parallel IO to go with it.
I.e. something like "read data starting from here" -> "here it is streaming one
megabit in parallel down the bus at 1Ghz over 1 million channels"

> Once you have your uncompressed stream, MPEG-2 encoding requires seeking
> through the time dimension with keyframes every n frames and out of order
> macro blocks, so we have to wait for n frames to be composited.  For the best
> quality the datarate is unconstrained on the first processing run and then
> macro blocks best-fitted and re-ordered on the second to match the desired
> output datarate, but again, this is n frames at a time.
>
> Amdahl is punching you in the face every time you say "see, it's easy".

I'm no expert on video encoding but it seems to me you are assuming I would
approach it the conventional stupid serial way.  With massively parallel
processing one could "seek" through the time dimension simply by comparing data
from all time offsets at once in parallel.

Can you give one example of a slow task that you think cannot benefit much from
parallel processing?  video is an extremely obvious example of one that
certainly does benefit from just about as much parallel processing as you can
throw at it, so I'm surprised you would argue about it.  Probably my "20
trillion" upset you or something, it seems you didn't get my point.

It might have been better to consider a simpler example, such as frequency
analysis of audio data to perform pitch correction (for out of tune singers).

I can write a simple shell script using ffmpeg to do h264 video encoding which
would take advantage of perhaps 720 "cores" to encode a two hour video in 10
second chunks with barely any Ahmdal effects, running the encoding over a LAN.
A server should be able to pipe the whole 800Mb input - I am assuming it is
already encoded in xvid or something - over the network in about 10 seconds on
a gigabit (or faster) network.  Each participating computer will receive the
chunk of data it needs.  The encoding would take perhaps 30 seconds for the 10
seconds of video on each of 720 1Ghz computers.  And another 10 seconds to pipe
the data back to the server.  Concatenating the video should take very little
time, although perhaps the mp4 format is not the best for that, I'm not sure.

The entire operation takes 50 seconds as opposed to 6 hours (21600 seconds).
With my 721 computers I achieve a 432 times speed up.  Ahmdal is not sucking up
much there, only a little for transferring data around.  And each computer
could be doing something else while waiting for its chunk of data to arrive,
the total actual utilization can be over 99%.  People do this stuff every day.
Have you heard of a render-farm?

This applies for all Ahmdal arguments - if part of the system is idle due to
serial constraints in the algorithm, it could likely be working on something
else.  Perhaps you have a couple of videos to recode?  Then you can achieve
close to 100% utilization.  The time taken for a single task may be limited by
the method or the hardware, but a batch of several tasks can be achieved close
to N times faster if you have N processors/computers.

I'm not sure why I'm wasting time writing about this, it's obvious anyway.

Sam