assembly - ¿Qué consideraciones entran en la predicción de la latencia para las operaciones en los procesadores superescalares modernos y cómo puedo calcularlos a mano?

x86-64 pipeline

Question

Quiero poder predecir, a mano, exactamente cuánto tiempo aritmético arbitrario (es decir, sin ramificación o memoria, aunque eso también sería bueno) el código de ensamblaje x86-64 tomará una arquitectura particular, teniendo en cuenta la reordenación de las instrucciones, la superscalaridad, latencias, CPIs, etc.

¿Qué / describir las reglas deben seguirse para lograr esto?

Creo que tengo algunas reglas preliminares resueltas, pero no he podido encontrar ninguna referencia al desglosar ningún código de ejemplo a este nivel de detalle, así que tuve que hacer algunas conjeturas. (Por ejemplo, el manual de optimización de Intel apenas menciona la reordenación de instrucciones).

Como mínimo, estoy buscando (1) confirmación de que cada regla es correcta o bien una declaración correcta de cada regla, y (2) una lista de cualquier regla que pueda haber olvidado.

• Se emiten tantas instrucciones como sea posible en cada ciclo, comenzando en orden desde el ciclo actual y potencialmente tan lejos como el tamaño del búfer de reorden.
• Se puede emitir una instrucción en un ciclo dado si:
  • No se están ejecutando instrucciones que afecten a sus operandos. Y:
  • Si se trata de una instrucción de punto flotante, todas las instrucciones de punto flotante antes de que se haya emitido (las instrucciones de punto flotante tienen una ordenación de instrucciones estáticas). Y:
  • Hay una unidad funcional disponible para esa instrucción en ese ciclo. Cada (?) Unidad funcional está canalizada, lo que significa que puede aceptar 1 nueva instrucción por ciclo, y el número total de unidades funcionales es 1 / CPI, para el CPI de una clase de función dada (nebuloso aquí: probablemente, por ejemplo, addps y subps usan el ¿La misma unidad funcional? ¿Cómo puedo determinar esto?). Y:
  • En este ciclo ya se ha emitido un número de instrucciones menor que el ancho superescala (generalmente 4 ).
• Si no se pueden emitir instrucciones, el procesador simplemente no emite ninguna, una condición llamada "bloqueo".

Como ejemplo, considere el siguiente código de ejemplo (que calcula un producto cruzado):

shufps   xmm3, xmm2, 210
shufps   xmm0, xmm1, 201
shufps   xmm2, xmm2, 201
mulps    xmm0, xmm3
shufps   xmm1, xmm1, 210
mulps    xmm1, xmm2
subps    xmm0, xmm1

Mi intento de predecir la latencia de Haswell es algo así:

; `mulps`  Haswell latency=5, CPI=0.5
; `shufps` Haswell latency=1, CPI=1
; `subps`  Haswell latency=3, CPI=1

shufps   xmm3, xmm2, 210   ; cycle  1
shufps   xmm0, xmm1, 201   ; cycle  2
shufps   xmm2, xmm2, 201   ; cycle  3
mulps    xmm0, xmm3        ;   (superscalar execution)
shufps   xmm1, xmm1, 210   ; cycle  4
mulps    xmm1, xmm2        ; cycle  5
                           ; cycle  6 (stall `xmm0` and `xmm1`)
                           ; cycle  7 (stall `xmm1`)
                           ; cycle  8 (stall `xmm1`)
subps    xmm0, xmm1        ; cycle  9
                           ; cycle 10 (stall `xmm0`)

Answer 1

Relacionado: ¿Cuántos ciclos de CPU se necesitan para cada instrucción de ensamblaje? es una buena introducción al rendimiento frente a la latencia por instrucción, y cómo esto significa para secuencias de instrucciones múltiples.

