데이터 의존성

 

1. 개요
2. Input Dependency
3. Flow Dependency
4. Name Dependency
4.1. Anti Dependency
4.2. Output Dependency
5. Control Dependency
6. Memory Dependency
7. 최적화


1. 개요

데이터 의존성은 이미 수행된 데이터의 변화가 뒤의 수행 결과에 영향을 끼치는 것을 의미한다. 컴파일러 이론에서 각 구문(또는 어셈블리 인스트럭션)의 데이터 의존성을 찾아내는 것을 '의존성 분석(Dependency Analysis)'라고 한다. 데이터 의존성은 크게 flow dependency, name dependency, control dependency의 세 가지로 나눌 수 있다.
아래와 같은 수식으로 표현할 수 있다. 이 조건을 처음으로 제시한 컴퓨터 과학자 A. J. Bernstein의 이름을 따서 '번스타인 조건'이라고 한다.
$$ [I(S_1) \cap O(S_2)] \cup [I(S_1) \cap O(S_2)] \cup [O(S_1) \cap O(S_2)] \neq \phi $$
  • $$ I(S_n) $$은 구문 Sn의 메모리 읽기 연산을 의미한다.
  • $$ O(S_n) $$은 구문 Sn의 메모리 쓰기 연산을 의미한다.
  • S1이 실행되고 어느 정도의 시간이 흐른 뒤 S2가 실행된다.
기본적인 조건 네 가지를 생각해볼 수 있다.
  • $$ I(S_1) \cap I(S_2) \neq \phi $$ : Read-After-Read(RAR). 또는 Input Dependency. S2에서 특정 변수를 읽기 이전에 S1에서 해당 값을 읽는 경우.
  • $$ I(S_1) \cap O(S_2) \neq \phi $$ : Write-After-Read(WAR). 또는 Anti Dependency. S2에서 특정 변수를 쓰기 이전에 S1에서 해당 값을 읽는 경우.
  • $$ O(S_1) \cap I(S_2) \neq \phi $$ : Read-After-Write(RAW). 또는 Flow Dependency. S2에서 특정 변수를 읽기 이전에 S1에서 해당 값을 쓰는 경우.
  • $$ O(S_1) \cap O(S_2) \neq \phi $$ : Write-After-Write(WAW). 또는 Output Dependency. S2에서 특정 변수를 쓰기 이전에 S1에서 해당 값을 쓰는 경우.

2. Input Dependency

RAR Dependency. 읽기 이후 읽기가 일어나는 경우. 나중에 실행되는 연산이 이전에 실행되는 연산의 읽기 값을 읽는 경우에 발생한다.
1. A = C + 3
2. B = C + 5
위의 두 구문은 어느 구문이 먼저 수행되어도 상관없다. 단, memory-mapped I/O를 할 때에는 순서가 보장되어야 할 수도 있다.

3. Flow Dependency

RAW Dependency. 쓰기 이후 읽기가 일어나는 경우. 나중에 실행되는 연산이 이전에 실행되는 연산의 쓰기 값을 읽는 경우에 발생한다.
1. A = 3
2. B = A
3. C = B
구문 3은 구문 2에 의존적이며, 구문 2는 구문 1에 의존적이다. 즉, 구문 3은 반드시 구문 2 이후에 실행되어야 하며, 구문 2는 반드시 구문 1 이후에 실행되어야 한다. 이 의존성은 없애는 것이 불가능하여 True Dependency라고도 한다. 만일 수행 순서가 뒤바뀌면 2번, 3번 구문의 수행 결과는 틀리게 되며, 이를 '데이터 위험(Data Hazard)'이라고 한다.


4. Name Dependency

변수의 이름을 변경하거나 사본을 만들어서 회피할 수 있는 의존성을 의미한다.

4.1. Anti Dependency

WAR Dependency. 읽기 이후 쓰기가 일어나는 경우. 나중에 실행되는 연산이 이전에 실행되는 연산의 읽기 값을 쓰는 경우에 발생한다.
1. B = 3
2. A = B + 1
3. B = 7
구문 3은 구문 2에 Anti-Dependent하다. 즉, 구문 2가 수행되기 이전에 구문 3이 수행되어서는 안 된다. 수행 순서가 뒤바뀌면 A의 값이 틀리게 된다.
1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7
위와 같이 새로운 변수 B2를 추가하면(변수 리네이밍Variable Renaming) 구문 2와 구문 3은 이제 병렬 수행이 가능하다. CPU에서 위와 같은 작업을 자동으로 수행해주기도 하며 이를 '레지스터 리네이밍'이라고 한다.

4.2. Output Dependency

WAW Dependency. 쓰기 이후 쓰기가 일어나는 경우. 나중에 실행되는 연산이 이전에 실행되는 연산의 쓰기 값을 쓰는 경우에 발생한다.
1. B = 3
2. A = B + 1
3. B = 7
위의 예제에서는 구문 3이 구문 1에 의존적이다. 수행 순서가 뒤바뀌면 A의 값이 틀려지게 된다. 따라서 구문 1과 구문 3은 병렬로 수행할 수 없다.
1. B2 = 3
2. A = B2 + 1
3. B = 7
B의 이름을 B2로 바꾸면 의존성이 사라진다. 이제 구문 1과 구문 3은 병렬 수행이 가능하다. 단, memory-mapped I/O를 할 때에나 멀티스레드에서 공유하는 변수는 함부로 변수명을 바꾸면 참조하여야 할 값을 건너뛰어버리는 현상이 발생할수도 있다. 이를 방지하기 위해 volatile 키워드나, atomic 연산 등을 활용한다.

