concurrency - resueltos - microprocesador

Instrucciones de SSE: ¿qué CPU puede hacer operaciones de memoria atómica de 16B?

Question

Considere la posibilidad de tener acceso a una sola memoria (una lectura única o una sola escritura, no lectura + escritura) en una CPU x86. La instrucción está accediendo a 16 bytes (128 bits) de memoria y la ubicación de la memoria a la que se accede está alineada con 16 bytes.

El documento "Libro blanco de solicitud de memoria Intel® 64" indica que para "Instrucciones que leen o escriben una palabra cuádruple (8 bytes) cuya dirección se alinea en un límite de 8 bytes", la operación de memoria parece ejecutarse como un único acceso de memoria independientemente de tipo de memoria

La pregunta: ¿Existen CPUs Intel / AMD / etc x86 que garanticen que leer o escribir 16 bytes (128 bits) alineados con un límite de 16 bytes se ejecute como un único acceso a la memoria? Es así, ¿qué tipo particular de CPU es (Core2 / Atom / K8 / Phenom / ...)? Si proporciona una respuesta (sí / no) a esta pregunta, especifique también el método utilizado para determinar la respuesta: búsqueda de documentos PDF, pruebas de fuerza bruta, pruebas de matemáticas o cualquier otro método que haya utilizado para determinar la respuesta.

Esta pregunta se relaciona con problemas tales como http://research.swtch.com/2010/02/off-to-races.html

Actualizar:

Creé un programa de prueba simple en C que puedes ejecutar en tus computadoras. Compila y ejecuta en tu Phenom, Athlon, Bobcat, Core2, Atom, Sandy Bridge o cualquier CPU compatible con SSE2 que tengas. Gracias.

// Compile with:
// gcc -o a a.c -pthread -msse2 -std=c99 -Wall -O2
//
// Make sure you have at least two physical CPU cores or hyper-threading.
#include <pthread.h>
#include <emmintrin.h>
#include <stdio.h>
#include <stdint.h>
#include <string.h>
typedef int v4si __attribute__ ((vector_size (16)));
volatile v4si x;
unsigned n1[16] __attribute__((aligned(64)));
unsigned n2[16] __attribute__((aligned(64)));
void* thread1(void *arg) {
for (int i=0; i<100*1000*1000; i++) {
int mask = _mm_movemask_ps((__m128)x);
n1[mask]++;
x = (v4si){0,0,0,0};
}
return NULL;
}
void* thread2(void *arg) {
for (int i=0; i<100*1000*1000; i++) {
int mask = _mm_movemask_ps((__m128)x);
n2[mask]++;
x = (v4si){-1,-1,-1,-1};
}
return NULL;
}
int main() {
// Check memory alignment
if ( (((uintptr_t)&x) & 0x0f) != 0 )
abort();
memset(n1, 0, sizeof(n1));
memset(n2, 0, sizeof(n2));
pthread_t t1, t2;
pthread_create(&t1, NULL, thread1, NULL);
pthread_create(&t2, NULL, thread2, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
for (unsigned i=0; i<16; i++) {
for (int j=3; j>=0; j--)
printf("%d", (i>>j)&1);
printf(" %10u %10u", n1[i], n2[i]);
if(i>0 && i<0x0f) {
if(n1[i] || n2[i])
printf(" Not a single memory access!");
}
printf("/n");
}
return 0;
}

La CPU que tengo en mi computadora portátil es Core Duo (no Core2). Esta CPU particular falla la prueba, implementa lecturas / escrituras de memoria de 16 bytes con una granularidad de 8 bytes. El resultado es:

0000 96905702 10512
0001 0 0
0010 0 0
0011 22 12924 Not a single memory access!
0100 0 0
0101 0 0
0110 0 0
0111 0 0
1000 0 0
1001 0 0
1010 0 0
1011 0 0
1100 3092557 1175 Not a single memory access!
1101 0 0
1110 0 0
1111 1719 99975389

Answer 1

De hecho, hay una advertencia en el Manual de Arquitectura de Intel Vol 3A. Sección 8.1.1 (mayo de 2011), en la sección de operaciones atómicas garantizadas:

Puede implementarse una instrucción x87 o una SSE que acceda a datos mayores que un quadword utilizando múltiples accesos de memoria. Si tal instrucción se almacena en la memoria, algunos de los accesos pueden completarse (escribir en la memoria) mientras que otro causa fallas en la operación por razones arquitectónicas (por ejemplo, debido a una entrada de tabla de página que está marcada como "no presente"). En este caso, los efectos de los accesos completados pueden ser visibles para el software aunque la instrucción general haya causado un error. Si la invalidación de TLB se ha retrasado (consulte la Sección 4.10.4.4), tales fallas de página pueden ocurrir incluso si todos los accesos están en la misma página.

por lo tanto, no se garantiza que las instrucciones SSE sean atómicas, incluso si la arquitectura subyacente utiliza un solo acceso a memoria (esta es una razón por la cual se introdujo la valla de memoria).

Combine eso con esta afirmación del Manual de optimización de Intel, Sección 13.3 (abril de 2011)

Las instrucciones AVX y FMA no introducen ninguna nueva operación de memoria atómica garantizada.

y el hecho de que ninguna de las operaciones de carga o almacenamiento de SIMD garantiza la atomicidad, podemos llegar a la conclusión de que Intel no es compatible con ninguna forma de SIMD atómica (aún).

Como un poco más, si la memoria se divide a lo largo de líneas de caché o límites de página (cuando se usan elementos como movdqu que permiten el acceso no alineado), los siguientes procesadores no realizarán accesos atómicos, independientemente de la alineación, pero los procesadores posteriores (una vez más desde Intel Manual de arquitectura):

Procesadores Intel Core 2 Duo, Intel® Atom ™, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon, familia P6, Pentium e Intel486. Los procesadores de la familia Intel Core 2 Duo, Intel Atom, Intel Core Duo, Pentium M, Pentium 4, Intel Xeon y P6

Answer 2

El "Manual del programador de arquitectura AMD, Volumen 1: Programación de aplicaciones" dice en la sección 3.9.1: " CMPXCHG16B se puede usar para realizar accesos atómicos de 16 bytes en el modo de 64 bits (con ciertas restricciones de alineación)".

Sin embargo, no hay tal comentario sobre las instrucciones de SSE. De hecho, hay un comentario en 4.8.3 que el prefijo LOCK "causa una excepción de código de operación no válida cuando se usa con instrucciones de medios de 128 bits". Por lo tanto, me parece bastante concluyente que los procesadores AMD NO garantizan los accesos atómicos de 128 bits para las instrucciones SSE, y la única manera de hacer un acceso atómico de 128 bits es usar CMPXCHG16B .

El " Manual de desarrollo de software Intel ARTH 64 e IA-32 Volume 3A: Guía de programación del sistema, Parte 1 " dice en 8.1.1 "Se puede implementar una instrucción x87 o SSE que acceda a datos mayores que un quadword utilizando múltiples accesos de memoria. " Esto es bastante concluyente de que las instrucciones SSE de 128 bits no están garantizadas atómicas por la ISA. El volumen 2A de los documentos de Intel dice de CMPXCHG16B : "Esta instrucción se puede usar con un prefijo LOCK para permitir que la instrucción se ejecute atómicamente".

Además, los fabricantes de CPU no han publicado garantías escritas de operaciones atómicas de 128b SSE para modelos de CPU específicos donde ese es el caso.

Answer 3

El IS86 x86 no garantiza la atomicidad para nada mayor que 8B, por lo que las implementaciones son libres de implementar el soporte SSE / AVX como lo hace Pentium III / Pentium M / Core Duo: internamente los datos se manejan en mitades de 64 bits. Una tienda de 128 bits se hace como dos tiendas de 64 bits. La ruta de datos hacia / desde la memoria caché tiene solo 64b de ancho en la microarquitectura Yonah (Core Duo). (fuente: documento microarch de Agner Fog ).

Las implementaciones más recientes tienen rutas de datos más amplias internamente y manejan las instrucciones 128b como una única operación. Core 2 Duo (conroe / merom) fue el primer microarchivo descifrado por Intel P6 con rutas de datos 128b. (IDK sobre P4, pero afortunadamente es lo suficientemente viejo como para ser totalmente irrelevante).

Esta es la razón por la cual OP encuentra que las operaciones 128b no son atómicas en Intel Core Duo (Yonah), pero otros carteles descubren que son atómicas en diseños Intel posteriores, comenzando con Core 2 (Merom).

Los diagramas en este informe de Realworldtech sobre Merom vs. Yonah muestran la ruta de 128 bits entre ALU y el caché de datos L1 en Merom (y P4), mientras que el Yonah de baja potencia tiene una ruta de datos de 64 bits. La ruta de datos entre la caché L1 y L2 es 256b en los 3 diseños.

El siguiente salto en el ancho de la ruta de datos vino con Haswell de Intel , con 256b (32B) cargas / tiendas AVX / AVX2 y una ruta de 64Byte entre la caché L1 y L2. Espero que 256b cargas / tiendas sean atómicas en Haswell, Broadwell y Skylake, pero no tengo una para probar. Me olvido si Skylake amplió nuevamente los caminos en preparación para AVX512 en Skylake-EP (la versión de servidor), o si quizás la implementación inicial de AVX512 será como AVX de SnB / IvB, y tendrá cargas / tiendas de 512b ocupando un puerto de carga / tienda por 2 ciclos

Como señala janneb en su excelente respuesta experimental, el protocolo de coherencia de caché entre sockets en un sistema multinúcleo podría ser más estrecho que el que se obtiene dentro de una CPU de caché compartida de último nivel. No existe un requisito arquitectónico de atomicidad para cargas / tiendas amplias, por lo que los diseñadores pueden convertirlas en atómicas dentro de un zócalo pero no atómicas en todos los zócalos, si es conveniente. IDK qué tan ancha es la ruta de datos lógicos entre socket para la familia Bulldozer de AMD o para Intel. (Digo "lógico", porque incluso si los datos se transfieren en fragmentos más pequeños, es posible que no modifiquen una línea de caché hasta que se reciban por completo).

Encontrar artículos similares sobre las CPU AMD debería permitir extraer conclusiones razonables sobre si las operaciones 128b son atómicas o no. Solo consultar las tablas de instrucciones es de alguna ayuda:

K8 decodifica movaps reg, [mem] a 2 m-ops, mientras que K10 y bulldozer-family lo decodifican a 1 m-op. El lince de baja potencia de AMD lo decodifica en 2 operaciones, mientras que el jaguar decodifica 128b movaps a 1 m-op. (Admite AVX1 similar a las CPU de bulldozer-family: 256b ins (incluso ALU ops) se dividen en dos operaciones de 128b. Intel SnB solo divide 256b load / stores, mientras que tiene ALU de ancho completo.)

El Opteron 2435 de janneb es una CPU de 6 núcleos de Estambul, que es parte de la familia K10 , por lo que esta conclusión atómica single-m-op -> parece precisa en un solo socket.

Intel Silvermont hace 128b cargas / tiendas con un solo uop, y un rendimiento de uno por reloj. Esto es lo mismo que para cargas / tiendas enteras, por lo que es bastante probable que sea atómico.

Answer 4

En las arquitecturas Intel® 64 e IA-32 Manual del desarrollador: vol. 3A , que en la actualidad contiene las especificaciones del documento en blanco para pedidos de memoria que mencionas, se dice en la sección 8.2.3.1, como te das cuenta, que

The Intel-64 memory ordering model guarantees that, for each of the following memory-access instructions, the constituent memory operation appears to execute as a single memory access: • Instructions that read or write a single byte. • Instructions that read or write a word (2 bytes) whose address is aligned on a 2 byte boundary. • Instructions that read or write a doubleword (4 bytes) whose address is aligned on a 4 byte boundary. • Instructions that read or write a quadword (8 bytes) whose address is aligned on an 8 byte boundary. Any locked instruction (either the XCHG instruction or another read-modify-write instruction with a LOCK prefix) appears to execute as an indivisible and uninterruptible sequence of load(s) followed by store(s) regardless of alignment.

Ahora, dado que la lista anterior NO contiene el mismo lenguaje para doble cuadrante (16 bytes), se deduce que la arquitectura NO garantiza que las instrucciones que acceden a 16 bytes de memoria sean atómicas.

Dicho esto, el último párrafo indica una salida, es decir, la instrucción CMPXCHG16B con el prefijo LOCK. Puede usar la instrucción CPUID para averiguar si su procesador es compatible con CMPXCHG16B (el bit de función "CX16").

En el documento AMD correspondiente, AMD64 Technology AMD64 Architecture Programmer''s Manual Volume 2: System Programming , no puedo encontrar un lenguaje claro similar.

EDITAR: resultados del programa de prueba

(Programa de prueba modificado para aumentar #iteraciones por un factor de 10)

En un Xeon X3450 (x86-64):

0000 999998139 1572 0001 0 0 0010 0 0 0011 0 0 0100 0 0 0101 0 0 0110 0 0 0111 0 0 1000 0 0 1001 0 0 1010 0 0 1011 0 0 1100 0 0 1101 0 0 1110 0 0 1111 1861 999998428

En un Xeon 5150 (32 bits):

0000 999243100 283087 0001 0 0 0010 0 0 0011 0 0 0100 0 0 0101 0 0 0110 0 0 0111 0 0 1000 0 0 1001 0 0 1010 0 0 1011 0 0 1100 0 0 1101 0 0 1110 0 0 1111 756900 999716913

En un Opteron 2435 (x86-64):

0000 999995893 1901 0001 0 0 0010 0 0 0011 0 0 0100 0 0 0101 0 0 0110 0 0 0111 0 0 1000 0 0 1001 0 0 1010 0 0 1011 0 0 1100 0 0 1101 0 0 1110 0 0 1111 4107 999998099

¿Esto significa que Intel y / o AMD garantizan que los accesos de memoria de 16 bytes son atómicos en estas máquinas? En mi humilde opinión, no es así. No está en la documentación como un comportamiento arquitectónico garantizado, y por lo tanto uno no puede saber si en estos procesadores particulares los accesos a memoria de 16 bytes realmente son atómicos o si el programa de prueba simplemente falla al desencadenarlos por una razón u otra. Y confiar en eso es peligroso.

EDIT 2: Cómo hacer que el programa de prueba falle

¡Decir ah! Logré hacer que el programa de prueba fallara. En el mismo Opteron 2435 que el anterior, con el mismo binario, pero ahora ejecutándolo a través de la herramienta "numactl" que especifica que cada hilo se ejecuta en un socket separado, obtuve:

0000 999998634 5990 0001 0 0 0010 0 0 0011 0 0 0100 0 0 0101 0 0 0110 0 0 0111 0 0 1000 0 0 1001 0 0 1010 0 0 1011 0 0 1100 0 1 Not a single memory access! 1101 0 0 1110 0 0 1111 1366 999994009

Entonces, ¿qué implica esto? Bueno, el Opteron 2435 puede, o no, garantizar que los accesos de memoria de 16 bytes sean atómicos para los accesos dentro del socket, pero al menos el protocolo de coherencia de caché que se ejecuta en la interconexión de HyperTransport entre los dos sockets no proporciona tal garantía.

EDIT 3: ASM para las funciones de hilo, a petición de "GJ".

Aquí está el asm generado para las funciones de subprocesos para la versión GCC 4.4 x86-64 utilizada en el sistema Opteron 2435:

.globl thread2
.type thread2, @function
thread2:
.LFB537:
.cfi_startproc
movdqa .LC3(%rip), %xmm1
xorl %eax, %eax
.p2align 5,,24
.p2align 3
.L11:
movaps x(%rip), %xmm0
incl %eax
movaps %xmm1, x(%rip)
movmskps %xmm0, %edx
movslq %edx, %rdx
incl n2(,%rdx,4)
cmpl $1000000000, %eax
jne .L11
xorl %eax, %eax
ret
.cfi_endproc
.LFE537:
.size thread2, .-thread2
.p2align 5,,31
.globl thread1
.type thread1, @function
thread1:
.LFB536:
.cfi_startproc
pxor %xmm1, %xmm1
xorl %eax, %eax
.p2align 5,,24
.p2align 3
.L15:
movaps x(%rip), %xmm0
incl %eax
movaps %xmm1, x(%rip)
movmskps %xmm0, %edx
movslq %edx, %rdx
incl n1(,%rdx,4)
cmpl $1000000000, %eax
jne .L15
xorl %eax, %eax
ret
.cfi_endproc

y para completar, .LC3 que es la información estática que contiene el vector (-1, -1, -1, -1) usado por thread2:

.LC3:
.long -1
.long -1
.long -1
.long -1
.ident "GCC: (GNU) 4.4.4 20100726 (Red Hat 4.4.4-13)"
.section .note.GNU-stack,"",@progbits

También tenga en cuenta que esta es la sintaxis AT & T ASM, no la sintaxis Intel con la que los programadores de Windows estarían más familiarizados. Finalmente, esto es con march = native que hace que GCC prefiera MOVAPS; pero no importa, si uso march = core2 usará MOVDQA para almacenar en x, y aún puedo reproducir las fallas.

Answer 5

Se han publicado muchas respuestas hasta ahora y, por lo tanto, mucha información ya está disponible (como confusión de efectos secundarios). Me gustaría ubicar los datos del manual de Intel sobre las operaciones atómicas garantizadas por hardware ...

En los procesadores más recientes de Intel de nehalem y familia de puentes arenosos, está garantizado leer o escribir en un quadword alineado con un límite de 64 bits.

Incluso las lecturas o escrituras de bytes sin alinear de 2, 4 u 8 están garantizadas para ser atómicas siempre que se encuentren en memoria caché y quepan en una línea de caché.

Una vez dicho esto, la prueba publicada en esta pregunta pasa al procesador Intel i5 de puente arenoso.

Answer 6

EDITAR: En los últimos dos días hice varias pruebas en mis tres PC y no reproduje ningún error de memoria, así que no puedo decir nada más precisamente. Tal vez este error de memoria también depende del sistema operativo.

EDITAR: estoy programando en Delphi y no en C, pero debería entender C. Así que he traducido el código, aquí están los procedimientos de hilos donde la parte principal está hecha en ensamblador:

procedure TThread1.Execute;
var
n :cardinal;
const
ConstAll0 :array[0..3] of integer =(0,0,0,0);
begin
for n := 0 to 100000000 do
asm
movdqa xmm0, dqword [x]
movmskps eax, xmm0
inc dword ptr[n1 + eax *4]
movdqu xmm0, dqword [ConstAll0]
movdqa dqword [x], xmm0
end;
end;
{ TThread2 }
procedure TThread2.Execute;
var
n :cardinal;
const
ConstAll1 :array[0..3] of integer =(-1,-1,-1,-1);
begin
for n := 0 to 100000000 do
asm
movdqa xmm0, dqword [x]
movmskps eax, xmm0
inc dword ptr[n2 + eax *4]
movdqu xmm0, dqword [ConstAll1]
movdqa dqword [x], xmm0
end;
end;

Resultado: ¡ no me equivoco en mi PC quad core y no me equivoco en mi PC dual core como esperaba!

1. PC con CPU Intel Pentium4
2. PC con CPU Intel Core2 Quad Q6600
3. PC con CPU Intel Core2 Duo P8400

¿Puedes mostrar cómo el debugador ve el código de tu procedimiento de subprocesos? Por favor...