C 并行合​​并排序有时可以工作

Question

按照本教程，我正在学习如何在 C 中并行化合并排序 http://elc.yonsei.ac.kr/courses/csi2110/PP-L05-ScalableAlgorithmicTechniques.pdf但它只是有时有效。我在终端中运行代码大约 10 次，有时会遇到段错误，有时会在数组中得到随机数，有时，它会起作用。我不确定我哪里出错了，因此我们将不胜感激任何帮助。

        #include <stdio.h> 
        #include <stdlib.h>
        #include <pthread.h> 
        #include <math.h>

        pthread_t LThread; 
        pthread_t RThread; 

        void MergeSort(float A[], int p, int r); 
        void ParallelMergeSort(float A[], int p, int r, int depth, int max_depth);
        void Merge(float A[], int p, int q, int r);

        struct arg {
            float* A;
            int p;
            int r;
            int depth;
            int max_depth;
        };

        void* PMSort(void* ptr){
            struct arg* MyArg = (struct arg*) ptr;
            ParallelMergeSort(MyArg->A, MyArg->p, MyArg->r, MyArg->depth, MyArg->max_depth);
            return 0;
        }

        void ParallelMergeSort(float A[], int p, int r, int depth, int max_depth){
            if (depth == max_depth){
                MergeSort(A, p, r);
            }
            else {
                /* 
                   1) Spawn 2 threads for left and right sub array
                   2) Join the 2 threads
                   3) Perform the merge
                */
                int q;
                if (p < r){
                    q = (p+r) / 2;
                    struct arg* LeftArg = malloc(sizeof(struct arg));
                    struct arg* RightArg = malloc(sizeof(struct arg));

                    LeftArg->A = A;
                    LeftArg->p = p;
                    LeftArg->r = q;
                    LeftArg->depth = depth + 1;
                    LeftArg->max_depth = max_depth;

                    RightArg->A = A;
                    RightArg->p = q + 1;
                    RightArg->r = r;
                    RightArg->depth = depth + 1;
                    RightArg->max_depth = max_depth;

                    pthread_create(&LThread, NULL, PMSort, (void*)LeftArg);
                    pthread_create(&RThread, NULL, PMSort, (void*)RightArg);

                    pthread_join(LThread, NULL);
                    pthread_join(RThread, NULL);
                    Merge(A, p, q, r);
                }
            }
        }

        void Merge(float A[], int p, int q, int r){
            int n1 = q -p + 1;
            int n2 = r - q;
            int i = 0; 
            int j = 0;
            int L[r];
            int R[r];
            for (i = 0; i < n1; i ++){
                L[i] = A[p + i];
            }
            for (j = 0; j < n2; j ++){
                R[j] = A[q + j + 1];
            }
            L[n1] = INFINITY;
            L[n2] = INFINITY;
            i = 0; 
            j = 0;
            for (int k = p; k <= r; k ++){
                if (L[i] <= R[j]){
                    A[k] = L[i]; 
                    i ++;
                }
                else {
                    A[k] = R[j];
                    j ++;
                }
            }
        }


        void MergeSort(float A[], int p, int r){
            int q;
            if (p < r){
                q = (p + r)/2;
                MergeSort(A, p, q);
                MergeSort(A, p+1, r);
                Merge(A, p, q, r);
            }
        }

        int main(void){  
            float array[] = {5,2,4,7,1,3,2,6};
            ParallelMergeSort(array, 0, 7, 0, 3);

            for (int i = 0; i <= 7; i ++){
                printf("%f ", array[i]);
            }
            printf("\n");
            return 0;
        }   

Answer 1

不要忽略 C 中函数调用的返回值。如果您的 pthread 调用不返回 0，请首先添加 perror 调用，然后看看会发生什么。您将看到 pthread_join 调用失败，因为您将 RThread 和 LThread 声明为全局变量。因此，当您生成线程时，您会不断地为它们重新分配新值。移动这些 pthread_t 声明，以便它们在 ParallelMergeSort 函数内声明。

这不会解决您的算法的任何排序问题，但至少您会得到一致的结果。