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

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 ?"

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.$\beta$$F_{\mathrm{max}}$$B_{\mathrm{max}}$$\frac{F_{\mathrm{max}}}{\beta} > B_{\mathrm{max}}$$B_{\mathrm{max}}\beta > F_{\mathrm{max}}$

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.

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(N^4)$$O(N)$$O(N \log N)$$O(N^2)$

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,

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.

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.

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.

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 ...

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.