[zeromq-dev] Parallel sort

[Oliver Smith]

On 8/2/2010 7:25 PM, Pieter Hintjens wrote:
> 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.
>    
It depends on the sort algorithm. "bitonic merge sort", for instance, 
produces binary.

However: if you introduce the overhead of having to create threads on 
demand, rather than being able to use a pool of pre-existing workers, 
you'd probably create a situation where - for purely local 
implementations - OpenMP's "#pragma omp task" or TBB's "TBB::Pipeline" 
system would be better (tbb in-particular if you are using Intel hardware :)

- Oliver

References:

bitonic merge sort: http://en.wikipedia.org/wiki/Bitonic_sorter
#pragma omp task 
http://wikis.sun.com/display/openmp/Using+the+Tasking+Feature
TBB::Pipeline 
http://software.intel.com/en-us/blogs/2007/10/31/tbb-pipeline-class-application-in-text_filtercpp/