Memory Consistency Model

Memory (Consistency) Model 이란

A formal specification of how the memory system will appear to the programmer, eliminating the gap between the behavior expected by the programmer and the actual behavior supported by a system.” [Adve’ 1995] 

Multiple threads program에서 shared data가 어떻게 작동할 지에 대한 명세. Memory consistency model에 따라 (완벽히 squential할 것인가? relaxed한 memory consistency를 허용할 것인가 등) multiple threads간 공유된 데이터의 consistency 보장이 달라짐

 

 

 

왜 필요한가?

여러 thread들 간에 공유된 데이터가 consistently 보이는가에 대한 얘기 -> 즉 multiple threads program이 문제

프로그램은 컴파일러와 하드웨어에 의해 성능을 위해 코드가 최적화됨. 이때 instruction 실행 순서가 바뀌는 최적화가 발생할 수 있음 (ex. instruction re-ordering, out-of-order excution, write buffer).

이때 당연히 코드 내 data, control dependence를 고려하여 instruction 실행 순서가 결정되기에 single thread에서는 프로그래머의 의도에서 벗어난 프로그램 작동이 일어나지 않음

문제는 multiple threads에 의해 여러 program instances (또는 instruction steams)가 실행될 때임. Program instances는 interleaving하게 실행되기에 다른 instruction streams 끼리는 data dependence를 확인할 수 없음

 

문제 상황) 두 프로세스가 돌아가는 예제

 

위 예제에서 사용자의 의도는 Z=10이 되는 것임.

하지만 P1 program instance에서는 X, Y가 서로 dependence가 없기 때문에 instruction re-ordering될 수 있고, 그에 따라 P1에서 X-write (X=2) 가 Y-write (Y=10) 보다 먼저 일어날 수 있음

만약 X-write -> X-read (while문) -> Z-write (Z=Y) -> Y-write 순으로 instruction이 실행된다면 Z는 의도와 달리 0이 될 수 있음

 

 

 

Memory coherence vs. Memory consistency

둘 다 multiple threads가 communication (i.e. shared data 사용) 하기 때문에 고려해야 함. 이때 두 개념은 다음과 같은 차이가 있음

• Memory coherence
  • 하나의 데이터에 대하여 일관성을 유지하는 것
  • 예) 일반적인 multi-core cpu 컴퓨터에서 하나의 데이터는 여러 CPU core들의 cache들에 복제되어 저장됨. 한 cache에 저장된 데이터를 읽고 쓰기 할 시, 다른 cache에 저장된 데이터도 일관성을 유지하기 위한 방법
• Memory consistency
  • 다른 데이터들끼리의 일관성 유지를 목표로, 허용되는 memory operations (i.e. store and load) ordering 정의
  • 예) Sequential memory consistency가 있음

 

 

Sequential memory consistency

구체적인 정의는 다음과 같음

1. The operations of all processes were executed in some sequential order (atomicity requirement), and
2. The operations of each individual processor appear in this sequence in the order specified by the program (program order requirement)

즉, sequential memory consistency는 [X-Write -> Y-Read] (WAR), [X-Read -> Y-Write] (RAW), [X-Read -> Y-Read] (RAR), [X-Write -> Y-Write] (WAW)의 모든 메모리 operations의 순서를 지키도록 강제함. 이때 중요한 것은 X, Y가 다른 memory address라는 것. Data dependence가 없기에 re-ordering이 가능한데 이것을 불가능하게 함. 

• 장점: 프로그래머의 의도대로 쉽게 프로그램을 구현할 수 있음 (프로그램의 복잡도 감소)
• 단점: 프로그램 실행 성능 감소

이때 atomicity requirement는 한 memory operatoin이 atomically 실행된다 -> 즉 한 memory operation이 완전히 끝나야 다음 memory operation이 가능하고, 그 operation의 결과는 끝나자마자 모든 프로세서가 알게 됨.

많은 책에서 다음과 같은 비유를 드는데 매우 좋은 것 같음.

 

출처 spcl.inf.ethz.ch

 

1) 모든 thread들은 한번에 하나씩만 memory에 접근할 수 있으며 그 결과는 다른 threads가 바로 알게 됨 (이때 process가 접근하는 순서는 강제되지 않음 -> 전체적으로 sequential order만 형성하면 됨)

2) 또한, 한 thread 내에서 memory operation들은 program order (프로그래머가 작성한 그대로) 실행됨

 

 

 

CUDA

cuda의 경우 weakly-ordered memory model을 사용

 

John Cheng, Max Grossman, Ty McKercher. Professional CUDA C Programming