quick - problemas de rendimiento en paralelo mergesort C++

quick sort in c

Question

Intenté escribir una implementación paralela de mergesort utilizando hilos y plantillas. El código relevante se enumera a continuación.

He comparado el rendimiento con el tipo de C ++ STL. Mi código es 6 veces más lento que std :: sort cuando no se generan hilos. Jugando con la variable maxthreads (y / o FACTOR) solo pude duplicar el rendimiento, de modo que en el mejor de los casos soy 3 veces más lento que std :: sort. Probé el código en una máquina multiprocesador de 16 núcleos.

htop muestra que los núcleos se utilizan como se esperaba, pero ¿por qué la falta de rendimiento y yo no siento el paralelismo en el tiempo de ejecución general?

Hay un error?

Gracias por una respuesta

#define FACTOR 1
static unsigned int maxthreads = FACTOR * std::thread::hardware_concurrency();

unsigned int workers=0;
std::mutex g_mutex;

template <typename T>
std::vector<T>* mergesort_inplace_multithreading(
    typename std::vector<T>::iterator* listbegin,
    typename std::vector<T>::iterator *listend,
    std::vector<T>* listarg)
{
    if (*listbegin == *listend)
    {
        return listarg;
    }
    else if (*listend == *listbegin + 1)
    {
        return listarg;
    }
    else
    {
        size_t offset = std::distance(*listbegin, *listend)/2;
        typename std::vector<T>::iterator listhalf = *listbegin + offset;
        g_mutex.lock();
        if (::workers <= maxthreads-2 and maxthreads >=2)
        {
            workers += 2;

            g_mutex.unlock();

            std::thread first_thread(mergesort_inplace_multithreading<T>, listbegin, &listhalf, listarg);
            std::thread second_thread(mergesort_inplace_multithreading<T>, &listhalf, listend, listarg);
            first_thread.join();
            second_thread.join();
            g_mutex.lock();
            workers -= 2;
            g_mutex.unlock();
        }
        else
        {
            g_mutex.unlock();
            mergesort_inplace_multithreading<T>(listbegin, &listhalf, listarg);
            mergesort_inplace_multithreading<T>(&listhalf, listend, listarg);
        }

        typename std::vector<T> result;
        typename std::vector<T>::iterator lo_sorted_it = *listbegin;
        typename std::vector<T>::iterator hi_sorted_it = listhalf;
        typename std::vector<T>::iterator lo_sortedend = listhalf;
        typename std::vector<T>::iterator hi_sortedend = *listend;
        while (lo_sorted_it != lo_sortedend and hi_sorted_it != hi_sortedend)
        {
            if (*lo_sorted_it <= *hi_sorted_it)
            {
                result.push_back(*lo_sorted_it);
                ++lo_sorted_it;
            }
            else
            {
                result.push_back(*hi_sorted_it);
                ++hi_sorted_it;
            }

        }//end while

        if (lo_sorted_it != lo_sortedend)
        {
            //assert(hi_sorted_it == hi_sortedend);
            result.insert(result.end(), lo_sorted_it, lo_sortedend);
        }
        else
        {
            //assert(lo_sorted_it == lo_sortedend);
            result.insert(result.end(), hi_sorted_it, hi_sortedend);
        }
        std::copy(result.begin(), result.end(), *listbegin);
        return listarg;
    }
}

int main()
{
    //some tests
}

Answer 1

Gracias por la respuesta.

El mutex solo protege a los trabajadores int sin firmar (una variable global) que realiza un seguimiento de cuántos subprocesos se generaron. Si se alcanza un máximo (dado por maxthreads), entonces no se generan más hilos. Lo logra usando el parámetro N en mergesort_mt2.

¿Cuántos núcleos tenía tu máquina?

Aún así, la actuación solo parece duplicarse ...

Answer 2

No necesita un mutex para el mergesort paralelo. Y ciertamente no es necesario iniciar dos subprocesos para cada división de particiones. Lanzas un hilo; la segunda partición se maneja en el hilo actual ; un mejor uso de los recursos de hilo que un hilo sentado sin hacer nada más que esperar a que otros dos terminen.

Primero, el programa de prueba simple, clasificando 20 millones de enteros sin signo. Nota: Todos los programas compilados con Apple LLVM versión 5.1 (clang-503.0.40) (basado en LLVM 3.4svn), 64 bits, subprocesos posix y optimizaciones establecidas en O2

