performance - Comprender el impacto de lfence en un bucle con dos largas cadenas de dependencia, para aumentar la longitud

assembly x86 (2)

Estaba jugando con el código en esta respuesta , modificándolo ligeramente:

BITS 64 GLOBAL _start SECTION .text _start: mov ecx, 1000000 .loop: ;T is a symbol defined with the CLI (-DT=...) TIMES T imul eax, eax lfence TIMES T imul edx, edx dec ecx jnz .loop mov eax, 60 ;sys_exit xor edi, edi syscall

Sin la lfence , los resultados que obtengo son consistentes con el análisis estático en esa respuesta.

Cuando introduzco un solo lfence esperaría que la CPU ejecute imul edx, edx secuencia imul edx, edx de la iteración k-th en paralelo con la secuencia imul eax, eax de la siguiente iteración ( k + 1-th ).
Algo como esto (llamando a A el imul eax, eax secuencia de imul eax, eax y D el imul edx, edx uno):

| | A | D A | D A | D A | ... | D A | D | V time

Tomando más o menos el mismo número de ciclos pero para una ejecución paralela no pareada.

Cuando taskset -c 2 ocperf.py stat -r 5 -e cycles:u ''-x '' ./main-$T el número de ciclos, para la versión original y modificada, con el conjunto de taskset -c 2 ocperf.py stat -r 5 -e cycles:u ''-x '' ./main-$T para T en el rango a continuación obtengo

T Cycles:u Cycles:u Delta lfence no lfence 10 42047564 30039060 12008504 15 58561018 45058832 13502186 20 75096403 60078056 15018347 25 91397069 75116661 16280408 30 108032041 90103844 17928197 35 124663013 105155678 19507335 40 140145764 120146110 19999654 45 156721111 135158434 21562677 50 172001996 150181473 21820523 55 191229173 165196260 26032913 60 221881438 180170249 41711189 65 250983063 195306576 55676487 70 281102683 210255704 70846979 75 312319626 225314892 87004734 80 339836648 240320162 99516486 85 372344426 255358484 116985942 90 401630332 270320076 131310256 95 431465386 285955731 145509655 100 460786274 305050719 155735555

¿Cómo se pueden explicar los valores de los Cycles:u lfence ?
Hubiera esperado que fueran similares a los de los Cycles:u no lfence ya que una sola lfence debería evitar que solo la primera iteración se ejecute en paralelo para los dos bloques.
No creo que se deba a la sobrecarga de información, ya que creo que debería ser constante para todos los T s.

Me gustaría arreglar lo que está mal con mi forma mentis al tratar con el análisis estático de código.

Apoyo repositorio con archivos de origen .

Creo que se está midiendo con precisión, y la explicación es microarquitectura, no cualquier tipo de error de medición.

Pienso que sus resultados para T media y baja apoyan la conclusión de que lfence impide que el front-end emita más allá de la lfence hasta que se lfence todas las instrucciones anteriores , en lugar de tener todos los uops de ambas cadenas ya emitidos y solo esperar a que lfence vuelta. cambie y deje que los multiplicados de cada cadena comiencen a despacharse en ciclos alternos.

(port1 obtendría edx, eax, empty, edx, eax, empty, ... para el multiplicador de rendimiento de latencia / 1c de Skylake de inmediato, si lfence no bloqueara el extremo delantero y la sobrecarga no se lfence con T. )

Está perdiendo el rendimiento total cuando solo uops de la primera cadena están en el programador porque el front-end no ha masticado aún el imul edx,edx y la rama de bucle. Y para la misma cantidad de ciclos al final de la ventana cuando la tubería está casi drenada y solo quedan los ops de la segunda cadena.

El delta superior parece lineal hasta aproximadamente T = 60. No corrí los números, pero la pendiente hasta allí parece razonable para que T * 0.25 relojes T * 0.25 emitan el primer cuello de botella en la ejecución de la cadena frente a la latencia 3c. es decir, el crecimiento delta puede ser 1/12 tan rápido como el total de los ciclos de ausencia .

Entonces (dada la sobrecarga de lfence continuación), con T <60:

no_lfence cycles/iter ~= 3T # OoO exec finds all the parallelism lfence cycles/iter ~= 3T + T/4 + 9.3 # lfence constant + front-end delay delta ~= T/4 + 9.3

@Margaret informa que T/4 es un mejor ajuste que 2*T / 4 , pero hubiera esperado T / 4 tanto al inicio como al final, para un total de 2T / 4 de pendiente del delta.

