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

suma de vectores en c++ con funciones (2)

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

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

Carga dos dobles
Los agrega 1000 veces (o incluso realiza a = 1000 * b)
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.

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.
En lugar de aumentar los punteros, indexarlos: a[i] += b[i];
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.

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.

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.