0 
#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]);
    }
}

输出：1 END 32 END 1 4 END 16 END 32 END 16 0 END 1 2 6 7 END 1267

所以我知道部分递归和由于前半部分的 32 而被弄乱了。但我目前正在努力寻找原因。初始算法使用从 1 到 n 的数组。它与范围有关吗？

谢谢你的帮助。

编辑：

现在我得到：

1 2 结束 6684773 7864425 结束 1 2 3 7 结束 1237

是什么导致无法计算前缀和？

现在解决了：

#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]);
    }
}
4

2 回答 2

0 
#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]);
    }
}
于 2021-08-22T01:05:08.147 回答
0

n请注意，如果是奇数，您答案中的程序不会给出正确的结果。对于这个简单的任务，您不需要递归算法，除非它是您的家庭作业并且您必须使用递归算法和 OpenMP 任务。您应该使用更简单的算法，例如

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;
        }
    }
}
于 2021-08-22T04:57:11.723 回答