2 * O(nlog n) work algorithm (Hillis-Steele)
4 #include "hillis_sum.h"
7 * Hillis/Steele, prefix sum version
9 unsigned long is_power_of_two(unsigned long var) {
14 if ((var & 0x1) == 0x1) {
22 void algorithm (numtype x[], unsigned long size, unsigned int ops[]) {
26 if (is_power_of_two(size) != 1) {
27 fprintf(stderr, "Hillis-Sum algorithm only works on arrays on size 2^n\n");
31 for(k=2; k <= size; k <<=1){
32 #pragma omp parallel for shared(x, size, ops, k) private(i)
33 for(i = (k-1); i < size; i+=k){
35 printf ("x[%2li] = x[%2li] + x[%2li]; // {i:%li, k:%li}\n", i, i-k, i, i, k);
37 x[i] = x[i-(k/2)] + x[i];