[Parallel Computing] (17) Memory Consistency

Consistency라는 단어는 어떤 의미일까?
네이버 사전을 찾아보면 일관성이라 표현되고, 영영 사전을 검색하면 아래와 같이 표현된다.

the quality of always behaving or performing in a similar way, or of always happening in a similar way

이전 Cache Coherence 포스트를 봤다면, 이상하다고 생각할 수도 있다.  Coherence도 우리말로 일관성이라는 의미를 가지며, 영영 사전에 의하면 'the situation when the parts of someting fit together in a natual or reasonable way'라고 표현했기 때문이다.
둘 다 일관성이며, 영영 사전에서 표현한 문구도 비슷하기 때문이다.
그러나 단어 해석에 미묘한 차이가 있다. 영영 사전을 살펴보면 Consistency는 'always happening in a similar way'라 하고, Coherence는 'fit together in a natural or reasonable way'라고 하였다. 이를 다시 표현하면, Consistency는 타당한 방식이 아니더라도 항상 동일한 방식으로 수행되는 것으로 이야기 하고, Coherence는 동일한 방식을 넘어 타당한 방식으로 수행되어야 한다고 말한다.
즉, 아래와 같이 정리가 가능하다.

In summary, consistency focuses on the absence of contradiction, while coherence goes beyond that to encompass a sense of harmony or logical unity among the elements of a system.
(Consistency는 모순의 부재에 초점을 맞추고, Coherence은 그 이상으로 시스템의 요소들 사이에 조화나 논리적 통일감을 포함합니다.)

이렇듯 Consistency는 어떤 동작을 수행함에 있어서 항상 동일한 방식으로 수행되는 것을 의미한다.
즉, Memory Consistency는 메모리 접근 동작을 항상 일정한 방식대로 수행되도록 하는 것을 말한다.
예를 들어, 두 개의 스레드(T0, T1)이 Shared variable(data, done)을 접근하는 코드를 각각 수행하고 있다고 생각해보자.

// shared variable
data = 0
done = false

// Thread-0
data = 5;         // T0_A
done = true;      // T0_B

// Thread-1
while(not done);  // T1_A
print data;       // T1_B

딱 코드를 봤을 때 우리가 생각할 수 있는 동작은 아래와 같다,
> 스레드 T0가 data에 '5'를 쓰면, 스레드 T1이 이를 출력한다.
이렇게 수행되려면 각 코드는 어떻게 실행되어야 하는 가? Case 1과 같이 실행되어야 우리가 원하는 동작을 수행할 수 있다.

// Case 1
T0_A : data = 5;        
T0_B : done = true;
T1_A : while (not done);
T1_B : print data 
Result : print 5

// Case 2
T0_B : done = true;
T1_A : while (not done);
T1_B : prnt data
T0_A : data 5
Result : print 0

위의 코드에는 2개의 Case에 대해서만 다루웠지만, 조합을 따지면 4! = 24개의 경우 수가 발생할 수 있다.  코드 실행마다 매번 Case가 달라지면 그 결과 값도 달라질 수 밖에 없다. 그러므로 수행 순서가 중요하다. 여담으로 Cache coherence는 데이터와 관련된 것으로 항상 최신의 데이터를 읽을 수 있도록 하는 것으로 이 문제를 해결하는 데는 도움이 되지 않는다.
이러한 특별한 순서를 정하는 방법에 따라 Memory Consistency Model이 달라진다. 즉, Memory Consistency Model은 서로 다른 프로세서들이 각자가 수행한 메모리 업데이트를 언제 확인할 수 있을 것인가를 정의한다. 이 모델은 Programming complexity와 performance를 조화롭게 균형을 맞추도록 해야 한다. 이는 프로그래머와 멀티프로세서 시스템 간의 Contract이다.
Memory Consistency model에는 여러가지가 존재한다. 그 중 하나인 Sequential consistency를 살펴보도록 하겠다. SC(Sequential consistency)는 여러 스레드 프로그램 P의 결과물이 프로그램 P를 하나의 스레드에서 수행한 것과 같은 결과를 보이는 것을 말한다. 아래 Lamport의 말처럼 이를 위해서는 스레들 간에 실행 순서가 정해져 있고, 하나의 스레드 안에서 실행 순서가 정해져있어야 한다.

A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operation of all the processors were executed in some sequiential order, and the operation of each individual processor appear in this sequence in the order specified by its program. [Lamport, IEEE TOC, 1979]

