performance - numero - lenguaje ensamblador pdf

¿Por qué la introducción de instrucciones MOV inútiles acelera un circuito cerrado en el ensamblaje x86_64?

Question

Fondo:

Mientras optimizaba algunos códigos Pascal con lenguaje ensamblador incorporado, noté una instrucción MOV innecesaria y la eliminé.

Para mi sorpresa, eliminar las instrucciones innecesarias hizo que mi programa se ralentizara .

Descubrí que agregar instrucciones MOV arbitrarias e inútiles aumentaba aún más el rendimiento .

El efecto es errático, y los cambios según el orden de ejecución: las mismas instrucciones no deseadas que se transponen hacia arriba o hacia abajo en una sola línea producen una desaceleración .

Entiendo que la CPU realiza todo tipo de optimizaciones y simplificaciones, pero esto parece más bien magia negra.

Los datos:

Una versión de mi código compila condicionalmente tres operaciones basura en medio de un bucle que se ejecuta 2**20==1048576 veces. (El programa circundante simplemente calcula SHA-256 hashes SHA-256 ).

Los resultados en mi máquina bastante antigua (Intel (R) Core (TM) 2 CPU 6400 @ 2.13 GHz):

avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without:        1836.44 ms

Los programas se ejecutaron 25 veces en un bucle, con el orden de ejecución cambiando aleatoriamente cada vez.

Extracto:

{$asmmode intel}
procedure example_junkop_in_sha256;
  var s1, t2 : uint32;
  begin
    // Here are parts of the SHA-256 algorithm, in Pascal:
    // s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
    // s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
    // Here is how I translated them (side by side to show symmetry):
  asm
    MOV r8d, a                 ; MOV r9d, e
    ROR r8d, 2                 ; ROR r9d, 6
    MOV r10d, r8d              ; MOV r11d, r9d
    ROR r8d, 11    {13 total}  ; ROR r9d, 5     {11 total}
    XOR r10d, r8d              ; XOR r11d, r9d
    ROR r8d, 9     {22 total}  ; ROR r9d, 14    {25 total}
    XOR r10d, r8d              ; XOR r11d, r9d

    // Here is the extraneous operation that I removed, causing a speedup
    // s1 is the uint32 variable declared at the start of the Pascal code.
    //
    // I had cleaned up the code, so I no longer needed this variable, and 
    // could just leave the value sitting in the r11d register until I needed
    // it again later.
    //
    // Since copying to RAM seemed like a waste, I removed the instruction, 
    // only to discover that the code ran slower without it.
    {$IFDEF JUNKOPS}
    MOV s1,  r11d
    {$ENDIF}

    // The next part of the code just moves on to another part of SHA-256,
    // maj { r12d } := (a and b) xor (a and c) xor (b and c)
    mov r8d,  a
    mov r9d,  b
    mov r13d, r9d // Set aside a copy of b
    and r9d,  r8d

    mov r12d, c
    and r8d, r12d  { a and c }
    xor r9d, r8d

    and r12d, r13d { c and b }
    xor r12d, r9d

    // Copying the calculated value to the same s1 variable is another speedup.
    // As far as I can tell, it doesn''t actually matter what register is copied,
    // but moving this line up or down makes a huge difference.
    {$IFDEF JUNKOPS}
    MOV s1,  r9d // after mov r12d, c
    {$ENDIF}

    // And here is where the two calculated values above are actually used:
    // T2 {r12d} := S0 {r10d} + Maj {r12d};
    ADD r12d, r10d
    MOV T2, r12d

  end
end;

Inténtalo tú mismo:

El código está en línea en GitHub si quieres probarlo tú mismo.

Mis preguntas:

• ¿Por qué copiar inútilmente el contenido de un registro en la RAM aumentaría el rendimiento?
• ¿Por qué la misma instrucción inútil proporcionaría una aceleración en algunas líneas y una desaceleración en otras?
• ¿Es este comportamiento algo que podría ser explotado de manera predecible por un compilador?

