[컴퓨터구조#12-2] 일관성 (Consistency) - Memory Consistency, Sequential Consistency, Relaxing SC

참고: Computer Architecture: A Quantitative Approach (5th edition) - 5.6.

이번 글에서는 일관성(consistency)에 대해 알아볼 것이다.

목차

1. Consistency란?
2. Sequential consistency
3. Relaxing SC
4. Enforcing SC

---

1. Consistency란?

프로세서는 새로운 값을 언제 봐야 할까? A,B를 shared variable이라 하고 다음과 같은 상황을 생각해보자.

P1:	A = 0;	P2:	B = 0;
	....		....
	A = 1;		B = 1;
L1:	if (B==0) ...	L2:	if (A==0) ...

P1에서 L1에 도달했다는 것은, P2에서 B=1;을 아직 실행하지 않은 상태라는 것을 의미한다. 반대의 경우도 마찬가지이다. 즉 L1과 L2는 mutual exclusive하다.

만약 쓰기 invalidation이 지연되고 프로세서가 계속 실행을 지속한다고 하면 L1과 L2가 동시에 실행될 수 있을까? 이러한 ordering 문제와 관련된 이슈를 Memory consistency라 한다. Memory consistency model은 서로에 대한 모든 메모리 위치의 균일한 view를 제공한다.create uniform view of all memory locations relative to each other.

또다른 예시를 생각해보자. 프로세서 1은 두 개의 write을, 프로세서 2는 두 개의 read를 수행한다. P1을 producer, P2를 consumer라 볼 수도 있겠다.

Processor 1	Processor 2
Store (a), 10;	L:  Load r1, (flag);
Store (flag), 1;	if (r1 == 0) goto L;
	Load r2, (a);

이때 flag는 두 프로세서 간 통신을 위한 marker 역할을 한다. flag가 1이라면 a 값도 업데이트되었다는 것을 의미한다. 이는 명령어 실행이 in-order로 진행되며, load와 store가 atomic하다는 가정이 뒷받침되기 때문이다. 

Coherence vs. Consistency

그렇다면, coherence와 consistency는 어떻게 다를까?

다음 예시를 통해 생각해 보자. 초기 값은 A=flag=0이다.

Processor 0	Processor 1
A = 1;	while (!flag);
flag = 1;	print A;

직관적으로 생각해 보면 P1은 A=1의 값을 print할 것이다.

• Cache Coherence: 메모리 위치의 consistency view를 제공한다. 서로 다른 두 location에 대한 순서를 보장하지는 않는다. 각 프로세서의 두 write은, cocherence 관점에서는 독립적인 트랜잭션이다.
• Consistency: 이 코드의 작동 여부를 결정한다. 프로세서에서 겹치지 않는 주소에 대한 메모리 연산(read/write)의 효과적인 순서를 정의한다. 또한, consistency model은 ISA의 일부분이다.

 

2. Sequential Consistency

(Lamport의 정의): 모든 실행의 결과가 모든 프로세서의 연산이 일종의 sequential order로 실행된 것과 동일하고, 각 개별 프로세서의 연산이 해당 순서에서 그 프로세서의 프로그램에 의해 지정된 순서로 발생하는 경우 그 멀티프로세서는 sequentially consistency하다고 한다.

프로그래머에게 직관적인 consistency 모델은, 프로세서는 그 프로세서와 다른 프로세서들의 load와 store를 프로그램 순서대로 보게 되며, 모든 프로세서는 동일한 전역 load/store 순서를 보게 된다.

위에서 나왔던 예시를 다시 생각해보자.

이 코드가 작동할 것이라 가정하는 것은 이 시스템이 sequential consistency로 작동할 것이라 가정하는 것과 동일하다. P1의 결과(flag)에 따라 P2의 결과가 달라지기 때문에, P1,P2의 순서가 보장되는 것이기 때문이다.

Processor 1	Processor 2
Store (a), 10;	L:  Load r1, (flag);
Store (flag), 1;	if (r1 == 0) goto L;
	Load r2, (a);

그렇다면 SC는 어떻게 구현할 수 있을까?

Load-Store Reordering: Committed Store Buffers

CPU는 commit된 store가 메모리 시스템을 전파하는 중에도 실행을 계속해서 이어나갈 수 있다. 프로세서는 첫 store가 메모리에 commit하는 동안 다른 명령어(load/store 등)를 commit할 수 있다. Commited store buffer는 OoO CPU의 speculative store buffer와 합쳐져 사용될 수 있다.

store->load: 같은 주소인 경우, 나중 load는 메모리에 접근하지 않고 이전 store의 값을 committed store buffer에서 읽어오면 되고, 다른 주소인 경우 load는 (성능을 위해) committed store buffer를 bypass해서 실행된다.

load->store: load는 항상 store 전에 실행되므로 크게 고려할 사항 아님.

예시) 초기값은 모두 0

