На самом деле я не запускал ваш код, но я вижу немедленную ошибку на p, которая должна быть private, а не shared. Параллельный вызов qs: qs(v, p.first, p.second); приведет к гонкам на p, что приведет к непредсказуемому поведению. Локальные переменные в qs должны быть в порядке, потому что все потоки имеют свой собственный стек. Однако общий подход хорош. Вы на правильном пути.
Вот мои общие комментарии по реализации параллельной быстрой сортировки. Сама быстрая сортировка смущающе параллельна , что означает, что синхронизация не требуется. Рекурсивные вызовы qs в секционированном массиве смущающе параллельны.
Однако, параллелизм представлен в рекурсивной форме. Если вы просто используете вложенный параллелизм в OpenMP, вы получите тысячи потоков в секунду. Никакого ускорения не будет получено. Итак, в основном вам нужно превратить рекурсивный алгоритм в интерактивный. Затем вам нужно реализовать своего рода рабочую очередь. Это твой подход. И это не легко.
Для вашего подхода есть хороший тест: OmpSCR. Вы можете скачать на http://sourceforge.net/projects/ompscr/
В тесте производительности существует несколько версий быстрой сортировки на основе OpenMP. Большинство из них похожи на ваши. Однако, чтобы увеличить параллелизм, нужно минимизировать конфликт в глобальной очереди (в вашем коде это s). Таким образом, может быть несколько оптимизаций, таких как наличие локальных очередей. Хотя сам алгоритм является чисто параллельным, реализация может потребовать артефактов синхронизации. И, самое главное, получить ускорение очень сложно.
Однако вы все еще напрямую используете рекурсивный параллелизм в OpenMP двумя способами: (1) регулирование общего числа потоков и (2) использование OpenMP 3.0 task.
Вот псевдокод для первого подхода (он основан только на тесте OmpSCR):
void qsort_omp_recursive(int* begin, int* end)
{
if (begin != end) {
// Partition ...
// Throttling
if (...) {
qsort_omp_recursive(begin, middle);
qsort_omp_recursive(++middle, ++end);
} else {
#pragma omp parallel sections nowait
{
#pragma omp section
qsort_omp_recursive(begin, middle);
#pragma omp section
qsort_omp_recursive(++middle, ++end);
}
}
}
}
Чтобы запустить этот код, вам нужно позвонить omp_set_nested(1) и omp_set_num_threads(2). Код действительно прост. Мы просто создаем две темы о разделении работы. Однако мы вставляем простую логику регулирования, чтобы предотвратить чрезмерные потоки. Обратите внимание, что мои эксперименты показали приличное ускорение для этого подхода.
Наконец, вы можете использовать OpenMP 3.0 task, где задача является логически параллельной работой. В приведенных выше подходах OpenMP каждая параллельная конструкция порождает два физических потока. Вы можете сказать, что между задачей и рабочим потоком существует жесткое соотношение 1: 1. Однако task разделяет логические задачи и рабочих.
Поскольку OpenMP 3.0 еще не пользуется популярностью, я буду использовать Cilk Plus , который отлично подходит для выражения такого рода вложенных и рекурсивных параллелизмов. В Cilk Plus распараллеливание чрезвычайно просто:
void qsort(int* begin, int* end)
{
if (begin != end) {
--end;
int* middle = std::partition(begin, end,
std::bind2nd(std::less<int>(), *end));
std::swap(*end, *middle);
cilk_spawn qsort(begin, middle);
qsort(++middle, ++end);
// cilk_sync; Only necessay at the final stage.
}
}
Я скопировал этот код из примера кода Cilk Plus. Вы увидите, что одно ключевое слово cilk_spawn - это все для распараллеливания быстрой сортировки. Я пропускаю объяснения Cilk Plus и ключевого слова spawn. Однако это легко понять: два рекурсивных вызова объявлены как логически параллельные задачи. Всякий раз, когда происходит рекурсия, создаются логические задачи. Но среда выполнения Cilk Plus (которая реализует эффективный планировщик кражи работы) будет обрабатывать все виды грязной работы. Он оптимально ставит в очередь параллельные задачи и сопоставляет их с рабочими потоками.
Обратите внимание, что OpenMP 3.0 task по сути аналогичен подходу Cilk Plus. Мои эксперименты показывают, что довольно хорошие ускорения были возможны. Я получил ускорение в 3 ~ 4 раза на 8-ядерном компьютере. И ускорение было масштабным. Абсолютные ускорения Cilk Plus выше, чем у OpenMP 3.0.
Подход Cilk Plus (и OpenMP 3.0) и ваш подход по сути одинаковы: разделение параллельных задач и распределение нагрузки Однако это очень сложно реализовать эффективно. Например, вы должны уменьшить количество конфликтов и использовать структуры данных без блокировки.