DAPPLE Example: oddeven
Source code:
// @TITLE "oddeven.cc -- odd-even transposition sort"
//
// oddeven -- an odd-even transposition sort routine
// written using the Data-Parallel Programming Library for Education (DAPPLE)
//
// In this sort, values are bubbled from one end to the other as
// needed. In each iteration, first the odd VPs then the even VPs
// look to the right to compare their value with their neighbor.
// This is done in parallel by all VPs. They then decide where the
// two values should end up, initializing a permutation vector. The
// permutation puts the values in the right places, but never moves
// a value more than one step at a time.
//
// David Kotz 1994
// $Id: oddeven.cc,v 2.13 94/09/29 12:18:12 dfk Exp Locker: dfk $
#include
#include
#include "dapple.h"
const int N = 11;
// which VP am I?
const intVector VP(N, Identity);
#define ITERATIONS ((N+1)/2) // ceil(N/2)
const int data[N] = {6, 5, 9, 2, 4, 3, 5, 1, 7, 5, 8};
int
main(int argc, char **argv)
{
intVector X(N, data); // the main data array
intVector P(N); // permutation vector
cout << "Initial: " << X << endl;
// We do about N/2 iterations.
// In each iteration, we do two compare & swaps (in parallel):
// first, all pairs (i, i+1), where i is ODD, are compared and swapped.
// then, all pairs (i, i+1), where i is EVEN, are compared and swapped.
// Note that each compare or swap involves both the even and the
// odd processors, so we can't restrict the active set in any way.
// For example; it would seem obvious to restrict the active set to
// the odds, and have them compare and possibly swap with the item
// to the right. Thus, that neighbor must be active. To avoid this
// inconvenience, perhaps I should allow actives to somehow
// store to inactives; eg, a shift() that could be used as an lvalue.
for (int iter = 0; iter < ITERATIONS; iter++) {
// ODDS look right, evens look left
P = VP;
ifp ((VP < N-1) && odd(VP) && (X > shift(X, -1)))
P = VP+1; // send it right
ifp ((VP > 0) && even(VP) && (X < shift(X, 1)))
P = VP-1; // send it left
X = permute(X, P);
// EVENS look right, odds look left
P = VP;
ifp ((VP < N-1) && even(VP) && (X > shift(X, -1)))
P = VP+1; // send it right
ifp ((VP > 0) && odd(VP) && (X < shift(X, 1)))
P = VP-1; // send it left
X = permute(X, P);
cout << "After iteration " << iter << ": " << X << endl;
}
return(0);
}
Demonstration:
oddeven
Initial: 6 5 9 2 4 3 5 1 7 5 8
After iteration 0: 5 6 2 9 3 4 1 5 5 7 8
After iteration 1: 2 5 3 6 1 9 4 5 5 7 8
After iteration 2: 2 3 1 5 4 6 5 9 5 7 8
After iteration 3: 1 2 3 4 5 5 5 6 7 9 8
After iteration 4: 1 2 3 4 5 5 5 6 7 8 9
After iteration 5: 1 2 3 4 5 5 5 6 7 8 9