5. Control Dependency

구문 S1의 결과에 따라서 구문 S2의 수행 여부가 결정되는 상황을 의미한다.
1. if (a == b)
2.    a += b
3. b += a
위의 예제에서 구문 2는 구문 1의 결과에 따라 수행 여부가 결정된다. 반면 구문 3은 구문 1의 결과에 상관없이 항상 수행된다. 이 때 구문 2는 구문 1에 Control Dependency가 있다.

6. Memory Dependency

변수가 포인터형인 경우 데이터 의존성을 명확하게 판단할 수 없을 때가 많다.
1. *x = *y + 1
2. *a = *b + 1
위 구문 둘 사이에는 얼핏 보면 의존성이 없어 보인다. 그러나, y와 a가 같은 곳을 가리킨다면 RAW, x와 b가 같은 곳이라면 WAR, x와 a가 같은 곳이라면 WAW 의존성이 존재한다.이렇기 때문에 컴파일러나 프로세서는 포인터 구문들 사이에는 잠재적으로 의존성이 존재한다고 보고 위 두 구문을 최적화하지 않는다. 이 때문에 포인터 변수를 남용하면 컴파일러/프로세서의 최적화 기능을 상당부분 제한하게 된다. 함수에 인수로 넘어오는 두 포인터 변수 사이에 의존성이 없다는 것을 명시할 수도 있는데 이것이 C99에서 추가된 restrict 키워드이다.[1]

7. 최적화

컴파일러나 프로세서는 위의 데이터 의존성들을 자체적으로 분석하여 명령어 순서를 뒤바꾸어 실행하거나 아예 구문 자체를 없애버리기도 한다. 명령어 순서를 바꾸거나 아예 없애버림으로써 발생하는 문제를 reordering problem이라고 하며, 일부 reordering problem을 감수하고라도 좀더 강력한 최적화를 하는 것을 '공격적 최적화(aggressive optimization)'라고 한다. 반면 성능 저하를 감수하고 최적화를 덜 하는 것을 '보수적 최적화(conservative optimization)'라고 한다.
int foo = 0;

Thread 1:
while(foo == 0)
{
    /* do something */
}

Thread 2:
// terminate thread 1
foo = 1;
위와 같은 코드를 공격적으로 최적화하면 1번 스레드의 'foo == 0'은 해당 스레드에서 RAW 의존성이 없기 때문에 컴파일러는 'foo == 0' 대신 그냥 'true'를 넣어 버리기도 한다.
int foo = 0;

Thread 1:
// 최적화 결과
while(true)
{
    /* do something */
}

Thread 2:
// terminate thread 1
foo = 1;
즉 스레드 2번에서 스레드 1번을 종료시키도록 했음에도 스레드 1은 끝나지 않고 무한루프를 돌게 된다. 이것을 방지하기 위해 volatile 구문을 추가하거나 atomic 연산, 혹은 메모리 배리어 연산 등을 활용한다.
long a = 0x0000FFFF;
short *b = (short*)&a;
short c;

c = b[0];
b[0] = b[1];
b[1] = c;

printf("%X\n", a);
...
FFFF0000
위 코드는 a의 상위 16비트와 하위 16비트를 서로 바꾸는 코드이다. 그런데 b와 c는 코드 내부에 RAW 의존성이 있는 부분이 없다. 따라서 컴파일러는 b와 c의 값을 읽고 쓰는 부분을 모두 없애버릴 수 있으며 틀린 결과를 얻게 된다.(0000FFFF) 이러한 경우에는 memcpy 함수 등을 활용하거나 #pragma opt 등의 컴파일러 지시자를 이용해 최적화를 방지해야 한다.
일반적으로 공격적 최적화가 더 좋은 성능을 발휘하는 코드를 생성해 주기 때문에, 보통은 공격적으로 최적화하고 최적화를 방지해야 할 부분은 프로그래머가 직접 명시하거나 아예 어셈블리로 작성하는 방법을 사용한다.

[1] C언어의 함수 memcpy(dest, src, size)와 memmove(dest, src, size)를 생각하면 된다. memcpy는 dest와 src 사이에 겹치는 부분이 없을 때에만 사용할 수 있다. 반면 memmove는 dest와 src 영역이 겹치는 부분이 있을 수도 있다고 가정한다. 따라서 memcpy 작성시에 여러가지 최적화 기법을 사용할 수 있으며 속도도 더 빠르다. C99부터는 memcpy 함수의 프로토타입을 void* memcpy(void *'''restrict''' dest, const void *'''restrict''' src, const size_t size)인 것을 볼 수 있다. 반면 memmove의 프로토타입에는 restrict가 붙지 않는다.

분류