Parallel sort

My next self-challenge for parallelism with ZeroMQ is going to have to be putting together a parallel sort.

With parallelism options like OpenMP and TBB, you know the data is local and can take various short cuts by handing over pointers. ZeroMQ takes the same short-cut for “inproc://” connections, and the zero-copy (that provides the ‘Zero’ part of the name) matches OpenMP and TB for efficiency (since they use mutexes, spinlocks etc).

A local-only parallel sort can take advantage of this; since you are only going to assign any given range to one thread at a time, you can just pass the address of the data and the working-range indexes and know that threads aren’t going to experience resource contention.

But if you want to make it scalable – e.g. by allowing remote connections to remote processors over InfiniBand with a tcp:// connection,


zmq::context_t zmqContext(2) ;
zmq::socket_t myEndpoint(ZMQ_DOWNSTREAM) ; // For sending work downstream to workers.

// Accept downstream worker connections from
// local threads via inproc://
myEndpoint.bind("inproc://local-thread-workers") ;

// Accept downstream worker connections
// from remote InfiniBand processes via tcp
myEndpoint.bind("tcp://0.0.0.0:12345") ;

well now you probably have to send them the data in the ranges they are going to be working on.

I suppose I could start by just adapting a traditional parallel sort to ZeroMQ and let someone smarter than me work out a scalable variant.

One Comment

Hi,
you might be interested in the recently published paper on a scalable parallel sorting algorithm:
http://darwin.bth.rwth-aachen.de/opus3/volltexte/2010/3502/pdf/3502.pdf

Though it is concerned with the implementation in MPI, the algorithm is described in detail, and might be transferable to the ZeroMQ framework.

Leave a Reply

Name and email address are required. Your email address will not be published.

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

You may use these HTML tags and attributes:

<a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <pre> <q cite=""> <s> <strike> <strong> 

%d bloggers like this: