I need an optimal code for parallel mergesort using intel thread building block

I need an optimal code for parallel mergesort using intel thread building bl开发者_如何学Cock in c++

First off, let me say that in my experience tbb::parallel_sort() is quite efficient and is a bit faster than the code I'm about to post (at least for input on the order of thousands of elements for which I've tested).

Having said that, I think the following code is exactly what you are looking for. Variables should be self explanatory and documentation in the code should explain the rest -

This will be needed for parallelization :

#include<tbb/parallel_invoke.h>

If you choose to use Concurrency::parallel_invoke(), which may work faster, then include this :

#include<ppl.h>

I recommend these settings -

#define MIN_ELEMENTS_FOR_RECURSION            (50)
#define MIN_ELEMENTS_FOR_PARALLEL_PROCESSING  (100)

Following is the main function to call. Parameters are iterators to start and end of a random access class (e.g., vector, deque, etc.) and a compare function -

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

This is called recursively from parallelMergeSort() in order to sort each half -

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

This is called from the recursive function in order to merge two halves -

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 already includes a sort method (parallel quicksort), which is -however- implemented quite poorly (runtime is at least linear independent of the number of processors).

My proposal would be you port parallel merge sort from an existing implementation. For example gnu parallel mode sort (included in any recent gcc with source files) wich uses OpenMP. Just replace all #pragma omp by some tbb parallel code.