performance atomic cpu-architecture lock-free

performance - costo de operación atómica



atomic cpu-architecture (3)

¿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? ¿Va a enjuagar el búfer en una CPU fuera de servicio?

¿Qué efectos habrá en el caché?

Estoy interesado en CPU modernas y populares: x86, x86_64, PowerPC, SPARC, Itanium.

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

Libro de Ppro & P2 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

Las instrucciones bloqueadas son la serialización, las operaciones de sincronización .... / about Fuera de orden / bloqueado RMW / read-modify-write = atomic itself / instruction garantiza que el procesador ejecutará todas las instrucciones antes de la instrucción bloqueada antes de ejecutarlo. / about yet not flushed writes / obliga a todas las escrituras publicadas dentro del procesador a enjuagarse a la memoria externa antes de ejecutar las siguientes instrucciones.

/ about SMP / semáforo está en caché en estado S ... emitiendo una transacción de lectura e invalidación para 0 bytes de fecha (esto es una eliminación / de copias compartidas de la línea de caché en CPU adyacentes /)

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 las fallas en el caché.

El costo del prefijo x86 LOCK, o CAS, antes de PentiumPro (como se describe en el documento), es un acceso a memoria (como una falta de caché), + operaciones de memoria de otros procesadores, + cualquier disputa con otros procesadores que intentan BLOQUEAR 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 caché relevante (según el enlace publicado anteriormente).

En realidad, el caso CAS puede ser más complicado, como se explica en esta página , sin tiempos, pero con una descripción reveladora por parte de un ingeniero confiable.

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 los mutexes, donde siempre CAS 0 y 1) puede costar dos errores 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 protocolo de coherencia de caché MESI . 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, explicado, es el siguiente:

  • la CARGA provoca una falta de caché: la caché correspondiente se carga desde la memoria en estado Compartido (es decir, otros procesadores aún pueden guardar esa línea de caché 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 Exclusivo. Costo posible: 1 error de caché. Esto no es necesario si ya es de propiedad exclusiva, es decir, en el 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 el 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 deberán 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é. En cambio, una operación LOCKed solo puede costar una caché fallida (porque la caché se solicitará directamente en estado Exclusive).

En todos los casos, una solicitud de caché puede ser detenida por otros procesadores que ya están modificando los datos.

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 coincidencia de 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 bloqueada en una falta de caché, agregué una instrucción wbinvld antes de la instrucción bloqueada y puse el wbinvld más un add [rsp - 8], rax en el bucle de comparación. En ambos casos, el costo fue de aproximadamente 80,000 ciclos por par de instrucciones. En el caso de lock 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 de 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