[zeromq-dev] Parallel sort

[Pieter Hintjens]

On Tue, Aug 3, 2010 at 1:59 AM, Oliver Smith <oliver at kfs.org> wrote:

> It's in the Subject line :)
>
> I've been thinking about this a lot today (how you might sub-division
> parallel work into sub-tasks and then perform a subsequent reunification).
> Fundamentally, it is the same principle as packet fragmentation and
> reassembly.

:-)  Yes, the subject line is clear but you've not explained a use case.

However it's an interesting question in itself.  It sounds like a tree
walking algorithm.  Breaking work down and redistributing it looks
easy enough, but merging results back together seems more tricky.
Presumably there is a symmetric algorithm involving xreq/xrep and
stacked identities so that results can be routed back to their
original node.

Do you know if the division is binary or n-ary?  I'm thinking each
node could be multithreaded and have three sockets per thread, one
connected to a dispatcher, n connected to potential sub-nodes in a
virtual tree.  Requests flow down the virtual tree, replies flow back
up.  Each thread waits for replies, consolidates them, sends the
result back up.

-Pieter