이를 다시 나열해보면, 아래와 같다.
1. 프로세서 간의 실행은 특정한 순서에 의해 결정된다.
2. 하나의 프로세서 안에서의 실행은 프로그램 순서대로 수행된다.
이 두 가지를 만족하면 SC 하다고 이야기 할 수 있다.
다만, 두 가지가 만족되지 않더라도 SC한 경우도 존재한다.
아래 예시로 살펴보자.

// Shared variable
x=0; y=0; X=0; Y=0;
// Thread 0
S11 : X = x;
S12 : y = 1;
// Thread 1
S21 : Y = y;
S22 : x = 1;

// Execution order
1. S11 -> S12 -> S21 -> S22 // Result X=0, Y=1; -> SC
2. S11 -> S21 -> S12 -> S22 // Result X=0, Y=0; -> SC
3. S11 -> S21 -> S22 -> S12 // Result X=0, Y=0; -> SC
4. S11 -> S12 -> S22 -> S21 // Result X=0, Y=1; -> Unordered But SC
5. S12 -> S21 -> S22 -> S11 // Result X=1, Y=1; -> Not SC

4번의 경우 S22 -> S21이므로 프로그램 순서를 지키지 않았지만, 결과적으로 SC로 구현된 상태의 결과와 같으므로 SC라고 이야기할 수 있다. 그러나 5번의 경우, 프로그램 순서를 지키지도 않았고, 그 결과 또한 SC로 구현된 상태와 다르므로 SC라고 이야기할 수 없다.

Relaxed Memory Consistency Models은 프로그램 순서를 지키는 것을 조금 완화한 것이다. 프로그램 순서를 지키게 되면, out-of-order를 수행할 수 없으므로 성능이 떨어질 수 밖에 없다. 성능을 향상을 위해서 이 순서에 대한 규칙을 완화하여 성능을 높이고자 한다. 그 대신 정확도 측면에서 보장할 수 없기 때문에, Programmer가 이를 책임지고 관리해야 한다. Programmer는 Memory fence/barrier instruction을 활용하여 memory instruction이 순차적으로 실행되지 않는 것을 방지할 수 있다. 이 Memory fence를 사용하면, 이 instruction을 기점으로 이전 memory instruction이 모두 완료되어야 한다.
Processor Consistency는 Read to Read, Read/Wrtie to Write는 수행된 Read/Write가 다른 프로세서에 의해 보이려면 Read는 이전 Read가 모두 수행된 상태여야 하며, Write는 Read/Write 모두 수행된 상태여야 한다.  
이 때, Write to Read는 순서를 변경할 수 있도록 허용한다. 즉 먼저온 Write보다 나중에 온 Read를 먼저 수행할 수 있다. 나중에 온 Read를 처리하기 위하여 먼저 온 Write를 수행하기 전에 buffer에 담아두는 용도로 write buffer가 사용된다.  

Weak ordering은 지켜야할 Program order가 존재하지 않는다. 다만, Sychronization 동작으로 구별 한다. Synchronization 동작이 수행되려면 이전에 read/write가 모두 수행되어야하며, read/write가 수행되려면 이전 syncrhonization 동작이 모두 수행되어야 한다.

Release Consistency은 weak ordering과 같이 program order를 더 이상 지키지 않아도 되며, synchronization 동작을 2가지로 구분하여 사용한다. Acquire/Release로 lock(V)/unlock(V)로도 표현할 수 있다. Lock을 습득하고, Read/Write를 수행해야한다. 반대로 모든 Read/Write가 수행된다음 unlock을 수행해야 한다. Weak ordering에 대비 장점은 아래와 같다.
Weak ordering은 sync. inst 기점으로 구분되는 하나의 critical section이 모두 수행되어야 다음 critical section으로 넘어갈 수 있지만, Release Consistency는 Critical section 내 동작들은 section 밖에서도 독립적으로 수행될 수 있다. 즉, Lock과 Unlock 사이에서만 수행하면 되고,
1. 나머지 unlock 이후에 수행된 inst은 unlock을 기다리지 않고 자유롭게 수행가능하다. 다만, 이전 lock이 수행되지 전에는 수행할 수 없다.
2. lock을 수행할 때는 lock 이전 instruction의 수행을 기다리지 않고 수행될 수 있다.
  
OpenMP Memory Consistency은 Relaxed consistency를 가지며, 항상 스레드의 temporary memory view가 consistent 할 필요는 없다. 각 스레드 별로 temporary memory view를 가지고 있으며, flush operation을 통해서 temporary view와 memory 간의 consistency를 강제할 수 있다.