costo de operación atómica

Question

¿Cuál es el costo de la operación atómica (cualquiera de comparar y cambiar o agregar/decrecer atómicos)? ¿Cuánto ciclos consume? ¿Pausará otros procesadores en SMP o NUMA, o bloqueará los accesos a la memoria? ¿Enjuagará el búfer en una CPU fuera de servicio?

¿Qué efectos habrá en la memoria caché?

Me interesan las CPU modernas y populares: x86, x86_64, PowerPC, SPARC, Itanium.

Answer 1

He buscado datos reales de los últimos días y no he encontrado nada. Sin embargo, investigué un poco, lo que compara el costo de las operaciones atómicas con los costos de fallas en la memoria caché.

El costo del prefijo LOCK x86, o CAS, antes PentiumPro (como se describe en el doc), es un acceso de memoria (como un fallo de caché), + detener las operaciones de memoria por otros procesadores, + cualquier contención con otros procesadores tratando de BLOQUEAR el autobús. Sin embargo, desde PentiumPro, para memoria de reescritura (es decir, memoria caché), a menos que hable directamente con el hardware, en lugar de bloquear todas las operaciones de memoria, solo se bloquea la correspondiente caché (según el enlace publicado anteriormente).

En realidad, la carcasa CAS puede ser más complicada, como se explica en this page, sin tiempos, pero con una descripción detallada de un ingeniero de confianza.

Antes de entrar en demasiados detalles, diré que una operación LOCKed cuesta una falta de caché + la posible contención con otro procesador en la misma línea de caché, mientras que CAS + la carga anterior (que casi siempre es necesaria excepto en mutexes , donde siempre CAS 0 y 1) puede costar dos fallas de caché.

Explica que una carga + CAS en una sola ubicación en realidad puede costar dos fallas de caché, como Load-Linked/Store-Conditional (ver allí para el último). Su explicación se basa en el conocimiento del MESI cache coherence protocol. Utiliza 4 estados para una línea de caché: M (odificado), E (xclusivo), S (hared), I (nulo) (y, por lo tanto, se llama MESI), se explica a continuación cuando es necesario. El escenario, explicó, es la siguiente:

• la carga provoca un error de caché - la cacheline correspondiente se carga desde la memoria en el estado compartido (es decir, otros procesadores todavía se les permite mantener que cacheline en la memoria; no se permiten cambios en este estado). Si la ubicación está en la memoria, esta falta de caché se omite.Costo posible: 1 error de caché. (omitido si la línea de caché está en estado Compartido, Exclusivo o Modificado, es decir, los datos están en la memoria caché L1 de esta CPU).
• el programa calcula los nuevos valores para almacenar,
• y ejecuta una instrucción CAS atómica.
  • Tiene que evitar la modificación simultánea, por lo que debe eliminar las copias de la línea de caché de la caché de otras CPU, para mover la línea de caché al estado Exclusive. Costo posible: 1 error de caché. Esto no es necesario si ya es de propiedad exclusiva, es decir, en estado Exclusivo o Modificado. En ambos estados, ninguna otra CPU mantiene la línea de caché, pero en el estado Exclusivo no se ha modificado (todavía).
  • Después de esta comunicación, la variable se modifica en la memoria caché local de nuestra CPU, en cuyo punto es visible globalmente para todas las demás CPU (porque sus cachés son coherentes con los nuestros). Eventualmente se escribirá en la memoria principal de acuerdo con los algoritmos habituales.
  • Otros procesadores que intenten leer o modificar esa variable primero tendrán que obtener esa línea de caché en modo Compartido o Exclusivo, y para hacerlo se contactarán con este procesador y recibirán la versión actualizada de la línea de caché. Una operación LOCKed, en cambio, solo puede costar una caché fallida (porque la caché se solicitará directamente en estado Exclusive).

En todos los casos, una solicitud cacheline puede ser detenido por otros procesadores ya la modificación de los datos.

Answer 2

En SMP basado en bus, el prefijo atómico LOCK hace referencia (enciende) una señal de cable de bus LOCK#. Prohibirá otras CPU/dispositivos en el bus para usarlo.

Ppro & P2 libro http://books.google.com/books?id=3gDmyIYvFH4C&pg=PA245&dq=lock+instruction+pentium&lr=&ei=_E61S5ehLI78zQSzrqwI&cd=1#v=onepage&q=lock%20instruction%20pentium&f=false páginas 244-246

