мне нужен оптимальный код для параллельной сортировки слияния с использованием блока Intel Thread здания

Question

мне нужен оптимальный код для параллельной сортировки слияния с использованием Intel Thread строительного блока в C++

Answer 1

Т уже включают в себя метод сортировки (параллельно QuickSort), который -however - реализовано довольно плохо (время выполнения по меньшей мере линейно независимо от количества процессоров).

Мое предложение было бы вы параллельным слиянием портов с существующей реализацией. Например, сортировка в режиме параллельного режима gnu (включена в любой новый gcc с исходными файлами), в котором используется OpenMP. Просто замените все #pragma omp на некоторый параллельный код tbb.

Answer 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) 

Ниже приведена основная функция вызова. Параметры являются итераторы для начала и конца класса произвольного доступа (например, вектор, DEQUE и т.д.), а также функция сравнения -

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; 
    } 
}