Después de aproximadamente T = 60, el delta crece mucho más rápidamente (pero aún de manera lineal), con una pendiente aproximadamente igual a la de los ciclos totales de cercado, por lo tanto, aproximadamente 3c por T. Creo que en ese punto, el tamaño del programador (Estación de reserva) es Limitando la ventana fuera de orden. Probablemente probó en un Haswell o Sandybridge / IvyBridge, ( que tienen un programador de 60 entradas o 54 entradas respectivamente . Skylake tiene 97 entradas.

El RS rastrea uops no ejecutados. Cada entrada de RS contiene 1 uop de dominio no fusionado que está esperando que sus entradas estén listas, y su puerto de ejecución, antes de que pueda enviarse y abandonar el RS ¹ .

Después de una lfence , el front-end se emite a 4 por reloj mientras que el back-end se ejecuta a 1 por 3 relojes, emitiendo 60 uops en ~ 15 ciclos, durante los cuales solo se ejecutaron 5 instrucciones de la cadena edx . (Aquí no hay carga ni micro-fusión de tienda, por lo que cada uop de dominio fusionado del front-end sigue siendo solo 1 uop de dominio no fusionado en el RS ² ).

Para la T grande, la RS se llena rápidamente, momento en el que el extremo frontal solo puede avanzar a la velocidad del back-end. (Para la T pequeña, golpeamos la siguiente lfence de iteración antes de que eso suceda, y eso es lo que detiene la interfaz). Cuando T> RS_size , el back-end no puede ver ninguno de los uops de la cadena eax imul hasta que el progreso suficiente de back-end a través de la cadena edx haya hecho espacio en el RS. En ese momento, un imul de cada cadena puede enviarse cada 3 ciclos, en lugar de solo la primera o la segunda cadena.

Recuerde en la primera sección que el tiempo que pasó justo después de lfence solo ejecutó la primera cadena = tiempo justo antes de que lfence solo ejecutara la segunda cadena. Eso se aplica aquí, también.

Obtenemos algo de este efecto incluso sin lfence , para T> RS_size , pero existe la posibilidad de superposición en ambos lados de una cadena larga. El ROB es al menos el doble del tamaño del RS, por lo que la ventana fuera de orden cuando no está bloqueada por la lfence debería poder mantener ambas cadenas en vuelo constantemente, incluso cuando T es algo más grande que la capacidad del programador. (Recuerda que dejas la RS tan pronto como se ejecutan. No estoy seguro de si eso significa que tienen que terminar de ejecutar y reenviar su resultado, o simplemente comenzar a ejecutar, pero esa es una pequeña diferencia para las instrucciones cortas de ALU. Una vez están listos, solo el ROB los retiene hasta que se retiran, en orden del programa.)

El ROB y el archivo de registro no deben limitar el tamaño de la ventana fuera de orden ( http://blog.stuffedcow.net/2013/05/measuring-rob-capacity/ ) en esta situación hipotética, o en su situación real. situación. Ambos deberían ser bastante grandes.

El bloqueo del front-end es un detalle de implementación de lfence en los lfence de Intel . El manual solo dice que las instrucciones posteriores no pueden ejecutarse . Esa redacción permitiría al front-end emitirlos / renombrarlos a todos en el programador (Estación de Reservaciones) y ROB mientras lfence aún está en espera, siempre y cuando ninguno sea enviado a una unidad de ejecución.

Por lo tanto, una lfence más lfence podría tener una sobrecarga plana hasta T = RS_size, luego la misma pendiente que ve ahora para T> 60. (Y la parte constante de la sobrecarga puede ser menor.)

Tenga en cuenta que las garantías sobre la ejecución especulativa de las ramas condicionales / indirectas después de la lfence aplican a la ejecución , no (por lo que sé) a la lfence de códigos. El simple hecho de activar la recuperación de código no es (AFAIK) útil para un ataque de Spectre o Meltdown. Posiblemente un canal lateral de temporización para detectar cómo se decodifica podría decirle algo sobre el código recuperado ...

Creo que LFENCE de AMD es al menos tan fuerte en las CPU AMD reales, cuando el MSR relevante está habilitado. ( ¿LFENCE se serializa en procesadores AMD? ).

`lfence` generales adicionales:

Sus resultados son interesantes, pero no me sorprende en absoluto que haya una sobrecarga constante significativa de lfence sí (para T pequeña), así como el componente que se escala con T.

Recuerde que lfence no permite que comiencen las instrucciones posteriores hasta que las instrucciones anteriores se hayan retirado . Esto es probablemente al menos un par de ciclos / etapas de tubería más tarde que cuando sus resultados están listos para el desvío hacia otras unidades de ejecución (es decir, la latencia normal).

Por lo tanto, para la T pequeña, es definitivamente significativo que agregue una latencia adicional a la cadena al requerir que el resultado no solo esté listo, sino que también se escriba en el archivo de registro.

Es probable que se requiera un ciclo adicional para que lfence permita que la etapa de problema / cambio de nombre comience a funcionar nuevamente después de detectar el retiro de la última instrucción anterior. El proceso de emisión / cambio de nombre toma varias etapas (ciclos), y quizás lfence bloquee al comienzo de esto, en lugar del último paso antes de que se agreguen uops a la parte de OoO del núcleo.

Incluso el respaldo en sí mismo tiene un rendimiento de 4 ciclos en la familia SnB, según las pruebas de Agner Fog. Agner Fog informa 2 uops de dominio fusionado (no sin fusionar), pero en Skylake lo mido en 6 dominios fusionados (aún sin fusionar) si solo tengo 1 lfence . ¡Pero con más lfence consecutiva, es menos Uops! Hasta ~ 2 uops por lfence con muchos back-to-back, que es como lo mide Agner.

lfence / dec / jnz (un bucle cerrado sin trabajo) se ejecuta en 1 iteración por ~ 10 ciclos en SKL, por lo que podría darnos una idea de la latencia adicional real que lfence agrega a las cadenas de dep, incluso sin el extremo frontal y RS-llenos de cuellos de botella.

Medición de los lfence generales con una sola cadena de dep , siendo el ejecutivo de OoO irrelevante:

.loop: ;mfence ; mfence here: ~62.3c (with no lfence) lfence ; lfence here: ~39.3c times 10 imul eax,eax ; with no lfence: 30.0c ; lfence ; lfence here: ~39.6c dec ecx jnz .loop

Sin lfence , se ejecuta a los 30.0c esperados por iter. Con lfence , se ejecuta a ~ 39.3c por iter, por lo que lfence efectivamente agregó ~ 9.3c de "latencia extra" a la cadena de dep del camino crítico. (Y 6 uops de dominio fusionado extra).

Con lfence después de la cadena imul, justo antes de la rama de bucle, es un poco más lento. Pero no un ciclo completo más lento, por lo que eso indicaría que el front-end está emitiendo el loop-branch + e imul en un solo grupo de problemas después de que lfence permita que la ejecución se reanude. Siendo ese el caso, IDK por qué es más lento. No es de rama se pierde.

Obteniendo el comportamiento que estabas esperando:

Intercalar las cadenas en el orden del programa, como sugiere @BeeOnRope en los comentarios, no requiere una ejecución fuera de orden para explotar el ILP, por lo que es bastante trivial:

.loop: lfence ; at the top of the loop is the lowest-overhead place. %rep T imul eax,eax imul edx,edx %endrep dec ecx jnz .loop

Podría poner pares de cadenas de times 8 imul cortos dentro de un %rep para permitir que el ejecutivo de OoO tenga un tiempo fácil.

Nota al pie de página 1: cómo interactúan el front-end / RS / ROB

Mi modelo mental es que las etapas de emisión / cambio de nombre / asignación en el front-end agregan nuevos ops a la RS y al ROB al mismo tiempo.

Uops abandona la RS después de ejecutar, pero permanece en el ROB hasta que se retire en orden. El ROB puede ser grande porque nunca se escanea fuera de orden para encontrar el primer uop listo, solo se escanea para verificar si el uop más antiguo ha terminado de ejecutarse y, por lo tanto, está listo para retirarse.

(Supongo que el ROB es físicamente un búfer circular con índices de inicio / fin, no una cola que en realidad copia uops a la derecha en cada ciclo. Pero solo piense en ello como una cola / lista con un tamaño máximo fijo, donde el front-end agrega uops en el frente, y la lógica de retiro se retira / compromete desde el final, siempre y cuando se ejecute por completo, hasta cierto límite de retiro por hebra por ciclo que no suele ser un cuello de botella. Skylake lo aumentó para mejor Hyperthreading, tal vez a 8 por reloj por hilo lógico. Tal vez la jubilación también signifique liberar registros físicos, lo que ayuda a HT, porque el propio ROB está particionado estáticamente cuando ambas hebras están activas. Es por eso que los límites de jubilación son por cadena lógica).

Uops como nop , xor eax,eax o lfence , que se manejan en el front-end (no necesitan unidades de ejecución en ningún puerto) se agregan solo al ROB, en un estado ya ejecutado. (Una entrada de ROB presumiblemente tiene un bit que lo marca como listo para retirarse en lugar de esperar a que se complete la ejecución. Este es el estado del que estoy hablando. Para los uops que necesitaban un puerto de ejecución, asumo que el bit de ROB está establecido a través de un puerto de finalización desde la unidad de ejecución. Y que la misma señal de puerto de finalización libera su entrada RS).

Uops se queda en el ROB desde la emisión hasta la jubilación .

Los Uops se quedan en la RS desde su emisión hasta su ejecución . La RS puede reproducir uops en algunos casos , por ejemplo, para la otra mitad de una carga de división de línea de caché , o si se envió en previsión de la llegada de datos de carga, pero en realidad no fue así. (La falta de caché u otros conflictos, como los efectos de rendimiento extraños de las tiendas dependientes cercanas en un bucle de búsqueda de punteros en IvyBridge. ¿Agregar una carga adicional lo acelera? ). para acortar la latencia de persecución del puntero con desplazamientos pequeños: ¿hay una penalización cuando la base + desplazamiento está en una página diferente a la base?

Por lo tanto, sabemos que la RS no puede eliminar un derecho uop a medida que se envía, ya que es posible que deba reproducirse. (Puede suceder incluso a uops sin carga que consumen datos de carga). Pero cualquier especulación que necesite repeticiones es de corto alcance, no a través de una cadena de uops, por lo que una vez que un resultado sale del otro extremo de una unidad de ejecución, el uop puede ser eliminado de la RS. Probablemente esto es parte de lo que hace un puerto de finalización, junto con poner el resultado en la red de reenvío de derivación.

Nota a pie de página 2: ¿Cuántas entradas de RS toma un uop microfusado?

TL: DR: P6-familia: RS está fusionada, SnB-familia: RS no está fusionada.

Se emite un uop microfundido a dos entradas RS separadas en la familia de Sandybridge , pero solo 1 entrada ROB. (Suponiendo que no esté sin laminar antes de su emisión, consulte la sección 2.3.5 para HSW o la sección 2.4.2.4 para SnB del manual de optimización de Intel, y los modos de fusión y direccionamiento . El formato más compacto uop de la familia Sandybridge no puede representar indexado Modos de direccionamiento en el ROB en todos los casos.)

La carga se puede despachar de forma independiente, antes del otro operando para que la ALU esté lista. (O bien, para las tiendas microfusionadas, la dirección de la tienda o los datos de la tienda pueden despacharse cuando su entrada esté lista, sin esperar a ambas).

Utilicé el método de dos cadenas de la pregunta para probar experimentalmente esto en Skylake (tamaño RS = 97) , con micro-fusionado or edi, [rdi] vs. mov + or , y otra cadena de rsi en rsi . ( Código de prueba completo, sintaxis NASM en Godbolt )

; loop body %rep T %if FUSE or edi, [rdi] ; static buffers are in the low 32 bits of address space, in non-PIE %else mov eax, [rdi] or edi, eax %endif %endrep %rep T %if FUSE or esi, [rsi] %else mov eax, [rsi] or esi, eax %endif %endrep

Si uops_executed.thread (dominio no fusionado) por ciclo (o por segundo que el perf calcula para nosotros), podemos ver un número de rendimiento que no depende de cargas separadas o plegadas.

Con una T pequeña (T = 30), se puede explotar todo el ILP, y obtenemos ~ 0,67 uops por reloj con o sin microfusión. (Estoy ignorando el pequeño sesgo de 1 uop adicional por iteración de bucle de dec / jnz. Es insignificante en comparación con el efecto que veríamos si los uops microfusidos solo usaron 1 entrada RS)

Recuerde que load + or es 2 uops, y tenemos 2 cadenas de dep en vuelo, por lo que es 4/6, porque or edi, [rdi] tiene una latencia de 6 ciclos. (No 5, lo que es sorprendente, ver más abajo).

En T = 60, todavía tenemos alrededor de 0.66 uops no fusionados ejecutados por reloj para FUSE = 0, y 0.64 para FUSE = 1. Todavía podemos encontrar básicamente todo el ILP, pero apenas está comenzando a sumergirse, ya que las dos cadenas de depuración tienen una longitud de 120 uops (en comparación con un tamaño RS de 97).

En T = 120, tenemos 0.45 uops no fusionados por reloj para FUSE = 0, y 0.44 para FUSE = 1. Definitivamente estamos más allá de la rodilla aquí, pero todavía estamos encontrando algo del ILP.

Si un uop microfusible tomó solo 1 entrada RS, FUSE = 1 T = 120 debería ser aproximadamente la misma velocidad que FUSE = 0 T = 60, pero ese no es el caso . En su lugar, FUSE = 0 o 1 casi no hace ninguna diferencia en cualquier T. (Incluyendo las más grandes como T = 200: FUSE = 0: 0.395 uops / reloj, FUSE = 1: 0.391 uops / reloj). Tendríamos que ir a una T muy grande antes de que empecemos por el tiempo con 1 cadena de caderas en vuelo para dominar totalmente la hora con 2 en vuelo, y bajar a 0.33 uops / reloj (2/6).

Rareza: tenemos una diferencia tan pequeña, pero aún medible, en el rendimiento para Fused frente a no fusionado, con cargas mov separadas más rápidas.

Otras rarezas: el uops_executed.thread total es ligeramente inferior para FUSE = 0 en cualquier T. Dada. Como 2,418,826,591 frente a 2,419,020,155 para T = 60. Esta diferencia fue repetible hasta + - 60k de 2.4G, bastante precisa. FUSE = 1 es más lento en los ciclos totales de reloj, pero la mayor parte de la diferencia proviene de uops más bajos por reloj, no de más uops.

Los modos de direccionamiento simple, como [rdi] se supone, solo tienen una latencia de 4 ciclos, por lo que load + ALU debería ser solo de 5 ciclos. Pero mido la latencia de 6 ciclos para la latencia de uso de carga or rdi, [rdi] , o con una carga de MOV separada, o con cualquier otra instrucción ALU, nunca puedo obtener la parte de carga de 4c.

Un modo de direccionamiento complejo como [rdi + rbx + 2064] tiene la misma latencia cuando hay una instrucción ALU en la cadena de dep, por lo que parece que la latencia de 4c de Intel para modos de direccionamiento simples solo se aplica cuando una carga se reenvía al registro base de otra carga (con hasta a + 0..2047 desplazamiento y sin índice).

La búsqueda de punteros es lo suficientemente común como para que sea una optimización útil, pero debemos pensar en ella como una ruta rápida de carga-carga especial, no como datos generales listos antes para su uso por las instrucciones de ALU.

La familia P6 es diferente: una entrada RS contiene un uop de dominio fusionado.

@Hadi encontró una patente de Intel desde 2002 , donde la Figura 12 muestra la RS en el dominio fusionado.

Las pruebas experimentales en un Conroe (primer gen Core2Duo, E6600) muestran que hay una gran diferencia entre FUSE = 0 y FUSE = 1 para T = 50. ( El tamaño RS es de 32 entradas ).

T = 50 FUSIBLE = 1: tiempo total de 2.346G ciclos (0.44IPC)
T = 50 FUSIBLE = 0: tiempo total de 3.272G ciclos (0.62IPC = 0.31 carga + O por reloj). ( perf / ocperf.py no tiene eventos para uops_executed en uarches antes de Nehalem o algo así, y no tengo oprofile instalado en esa máquina).
T = 24 hay una diferencia insignificante entre FUSE = 0 y FUSE = 1, alrededor de 0.47 IPC vs 0.9 IPC (~ 0.45 carga + O por reloj).

T = 24 todavía tiene más de 96 bytes de código en el bucle, demasiado grande para el búfer de bucle de 64 bytes (predecodificación) del Core 2, por lo que no es más rápido debido a que se ajusta en un búfer de bucle. Sin un caché de uop, debemos preocuparnos por el front-end, pero creo que estamos bien porque estoy usando exclusivamente instrucciones de uop de 2 bytes que deberían decodificarse fácilmente a 4 uops de dominio fusionado por reloj.

Presentaré un análisis para el caso donde T = 1 para ambos códigos (con y sin lfence ). Luego puede extender esto para otros valores de T. Puede consultar la Figura 2.4 del Manual de optimización de Intel para obtener una imagen.

Debido a que solo hay una única rama fácil de predecir, el frontend solo se detendrá si el backend se detiene. La interfaz es de 4 anchos en Haswell, lo que significa que se pueden emitir hasta 4 uops fusionados desde la IDQ (cola de decodificación de instrucciones, que es solo una cola que contiene uops de dominio fusionado en orden, también llamada cola uop) a la Estación de reserva (RS) del planificador. Cada imul se decodifica en un solo uop que no se puede fusionar. Las instrucciones dec ecx y jnz .loop se macrofunden en el frontend a un solo uop. Una de las diferencias entre la microfusión y la macrofusión es que cuando el programador envía un uop macrofundido (que no está microfundido) a la unidad de ejecución a la que está asignado, se envía como un solo uop. En contraste, un uop microfundido debe dividirse en sus uops constituyentes, cada uno de los cuales debe enviarse por separado a una unidad de ejecución. (Sin embargo, la división de uops microfundidos ocurre en la entrada de la RS, no en el envío; consulte la nota al pie de página 2 en la respuesta de @Peter). lfence se decodifica en 6 uops. Reconocer la microfusión solo importa en el backend, y en este caso, no hay microfusión en el bucle.

Dado que la rama del bucle es fácilmente predecible y que el número de iteraciones es relativamente grande, podemos suponer sin comprometer la precisión que el asignador siempre podrá asignar 4 uops por ciclo. En otras palabras, el programador recibirá 4 uops por ciclo. Dado que no hay micorfusión, cada uop se enviará como un solo uop.

imul solo puede ser ejecutado por la unidad de ejecución Slow Int (ver Figura 2.4). Esto significa que la única opción para ejecutar el imul uops es enviarlos al puerto 1. En Haswell, el Slow Int está bien canalizado para que se pueda enviar un solo imul por ciclo. Pero se requieren tres ciclos para que el resultado de la multiplicación esté disponible para cualquier instrucción que requiera (la etapa de reescritura es el tercer ciclo desde la etapa de despacho de la tubería). Por lo tanto, para cada cadena de dependencia, como máximo se puede enviar un imul por 3 ciclos.

Debido a que se predice que dec/jnz se toma, la única unidad de ejecución que puede ejecutarlo es la rama primaria en el puerto 6.

Entonces, en cualquier ciclo dado, siempre que la RS tenga espacio, recibirá 4 puntos. Pero, ¿qué tipo de uops? Vamos a examinar el bucle sin lfence:

imul eax, eax imul edx, edx dec ecx/jnz .loop (macrofused)

Hay dos posibilidades:

Dos imul s de la misma iteración, uno imul de una iteración vecina y una dec/jnz de una de esas dos iteraciones.
Una dec/jnz de una iteración, dos imul de la siguiente iteración y una dec/jnz de la misma iteración.

Así que al comienzo de cualquier ciclo, la RS recibirá al menos una dec/jnz y al menos un imul de cada cadena. Al mismo tiempo, en el mismo ciclo y desde los uops que ya existen en la RS, el programador realizará una de dos acciones:

Envíe el dec/jnz más dec/jnz al puerto 6 y dec/jnz el imul más antiguo que esté listo para el puerto 1. Eso es un total de 2 uops.
Debido a que el Slow Int tiene una latencia de 3 ciclos, pero solo hay dos cadenas, por cada ciclo de 3 ciclos, ningún imul en el RS estará listo para la ejecución. Sin embargo, siempre hay al menos una dec/jnz en la RS. Así que el programador puede despachar eso. Eso es un total de 1 uop.

Ahora podemos calcular el número esperado de uops en la RS, X _N , al final de cualquier ciclo N:

X _N = X _N-1 + (el número de uops que se asignarán en la RS al comienzo del ciclo N) - (el número esperado de uops que se enviarán al comienzo del ciclo N)
= X _N-1 + 4 - ((0 + 1) * 1/3 + (1 + 1) * 2/3)
= X _N-1 + 12/3 - 5/3
= X _N-1 + 7/3 para todos N> 0

La condición inicial para la recurrencia es X ₀ = 4. Esta es una recurrencia simple que puede resolverse desplegando X _N-1 .

X _N = 4 + 2.3 * N para todos N> = 0

El RS en Haswell tiene 60 entradas. Podemos determinar el primer ciclo en el que se espera que la RS se llene:

60 = 4 + 7/3 * N
N = 56 / 2.3 = 24.3

Así que al final del ciclo 24.3, se espera que la RS esté llena. Esto significa que al comienzo del ciclo 25.3, el RS no podrá recibir ningún nuevo uops. Ahora el número de iteraciones, I, bajo consideración determina cómo debe proceder con el análisis. Dado que una cadena de dependencia requerirá al menos 3 * I ciclos para ejecutarse, se necesitan aproximadamente 8.1 iteraciones para alcanzar el ciclo 24.3. Entonces, si el número de iteraciones es mayor que 8.1, que es el caso aquí, necesita analizar lo que sucede después del ciclo 24.3.

El programador envía instrucciones a las siguientes tasas en cada ciclo (como se explicó anteriormente):

1 2 2 1 2 2 1 2 . .

Pero el asignador no asignará ningún uops en la RS a menos que haya al menos 4 entradas disponibles. De lo contrario, no desperdiciará energía en emitir uops a un rendimiento subóptimo. Sin embargo, solo al comienzo de cada 4º ciclo hay al menos 4 entradas gratuitas en el RS. Así que a partir del ciclo 24.3, se espera que el asignador se detenga 3 de cada 4 ciclos.

Otra observación importante para el código que se está analizando es que nunca sucede que haya más de 4 uops que se puedan enviar, lo que significa que el número promedio de uops que dejan sus unidades de ejecución por ciclo no es mayor que 4. Como máximo, 4 uops puede ser retirado del Reordenar Buffer (ROB). Esto significa que el ROB nunca puede estar en el camino crítico. En otras palabras, el rendimiento está determinado por el rendimiento del envío.

Podemos calcular el IPC (instrucciones por ciclos) con bastante facilidad ahora. Las entradas de ROB se ven algo así:

imul eax, eax - N imul edx, edx - N + 1 dec ecx/jnz .loop - M imul eax, eax - N + 3 imul edx, edx - N + 4 dec ecx/jnz .loop - M + 1

La columna de la derecha muestra los ciclos en los que se puede retirar la instrucción. La jubilación ocurre en orden y está limitada por la latencia de la ruta crítica. Aquí, cada cadena de dependencia tiene la misma longitud de ruta y, por lo tanto, ambas constituyen dos rutas críticas iguales de 3 ciclos de longitud. Así que cada 3 ciclos, se pueden retirar 4 instrucciones. Entonces, el IPC es 4/3 = 1.3 y el IPC es 3/4 = 0.75. Esto es mucho más pequeño que el IPC óptimo teórico de 4 (incluso sin considerar la microfusión y la macro fusión). Debido a que la jubilación ocurre en orden, el comportamiento de la jubilación será el mismo.

Podemos verificar nuestro análisis usando tanto perf como IACA. Voy a discutir perf . Tengo una CPU Haswell.

perf stat -r 10 -e cycles:u,instructions:u,cpu/event=0xA2,umask=0x10,name=RESOURCE_STALLS.ROB/u,cpu/event=0x0E,umask=0x1,cmask=1,inv=1,name=UOPS_ISSUED.ANY/u,cpu/event=0xA2,umask=0x4,name=RESOURCE_STALLS.RS/u ./main-1-nolfence Performance counter stats for ''./main-1-nolfence'' (10 runs): 30,01,556 cycles:u ( +- 0.00% ) 40,00,005 instructions:u # 1.33 insns per cycle ( +- 0.00% ) 0 RESOURCE_STALLS.ROB 23,42,246 UOPS_ISSUED.ANY ( +- 0.26% ) 22,49,892 RESOURCE_STALLS.RS ( +- 0.00% ) 0.001061681 seconds time elapsed ( +- 0.48% )

Hay 1 millón de iteraciones, cada una toma alrededor de 3 ciclos. Cada iteración contiene 4 instrucciones y el IPC es 1.33. RESOURCE_STALLS.ROB muestra el número de ciclos en los que el asignador se detuvo debido a un ROB completo. Esto, por supuesto, nunca sucede. UOPS_ISSUED.ANY se puede usar para contar el número de uops emitidos a la RS y el número de ciclos en los que se estancó el asignador (sin una razón específica). El primero es sencillo (no se muestra en la salida de perf ); 1 millón * 3 = 3 millones + ruido pequeño. Este último es mucho más interesante. Muestra que aproximadamente el 73% de todos los tiempos el asignador se ha estancado debido a una RS completa, que coincide con nuestro análisis. RESOURCE_STALLS.RS cuenta el número de ciclos en los que el asignador se detuvo debido a una RS completa. Esto está cerca de UOPS_ISSUED.ANY porque el asignador no se detiene por ninguna otra razón (aunque la diferencia podría ser proporcional al número de iteraciones por alguna razón, tendré que ver los resultados para T> 1).

El análisis del código sin el lfence puede extenderse para determinar qué sucede si se agrega un lfence entre los dos imul . Veamos primero los resultados de perf (IACA desafortunadamente no admite lfence ):

perf stat -r 10 -e cycles:u,instructions:u,cpu/event=0xA2,umask=0x10,name=RESOURCE_STALLS.ROB/u,cpu/event=0x0E,umask=0x1,cmask=1,inv=1,name=UOPS_ISSUED.ANY/u,cpu/event=0xA2,umask=0x4,name=RESOURCE_STALLS.RS/u ./main-1-lfence Performance counter stats for ''./main-1-lfence'' (10 runs): 1,32,55,451 cycles:u ( +- 0.01% ) 50,00,007 instructions:u # 0.38 insns per cycle ( +- 0.00% ) 0 RESOURCE_STALLS.ROB 1,03,84,640 UOPS_ISSUED.ANY ( +- 0.04% ) 0 RESOURCE_STALLS.RS 0.004163500 seconds time elapsed ( +- 0.41% )

Observe que el número de ciclos ha aumentado en aproximadamente 10 millones, o 10 ciclos por iteración. El número de ciclos no nos dice mucho. El número de instrucciones retiradas ha aumentado en un millón, lo que se espera. Ya sabemos que el lfence no hará que la instrucción se complete más rápido, por lo que RESOURCE_STALLS.ROB no debe cambiar. UOPS_ISSUED.ANY y RESOURCE_STALLS.RS son particularmente interesantes. En esta salida, UOPS_ISSUED.ANY cuenta ciclos, no uops. El número de uops también se puede contar (utilizando cpu/event=0x0E,umask=0x1,name=UOPS_ISSUED.ANY/u lugar de cpu/event=0x0E,umask=0x1,cmask=1,inv=1,name=UOPS_ISSUED.ANY/u ) y ha aumentado en 6 uops por iteración (sin fusión). Esto significa que una lfence que se colocó entre dos imul se decodificó en 6 puntos. La pregunta de un millón de dólares es ahora qué hacen estos uops y cómo se mueven en la tubería.

RESOURCE_STALLS.RS es cero. Qué significa eso? Esto indica que el asignador, cuando ve un lfence en el IDQ, deja de asignar hasta que todos los uops actuales en el ROB se retiren. En otras palabras, el asignador no asignará entradas en el RS más allá de una lfence hasta que la lfence retire. Como el cuerpo del bucle solo contiene otros 3 uops, el RS de 60 entradas nunca estará lleno. De hecho, siempre estará casi vacío.

El IDQ en realidad no es una sola cola simple. Consiste en múltiples estructuras de hardware que pueden operar en paralelo. El número de uops que requiere una lfence depende del diseño exacto del IDQ. El asignador, que también consta de muchas estructuras de hardware diferentes, cuando ve que hay un lfence ufence en la parte frontal de cualquiera de las estructuras del IDQ, suspende la asignación de esa estructura hasta que el ROB esté vacío. Así que diferentes uops son usd con diferentes estructuras de hardware.

UOPS_ISSUED.ANY muestra que el asignador no emite uops durante aproximadamente 9-10 ciclos por iteración. ¿Que está sucediendo aquí? Bueno, uno de los usos de lfence es que puede decirnos cuánto tiempo se tarda en retirar una instrucción y asignar la siguiente instrucción. El siguiente código de ensamblaje se puede usar para hacer eso:

TIMES T lfence

Los contadores de eventos de rendimiento no funcionarán bien para valores pequeños de T Para una T suficientemente grande, y al medir UOPS_ISSUED.ANY , podemos determinar que se necesitan aproximadamente 4 ciclos para retirar cada lfence . Esto se debe a que UOPS_ISSUED.ANY se incrementará aproximadamente 4 veces cada 5 ciclos. Entonces, después de cada 4 ciclos, el asignador emite otra lfence (no se lfence ), luego espera otros 4 ciclos, y así sucesivamente. Dicho esto, las instrucciones que producen resultados pueden requerir 1 o más ciclos para retirarse, según la instrucción. IACA siempre asume que se necesitan 5 ciclos para retirar una instrucción.

Nuestro bucle se ve así:

imul eax, eax lfence imul edx, edx dec ecx jnz .loop

En cualquier ciclo en el límite de lfence , el ROB contendrá las siguientes instrucciones comenzando desde la parte superior del ROB (la instrucción más antigua):

imul edx, edx - N dec ecx/jnz .loop - N imul eax, eax - N+1

Donde N denota el número de ciclo al que se envió la instrucción correspondiente. La última instrucción que se va a completar (llegar a la etapa de reescritura) es imul eax, eax . y esto sucede en el ciclo N + 4. El recuento del ciclo de bloqueo del asignador se incrementará durante los ciclos, N + 1, N + 2, N + 3 y N + 4. Sin embargo, pasarán unos 5 ciclos más hasta que se retire imul eax, eax . Además, después de que se retire, el asignador debe limpiar los lfence ufence del IDQ y asignar el siguiente grupo de instrucciones antes de que puedan enviarse en el próximo ciclo. La salida de rendimiento nos dice que toma alrededor de 13 ciclos por iteración y que el asignador se detiene (debido a la lfence ) durante 10 de estos 13 ciclos.

La gráfica de la pregunta muestra solo el número de ciclos hasta T = 100. Sin embargo, hay otra rodilla (final) en este punto. Por lo tanto, sería mejor trazar los ciclos de hasta T = 120 para ver el patrón completo.