Cuenta FLOP para funciones de biblioteca

Al evaluar el número de FLOP en una función simple, a menudo se puede bajar la expresión que cuenta los operadores aritméticos básicos. Sin embargo, en el caso de enunciados matemáticos que involucran una división pareja, uno no puede hacer esto y esperar poder comparar con los conteos FLOP de funciones con solo sumas y multiplicaciones. La situación es aún peor cuando la operación se implementa en una biblioteca. Por lo tanto, es imperativo tener una noción razonable del desempeño de las funciones especiales.

Por funciones especiales, queremos decir cosas como:

• Exp()
• sqrt ()
• sin / cos / tan ()

que suelen proporcionar las bibliotecas del sistema.

Determinar la complejidad de estos se confunde aún más por el hecho de que muchos de ellos son adaptativos y tienen una complejidad dependiente de los insumos. Por ejemplo, las implementaciones numéricamente estables de exp () a menudo cambian la escala de forma adaptativa y usan búsquedas. Mi impresión inicial aquí es que lo mejor que se puede hacer en este caso es determinar el comportamiento promedio de las funciones.

Toda esta discusión es, por supuesto, altamente dependiente de la arquitectura. Para esta discusión, podemos restringirnos a las arquitecturas tradicionales de propósito general y excluir aquellas con unidades de funciones especiales (GPU, etc.)

Uno puede encontrar intentos bastante simples de estandarizarlos para arquitecturas particulares por el bien de la comparación de sistema versus sistema, pero esto no es aceptable si uno se preocupa por el método versus el rendimiento del método. ¿Qué metodologías para determinar la complejidad FLOP de estas funciones se consideran aceptables? ¿Hay alguna dificultad importante?

Parece que quiere una manera de evaluar qué tan vinculado está el código con la FPU, o qué tan efectivamente está usando la FPU, en lugar de contar el número de flops de acuerdo con la misma definición anacrónica de un "flop". En otras palabras, desea una métrica que alcance el mismo pico si cada unidad de coma flotante funciona a plena capacidad en cada ciclo. Echemos un vistazo a un Intel Sandy Bridge para ver cómo esto podría sacudirse.

Operaciones de punto flotante soportadas por hardware

Este chip admite instrucciones AVX , por lo que los registros tienen una longitud de 32 bytes (con capacidad para 4 dobles). La arquitectura superescalar permite que las instrucciones se superpongan, y la mayoría de las instrucciones aritméticas tardan unos pocos ciclos en completarse, a pesar de que una nueva instrucción podría comenzar en el siguiente ciclo. Esta semántica generalmente se abrevia escribiendo latencia / rendimiento inverso, un valor de 5/2 significaría que la instrucción tarda 5 ciclos en completarse, pero puede comenzar una nueva instrucción cada dos ciclos (suponiendo que los operandos estén disponibles, por lo que no hay datos dependencia y no esperar memoria).

Hay tres unidades aritméticas de coma flotante por núcleo, pero la tercera no es relevante para nuestra discusión, llamaremos a las dos unidades A y M relevantes porque sus funciones principales son la suma y la multiplicación. Instrucciones de ejemplo (ver las tablas de Agner Fog )

• vaddpd: adición empaquetada, ocupando la unidad A durante 1 ciclo, latencia / rendimiento inverso es 3/1
• vmulpd: multiplicación empaquetada, unidad M, 5/1
• vmaxpd: embalado seleccione máximo en pares, unidad A, 3/1
• vdivpd: división empaquetada, unidad M (y algo de A), 21/20 a 45/44 dependiendo de la entrada
• vsqrtpd: raíz cuadrada empaquetada, algunas A y M, 21/21 a 43/43 dependiendo de la entrada
• vrsqrtps: raíz cuadrada recíproca de baja precisión para entrada de precisión simple (8 floats)

La semántica precisa de lo que puede superponerse vdivpdy vsqrtpdaparentemente es sutil y AFAIK, no está documentada en ninguna parte. En la mayoría de los usos, creo que hay pocas posibilidades de superposición, aunque la redacción del manual sugiere que múltiples hilos pueden ofrecer más posibilidades de superposición en esta instrucción. Podemos atacar pico fracasos si partimos de una vaddpdy vmulpden cada ciclo, para un total de 8 flops por ciclo. Densa matriz-matriz multiply ( dgemm) puede llegar razonablemente cerca de este pico.

Al contar los flops para obtener instrucciones especiales, miraría cuánto de la FPU está ocupada. Supongamos por argumento que en su rango de entrada, vdivpdtardó un promedio de 24 ciclos en completarse, ocupando completamente la unidad M, pero la adición podría (si estuviera disponible) ejecutarse simultáneamente durante la mitad de los ciclos. La FPU es capaz de realizar 24 multiplicaciones empaquetadas y 24 adiciones empaquetadas durante esos ciclos (perfectamente intercaladas vaddpdy vmulpd), pero con un vdivpd, lo mejor que podemos hacer es 12 adiciones empaquetadas adicionales. Si suponemos que la mejor manera posible de hacer la división es usar el hardware (razonable), podríamos contar los vdivpd36 "flops" empaquetados, lo que indica que debemos contar cada división escalar como 36 "flops".

