CPU 설계, 그 첫 번째 이야기 | 데이터 의존성
2명의 계산원, 철수와 영희가 있다고 하자. 한 작업은 한 명이 수행하며, 한 계산원은 두 작업을 동시에 수행할 수 없다. 철수와 영희는 주어진 계산을 최대한 빠르게 수행하고자 한다.
여기 순서대로 3개의 작업이 들어왔다.
- 10*20을 계산하시오 (1초 소요)
- 797*3874를 계산하시오. (10초 소요)
- 1+2를 계산하시오. (2초 소요)
가장 빠르게 해결하려면 어떻게 해야 할까? 1-철수, 2-영희, 3-철수 순서로 작업하면 된다. 철수가 1번, 3번 작업을 미리 하는 사이 영희가 2번 작업을 수행하면 되기 때문. 이 경우 걸리는 시간은 10초다. 1, 2, 3번 작업의 순서가 상관 없기 때문이다.
다른 작업이 들어왔다.
- 10*20을 계산하시오 (1초 소요)
- 797*3874를 계산하시오. (10초 소요)
- 1.의 답과 2.의 답의 합을 구하시오. (2초 소요)
이 경우 걸리는 시간은 최소 12초다. 3번 작업을 하려면 1, 2번 작업이 모두 완료되어야 하기 때문이다. 설령 철수가 1번 작업을 1초만에 끝냈더라도, 3번 작업에 2번의 결과를 요구하므로 9초를 더 기다려야 하는 것이다.
데이터 의존성
데이터 의존성은 여러 작업 간에 선행관계를 나타낸다. 데이터 의존성은 크게 flow dependency, name dependency, control dependency로 구분할 수 있다.
조금 더 구체적으로, 데이터 의존성은 아래와 같이 나타낼 수 있다. 컴퓨터 과학자 A. J. Bernstein의 이름을 따서 '번스타인 조건'(Bernstein Condition)이라고 한다.
$$[I(S_1) \cap O(S_2)] \cup [O(S_1) \cap I(S_2)] \cup [O(S_1) \cap O(S_2)] \neq \varnothing$$
- $I(S_n)$은 구문 $S_n$이 읽는 메모리의 집합이며
- $O(S_n)$은 구문 $S_n$이 쓰는 메모리의 집합이다.
이때, $S_1$이 실행되고 어느 정도의 시간이 흐른 뒤 $S_2$가 실행된다. 즉, 이전 연산이 완벽하게 실행된 후 다음 연산이 실행된다.
따라서, Bernstein 조건이 성립하지 않는 경우는 세 유형으로 분류할 수 있다.
- Anti Dependence(Write-After-Read): $[I(S_1) \cap O(S_2)] \neq \varnothing$, $S_2$에서 특정 값을 쓰기 전 $S_1$에서 해당 값을 읽는 경우
- Flow Dependence(Read-After-Write): $[O(S_1) \cap I(S_2)] \neq \varnothing$, $S_2$에서 특정 값을 읽기 전 $S_1$에서 해당 값을 쓰는 경우
- Output Dependence(Write-After-Write): $[O(S_1) \cap O(S_2)] \neq \varnothing$, $S_2$에서 특정 값을 쓰기 전 $S_1$에서 해당 값을 쓰는 경우
- Input Dependence(Read-After-Read): $[I(S_1) \cap I(S_2)] \neq \varnothing$, 일반적으로 종속관계가 없다.
더 자세한 예시를 들어 보자.
Input Dependency
읽기 이후에 다시 읽기 연산이 일어나는 경우다.
1. A = C + 1
2. B = C + 2
위 두 구문의 순서는 일반적인 경우 상관이 없다. 그러나 Memory-Mapped I/O와 같이 읽기 연산이 그 값을 바꾸거나 다음 값을 가져오는 경우 순서 의존성이 있다.
Flow Dependency
쓰기 이후에 읽기 연산이 일어나는 경우다.
1. A = 1
2. B = A
3. C = B구문 2는 구문 1에, 구문 3은 구문 2에 의존적이다. 이 경우처럼 제거할 수 없는 의존성을 True Dependency라고 부르며 Instruction-Level 병렬 연산을 불가능하다.
Anti Dependency
읽기 이후에 쓰기 연산이 일어나는 경우다.
1. A = 1
2. B = A + 1
3. A = 3구문 2와 구문 3을 바꾸면 그 결과 또한 달라진다. A에 대한 읽기 연산과 쓰기 연산이 모두 포함되어 있기 때문이다.
1. A = 1
#. C = A
2. B = C + 1
3. A = 3종속성을 제거하기 위해 # 구문을 추가할 수 있다. CPU가 이러한 Register Renaming 작업을 자동으로 수행하기도 하며, 이제 구문 2와 구문 3을 병렬로 처리할 수 있다.
Output Dependency
읽기 이후에 쓰기 연산이 일어나는 경우다.
1. A = 1
2. B = A + 1
3. A = 3이 예시에서 구문 1과 구문 3이 Output Dependency를 가지고 있다. 따라서 구문 1과 3은 병렬로 처리될 수 없다.
1. C = 1
2. B = C + 1
3. A = 3종속성을 제거하기 위해 구문 1, 2의 A를 C로 바꿀 수 있다. 그러나 멀티스레드 프로그램에서 공유하는 변수의 경우 함부로 그 이름을 바꿔서는 안 된다.
Input Dependency와 Output Dependency는 변수명을 Rewrite하는 방식으로 제거할 수 있기에 Name Dependency라고도 부른다.
Control Dependency
앞선 구문의 결과에 따라 다음 구문의 수행 여부가 변하는 경우다.
1. if A > B
2. A = B
3. C = A위 예시에서 구문 2의 수행 여부는 구문 1의 결과에 따라 변한다.
Memory Dependency
포인터 변수를 사용하는 경우 그 의존성을 쉽게 확인하기 어렵다.
*X = *Y + 1
*A = *B + 1위 예시는 얼핏 보면 의존성이 없어 보이지만, Y와 A가 같은 곳을 가리킨다면 Flow Dependency, X와 B가 같은 곳을 가리킨다면 Anti Dependency가, X와 A가 같은 곳이라면 Output Dependency가 발생한다.
