Мне нужен оптимальный код для параллельной сортировки слиянием с использованием строительного блока потоков Intel в С++
Мне нужен оптимальный код для параллельной сортировки слиянием с использованием строительного блока потоков Intel.
Ответы (2)
Прежде всего, позвольте мне сказать, что, по моему опыту, tbb::parallel_sort() довольно эффективен и немного быстрее, чем код, который я собираюсь опубликовать (по крайней мере, для ввода порядка тысяч элементов, для которых я проверено).
Сказав это, я думаю, что следующий код — это именно то, что вы ищете. Переменные должны говорить сами за себя, а документация в коде должна объяснять все остальное.
Это понадобится для распараллеливания:
#include<tbb/parallel_invoke.h>
Если вы решите использовать Concurrency::parallel_invoke(), который может работать быстрее, включите это:
#include<ppl.h>
Я рекомендую эти настройки -
#define MIN_ELEMENTS_FOR_RECURSION (50)
#define MIN_ELEMENTS_FOR_PARALLEL_PROCESSING (100)
Ниже приведена основная функция для вызова. Параметры — это итераторы для начала и конца класса произвольного доступа (например, вектора, очереди и т. д.) и функция сравнения —
template <typename T_it, typename T_it_dereferenced>
void parallelMergeSort( T_it first, T_it last, bool (*firstLessThanSecond)(const T_it_dereferenced& a, const T_it_dereferenced& b) )
{
// create copy of container for extra space
std::vector<T_it_dereferenced> copy(first, last);
parallelMergeSortRecursive( first, last, copy.begin(), copy.end(), firstLessThanSecond );
}
Это вызывается рекурсивно из parallelMergeSort() для сортировки каждой половины -
template <typename T_it, typename T_it_dereferenced>
void parallelMergeSortRecursive( T_it source_first, T_it source_last, T_it copy_first, T_it copy_last,
bool (*firstLessThanSecond)(const T_it_dereferenced& a, const T_it_dereferenced& b), int recursion_depth = 0 )
{
// divide the array in two, and sort the two halves
long num_elements = source_last - source_first;
if ( num_elements > MIN_ELEMENTS_FOR_RECURSION )
{
T_it source_middle = source_first + num_elements / 2;
T_it copy_middle = copy_first + num_elements / 2;
if ( num_elements > MIN_ELEMENTS_FOR_PARALLEL_PROCESSING )
{
// Concurrency::parallel_invoke() may work faster
tbb::parallel_invoke(
[=] { parallelMergeSortRecursive( source_first, source_middle, copy_first, copy_middle, firstLessThanSecond, recursion_depth + 1 ); },
[=] { parallelMergeSortRecursive( source_middle, source_last, copy_middle, copy_last, firstLessThanSecond, recursion_depth + 1 ); }
);
}
else // sort serially rather than in parallel
{
parallelMergeSortRecursive( source_first, source_middle, copy_first, copy_middle, firstLessThanSecond, recursion_depth + 1 );
parallelMergeSortRecursive( source_middle, source_last, copy_middle, copy_last, firstLessThanSecond, recursion_depth + 1 );
}
// merge the two sorted halves
// we switch source <--> target with each level of recursion.
// at even recursion depths (including zero which is the root level) we assume the source is sorted and merge into the target
if ( recursion_depth % 2 == 0 )
{
merge( source_first, copy_first, copy_middle, copy_last, firstLessThanSecond );
}
else
{
merge( copy_first, source_first, source_middle, source_last, firstLessThanSecond );
}
}
else // very few elements remain to be sorted, stop the recursion and sort in place
{
if ( recursion_depth % 2 == 0 )
{
std::stable_sort(source_first, source_last, firstLessThanSecond);
}
else
{
std::stable_sort(copy_first, copy_last, firstLessThanSecond);
}
}
}
Это вызывается из рекурсивной функции, чтобы объединить две половины -
template <typename T_it, typename T_it_dereferenced>
void merge( T_it target_first, T_it source_first, T_it source_middle, T_it source_last,
bool (*firstLessThanSecond)(const T_it_dereferenced& a, const T_it_dereferenced& b) )
{
// source is assumed to contain two sorted sequences (from first to middle and from middle to last)
T_it source_it1 = source_first;
T_it source_it2 = source_middle;
T_it target_it = target_first;
for ( /* intentional */ ; source_it1 < source_middle && source_it2 < source_last ; ++target_it )
{
//if ( source_container[i] < source_container[j] )
if ( firstLessThanSecond(*source_it1, *source_it2) )
{
*target_it = *source_it1;
++source_it1;
}
else
{
*target_it = *source_it2;
++source_it2;
}
}
// insert remaining elements in non-completely-traversed-half into original container
// only one of these two whiles will execute since one of the conditions caused the previous while to stop
for ( /* intentional */ ; source_it1 < source_middle ; ++target_it )
{
*target_it = *source_it1;
++source_it1;
}
for ( /* intentional */ ; source_it2 < source_last ; ++target_it )
{
*target_it = *source_it2;
++source_it2;
}
}
TBB уже включает в себя метод сортировки (параллельная быстрая сортировка), который, однако, реализован довольно плохо (время выполнения, по крайней мере, линейно независимо от количества процессоров).
Я бы предложил вам портировать параллельную сортировку слиянием из существующей реализации. Например, сортировка в параллельном режиме gnu (включенная в любой последний gcc с исходными файлами), которая использует OpenMP. Просто замените все #pragma omp
некоторым параллельным кодом tbb.