Processor 1	Processor 2
Store (flag_1), 1;	Store (flag_2), 1;
Load r1, (flag_2);	Load r2, (flag_1);

• SC만으로는, r1=0과 r2=0가 동시에 발생하는 것은 불가능하다.
• Store Buffer를 사용하는 경우, Load가 store buffer에 있는 store보다 먼저 실행될 수 있으므로 r1=0, r2=0 동시에 가능

Store-Store Reordering: Non-blocking Caches

예시) 초기값은 모두 0

Processor 1	Processor 2
Store (a), 1;	Load r1, (flag);
Store (flag), 1;	Load r2, (a);

• SC만으로는, r1=0과 r2=0가 동시에 발생하는 것은 불가능하다.
• Store 순서를 바꿀 수 있따면, load의 reordering이 가능하므로 r1=0, r2=0이 동시에 가능하다.

Load-Load Reordering: Speculative Execution

예시) 초기값은 모두 0

Processor 1	Processor 2
Store (a), 1;	L: Load r1, (flag);
Store (flag), 1;	if (r1==0) goto L;
	Load r2, (a);

• SC만으로는, r1=0과 r2=0가 동시에 발생하는 것은 불가능하다.
• Speculative load가 있다면 store의 순서가 정해져 있더라도 r1=0, r2=0 가능하다.

 

3. Relaxing SC

Sequential Consistency는 이해하기 쉽지만, 높은 성능 cost를 가진다. 또한, 대부분의 프로그램은 동기화되어 있기 때문에 대부분의 현재 시스템들은 SC를 relax해서 사용한다. Relaxed model은 서로 다른 주소에 대한 RAW, WAR, RAW, WAW를 대하는 방식에서 달라진다.

핵심 아이디어는, read와 write가 OoO로 실행될 수 있도록 허용하지만 순서를 강제하기 위해 동기화 연산을 사용함으로써 프로세서가 sequentially consistent인 것처럼 동기화된 프로그램이 행동하는 것이다.

• 순서를 relaxing함으로써 성능 이득을 얻을 수 있다.
• 공유 데이터에 대한 컴파일러 최적화의 정도를 명시한다.
• 동기화 포인트가 명확히 정의되고 프로그램이 동기화되어있지 않는 한, 컴파일러는 2개의 공유 데이터 item에 대한 읽기와 쓰기를 교환할 수 없다. (프로그램 semantic에 영향을 줄 수 있으므로)

완화 순서에 대한 기본 집합은 다음과 같다.

1. W → R ordering: 모든 쓰기는 다음 읽기 전 완료된다.
   • 쓰기 간 순서를 유지하기 때문에, sequential consistency 하에서 작동하는 많은 프로그램은 추가적인 동기화 없이 이 모델에서 작동함. processor consistency라고도 함.
2. W → W ordering: 모든 쓰기는 다음 쓰기 전 완료된다.
3. R → W and R → R ordering: 많은 모델이 이 제한 순서와 어떻게 동기화 연산의 순서를 강제하는지에 따라 달라짐.

⇒ 완화된 SC에는 많은 복잡성이 존재한다. 쓰기과 완료된다는 것이 정확히 무엇을 의미하는지 정의해야 하고, write된 값을 프로세서들이 언제 볼 수 있는지 정해야 함.

Relaxed Consistency Models

크게 두 종류가 있다.

Processor Consistency (PC)	Weak ordering (WO)
W → R ordering만 relax	모든 ordering을 relax
하지만 W → W, R → W, R → R ordering도 지원함.
Intel / AMD x86, SPARC 등 in-order write buffer 허용 프로그래머를 헷갈리게 하지 않음	Alpha, Itanium, ARM, PowerPC 등 ordering이 꼭 필요한 경우 memory fence instruction 사용 동기화 라이브러리 사용

Weaker Memory Models

load와 store의 reordering을 예방하기 위해 다음과 같이 memory fence 명령어를 사용한다.

Store	(a1), r2;
Fence_wr;
Load	r1, (a2);

• 만약 a1 != a2라면, load와 store는 reorder될 수 있다. Fence_wr 명령어는 이러한 재정렬을 막는다. (-> OoO 성능 저하)
• 비슷하게, Fence_rr, Fence_rw, Fence_ww가 존재한다.
• 동기화와 관련된 이전 글에서 나왔던 atomic exchange 명령어 (exch)에도 이러한 barrier semantic이 포함되어 있어, 나머지 메모리 연산이 issue되기 전에 exch가 완료된다.

Fence를 사용하는 경우, 다음 예시가

Processor 1	Processor 2
Store (a), 1;	L: Load r1, (flag);
Store (flag), 1;	if (r1==0) goto L;
	Load r2, (a);

아래와 같이 수정되어 각 명령어의 순서를 강제할 수 있다. (Fence_ww: 두 store간의 순서 보장, Fence_rr: 두 load 간의 순서 보장)

