DAPPLE Example: prefix
Source code:
// @TITLE "prefix.cc -- prefix sum, manually"
//
// prefix -- prefix sum, manually
// written using the Data-Parallel Programming Library for Education (DAPPLE)
//
// Of course, DAPPLE includes a sum scan function, so this is not
// necessary, but it is a good exercise. Each time, the vector is
// shifted twice as far, and then add into itself. Note that
// the left-most M processors will add 0 after log(M) iterations.
// This solution works for any size list.
//
// David Kotz 1994
// $Id: prefix.cc,v 2.13 94/09/29 12:18:25 dfk Exp Locker: dfk $
#include
#include
#include
#include "dapple.h"
const int N = 11;
int
main(int argc, char **argv)
{
intVector v(N); // the intVector to prefix sum
intVector prefix(N); // where we get the prefix sum
int m = 1; // current shift distance
// 6 5 9 2 4 3 5 1 7 5 8
cout << "Enter vector of " << N << " integers: ";
cin >> v;
cout << endl;
prefix = shift(v, 1); // start with an initial shift
cout << prefix << endl;
while (m < N) {
prefix += shift(prefix, m); // shift it over this far
// note: left-most m processors will add 0
m *= 2; // double the distance next time
cout << prefix << endl;
}
cout << "verification:" << endl;
cout << plus_scan(v) << endl;
return(0);
}
Demonstration:
cat prefix.data
1 9 36 84 126 126 84 36 9 1 0
prefix < prefix.data
Enter vector of 11 integers:
0 1 9 36 84 126 126 84 36 9 1
0 1 10 45 120 210 252 210 120 45 10
0 1 10 46 130 255 372 420 372 255 130
0 1 10 46 130 256 382 466 502 510 502
0 1 10 46 130 256 382 466 502 511 512
verification:
0 1 10 46 130 256 382 466 502 511 512