DAPPLE Example: oddeven2
Source code:
// @TITLE "oddeven2.cc -- odd-even transposition sort"
//
// oddeven2 -- an odd-even transposition sort routine
// written using the Data-Parallel Programming Library for Education (DAPPLE)
// this version is different, with idea from Parallaxis example
//
// Iterations alternate between "odd" and "even" iterations, in terms of
// which VPs do the comparison. Basically, every VP collects the value
// of the VP to the left and to the right, and then half compare their
// value with that to the right; if a swap is needed, they set a "swap"
// flag and keep their right value. The swap flag is shifted right, and
// VPs who now have a true swap flag will keep their left value.
//
// David Kotz 1994
// $Id: oddeven2.cc,v 2.13 94/09/29 12:18:14 dfk Exp Locker: dfk $
#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] = {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 Xleft(N), Xright(N); // value of X to the left or to the right
booleanVector swap(N); // boolean flag
cout << "Initial: " << X << endl;
// We do N iterations.
// In each iteration, we shift the vector left and right by one,
// then compare against the original.
for (int iter = 0; iter < N; iter++) {
Xleft = shift(X, 1); // for any VP, Xleft contains X from the left
Xright = shift(X, -1); // and Xright contains X from the right
swap = false; // default is no swap
// we alternate behaviors in each iteration
if (odd(iter)) {
// ODD iteration: odd processors do comparison
ifp (odd(VP) && (VP < N-1) && Xright < X) {
X = Xright; // start the swap, by keeping Xright here
swap = true; // we'll finish the swap below
}
} else {
// EVEN iteration: even processors do comparison
ifp (even(VP) && (VP < N-1) && Xright < X) {
X = Xright; // start the swap, by keeping Xright here
swap = true; // we'll finish the swap below
}
}
// shift our swap flag over; anywhere it is true, the
// VP to the left decided to swap, and kept our value
// (the value to its right). So we need to keep its value
// (the value to our left).
ifp (shift(swap, 1))
X = Xleft;
cout << "After iteration " << iter << ": " << X << endl;
}
return(0);
}
Demonstration:
oddeven2
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: 5 2 6 3 9 1 4 5 5 7 8
After iteration 2: 2 5 3 6 1 9 4 5 5 7 8
After iteration 3: 2 3 5 1 6 4 9 5 5 7 8
After iteration 4: 2 3 1 5 4 6 5 9 5 7 8
After iteration 5: 2 1 3 4 5 5 6 5 9 7 8
After iteration 6: 1 2 3 4 5 5 5 6 7 9 8
After iteration 7: 1 2 3 4 5 5 5 6 7 8 9
After iteration 8: 1 2 3 4 5 5 5 6 7 8 9
After iteration 9: 1 2 3 4 5 5 5 6 7 8 9
After iteration 10: 1 2 3 4 5 5 5 6 7 8 9