Algoritmo para evitar la comunicación

Los algoritmos que evitan la comunicación minimizan el movimiento de datos dentro de una jerarquía de memoria para mejorar su tiempo de ejecución y consumo de energía. Estos minimizan la suma de dos costos (en términos de tiempo y energía): aritmética y comunicación. La comunicación, en este contexto, se refiere al movimiento de datos, ya sea entre niveles de memoria o entre múltiples procesadores a través de una red. Es mucho más costosa que la aritmética. ^{[ 1 ]}

Teoría formal

Modelo de memoria de dos niveles

Un modelo computacional común para analizar algoritmos que evitan la comunicación es el modelo de memoria de dos niveles:

Tiene un procesador y dos niveles de memoria.
La memoria de nivel 1 es infinitamente grande. La memoria de nivel 0 ("caché") tiene tamaño $M$ .
Al principio, la entrada reside en el nivel 1. Al final, la salida reside en el nivel 1.
El procesador solo puede operar con los datos que se encuentran en la caché.
El objetivo es minimizar las transferencias de datos entre los dos niveles de memoria.

multiplicación de matrices

^{[ 2 ]} Corolario 6.2:

Teorema — Matrices dadas $A,B,C$ de tamaños $n\times m,m\times k,n\times k$ , entonces $AB+C$ tiene complejidad de comunicación $\Omega (\max(mkn/M^{1/2},mk+kn+mk))$ .

Este límite inferior se puede lograr mediante la multiplicación de matrices por teselado .

Resultados más generales para otras operaciones numéricas de álgebra lineal se pueden encontrar en ^{[ 3 ]} . La siguiente demostración proviene de ^{[ 4 ].}

Prueba

Podemos dibujar el grafo de cálculo de $D=AB+C$ como un cubo de puntos de la red, cada punto tiene la forma $(i,j,k)$ . Desde $D[i,k]=\sum _{j}A[i,j]B[j,k]+C[i,k]$ computación $AB+C$ requiere que el procesador tenga acceso a cada punto dentro del cubo al menos una vez. Por lo tanto, el problema se convierte en cubrir el $mnk$ Puntos de la red con una cantidad mínima de comunicación.

Si $M$ es grande, entonces podemos simplemente cargar todo $mn+nk+mk$ luego escribe entradas $nk$ entradas. Esto no tiene interés.

Si $M$ es pequeño, entonces podemos dividir el algoritmo de comunicación mínima en segmentos separados. Durante cada segmento, realiza exactamente $M$ lecturas a la caché y cualquier número de escrituras desde la caché.

Durante cada segmento, el procesador tiene acceso a como máximo $2M$ diferentes puntos de $A,B,C$ .

Dejar $E$ Sea el conjunto de puntos de la red cubiertos durante este segmento. Entonces, por la desigualdad de Loomis-Whitney ,

$|E|\leq {\sqrt {|\pi _{1}(E)||\pi _{2}(E)||\pi _{3}(E)|}}$ con restricción $\sum _{i}|\pi _{i}(E)|\leq 2M$ .

Por la desigualdad de las medias aritméticas y geométricas , tenemos $|E|\leq \left({\frac {2}{3}}M\right)^{3/2}$ , con extremo alcanzado cuando $\pi _{i}(E)={\frac {2}{3}}M$ .

Por lo tanto, la intensidad aritmética está limitada superiormente por $CM^{1/2}$ dónde $C=(2/3)^{3/2}$ y, por lo tanto, la comunicación está delimitada inferiormente por ${\frac {nmk}{CM^{1/2}}}$ .

El cálculo directo verifica que el algoritmo de multiplicación de matrices por teselado alcanza el límite inferior.

Motivación

Considere el siguiente modelo de tiempo de ejecución: ^{[ 5 ]}

Medida de computación = Tiempo por FLOP = γ
Medida de comunicación = Número de palabras de datos transferidos = β

⇒ Tiempo total de ejecución = γ·(número de FLOPs ) + β·(número de palabras)

