[zeromq-dev] Parallel sort

[Martin Sustrik]

On 08/03/2010 03:07 AM, Pieter Hintjens wrote:
> There are certainly ways to map a very large virtual tree onto a 
> smaller number of real worker threads. It just requires some passing 
> of state up and down. Grab state, decide whether to split or execute, 
> return results, repeat. Would work with stateless workers and all 
> state concentrated in one dispatcher.
>    
Yes. Conflating the tree to limited number of workers is easy:

Have one queue device, N workers, each worker looks like this:

socket_t parent (ctx, ZMQ_REP);
parent.connect (queue);
sokcet_t child1 (ctx, ZMQ_REQ);
child1.connect (queue);
socket_t child2 (ctx, ZMQ_REQ);
child2.connect (queue);
while (true) {
     request = patent.recv ();
     child1.send (split_left (request));
     child2.send (split_right (request));
     left = child1.recv ();
     right = child2.recv ();
     parent.send (join (left, right));
}

Looks good, but will end up deadlocked in any non-trivial case :(

To prevent hangups components would have to be able to process multiple 
request in parallel, which means storing state. Storing state in turn 
means loosing scalability.

My gut feeling is that scalability and recursive algorithms are 
inherently incompatible.

One option would be to rewrite the sort in iterative (rather than 
recursive) manner and apply divide and conquer approach on the result.

Martin