c++ - unidimensionales - Sin aceleración para sumas vectoriales con subprocesos

suma de vectores en c++ con funciones

Question

Tengo un programa en C ++ que básicamente realiza algunos cálculos matriciales. Para estos utilizo LAPACK / BLAS y, por lo general, se vincula a MKL o ACML según la plataforma. Muchos de estos cálculos matriciales operan en diferentes matrices independientes y, por lo tanto, uso std :: thread''s para permitir que estas operaciones se ejecuten en paralelo. Sin embargo, noté que no tengo aceleración cuando uso más hilos. Rastreé el problema hasta la rutina de Daxpy Blas. Parece que si dos subprocesos utilizan esta rutina en paralelo, cada subproceso lleva el doble de tiempo, incluso aunque los dos subprocesos operen en matrices diferentes.

Lo siguiente que intenté fue escribir un nuevo método simple para realizar adiciones de vectores para reemplazar la rutina de Daxpy. Con un hilo, este nuevo método es tan rápido como la rutina BLAS, pero, al compilar con gcc, tiene los mismos problemas que la rutina BLAS: duplicar el número de hilos que se ejecutan en paralelo también duplica la cantidad de tiempo que necesita cada hilo, por lo que no se gana ninguna aceleración. Sin embargo, al usar el compilador Intel C ++, estos problemas desaparecen: con un número creciente de subprocesos, el tiempo que necesita un subproceso único es constante.

Sin embargo, necesito compilar también en sistemas donde no hay un compilador de Intel disponible. Así que mis preguntas son: ¿por qué no hay aceleración con el gcc y hay alguna posibilidad de mejorar el rendimiento del gcc?

Escribí un pequeño programa para demostrar el efecto:

// $(CC) -std=c++11 -O2 threadmatrixsum.cpp -o threadmatrixsum -pthread

#include <iostream>
#include <thread>
#include <vector>

#include "boost/date_time/posix_time/posix_time.hpp"
#include "boost/timer.hpp"

void simplesum(double* a, double* b, std::size_t dim);

int main() {

    for (std::size_t num_threads {1}; num_threads <= 4; num_threads++) {
        const std::size_t N { 936 };

        std::vector <std::size_t> times(num_threads, 0);    

        auto threadfunction = [&](std::size_t tid)
        {
            const std::size_t dim { N * N };
            double* pA = new double[dim];
            double* pB = new double[dim];

            for (std::size_t i {0}; i < N; ++i){
                pA[i] = i;
                pB[i] = 2*i;
            }   

            boost::posix_time::ptime now1 = 
                boost::posix_time::microsec_clock::universal_time();    

            for (std::size_t n{0}; n < 1000; ++n){
                simplesum(pA, pB, dim);
            }

            boost::posix_time::ptime now2 = 
                boost::posix_time::microsec_clock::universal_time(); 
            boost::posix_time::time_duration dur = now2 - now1; 
            times[tid] += dur.total_milliseconds(); 
            delete[] pA;
            delete[] pB;
        };

        std::vector <std::thread> mythreads;

        // start threads
        for (std::size_t n {0} ; n < num_threads; ++n)
        {
            mythreads.emplace_back(threadfunction, n);
        }

        // wait for threads to finish
        for (std::size_t n {0} ; n < num_threads; ++n)
        {
            mythreads[n].join();
            std::cout << " Thread " << n+1 << " of " << num_threads 
                      << "  took " << times[n]<< "msec" << std::endl;
        }
    }
}

void simplesum(double* a, double* b, std::size_t dim){

    for(std::size_t i{0}; i < dim; ++i)
    {*(++a) += *(++b);}
}

La salida con gcc:

Thread 1 of 1  took 532msec
Thread 1 of 2  took 1104msec
Thread 2 of 2  took 1103msec
Thread 1 of 3  took 1680msec
Thread 2 of 3  took 1821msec
Thread 3 of 3  took 1808msec
Thread 1 of 4  took 2542msec
Thread 2 of 4  took 2536msec
Thread 3 of 4  took 2509msec
Thread 4 of 4  took 2515msec

El outout con icc:

Thread 1 of 1  took 663msec
Thread 1 of 2  took 674msec
Thread 2 of 2  took 674msec
Thread 1 of 3  took 681msec
Thread 2 of 3  took 681msec
Thread 3 of 3  took 681msec
Thread 1 of 4  took 688msec
Thread 2 of 4  took 689msec
Thread 3 of 4  took 687msec
Thread 4 of 4  took 688msec