Dado que β >> γ , medido en tiempo y energía, el costo de comunicación predomina sobre el costo de computación. Las tendencias tecnológicas ^{[ 6 ]} indican que el costo relativo de la comunicación está aumentando en diversas plataformas, desde la computación en la nube hasta las supercomputadoras y los dispositivos móviles. El informe también predice que la brecha entre el tiempo de acceso a la DRAM y los FLOPs aumentará 100 veces durante la próxima década para equilibrar el uso de energía entre los procesadores y la DRAM. ^{[ 1 ]}

El consumo de energía aumenta en órdenes de magnitud a medida que ascendemos en la jerarquía de memoria. ^{[ 7 ]}

El presidente de los Estados Unidos, Barack Obama, citó algoritmos que evitan la comunicación en la solicitud de presupuesto del Departamento de Energía para el año fiscal 2012 al Congreso: ^{[ 1 ]}

Nuevo algoritmo mejora el rendimiento y la precisión en sistemas de computación a gran escala. En las arquitecturas informáticas modernas, la comunicación entre procesadores tarda más que la ejecución de una operación aritmética de punto flotante por parte de un procesador determinado. Investigadores de ASCR han desarrollado un nuevo método, derivado de métodos de álgebra lineal de uso común, para minimizar la comunicación entre procesadores y la jerarquía de memoria, reformulando los patrones de comunicación especificados en el algoritmo. Este método se ha implementado en el entorno TRILINOS, un conjunto de software de gran prestigio que proporciona funcionalidades a investigadores de todo el mundo para resolver problemas multifísicos complejos a gran escala.

Objetivos

Los algoritmos que evitan la comunicación se diseñan con los siguientes objetivos:

Reorganizar los algoritmos para reducir la comunicación entre todas las jerarquías de memoria.
Alcanzar el límite inferior de comunicación siempre que sea posible.

El siguiente ejemplo sencillo ^{[ 1 ]} demuestra cómo se logran.

Ejemplo de multiplicación de matrices

Sean A, B y C matrices cuadradas de orden n × n . El siguiente algoritmo ingenuo implementa C = C + A * B:

para i = 1 a n para j = 1 a n para k = 1 a n C(i,j) = C(i,j) + A(i,k) * B(k,j)

Coste aritmético (complejidad temporal): n ² (2 n − 1) para n suficientemente grande o O( n ³ ).

Reescribiendo este algoritmo con el costo de comunicación etiquetado en cada paso.

para i = 1 a n {leer la fila i de A en la memoria rápida} - n ² lecturas para j = 1 a n {leer C(i,j) en memoria rápida} - n ² lecturas {leer la columna j de B en la memoria rápida} - n ³ lecturas para k = 1 a n C(i,j) = C(i,j) + A(i,k) * B(k,j) {escribir C(i,j) de vuelta a la memoria lenta} - n ² escrituras

La memoria rápida se puede definir como la memoria local del procesador ( caché de la CPU ) de tamaño M y la memoria lenta se puede definir como la DRAM.

Coste de comunicación (lecturas/escrituras): n ³ + 3 n ² o O( n ³ )

Dado que el tiempo total de ejecución = γ ·O( n ³ ) + β ·O( n ³ ) y β >> γ, el costo de comunicación es dominante. El algoritmo de multiplicación de matrices por bloques (en mosaico) ^{[ 1 ]} reduce este término dominante:

Multiplicación de matrices en bloques (en mosaico)

Consideremos A, B y C como matrices de n / b por n / b de subbloques de b por b , donde b se denomina tamaño del bloque; supongamos que tres bloques de b por b caben en una memoria rápida.

para i = 1 a n/b para j = 1 a n/b {leer el bloque C(i,j) en la memoria rápida} - b ² × (n/b) ² = n ² lecturas para k = 1 a n/b {leer el bloque A(i,k) en la memoria rápida} - b ² × (n/b) ³ = n ³ /b lecturas {leer el bloque B(k,j) en la memoria rápida} - b ² × (n/b) ³ = n ³ /b lecturas C(i,j) = C(i,j) + A(i,k) * B(k,j) - {realizar una multiplicación de matrices en bloques} {escribir el bloque C(i,j) de vuelta a la memoria lenta} - b ² × (n/b) ² = n ² escrituras

