performance - ¿Cómo se programan x86 uops, exactamente?

optimization intel (2)

Las CPU x86 modernas descomponen la secuencia de instrucciones entrantes en microoperaciones (uops ¹ ) y luego programan estos uops out-of-order medida que sus entradas están listas. Si bien la idea básica es clara, me gustaría saber los detalles específicos de cómo están programadas las instrucciones, ya que afecta las decisiones de micro-optimización.

Por ejemplo, tome el siguiente bucle de juguete ² :

top: lea eax, [ecx + 5] popcnt eax, eax add edi, eax dec ecx jnz top

esto básicamente implementa el ciclo (con la siguiente correspondencia: eax -> total, c -> ecx ):

do { total += popcnt(c + 5); } while (--c > 0);

Estoy familiarizado con el proceso de optimización de cualquier ciclo pequeño mirando el desglose uop, las latencias de la cadena de dependencia, etc. En el ciclo de arriba solo tenemos una cadena de dependencia transportada: dec ecx . Las primeras tres instrucciones del ciclo ( lea , imul , add ) son parte de una cadena de dependencia que comienza cada ciclo de forma fresca.

La dec final y la jne están fusionadas. Así que tenemos un total de 4 uops de dominio fusionado y una cadena de dependencia solo transportada por bucle con una latencia de 1 ciclo. Por lo tanto, según ese criterio, parece que el ciclo se puede ejecutar a 1 ciclo / iteración.

Sin embargo, también debemos mirar la presión del puerto:

El lea puede ejecutarse en los puertos 1 y 5
El popcnt puede ejecutarse en el puerto 1
El add puede ejecutarse en el puerto 0, 1, 5 y 6
El jnz ejecuta en el puerto 6

Entonces, para llegar a 1 ciclo / iteración, casi necesita que ocurra lo siguiente:

El popcnt debe ejecutarse en el puerto 1 (el único puerto en el que se puede ejecutar)
El lea debe ejecutarse en el puerto 5 (y nunca en el puerto 1)
El add debe ejecutarse en el puerto 0, y nunca en ninguno de los otros tres puertos que puede ejecutar en
El jnz solo puede ejecutarse en el puerto 6 de todos modos

¡Son muchas las condiciones! Si las instrucciones se programaran aleatoriamente, podría obtener un rendimiento mucho peor. Por ejemplo, el 75% del add iría al puerto 1, 5 o 6, lo que retrasaría el popcnt , lea o jnz en un ciclo. Del mismo modo para el lea que puede ir a 2 puertos, uno compartido con popcnt .

Por otro lado, IACA informa un resultado muy cercano al óptimo, 1.05 ciclos por iteración:

Intel(R) Architecture Code Analyzer Version - 2.1 Analyzed File - l.o Binary Format - 64Bit Architecture - HSW Analysis Type - Throughput Throughput Analysis Report -------------------------- Block Throughput: 1.05 Cycles Throughput Bottleneck: FrontEnd, Port0, Port1, Port5 Port Binding In Cycles Per Iteration: --------------------------------------------------------------------------------------- | Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | --------------------------------------------------------------------------------------- | Cycles | 1.0 0.0 | 1.0 | 0.0 0.0 | 0.0 0.0 | 0.0 | 1.0 | 0.9 | 0.0 | --------------------------------------------------------------------------------------- N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0) D - Data fetch pipe (on ports 2 and 3), CP - on a critical path F - Macro Fusion with the previous instruction occurred * - instruction micro-ops not bound to a port ^ - Micro Fusion happened # - ESP Tracking sync uop was issued @ - SSE instruction followed an AVX256 instruction, dozens of cycles penalty is expected ! - instruction not supported, was not accounted in Analysis | Num Of | Ports pressure in cycles | | | Uops | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | | --------------------------------------------------------------------------------- | 1 | | | | | | 1.0 | | | CP | lea eax, ptr [ecx+0x5] | 1 | | 1.0 | | | | | | | CP | popcnt eax, eax | 1 | 0.1 | | | | | 0.1 | 0.9 | | CP | add edi, eax | 1 | 0.9 | | | | | | 0.1 | | CP | dec ecx | 0F | | | | | | | | | | jnz 0xfffffffffffffff4

