Egloos | Log-in
F/OSS study
F/OSS study
Shared memory consistency models
shared memory multiprocessor system에서는 각 processor들이 변경한 데이터를
다른 processor들이 올바로(consistent하게) 접근하도록 보장해 주어야 한다.
특히나 distributed shared memory system에서는 각 메모리 노드에 대한 접근 시간이 달라지므로
이러한 작업이 무척 복잡해 질 수 있다.
따라서 이를 제공하는 정도와 방법에 따라 여러 consistency model이 존재한다.

먼저 확인해야 할 사항은
memory consistency는 processor가 program을 실행할 때
서로 다른 영역에 대한 메모리 접근 순서(ordering)를 제어한다는 것이다.
동일한 메모리 영역에 대한 접근은 반드시 순서대로 이루어져야 한다. (serialize)

물론 memory consistency를 보장하는 가장 간단한 방법은
각 processor의 메모리 접근을 순서대로 atomic하게 처리하는 것이다.
하지만 이는 (memory latency로 인해) processor의 성능에 심각한 영향을 미치게 된다.

strict consistency model
어떠한 상황에서도(?) 특정 메모리 영역에 대한 read가 가장 최근에 write된 값을 읽도록 보장한다.
즉 processor1 (이하 P1)이 X에 write할 때 P2가 (동시에) Y를 write했고
P1이 Y를 read했다면 P1은 P2가 write한 값을 읽게 된다.

sequential consistency model
한 processor에서 메모리에 접근하는 것은 순서대로 이루어지지만
다른 processor에서 메모리에 접근하는 순서는 임의로 처리될 수도 있다.
이 경우 processor1 (이하 P1)이 X에 write할 때 P2가 (동시에) Y를 write했고
P1이 Y를 read했다면 P1은 P2가 write한 값을 읽는다고 보장할 수 없다.
하지만P1이 X에 write한 후 Y에 write했다면 P2에서 Y를 확인한 후에 X를 read하는 것은 안전하다.
(P1이 X에 올바로 write했음을 보장한다.)
sequential consistency model은 program의 실행에 영향을 미치지 않기 때문에
이후의 memory consistency model의 동작에 reference 역할을 하게 된다.

memory consistency를 설명할 때 매번 등장하는 예제를 살펴보자.
int A = 0, B = 0, C = 0;

/* P1 */
A = 1;
if (B == 0)
  C = A;

/* P2 */
B = 2;
if (A == 0)
  C = B;

P1와 P2는 동시에 위의 코드를 실행하는 중이라고 가정하자.
(두 processor는 모두 C의 값을 변경하려고 하므로 race condition이 발생할 여지가 있다.
여기서는 C가 최대 1번만 write되어야 한다고 가정하자.)

먼저 strict consistency model이라면
P1은 A를 write한 후에 P2가 B를 write하고 (경우에 따라 동시에 실행될 수도 있다.)
P1은 B를 read하는데 B의 값이 0이 아니므로 C를 write하지 않는다.
마찬가지로 P2도 A를 read하고 0이 아니므로 C를 write하지 않는다.

sequential consistency model이라면
P1이 B를 read하는 시점에서  P2가 B를 write하지 않았을수도 있으므로 이 경우 C는 A의 값인 1로 write될 것이다.
P1 대신 P2가 먼저 실행되더라도 C는 2로 write되겠지만, 두번 write되는 상황은 발생할 수 없다.

이러한 model을 이용한다면 consistency는 보장되겠지만
instruction scheduling이 거의 불가능해지므로 ILP를 높일 수 없어 실행 성능은 매우 나빠질 것이다.
그리하여 메모리 접근 순서 변경을 지원하는 relaxed consistency model을 도입하게 되었다.
이는 크게 다음과 같은 세 가지로 나누어진다.
  • relaxed W -> R ordeing : total store ordering (SPARC v8), processor ordering
  • relaxed W -> W ordering : partial store ordering (SPARC v8)
  • relaxed R -> R/W ordering : weak ordering, release oridering, relaxed memory ordering (SPARC v9), Alpha, PowerPC