Answer 1

Preparando el caché

Mover operaciones a la memoria puede preparar el caché y hacer que las operaciones de movimiento subsiguientes sean más rápidas. Una CPU normalmente tiene dos unidades de carga y una unidad de almacenamiento. Una unidad de carga puede leer de la memoria a un registro (una lectura por ciclo), una unidad de almacenamiento almacena desde el registro a la memoria. También hay otras unidades que hacen operaciones entre registros. Todas las unidades funcionan en paralelo. Por lo tanto, en cada ciclo, podemos realizar varias operaciones a la vez, pero no más de dos cargas, una tienda y varias operaciones de registro. Por lo general, son hasta 4 operaciones simples con registros simples, hasta 3 operaciones simples con registros XMM / YMM y 1-2 operaciones complejas con cualquier tipo de registros. Su código tiene muchas operaciones con registros, por lo que una operación de almacenamiento de memoria ficticia es gratuita (ya que hay más de 4 operaciones de registro de todos modos), pero prepara la memoria caché para la siguiente operación de almacenamiento. Para saber cómo funcionan los almacenes de memoria, consulte el Manual de referencia de optimización de arquitecturas Intel 64 e IA-32 .

Romper las dependencias falsas.

Aunque esto no se refiere exactamente a su caso, pero a veces se utilizan operaciones mov de 32 bits bajo el procesador de 64 bits (como en su caso) para borrar los bits más altos (32-63) y romper las cadenas de dependencia.

Es bien sabido que bajo x86-64, el uso de operandos de 32 bits borra los bits más altos del registro de 64 bits. Por favor lea la sección relevante - 3.4.1.1 - del Manual del desarrollador de software de las arquitecturas Intel® 64 e IA-32 Volumen 1 :

Los operandos de 32 bits generan un resultado de 32 bits, con extensión cero a un resultado de 64 bits en el registro de propósito general de destino

Por lo tanto, las instrucciones de movimiento, que pueden parecer inútiles a primera vista, borran los bits más altos de los registros apropiados. ¿Qué nos da? Rompe las cadenas de dependencia y permite que las instrucciones se ejecuten en paralelo, en orden aleatorio, mediante el algoritmo de fuera de orden implementado internamente por las CPU desde Pentium Pro en 1995.

Una cotización del Manual de referencia de optimización de arquitecturas Intel® 64 e IA-32 , Sección 3.5.1.8:

Las secuencias de código que modifican el registro parcial pueden experimentar cierta demora en su cadena de dependencia, pero se pueden evitar mediante el uso de expresiones idiomáticas que rompan la dependencia. En los procesadores basados ​​en la microarquitectura Intel Core, varias instrucciones pueden ayudar a eliminar la dependencia de ejecución cuando el software usa estas instrucciones para borrar el contenido del registro a cero. Rompa las dependencias en porciones de registros entre instrucciones operando en registros de 32 bits en lugar de registros parciales. Para movimientos, esto se puede lograr con movimientos de 32 bits o usando MOVZX.

Regla de codificación de ensamblaje / compilador 37. (Impacto M, generalidad MH) : Rompe las dependencias en porciones de registros entre instrucciones al operar en registros de 32 bits en lugar de registros parciales. Para movimientos, esto se puede lograr con movimientos de 32 bits o usando MOVZX.

El MOVZX y el MOV con operandos de 32 bits para x64 son equivalentes, todos rompen cadenas de dependencia.

Es por eso que su código se ejecuta más rápido. Si no hay dependencias, la CPU puede renombrar internamente los registros, aunque a primera vista puede parecer que la segunda instrucción modifica un registro utilizado por la primera instrucción, y las dos no pueden ejecutarse en paralelo. Pero debido al registro de cambio de nombre que pueden.

El cambio de nombre de registro es una técnica utilizada internamente por una CPU que elimina las dependencias de datos falsos que surgen de la reutilización de registros mediante instrucciones sucesivas que no tienen ninguna dependencia de datos real entre ellos.

