데이터 의존성

3. 데이터 의존성 유형

두 명령어(Instruction) $S\_1$과 $S\_2$가 주어졌을 때, $S\_2$가 $S\_1$에 의존하는 경우는 다음 조건을 만족할 때이다.

:$\backslash left[I(S\_1)\; \backslash cap\; O(S\_2)\backslash right]\; \backslash cup\; \backslash left[O(S\_1)\; \backslash cap\; I(S\_2)\backslash right]\; \backslash cup\; \backslash left[O(S\_1)\; \backslash cap\; O(S\_2)\backslash right]\; \backslash neq\; \backslash varnothing$

여기서 각 기호의 의미는 다음과 같다.

• $I(S\_i)$: 명령어 $S\_i$가 읽는 메모리 위치들의 집합
• $O(S\_j)$: 명령어 $S\_j$가 쓰는 메모리 위치들의 집합
• 또한, $S\_1$ 이후에 $S\_2$가 실행될 수 있는 경로가 존재해야 한다.

• 반의존성 (Anti-dependency): $I(S\_1)\; \backslash cap\; O(S\_2)\; \backslash neq\; \backslash varnothing$ 인 경우. 즉, $S\_1$이 읽으려는 메모리 위치에 $S\_2$가 값을 쓰는 경우이다. $S\_1$은 $S\_2$가 값을 덮어쓰기 전에 해당 위치의 값을 읽어야 한다.
• 흐름 의존성 (Flow dependency 또는 True dependency): $O(S\_1)\; \backslash cap\; I(S\_2)\; \backslash neq\; \backslash varnothing$ 인 경우. 즉, $S\_1$이 쓴 메모리 위치의 값을 $S\_2$가 읽는 경우이다. $S\_1$은 $S\_2$가 값을 읽기 전에 해당 위치에 값을 써야 한다. 이는 가장 기본적인 데이터 의존성 형태로, 데이터 의존성이라고도 불린다.
• 출력 의존성 (Output dependency): $O(S\_1)\; \backslash cap\; O(S\_2)\; \backslash neq\; \backslash varnothing$ 인 경우. 즉, $S\_1$과 $S\_2$가 동일한 메모리 위치에 값을 쓰는 경우이다.

3. 1. 진정한 의존성 (True dependency, Read-After-Write, RAW)

3. 2. 반의존성 (Anti-dependency, Write-After-Read, WAR)

3. 3. 출력 의존성 (Output dependency, Write-After-Write, WAW)

1. B = 3

2. A = B + 1

3. B = 7

1. B2 = 3

2. A = B2 + 1

3. B = 7

4. 이름 의존성

데이터 의존성 중 반의존성과 출력 의존성은 변수의 이름을 변경하는 것으로 해결할 수 있다. 이러한 종류의 의존성을 이름 의존성(Name Dependency)이라고 한다. 이름 의존성은 실제 데이터 흐름과는 관계없이 단순히 동일한 이름을 사용하기 때문에 발생한다.

=== 반의존성 (Anti-dependency) ===

반의존성은 어떤 명령어가 나중에 다른 명령어에 의해 갱신될 값을 먼저 읽어야 할 때 발생한다. 이는 '''읽기 후 쓰기(Read-After-Write, WAR)''' 위험으로 이어질 수 있다.

다음 예시를 보자.



1. B = 3

2. A = B + 1 // 명령어 3보다 먼저 B를 읽음

3. B = 7 // 명령어 2가 읽은 후 B에 새로운 값을 씀



여기서 명령어 2는 명령어 3에 대해 반의존성을 가진다. 즉, 명령어 2는 명령어 3이 B의 값을 바꾸기 전에 B의 원래 값을 읽어야 한다. 따라서 이 명령어들의 순서는 바뀔 수 없으며, 순서 변경 가능성이 있는 병렬 실행도 어렵다. 순서가 바뀌면 A의 최종 값이 달라지기 때문이다.

다른 예시는 다음과 같다.



MUL R3, R1, R2 // R2 레지스터 값을 읽음

ADD R2, R5, R6 // R2 레지스터에 새로운 값을 씀



이 두 명령어 사이에는 명백한 반의존성이 존재한다. 첫 번째 명령어가 R2를 읽고, 두 번째 명령어에서 R2에 새로운 값을 쓰기 때문이다.