Con la raíz cuadrada recíproca, a veces es posible superar el hardware, especialmente si no se necesita una precisión total o si el rango de entrada es estrecho. Como se mencionó anteriormente, la vrsqrtpsinstrucción es muy económica, por lo que (si se trata de una precisión simple) puede realizar una vrsqrtpsseguida de una o dos iteraciones de Newton para limpiar. Estas iteraciones de Newton son solo

y *= (3 - x*y*y)*0.5;

Si es necesario realizar muchas de estas operaciones, esto puede ser significativamente más rápido que una evaluación ingenua y = 1/sqrt(x). Antes de la disponibilidad de la raíz cuadrada recíproca aproximada del hardware, algunos códigos sensibles al rendimiento utilizaban operaciones enteras infames para encontrar una suposición inicial para la iteración de Newton.

Funciones matemáticas proporcionadas por la biblioteca

Podemos aplicar una heurística similar a las funciones matemáticas proporcionadas por la biblioteca. Puede crear un perfil para determinar la cantidad de instrucciones de SSE, pero como hemos discutido, esa no es la historia completa y un programa que pasa todo su tiempo evaluando funciones especiales puede no parecer estar cerca del pico, lo que podría ser cierto, pero no lo es No es útil para decirle que pasa todo el tiempo fuera de su control en la FPU.

Sugiero usar una buena biblioteca matemática de vectores como línea de base (por ejemplo, VML de Intel, parte de MKL). Mida el número de ciclos para cada llamada y multiplíquelo por el máximo de flops alcanzables durante ese número de ciclos. Entonces, si un exponencial empaquetado tarda 50 ciclos en evaluarse, cuéntelo como 100 flops multiplicado por el ancho del registro. Desafortunadamente, las bibliotecas de matemática vectorial a veces son difíciles de llamar y no tienen todas las funciones especiales, por lo que podría terminar haciendo matemática escalar, en cuyo caso contaría nuestro hipotético exponencial escalar como 100 flops (aunque probablemente todavía tome 50 ciclos, por lo que solo obtendría el 25% del "pico" si dedica todo el tiempo a evaluar estos exponenciales).

Como otros han mencionado, puede contar ciclos y contadores de eventos de hardware utilizando PAPI o varias interfaces. Para un conteo de ciclos simple, puede leer el contador de ciclos directamente usando las rdtscinstrucciones con un fragmento de ensamblaje en línea.

Puede contar con ellos en sistemas reales utilizando PAPI , que otorga acceso a contadores de hardware y programas de prueba simples. Mi interfaz / contenedor PAPI favorito es IPM (Integrated Performance Monitor), pero existen otras soluciones ( TAU , por ejemplo). Esto debería proporcionar una comparación método a método bastante estable.

Voy a responder esta pregunta como si preguntaras:

"¿Cómo puedo comparar o predecir analíticamente el rendimiento de los algoritmos que dependen en gran medida de funciones especiales, en lugar de los conteos tradicionales de FLOP de multiplicar-agregar-transportar que provienen del álgebra lineal numérica"

Estoy de acuerdo con su primera premisa, que el rendimiento de muchas funciones especiales depende de la arquitectura, y que aunque generalmente puede tratar cada una de estas funciones como si tuviera un costo constante, el tamaño de la constante variará, incluso entre dos procesadores del mismo compañía pero con diferentes arquitecturas (consulte la tabla de temporización de instrucciones de Agner Fog como referencia).

No estoy de acuerdo, sin embargo, en que el enfoque de la comparación debería estar en los costos de las operaciones individuales de coma flotante. Creo que contar FLOP es útil hasta cierto punto, pero hay varias consideraciones mucho más importantes que pueden hacer que el costo de las funciones especiales sea menos relevante al comparar dos algoritmos potenciales, y estos deberían examinarse explícitamente primero antes de ir a una comparación de operaciones de punto flotante:

1. Escalabilidad: los algoritmos que presentan tareas que se pueden implementar de manera eficiente en arquitecturas paralelas dominarán el campo de la computación científica en el futuro previsible. Un algoritmo con una mejor "escalabilidad", ya sea a través de una comunicación más baja, una menor necesidad de sincronización o un mejor equilibrio de carga natural, puede emplear funciones especiales más lentas y, por lo tanto, ser más lento para un pequeño número de procesos, pero eventualmente alcanzará el número de procesadores se incrementa.

2. Localidad de referencia temporal: ¿el algoritmo reutiliza datos entre tareas, lo que permite que el procesador evite el tráfico innecesario de memoria? Cada nivel de la jerarquía de memoria que atraviesa un algoritmo agrega otro orden de costo de magnitud (aproximadamente) a cada acceso a la memoria. Como resultado, un algoritmo con alta densidad de operaciones especiales probablemente será significativamente más rápido que un algoritmo con el número equivalente de operaciones de funciones simples en una región de memoria más grande.

3. Huella de memoria: esto está fuertemente relacionado con los puntos anteriores, pero a medida que las computadoras crecen más y más, la cantidad de memoria por núcleo en realidad tiende a la baja. Hay dos beneficios para una pequeña huella de memoria. La primera es que es probable que una pequeña cantidad de datos del programa pueda caber completamente en la memoria caché del procesador. El segundo es que, para problemas muy grandes, un algoritmo con una huella de memoria más pequeña puede encajar en la memoria del procesador, lo que permite resolver problemas que de otro modo superarían la capacidad de la computadora.

¿Por qué molestarse contando flops? Solo cuente los ciclos para cada operación y tendrá algo que es universal.