Refleja más o menos la programación "ideal" necesaria que mencioné anteriormente, con una pequeña desviación: muestra el add puerto 5 de robo en 1 de cada 10 ciclos. Tampoco sabe que la rama fusionada va a ir al puerto 6, ya que se prevé tomar, por lo que coloca la mayoría de los uops para la bifurcación en el puerto 0, y la mayoría de los uops para el add en el puerto 6, más bien que al revés.

No está claro si los 0.05 ciclos extra que IACA informa sobre el óptimo es el resultado de un análisis profundo y preciso, o una consecuencia menos profunda del algoritmo que utiliza, por ejemplo, analizar el ciclo en un número fijo de ciclos, o simplemente un error o lo que sea. Lo mismo ocurre con la fracción 0.1 de un uop que cree que irá al puerto no ideal. Tampoco está claro si uno explica al otro: creo que asignar erróneamente un puerto 1 de 10 veces provocaría un recuento de ciclo de 11/10 = 1.1 ciclos por iteración, pero no resolví el flujo descendente real. resultados - tal vez el impacto es menos en promedio. O podría ser un redondeo (0.05 == 0.1 a 1 lugar decimal).

Entonces, ¿cómo se programan las CPU modernas x86? En particular:

Cuando varios uops están listos en la estación de reservas, ¿en qué orden están programados en los puertos?
Cuando un uop puede ir a varios puertos (como el add y el lea en el ejemplo anterior), ¿cómo se decide qué puerto se elige?
Si alguna de las respuestas implica un concepto como el más antiguo para elegir entre los uops, ¿cómo se define? Edad desde que fue entregado a la RS Edad desde que se hizo listo? ¿Cómo se rompen los lazos? ¿El orden del programa alguna vez entra?

Resultados en Skylake

Midamos algunos resultados reales en Skylake para verificar qué respuestas explican la evidencia experimental, así que aquí hay algunos resultados medidos del mundo real (de perf ) en mi caja de Skylake. Confusamente, voy a cambiar a usar imul para mi instrucción "solo se ejecuta en un puerto", ya que tiene muchas variantes, incluidas las versiones de 3 argumentos que le permiten usar registros diferentes para la (s) fuente (s) y el destino. Esto es muy útil cuando se trata de construir cadenas de dependencia. También evita toda la "dependencia incorrecta en el destino" que tiene popcnt .

Instrucciones independientes

Comencemos por ver el caso simple (?) De que las instrucciones son relativamente independientes, sin cadenas de dependencia que no sean triviales como el contador de bucles.

Aquí hay un bucle de 4 uop (solo 3 uops ejecutados) con leve presión. Todas las instrucciones son independientes (no comparta fuentes ni destinos). El add podría, en principio, robar el p1 necesario por el imul o p6 necesita el dic:

Ejemplo 1

instr p0 p1 p5 p6 xor (elim) imul X add X X X X dec X top: xor r9, r9 add r8, rdx imul rax, rbx, 5 dec esi jnz top The results is that this executes with perfect scheduling at 1.00 cycles / iteration: 560,709,974 uops_dispatched_port_port_0 ( +- 0.38% ) 1,000,026,608 uops_dispatched_port_port_1 ( +- 0.00% ) 439,324,609 uops_dispatched_port_port_5 ( +- 0.49% ) 1,000,041,224 uops_dispatched_port_port_6 ( +- 0.00% ) 5,000,000,110 instructions:u # 5.00 insns per cycle ( +- 0.00% ) 1,000,281,902 cycles:u ( +- 0.00% )

Como era de esperar, p1 y p6 son totalmente utilizados por imul y dec/jnz respectivamente, y luego el add emite aproximadamente la mitad y la mitad entre los puertos disponibles restantes. Obsérvese aproximadamente : la relación real es del 56% y del 44%, y esta relación es bastante estable en todas las ejecuciones (tenga en cuenta la variación de +- 0.49% ). Si ajusto la alineación del lazo, la división cambia (53/46 para alineación 32B, más como 57/42 para alineación 32B + 4). Ahora, si cambiamos nada, excepto la posición de imul en el ciclo:

