#c #openmp #mergesort
#c #openmp #слияние
Вопрос:
Я изучаю параллельное программирование и пытаюсь распараллелить 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]; }
Комментарии:
1. Я бы попробовал то, что вы написали в своем вопросе. Разделите массив на 8 массивов (логически, используя 8 пар индексов). Используйте 8 «потоков» для объединения сортировки 8 массивов, затем 4 «потока» для объединения 4 пар массивов в 4 массива, затем 2 «потока» для объединения 2 пар массивов в 2 массива и 1 «поток» для объединения 1 пары в 1 массив.
Ответ №1:
Прежде всего, переместите #pragma omp parallel
в основную, так как несколько параллельных секций не должны быть вложенными (для повышения производительности, так как это создаст новую параллельную секцию для каждого потока).
Затем не используйте sections
/ section
, так как это не делается для такого использования. Вместо этого используйте задачи. Задачи могут быть отправлены рекурсивно, как то, что вы хотите сделать. Вы можете дождаться выполнения задач с помощью a taskwait
(обычно перед слиянием).
Поскольку задачи стоят дорого, вам следует подумать о том, чтобы не создавать слишком много задач. Вы можете управлять тем, хотите ли вы создать задачу или нет, используя if
предложение.
Не забудьте освободить выделенные данные в основной функции.
Комментарии:
1. Одно дополнение: если OP хочет отслеживать уровень рекурсии, в функции необходим новый параметр
mergesort
, который можно использовать вif
предложении, чтобы прекратить создание дополнительных задач. (Я не уверен, что это очевидно для ОП)