Блог

Я изучаю параллельное программирование и пытаюсь распараллелить mergesort таким образом, чтобы количество потоков равнялось количеству уровней рекурсии. Разделите массив на 8 подмассивов и используйте каждый поток для каждого подмассива. Я не хочу использовать pthreads. Я публикую последовательный код. Пожалуйста, расскажите мне, как я могу использовать команды #pragma и распараллеливать алгоритм.

 #include lt;stdlib.hgt;  #include "omp.h"  void mergesort(int a[],int i,int j); void merge(int a[],int i1,int j1,int i2,int j2);  int main() {  int *a, num, i;  scanf("%d",amp;num);   a = (int *)malloc(sizeof(int) * num);  for(i=0;ilt;num;i  )  scanf("%d",amp;a[i]);    mergesort(a, 0, num-1);    printf("nSorted array :n");  for(i=0;ilt;num;i  )  printf("%d ",a[i]);    return 0; }  void mergesort(int a[],int i,int j) {  int mid;  int tid;   if(ilt;j)  {  mid=(i j)/2;  //tid=omp_get_thread_num;  #pragma omp parallel sections   ct=omp_get_num_threads(3);  {   //printf("%d",tid);  #pragma omp section  {  mergesort(a,i,mid); //left recursion  }   #pragma omp section  {  mergesort(a,mid 1,j); //right recursion  }  }   merge(a,i,mid,mid 1,j); //merging of two sorted sub-arrays  } }   void merge(int a[],int i1,int j1,int i2,int j2) {  int temp[1000]; //array used for merging  int i,j,k;  i=i1; //beginning of the first list  j=i2; //beginning of the second list  k=0;    while(ilt;=j1 amp;amp; jlt;=j2) //while elements in both lists  {  if(a[i]lt;a[j])  temp[k  ]=a[i  ];  else  temp[k  ]=a[j  ];  }    while(ilt;=j1) //copy remaining elements of the first list  temp[k  ]=a[i  ];    while(jlt;=j2) //copy remaining elements of the second list  temp[k  ]=a[j  ];    //Transfer elements from temp[] back to a[]  for(i=i1,j=0;ilt;=j2;i  ,j  )  a[i]=temp[j]; }  

Прежде всего, переместите #pragma omp parallel в основную, так как несколько параллельных секций не должны быть вложенными (для повышения производительности, так как это создаст новую параллельную секцию для каждого потока).

Затем не используйте sections / section , так как это не делается для такого использования. Вместо этого используйте задачи. Задачи могут быть отправлены рекурсивно, как то, что вы хотите сделать. Вы можете дождаться выполнения задач с помощью a taskwait (обычно перед слиянием).

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

Не забудьте освободить выделенные данные в основной функции.