Дать параллельную быструю сортировку в с

Обновить

December 2018

Просмотры

1.4k раз

1

Мне нужно написать параллельную быструю сортировку в с помощью Pthreads. Это то, что я сделал до сих пор.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <pthread.h>
    #include <unistd.h>  // sleep()
    #include <stdio.h>
    #include <stdlib.h>  // EXIT_SUCCESS
    #include <string.h>  // strerror()
    #include <errno.h>

    #define SIZE_OF_DATASET 6
    void* quickSort( void* data);
    int partition( int* a, int, int);


    struct info {
        int start_index;
        int* data_set;
        int end_index;
    };



    int main(int argc, char **argv)
    {

        int a[] = { 7, 12, 1, -2,8,2};
        pthread_t thread_id;
        struct info *info = malloc(sizeof(struct info));
        info->data_set=malloc(sizeof(int)*SIZE_OF_DATASET);

        info->data_set=a;
        info->start_index=0;
        info->end_index=SIZE_OF_DATASET-1;

        if (pthread_create(&thread_id, NULL, quickSort, info)) {
            fprintf(stderr, "No threads for you.\n");
            return 1;
        }

        pthread_join(thread_id, NULL);

        printf("\n\nSorted array is:  ");
        int i;
          for(i = 0; i < SIZE_OF_DATASET; ++i)
               printf(" %d ", info->data_set[i]);

        return 0;
    }

    void* quickSort( void *data)
    {
        struct info *info = data;
        int j,l,r;
        l = info->start_index;
        r = info->end_index;

        pthread_attr_t attr;
        pthread_t thread_id1;
        pthread_t thread_id2;
        pthread_attr_init(&attr);

       if( l < r )
       {

           j = partition( info->data_set, l, r);
           info->start_index=l;
           info->end_index=j-1;
           if(info->end_index<0)info->end_index=0;

          if (pthread_create(&thread_id1, NULL, quickSort, info)) {
                fprintf(stderr, "No threads for you.\n");
                return NULL;
          }
          info->start_index=j+1;
          info->end_index=r;

          if (pthread_create(&thread_id2, NULL, quickSort, info)) {
              fprintf(stderr, "No threads for you.\n");
              return NULL;
          }

          pthread_join(thread_id1, NULL);
          pthread_join(thread_id2, NULL);
      }

    return NULL;

    }


    int partition( int* a, int l, int r) {
       int pivot, i, j, t;
       pivot = a[l];
       i = l; j = r+1;

       while( 1)
       {
        do ++i; while( a[i] <= pivot && i <= r );
        do --j; while( a[j] > pivot );
        if( i >= j ) break;
        t = a[i]; a[i] = a[j]; a[j] = t;
       }
       t = a[l]; a[l] = a[j]; a[j] = t;
       return j;
    }

Но внутри функция быстрого сортировки только вызвать только первый поток. Брус понять, что здесь происходит.

Примечание: серийный вариант кода был протестирован. нет проблемы с этим

ОБНОВИТЬ:

Это модифицированная версия на основе решения Джона Боллинджера. Но все-таки вторая половина массива, который принимается вновь созданного потока внутри сортировки не сортируется.

   int main(int argc, char **argv)
{

    int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9,5,3,24,5,23,3,1,56,8,4,34,23,51};
    struct info *info = malloc(sizeof(struct info));
    info->data_set=malloc(sizeof(int)*SIZE_OF_DATASET);
    info->data_set=a;
    info->start_index=0;
    info->end_index=SIZE_OF_DATASET-1;

    quickSort(info);
    printf("\n\nSorted array is:  ");
    int i;
      for(i = 0; i < SIZE_OF_DATASET; ++i)
           printf(" %d ", info->data_set[i]);
    return 0;
}

void* quickSort( void *data)
{
    struct info *info = data;
    struct info *info1 = data;
    int j,l,r;
    l = info->start_index;
    r = info->end_index;

    pthread_attr_t attr;
    pthread_t thread_id1;
    pthread_attr_init(&attr);

   if( l < r )
   {

       j = partition( info->data_set, l, r);
       info1->start_index=j+1;
       info1->end_index=r;
       info1->data_set = info->data_set;
       if(info1->end_index<0)info1->end_index=0;

      if (pthread_create(&thread_id1, NULL, quickSort, info1)) {
            fprintf(stderr, "No threads for you.\n");
            return NULL;
      }
      info->start_index=l;
      info->end_index=j-1;

      if(info->end_index < 0) info->end_index = 0;
      quickSort(info);  /* don't care about the return value */
      pthread_join(thread_id1, NULL);

  }

return NULL;

}

1 ответы

3

The program is incorrect because your threads all share the same struct info structure describing the sub-problem they are supposed to be working on. They run concurrently (or may do, anyway) and they modify that structure as they proceed, so the values that any particular thread sees are indeterminate.

To resolve this, each quickSort frame must create at least one new struct info, so that the two quickSort() calls it makes in different threads each has its own. As a matter of efficiency, it would also be better to spawn only one additional thread in each quickSort() call. For example:

void* quickSort( void *data)
{
    struct info *info = data;
    struct info other_info;

    /* ... */

        /* launch a new thread to handle one partition: */
        other_info.start_index = j + 1;
        other_info.end_index = r;
        other_info.data_set = info->data_set;
        if (pthread_create(&thread_id1, NULL, quickSort, &other_info)) {
            fprintf(stderr, "No threads for you.\n");
            return NULL;
        }

        /* handle the other partition in the current thread: */
        info->start_index = l;
        info->end_index = j - 1;
        if(info->end_index < 0) info->end_index = 0;
        quickSort(info);  /* don't care about the return value */

        /* after this thread is done, wait for the other thread to finish, too */
        pthread_join(thread_id1, NULL);

    /* ... */
}

Note that this does not ensure that any particular pair of threads runs concurrently, neither in a multi-core sense nor in a time-slicing sense. That's up to the OS. Certainly, however, the multi-core sense of parallelism applies only where there are in fact multiple cores available on the host machine on which the OS is willing to schedule your process.

Связанные вопросы