openmp/prefix/hillis_sum.c

   1 /*
   2  * O(nlog n) work algorithm (Hillis-Steele)
   3  */
   4 #include "hillis_partial.h"
   5
   6 /*
   7  * Hillis/Steele, prefix sum version
   8  */
   9 void algorithm (numtype x[], unsigned long size, unsigned int ops[]) {
  10         numtype tmp[size];
  11         unsigned long k;
  12         unsigned long i;
  13
  14         for(k=2; k <= size; k <<=1){
  15                 #pragma omp parallel for shared(x, size, ops, k) private(i)
  16                 for(i = (k-1); i < size; i+=k){
  17 #ifdef DEBUG
  18                         printf ("x[%2li] = x[%2li] + x[%2li]; // {i:%li, k:%li}\n", i, i-k, i, i, k);
  19 #endif
  20                         x[i] = x[i-(k/2)] + x[i];
  21                 }
  22         }
  23 }
  24