Processor 1	Processor 2
Store (a), 1;	L: Load r1, (flag);
Fence_ww;	if (r1==0) goto L;
Store (flag), 1;	Fence_rr;
	Load r2, (a);

 

4. Enforcing SC

Sequential Consistency를 강제하는 것은, 모든 load와 store가 globally ordered되도록 하는 것이다. 모든 load와 store의 순서를 정하기 위해 coherence event의 순서를 활용한다.

coherence event는, 각 캐시 접근에서 발생하며 메모리 연산별로 다음과 같은 특징을 가진다.

• store: commit되는 경우 (in-order)
• load: 실행되는 경우 (out-of-order일 수 있음)

즉, load가 OoO로 실행되는 경우가 tricky하며 이를 다룰 수 있는 방법이 필요하다.

Enforcing SC with Out-of-Order

speculative execution을 떠올려 보자. 이전 store 주소가 알려지지 않았을 때도, load는 speculative 하게 실행이 가능했다. 순서 위반이 발생하면 파이프라인을 flush하고 load를 재시작했다.

OoO load를 가진 SC를 지원하기 위해서도 이와 비슷한 방법을 사용한다. 다른 프로세서에서 온 invalidation 은 in-flight load를 snoop한다. 만약 invalidation이 가장 오래된 명령어가 아니면서 완료된 load와 hit한다면, flush하고 load를 재시작한다. 이는 in-order commit으로 프로그램 순서를 보존하고, 메모리가 load 실행과 commit 사이에 업데이트되지 않으며, 변했다면 sequential consistency 위반이므로 flush & restart를 한다는 점에서 순서를 올바르게 강제할 수 있는 것이다.

예시를 통해 살펴보자.

A=0, B=0에서 각 프로세서가 다음과 같은 연산을 한다고 가정하자.

Processor 0	Processor 1
read A	B = 1
read B	A = 1

SC가 보장되는 경우, P0이 읽을 수 있는 가능한 (A,B)의 종류는 (0,0), (1,1)이다.

하지만 read가 out-of-order로 실행되는 경우 이러한 SC를 위반하게 될 수 있다. 다음과 같은 상황에서는 A=1, B=0이 가능하다. 이는 Sequential consistency에 위배된다.

Processor 0	Processor 1
exec read B // out-of-order
	B = 1
	A = 1
exec read A // out-of-order

이를 해결하기 위해, invalidation을 보내고(=misspeculative execution으로 표시) load hit인 경우 flush&restart 하는 방법을 사용한다. 따라서 이 방식을 사용하면 read가 out-of-order로 실행되더라도 sequential consistency를 만족할 수 있는 올바른 순서로 실행될 수 있다.

Processor 0	Processor 1
exec read B // out-of-order
	B = 1
	send invlidation for B
receive invalidation for B → sqush read B and younger instructions
	A = 1
exec read A
exec read B // re-execution after flush

 

x86 consistency relaxation 정리

W → R	relax
W → W	성능에 크게 영향 주지 않고 쉽게 구현 가능	write은 CPU 실행의 critical path에 있지 않음 write은 in-order로 시스템에 propagate됨.
R → W		read는 항상 write 이전에 실행된 write은 commite된 이후에만 메모리를 업데이트.
R → R	성능 저하를 일으킬 수 있음	speculative technique으로 reorder
	* misspeculative인 read를 결정하는 방법 1) invalidation 요청이 들어오면 해당 주소를 LQ에 있는 모든 이전의 load와 비교 2) matching load가 있는 경우(즉, 이전 load가 그 memory에서 value 얻은 경우 => conflict), 3-1) 그 load가 LSQ/ROB의 head가 아니라면(not the oldest) misspeculative로 결정 & invalidation 메시지 받아들이고 re-execute 3-2) 그 load가 oldest 명령어라면 not misspeculative

 

 

Aggressive SC 구현

load는 speculatively & OoO로 완료될 수 있음.

Processor 1	Processor 2
Load r1, (flag); -> miss	Store (a), 10;
Load r2, (a); -> hit

만약 Load r1이 miss고 Load r2가 hit이라고 해보자. => Store(a)가 Load(flag)의 커밋 이전에 커밋된다면 Load (a)와 그 이후의 명령어들을 kill.

이러한 확인 절차를 구현하려면, 커밋될 때 값이 바뀌는지 보기 위해 speculative load를 재실행하거나, 각 incoming cache invalidate에 대해 speculative Load queue를 확인한다. 하지만 구현하기에 복잡하고, waekr memoroy model(fence 사용)만큼 효율적이지도 않다.

 

보통, 실제 프로그래머들은 SC에 의존하는 대신 lock, semaphore, monitors 같은 high level의 동기화 primitive를 활용한다. 잘 동기화된 프로그램에서는 각 공유된 writable variable이 보호받으며, 변수 업데이트 시 race condition이 없어야 한다. high-level의 병렬 프로그래밍은 memory consistency 모델을 생각하지 않고, 동기화에는 high level primitive 정도만 고려하면 된다.