반의존성은 이름 의존성이므로, 변수 이름(여기서는 레지스터 이름)을 변경하면 의존성을 제거할 수 있다. 이를 레지스터 리네이밍이라고도 한다. 앞의 첫 번째 예시를 다음과 같이 수정할 수 있다.



1. B = 3

N. B2 = B // 새로운 변수 B2에 B의 값을 복사

2. A = B2 + 1 // B 대신 B2를 사용

3. B = 7



새로운 변수 B2를 도입하여 명령어 2와 3 사이의 반의존성을 제거했다. 이제 명령어 2와 3은 병렬로 실행될 수 있다. 하지만 이 수정으로 인해 새로운 의존성이 생겼다. 명령어 2는 명령어 N에 흐름 의존성을 가지게 되고, 명령어 N은 명령어 1에 흐름 의존성을 가진다. 이러한 실제 데이터 흐름에 따른 의존성은 제거할 수 없다.^[2]

=== 출력 의존성 (Output Dependency) ===

출력 의존성은 두 명령어가 동일한 변수(메모리 위치 또는 레지스터)에 값을 쓰는 경우, 명령어의 실행 순서가 해당 변수의 최종 값에 영향을 미칠 때 발생한다. 이는 '''쓰기 후 쓰기(Write-After-Write, WAW)''' 위험으로 이어질 수 있다.

다음 예시를 보자.



1. B = 3 // B에 값을 씀

2. A = B + 1

3. B = 7 // 다시 B에 값을 씀



여기서 명령어 1과 명령어 3 사이에는 출력 의존성이 있다. 두 명령어 모두 변수 B에 값을 쓰기 때문에, 실행 순서가 바뀌면 B의 최종 값이 달라진다. 따라서 이 명령어들은 순서를 유지해야 하며 병렬 실행이 제한된다.

출력 의존성 역시 이름 의존성이므로, 변수 이름을 변경하여 해결할 수 있다.



1. B2 = 3 // B 대신 새로운 변수 B2 사용

2. A = B2 + 1

3. B = 7



변수 B의 첫 번째 쓰기를 새로운 변수 B2에 하도록 변경함으로써, 명령어 1과 3 사이의 출력 의존성이 제거되었다.

5. 컴퓨팅에서의 중요성

데이터 의존성은 컴퓨터 프로그램의 올바른 실행 순서를 보장하고 병렬 처리의 효율성을 높이는 데 핵심적인 역할을 한다. 따라서 컴퓨팅의 다양한 분야, 특히 프로세서 설계, 컴파일러 구축, 병렬 컴퓨팅 및 동시성 프로그래밍에서 매우 중요하게 다루어진다.^[2] 프로그램 내 명령어들이 서로 의존하는 관계를 정확히 파악하고 관리해야만, 여러 명령어를 동시에 처리하거나 순서를 변경하는 최적화를 적용할 때 발생할 수 있는 오류(위험)를 방지하고 성능을 극대화할 수 있다.

5. 1. 프로세서 설계

5. 1. 1. 명령어 파이프라인

5. 1. 2. 아웃 오브 오더 실행

5. 1. 3. 메모리 모호성 제거

5. 2. 컴파일러 구축

5. 2. 1. 명령어 스케줄링

5. 2. 2. 루프 변환

5. 2. 3. 코드 이동

5. 3. 병렬 컴퓨팅 및 동시 프로그래밍

6. 한국의 관점

주어진 원본 소스 내용은 데이터 의존성의 일반적인 개념과 병렬 처리의 어려움에 대해 설명하고 있습니다. 이는 "한국의 관점"이라는 특정 섹션 제목과 직접적인 관련성을 찾기 어렵습니다. 원본 소스에는 한국의 상황이나 특정 관점에 대한 정보가 포함되어 있지 않습니다. 따라서 제공된 원본 소스만으로는 해당 섹션의 내용을 작성할 수 없습니다.

참조

_[1] 논문 Analysis of Programs for Parallel Processing 1966-10-01
_[2] 서적 Computer Architecture: a quantitative approach (3rd ed.) "[[Morgan Kaufmann]]"
_[3] 서적