instrucciones bloquean son serialización, la sincronización de las operaciones .... /sobre Out-of-order/bloqueado RSR/lectura-modificación-escritura = atomic itself/instruction asegura que el procesador ejecutará todas las instrucciones antes de la instrucción bloqueada antes de ejecutarlo. /about yet not flushed writes/fuerza todas las escrituras publicadas dentro del procesador para que se vacíen a la memoria externa antes de ejecutar la siguiente instrucción.

/sobre SMP/semáforo está en caché en el estado S ... emitir una lectura e invalidar la transacción de 0 bytes de fecha (esto es una muerte/de copias compartidas de la línea de caché de CPU adyacentes /)

Answer 3

Hice algunos perfiles con la siguiente configuración: la máquina de prueba (AMD Athlon64 x2 3800+) se inició, cambió a modo largo (interrupciones deshabilitadas) y la instrucción de interés se ejecutó en un bucle, 100 iteraciones desenrolladas y 1,000 ciclos de bucle El cuerpo del bucle estaba alineado a 16 bytes. El tiempo se midió con una instrucción rdtsc antes y después del ciclo. Además, se ejecutó un bucle ficticio sin ninguna instrucción (que midió 2 ciclos por iteración de bucle y 14 ciclos para el resto) y el resultado se resta del resultado del tiempo de creación de la instrucción. Se midieron

Las siguientes instrucciones:

• "lock cmpxchg [rsp - 8], rdx" (ambos con partido comparación y falta de coincidencia),
• "lock xadd [rsp - 8], rdx",
• "lock bts qword ptr [rsp - 8], 1"

En todos los casos el tiempo medido fue de aproximadamente 310 ciclos, el error fue de aproximadamente +/- 8 ciclos

Este es el valor para la ejecución repetida en la misma memoria (en caché). Con una falta de caché adicional, los tiempos son considerablemente más altos. También esto se hizo con solo uno de los 2 núcleos activos, por lo que el caché era de propiedad exclusiva y no se requería sincronización de caché.

Para evaluar el costo de una instrucción encerrado en un error de caché, que añade una instrucción wbinvld antes de la instrucción bloqueada y poner el wbinvld más un add [rsp - 8], rax en el circuito de comparación. En ambos casos, el costo fue de aproximadamente 80,000 ciclos por par de instrucciones. En caso de bloqueo bts, la diferencia de tiempo fue de aproximadamente 180 ciclos por instrucción.

Tenga en cuenta que este es el rendimiento recíproco, pero dado que las operaciones bloqueadas son operaciones de serialización, probablemente no exista diferencia con respecto a la latencia.

Conclusión: una operación bloqueada es pesada, pero una falta de memoria caché puede ser mucho más pesada. Además: una operación bloqueada no causa fallas en la memoria caché. Solo puede causar tráfico de sincronización de caché, cuando una línea de caché no es de propiedad exclusiva.

Para arrancar la máquina, utilicé una versión x64 de FreeLdr del proyecto ReactOS. Aquí está el código fuente del ASM:

#define LOOP_COUNT 1000 
#define UNROLLED_COUNT 100 

PUBLIC ProfileDummy 
ProfileDummy: 

    cli 

    // Get current TSC value into r8 
    rdtsc 
    mov r8, rdx 
    shl r8, 32 
    or r8, rax 

    mov rcx, LOOP_COUNT 
    jmp looper1 

.align 16 
looper1: 

REPEAT UNROLLED_COUNT 
    // nothing, or add something to compare against 
ENDR 

    dec rcx 
    jnz looper1 

    // Put new TSC minus old TSC into rax 
    rdtsc 
    shl rdx, 32 
    or rax, rdx 
    sub rax, r8 

    ret 

PUBLIC ProfileFunction 
ProfileFunction: 

    cli 

    rdtsc 
    mov r8, rdx 
    shl r8, 32 
    or r8, rax 
    mov rcx, LOOP_COUNT 

    jmp looper2 

.align 16 
looper2: 

REPEAT UNROLLED_COUNT 
    // Put here the code you want to profile 
    // make sure it doesn't mess up non-volatiles or r8 
    lock bts qword ptr [rsp - 8], 1 
ENDR 

    dec rcx 
    jnz looper2 

    rdtsc 
    shl rdx, 32 
    or rax, rdx 
    sub rax, r8 

    ret