Cache State-Transition Diagram (MSI)

 

 

 

성균관대학교 조형민 교수님 "컴퓨터구조설계특론" 수업을 바탕으로 만들었습니다.

저번에 multi-core환경에서 Cache Coherence에 대해서 알아봤습니다. 이번에는 Cache Coherence를 유지할 때 자주쓰이는 MSI에 대해 알아보도록 하죠.

여러분들은 Finite State Machine (FSM)에 대해 아시나요? Finite State Machine이란 어떠한 고유한 특징을 가지는 유한한 개수의 상태(State)가 있는데 어떤 조건에 의하여 서로간의 상태가 이동될 수 있는 state들을 말합니다.

---

MSI는 "Modified", "Shared", "Invalid"라는 세 가지 State로 구성되어 있습니다. 어떤 processor의 cache가 다른 processor의 cache와 서로 공유된 상태를 "Shared", cache line을 바꿔야 한다면 "Modified", 다른 processor의 cache line이 변경되기 위하여, 같은 address를 가진 cache line을 사용하지 못하도록 만드는 "Iinvalid가 있죠.

(정확한 예시는 이전 블로그에 있습니다. ) [ https://johnkims2.tistory.com/8 ]

MSI protocol

위가 MSI protocol의 예시입니다. 각 state에 있을 때 이동하는 조건이 만족된다면 state는 바뀌게 됩니다. 각 state는 의미하는 바가 다르며, 특징이 다릅니다.

예시를 차근차근 들어보겠습니다.

여기 두개의 processor가 있습니다. 위는 동일한 cache line을 read/write한다고 가정합니다.

P1(processor 1)이 cache가 read를 할 때, S를 가집니다.

그다음 P1이 write하고 싶다면 cache line을 수정해야하니 M으로 이동하게 됩니다.

이 때, P2가 동일한 cache line을 읽고 싶어한다면, P1은 M에서 S로 변경됩니다. 그리고 P2는 S를 가지게 되죠.

이로써 P1과 P2는 둘다 S를 가지게 되었습니다.

이 때, P2가 write를 하고 싶다면 먼저 P1의 state를 S에서 I로 변경합니다. Invalid를 해서 해당 cache line을 사용하지 말겠다고 선언해야지 write를 할 수 있습니다.

P2가 수정되어야 하니 M으로 이동하게 됩니다.

그 다음, P2가 read를 한다면, I에서 S로 이동시켜줍니다. 이런식으로 P1과 P2간의 동일한 cache line에 대해서 수정(write)이 있다면 다른 processor의 cache line을 invalid로 만들어 해당 cache line을 쓰지 않게 만들고 (Invalid하지 않으면, 수정되기 전의 value를 사용하는 것이기 때문에 processor가 원하는 결과로 돌아가지 않거나 성능이 매우 떨어지게 됩니다.) cache coherence를 유지합니다.

• M state에 있을 경우, 다른 cache가 동일한 cache line을 가져서는 안됩니다. 즉, 순간적으로나마 동일한 cache line에 대해서 M과 S가 공존해서는 절대로 안됩니다. (cache coherence가 깨집니다.)

하지만 MSI protocol에 문제가 있다면, write하여 수정한 cache line을 다른 processor가 access할 때, memory를 꼭 거쳐서 가져와야한다는 것입니다.  memory에서 data를 가져오는 것보다, 다른 processor의 cache에서 가져오는 것이 훨씬 더 energy efficient하기 때문에, 불필요한 memory access를 하지 말아야합니다.

이를 위해서 나온 것이 MESI입니다. MSI에 "E" state를 추가한 것이죠.  이는 내용이 길어서, 다음 블로그에 자세히 설명하도록 하겠습니다.