]> git.somenet.org - pub/jan/parprog.git/blob - openmp/prefix/hillis.c
add newline
[pub/jan/parprog.git] / openmp / prefix / hillis.c
1 /*
2  * O(nlog n) work algorithm (Hillis-Steele)
3  */
4 #include "hillis.h"
5
6 /*
7  * Hillis/Steele, prefix sum version
8  */
9 /*
10 void algorithm (numtype x[], unsigned long size, unsigned int ops[]) {
11         numtype tmp[size];
12         unsigned long k;
13         unsigned long i;
14
15         for(k=2; k <= size; k <<=1){
16                 #pragma omp parallel for shared(x, size, ops, k) private(i)
17                 for(i = (k-1); i < size; i+=k){
18 #ifdef DEBUG
19                         printf ("x[%2li] = x[%2li] + x[%2li]; // {i:%li, k:%li}\n", i, i-k, i, i, k);
20 #endif
21                         x[i] = x[i-(k/2)] + x[i];
22                 }
23         }
24 }
25 */
26
27 /*
28  * Hillis/Steele, partial prefix sum version
29  */
30 void algorithm (numtype x[], unsigned long size, unsigned int ops[]) {
31         numtype *y;
32         unsigned long k;
33         unsigned long i;
34
35         y = malloc(size * sizeof(numtype));
36         y[0] = x[0];
37
38         for (k=1; k<size; k<<=1) {
39                 #pragma omp parallel for shared (x, y, ops, k) private (i)
40                 for (i=k; i<size; i++) {
41 #ifdef DEBUG
42                         printf ("y[%li] = x[%li] + x[%li]; // %li + %li\n", i, i-k, i, x[i-k], x[i]);
43 #endif
44                         y[i] = x[i-k]+x[i];
45                 }
46                 memcpy (x, y, size * sizeof(numtype));
47         }
48
49         if (y != NULL) {
50                 free(y);
51                 y = NULL;
52         }else{
53                 printf ("Has not been freed!!!\n");
54         }
55 }