Costo de comunicación: 2 n ³ / b + 2 n ² lecturas/escrituras << 2 n ³ costo aritmético

Haciendo b lo más grande posible:

3 b ² ≤ M

Logramos el siguiente límite inferior de comunicación:

3 ^1/2n ³ / M ^1/2 + 2 n ² o Ω (número de FLOPs / M ^1/2 )

Enfoques anteriores para reducir la comunicación

La mayoría de los enfoques investigados en el pasado para abordar este problema se basan en técnicas de planificación o ajuste que buscan superponer la comunicación con el cálculo. Sin embargo, este enfoque puede conducir a una mejora de, como máximo, un factor de dos. Ghosting es una técnica diferente para reducir la comunicación, en la que un procesador almacena y calcula de forma redundante datos de procesadores vecinos para cálculos futuros. ^Los algoritmos ajenos a la caché representan un enfoque diferente introducido en 1999 para transformadas rápidas de Fourier [ ⁸^] y luego extendido a algoritmos de grafos, programación dinámica , etc. También se aplicaron a varias operaciones en álgebra lineal ^[⁹^]^[¹⁰^]^[¹¹^] como factorizaciones densas LU y QR. El diseño de algoritmos específicos de la arquitectura es otro enfoque que se puede utilizar para reducir la comunicación en algoritmos paralelos , y existen muchos ejemplos en la literatura de algoritmos que se adaptan a una topología de comunicación dada ^[¹²^{] .}

Véase también

Localidad de los datos

Referencias

1 2 3 4 5 Demmel, Jim. "Algoritmos para evitar la comunicación". 2012 SC Companion: High Performance Computing, Networking Storage and Analysis. IEEE, 2012.
↑ Jia-Wei, Hong; Kung, HT (1981). "Complejidad de E/S" . Actas del decimotercer simposio anual de la ACM sobre Teoría de la Computación - STOC '81 . Nueva York, Nueva York, EE. UU.: ACM Press. págs. 326–333 . doi : 10.1145/800076.802486 . S2CID 8410593 .
↑ Ballard, G.; Carson, E.; Demmel, J.; Hoemmen, M.; Knight, N.; Schwartz, O. (mayo de 2014). "Límites inferiores de comunicación y algoritmos óptimos para álgebra lineal numérica" . Acta Numerica . 23 : 1–155 . doi : 10.1017/s0962492914000038 . ISSN 0962-4929 . S2CID 122513943 .
↑ Demmel, James; Dinh, Grace (2018-04-24). "Redes neuronales convolucionales óptimas para la comunicación". arXiv : 1802.06905 [ cs.DS ].
↑ Demmel, James y Kathy Yelick. «Communication Avoiding (CA) and Other Innovative Algorithms». The Berkeley Par Lab: Progress in the Parallel Computing Landscape: 243–250.
↑ Bergman, Keren, et al. " Estudio de computación a exaescala: desafíos tecnológicos en sistemas de computación a exaescala ". Oficina de Técnicas de Procesamiento de Información de la Agencia de Proyectos de Investigación Avanzada de Defensa (DARPA IPTO), Informe técnico 15 (2008).
↑ Shalf, John, Sudip Dosanjh y John Morrison. «Desafíos de la tecnología de computación a exaescala». Computación de alto rendimiento para la ciencia computacional – VECPAR 2010. Springer Berlin Heidelberg, 2011. 1–25.
↑ M. Frigo, CE Leiserson, H. Prokop y S. Ramachandran, "Algoritmos ajenos a la caché", En FOCS '99: Actas del 40.º Simposio Anual sobre Fundamentos de la Informática, 1999. IEEE Computer Society.
↑ S. Toledo, " Localidad de referencia en la descomposición LU con pivoteo parcial ," SIAM J. Matrix Anal. Appl., vol. 18, no. 4, 1997.
↑ F. Gustavson, "La recursión conduce al bloqueo automático de variables para algoritmos de álgebra lineal densos", IBM Journal of Research and Development, vol. 41, n.º 6, págs. 737–755, 1997.
↑ E. Elmroth, F. Gustavson, I. Jonsson y B. Kagstrom, " Algoritmos recursivos bloqueados y estructuras de datos híbridas para software de biblioteca de matrices densas ", SIAM Review, vol. 46, n.º 1, págs. 3–45, 2004.
↑ Grigori, Laura . " Introducción a la comunicación evitando algoritmos de álgebra lineal en computación de alto rendimiento .

