multithreading - tipos - ¿Qué arquitecturas de CPU son compatibles con Compare And Swap(CAS)?

primeros procesadores

Question

solo curiosidad por saber qué arquitecturas de CPU admiten comparar e intercambiar primitivas atómicas?

Answer 1

Algunas personas comentaron / preguntaron si el prefijo "lock" es necesario en x86 / x64 para cmpxchg. La respuesta es sí para máquinas multinúcleo. La instrucción es completamente atómica para máquinas de un solo núcleo sin bloqueo.

Ha pasado un tiempo desde que estudié estas cosas tan profundamente, pero parece recordar que la instrucción es técnicamente reiniciable: puede abortar la instrucción a mitad del vuelo (si aún no ha tenido efectos secundarios) para evitar retrasar el manejo de interrupciones también. largo.

Answer 2

Comenzando con la arquitectura ARMv6, ARM tiene las instrucciones LDREX / STREX que se pueden usar para implementar una operación de cambio de comparación atómica.

Answer 3

Compare y swap se agregó a los mainframes de IBM en 1973. It (y compare doble y swap) aún se encuentran en los mainframes de IBM (junto con las funciones más recientes de multiprocesos como PLO - realizar operación bloqueada).

Answer 4

El x86 y Itanium tienen CMPXCHG (comparar e intercambiar)

Answer 5

Intel x86 tiene este soporte. IBM en su Guía de puertos de Solaris a Linux da este ejemplo:

bool_t My_CompareAndSwap(IN int *ptr, IN int old, IN int new)
{
        unsigned char ret;

        /* Note that sete sets a ''byte'' not the word */
        __asm__ __volatile__ (
                "  lock/n"
                "  cmpxchgl %2,%1/n"
                "  sete %0/n"
                : "=q" (ret), "=m" (*ptr)
                : "r" (new), "m" (*ptr), "a" (old)
                : "memory");

        return ret;
}

Answer 6