Esto se llama análisis estático (rendimiento) . Wikipedia dice ( https://en.wikipedia.org/wiki/List_of_performance_analysis_tools ) que AMD CodeXL de AMD tiene un "analizador estático de kernel" (es decir, para kernels computacionales, también conocidos como bucles). Nunca lo he intentado.

Intel también tiene una herramienta gratuita para analizar cómo pasarán los bucles a través de la tubería en las CPU de la familia Sandybridge: ¿Qué es IACA y cómo lo uso?

IACA no es mala, pero tiene errores (p. Ej., Datos incorrectos para shld en Sandybridge, y la última vez que lo verifiqué, no sabe que Haswell / Skylake puede mantener los modos de direccionamiento indexados micro-fusionados para algunas instrucciones . Pero tal vez eso cambie ahora. Intel agregó detalles sobre eso a su manual de optimización.) IACA tampoco es útil para contar uops de front-end para ver qué tan cerca de un cuello de botella está (le gusta solo darle recuentos de uop de dominio no fusionado).

El análisis estático a menudo es bastante bueno, pero definitivamente compruebe los perfiles con contadores de rendimiento. Ver ¿Puede MOV de x86 realmente ser "gratis"? ¿Por qué no puedo reproducir esto en absoluto? para un ejemplo de perfilar un bucle simple para investigar una característica de microarquitectura.

Lectura esencial:

La guía de microarquía de Agner Fog (capítulo 2: Ejecutivos fuera de orden) explica algunos de los conceptos básicos de las cadenas de dependencia y la ejecución fuera de orden. Su guía "Optimizing Assembly" tiene más cosas buenas de introducción y rendimiento avanzado.

Los capítulos posteriores de su guía de microarquía cubren los detalles de las tuberías en CPU como Nehalem, Sandybridge, Haswell, K8 / K10, Bulldozer y Ryzen. (Y Atom / Silvermont / Jaguar).

Las tablas de instrucciones de Agner Fog (hoja de cálculo o PDF) también son normalmente la mejor fuente para las fallas de latencia / rendimiento / puertos de ejecución.

Los documentos de análisis de microarquía de David Kanter son muy buenos, con diagramas. por ejemplo, https://www.realworldtech.com/sandy-bridge/ , https://www.realworldtech.com/haswell-cpu/ , y https://www.realworldtech.com/bulldozer/ .

Vea también otros enlaces de rendimiento en la etiqueta wiki x86 .

También intenté explicar cómo un núcleo de CPU encuentra y explota el paralelismo a nivel de instrucción en esta respuesta , pero creo que ya ha comprendido esos conceptos básicos en la medida en que es relevante para el software de ajuste. Sin embargo, mencioné cómo SMT (Hyperthreading) funciona como una forma de exponer más ILP a un solo núcleo de CPU.

En la terminología de Intel :

• "problema" significa enviar un uop a la parte fuera de orden del núcleo; junto con el registro de cambio de nombre, este es el último paso en el front-end. La etapa de problema / cambio de nombre es a menudo el punto más estrecho en la tubería, por ejemplo, 4-ancho en Intel desde Core2. (Con uarches posteriores como Haswell y, especialmente, Skylake a menudo se acerca mucho a eso en algún código real, gracias a los decodificadores mejorados de SKL y al ancho de banda de caché uop, así como a las mejoras en el back-end y el caché de caché). : micro-fusion le permite enviar 2 uops a través del front-end y solo ocupar una entrada de ROB. (Pude construir un bucle en Skylake que sostiene 7 uops de dominio no fusionado por reloj ). Consulte también http://blog.stuffedcow.net/2013/05/measuring-rob-capacity/ re: tamaño de ventana fuera de orden.

• "envío" significa que el programador envía un uop a un puerto de ejecución. Esto sucede tan pronto como todas las entradas están listas y el puerto de ejecución relevante está disponible. ¿Cómo están programados los uops x86, exactamente? . La programación ocurre en el dominio "no fusionado"; los uops microfundidos se rastrean por separado en el programador de OoO (también conocido como Reservation Station, RS).

Una gran cantidad de otras publicaciones sobre arquitectura de computadoras usan estos términos en el sentido opuesto, pero esta es la terminología que encontrará en el manual de optimización de Intel, y los nombres de contadores de rendimiento de hardware como uops_issued.any o uops_dispatched_port.port_5 .

exactamente cuánto tiempo tomará el código de ensamblaje x86-64 aritmético arbitrario

También depende del código circundante, debido al ejecutivo de OoO

El resultado final de sus subps no tiene que estar listo antes de que la CPU comience a ejecutar instrucciones posteriores. La latencia solo importa para las instrucciones posteriores que necesitan ese valor como entrada, no para el bucle de enteros y todo eso.

A veces, el rendimiento es lo que importa, y un ejecutivo fuera de orden puede ocultar la latencia de múltiples cadenas de dependencias cortas independientes. (Por ejemplo, si está haciendo lo mismo con cada elemento de una gran variedad de vectores múltiples, múltiples productos cruzados pueden estar en vuelo al mismo tiempo). Terminará con múltiples iteraciones en vuelo a la vez, aunque esté en el orden del programa. termina toda una iteración antes de hacer cualquiera de las siguientes. (La canalización de software puede ayudar a los cuerpos de bucle de alta latencia si el ejecutivo de OoO tiene dificultades para hacer todo el reordenamiento en HW).

Hay tres dimensiones principales para analizar en un bloque corto.

Puede caracterizar aproximadamente un bloque corto de código no ramificado en términos de estos tres factores. Por lo general, solo uno de ellos es el cuello de botella para un caso de uso determinado. A menudo, está viendo un bloque que usará como parte de un bucle, no como todo el cuerpo del bucle, pero el exo OoO normalmente funciona lo suficientemente bien como para que pueda sumar estos números para un par de bloques diferentes , si son no es tan largo que el tamaño de la ventana de OoO impide encontrar todo el ILP.

• Latencia de cada entrada a la (s) salida (s) . Mire qué instrucciones están en la cadena de dependencia de cada entrada a cada salida. por ejemplo, una opción puede necesitar una entrada para estar listo antes.
• recuento total de uop (para cuellos de botella en el rendimiento del front-end) , dominio fusionado en CPU de Intel. por ejemplo, Core2 y posteriores pueden en teoría emitir / renombrar 4 uops de dominio fusionado por reloj en el programador fuera de orden / ROB. La familia Sandybridge a menudo puede lograr eso en la práctica con el caché uop y el búfer de bucle, especialmente Skylake con sus decodificadores mejorados y el rendimiento del caché uop.

• uop cuenta para cada puerto de ejecución de back-end (dominio no fusionado). por ejemplo, el código de orden aleatorio a menudo causará un cuello de botella en el puerto 5 de las CPU de Intel. Por lo general, Intel solo publica números de rendimiento, no desgloses de puertos, por lo que debe mirar las tablas de Agner Fog (o la salida de IACA) para hacer algo significativo si no está repitiendo la misma instrucción un millón de veces.

  Por lo general, puede asumir la mejor programación / distribución, con uops que pueden ejecutarse en otros puertos sin robar los puertos ocupados con mucha frecuencia, pero sucede algo. ( ¿Cómo están programados los uops x86, exactamente? )

  Mirar el IPC no es suficiente ; dos instrucciones CPI = 1 pueden o no competir por el mismo puerto de ejecución. Si no lo hacen, pueden ejecutarse en paralelo. por ejemplo, Haswell solo puede ejecutar psadbw en el puerto 0 (5c de latencia, 1c de rendimiento, es decir, CPI = 1) pero es un solo uop, por lo que una combinación de 1 psadbw + 3 instrucciones add puede psadbw 4 instrucciones por reloj. Hay ALU vectoriales en 3 puertos diferentes en las CPU de Intel, con algunas operaciones replicadas en los 3 (por ejemplo, booleanos) y algunas solo en un puerto (por ejemplo, cambios antes de Skylake).

A veces, puede idear un par de estrategias diferentes, tal vez una menor latencia pero que cuesten más uops. Un ejemplo clásico es multiplicar por constantes como imul eax, ecx, 10 (1 uop, 3c de latencia en Intel) frente a lea eax, [rcx + rcx*4] / add eax,eax (2 uops, 2c de latencia). Los compiladores modernos tienden a elegir 2 LEA frente a 1 IMUL, aunque el sonido de hasta 3.7 favoreció a IMUL, a menos que pudiera hacer el trabajo con solo una instrucción más.

Consulte ¿Cuál es la forma eficiente de contar los bits establecidos en una posición o menos? para un ejemplo de análisis estático para algunas formas diferentes de implementar una función.

Vea también ¿Por qué mulss toma solo 3 ciclos en Haswell, diferente de las tablas de instrucciones de Agner? (que terminó siendo mucho más detallado de lo que cabría adivinar en el título de la pregunta) para otro resumen de análisis estático, y algunas cosas interesantes sobre el desenrollado con múltiples acumuladores para una reducción.

Cada (?) Unidad funcional está canalizada

El divisor se canaliza en las CPU recientes, pero no se canaliza completamente . (Sin embargo, la división FP es un solo uop, así que si haces un divps mezclado con docenas de mulps / addps , puede tener un impacto de rendimiento insignificante si la latencia no importa: división de punto flotante frente a multiplicación de punto flotante . rcpps + a Newton La iteración es peor rendimiento y aproximadamente la misma latencia.

Todo lo demás está completamente canalizado en las CPU de Intel convencionales; rendimiento de ciclo múltiple (recíproco) para un solo uop. (Los desplazamientos de enteros de cuenta variable como shl eax, cl tienen un rendimiento inferior al esperado para sus 3 uops, porque crean una dependencia a través de la combinación de banderas uops. Pero si rompe esa dependencia a través de FLAGS con un add o algo así, puede obtener un mejor rendimiento y latencia )

En AMD antes de Ryzen, el multiplicador de enteros también está parcialmente segmentado. por ejemplo, el imul ecx, edx Bulldozer imul ecx, edx es solo de 1 uop, pero con 4c de latencia, 2c de rendimiento.

Xeon Phi (KNL) también tiene algunas instrucciones aleatorias no completamente canalizadas, pero tiende a tener cuellos de botella en la parte delantera (decodificación de instrucciones), no en la parte trasera, y tiene un pequeño búfer + OoO exec capacidad para ocultar -en fin de burbujas.

Si se trata de una instrucción de punto flotante, todas las instrucciones de punto flotante antes de que se haya emitido (las instrucciones de punto flotante tienen una ordenación de instrucciones estáticas)

No.

Tal vez haya leído eso para Silvermont, que no hace execiones OoO para FP / SIMD, solo enteros (con una ventana pequeña de ~ 20 uop). ¿Quizás algunos chips ARM también son así, con programadores más simples para NEON? No sé mucho sobre los detalles de ARM uarch.

Las principales microarquitecturas de núcleo grande, como la familia P6 / SnB, y todos los chips AMD OoO, ejecutan OoO exec para las instrucciones SIMD y FP de la misma manera que para los enteros. Las CPU de AMD usan un programador separado, pero Intel usa un programador unificado para que su tamaño completo pueda aplicarse para encontrar ILP en código entero o FP, lo que se esté ejecutando actualmente.

Incluso Knight''s Landing (en Xeon Phi), con sede en Silvermont, realiza el ejecutivo de OoO para SIMD.

En general, x86 no es muy sensible al ordenamiento de instrucciones, pero la programación uop no realiza un análisis de ruta crítica. Por lo tanto, a veces podría ser útil colocar primero las instrucciones en la ruta crítica, de modo que no se queden atascados esperando con sus entradas listas mientras otras instrucciones se ejecutan en ese puerto, lo que lleva a un puesto más grande cuando lleguemos a las instrucciones que necesitan el resultado del camino critico. (Es decir, por eso es el camino crítico).

Mi intento de predecir la latencia de Haswell es algo así:

Sí, eso se ve bien. shufps ejecuta en el puerto 5, addps ejecuta en p1, mulps ejecuta en p0 o p1. Skylake deja caer la unidad dedicada de adición de FP y ejecuta SIMD FP add / mul / FMA en las unidades de FMA en p0 / p1, todas con una latencia de 4c (arriba / abajo de 3/5/5 en Haswell, o 3/3/5 en Broadwell).

Este es un buen ejemplo de por qué mantener un vector de dirección XYZ completo en un vector SIMD generalmente apesta. Mantener una matriz de X, una matriz de Y y una matriz de Z, le permitiría hacer 4 productos cruzados en paralelo sin barajar.

La etiqueta wiki de la SSE tiene un enlace a estas diapositivas: SIMD en Insomniac Games (GDC 2015) que cubre los problemas de matriz de estructuras frente a la estructura de matrices para vectores 3D, y por qué a menudo es un error tratar siempre de SIMD una sola operación en lugar de utilizar SIMD para realizar múltiples operaciones en paralelo.