reference: "프로그래머가 몰랐던 멀티코어 CPU 이야기" / 김민장, "Computer System A Programmers'Perspective" / 랜달 E.브라이언트
올바른 병렬 프로그램은 역시 순서를 지키며 실행. 의존성 개념은 파이프라인, 비순차 실행, 병렬 프로그래밍의 기초를 이해하는데 중요.
데이터 의존성(data dependency)
데이터 의존성은 명령어들 사이의 데이터 흐름으로, 프로그램의 문맥을 결정하는데 중요한 요소. 특히 컴파일러에서도 최적화를 할 때 의존성 파악은 가장 중요한 작업 중 하나. 컴파일러는 명령어들의 순서를 이리저리 바꾸는 최적화를 수행하기도 함. 이때 의존성은 반드시 고려해야하는 사항이다. 의존성이 있는 명령어란 곧 순서대로 실행되어야 함을 의미.
데이터 의존성은 읽기/쓰기의 순서에 따라 RAW, WAW, WAR이라는 의존성으로 구분가능.
RAW(Read after Write) 의존성
x = y + 1; // (1)
z = x * 2; // (2)변수 x는 1번 명령이 계산 결과를 만들면 2번 명령이 이를 사용함. 따라서 2번 명령은 1번 명령에 앞서 게산될 수 없음. x 변수에 대한 쓰기 후 읽기를 수행해야 한다는 의미 Read after Write 의존성이라 한다.
헤저드(Hazard)
컴퓨터 구조에 한정하여 이야기할 때 이러한 의존성을 헤저드로 표현하기도 함. 따라서 RAW 헤저드라는 말도 사용.
컴파일러 분야에서는 RAW 의존성을 흐름 의존성(flow dependency)라 부르기도 한다.
WAR(Write after Read) 의존성
z = x * 2; // (1)
x = y + 1; // (2)변수 x가 먼저 읽힌 뒤 값이 쓰여짐. Write after Read 의존성이라함.
컴파일러 분야에서는 반의존성(antidependency)라는 표현을 쓰기도 한다.
WAW(Write after Write) 의존성
x = z * 2; // (1)
x = y + 1; // (2)같은 대상에 쓰여지기에 의존성을 유발함. 다른 이름으로는 출력 의존성(output dependency)라고 불림.
프로그램 코드가 이 세가지 데이터 의존성 중 하나라도 있으면 일단 순서대로 실행을 해야만 정확한 결과를 얻을 수 있음. 그런데 WAR이나 WAW 의존성은 RAW 의존성과 성격이 달라 이 두 의존성은 약간의 속임수로 없앨 수 있다.
WAR 의존성 제거
// WAR 의존성
z = x * 2; // (1) read x
x = y + 1; // (2) write x // (1), (2)의 순서가 바뀌면 z에는 의도치 않은 값이 들어간다.
a = x / 2; // (3)
// (1),(2): WAR 의존성 / (2),(3): RAW 의존성
// WAR 의존성 제거
z = x * 2; // (1)
x1 = y + 1; // (2)
a = x1 / 2; // (3)(1),(2)는 WAR 의존성은 제거되어 동시에 혹은 순서를 바꾸어 수행 가능해진다. 반면 (2),(3)의 RAW 의존성은 이런 이름 바꾸기로는 결코 해결하지 못한다.
WAW 의존성 제거
// WAW 의존성
x = z * z; // (1)
x = y + 1; // (2)
a = x / 2; // (3)
// (1),(2): WAW 의존성
// WAW 의존성 제거
x = z * 2; // (1)
x1 = y + 1; // (2)
a = x1 / 2; // (3)WAW 역시 이름 바꾸기로 해결 가능. WAR 의존성과 마찬가지로 이름을 바꾼 변수가 그 뒤에 사용되고 있다면 그들도 모두 바꾸어야 함.
이렇듯 WAR/WAW 의존성은 변수의 이름을 바꿈으로써 쉽게 없앨 수 있다.
How to RAW 의존성?
RAW 의존성이 있는 명령어들은 순서대로 실행되어야만 함. 이러한 의미에서 RAW 의존성을 진짜 의존성(true dependence)라고 부르고, WAR이나 WAR 의존성을 가짜 의존성(false dependece)이라 부르기도 함. (또한 WAR, WAW 의존성은 이름 변경으로 의존성을 회피할 수 있는, 이름 때문에 발생한 의존성이라하여 이름 의존성(name dependece)라 분류하기도 함.)
