¿Por qué no es mi Escala de multiplicación de matriz-vector?

15

Perdón por la larga publicación, pero quería incluir todo lo que pensé que era relevante al principio.

Lo que quiero

Estoy implementando una versión paralela de los métodos de Krylov subespacio para matrices densas. Principalmente GMRES, QMR y CG. Me di cuenta (después del perfil) que mi rutina DGEMV era patética. Así que decidí concentrarme en eso aislándolo. He intentado ejecutarlo en una máquina de 12 núcleos, pero los resultados a continuación son para una computadora portátil Intel i3 de 4 núcleos. No hay mucha diferencia en la tendencia.

Mi KMP_AFFINITY=VERBOSEsalida está disponible aquí .

Escribí un pequeño código:

size_N = 15000
A = randomly_generated_dense_matrix(size_N,size_N); %Condition Number is not bad
b = randomly_generated_dense_vector(size_N);
for it=1:n_times %n_times I kept at 50 
 x = Matrix_Vector_Multi(A,b);
end

Creo que esto simula el comportamiento de CG durante 50 iteraciones.

Lo que he intentado:

Traducción

Originalmente había escrito el código en Fortran. Lo traduje a C, MATLAB y Python (Numpy). No hace falta decir que MATLAB y Python fueron horribles. Sorprendentemente, C fue mejor que FORTRAN por un segundo o dos para los valores anteriores. Consecuentemente.

Perfilado

Perfilé mi código para ejecutarlo y se ejecutó durante 46.075segundos. Esto fue cuando se configuró MKL_DYNAMICFALSE y se usaron todos los núcleos. Si utilicé MKL_DYNAMIC como verdadero, solo (aproximadamente) la mitad del número de núcleos estaban en uso en un momento dado. Aquí hay algunos detalles:

Address Line    Assembly                CPU Time

0x5cb51c        mulpd %xmm9, %xmm14     36.591s

El proceso que consume más tiempo parece ser:

Call Stack                          LAX16_N4_Loop_M16gas_1
CPU Time by Utilization             157.926s
CPU Time:Total by Utilization       94.1%
Overhead Time                       0us
Overhead Time:Total                 0.0%    
Module                              libmkl_mc3.so   

Aqui estan algunas imagenes:ingrese la descripción de la imagen aquí ingrese la descripción de la imagen aquí

Conclusiones:

Soy un verdadero principiante en la creación de perfiles, pero me doy cuenta de que la velocidad aún no es buena. El código secuencial (1 núcleo) termina en 53 segundos. ¡Esa es una velocidad de menos de 1.1!

Pregunta real: ¿Qué debo hacer para mejorar mi aceleración?

Cosas que creo que podrían ayudar, pero no puedo estar seguro:

  • Implementación de Pthreads
  • Implementación de MPI (ScaLapack)
  • Ajuste manual (no sé cómo. Recomiende un recurso si sugiere esto)

Si alguien necesita más detalles (especialmente con respecto a la memoria), avíseme qué debo ejecutar y cómo. Nunca he hecho un perfil de memoria antes.

Encuesta
fuente

Respuestas:

20

Su matriz tiene un tamaño de 15,000 x 15,000, por lo que tiene 225M elementos en la matriz. Esto genera aproximadamente 2 GB de memoria. Esto es mucho más que el tamaño de caché de su procesador, por lo que debe cargarse completamente desde la memoria principal en cada multiplicación de matriz, lo que genera aproximadamente 100 GB de transferencias de datos, además de lo que necesita para los vectores de origen y destino.

El ancho de banda máximo de memoria del i3 es de aproximadamente 21 GB / s según las especificaciones de Intel, pero si mira por la web, encontrará que, como máximo, la mitad de eso está realmente disponible en realidad. Por lo tanto, como mínimo, esperaría que su punto de referencia dure 10 segundos, y su medición real de 45 segundos no está tan lejos de esa marca.

Al mismo tiempo, también está haciendo unos 10 mil millones de multiplicaciones y sumas de punto flotante. Teniendo en cuenta, digamos, 10 ciclos de reloj para la combinación y una velocidad de reloj de 3 GHz, saldrás a ~ 30 segundos. Por supuesto, pueden ejecutarse simultáneamente con cargas de memoria especulativas si el caché es inteligente.

En general, diría que no estás demasiado lejos de la marca. ¿Qué hubieras esperado?

Wolfgang Bangerth
fuente
¿No hay una manera de obtener al menos una aceleración de 2-3?
Investigación
@Nunoxic: es posible que desee comparar el rendimiento de la memoria en su sistema utilizando una herramienta como SiSoftware Sandra. El análisis de Wolfgangs me parece perfecto, si su aplicación está vinculada al ancho de banda de la memoria, la paralelización ayudará poco o nada. Además, observe las opciones de ahorro de energía que pueda tener, ya que pueden estar limitando el rendimiento de la memoria. Además, considere reemplazar su memoria con una memoria de mayor calidad, una latencia CAS más baja, por ejemplo, podría marcar una gran diferencia en su tiempo de pared.
Mark Booth
4

¿Cómo estás multiplicando el vector matriz? ¿Un doble bucle a mano? O llamadas a BLAS? Si está utilizando MKL, recomiendo encarecidamente utilizar las rutinas BLAS de la versión roscada.

Por curiosidad, es posible que también desee compilar su propia versión sintonizada de ATLAS y ver cómo funciona en su problema.

Actualizar

Después de la discusión en los comentarios a continuación, resulta que su Intel Core i3-330M solo tiene dos núcleos "reales". Los dos núcleos faltantes se emulan con hyperthreading . Dado que en los núcleos hiperprocesados ​​se comparten tanto el bus de memoria como las unidades de punto flotante, no obtendrá ninguna aceleración si alguno de los dos es un factor limitante. De hecho, el uso de cuatro núcleos probablemente incluso retrasará las cosas.

¿Qué tipo de resultados obtienes en "solo" dos núcleos?

Pedro
fuente
He probado ATLAs, GoTo y Netlib BLAS. Todos son más débiles que MKL en rendimiento. ¿Es esto esperado o estoy haciendo algo mal? Compilé ATLAS como se menciona en el manual. Además, he pegado mi código (exacto) aquí . Se llama BLAS de MKL.
Investigación
Ok, y para el escalado, ¿estás seguro de que en tu caso de referencia, el código solo se ejecuta en una sola CPU? Por ejemplo, si lo compara, ¿el histograma de uso de la CPU muestra un solo núcleo?
Pedro
Si. El histograma de la CPU muestra 1 núcleo.
Investigación
Solo por curiosidad nuevamente, ¿qué obtienes por dos o tres núcleos? ¿Su máquina realmente tiene cuatro núcleos físicos, o solo dos núcleos con hyperthreading ?
Pedro
¿Cómo lo descubro? He incluido mi KMP_AFFINITY en el principal.
Investigación
0

Tengo la impresión de que el orden de filas principales es óptimo para este problema con respecto a los tiempos de acceso a la memoria, el uso de líneas de caché y las fallas de TLB. Supongo que su versión FORTRAN usó el orden de columnas principales, lo que podría explicar por qué es consistentemente más lenta que la versión C.

si

También podría probar la velocidad si solo suma todos los elementos de la matriz en un solo bucle en lugar de la multiplicación del vector de la matriz. (Es posible que desee desenrollar el bucle por un factor 4, porque la no asociatividad de la adición podría evitar que el compilador realice esta optimización por usted).

Thomas Klimpel
fuente