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