Entonces, con el icc, el tiempo necesario para que un subproceso realice los cálculos es constante (como hubiera esperado; mi CPU tiene 4 núcleos físicos) y con el gcc el tiempo para un subproceso aumenta. Reemplazar la rutina simpleum por BLAS :: daxpy produce los mismos resultados para icc y gcc (no es de extrañar, ya que la mayoría del tiempo se pasa en la biblioteca), que son casi los mismos que los resultados de gcc indicados anteriormente.

Answer 1

La respuesta es bastante simple: tus hilos están luchando por el ancho de banda de la memoria.

Tenga en cuenta que realiza una adición de punto flotante por 2 tiendas (una inicialización, una después de la adición) y 2 lecturas (en la adición). La mayoría de los sistemas modernos que ofrecen múltiples CPUs tienen que compartir el controlador de memoria entre varios núcleos.

Lo siguiente se ejecutó en un sistema con 2 zócalos físicos de CPU y 12 núcleos (24 con HT). Su código original exhibe exactamente su problema:

Thread 1 of 1  took 657msec
Thread 1 of 2  took 1447msec
Thread 2 of 2  took 1463msec
[...]
Thread 1 of 8  took 5516msec
Thread 2 of 8  took 5587msec
Thread 3 of 8  took 5205msec
Thread 4 of 8  took 5311msec
Thread 5 of 8  took 2731msec
Thread 6 of 8  took 5545msec
Thread 7 of 8  took 5551msec
Thread 8 of 8  took 4903msec

Sin embargo, al simplemente aumentar la densidad aritmética, podemos ver un aumento significativo en la escalabilidad. Para demostrar, cambié tu rutina de adición para realizar también una exponenciación: *(++a) += std::exp(*(++b)); . El resultado muestra una escala casi perfecta:

Thread 1 of 1  took 7671msec
Thread 1 of 2  took 7759msec
Thread 2 of 2  took 7759msec
[...]
Thread 1 of 8  took 9997msec
Thread 2 of 8  took 8135msec
Thread 3 of 8  took 10625msec
Thread 4 of 8  took 8169msec
Thread 5 of 8  took 10054msec
Thread 6 of 8  took 8242msec
Thread 7 of 8  took 9876msec
Thread 8 of 8  took 8819msec

Pero ¿qué pasa con la CPI?

Primero, ICC en línea simplesum . Demostrar que el proceso de incorporación es simple: al usar icc, he deshabilitado la optimización interprocedencial de múltiples archivos y simplesum movido simplesum a su propia unidad de traducción. La diferencia es asombrosa. La actuación pasó de

Thread 1 of 1  took 687msec
Thread 1 of 2  took 688msec
Thread 2 of 2  took 689msec
[...]
Thread 1 of 8  took 690msec
Thread 2 of 8  took 697msec
Thread 3 of 8  took 700msec
Thread 4 of 8  took 874msec
Thread 5 of 8  took 878msec
Thread 6 of 8  took 874msec
Thread 7 of 8  took 742msec
Thread 8 of 8  took 868msec

A

Thread 1 of 1  took 1278msec
Thread 1 of 2  took 2457msec
Thread 2 of 2  took 2445msec
[...]
Thread 1 of 8  took 8868msec
Thread 2 of 8  took 8434msec
Thread 3 of 8  took 7964msec
Thread 4 of 8  took 7951msec
Thread 5 of 8  took 8872msec
Thread 6 of 8  took 8286msec
Thread 7 of 8  took 5714msec
Thread 8 of 8  took 8241msec

Esto ya explica por qué la biblioteca tiene un mal desempeño: ICC no puede alinearla y, por lo tanto, no importa qué otra cosa haga que ICC funcione mejor que g ++.

También da una pista de lo que ICC podría estar haciendo aquí ... Qué pasa si, en lugar de ejecutar simplesum 1000 veces, intercambia los bucles para que

1. Carga dos dobles
2. Los agrega 1000 veces (o incluso realiza a = 1000 * b)
3. Almacena dos dobles

Esto aumentaría la densidad aritmética sin agregar exponenciales a la función ... ¿Cómo probar esto? Bueno, para comenzar, ¡simplemente implementemos esta optimización y veamos qué sucede! Para analizar, veremos el rendimiento de g ++. Recordemos nuestros resultados de referencia:

Thread 1 of 1  took 640msec
Thread 1 of 2  took 1308msec
Thread 2 of 2  took 1304msec
[...]
Thread 1 of 8  took 5294msec
Thread 2 of 8  took 5370msec
Thread 3 of 8  took 5451msec
Thread 4 of 8  took 5527msec
Thread 5 of 8  took 5174msec
Thread 6 of 8  took 5464msec
Thread 7 of 8  took 4640msec
Thread 8 of 8  took 4055msec

