Ошибки в коде в вопросе
С приведённым кодом много проблем, как методологических, так и алгоритмических, и, само собой, в работе с openmp
. Вот то что бросилось в глаза:
- Массив слишком мал, чтобы оценить или получить выгоду от распараллеливания
clock ()
возвращает процессорное время всего процесса, что непригодно для замера времени выполнения многопоточного приложения.
- Диапазоны рекурсивных вызовов могут пересекаться. В однопоточном режиме это можно простить, но в многопоточном это фатально.
- Из-за бестолкового использования счётчика глубины рекурсии (
d
) код всегда работает в один поток (с затратами на вызовы openmp).
- Даже если бы оно работало правильно, оно создавало бы не больше двух потоков, если не вызвать
omp_set_nested(1)
или не передать в среду переменную OMP_NESTED=true
.
Как следует делать
Хотя распараллеливание при рекурсии и можно ограничить средствами sections
, эффективнее это будет сделать с помощью заданий (task
):
#include <algorithm>
#include <chrono>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <omp.h>
using namespace std;
constexpr size_t n = 1024*1024*128;
//const int n = 16;
static size_t minParallelSize = 128*1024;
static unsigned maxParallelDepth = 4;
void serialQuicksort(int* mas, size_t first, size_t last) {
int mid;
size_t f = first, l = last;
mid = mas[(f + l) / 2];
while (1) {
while (mas[f] < mid) { ++f; };
while (mas[l] > mid) { --l; };
if (f >= l) { break; }
std::swap (mas[f++], mas[l--]);
}
size_t part = l;
if (first < part)
serialQuicksort(mas, first, part);
if (part+1 < last)
serialQuicksort(mas, part+1, last);
}
void quicksort(int* mas, size_t first, size_t last, unsigned d = 0) {
int mid;
size_t f = first, l = last;
mid = mas[(f + l) / 2];
while (1) {
while (mas[f] < mid) { ++f; };
while (mas[l] > mid) { --l; };
if (f >= l) { break; }
std::swap (mas[f++], mas[l--]);
}
size_t part = l;
#pragma omp task if (d <maxParallelDepth && (last - first) > minParallelSize)
{
if (first < part)
quicksort(mas, first, part, d+1);
}
#pragma omp task if (d <maxParallelDepth && (last - first) > minParallelSize)
{
if (part+1 < last)
quicksort(mas, part+1, last, d+1);
}
#pragma omp taskwait
}
int main() {
int rc = EXIT_SUCCESS;
int* parallelA = new int[n];
int* serialA = new int[n];
for (size_t i=0; i<n; i++) {
int r = rand();
parallelA[i] = r;
serialA[i] = r;
}
[[maybe_unused]] unsigned num_threads = std::min<unsigned> (
n / minParallelSize / 2,
1 << (maxParallelDepth-1) );
auto start_time = std::chrono::steady_clock::now();
#pragma omp parallel num_threads(num_threads)
{
#pragma omp single
{ quicksort(parallelA, 0, n-1); }
}
auto end_time = std::chrono::steady_clock::now();
std::chrono::duration<double, std::milli> time = end_time - start_time;
fprintf(stderr, "Complete parallel qsort in %-8.3lfms\n", time.count ());
start_time = std::chrono::steady_clock::now();
serialQuicksort(serialA, 0, n-1);
end_time = std::chrono::steady_clock::now();
time = end_time - start_time;
fprintf(stderr, "Complete serial qsort in %-8.3lfms\n", time.count ());
for (size_t i=0; i<n-1; i++) {
if (parallelA[i]>parallelA[i+1]) {
rc = EXIT_FAILURE;
fprintf (stderr, "Array is not sorted A[%zd]=%d (>) A[%zd]=%d\n",
i, parallelA[i], i+1, parallelA[i+1] );
break;
}
}
delete[] parallelA;
delete[] serialA;
return rc;
}
Типовой результат:
Complete parallel qsort in 6492.260ms
Complete serial qsort in 13031.032ms
Т.е. прирост производительности составляет ±2 раза на 4-х рельных ядрах.
Дальнейшая оптимизация:
Приведённый пример слабо оптимизирован и требует более тонкой настройки. Во-первых требуется подобрать такие магические константы, как minParallelSize
и maxParallelDepth
, ограничивающих соответственно минимальный размер массива и максимальную глубину рекурсии для которых будут создаваться задания для параллельного выполнения. Они устанавливаются исключительно экспериментально.
Далее нужно подобрать формулу для num_threads
в main()
. Дело в том, что, судя по всему (только моё предположение), переключение потоков в ядре происходит несколько быстрее нежели переключение заданий в реализации OpenmMP(по крайней мере в связке linux/gomp). В результате простое избыточное увеличение количества потоков даёт прирост до 25%. Текущая формула чисто умозрительная. Помимо прочего она, вероятно, должна зависеть от числа доступных процессоров.
Кроме того значительный прирост производительности дадут вызовы не-параллельных версий по вышеозначенным условиям, вместо простой рекурсии; а также использование других методов сортировки для малых массивов (пирамида? шелл? слияние?).