[Demmel_2012-1] 1 2 3 4 5 Demmel, Jim. "Algoritmos para evitar la comunicación". 2012 SC Companion: High Performance Computing, Networking Storage and Analysis. IEEE, 2012.

[2] Jia-Wei, Hong; Kung, HT (1981). "Complejidad de E/S" . Actas del decimotercer simposio anual de la ACM sobre Teoría de la Computación - STOC '81 . Nueva York, Nueva York, EE. UU.: ACM Press. págs. 326–333 . doi : 10.1145/800076.802486 . S2CID 8410593 .

[3] Ballard, G.; Carson, E.; Demmel, J.; Hoemmen, M.; Knight, N.; Schwartz, O. (mayo de 2014). "Límites inferiores de comunicación y algoritmos óptimos para álgebra lineal numérica" . Acta Numerica . 23 : 1–155 . doi : 10.1017/s0962492914000038 . ISSN 0962-4929 . S2CID 122513943 .

[4] Demmel, James; Dinh, Grace (2018-04-24). "Redes neuronales convolucionales óptimas para la comunicación". arXiv : 1802.06905 [ cs.DS ].

[Demmel_2-5] Demmel, James y Kathy Yelick. «Communication Avoiding (CA) and Other Innovative Algorithms». The Berkeley Par Lab: Progress in the Parallel Computing Landscape: 243–250.

[DARPA_2008-6] Bergman, Keren, et al. " Estudio de computación a exaescala: desafíos tecnológicos en sistemas de computación a exaescala ". Oficina de Técnicas de Procesamiento de Información de la Agencia de Proyectos de Investigación Avanzada de Defensa (DARPA IPTO), Informe técnico 15 (2008).

[Shalf_2010-7] Shalf, John, Sudip Dosanjh y John Morrison. «Desafíos de la tecnología de computación a exaescala». Computación de alto rendimiento para la ciencia computacional – VECPAR 2010. Springer Berlin Heidelberg, 2011. 1–25.

[Frigo_1999-8] M. Frigo, CE Leiserson, H. Prokop y S. Ramachandran, "Algoritmos ajenos a la caché", En FOCS '99: Actas del 40.º Simposio Anual sobre Fundamentos de la Informática, 1999. IEEE Computer Society.

[Toledo_1997-9] S. Toledo, " Localidad de referencia en la descomposición LU con pivoteo parcial ," SIAM J. Matrix Anal. Appl., vol. 18, no. 4, 1997.

[Gustavson_1997-10] F. Gustavson, "La recursión conduce al bloqueo automático de variables para algoritmos de álgebra lineal densos", IBM Journal of Research and Development, vol. 41, n.º 6, págs. 737–755, 1997.

[Elmroth_2004-11] E. Elmroth, F. Gustavson, I. Jonsson y B. Kagstrom, " Algoritmos recursivos bloqueados y estructuras de datos híbridas para software de biblioteca de matrices densas ", SIAM Review, vol. 46, n.º 1, págs. 3–45, 2004.

[Grigori_2014-12] Grigori, Laura . " Introducción a la comunicación evitando algoritmos de álgebra lineal en computación de alto rendimiento .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ].

[ 5 ]

[ 6 ]

[ 7 ]

Los

[

[

[

[