Perdón por muchas cartas. :(

Casi todas las instrucciones en el ISA x86 (excepto las denominadas instrucciones de cadena, y tal vez algunas otras), incluido CMPXCHG, son atómicas en el contexto de la CPU Unicore. Esto se debe a que, según la arquitectura x86, la CPU verifica las interrupciones recibidas después de la finalización de la ejecución de cada instrucción y nunca en el medio. Como resultado, la solicitud de interrupción puede detectarse y su gestión se iniciará solo en el límite entre la ejecución de dos instrucciones consecutivas. Debido a esto, todas las referencias de memoria tomadas por la CPU durante la ejecución de una sola instrucción están aisladas y no pueden ser intercaladas por ninguna otra actividad. Ese comportamiento es común para CPU unicore y multinúcleo. Pero si en el contexto de la CPU unicore solo hay una unidad del sistema que realiza acceso a la memoria, en el contexto de la CPU multinúcleo hay más de una unidad del sistema que realiza el acceso a la memoria simultáneamente. El aislamiento de la instrucción no es suficiente para la coherencia en dicho entorno, ya que los accesos de memoria realizados por diferentes CPU al mismo tiempo pueden intercalarse entre sí. Debido a esto, se debe aplicar una capa de protección adicional al protocolo de cambio de datos. Para el x86, esta capa es el prefijo de bloqueo, que inicia la transacción atómica en el bus del sistema.

Resumen: es seguro y menos costoso utilizar instrucciones de sincronización como CMPXCHG, XADD, BTS, etc. sin el prefijo de bloqueo si se tiene la seguridad de que solo se puede acceder a los datos a los que se accede mediante esta instrucción en un núcleo. Si no está seguro de esto, aplique el prefijo de bloqueo para proporcionar seguridad al cambiar el rendimiento.

Hay dos enfoques principales para la compatibilidad de sincronización de hardware por CPU:

1. Transacción atómica basada.
2. Protocolo de coherencia de caché basado.

Nadie es una bala de plata. Ambos enfoques tienen ventajas y desventajas.

El enfoque basado en transacciones atómicas se basa en el soporte del tipo especial de transacciones en el bus de memoria. Durante dicha transacción, solo un agente (núcleo de CPU) conectado al bus es elegible para acceder a la memoria. Como resultado, por un lado, todas las referencias de memoria realizadas por el propietario del bus durante la transacción atómica están aseguradas de realizarse como una única transacción ininterrumpida. Por otro lado, todos los demás agentes de bus (núcleos de CPU) se aplicarán para esperar la finalización de la transacción atómica, para recuperar la capacidad de acceder a la memoria. No importa a qué celdas de memoria quieran acceder, incluso si quieren acceder a la región de memoria a la que el propietario del bus no hace referencia durante la transacción atómica. Como resultado, el uso extenso de instrucciones prefijadas de bloqueo ralentizará significativamente el sistema. Por otro lado, debido al hecho de que el árbitro del autobús da acceso al autobús para cada agente de autobús de acuerdo con la programación de turnos rotativos, existe una garantía de que cada agente de autobús tendrá un acceso relativamente justo a la memoria y todos los agentes serán capaz de progresar y lo hizo con la misma velocidad. Además, el problema ABA entra en juego en caso de transacciones atómicas, porque por su naturaleza, las transacciones atómicas son muy cortas (pocas referencias de memoria hechas por instrucción única) y todas las acciones tomadas en la memoria durante la transacción dependen únicamente del valor de la región de memoria , sin tener en cuenta, es que la región de memoria fue accedida por alguien más entre dos transacciones. Un buen ejemplo de compatibilidad de sincronización basada en transacciones atómicas es la arquitectura x86, en la que las instrucciones prefijadas de bloqueo obligan a la CPU a ejecutarlas en transacciones atómicas.

El enfoque basado en el protocolo de coherencia de caché se basa en el hecho de que la línea de memoria se puede almacenar en caché solo en la memoria caché L1 en el único instante de tiempo. El protocolo de acceso a memoria en el sistema de coherencia de caché es similar a la siguiente secuencia de acciones:

1. CPU A almacena la línea de memoria X en la memoria caché L1. Al mismo tiempo, la CPU B desea acceder a la línea de memoria X. (X -> CPU A L1)
2. La CPU B emite la línea de acceso X a la transacción en el bus. (X -> CPU A L1)
3. Todos los agentes de bus (núcleos de CPU) tienen un llamado agente de espionaje que escucha todas las transacciones en el bus y verifica si el acceso a la línea de memoria al que se solicitó la transacción se almacena en su caché CPU L1 propietaria. Por lo tanto, el agente de espionaje de la CPU A detecta que la CPU A posee la línea de memoria solicitada por la CPU B. (X -> CPU A L1)
4. La CPU A suspende la transacción de acceso a memoria emitida por la CPU B. (X -> CPU A L1)
5. La CPU A purga la línea de memoria solicitada por B desde su caché L1. (X -> memoria)
6. CPU A reanuda la transacción previamente suspendida. (X -> memoria)
7. La CPU B recupera la línea de memoria X de la memoria. (X -> CPU B L1)

Gracias a ese protocolo, el núcleo de CPU siempre accede a los datos reales en la memoria, y los accesos a la memoria se serializan en orden estricto, un acceso en el tiempo. El soporte de sincronización basado en el protocolo de coherencia de caché se basa en el hecho de que la CPU puede detectar fácilmente que se accedió a la línea de memoria particular entre dos puntos de tiempo. Durante el primer acceso a la memoria a la línea X que debe abrir la transacción, la CPU puede marcar que la línea de memoria en la memoria caché L1 debe ser controlada por el agente de inspección. A su vez, el agente de espionaje puede durante el enjuague de la línea de caché, además de realizar una comprobación para identificar que esa línea está marcada para el control, y elevar la bandera interna si se enjuaga la línea controlada. Como resultado, si la CPU verificará el indicador interno durante el acceso a la memoria que cierra la transacción, sabrá que la línea de memoria controlada pudo ser cambiada por otra persona y concluirá que la transacción se debe realizar con éxito o se debe considerar como fallida. Esta es la forma de implementación de la clase de instrucción LL / SCS. Este enfoque es más simple que la transacción atómica y proporciona mucha más flexibilidad en la sincronización, ya que se puede construir mucho más número de primitivas de sincronización sobre la base en comparación con el enfoque de las transacciones atómicas. Este enfoque es más escalable y eficiente, ya que no bloquea el acceso a la memoria para todas las demás partes del sistema. Y como puede ver, resuelve el problema de ABA, porque se basa en el hecho de la detección de acceso a la región de memoria, pero no en el valor de la detección de cambio de región de memoria. Cualquier acceso a la región de memoria que participa en una transacción en curso se considerará como una transacción fallida. Y esto puede ser bueno y malo al mismo tiempo, porque el algoritmo en particular puede interesar solo en el valor de la región de memoria y no tiene en cuenta que alguien accedió a esa ubicación en el medio, hasta que ese acceso cambie la memoria . En ese caso, la lectura del valor de la memoria en el medio dará lugar a un falso error de transacción negativa. Además, este enfoque puede conducir a una gran degradación del rendimiento de los flujos de control que se concentran en la misma línea de memoria, ya que pueden alinear constantemente la línea de memoria entre sí, impidiéndose mutuamente la transacción de finalización con éxito. Ese es un problema realmente significativo porque en el caso de la terminal puede activar el sistema en Livelock. Compatibilidad de sincronización basada en el protocolo de coherencia de caché que generalmente se utiliza en la CPU RISC, debido a su simplicidad y flexibilidad. Pero debe tenerse en cuenta que Intel decidió apoyar dicho enfoque para la compatibilidad de sincronización en la arquitectura x86 también. El año pasado, Intel anunció las extensiones de sincronización transaccional a la arquitectura x86 que se implementarán en la generación de procesadores Intel de Haswell. Como resultado, parece que el x86 tendrá un soporte de sincronización más poderoso y permitirá a los desarrolladores del sistema usar las ventajas de ambos enfoques.

Answer 7

Powerpc tiene primitivas más potentes disponibles: "lwarx" y "stwcx"

lwarx carga un valor de la memoria pero recuerda la ubicación. Cualquier otro hilo o CPU que toque esa ubicación hará que falle el "stwcx", una instrucción de almacenamiento condicional.

Por lo tanto, el combo lwarx / stwcx le permite implementar incrementos / decrementos atómicos, comparar y intercambiar, y operaciones atómicas más potentes, como "índice de buffer circular de incremento atómico".

Answer 8

Solo para completar la lista, MIPS tiene instrucciones Load Linked (ll) y Store Conditional (sc) que cargan un valor de la memoria y luego almacenan condicionalmente si ninguna otra CPU ha accedido a la ubicación. Es cierto que puede usar estas instrucciones para realizar intercambios, incrementos y otras operaciones. Sin embargo, la desventaja es que con una gran cantidad de CPUs que ejercen bloqueos de manera muy intensa ingresa a livelock: la tienda condicional con frecuencia fallará y necesitará otro ciclo para volver a intentarlo, lo que no funcionará, etc.

La implementación del software mutex_lock puede volverse muy complicada al intentar implementar un retroceso exponencial si estas situaciones se consideran lo suficientemente importantes como para preocuparse. En un sistema en el que trabajé con 128 núcleos, lo eran.

Answer 9

Sparc v9 tiene una instrucción cas. El manual de arquitectura SPARC v9 discute el uso de la instrucción CAS en el Anexo J, mira específicamente los ejemplos J.11 y J.12.

Creo que el nombre de la instrucción es en realidad "casa", porque puede acceder al espacio de direcciones actual o a un alternativo. "cas" es una macro de ensamblador que accede al ASI actual.

También hay un artículo en developers.sun.com que analiza las diversas instrucciones atómicas que los procesadores Sparc han implementado a lo largo de los años, incluida la versión en cas.

Answer 10

Una forma diferente y más fácil de responder a esta pregunta puede ser enumerar plataformas multiprocesador que NO admiten una comparación y un intercambio (o un enlace de carga / almacenamiento-condicional que se puede usar para escribir uno).

El único que conozco es PARISC, que solo tiene una instrucción atómica de palabras claras. Esto se puede usar para construir un mutex (siempre que uno alinee la palabra en un límite de 16 bytes). No hay CAS en esta arquitectura (a diferencia de x86, ia64, ppc, sparc, mips, s390, ...)