Tuesday, August 4, 2009

A Bit of Distributed Computation...

In the last months I've worked on various 2D rendering projects, that requires lots of row power to be executed in smallest time as possible.

The rendering result is an aggregation of components (or better, Group of Components) that can be rendered independently of each other in a  process because each components has its own input data and until the aggregation process starts there're no dependencies between components. In a few words, foreach input data I've to call a Render method that returns the "computed" data, that at the end will be aggregated with all the computed values.

So, how speed-up the rendering? The standard answer is using Threads, to take advantage of multi-core system. But I need lots row power and lots of core to be fast enought. Another solution that doesn't require to spent a lot of money for a faster computer it to distribute the computation across different machines. And this is my attempt...

The Master receive an array of elements as input and splits up it according to the number of the available Nodes (Machines), and foreach node assigns its sub-array and sends an "informative message" to the node.

The Node waits for an "informative message" and when it has received it, starts its computation. Foreach Data Item that fetch runs the Computation and sends back the result.

The Master decompose data into equal-size partitions, so each node has  an equal-size queue to process, but if someone finishes its job and there're more data to process (in someone else queue) The Master dequeue couple of items from the slower node queue and add to the queue of the one that has finished its job. In this way you've done your computation faster then ever, and if one machine crashes (slow one case) its job will be taken by someone else that has finished its own.

And this is just a bit of General Theory, but the implementation is really simple. Maybe I'll try to reimplement something more generic in the near future (October, November) when I'll have a bit more of free time. If you've any question send me a mail!

No comments:

Post a Comment