Programa de prueba

int main()
{
    using namespace std::chrono;

    std::random_device rd;
    std::mt19937 rng(rd());
    std::uniform_int_distribution<unsigned int> dist(0, std::numeric_limits<unsigned int>::max());

    std::vector<unsigned int> v, back(20*1000000);

    for (int i=0; i<5; ++i)
    {
        std::cout << "Generating.../n";
        std::generate_n(back.begin(), back.size(), [&](){return dist(rng);});

        time_point<system_clock> t0, t1;

        v = back;
        std::cout << "std::sort: ";
        t0 = system_clock::now();
        std::sort(v.begin(), v.end());
        t1 = system_clock::now();
        std::cout << duration_cast<milliseconds>(t1-t0).count() << "ms/n";

        v = back;
        std::cout << "mergesort_mt1: ";
        t0 = system_clock::now();
        mergesort_mt1(v.begin(), v.end());
        t1 = system_clock::now();
        std::cout << duration_cast<milliseconds>(t1-t0).count() << "ms/n";
    }

    return 0;
}

Paralelo Mergesort

Comenzamos con algo súper básico. Limitamos el número de subprocesos simultáneos para que sea la concurrencia de hardware informada de la biblioteca estándar. Una vez que alcanzamos ese límite, dejamos de emitir nuevos hilos y simplemente recursemos en los existentes. Este algoritmo trivial tiene un comportamiento sorprendentemente decente una vez distribuido a través de subprocesos soportados por hardware.

template<typename Iter>
void mergesort_mt1(Iter begin, Iter end,
                  unsigned int N = std::thread::hardware_concurrency()/2)
{
    auto len = std::distance(begin, end);
    if (len < 2)
        return;

    Iter mid = std::next(begin, len/2);
    if (N > 1)
    {
        auto fn = std::async(mergesort_mt1<Iter>, begin, mid, N-2);
        mergesort_mt1(mid, end, N-2);
        fn.wait();
    }
    else
    {
        mergesort_mt1(begin, mid, 0);
        mergesort_mt1(mid, end, 0);
    }

    std::inplace_merge(begin, mid, end);
}

Salida

Generating...
std::sort: 1902ms
mergesort_mt1: 1609ms
Generating...
std::sort: 1894ms
mergesort_mt1: 1584ms
Generating...
std::sort: 1881ms
mergesort_mt1: 1589ms
Generating...
std::sort: 1840ms
mergesort_mt1: 1580ms
Generating...
std::sort: 1841ms
mergesort_mt1: 1631ms

Esto parece prometedor, pero ciertamente se puede mejorar.

Paralelo Merge + Biblioteca estándar Ordenar

El algoritmo std::sort varía ampliamente de un proveedor a otro en su implementación. La principal restricción impuesta por el estándar es que debe tener una complejidad promedio O (NlogN). Para lograr esto por el lado del rendimiento, muchos algoritmos std::sort son algunos de los códigos más complejos y optimizados que encontrará en la biblioteca estándar. He leído algunas implementaciones que tienen varias características de clasificación internas. Una de esas implementaciones que he visto usa introsort ( quicksort hasta que recursividad-profundidad es limitada, luego heapsort ) para particiones más grandes, y una vez que se alcanzan particiones pequeñas, sucumbe a una gigantesca distribución de inserción de 16 ranuras, desenrollada a mano.

El punto es que los autores de la biblioteca estándar entienden que un algoritmo de clasificación universal simplemente no se ajusta a todos. A menudo se emplean varios para la tarea, a menudo trabajando juntos en armonía. No ingenuamente pienses que puedes vencerlos; más bien, únete a ellos explotando su arduo trabajo.

Modificar nuestro código es sencillo. Usamos std::sort para todas las particiones menores a 1025. El resto es idéntico:

template<typename Iter>
void mergesort_mt2(Iter begin, Iter end,
                   unsigned int N = std::thread::hardware_concurrency())
{
    auto len = std::distance(begin, end);
    if (len <= 1024)
    {
        std::sort(begin,end);
        return;
    }

    Iter mid = std::next(begin, len/2);
    if (N > 1)
    {
        auto fn = std::async(mergesort_mt2<Iter>, begin, mid, N-2);
        mergesort_mt2(mid, end, N-2);
        fn.wait();
    }
    else
    {
        mergesort_mt2(begin, mid, 0);
        mergesort_mt2(mid, end, 0);
    }

    std::inplace_merge(begin, mid, end);
}

