Multithread-Merge-Sortierung, wenn große Datenmengen nicht sortiert werden können?

Question

Hausübung

Ich Partitionieren meine Daten in kleinere Matrizen und Threads unter Verwendung der rekursiven Art zu optimieren. Meine Funktion funktioniert perfekt auf kleinen Datensätzen, bei denen die Anzahl der Elemente nicht größer als 2000 ist. Sobald die Daten jedoch größer werden, bekomme ich einige Elemente außer Betrieb und bekomme keine Speicherfehler, wenn ich Adress-Desinfektionsmittel verwende oder Valgrind. Ich habe es nicht herausgefunden. Ich habe versucht, den Pivot zu ändern, um eine if-Anweisung mit einem Modulo für gerade oder ungerade Mengen von Elementen zu haben, die durch n/2 für even und (n+1)/2 für Odd partitioniert werden, aber das hat immer noch nicht funktioniert. Kann jemand sehen, was ich verpasst habe, oder mir nur einen Hinweis geben?

// struct used for merge sort threads 
typedef struct { 
    float* m; 
    size_t n; 
} thread_arg; 

/* 
* Merge matrices together 
*/ 
void merge(float* main_matrix, float* left_matrix, int left_elements, float* right_matrix, int right_elements) { 
    // left_matrix index 
    int l = 0; 
    // right_matrix index 
    int r = 0; 
    // main_matrix index 
    int m = 0; 

    while (l < left_elements && r < right_elements) { 
     if (left_matrix[l] < right_matrix[r]) { 
      main_matrix[m++] = left_matrix[l++]; 
     } else { 
      main_matrix[m++] = right_matrix[r++]; 
     } 
    } 

    while (l < left_elements) { 
     main_matrix[m++] = left_matrix[l++]; 
    } 

    while (r < right_elements) { 
     main_matrix[m++] = right_matrix[r++]; 
    } 
} 

/* 
* Threaded merge sort 
*/ 
void* merge_sort(void* arg) { 
    thread_arg* t_arg = (thread_arg*) arg; 

    // base case 
    if (t_arg->n < 2) { 
     return NULL; 
    } 

    size_t pivot = (t_arg->n/2); 

    // left and right sub-matrices 
    float* left_matrix = malloc(sizeof(float) * pivot); 
    float* right_matrix = malloc(sizeof(float) * (t_arg->n - pivot)); 

    // fill left_matrix 
    for (size_t i = 0; i < pivot; i++) { 
     left_matrix[i] = t_arg->m[i]; 
    } 

    // fill right_matrix 
    for (size_t i = pivot; i < t_arg->n; i++) { 
     right_matrix[(i - pivot)] = t_arg->m[i]; 
    } 

    // create structs for recursive thread call 
    thread_arg t_arg1 = (thread_arg) { 
     .m = left_matrix, 
     .n = pivot 
    }; 
    thread_arg t_arg2 = (thread_arg) { 
     .m = right_matrix, 
     .n = (t_arg->n - pivot) 
    }; 

    // create threads and send structs to sort recursively 
    pthread_t thread1; 
    pthread_t thread2; 
    pthread_create(&thread1, NULL, merge_sort, &t_arg1); 
    pthread_create(&thread2, NULL, merge_sort, &t_arg2); 
    // join threads to retrieve sorted sub-matrices 
    pthread_join(thread1, NULL); 
    pthread_join(thread2, NULL); 

    // Merge left_matrix and right_matrix into sorted matrix. 
    merge(t_arg->m, left_matrix, pivot, right_matrix, (t_arg->n - pivot)); 

    // free left and right matrices 
    free(left_matrix); 
    free(right_matrix); 

    return NULL; 
} 

/** 
* Returns sorted matrix. 
*/ 
float* sort(float* matrix) { 
    float* result = cloned(matrix); 

    // structs for threaded merge sort 
    thread_arg t_arg = (thread_arg) { 
     .m = result, 
     .n = g_elements 
    }; 

    merge_sort(&t_arg); 

    return result; 
} 

Answer 1

Das Problem schien nicht zu überprüfen, ob der pthread_create fehlschlägt. Indem Sie den Code für eine Überprüfung ändern, können Sie einen Thread ohne Thread ausführen, wenn alle Threads verwendet werden. Hier ist ein Pseudo-Code.

// create threads and send structs to recursively sort 
pthread_t thread1; 
if (pthread_create(&thread1, NULL, merge_sort, &t_arg1) != 0 || t_arg->n_threads == MAX_THREADS) { 
    merge_sort(&t_arg1); 
} else { 
    no. of threads++ 
} 

merge_sort(&t_arg2); 

pthread_join(thread1, NULL); 
no. of threads-- 

Answer 2

Ich denke, dass Sie eine Race-Bedingung haben, da ich keine Sperren sehe. Sie müssen Ihre gemeinsamen Daten gegen den gleichzeitigen Zugriff mehrerer Threads schützen.