[Parallel Computing] (15) Cache Coherence

Coherence은 우리말로 표현하면 '통일성/일관성'이라 표현될 수 있으며, 영영 사전에 의하면 'the situation when the parts of something fit together in a natural or reasonable way'으로 설명하기도한다. 두 표현이 공통적으로 말하는 것은 어떤 것에 대해 일관적이고,  타당한 방식으로 어떤 것들이 함께 존재한다는 점이다.
그렇다면 Cache Coherence는 어떤 의미일까? 위의 표현 중 어떤 것이 Cache 라고 생각하면 아래와 같이 다시 표현할 수 있다.  
> Cache에 대해 일관적이고,  타당한 방식으로 Cache들이 함께 존재한다는 점이다.
그렇다면 어떤 관점에서 Cache가 일관적이고, Cache들이 타당한 방식으로 존재한다는 것일까?
바로 Cache 내에 존재하는 데이터를 바라보는 관점이다.
즉, 여러 Cache 내에 동일한 주소의 데이터를 가지고 있을 때, 해당 데이터가 일관적으로 존재한다는 것을 말한다.
그런데 이 개념이 새로운 것이 아니라 우리가 일반적으로 프로그램을 수행할 때 기대하는 것이다. 우리는 여러 프로세서들이 동일한 테스크를 수행할 때, 각 프로세서가 최신의 데이터를 가지고, 테스크를 수행하기 기대하고 있다.
  이제 개념적인 측면에서 컴퓨터 구조로 넘어가보자.
일반적으로 각 프로세서들은 각자의 캐쉬를 가지고 있고, 공통된 메모리를 사용한다. 그리고 메모리 접근 속도를 감추기 위하여 각 프로세서들은 각자의 Cache를 가지고 있다. 이 때, 서로 다른 프로세서가 동일 주소의 데이터를 각자의 Cache에 올려두고 사용할 때, 데이터의 일관성(Coherence)은 어떻게 보존될 수 있을 까?  
이를 수행할 수 있는 방법에는 여러 가지가 있지만, 해당 포스트에서는 Cache Coherence를 설명하기 위하여 간단한 방식인 Invalidation protocol를 사용하겠다.
두 개의 Processor(P1, P2)가 각자의 Cache를 가지고 있고, 주소 A를 접근하는 상황을 가정하자.
이 때, Cache 정책은 Write Back, Write allocation 방식을 사용한다고 가정하자.
*Write Back         :: Cache Evitcion 될 때, Memory에 업데이트 수행.
*Write allocaton :: Write 수행 시, Cache에 올려두고 수행.

아래와 같이 동작이 발생할 때, 메모리(M) A 값과 Cache(C) A값이 어떻게 변하는 지 살펴보자.
(최신 값은 빨간색으로 표현하겠다.)
0. Initialization          ||  M[A] :: 10, P1_C[A] :: Not Valid, P2_C[A] :: Not Valid
1. P1 Read A             ||  M[A] :: 10, P1_C[A] :: 10,              P2_C[A] :: Not Valid
2. P2 Write A -> 20  ||  M[A] :: 10, P1_C[A] :: 10,              P2_C[A] :: 20

2번까지 수행했을 때, 최신 값은 20이지만, P1의 Cache와 Memory에는 이전 값인 10이 저장되어 있다. 이 상황에서 P1이 이 데이터를 사용한다면 이전 값인 10을 사용하므로 Cache coherence가 유지될 수 없다. P1이 최신 값을 사용하려면 어떻게 해야할 까?
최신 값을 가지고 있는 P2가 P1에서 자신이 최신 데이터를 가지고 있다고 알리는 것이다. P1은 이 정보를 가지고 자신이 가지고 있는 데이터가 Invalid 하다는 것을 알고, 더이상 사용하지 않는다.
이 때, P1의 A 주소에 접근하면 Cache miss가 발생하는 데, 이를 Coherence로 인한 Miss이기 때문에, Coherence miss라 부른다.  
그런데, P1이 다시 A주소의 데이터를 가져오더라도 메모리에는 최신 데이터가 없기 때문에, 또 다시 문제가 발생한다. 이를 해결하려면 P2가 정보를 보낼 때, 최신 데이터를 같이 보내야 한다. 그렇게 되면 P1은 Invalidation을 수행하지 않고, 최신 데이터로 업데이트하여 사용하면 된다.
위의 예제에서는 두 개의 프로세서들만 있었고, 하나의 주소에 대해서만 업데이트가 발생했지만, 여러 프로세서들이 존재하고, 여러 주소의 데이터가 업데이트 되면, Cache coherence를 지키기 위해서 발생하는 Request들이 많아 질 수 있다. 어떻게 효율적으로 수행 할 수 있을 지에 대한 여러 방법들(Snoopy and directory-based protocols//MSI, MESI, MOESI)이 존재하는데, 이 포스트에서는 다루지 않겠다.
다만, 각 프로세서들이 각자의 Cache를 가지고 있기 때문에 이런 문제가 발생하는데, Cache를 각자 가지고 있지 않고, 공유해서 사용한다면 이런 문제는 해결된다.
또한, Write back을 사용하지 않고, Write through를 사용한다면, Write를 수행할 때마다 Memory에는 최신 데이터가 존재한다. 그러므로 위의 예제로 따지면 P2는 P1의 Cache를 Invalidaton만 수행하고, 최신 데이터는 전송하지 않는다. P1이 Coherence miss가 발생하면, 메모리로부터 최신 데이터를 가져올 수 있다.
여기서 각 부분에서 데이터를 처리하는 단위를 살펴보자. Cache는 일반적으로 Cacheline 단위인 64B로 데이터를 처리하고, 메모리도 마찬가지이다. 그런데 프로세서는 변수의 크기에 따라 1B, 2B, 4B 등 다양한 크기로 데이터를 처리한다. 만약 동일한 Cacheline에서 서로 다른 프로세서가 서로 다른 데이터를 사용하면 어떻게 될 것인가?
위의 예제를 다시 가져와보자. A 주소의 데이터를 2개로 나누고 각 프로세서가 이를 사용해보자.
0. Initialization          ||  M[A] :: {11, 22}, P1_C[A] :: Not Valid, P2_C[A] :: Not Valid
1. P1 Read A             ||  M[A] :: {11, 22}, P1_C[A] :: {11, 22}   , P2_C[A] :: Not Valid
2. P2 Write A-> 33   ||  M[A] :: {11, 22},  P1_C[A] :: {11, 22}  ,  P2_C[A] :: {11, 33}

P1은 '11' 데이터를  사용하고, P2는 '22' 데이터를 사용한다.  그런데, P2가 '22'를 '33'으로 업데이트를 수행하였다. P1은 '33'이라는 데이터를 사용하지 않으므로, 업데이트를 할 필요가 없다. 그렇지만, Cacheline 대로 처리를 수행하기 때문에 P1의 데이터를 다시 업데이트해야 한다. 이와 같이  사용하지 않는 영역 때문에 업데이트를 계속 수행해야하는 문제를 False sharing이라고 한다. False sharing을 방지하려면, 하나의 Cacheline에 하나의 프로세서만 접근하도록 해야한다. 데이터가 Cacheline보다 작을 경우, Cacheline에 맞게 패딩을 하여 사용할 수도 있다.