Ejemplo 2

top: imul rax, rbx, 5 xor r9, r9 add r8, rdx dec esi jnz top

Entonces, de repente, la división p1 / p5 es exactamente 50% / 50%, con una variación de 0.00%:

500,025,758 uops_dispatched_port_port_0 ( +- 0.00% ) 1,000,044,901 uops_dispatched_port_port_1 ( +- 0.00% ) 500,038,070 uops_dispatched_port_port_5 ( +- 0.00% ) 1,000,066,733 uops_dispatched_port_port_6 ( +- 0.00% ) 5,000,000,439 instructions:u # 5.00 insns per cycle ( +- 0.00% ) 1,000,439,396 cycles:u ( +- 0.01% )

Entonces eso ya es interesante, pero es difícil saber qué está pasando. Quizás el comportamiento exacto dependa de las condiciones iniciales en la entrada de bucle y sea sensible al orden dentro del bucle (por ejemplo, porque se usan contadores). Este ejemplo muestra que está ocurriendo algo más que una programación "aleatoria" o "estúpida". En particular, si elimina la instrucción imul del ciclo, obtendrá lo siguiente:

Ejemplo 3

330,214,329 uops_dispatched_port_port_0 ( +- 0.40% ) 314,012,342 uops_dispatched_port_port_1 ( +- 1.77% ) 355,817,739 uops_dispatched_port_port_5 ( +- 1.21% ) 1,000,034,653 uops_dispatched_port_port_6 ( +- 0.00% ) 4,000,000,160 instructions:u # 4.00 insns per cycle ( +- 0.00% ) 1,000,235,522 cycles:u ( +- 0.00% )

Aquí, el add ahora está aproximadamente distribuido equitativamente entre p0 , p1 y p5 , por lo que la presencia del imul sí afectó la programación de add : no fue solo una consecuencia de alguna regla de "evitar el puerto 1".

Tenga en cuenta que la presión total del puerto es de solo 3 uops / ciclo, ya que el xor es un modismo de puesta a cero y se elimina en el renombrador. Probemos con la presión máxima de 4 uops. Espero que cualquier mecanismo que se inicie en la parte superior también pueda programarlo perfectamente. Solo cambiamos xor r9, r9 a xor r9, r10 , por lo que ya no es una expresión idiomática de xor r9, r9 a cero. Obtenemos los siguientes resultados:

Ejemplo 4

top: xor r9, r10 add r8, rdx imul rax, rbx, 5 dec esi jnz top 488,245,238 uops_dispatched_port_port_0 ( +- 0.50% ) 1,241,118,197 uops_dispatched_port_port_1 ( +- 0.03% ) 1,027,345,180 uops_dispatched_port_port_5 ( +- 0.28% ) 1,243,743,312 uops_dispatched_port_port_6 ( +- 0.04% ) 5,000,000,711 instructions:u # 2.66 insns per cycle ( +- 0.00% ) 1,880,606,080 cycles:u ( +- 0.08% )

Oops! En lugar de programar uniformemente todo a través de p0156 , el planificador ha subutilizado p0 (solo está ejecutando algo ~ 49% de ciclos), y por lo tanto, p1 y p6 están sobrescritos porque están ejecutando tanto sus operaciones requeridas de imul como dec/jnz . Este comportamiento, creo que es consistente con un indicador de presión basado en contador como lo indicaba hayesti en su respuesta, y con uops asignados a un puerto en el momento de emisión, no en el tiempo de ejecución como mencionaron hayesti y Peter Cordes. Ese comportamiento ³ hace que ejecutar la regla de uops ready más antigua no sea tan eficaz. Si los uops no estaban vinculados a los puertos de ejecución en cuestión, sino más bien a la ejecución, esta regla "más antigua" solucionaría el problema anterior después de una iteración: una vez que un imul y una dec/jnz se dec/jnz para una única iteración, lo harán siempre ser más viejo que el xor competidor y add instrucciones, por lo que siempre debe programarse primero. Sin embargo, estoy aprendiendo que si se asignan puertos en el momento de la emisión, esta regla no ayuda porque los puertos están predeterminados en el momento de la emisión. Supongo que aún ayuda un poco al favorecer las instrucciones que forman parte de las largas cadenas de dependencia (ya que tienden a quedarse atrás), pero no es la panacea que pensé que era.