Y ahora, intercambiemos

for (std::size_t n{0}; n < 1000; ++n){
    simplesum(pA, pB, dim);
}

con la versión en la que el bucle interno se hizo el bucle externo:

double* a = pA; double* b = pB;
for(std::size_t i{0}; i < dim; ++i, ++a, ++b)
{
    double x = *a, y = *b;
    for (std::size_t n{0}; n < 1000; ++n)
    {
        x += y;
    }
    *a = x;
}

Los resultados muestran que estamos en el camino correcto:

Thread 1 of 1  took 693msec
Thread 1 of 2  took 703msec
Thread 2 of 2  took 700msec
[...]
Thread 1 of 8  took 920msec
Thread 2 of 8  took 804msec
Thread 3 of 8  took 750msec
Thread 4 of 8  took 943msec
Thread 5 of 8  took 909msec
Thread 6 of 8  took 744msec
Thread 7 of 8  took 759msec
Thread 8 of 8  took 904msec

Esto demuestra que la optimización del intercambio de bucles es, de hecho, la fuente principal del excelente rendimiento que ICC exhibe aquí.

Tenga en cuenta que ninguno de los compiladores probados (MSVC, ICC, g ++ y clang) reemplazará el bucle con una multiplicación, lo que mejora el rendimiento en 200x en los casos de subproceso único y 15x en los casos de 8 hilos. Esto se debe al hecho de que la inestabilidad numérica de las adiciones repetidas puede causar resultados muy diferentes cuando se reemplaza con una sola multiplicación. Cuando se realizan pruebas con tipos de datos enteros en lugar de tipos de datos de punto flotante, esta optimización ocurre.

¿Cómo podemos obligar a g ++ a realizar esta optimización?

Curiosamente, el verdadero asesino de g ++ no es una incapacidad para realizar el intercambio de bucles. Cuando se llama con -floop-interchange , g ++ también puede realizar esta optimización. Pero solo cuando las probabilidades están significativamente apiladas a su favor.

1. En lugar de std::size_t todos los límites se expresaron como int s. No long , no unsigned int , pero int . Todavía me resulta difícil de creer, pero parece que este es un requisito difícil.

2. En lugar de aumentar los punteros, indexarlos: a[i] += b[i];

3. G ++ necesita que se le diga -floop-interchange . Un simple -O3 no es suficiente.

Cuando se cumplen los tres criterios, el rendimiento de g ++ es similar al que proporciona ICC:

Thread 1 of 1  took 714msec
Thread 1 of 2  took 724msec
Thread 2 of 2  took 721msec
[...]
Thread 1 of 8  took 782msec
Thread 2 of 8  took 1221msec
Thread 3 of 8  took 1225msec
Thread 4 of 8  took 781msec
Thread 5 of 8  took 788msec
Thread 6 of 8  took 1262msec
Thread 7 of 8  took 1226msec
Thread 8 of 8  took 820msec

Nota: La versión de g ++ utilizada en este experimento es 4.9.0 en un Arch 64 de Linux.

Answer 2

Ok, llegué a la conclusión de que el problema principal es que el procesador actúa en diferentes partes de la memoria en paralelo y, por lo tanto, asumo que uno tiene que lidiar con muchas fallas de caché, lo que ralentiza el proceso. Poner la función de suma real en una sección crítica

summutex.lock();
simplesum(pA, pB, dim);
summutex.unlock();

resuelve el problema de las fallas de caché, pero por supuesto no produce una aceleración óptima. De todos modos, como ahora los otros subprocesos están bloqueados, el método simpleum también podría usar todos los subprocesos disponibles para la suma

void simplesum(double* a, double* b, std::size_t dim, std::size_t numberofthreads){

    omp_set_num_threads(numberofthreads);
    #pragma omp parallel 

    {
    #pragma omp for
    for(std::size_t i = 0; i < dim; ++i)
    {
      a[i]+=b[i];

    }
    }
}

En este caso, todos los subprocesos funcionan en la misma parte de la memoria: debe estar en la memoria caché del procesador y si el procesador necesita cargar algunas otras partes de la memoria en la memoria caché, los otros subprocesos se benefician de todo esto (dependiendo de si esto es L1 o L2 caché, pero reconozco que los detalles realmente no importan por el bien de esta discusión).

No afirmo que esta solución sea perfecta o esté en un lugar óptimo, pero parece funcionar mucho mejor que el código original. Y no se basa en algunos trucos de cambio de bucle que no puedo hacer en mi código real.