C-OpenMP/尝试将递归代码与任务并行化，但速度较慢

Question

来自墨西哥的问候!

我面临着并行化一些涉及递归的代码的任务，在做了一些研究之后，我意识到最好的方法是利用 omp 的任务。然而，它的运行时间似乎比它的串行版本要大得多。

我知道这个问题已在本论坛中被问过多次，但似乎没有一个建议的解决方案适合我的情况。

下面我添加我的代码。 infijaParallelSearch() 接收 BST 的头部和要查找的值，如果它在树中，则返回节点。 convertToBST() 接收排序列表并将其转换为返回头部的二叉搜索树。

typedef struct node
{
    int key;
    struct node *left;
    struct node *right;
} Node;


Node* convertToBST(int* array, int size) {
    if( size == 1)
        return NULL;
    Node* root= (Node*)malloc(sizeof(Node));
    if(root == NULL)
    {
        printf("Error creating a new node.\n");
        exit(0);
    }
    root->key=array[size/2-1];
    root->left=convertToBST(array,size/2);
    root->right=convertToBST(array+size/2,size-size/2);
    return root;
}

Node* infijaParallelSearch(Node* root, int x){
    if( root == NULL)
        return NULL;
    if( root->key == x )
        return root;
    #pragma omp task firstprivate(root)
        infijaParallelSearch(root->left,x);

    infijaParallelSearch(root->right,x);
}

当我使用长度递增的列表运行它以将其运行时间与其串行对应物进行比较时，我得到:Runtime results

我正在使用 omp_get_wtime() 测量时间，我几乎尝试了所有方法，从单次遍历到多次遍历，但似乎没有什么不同。如果代码的长度低于并行代码性能更好的值，我也考虑过将代码串行制作，但在多次运行代码后，该值似乎不存在。

再次感谢您的宝贵时间。这是我第一次提问，我希望我没有以任何方式含糊其辞。我是初学者，我只是在培养我对编码的热情，因此非常感谢任何帮助或建议。

PS:我不知道这是否会有所不同，但我在下面添加了代码，用于比较两种代码的运行时间。

    int main(){
    int i,*ptrA,n=10;
    double startTime, normalTime, parallelTime;
    FILE *fPtr;

    fPtr=fopen("statistics.txt","w");
        if(fPtr == NULL){
            printf("File cannot be created");
            exit(0);
        }
    while(n<=100000){
        printf("\nTamaño: %d\t",n);

        ptrA = (int*)calloc(n,sizeof(int));
        if (ptrA == NULL)
        {
            printf("Error 401. Memory not available");
            exit(0);
        }


        for (i=0;i<n;i++){
            ptrA[i]=i+1;
        }
        Node *root=convertToBTS(ptrA,n);

        startTime=omp_get_wtime();
        infijaParallelSearch(root,-1);
        normalTime=omp_get_wtime()-startTime;
        printf("Parallel final Time: %f\t",normalTime);

        for (i=0;i<n;i++){
            ptrA[i]=i+1;
        }

        root=convertToBTS(ptrA,n);

        startTime=omp_get_wtime();
        infijaSearch(root,-1);
        parallelTime=omp_get_wtime()-startTime;
        printf("Normal final Time: %f\n",parallelTime);
        free(ptrA);

        fprintf(fPtr,"%d::%f::%f\n",n,normalTime,parallelTime);

        n+=100;
    }
    fclose(fPtr);
    return 0;
}

Answer 1

首先，您假设并行搜索会独立于数据大小提高性能是错误的。根据您的运行时结果，我们可以得出结论，即使对于您在序列化版本中提供的数组大小，总运行时间更快，但与并行版本相比，随着大小的增加，它肯定会变得更糟。

例如，在将数组大小增加近 10 倍(从 100 到 ~10000)的同时，序列化版本的性能降低了 50 倍。但是并行版本只慢了大约 40 倍(这意味着并行版本的性能提升更好)。

这让我假设如果数据集足够大，并行版本的性能会优于序列化版本。

为什么会这样？无论您在这里选择如何实现并发，产生新任务(线程)都会带来开销，在您的情况下，与您要完成的每个工作项作业相比，它恰好很大。