Eso también parece ser una explicación de los resultados anteriores: a p0 se le asigna más presión de la que realmente tiene porque el combo dec/jnz en teoría puede ejecutarse en p06 . De hecho, como se pronostica la ramificación, solo llega a p6 , pero tal vez esa información no se pueda incorporar al algoritmo de equilibrio de presión, por lo que los contadores tienden a ver la misma presión en p016 , lo que significa que el add y el xor se extienden diferente de lo óptimo.

Probablemente podamos probar esto, desenrollando el bucle un poco para que el jnz sea menos importante ...

¹ OK, está escrito correctamente μops , pero eso mata la capacidad de búsqueda y realmente escribe el carácter "μ" que suelo copiar, pegar el personaje de una página web.

² Originalmente había usado imul lugar de popcnt en el ciclo, pero, increíblemente, ¡ IACA no lo admite !

³ Tenga en cuenta que no estoy sugiriendo que este sea un diseño deficiente ni nada por el estilo. Probablemente haya muy buenas razones de hardware por las cuales el planificador no puede tomar fácilmente todas sus decisiones en el momento de la ejecución.

Esto es lo que encontré en Skylake, desde el ángulo que los uops se asignan a los puertos en el momento de la emisión (es decir, cuando se emiten a la RS), no en el momento del envío (es decir, en el momento en que se envían a ejecutar) . Antes había entendido que la decisión del puerto se tomó en el momento del despacho.

Hice una variedad de pruebas que intentaron aislar secuencias de operaciones de add que pueden ir a p0156 y operaciones de imul que van solo al puerto 0. Una prueba típica es algo como esto:

mov eax, [edi] mov eax, [edi] mov eax, [edi] mov eax, [edi] ... many more mov instructions mov eax, [edi] mov eax, [edi] mov eax, [edi] mov eax, [edi] imul ebx, ebx, 1 imul ebx, ebx, 1 imul ebx, ebx, 1 imul ebx, ebx, 1 add r9, 1 add r8, 1 add ecx, 1 add edx, 1 add r9, 1 add r8, 1 add ecx, 1 add edx, 1 add r9, 1 add r8, 1 add ecx, 1 add edx, 1 mov eax, [edi] mov eax, [edi] mov eax, [edi] mov eax, [edi] ... many more mov instructions mov eax, [edi] mov eax, [edi] mov eax, [edi] mov eax, [edi]

Básicamente hay una larga p23 instrucciones de mov eax, [edi] , que solo se emiten en p23 y por lo tanto no obstruyen los puertos utilizados por las instrucciones (podría haber usado también instrucciones nop , pero la prueba sería una un poco diferente ya que nop no se emite a la RS). Esto es seguido por la sección de "carga útil", compuesta aquí de 4 imul y 12 add , y luego una sección de salida de más instrucciones ficticias mov .

Primero, echemos un vistazo a la patente que hayesti vinculada anteriormente, y sobre la cual describe la idea básica: contadores para cada puerto que rastrean el número total de uops asignados al puerto, que se utilizan para equilibrar la carga de las asignaciones de puertos. Eche un vistazo a esta tabla incluida en la descripción de la patente:

Esta tabla se usa para elegir entre p0 o p1 para los 3 uups en un grupo de problemas para la arquitectura de 3 niveles discutida en la patente. Tenga en cuenta que el comportamiento depende de la posición del uop en el grupo , y que hay 4 reglas ¹ basadas en el recuento, que distribuyen los uops de una manera lógica. En particular, el recuento debe ser de +/- 2 o superior antes de que se le asigne al grupo el puerto infrautilizado.

Veamos si podemos observar el comportamiento de "posición en el grupo de problemas" en Sklake. Utilizamos una carga útil de un solo add como:

add edx, 1 ; position 0 mov eax, [edi] mov eax, [edi] mov eax, [edi]

