0

Суть задания - сделать обычный последовательный метод сортировки массива параллельным при помощи MPICH. В качестве исходника был выбран этот текст программы. Он написан на С++ а мне нужен язык Си. Выводится ошибка Segmentation fault и не могу понять из-за чего( думаю, где то допустил ошибку с динамическим выделением памяти)

    #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;
       }

Прошу знающих о помощи. Спасибо.

2 ответа 2

1

Самый простой вариант - собрать программу с ключом -g1 (режим отладки), запустить её из под gdb и когда она упадёт, дать команду распечатки стека. По идее, он должен показать строку исходного текста, на которой происходит падение.

Если такой вариант не проходит, но надо:

  1. Написать функцию обработки прерывания, в которой будет вызываться backtrace
  2. Задать эту функцию в качестве обработчика (signal)
  3. Пересобрать и запустить.

Что бы выводились символические имена функций, необходимо добавить ключ для линкера -rdynamic

1

Посмотрел внимательно на код. Как всегда, попытка написать свой велосипед ни к чему хорошему не приводит. В данном случае написана своя сортировка, причем, запутанным способом. Посмотрим на нее внимательно

 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);}
   }
  }

при первой итерации по i, i = n, а в внутреннем цикле на последней итерации j = i = n. Так как n - размер массива, то в выражении v[j+1] происходит выход за пределы массива. А он может привести к чему угодно (си компилятор не вставляет проверку выхода за пределы массива).

Собственно, легкое исправление сразу привело к работоспособности

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);}
  }
}

называется, найдите два отличия! Кстати, форматирование - жуткое. Но в си есть хорошая функция для сортировки - qsort. Перепишем с ее использованием

// воспомогательная функция-компаратор
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);
}

вывод остался тот же, но скорость возросла в много-много раз. В отладочном режиме с 2.5 - 3 секунд до 0.04-0.05 - то есть, где то на два порядка. Очень хороший результат.

Кстати, современный (ну как сказать современный, где то ещё начиная с 4.8) представляет встроенный инструмент для поиска подобных бяк. Достаточно скомпилировать где то так

gcc mpi.c -o mpi -lmpi -fsanitize=address -ggdb
  • -fsanitize=address - добавить проверок
  • -ggdb - добавить отладочной информации

Чуть позже нашел ещё пару падений - в free. Дело в том, что указатели объявляются, но могут не быть инициализированы. А вот удалятся - удаляются. Достаточно их вначале занулить. (sub = NULL;)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.