¿Es obsoleto el análisis algorítmico por conteo de flop?

43

En mis cursos de análisis numérico, aprendí a analizar la eficiencia de los algoritmos contando el número de operaciones de punto flotante (flops) que requieren, en relación con el tamaño del problema. Por ejemplo, en el texto de Trefethen & Bau sobre Álgebra lineal numérica, incluso hay imágenes en 3D de los recuentos de flop.

Ahora está de moda decir que los "flops son gratuitos" porque la latencia de memoria para buscar cualquier cosa que no esté en la memoria caché es mucho mayor que el costo de un flop. Pero todavía estamos enseñando a los estudiantes a contar los fracasos, al menos en los cursos de análisis numérico. ¿Deberíamos enseñarles a contar los accesos a la memoria? ¿Necesitamos escribir nuevos libros de texto? ¿O el acceso a la memoria es demasiado específico de la máquina para pasar el tiempo? ¿Cuál será la tendencia a largo plazo en términos de si los fracasos o el acceso a la memoria es el cuello de botella?

Nota: algunas de las respuestas a continuación parecen estar respondiendo a una pregunta diferente como "¿Debería reescribir obsesivamente mi implementación para guardar algunos fracasos o mejorar el rendimiento del caché?" Pero lo que pregunto es más parecido a " ¿Es más útil estimar la complejidad algorítmica en términos de operaciones aritméticas o accesos a la memoria ?"

David Ketcheson
fuente
1
> "¿Es más útil estimar la complejidad algorítmica en términos de operaciones aritméticas o accesos a la memoria?" . Desde un punto de vista práctico, los sistemas embebidos aún están limitados por la velocidad de la FPU en lugar del ancho de banda de la memoria. Por lo tanto, incluso si el conteo de fracasos se considera obsoleto según los estándares de HPC, sigue siendo útil para otras comunidades.
Damien

Respuestas:

31

Creo que lo correcto (primer orden) es mirar la relación de flops a bytes necesarios en el algoritmo, que llamo . Supongamos que es la tasa de flop máxima del procesador y el ancho de banda máximo. Si , entonces el algoritmo tendrá un ancho de banda limitado. Si , el algoritmo tiene un flop limitado.βFmaxBmaxFmaxβ>BmaxBmaxβ>Fmax

Creo que contar los accesos a la memoria es obligatorio, pero también deberíamos pensar en:

  • Cuánta memoria local se requiere

  • Cuánta concurrencia posible tenemos

Entonces puede comenzar a analizar algoritmos para hardware moderno.

Matt Knepley
fuente
3
Estoy de acuerdo con Matt, pero quiero señalar que ahora se encuentra razonablemente comúnmente definido en la literatura como "intensidad aritmética" e "intensidad numérica". Creo que el modelo Roofline de Williams, Waterman y Patterson es probablemente un buen comienzo para pensar en estos problemas. Creo que esto debería extenderse a la relación de memoria / flop de un algoritmo en el tiempo. β
Aron Ahmadia
2
David haciendo más 8 años antes.
Matt Knepley
3
Bien, entonces hay un modelo mejor y más complejo (como siempre). Pero este modelo da una respuesta que depende de la máquina. ¿Qué deberíamos enseñar a los estudiantes a usar como primer análisis?
David Ketcheson
3
El punto es que la máquina se ha reducido a un solo número, la proporción de flops pico a ancho de banda pico, al igual que el algoritmo. Esto es tan simple como se pone. Sin un modelo computacional, cualquier estimación de complejidad es inútil y esta es la más simple y realista.
Matt Knepley
1
Creo que malinterpretas el problema. Ya tenemos transporte óptico que puede transportar grandes cargas. El problema es conseguir eso en un chip. Solo tiene tantos cables y una frecuencia de reloj superior. El transporte óptico solo aliviará este problema en un chip óptico.
Matt Knepley
22

No veo por qué uno tiene que ser el "ganador"; Este no es un juego de suma cero, donde el conteo de flop y el acceso a la memoria tienen que ahogar al otro. Puedes enseñarles a ambos, y creo que ambos tienen sus usos. Después de todo, es difícil decir que su algoritmo con accesos de memoria será necesariamente más rápido que su algoritmo con accesos . Todo depende de los costos relativos de las diferentes partes (¡ese molesto prefactor que siempre ignoramos en estos análisis!).O(N4)O(N)O(NlogN)O(N2)

Desde una perspectiva más amplia, creo que el análisis del rendimiento algorítmico debería ser "todo incluido". Si estamos enseñando a las personas a ser verdaderos desarrolladores y usuarios de HPC, entonces deben comprender cuáles son los costos de la programación en el mundo real. Los modelos de análisis abstracto que tenemos no tienen en cuenta el tiempo del programador. Deberíamos pensar en términos de "tiempo total para la solución", en lugar de solo recuentos de fracaso y eficiencia algorítmica. No tiene mucho sentido pasar tres o cuatro días de programador para reescribir una rutina que ahorrará un segundo de tiempo de computadora por trabajo a menos que esté planeando ejecutar algunos millones de cálculos. Del mismo modo, la inversión de unos pocos días para ahorrar una o dos horas de tiempo de cálculo vale la pena rápidamente. Ese nuevo algoritmo puede ser asombroso,

