[zeromq-dev] Parallel sort

[Oliver Smith]

Martin,

> I have no real answer as for now. However, the idea of sending messages
> in (possibly infinite?) loops sound kind of scary.
>    
Not infinite :) I think the issue is one of collection; step X creates N 
units of work that require processing and then resumption:

Recurse(work, token)
   if work.load.size <= minimum
     Process(work)
     DispatchToken(Complete, token)
   else
     leftToken = DispatchTask(Recurse, work.left)
     rightToken = DispatchTask(Recurse, work.right)
     DispatchJoin(Join, leftToken, rightToken, work, token)

Join(leftToken, rightToken, work, token)
   PostProcess(work)
   DispatchToken(Complete, token)

Complete(token)
   if token == parentToken
     ReplyToParent() # Tell the parent thread we're finished
   else
     pair = pairs[token]
     if pair.empty()     # I'm the first to complete
       pair.push_back(token)
     else
       DispatchTask(pair.work, pair.token)
       delete pair         # we're done

ParallelDivideAndConquer(work)
   Recurse(work, parentToken)
   WaitForReply()


(Or something vaguely like that)

I'm thinking it needs a 3 stage system:

- Parent thread, which generates the initial tasks,
- Join thread, which tracks in-flight tokens and collects completed tokens
- Worker threads, which received tokenized work and send completions 
back to the Join thread

- Oliver