... y lo deslizamos dentro del mandril de 4 instrucciones como:

mov eax, [edi] add edx, 1 ; position 1 mov eax, [edi] mov eax, [edi]

... y así sucesivamente, probando las cuatro posiciones dentro del grupo de problemas ² . Esto muestra lo siguiente, cuando el RS está lleno (de instrucciones mov ) pero sin presión de puerto de ninguno de los puertos relevantes:

Las primeras instrucciones de add van a p5 o p6 , con el puerto seleccionado generalmente alternando a medida que la instrucción disminuye (es decir, add instrucciones en posiciones pares, ve a p5 y en posiciones impares pasa a p6 ).
La segunda instrucción de add también va a p56 , cualquiera de los dos a los que el primero no fue.
Después de eso, las instrucciones add comienzan a equilibrar en torno a p0156 , con p5 y p6 usualmente por delante, pero con las cosas relativamente uniformes en general (es decir, la brecha entre p56 y los otros dos puertos no aumenta).

A continuación, eché un vistazo a lo que sucede si carga p1 con operaciones de imul , luego primero en un grupo de operaciones de add :

imul ebx, ebx, 1 imul ebx, ebx, 1 imul ebx, ebx, 1 imul ebx, ebx, 1 add r9, 1 add r8, 1 add ecx, 1 add edx, 1 add r9, 1 add r8, 1 add ecx, 1 add edx, 1 add r9, 1 add r8, 1 add ecx, 1 add edx, 1

Los resultados muestran que el planificador lo maneja bien: todos los imul llegaron a programarse en p1 (como se esperaba), y luego ninguna de las instrucciones de add posteriores fue a p1 , p056 se distribuyó alrededor de p056 . Entonces aquí la programación está funcionando bien.

Por supuesto, cuando la situación se invierte, y la serie de imul viene después del add s, p1 se carga con su parte de adds antes del golpe de imul . Esto se debe a que la asignación del puerto se realiza en orden en el momento de la emisión, ya que no hay un mecanismo para "mirar hacia adelante" y ver el imul al programar los add .

En general, el programador busca hacer un buen trabajo en estos casos de prueba.

No explica lo que sucede en bucles más pequeños y ajustados como los siguientes:

sub r9, 1 sub r10, 1 imul ebx, edx, 1 dec ecx jnz top

Al igual que el Ejemplo 4 en mi pregunta, este ciclo solo llena p0 en ~ 30% de ciclos, a pesar de que hay dos instrucciones sub que deberían poder ir a p0 en cada ciclo. p1 y p6 están sobresuscritos, cada uno ejecutando 1,24 uops por cada iteración (1 es ideal). No pude triangular la diferencia entre los ejemplos que funcionan bien en la parte superior de esta respuesta con los bucles malos, pero todavía hay muchas ideas para probar.

Noté que los ejemplos sin las diferencias de latencia de las instrucciones no parecen sufrir este problema. Por ejemplo, aquí hay otro bucle de 4 uop con presión de puerto "compleja":

top: sub r8, 1 ror r11, 2 bswap eax dec ecx jnz top

El mapa de uop es el siguiente:

instr p0 p1 p5 p6 sub X X X X ror X X bswap X X dec/jnz X

Entonces, el sub debe ir siempre a p15 , compartido con bswap para que las cosas funcionen. Ellas hacen:

Estadísticas del contador de rendimiento para ''./sched-test2'' (2 carreras):

999,709,142 uops_dispatched_port_port_0 ( +- 0.00% ) 999,675,324 uops_dispatched_port_port_1 ( +- 0.00% ) 999,772,564 uops_dispatched_port_port_5 ( +- 0.00% ) 1,000,991,020 uops_dispatched_port_port_6 ( +- 0.00% ) 4,000,238,468 uops_issued_any ( +- 0.00% ) 5,000,000,117 instructions:u # 4.99 insns per cycle ( +- 0.00% ) 1,001,268,722 cycles:u ( +- 0.00% )

Por lo tanto, parece que el problema puede estar relacionado con las latencias de instrucción (sin duda, existen otras diferencias entre los ejemplos). Eso es algo que surgió en esta pregunta similar .

