Почему мой параллельный код медленнее последовательного?
Я реализовал параллельный код в C для сортировки слиянием с помощью OPENMP. Я получаю скорость 3,9 секунды, что значительно медленнее, чем последовательная версия того же кода(для которой я получаю 3,6). Я пытаюсь оптимизировать код до наилучшего возможного состояния, но не могу увеличить скорость. Не могли бы вы помочь мне с этим? Спасибо.
void partition(int arr[],int arr1[],int low,int high,int thread_count)
{
int tid,mid;
#pragma omp if
if(low<high)
{
if(thread_count==1)
{
mid=(low+high)/2;
partition(arr,arr1,low,mid,thread_count);
partition(arr,arr1,mid+1,high,thread_count);
sort(arr,arr1,low,mid,high);
}
else
{
#pragma omp parallel num_threads(thread_count)
{
mid=(low+high)/2;
#pragma omp parallel sections
{
#pragma omp section
{
partition(arr,arr1,low,mid,thread_count/2);
}
#pragma omp section
{
partition(arr,arr1,mid+1,high,thread_count/2);
}
}
}
sort(arr,arr1,low,mid,high);
}
}
}
2 ответа:
Это заняло некоторое время, что немного смущает, поскольку, когда вы видите это, ответ так прост.
Как это стоит в вопросе, программа не работает правильно, вместо этого она случайным образом на некоторых запусках дублирует некоторые числа и теряет другие. Это, по-видимому, полностью параллельная ошибка, которая не возникает при запуске программы с переменной thread_count == 1.
Pragma "parallel sections", представляет собой комбинированную директиву parallel and sections, которая в данном случае это означает, что он запускает вторую параллельную область внутри предыдущей. Параллельные области внутри других параллельных областей хороши, но я думаю, что большинство реализаций не дают вам дополнительных потоков, когда они сталкиваются с вложенной параллельной областью.
Исправление состоит в замене
#pragma omp parallel sectionsС
#pragma omp sectionsПосле этого исправления программа начинает давать правильные ответы, и с помощью двухъядерной системы и для миллиона чисел я получаю для синхронизации следующие результаты.
Один поток:
time taken: 0.378794Два потока:
time taken: 0.203178Поскольку директива sections содержит только две секции, я думаю, что вы не получите никакой выгоды от создания большего количества потоков, чем два в предложении parallel, поэтому измените num_threads (thread_count) - > num_threads (2)
Но из-за того, что по крайней мере две реализации, которые я пробовал, не могут порождать новые потоки для вложенных параллельных областей, программа в ее нынешнем виде не масштабируется более чем до двух потоков.
Как было правильно отмечено, в вашем коде есть несколько ошибок, которые мешают его правильному выполнению, поэтому я бы сначала предложил рассмотреть эти ошибки.
Во всяком случае, принимая во внимание только то, как производительность OpenMP масштабируется с потоком, возможно, реализация, основанная на директивах задач, подойдет лучше, поскольку она преодолевает ограничения, уже указанные предыдущим ответом:
Поскольку директива о секциях имеет только две секции, я думаю, что вы не получите никакой выгоды от нереста больше потоки, чем два в параллельном предложении
Вы можете найти след такой реализации ниже:
Обратите внимание, что если вы ищете производительность, вы также должны гарантировать, что базовый случай вашей рекурсии достаточно груб, чтобы избежать значительных накладных расходов из-за рекурсивных вызовов функций. Кроме того, я бы предложил профилировать ваш код, чтобы вы могли иметь хороший намек на то, какие части действительно стоит оптимизировать.#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <sys/time.h> void getTime(double *t) { struct timeval tv; gettimeofday(&tv, 0); *t = tv.tv_sec + (tv.tv_usec * 1e-6); } int compare( const void * pa, const void * pb ) { const int a = *((const int*) pa); const int b = *((const int*) pb); return (a-b); } void merge(int * array, int * workspace, int low, int mid, int high) { int i = low; int j = mid + 1; int l = low; while( (l <= mid) && (j <= high) ) { if( array[l] <= array[j] ) { workspace[i] = array[l]; l++; } else { workspace[i] = array[j]; j++; } i++; } if (l > mid) { for(int k=j; k <= high; k++) { workspace[i]=array[k]; i++; } } else { for(int k=l; k <= mid; k++) { workspace[i]=array[k]; i++; } } for(int k=low; k <= high; k++) { array[k] = workspace[k]; } } void mergesort_impl(int array[],int workspace[],int low,int high) { const int threshold = 1000000; if( high - low > threshold ) { int mid = (low+high)/2; /* Recursively sort on halves */ #ifdef _OPENMP #pragma omp task #endif mergesort_impl(array,workspace,low,mid); #ifdef _OPENMP #pragma omp task #endif mergesort_impl(array,workspace,mid+1,high); #ifdef _OPENMP #pragma omp taskwait #endif /* Merge the two sorted halves */ #ifdef _OPENMP #pragma omp task #endif merge(array,workspace,low,mid,high); #ifdef _OPENMP #pragma omp taskwait #endif } else if (high - low > 0) { /* Coarsen the base case */ qsort(&array[low],high-low+1,sizeof(int),compare); } } void mergesort(int array[],int workspace[],int low,int high) { #ifdef _OPENMP #pragma omp parallel #endif { #ifdef _OPENMP #pragma omp single nowait #endif mergesort_impl(array,workspace,low,high); } } const size_t largest = 100000000; const size_t length = 10000000; int main(int argc, char *argv[]) { int * array = NULL; int * workspace = NULL; double start,end; printf("Largest random number generated: %d \n",RAND_MAX); printf("Largest random number after truncation: %d \n",largest); printf("Array size: %d \n",length); /* Allocate and initialize random vector */ array = (int*) malloc(length*sizeof(int)); workspace = (int*) malloc(length*sizeof(int)); for( int ii = 0; ii < length; ii++) array[ii] = rand()%largest; /* Sort */ getTime(&start); mergesort(array,workspace,0,length-1); getTime(&end); printf("Elapsed time sorting: %g sec.\n", end-start); /* Check result */ for( int ii = 1; ii < length; ii++) { if( array[ii] < array[ii-1] ) printf("Error:\n%d %d\n%d %d\n",ii-1,array[ii-1],ii,array[ii]); } free(array); free(workspace); return 0; }