DAPPLE Example: qsort0
Source code:
// @TITLE "qsort.cc -- parallel quicksort"
//
// qsort -- an parallel quicksort routine
// written using the Data-Parallel Programming Library for Education (DAPPLE)
//
// This parallel quicksort recurses through smaller and smaller subsets
// of the list, as with any quicksort; we track the current subset by
// using DAPPLE's dynamic active-set facility. That is, only those processors
// in the current subset are active. The recursive quicksort routine
// can tell the size of the list with an n_active reduction,
// pick a splitter, and then compare all active elements against the splitter
// in parallel. It builds a permutation vector for these elements,
// so that each element knows where it should go in the partitioned
// subset, and permutes. Then it recurses on the two partitions.
//
// David Kotz 1994
// $Id: qsort.cc,v 2.13 94/09/29 12:18:32 dfk Exp $
#include
#include
#include "dapple.h"
// #define DEBUG // turns on some debugging output
const int N = 11;
// which VP am I? useful for VP-specific math
const intVector VP(N, Identity);
const int data[N] = {16, 15, 19, 12, 14, 13, 15, 11, 17, 15, 18};
const intVector ONE(N, 1); // vector with all elements == 1
void quicksort(intVector& X);
int
main(int argc, char **argv)
{
intVector X(N, data); // the main data array
cout << "Initial: " << X << endl;
quicksort(X);
cout << "Final: " << X << endl;
return(0);
}
// @SUBTITLE "quicksort - sort a vector"
// the sort is done in place, ie, X is updated
void
quicksort(intVector& X)
{
int n = n_active(X); // how big is this sublist?
#ifdef DEBUG
cout << "start quicksort subset: " << endl;
cout << "VP " << VP << endl;
cout << "X " << X << endl;
cout << endl;
#endif
// check the number of active processors (ie, size of our sublist)
if (n <= 1)
; // do nothing
else if (n == 2) {
// too small to recurse, so just check to see if we need to swap
int largest = max_value(X);
int smallest = min_value(X);
ifp (VP == first(VP))
X = smallest; // first one get smallest
else
X = largest; // second one gets largest
} else { // n >= 3
intVector P(N); // permutation vector
int splitter; // splitter value
int left, middle, right; // first VP# in each subset
// pick a splitter; for now I'll just use the first value
splitter = first(X);
left = first_index(X); // which VP holds the splitter?
#ifdef DEBUG
cout << "splitter value " << splitter << endl;
#endif
// find the left half, those less than or equal to splitter
// except for that first one...
ifp (X <= splitter && VP != left) {
// compute our destination in the result vector
// they begin at the first active VP,
P = left + plus_scan(ONE);
middle = left + n_active(X); // rest will begin here
}
// move the splitter into the middle
ifp (VP == left) {
P = middle; // route it there
right = middle + 1; // the rest will begin here
}
// do the right half, those greater than the splitter
ifp (X > splitter) {
// compute our destination in the result vector
// starting where we left off above
P = right + plus_scan(ONE);
}
#ifdef DEBUG
cout << "left " << left << "; middle " << middle
<< "; right " << right << endl;
cout << "P " << P << endl;
#endif
X = permute(X, P); // partition the data
ifp (VP < middle)
quicksort(X); // sort the left half
ifp (VP > middle)
quicksort(X); // sort the right half
}
#ifdef DEBUG
cout << "end quicksort subset: " << endl;
cout << "VP " << VP << endl;
cout << "X " << X << endl;
cout << endl;
#endif
}
Demonstration:
qsort0
Initial: 16 15 19 12 14 13 15 11 17 15 18
Final: 11 12 13 14 15 15 15 16 17 18 19