Loop-Level Prefix-Sum: Messed up partial sums

Question

#include <omp.h>
#include <stdio.h>


void prefix(int n, int A[n]){
    
    //end of recursion
    if(n==1) return;
    
    int n2 = n/2;
    
    //Array split
    int L[n2];
    int R[n-n2];
    
    #pragma omp parallel for
    for(int i=0; i<n2; i++){
        L[i]=A[i];
    }
    

    #pragma omp parallel for
    for(int i=n2; i<n-n2; i++){
        R[i-n2]=A[i];
    }
         
    
    //recursion
    #pragma omp task
    prefix(n2,L);
    
    #pragma omp task
    prefix(n-n2,R);
    
    #pragma omp taskwait
    #pragma omp parallel for
    for(int i = 0; i<n2; i++){
        A[n2+i]=A[n2]+A[n2+i];
    }
    for(int i = 0; i<n; i++){
        printf("%d\n",A[i]);
    }
    printf("END\n");
}

int main(){
    
    int A[4] = {1,2,3,4};
    prefix(4,A);
    
    for(int i=0;i<4;i++){
        printf("%d",A[i]);
    }
}

Outputs: 1 END 32 END 1 4 END 16 END 32 END 16 0 END 1 2 6 7 END 1267

So I know that the partial recursion sums are messed up due to 32 in the first right half. But I am currently struggling to find the reason. The initial algorithm uses arrays from 1 to n. Is it something with the ranges?

Thanks for any help.

Edit:

Now I get:

1 2 END 6684773 7864425 END 1 2 3 7 END 1237

What is it causing to fail to calculate the prefix sum?

Solved it now:

#include <omp.h>
#include <stdio.h>


void prefix(int n, int *A, int start, int end){
    
    //end of recursion
    if(n==1) return;
    
    int n2 = n/2;
    
    //recursion
    #pragma omp task
    prefix(n2,A, start, end-n2);
    
    #pragma omp task
    prefix(n-n2,A,end-n2+1, end);   
    #pragma omp taskwait
   
    #pragma omp parallel for
    for(int i = 0; i<n2; i++){
        A[end-n2+1+i]=A[end-n2]+A[end-n2+1+i];
    }
    for(int i = 0; i<n; i++){
        printf("%d\n",A[i]);
    }
    printf("END\n");
}

int main(){
    
    int A[4] = {1,1,1,1};
    prefix(4,A,0,3);
    
    for(int i=0;i<4;i++){
        printf("%d",A[i]);
    }
}

Answer 1

#include <omp.h>
#include <stdio.h>


void prefix(int n, int *A, int start, int end){
    
    //end of recursion
    if(n==1) return;
    
    int n2 = n/2;
    
    //recursion
    #pragma omp task
    prefix(n2,A, start, end-n2);
    
    #pragma omp task
    prefix(n-n2,A,end-n2+1, end);   
    #pragma omp taskwait
   
    #pragma omp parallel for
    for(int i = 0; i<n2; i++){
        A[end-n2+1+i]=A[end-n2]+A[end-n2+1+i];
    }
    for(int i = 0; i<n; i++){
        printf("%d\n",A[i]);
    }
    printf("END\n");
}

int main(){
    
    int A[4] = {1,1,1,1};
    prefix(4,A,0,3);
    
    for(int i=0;i<4;i++){
        printf("%d",A[i]);
    }
}

Answer 2

Note that the program in your answer does not give correct result if n is odd. For this simple task you do not need a recursive algorithm unless it is your homework and you have to use a recursive algorithm and OpenMP tasks. You should use a much simpler algorithm such as

void prefix(int n, int* A){    
    if (n>1) {
        int sum=A[0];
        for(int i=1; i<n;i++){
            sum+=A[i];
            A[i]=sum;
        }
    }
}