Diferencia entre consistencia estricta y consistencia secuencial

8

Entiendo la consistencia estricta y secuencial independientemente bastante bien.

El estricto C básicamente impone el orden real en el que se ejecutaron las instrucciones en el reloj global.

La coherencia secuencial básicamente impone el orden solo en un procesador.

Sin embargo, tengo problemas para reunir algo de literatura. http://www.cs.nmsu.edu/~pfeiffer/classes/573/notes/consistency.html describe la coherencia secuencial que permite el "retraso" de la memoria. Puede tomar tiempo para que una escritura se propague por todos los procesadores. Pero cuando lo hace, los alcanza a todos a la vez, lo cual está bien. Por lo tanto, lo siguiente es válido bajo Consistencia secuencial

P1:  W(x)1
-----------------------
P2:        R(x)0 R(x)1

Lo que me preocupa ahora son los siguientes procesos, que es algo así como el algoritmo de Dekker.

P1:  W(x)1  R(y)0
-----------------
P2:  W(y)1  R(x)0

Esto seguramente NO debería ser posible con la coherencia secuencial ( http://portal.acm.org/citation.cfm?id=1787234.1787255 pg 2). No hay un orden total que pueda dar este resultado.

Pero tiene sentido la idea de que la coherencia secuencial permite que las escrituras se propaguen lentamente y un hilo puede no tener idea de lo que otros procesadores están haciendo.

¿Que me estoy perdiendo aqui?

pl.programming-languages dc.parallel-comp concurrency jetru
fuente
Creo que confunde la coherencia secuencial y la coherencia causal. SC es una condición más fuerte que tu fraseo intuitivo ... si te entiendo correctamente. Su segunda ejecución es CC (y PRAM C) pero no SC.
Aaron Sterling
Sí quizás. Mi pregunta es específicamente ¿por qué la segunda ejecución NO es secuencialmente consistente? Si el primero es, ¿cuál es el razonamiento especial que hace que la ejecución 2 sea inconsistente?
jetru
Gracias por todas las respuestas. También leí sobre la coherencia causal y entendí que lo que estaba pensando era exactamente eso.
jetru

Respuestas:

8

Tu no te estas perdiendo nada :)

El algoritmo de Dekker no será secuencialmente consistente en el multiprocesador basado en la jerarquía de memoria compartida distribuida, pero es muy posible ya que las actualizaciones de memoria se propagan no al ritmo de la actualización de memoria local (caché) sino de forma asíncrona a través de protocolos de coherencia de caché como MESI (modelo de memoria más débil).

En un procesador uni en el cual el algoritmo de Dekker este no es el caso y será estrictamente consistente.

Sai Venkat
fuente
Entonces, al considerar la propagación de actualizaciones de memoria, en realidad estoy relajando el modelo de memoria, por lo tanto, en mi modelo de memoria imaginado, la ejecución 2 es posible. En un almacén de memoria consecuentemente consecuentemente secuencial, las escrituras se propagarían instantáneamente. ¿Es esto correcto?
jetru
1
Sí. Si cada proceso solo mira su memoria local, es posible la ejecución 2. En una coherencia secuencial adecuada, las escrituras no necesitan propagarse instantáneamente, sino cuando otra ubicación se refiere o actualiza a la ubicación escrita, que normalmente es el caso.
Sai Venkat
4

Ya tienes la respuesta correcta. La segunda ejecución no es secuencialmente consistente porque "no hay un orden total que pueda dar este resultado".

Supongo que tu confusión proviene de esta idea:

La idea de que la coherencia secuencial permite que las escrituras se propaguen lentamente y un hilo puede no tener idea de lo que otros procesadores están haciendo.

Esto es correcto. La propagación puede ser lenta. La coherencia secuencial permite que un hilo no sea consciente de lo que otros procesos están haciendo (para cualquier programa). Sin embargo, la coherencia secuencial no permite que cada hilo no sea consciente de lo que otros procesos están haciendo (para algunos programas, incluido el algoritmo de Dekker).

La frase anterior "para algunos programas" proviene de esta consideración: incluso con coherencia secuencial, si los hilos no usan memoria compartida, ningún hilo es consciente del comportamiento de otro hilo.

yhirai
fuente
3

Este documento también podría ayudar a comprender, ya que su título sugiere la diferencia entre las dos consistencias que menciona. (Sin embargo, se trata en gran parte de la implementación de los objetos compartidos SeqCon y StrictCon en el paso de mensajes, que es una forma de pensar sobre el retraso que mencionó).

Para responder a su pregunta específica: la coherencia secuencial exige que todos los eventos sucedan en un orden secuencial y que lo que sucede en un proceso siempre es coherente con el tiempo.

Entonces la razón por la cual 

P1:  W1(x,1)  R2(y)0
-------------------
P2:  W2(y,1)  R2(x)0

no es posible, es que tiene que haber alguna secuencia global, por ejemplo W1(x,1) R1(y)0 W2(y,1) R2(x)?. En esta secuencia, la última lectura claramente no puede devolver 0. Sin embargo, esta secuencia no tiene que ser consistente con el tiempo real. Es completamente posible (consistencia secuencial) que en tiempo real la secuencia de eventos fueraW1(x,1) W2(y,1) R1(y)0 R2(x)1 . Esta secuencia es ilegal para una consistencia estricta (ya que R1 (y) no devolvió el valor de la escritura anterior).

Martin B.
fuente
Lamento el comentario tardío, pero ¿podría ser posible que W1 (x, 1) W2 (y, 1) R1 (y) 1 R2 (x) 1 también ocurra en un entorno secuencialmente consistente? Si se ordena que la orden de ejecución suceda en este orden antes de que ocurra a tiempo?
William
La ejecución W1 (x, 1) W2 (y, 1) R1 (y) 1 R2 (x) 1 es secuencialmente consistente, incluso estrictamente consistente, si no me equivoco (ya estoy un poco cansado hoy).
Martin B.
En cuanto a lo que quiere decir exactamente con "la orden de ejecución está dispuesta a suceder", no estoy seguro de entender.
Martin B.