C Parallel merge sort arbeiten manchmal

Question

Ich lerne, wie die Parallelliste sortieren in C nach diesem Tutorial http://elc.yonsei.ac.kr/courses/csi2110/PP-L05-ScalableAlgorithmicTechniques.pdf Aber es funktioniert nur manchmal. Ich führe den Code im Terminal ungefähr 10 Mal aus, und manchmal bekomme ich einen Segmentierungsfehler, zu anderen Zeiten bekomme ich Zufallszahlen in meinem Array oder manchmal funktioniert es. Ich bin mir nicht sicher, wo ich falsch liege, also wäre jede Hilfe sehr geschätzt.

 #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

Ignorieren Sie nicht die Rückgabewerte von Funktion in C durch perror Anrufe Hinzufügen Beginnen Sie ruft, wenn Ihre pthread Anrufe nicht 0 zurück und sehen, was passiert. Sie werden sehen, dass die pthread_join Aufrufe fehlschlagen, weil Sie RThread und LThread als globale deklariert haben. Daher weisen Sie ihnen immer wieder neue Werte zu, wenn Sie Threads spawnen. Verschieben Sie diese pthread_t Deklarationen so, dass sie stattdessen in der ParallelMergeSort-Funktion deklariert werden.

Das wird keine Sortierprobleme mit Ihrem Algorithmus beheben, aber zumindest werden Sie konsistente Ergebnisse erhalten.