Parallel sorting

After my problems with parallel_scan, I approached parallel_sort with some trepidation. I was pleasantly surprised when parallel_sort worked as advertised. (I did have a few problems, but these were related to my C++ skills and not to TBB directly.)

The simple program shown below generates a vector of randomly-spaced, three-dimensional points and sorts them in ascending order based on their distance from the origin:

// example5.cpp : Defines the entry point for the console application.
//

#include “stdafx.h”
#include #include
#include
#include “tbb/task_scheduler_init.h”
#include “tbb/parallel_sort.h”

using namespace tbb;
using namespace std;

// 3-D point object
class point {
public:
double x, y, z; // point coordinates
// compute the distance from the point to the origin
double radius() const { return sqrt(x*x + y*y + z*z); }
// operator that determines which point is closer to the origin
bool operator< (const point& that) const { return radius() < that.radius(); } }; int _tmain(int argc, _TCHAR* argv[]) { // create a vector of points randomly distributed in space vector points(10000);
for(size_t i=0; i());

// check to make sure the points are sorted correctly
for(size_t i=1; iparallel_sort is on line 38. I just passed it a pair of iterators that point to the beginning and end of the vector of point objects. I also passed a function object, less, that makes use of the < operator (line 21) and radius method (line 19) in point to determine which 3-D point is closer to the origin. Upon return from parallel_sort, the points are properly ordered by their distance from the origin. It’s really no harder than calling a standard sort subroutine, with the added benefit of a speedup from parallel execution.

You can also do this with standard arrays instead of STL objects like vectors and lists. Just pass pointers to the beginning and ending of the array instead of iterators. And, obviously, you can sort in a different direction by supplying a different function object, e.g. greater.

Here’s the source code for this example if you want to try it.

About dave_vandenbout
President of XESS Corp, a manufacturer of FPGA development boards.

One Response to Parallel sorting

  1. rahul says:

    hey hi can u plz help me to implement string matching algorithm for dna sequencing on cuda?

Leave a Reply

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

%d bloggers like this: