parallel processing - ¿Cuál es el propósito de la instrucción "PAUSA" en x86?

parallel-processing x86-64

Question

Estoy tratando de crear una versión tonta de un bloqueo de giro. Al buscar en la web, encontré una instrucción de ensamblaje llamada "PAUSA" en x86 que se usa para dar pistas a un procesador de que actualmente se está ejecutando un spin-lock en esta CPU. El manual de inteligencia y otra información disponible indican que

El procesador utiliza esta sugerencia para evitar la violación del orden de memoria en la mayoría de las situaciones, lo que mejora considerablemente el rendimiento del procesador. Por este motivo, se recomienda que se coloque una instrucción de PAUSA en todos los bucles de espera de espín. La documentación también menciona que "esperar (alguna demora)" es la pseudo implementación de la instrucción.

La última línea del párrafo anterior es intuitiva. Si no logro agarrar la cerradura, debo esperar un tiempo antes de volver a agarrar la cerradura.

Sin embargo, ¿qué entendemos por violación de orden de memoria en caso de un bloqueo de giro? ¿"Violación de orden de memoria" significa la carga / almacenamiento especulativo incorrecto de las instrucciones después del bloqueo de giro?

La pregunta de bloqueo de giro se ha preguntado anteriormente sobre el desbordamiento de Pila, pero la pregunta de violación de orden de memoria permanece sin respuesta (al menos para mi comprensión).

Answer 1

Como dice @Mackie, la tubería se llenará con cmp s. Intel tendrá que vaciar esos cmp s cuando otro núcleo escriba, lo que es una operación costosa. Si la CPU no lo vacía, entonces tiene una violación de orden de memoria. Un ejemplo de tal violación sería el siguiente:

(Esto comienza con lock1 = lock2 = lock3 = var = 1)

Hilo 1:

spin:
cmp lock1, 0
jne spin
cmp lock3, 0 # lock3 should be zero, Thread 2 already ran.
je end # Thus I take this path
mov var, 0 # And this is never run
end:

Hilo 2:

mov lock3, 0
mov lock1, 0
mov ebx, var # I should know that var is 1 here.

Primero, considera el hilo 1:

si cmp lock1, 0; jne spin cmp lock1, 0; jne spin branch predice que lock1 no es cero, agrega cmp lock3, 0 a la tubería.

En la tubería, cmp lock3, 0 lee lock3 y descubre que es igual a 1.

Ahora, supongamos que Thread 1 está tomando su tiempo dulce, y Thread 2 comienza a ejecutarse rápidamente:

lock3 = 0
lock1 = 0

Ahora, volvamos al tema 1:

Digamos que cmp lock1, 0 finalmente lee lock1, descubre que lock1 es 0 y está contento con su capacidad de predicción de ramas.

Este comando se compromete, y nada se vacía. La correcta predicción de ramificación significa que no se vacía nada, incluso con lecturas fuera de orden, ya que el procesador dedujo que no hay dependencia interna. Lock3 no depende de Lock1 en los ojos de la CPU, así que todo está bien.

Ahora, el cmp lock3, 0 , que leyó correctamente que lock3 era igual a 1, confirma.

je end no se toma, y mov var, 0 ejecuta.

En el subproceso 3, ebx es igual a 0. Esto debería haber sido imposible. Esta es la violación de orden de memoria que Intel debe compensar.

Ahora, la solución que Intel toma para evitar ese comportamiento no válido, es vaciar. Cuando lock3 = 0 ejecutó en Thread 2, obliga a Thread 1 a eliminar las instrucciones que usan lock3. La descarga en este caso significa que el subproceso 1 no agregará instrucciones a la tubería hasta que todas las instrucciones que usan lock3 hayan sido confirmadas. Antes de que pueda comprometerse el cmp lock1 del Thread 1, el cmp lock1 debe comprometerse. Cuando el cmp lock1 intenta confirmar, lee que lock1 es en realidad igual a 1, y que la predicción de bifurcación fue un fracaso. Esto hace que el cmp sea ​​expulsado. Ahora que se ha lock3 subproceso 1, la ubicación de lock3 en el caché del subproceso 1 se establece en 0 , y luego el subproceso 1 continúa su ejecución (Esperando en el lock1 ). El subproceso 2 ahora recibe una notificación de que todos los demás núcleos han eliminado el uso de lock3 y han actualizado sus cachés, por lo que el subproceso 2 continúa su ejecución (se habrá ejecutado sentencias independientes mientras tanto, pero la siguiente instrucción fue otra escritura, así que probablemente tenga que colgarse, a menos que los otros núcleos tengan una cola para retener el lock1 = 0 pendiente1 lock1 = 0 escritura).

