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

は、関数からの戻り値を無視しないでください、あなたのpthread呼び出しは0を返し、何が起こるかが表示されない場合perror呼び出しを追加することから始めC.に呼び出します。 RThreadとLThreadがグローバルとして宣言されているので、pthread_joinコールが失敗していることがわかります。したがって、スレッドを生成する際に新しい値を割り当て続けます。これらの宣言をParallelMergeSort関数内で宣言するようにそれらの宣言を移動してください。

アルゴリズムのソートの問題は解決しませんが、少なくとも一貫した結果が得られます。