¿Por qué los cálculos expresados como multiplicaciones de matrices los hacen más rápidos?

13

En el tutorial de MNist de Google utilizando TensorFlow , se muestra un cálculo en el que un paso es equivalente a multiplicar una matriz por un vector. Google primero muestra una imagen en la que cada multiplicación numérica y suma que se incluiría en la realización del cálculo se escribe en su totalidad. A continuación, muestran una imagen en la que, en cambio, se expresa como una multiplicación de matrices, afirmando que esta versión del cálculo es, o al menos podría ser, más rápida:

  

Si escribimos eso como ecuaciones, obtenemos:

     

    

Podemos"vectorizar" este procedimiento, convirtiéndolo en una multiplicación de matrices y la suma de vectores. Esto es útil para la eficiencia computacional. (También es una forma útil de pensar.)

     

Séquelasecuacionescomoestasuelenestarescritasenelformatodemultiplicacióndematricesporlospracticantesdelaprendizajeautomáticoy,porsupuesto,puedenverlasventajasdehacerlodesdeelpuntodevistadelatersidaddelcódigoodelacomprensióndelasmatemáticas.LoquenoentiendoeslaafirmacióndeGoogledequelaconversióndelformulariodemanoalzadaalformulariodematriz"es útil para la eficiencia computacional"

¿Cuándo, por qué y cómo sería posible obtener mejoras en el rendimiento del software al expresar los cálculos como multiplicaciones de matriz? Si tuviera que calcular la multiplicación de la matriz en la segunda imagen (basada en la matriz), como humano, lo haría haciendo secuencialmente cada uno de los distintos cálculos que se muestran en la primera imagen (escalar). Para mí, no son más que dos notaciones para la misma secuencia de cálculos. ¿Por qué es diferente para mi computadora? ¿Por qué una computadora podría realizar el cálculo matricial más rápido que el escalar?

    
pregunta Mark Amery 11.03.2016 - 12:45

3 respuestas

16

Esto puede sonar obvio, pero las computadoras no ejecutan fórmulas , ejecutan código , y el tiempo que demora la ejecución depende directamente del código que ejecutan y solo de manera indirecta. en cualquier concepto que implemente el código. Dos piezas de código lógicamente idénticas pueden tener características de rendimiento muy diferentes. Algunas razones que probablemente surjan en la multiplicación de matrices específicamente:

  • Usando múltiples hilos. Casi no hay una CPU moderna que no tenga múltiples núcleos, muchos tienen hasta 8, y las máquinas especializadas para computación de alto rendimiento pueden tener fácilmente 64 en varios sockets. Escribir código de manera obvia, en un lenguaje de programación normal, usa solo uno de esos. En otras palabras, puede usar menos del 2% de los recursos informáticos disponibles de la máquina en la que se está ejecutando.
  • Usar instrucciones SIMD (confusamente, esto también se denomina "vectorización" pero en un sentido diferente al de las citas de texto en la pregunta). En esencia, en lugar de 4 u 8 o más instrucciones aritméticas escalares, dé a la CPU una instrucción que realice aritmética en 4 u 8 o más registros en paralelo. Esto puede, literalmente, hacer algunos cálculos (cuando son perfectamente independientes y aptos para el conjunto de instrucciones) 4 u 8 veces más rápido.
  • Haciendo más inteligente uso del caché . El acceso a la memoria es más rápido si es temporal y espacialmente coherente , es decir, los accesos consecutivos son a direcciones cercanas y cuando se accede a una dirección dos veces, se accede dos veces en una sucesión rápida en lugar de una pausa prolongada.
  • Uso de aceleradores como GPU. Estos dispositivos son bestias muy diferentes de las CPU y su programación de manera eficiente es una forma de arte propia. Por ejemplo, tienen cientos de núcleos, que se agrupan en grupos de unas pocas docenas de núcleos, y estos grupos comparten recursos: comparten algunos KiB de memoria que son mucho más rápidos que la memoria normal, y cuando cualquier núcleo del grupo ejecuta una Todos los demás en ese grupo tienen que esperar por ello.
  • Distribuya el trabajo a través de varias máquinas (¡muy importantes en las supercomputadoras!) que introducen una gran cantidad de nuevos dolores de cabeza pero, por supuesto, pueden , dar acceso a recursos informáticos mucho mayores.
  • Algoritmos más inteligentes. Para la multiplicación de matrices, el algoritmo simple O (n ^ 3), correctamente optimizado con los trucos anteriores, suele ser más rápido que la sub -los cúbicos para tamaños de matriz razonables, pero a veces ganan. Para casos especiales como matrices dispersas, puede escribir algoritmos especializados.

Muchas personas inteligentes han escrito código eficiente para operaciones de álgebra lineal común , usando los trucos anteriores y muchos más y por lo general incluso con estúpidos trucos específicos de plataforma. Por lo tanto, transformar su fórmula en una multiplicación de matriz y luego implementar ese cálculo llamando a una biblioteca de álgebra lineal madura se beneficia de ese esfuerzo de optimización. Por el contrario, si simplemente escribe la fórmula de manera obvia en un lenguaje de alto nivel, el código de máquina que se genera finalmente no utilizará todos esos trucos y no será tan rápido. Esto también es cierto si toma la formulación matricial y la implementa llamando a una rutina ingenua de multiplicación de matrices que usted mismo escribió (nuevamente, de la manera más obvia).

Hacer que el código sea rápido requiere trabajo y, a menudo, mucho trabajo si se desea esa última onza de rendimiento. Debido a que muchos cálculos importantes se pueden expresar como una combinación de un par de operaciones de álgebra lineal, es económico crear un código altamente optimizado para estas operaciones. ¿Su caso de uso especializado único, sin embargo? A nadie le importa eso, excepto a ti, por lo que no es económico optimizarlo.

    
respondido por el user7043 11.03.2016 - 13:20
3

(escasa) La multiplicación de matrices-vector es altamente paralelizable. Lo que es muy útil si sus datos son grandes y tiene una granja de servidores a su disposición.

Esto significa que puede dividir la matriz y el vector en trozos y dejar que máquinas separadas hagan parte del trabajo. Luego comparta algunos de sus resultados entre sí y luego obtenga el resultado final.

En su ejemplo, las operaciones serían las siguientes

  1. configure una cuadrícula de procesadores, cada uno con una Wx, y de acuerdo con sus coordenadas en la cuadrícula

  2. difundió el vector fuente a lo largo de cada columna (costo O(log height) )

  3. haga que cada procesador se multiplique localmente (costo O(width of submatrix * heightof submatrix) )

  4. contraiga el resultado en cada fila usando una suma (cost O(log width) )

Esta última operación es válida porque la suma es asociativa.

Esto también permite generar redundancia y evitar tener que colocar toda la información en una sola máquina.

Para pequeñas matrices 4x4 como las que se ven en los gráficos, es porque la CPU tiene instrucciones especiales y se registra para tratar esas operaciones.

    
respondido por el ratchet freak 11.03.2016 - 13:08
-1

Lo más instructivo sería comparar el rendimiento de su código con el rendimiento de la multiplicación de matrices ya implementada.

Siempre hay una optimización de nivel inferior en la que no pensaste, aquí puedes encontrar un ejemplo:

enlace

    
respondido por el ThePunisher 31.05.2018 - 11:40

Lea otras preguntas en las etiquetas