The essence of the task is to make the usual sequential method of sorting an array parallel using MPICH. As the source code was selected this text. It is written in C ++ and I need the C language. An error is displayed on the Segmentation fault and I cannot understand why (I think that I made a mistake somewhere with dynamic memory allocation)

#include <stdio.h> #include <stdlib.h> #include <time.h> #include <mpi.h> int *result; int *sum(int* v1, int n1, int* v2, int n2) { int i=0, j=0, k=0; result = (int *)malloc((n1+n2)*sizeof(int)); while (i < n1 && j < n2) { if (v1[i] < v2[j]) { result[k] = v1[i]; i++; k++; } else { result[k] = v2[j]; j++; k++; } } if (i == n1) { while (j < n2) { result[k] = v2[j]; j++; k++; }} if(j == n2) {while (i < n1) { result[k] = v1[i]; i++; k++; }} return result; } void swap (int* v, int i, int j) { int t; t = v[i]; v[i] = v[j]; v[j] = t; } void sort (int* v, int n) { int i, j; for (i = n; i >= 0; i--) {for (j = 0; j <= i; j++) if (v[j] > v[j + 1]) {swap (v, j, j + 1);} } } int main (int argc, char **argv) { int *data; int *resultant_array; int *sub; int m, n=11000; int rank, size; int r; int s; int i; int z; int move; MPI_Status status; MPI_Init (&argc, &argv); MPI_Comm_rank (MPI_COMM_WORLD, &rank); MPI_Comm_size (MPI_COMM_WORLD, &size); if (rank == 0) { s = n /size; data = (int *)malloc(s*sizeof(int)); srand(time(NULL)); FILE *bf = fopen("unsorted", "w"); for(i = 0; i < n; i++) { data[i] = rand() % 10000; fscanf(bf,"%d\n", &data[i]); } fclose(bf); MPI_Bcast (&s, 1, MPI_INT, 0, MPI_COMM_WORLD); resultant_array = (int *)malloc(s*sizeof(int)); MPI_Scatter(data, s, MPI_INT, resultant_array, s, MPI_INT, 0, MPI_COMM_WORLD); sort (resultant_array, s); } else { MPI_Bcast (&s, 1, MPI_INT, 0, MPI_COMM_WORLD); resultant_array = (int *)malloc(s*sizeof(int)); MPI_Scatter(data, s, MPI_INT, resultant_array, s, MPI_INT, 0, MPI_COMM_WORLD); sort(resultant_array, s); } move = 1; for(move=1;move < size; move*=2) { if (rank%(2*move)==0) { if (rank + move < size) { MPI_Recv (&m, 1, MPI_INT, rank + move, 0, MPI_COMM_WORLD, &status); sub = (int *)malloc(m*sizeof(int)); MPI_Recv (sub, m, MPI_INT, rank + move, 0, MPI_COMM_WORLD, &status); resultant_array = sum(resultant_array, s, sub, m); s = s + m; } } else { int near = rank - move; MPI_Send (&s, 1, MPI_INT, near, 0, MPI_COMM_WORLD); MPI_Send (resultant_array, s, MPI_INT, near, 0, MPI_COMM_WORLD); } } if (rank == 0) { sort(data,n); for (i=0; i<n; i++) { printf("%d", resultant_array[i]); } } FILE *bfs = fopen("sort", "w"); for(i = 0; i < n; i++) { fscanf(bfs,"%d\n",&resultant_array[i]); } fclose(bfs); MPI_Finalize(); free(data); free(resultant_array); free(sub); free(result); return 0; }

I ask those who know about help. Thank.

    2 answers 2

    The easiest option is to build a program with the -g1 key (debug mode), run it from under gdb, and when it crashes, give the command to print the stack. In theory, it should show the source line on which the crash occurs.

    If this option does not work, but it is necessary:

    1. Write an interrupt handling function in which the backtrace will be called
    2. Set this function as a handler (signal)
    3. Rebuild and run.

    To display the symbolic names of functions, you need to add a key for the linker -rdynamic

      I looked carefully at the code. As always, trying to write your bike doesn’t lead to anything good. In this case, its own sorting is written, moreover, in a confusing way. Look at her carefully

        void sort (int* v, int n) { int i, j; for (i = n; i >= 0; i--) {for (j = 0; j <= i; j++) if (v[j] > v[j + 1]) {swap (v, j, j + 1);} } }

      at the first iteration over i, i = n , and in the inner loop at the last iteration j = i = n . Since n is the size of the array, in the expression v[j+1] , the output goes beyond the array. And it can lead to anything (the compiler does not insert a check for going beyond the array).

      Actually, a slight fix immediately led to the performance

       void sort (int* v, int n) { int i, j; for (i = n-1; i >= 0; i--) {for (j = 0; j < i; j++) if (v[j] > v[j + 1]) {swap (v, j, j + 1);} } }

      called, find two differences! By the way, formatting is creepy. But in si there is a good sorting function - qsort . Rewrite with its use

       // воспомогательная функция-компаратор int cmpfunc (const void * a, const void * b) { ···· return ( *(int*)a - *(int*)b ); } // собственно, завернем сортировку внутрь void sort(int* v, int n) { ····qsort(v, n, sizeof(int), &cmpfunc); }

      The conclusion remains the same, but the speed has increased many, many times. In the debug mode from 2.5 - 3 seconds to 0.04-0.05 - that is, somewhere in two orders of magnitude. Very good result.

      By the way, modern (well, how to say modern, somewhere else starting from 4.8) is a built-in tool for searching for such biacs. It is enough to compile somewhere

       gcc mpi.c -o mpi -lmpi -fsanitize=address -ggdb
      • -fsanitize=address - add checks
      • -ggdb - add debug info

      A little later I found a couple more falls - in free. The fact is that pointers are declared, but may not be initialized. But deleted - deleted. It is enough to annihilate them first. ( sub = NULL; )