¹ La tabla tiene 5 reglas, pero la regla para conteos 0 y -1 es idéntica.

² Por supuesto, no puedo estar seguro de dónde comienzan y terminan los grupos de problemas, pero a pesar de que probamos cuatro posiciones diferentes a medida que deslizamos hacia abajo cuatro instrucciones (pero las etiquetas podrían estar equivocadas). Tampoco estoy seguro de que el tamaño máximo del grupo de problemas sea 4, las partes anteriores de la canalización son más amplias, pero creo que sí y algunas pruebas parecieron demostrar que sí (los bucles con un múltiplo de 4 uops mostraron un comportamiento de programación constante). En cualquier caso, las conclusiones se mantienen con diferentes tamaños de grupos de programación.

Sus preguntas son difíciles por un par de razones:

La respuesta depende mucho de la microarquitectura del procesador, que puede variar significativamente de generación en generación.
Estos son detalles minuciosos que Intel generalmente no publica al público.

Sin embargo, intentaré responder ...

Cuando varios uops están listos en la estación de reservas, ¿en qué orden están programados en los puertos?

Debería ser el más antiguo [ver abajo], pero su millaje puede variar. La microarquitectura P6 (utilizada en Pentium Pro, 2 y 3) utilizó una estación de reserva con cinco programadores (uno por puerto de ejecución); los programadores usaron un puntero de prioridad como lugar para comenzar a escanear y listo para enviar. Era solo pseudo FIFO, por lo que es muy posible que la instrucción ready más antigua no siempre estuviera programada. En la microarquitectura NetBurst (utilizada en Pentium 4), abandonaron la estación unificada de reservas y utilizaron dos colas uop en su lugar. Éstas eran colas de prioridad colapsadas adecuadas, por lo que se garantizó que los programadores obtuvieran la instrucción lista más antigua. La arquitectura del Núcleo regresó a una estación de reservación y me arriesgaría a adivinar que usaron la cola de prioridad colapsante, pero no puedo encontrar una fuente para confirmar esto. Si alguien tiene una respuesta definitiva, soy todo oídos.

Cuando un uop puede ir a varios puertos (como el agregar y el lea en el ejemplo anterior), ¿cómo se decide qué puerto se elige?

Eso es difícil de saber. Lo mejor que pude encontrar es una patente de Intel describiendo tal mecanismo. Esencialmente, mantienen un contador para cada puerto que tiene unidades funcionales redundantes. Cuando los uops salen de la parte frontal de la estación de reserva, se les asigna un puerto de despacho. Si tiene que decidir entre múltiples unidades de ejecución redundantes, los contadores se utilizan para distribuir el trabajo de manera uniforme. Los contadores se incrementan y disminuyen a medida que los uops entran y salen de la estación de reserva respectivamente.

Naturalmente, esto es solo una heurística y no garantiza un cronograma perfecto sin conflictos, sin embargo, aún puedo verlo trabajando con tu ejemplo de juguete. Las instrucciones que solo pueden ir a un puerto en última instancia, influirían en el planificador para enviar los uops "menos restringidos" a otros puertos.

En cualquier caso, la presencia de una patente no implica necesariamente que la idea haya sido adoptada (aunque, dicho esto, uno de los autores también era un líder tecnológico del Pentium 4, entonces, ¿quién sabe?)

Si alguna de las respuestas implica un concepto como el más antiguo para elegir entre los uops, ¿cómo se define? Edad desde que fue entregado a la RS Edad desde que se hizo listo? ¿Cómo se rompen los lazos? ¿El orden del programa alguna vez entra?

Como los uops se insertan en la estación de reservas en orden, el más antiguo aquí hace referencia a la hora en que entró en la estación de reservas, es decir, la más antigua en el orden del programa.

Por cierto, tomaría esos resultados de IACA con un grano de sal ya que pueden no reflejar los matices del hardware real. En Haswell, hay un contador de hardware llamado uops_executed_port que puede decirle cuántos ciclos en su hilo fueron uops a los puertos 0-7. ¿Tal vez podría aprovechar estos para obtener una mejor comprensión de su programa?