aeismail
fuente
77
¿Un algoritmo que realiza el acceso a datos ? :)O(NlogN)O(N2)
Andreas Klöckner
2
Por qué no? Si solo se refiere a las operaciones de coma flotante, tal vez hay además un número significativo de operaciones enteras que causan el acceso a los datos :)O(NlogN)O(N2)
kini
9

Como otros han señalado, la respuesta depende, por supuesto, de si el cuello de botella es la CPU o el ancho de banda de la memoria. Para muchos algoritmos que funcionan en un conjunto de datos de tamaño arbitrario, el cuello de botella suele ser el ancho de banda de la memoria, ya que el conjunto de datos no cabe en la memoria caché de la CPU.

Además, Knuth menciona que es más probable que el análisis de acceso a la memoria resista la prueba del tiempo, presumiblemente porque es relativamente simple (incluso teniendo en cuenta la compatibilidad con el caché) en comparación con las complejidades de las tuberías de CPU modernas y la predicción de ramificaciones.

Knuth usa el término gigamems en el Volumen 4A de TAOCP, cuando analiza BDD. No estoy seguro de si lo usa en volúmenes anteriores. Hizo el comentario antes mencionado sobre resistir el paso del tiempo en su conferencia anual del árbol de Navidad en 2010.

Curiosamente, lo estás haciendo mal muestra que incluso analizar el rendimiento basado en las operaciones de memoria no siempre es sencillo, ya que hay elementos como la presión de VM que entran en juego si los datos no caben en la RAM física de una vez.

Jason Davies
fuente
8

La forma de determinar los costos de un algoritmo depende de qué "nivel" de computación científica trabaje y qué clase (estrecha o amplia) de problemas considere.

Si piensa en la optimización de caché, esto es claramente más relevante para, por ejemplo, la implementación de paquetes de álgebra lineal numérica como BLAS y bibliotecas similares. Entonces, esto pertenece a la optimización de bajo nivel, y está bien si tiene un algoritmo fijo para un problema específico y con suficientes restricciones en la entrada. Por ejemplo, la optimización de caché podría ser relevante para tener una implementación rápida de la iteración de gradiente conjugado si se promete que la matriz es lo suficientemente escasa.

Por otro lado, cuanto más amplia es la clase de problemas, menos puede predecir sobre la computación real (por ejemplo, no sabe cuán dispersas serán realmente las matrices de entrada de su implementación de CG). Cuanto más amplia sea la clase de máquinas en las que se supone que se ejecuta su programa, menos podrá predecir sobre la arquitectura de caché.

Además, en un nivel superior de computación científica, podría ser más relevante cambiar la estructura del problema. Por ejemplo, si pasa tiempo buscando un buen preacondicionador para un sistema lineal de ecuaciones, este tipo de optimización generalmente supera cualquier optimización de bajo nivel, porque el número de iteraciones se reduce drásticamente.

En conclusión, la optimización de caché es útil solo si no queda nada para optimizar por paralelismo y reducción del número asintótico de FLOP.

Creo que es aconsejable adaptar la postura de la informática teórica: al final, mejorar la complejidad asintótica de un algoritmo tiene más rendimiento que la microoptimización de algunas líneas de código existentes. Por lo tanto, todavía se prefiere el conteo de FLOP.

shuhalo
fuente
"la optimización de caché es útil solo si no queda nada para optimizar por paralelismo y reducción del número asintótico de FLOP". Estoy en desacuerdo. Si desea calcular una gran expresión de un gran grupo de números, es mejor realizar un paso a la vez con todos los números que todos los pasos para cada número. Ambos tienen el mismo número de FLOPS, pero uno es mejor en el acceso a la memoria. Bonificación si selecciona el tamaño del grupo para caber en la memoria caché (o el compilador lo hace por usted). Esto es lo que hace numexpr en Python: github.com/pydata/numexpr
Davidmh
6

Siempre me he negado a pensar en contar flops, accesos a memoria o lo que sea que tengas. Ese es un concepto de la década de 1960 cuando lo que hiciste fue más o menos dado y solo cómo lo hiciste fue hasta la optimización algorítmica. Piense en resolver un problema de elementos finitos en una malla xyz uniforme utilizando la eliminación gaussiana de la iteración de Jacobi.

