Параллельное слияние-сортировка в OpenMP

Question

Параллельное слияние-сортировка в OpenMP

Я видел алгоритм параллельной сортировки слиянием в этот бумага. Это код:

void mergesort_parallel_omp (int a[], int size, int temp[], int threads)
{
if ( threads == 1)       { mergesort_serial(a, size, temp); }
else if (threads > 1)
{
#pragma omp parallel sections
{
#pragma omp section
mergesort_parallel_omp(a, size/2, temp, threads/2);
#pragma omp section
mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2, threads - threads/2);
}
merge(a, size, temp);
} // threads > 1
}

Я запускаю его на многоядерном компьютере. Что происходит, так это то, что на листьях дерева 2 потока работают параллельно. После того, как они закончили свою работу, запускаются 2 других потока и так далее. Даже если у нас есть свободные ядра для всех листовых узлов.

Я думаю, что причина в том, что этот код OpenMP не создает параллельные области внутри параллельных областей. Я прав?

6

c++openmp parallel-processing sections

Решение

Другие решения

Современный ответ на этот вопрос заключается в использовании задач вместо разделов. Задачи были добавлены в OpenMP 3.0 (2009) и работают лучше / проще, чем вложенный параллелизм и разделы, потому что вложенный параллелизм может привести к переподписке (больше активных потоков, чем доступных процессоров), что приводит к значительному снижению производительности. С задачами у вас есть одна группа потоков, соответствующих количеству процессоров, и они будут работать над задачами. Таким образом, вам не нужно ручное управление с threads параметр. Простое решение выглядит так:

// span parallel region outside once outside
void mergesort_omp(...) {
#pragma omp parallel
#pragma omp single
mergesort_parallel_omp(...)
}void mergesort_parallel_omp (int a[], int size, int temp[])
{
#pragma omp task
mergesort_parallel_omp(a, size/2, temp);

mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2);

#pragma omp taskwait
merge(a, size, temp);
}

Однако все еще может быть проблематично создавать задачи для слишком маленьких частей работы, поэтому полезно ограничить параллелизм на основе детализации работы, например, в качестве таких:

void mergesort_parallel_omp (int a[], int size, int temp[])
{
if (size < size_threshold) {
mergesort_serial(a, size, temp);
return;
}
#pragma omp task
mergesort_parallel_omp(a, size/2, temp);

mergesort_parallel_omp(a + size/2, size - size/2, temp + size/2);

#pragma omp taskwait
merge(a, size, temp);
}

2

Может быть, я здесь полностью упускаю из виду … но знаете ли вы, что вам нужно установить переменную среды OMP_NUM_THREADS, если вы хотите выполнять в более чем 2 потоках?

0

Источник

Accepted Answer

«Я думаю, причина в том, что OpenMP не может создавать параллельные регионы внутри параллельных регионов»

Вы можете иметь параллельный регион параллельного региона.

OpenMP параллельные регионы могут быть вложенными друг в друга. Если вложенными
параллелизм отключен, тогда новая команда, созданная потоком
встреча параллельной конструкции внутри параллельной области состоит
только встречной ветки. Если вложенный параллелизм включен,
тогда новая команда может состоять из более чем одного потока (источник).

Для правильного запуска вашего кода вам нужно позвонить omp_set_nested(1) а также omp_set_num_threads(2),

Вложенный параллелизм можно включить или отключить, установив
Переменная среды OMP_NESTED или вызывающая функция omp_set_nested ()

7