relaxed W -> R ordering
write 간의 순서를 보장하는 방법으로 write 후의 read를 먼저 실행할 수 있다.
(단 read끼리는 순서대로 실행되어야 한다.)
이 model은 일반적인 경우 sequential consistency model과 동일한 결과를 얻을 수 있지만
data race가 발생하는 경우에는 synchronization이 필요해진다.
즉 위의 예제에서 P1은 A를 write하기 전에 B를 먼저 read할 수 있다.
마찬가지로 P2도 B를 write하기 전에 A를 read할 수 있으므로 C는 두 번 write될 수 있다!!

processor consistency model은 relaxed W -> R ordering이지만
다른 processor의 write가 완료되기 전에 일부 processor에서 read가 가능하다는 점이 다르다.
(즉 write atomicity를 보장하지 않는다.
예를 들어 P1이 X에 write를 한 후에 P2는 P1이 write한 값을 읽지만 P3는 write하기 전의 값을 읽을 수도 있다.)

이러한 consistency model에서 write가 read보다 먼저 실행되도록 보장하려면 (synchronize)
read를 read-modify-write instruction으로 변경해야 한다. (dummy write)
(또한 이 방법은 write atomicity도 보장해 준다.)

relaxed W -> W ordering
relaxed W -> R ordering을 포함하며 write 후의 write도 먼저 실행할 수 있다.
이는 (유일하게) SPARC v8의 PSO model에 해당하며
write 간의 순서를 보장하기 위해 STBAR (store barrier) instruction을 이용할 수 있다.

relaxed R -> R/W ordering
위의 두 ordering model을 포함하기 때문에 ordering의 제약이 전혀 없다.
때문에 static/dynamic instruction scheduling을 활용하여 최대의 ILP를 활용할 수 있다.
Alpha, Power PC, SPARC v9 RMO 등에서 이 model을 이용하며
명시적인 synchronization을 위해 여러 barrier/fench/sync instruction들을 지원한다.
(x86의 memory consistency model도 여기에 속하지만 W -> W ordering은 relax하지 않는다고 알고 있다.)

weak consistency model은 relax R -> R/W ordering이며
메모리 접근을 data operation과 synchronization operation의 두 종류로 나눈다.
sync. operation들은 원래의 program 순서대로 실행되며
data operation의 경우는 임의의 순서로 실행되지만 sync. operation을 넘어갈 수는 없다.

release consistency model은 weak consistency model보다 더 세분화하여
메모리 접근을 shared, special (competing), sync, acquire/release로 나눈다.
acquire/release operation은 특정 메모리 영역의 lock을 구현하는데 사용한다.

다음은 이들의 특징을 정리한 표이다.
(safety net은 메모리 접근 순서를 보장하기 위한 기법을 말한다.)



=== NOTE ===
이 글은 CA:AQA3를 보는 중 memory consistency model에 대한 개념이 잘 정리가 되질 않아서
몇 가지 자료들을 찾아본 후 내 나름대로 요약해 본 글이다.
혹시나 내용에 오류가 있을 수도 있으니 이를 발견하면 지체없이 알려주시면 감사하겠다..

=== 참고 문서 ===
by namhyung | 2009/10/14 19:20 | General | 트랙백 | 덧글(2)
트랙백 주소 : http://studyfoss.egloos.com/tb/5141402
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Commented by 물꼬기 at 2009/12/01 11:37
쉬운 설명 감사합니다.
Commented by namhyung at 2009/12/01 19:09
조금이라도 도움이 되셨길 바랍니다..

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
blktrace emacs vcs script patch awk build synchronization perf glibc documentation scm elf C SMP algorithm gcc block-layer computer-architecture x86 git CARM bash binutils linux compiler memory CAaQA3 kernel sed
전체보기
이글루 파인더

최근 등록된 덧글
1번은 call-stack 금방 확인이 ..
by 혁 at 11/13
해당 문법에 대한 자세한 가이드 같..
by ㅇㄷㅎ at 11/07
perf에 대한 설명 감사드립니다! ..
by flavono123 at 10/24
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X