Creo que ahora ves que es demasiado obvio.

Answer 2

Creo que en las CPU modernas las instrucciones de ensamblaje, si bien son la última capa visible para un programador que proporciona instrucciones de ejecución a una CPU, en realidad son varias capas de la ejecución real de la CPU.

Las CPU modernas son híbridos RISC / CISC que traducen las instrucciones CISC x86 en instrucciones internas que tienen un comportamiento más RISC. Además, existen analizadores de ejecución fuera de orden, predictores de ramificación, la "fusión de microoperaciones" de Intel que intentan agrupar las instrucciones en lotes más grandes de trabajo simultáneo (como el VLIW / Itanium titanic). Incluso hay límites de caché que podrían hacer que el código se ejecute más rápido para que Dios sepa por qué, si es más grande (tal vez el controlador del caché lo haga de manera más inteligente o lo mantenga más tiempo).

CISC siempre ha tenido una capa de traducción de ensamblado a microcódigo, pero el punto es que con las CPU modernas las cosas son mucho más complicadas. Con todas las propiedades de transistores adicionales en las plantas modernas de fabricación de semiconductores, las CPU probablemente pueden aplicar varios enfoques de optimización en paralelo y luego seleccionar el que ofrece la mejor velocidad. Las instrucciones adicionales pueden estar obligando a la CPU a utilizar una ruta de optimización que sea mejor que otras.

El efecto de las instrucciones adicionales probablemente depende del modelo / generación / fabricante de la CPU y no es probable que sea predecible. La optimización del lenguaje de ensamblaje de esta manera requeriría la ejecución contra muchas generaciones de arquitectura de CPU, tal vez utilizando rutas de ejecución específicas de la CPU, y solo sería deseable para las secciones de código realmente importantes, aunque si está haciendo ensamblaje, probablemente ya lo sepa.

Answer 3

Es posible que desee leer http://research.google.com/pubs/pub37077.html

TL; DR: la inserción aleatoria de instrucciones nop en programas puede aumentar fácilmente el rendimiento en un 5% o más, y no, los compiladores no pueden explotar esto fácilmente. Por lo general, es una combinación de predictor de rama y comportamiento de caché, pero también puede ser, por ejemplo, un puesto de estación de reserva (incluso en caso de que no haya cadenas de dependencias rotas o sobre-suscripciones obvias de recursos de cualquier tipo).

Answer 4

La causa más probable de la mejora de la velocidad es que:

• la inserción de un MOV desplaza las instrucciones subsiguientes a diferentes direcciones de memoria
• Una de esas instrucciones movidas fue una importante rama condicional.
• esa rama estaba siendo predicha incorrectamente debido al alias en la tabla de predicción de ramas
• mover la rama eliminó el alias y permitió predecir la rama correctamente

Su Core2 no mantiene un registro histórico separado para cada salto condicional. En su lugar, mantiene un historial compartido de todos los saltos condicionales. Una desventaja de la predicción de rama global es que la historia se diluye con información irrelevante si los diferentes saltos condicionales no están correlacionados.

Este pequeño tutorial de predicción de ramas muestra cómo funcionan los búferes de predicción de ramas. El búfer de caché está indexado por la parte inferior de la dirección de la instrucción de bifurcación. Esto funciona bien a menos que dos ramas importantes no correlacionadas compartan los mismos bits inferiores. En ese caso, terminas con un alias que causa muchas ramificaciones mal pronosticadas (lo que detiene el flujo de instrucciones y ralentiza el programa).

Si desea comprender cómo las predicciones erróneas de las sucursales afectan el rendimiento, observe esta excelente respuesta: https://.com/a/11227902/1001643

Los compiladores generalmente no tienen suficiente información para saber qué ramas serán alias y si esos alias serán significativos. Sin embargo, esa información se puede determinar en tiempo de ejecución con herramientas como Cachegrind y VTune .