DAPPLE Example: qsort
Source code:
// qsort -- a parallel quicksort program
// 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.
// Each recursive call acts only on the elements that correspond to
// active VPs, and assigns values to the permutation vector only for those
// VP. On return from quicksortr, the permutation vector holds the
// values of the eventual position in the sorted output list for each
// of the currently active VPs.
//
// David Kotz 1994
// $Id: qsort.cc,v 2.15 95/02/26 18:34:34 dfk Exp $
#include
#include
#include "dapple.h"
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};
void quicksort(intVector& X);
intVector quicksortr(const intVector& X, const int left);
int
main(int argc, char **argv)
{
intVector X(N, data); // X the main data array, initialized here
cout << "Initial: " << X << endl;
quicksort(X);
cout << "Final: " << X << endl;
return(0);
}
// @SUBTITLE "quicksort - sort a vector"
// We call an auxiliary function quicksortr to determine the permutation
// needed to sort X, and then we actually sort X by permuting it.
// The permutation vector is simply a list of N values, one for each
// data value in X, that are the *position* in the sorted list where that
// data element should go.
void
quicksort(intVector& X) // X is input and output
{
intVector P(N); // a permutation vector
P = quicksortr(X, 0); // find the permutation needed to sort X
cout << "Permutation: " << P << endl;
X = permute(X, P); // permute X according to P
}
// @SUBTITLE "quicksortr - the recursive part"
// X is not changed here. We are responsible for filling in P;
// well, that part of P corresponding to the current active set.
// X is the vector to sort.
// "left" is the destination VP for the leftmost element of the sorted
// set of integers represented by the current active set of VPs.
// returns a permutation vector giving the final destination of
// every element in the active set.
intVector // a permutation vector
quicksortr(const intVector& X, const int left)
{
int n = n_active(X); // how big is this sublist?
intVector P(N); // the result
// check the number of active processors (ie, size of our sublist)
if (n <= 0)
; // do nothing
else if (n == 1)
P = left; // the one element goes right THERE
else if (n == 2) {
// too small to recurse, so just check to see if we need to swap
ifp (VP == min_index(X))
P = left; // left one get smallest
else
P = left+1; // next one gets largest
} else { // n >= 3
int splitter; // splitter value
int splitVP; // VP# that holds the splitter value
int middle, right; // starting position of subsets
// pick a splitter; for simplicity I'll just use the first value
splitter = first(X);
splitVP = first_index(X); // which VP holds the splitter?
// find the left half, those less than or equal to splitter
// except for that first one...
ifp (X <= splitter && VP != splitVP) {
// compute our destination in the result vector
P = quicksortr(X, left);
middle = left + n_active(X); // rest will begin here
}
// move the splitter into the middle
ifp (VP == splitVP) {
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
P = quicksortr(X, right);
}
}
return P;
}
Demonstration:
qsort
Initial: 16 15 19 12 14 13 15 11 17 15 18
Permutation: 7 6 10 1 3 2 4 0 8 5 9
Final: 11 12 13 14 15 15 15 16 17 18 19