我正在学习如何按照本教程对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;
        }

最佳答案

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

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

关于c - C并行合并排序有时工作,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/37895715/

10-13 08:18