Ahora, puede optimizar esto al infierno y ahorrar unos pocos fracasos, ganando el 10% del tiempo de ejecución. O puede pensar en implementar un método de cuadrícula múltiple y un preacondicionador de bloque óptimo, obteniendo un factor de 10 en tiempo de ejecución. Esto es lo que deberíamos capacitar a nuestros estudiantes para que hagan: piense en qué algoritmos externos complejos pueden ganarle al tratar de encontrar un mejor algoritmo interno. Su jefe (Keyes) tiene estas diapositivas sobre el progreso en los cálculos de MHD que hacen que este punto sea bastante obvio.

Wolfgang Bangerth
fuente
En realidad, estaba preguntando sobre el tipo de pensamiento de alto nivel que sugiere, no la optimización de bajo nivel. ¿Qué métrica debe usar para determinar si multigrid y su preacondicionador serán más rápidos que las alternativas?
David Ketcheson
No sabría contar, a mano, FLOPS o cualquier otra instrucción para algoritmos complejos que se ejecutan en decenas o miles de líneas de código. Piense, por ejemplo, cuán compleja es la fase de análisis y construcción de los algoritmos AMG. Hay tantas partes de estos algoritmos, y todos dependen de los datos reales que no puede predecir el número de operaciones.
Wolfgang Bangerth
1
Creo que al principio no entendí a lo que te referías, pero todavía no estoy de acuerdo con tu punto. Los "algoritmos externos" pueden (y diría, deberían) seguir siendo diseñados teniendo en cuenta la complejidad asintótica. Seguramente no afirmaría que una caída de un algoritmo cuadrático a un algoritmo casi lineal conduciría, en el mejor de los casos, a una reducción del 10% en el tiempo de ejecución; sin embargo, ¿cómo más cuantificar la complejidad asintótica que a través de los fracasos y / o las operaciones de memoria?
Jack Poulson
77
Creo que este enfoque de "arrojar las manos" a los algoritmos es una mierda. Debe simplificar el análisis solo observando los costos de primer orden y simplificando el modelo para que sea manejable, pero decir que no puede analizar algo como MG o Cholesky porque es demasiado complicado es completamente incorrecto.
Matt Knepley
1
Bueno, pero ¿qué significa analizar MG o Cholesky cuando cada FLOP que cuenta está oculto detrás de varias capas de latencia causadas por procesadores hiperprocesados, cachés, RAM lenta, procesadores multiescalares y vectorización automática? Lo que quiero decir es que dentro de un factor de 5-10, ya no puedes predecir el tiempo de ejecución de tus algoritmos sin cronometrarlo. Eso fue completamente diferente en los años 50 y 60 cuando las personas comenzaron este conteo FLOP.
Wolfgang Bangerth
1

Sí, obsoleto El análisis algorítmico por flops, o cualquier otro método, es tan útil como el modelo abstracto de la máquina cuando se considera el tamaño del problema en cuestión. El rendimiento real depende tanto de la implementación como del hardware, y la aplicabilidad de cualquier modelo abstracto para este último a la realidad está disminuyendo con el tiempo. Por ejemplo, a medida que paraleliza aún más la implementación de un algoritmo complejo, como la dinámica molecular, diferentes aspectos se vuelven limitantes de la velocidad en diferentes hardware, y el análisis algorítmico no tiene nada que ver con las observaciones. En cierto sentido, lo único importante es medir el rendimiento de las implementaciones de los algoritmos en los tipos de hardware en cuestión.

¿Son útiles estas abstracciones como herramienta de aprendizaje? Sí, al igual que muchos modelos utilizados para la enseñanza, son útiles siempre que se coloquen junto con la comprensión de las limitaciones del modelo. La mecánica clásica está bien siempre y cuando aprecies que no funcionará en escalas de pequeña distancia o gran velocidad ...

mabraham
fuente
-1

Realmente no responde a su pregunta, pero agrega más otra variable a considerar: algo a tener en cuenta son las características del lenguaje de programación. Por ejemplo, Python sortusa el algoritmo de Timsort , que está diseñado (entre otras buenas propiedades) para minimizar el número de comparaciones, que podrían ser potencialmente lentas para los objetos de Python. Por otro lado, comparar dos flotantes en C ++ es increíblemente rápido, pero intercambiarlos es más costoso, por lo que utilizan otros algoritmos.

Otros ejemplos son la asignación dinámica de memoria (trivial en una lista de Python, rápida tanto en tiempo de ejecución como en tiempo de desarrolladores, solo .append()), frente a FORTRAN o C, donde, aunque es posible y más rápido cuando se implementa adecuadamente, requiere mucho más tiempo de programación y cerebro. Ver Python es más rápido que el FORTRAN.

Davidmh
fuente
Esto es cierto, pero, como usted dice, no responde la pregunta. Está en un tema diferente.
David Ketcheson
Bueno, en un análisis adecuado es algo a tener en cuenta al decidir qué algoritmo implementar.
Davidmh