Todo este proceso es caro, de ahí la PAUSA. La PAUSA ayuda al subproceso 1, que ahora puede recuperarse de la rama inminente y predecir de forma instantánea, y no tiene que vaciar su tubería antes de bifurcarse correctamente. La PAUSA también ayuda con el subproceso 2, que no tiene que esperar en el lavado del subproceso 1 (como se dijo antes, no estoy seguro de este detalle de implementación, pero si el subproceso 2 intenta escribir bloqueos utilizados por muchos otros núcleos, el subproceso 2 eventualmente hay que esperar a los sofocos).

Un entendimiento importante es que mientras que en mi ejemplo, la descarga es necesaria, en el ejemplo de Mackie, no lo es. Sin embargo, la CPU no tiene forma de saberlo (no analiza el código en absoluto, aparte de verificar las dependencias de las sentencias consecutivas y un caché de predicción de bifurcación), por lo que la CPU lockvar instrucciones para acceder a lockvar en el ejemplo de Mackie tal como lo hace en la mía , con el fin de garantizar la corrección.

Answer 2

Imagínese, cómo el procesador ejecutaría un bucle típico de espín de espera:

1 Spin_Lock:
2    CMP lockvar, 0   ; Check if lock is free
3    JE Get_Lock
4    JMP Spin_Lock
5 Get_Lock:

Después de algunas iteraciones, el predictor de rama predecirá que la rama condicional (3) nunca se tomará y la canalización se llenará con las instrucciones de CMP (2). Esto continúa hasta que finalmente otro procesador escribe un cero para lockvar. En este punto, tenemos la tubería llena de instrucciones CMP especulativas (es decir, aún no comprometidas), algunas de las cuales ya leen lockvar e informaron un resultado distinto de (incorrecto) en la siguiente rama condicional (3) (también especulativa). Esto es cuando ocurre la violación del orden de memoria. Cada vez que el procesador "ve" una escritura externa (una escritura de otro procesador), busca en su canalización instrucciones que accedieron especulativamente a la misma ubicación de memoria y que aún no se hayan confirmado. Si se encuentra alguna de estas instrucciones, el estado especulativo del procesador no es válido y se borra con un flujo de tubería.

Desafortunadamente, este escenario (muy probablemente) se repetirá cada vez que un procesador esté esperando en un bloqueo de giro y hará que estos bloqueos sean más lentos de lo que deberían ser.

Ingrese la instrucción PAUSA:

1 Spin_Lock:
2    CMP lockvar, 0   ; Check if lock is free
3    JE Get_Lock
4    PAUSE            ; Wait for memory pipeline to become empty
5    JMP Spin_Lock
6 Get_Lock:

La instrucción de PAUSA "eliminará la tubería" que lee la memoria, de modo que la tubería no se llena con instrucciones CMP (2) especulativas como en el primer ejemplo. (Es decir, podría bloquear la tubería hasta que todas las instrucciones de memoria anteriores se hayan confirmado). Debido a que las instrucciones CMP (2) se ejecutan secuencialmente, es poco probable (es decir, que la ventana de tiempo sea mucho más corta) que se produzca una escritura externa después de que se lea la instrucción CMP (2) Lockvar pero antes de que se confirme el CMP.

Por supuesto, la "eliminación de tuberías" también desperdiciará menos energía en el bloqueo de giro y, en caso de un subproceso, no desperdiciará recursos que el otro subproceso podría utilizar mejor. Por otro lado, todavía hay una predicción errónea de ramificación en espera de ocurrir antes de cada salida de bucle. La documentación de Intel no sugiere que PAUSA elimine el flujo de la tubería, pero quién sabe ...