Después de agregar nuestro nuevo caso de prueba al programa de prueba, obtenemos:

Salida

Generating...
std::sort: 1930ms
mergesort_mt1: 1695ms
mergesort_mt2: 998ms
Generating...
std::sort: 1854ms
mergesort_mt1: 1573ms
mergesort_mt2: 1030ms
Generating...
std::sort: 1867ms
mergesort_mt1: 1584ms
mergesort_mt2: 1005ms
Generating...
std::sort: 1862ms
mergesort_mt1: 1589ms
mergesort_mt2: 1001ms
Generating...
std::sort: 1847ms
mergesort_mt1: 1578ms
mergesort_mt2: 1009ms

DE ACUERDO. Ahora estamos viendo cosas impresionantes. ¿Pero podemos exprimir aún más?

Combinación paralela + Clasificación estándar con recursión limitada

Si lo piensas, para explotar por completo todo el trabajo duro que se le dio a std::sort , podemos simplemente dejar de recurrir una vez que lleguemos a la población total de subprocesos. Si eso sucede, solo ordena todo lo que tenemos con std::sort y fusiona las cosas juntas cuando hayas terminado. Aunque sea difícil de creer, esto reducirá la complejidad del código. Nuestro algoritmo se convierte en una simple división de particiones en los núcleos, cada uno manejado por std::sort cuando llega el momento:

template<typename Iter>
void mergesort_mt3(Iter begin, Iter end,
                   unsigned int N = std::thread::hardware_concurrency()/2)
{
    auto len = std::distance(begin, end);
    if (len <= 1024 || N < 2)
    {
        std::sort(begin,end);
        return;
    }

    Iter mid = std::next(begin, len/2);
    auto fn = std::async(mergesort_mt3<Iter>, begin, mid, N-2);
    mergesort_mt3(mid, end, N-2);
    fn.wait();
    std::inplace_merge(begin, mid, end);
}

Una vez más, después de agregar esto a nuestro ciclo de prueba ...

Salida

Generating...
std::sort: 1911ms
mergesort_mt1: 1656ms
mergesort_mt2: 1006ms
mergesort_mt3: 802ms
Generating...
std::sort: 1854ms
mergesort_mt1: 1588ms
mergesort_mt2: 1008ms
mergesort_mt3: 806ms
Generating...
std::sort: 1836ms
mergesort_mt1: 1580ms
mergesort_mt2: 1017ms
mergesort_mt3: 806ms
Generating...
std::sort: 1843ms
mergesort_mt1: 1583ms
mergesort_mt2: 1006ms
mergesort_mt3: 853ms
Generating...
std::sort: 1855ms
mergesort_mt1: 1589ms
mergesort_mt2: 1012ms
mergesort_mt3: 798ms

Tal como está escrito, para cualquier partición que tenga 1024 elementos o menos, simplemente delegaremos a std::sort . Si las particiones son más grandes , presentamos un nuevo hilo para manejar un lado de la partición dividida, usando el hilo actual para manejar el otro. Una vez que saturamos el límite de hilo N, dejamos de dividir y simplemente delegamos todo a std::sort lo que std::sort . En resumen, somos un front-end de distribución de múltiples hilos para std::sort .

Resumen

Todavía hay más balas en la cámara que podríamos disparar (usando algo de meta-programación y suponiendo un número de conjunto de concurrencia fijo), pero eso te lo dejo a ti.

Puede aumentar drásticamente su rendimiento de clasificación si simplemente se centra en la creación de particiones, distribuye los hilos hasta que se toquen, utilice un algoritmo de clasificación altamente optimizado para las particiones del piso, luego cosa los elementos para terminar el trabajo. ¿Todavía hay espacio para mejorar? Ciertamente. Pero en su forma más simple presentada arriba no hay bloqueo, mutex, etc. La diferencia entre la muestra final y bare std::sort es una enorme mejora del 58% en conjuntos de datos idénticos en un pequeño MacBook Air a mediados de 2011 con 4 gb RAM y un procesador duo-core i7. Esto es impresionante, y teniendo en cuenta el poco código que se necesitó para hacerlo, simplemente-claro f''ing impresionante .