reference: "프로그래머가 몰랐던 멀티코어 CPU 이야기" / 김민장, "Computer System A Programmers'Perspective" / 랜달 E.브라이언트
컨트롤 의존성(Control dependency)
프로그램의 의미는 데이터 의존성 뿐 아니라 조건 분기문으로도 결정된다.
if (a == 10) // (1)
b = 10; // (2) (1)명령과 컨트롤 의존성
else // (3)
b = 20; // (4) (1)명령과 컨트롤 의존성
a = b + 10; // (5) (2),(4)와 RAW 의존성
z = x / y; // (6)
k = a + z; // (7) (6)과 RAW 의존성(1),(2),(4) 명령어에는 실행 흐름(control flow) 때문에 의존성이 만들어짐. 이것을 컨트롤 의존성(control dependency)라 한다.
이렇듯 조건 분기문으로 인한 제어 흐름의 변화도 의존성을 만든다.
참고로 무조건 분기문(uncondition branch)는 컨트롤 의존성을 만들지 않음.
또 다른 분기문인 함수 호출은, 이 자체는 무조건 분기를 하지만 함수 호출이 완료되면 결국 다음 문장으로 이어지므로 겉으로는 컨트롤 의존성을 만들지 않는다.
(이후 교재 프로시저 간 최적화(IPO) 참고할 것)
컨트롤 의존성 파악 문제는 비단 프로세서와 컴파일러에서만 필요한 것이 아니라 소프트웨어 테스팅에서도 중요한 문제.
컨트롤 의존성은 어떻게 보면 PC(Program Counter) 레지스터에 의한 RAW 데이터 의존성으로도 볼 수 있음.
메모리 의존성(Memory dependency)
데이터 의존성을 이야기할 때 예로 들었던 int, float와 같은 비포인터 형의 자료이다. 기계어 수준으로 이야기하면 모두 레지스터 형. 그러나 만약 포인터 형이라면 의존성이 달라짐.
*x = *y + 1; // (1)
*a = *b + 2; // (2)
// 포인터로 인한 메모리 의존성: 이 정보만으로는 (1),(2) 사이에 어떤 의존성이 있는지 말할 수 없다. 만약 4개의 포인터(x, y, a, b)가 모두 다른 변수를 가리키면 의존성이 없음.
그러나 포인터 x, b가 같은 대상을 가리킨다면 RAW 의존성 발생. 또는 y와 a가 같은 대상을 가리킨다면 WAR 의존성 유발.
이렇듯 의존성 파악을 위해 포인터 변수가 가리키는 목적지를 정확히 알아야만 파악할 수 있다. 이 메모리 의존성을 파악하는 문제는 최신 프로세서 뿐 아니라 컴파일러 최적화에도 매우 큰 골칫거리.
주어진 명령어 사이에 메모리 의존성이 있는지 없는지 밝혀내는 것을 메모리 명확화(memory disambiguation) 문제라 함. 이 문제는 프로세서와 컴파일러에 모두 중요함.
컴파일러에서는 포인터가 어떤 값을 가리키는지 알아내야 하므로 포인터 분석(pointer analysis)이라 하기도 한다. 데이터 의존성은 단순히 이름을 확인함으로써 의존성이 파악되므로 두 명령어에 인코딩 되어 있는 레지스터 이름을 간단히 비교하면 데이터 의존성이 파악된다.
메모리 의존성은 로드/스토어 대상을 실행하지 않고서는 정확히 알 수 없으므로 의존성을 파악하기 어렵다. 컴파일러가 컴파일할 때, 실제 어떤 주소 값이 올지 모름. 컴파일러가 두 메모리 연산 사이에 의존성을 예측하는 것은 일반적으로 매우 어려운 문제. 그 이유는 의존성 여부를 판단하려면 결국 두 메모리 연산이 가리키는 주소 값의 범위를 알아야 하는데, 코드를 실행하지 않고서는 이것을 알아내기가 굉장이 어렵다.
따라서 실제 실행하지 않고서는 의존성을 완벽히 파악할 수 없으므로 컴파일러는 보수적으로 의존성을 판단할 때가 많다. 이 결과 코드를 최적화하기가 어려워지고, 현대 프로세서 역시 자체적으로 최적화하기 어려워진다.
명령어 재배치
정리하자면, 의존성이 있는 두 명령어는 반드시 그 순서대로 실행되어야만 정확한 문맥을 유지할 수 있다. 두 명령어 사이에 의존성이 없다면 어떤 순서로 혹은 병렬로 실행되어도 상관없다. 이렇게 의존성 분석을 하면 컴파일러나 프로세서는 최적의 명령어 실행 순서를 정할 수 있다. 이런 것을 보통 명령어 재배치(instruction reordering) 혹은 명령어 스케줄링(instruction scheduling) 최적화라 부른다.
명령어 재배치 예시
메모리 로드 연산은 캐시 미스를 유발할 수 있으므로 시간이 오래 걸릴 수 있다. 만약 메모리 로드 뒤에 RAW 의존성을 갖는 명령어가 줄줄이 있다면 최대한 빨리 메모리 로드를 마치는 것이 효과적일 것. 그럴 때, 컴파일러나 프로세서는 메모리 로드 앞에 있는 명령어를 살펴보고, 만약 아무 의존성이 없는 명령어가 있다면 메모릴 로드를 이들 앞에 배치할 수 있다. 일종의 레이턴시 감추기(latency hiding)같은 기술로 최대한 메모리 로드에 걸리는 시간을 줄이려는 노력으로 볼 수 있다.
루프에서의 데이터 의존성
데이터 의존성은 루프에서 좀 더 특별한 형태로 나타날 수 있다. 여기에도 RAW, WAR, WAW 의존성이 있다.
for(int i=1; i<N; i++)
A[i] = A[i-1] + 1;
// 루프 순환에 따른 2번 구문의 메모리 접근
i=1: A[1] = A[0] + 1;
i=2: A[2] = A[1] + 1; // A[1]에 대한 RAW 의존성
i=3: A[3] = A[2] + 1; // A[2]에 대한 RAW 의존성위와 같이 배열 A는 루프에 대한 루프 전이 RAW 의존성을 가진다고 말한다.
루프 전이 의존성과 구분하여, 루프 순환 사이에 걸쳐 발생하지 않는 의존성을 루프 무관 의존성으로 부른다.
루프 전이/무관 의존성은 모두 데이터 의존성의 부분 집합.
루프 전이 WAR 의존성
// 루프 전이 WAR 의존성
for(int i=0; i<N-1; i++)
A[i] = A[i+1] + 1;
// 루프 순환에 따른 2번 구문의 메모리 접근
i=1: A[0] = A[1] + 1;
i=2: A[1] = A[2] + 1; // A[1]에 대한 WAR 의존성
i=3: A[2] = A[3] + 1; // A[2]에 대한 WAR 의존성루프 전이 WAR, WAW 의존성도 앞서 본 것처럼(데이터 의존성 파트) 이름 바꾸기와 같은 기법으로 없앨 수 있다. 그러나 명시적으로 이름을 바꾸는 것이 아니라 루프 전이 WAR 의존성은 복사본을 하나 만듦으로써 의존성을 극복할 수 있다.
int oldA[N];
memcpy(oldA, A, sizeof(int)*N); // 배열 복사
for(int i=0; i<N-1; i++)
A[i] = oldA[i+1] + 1;
// 루프 순환에 따른 2번 구문의 메모리 접근
i=1: A[0] = oldA[1] + 1;
i=2: A[1] = oldA[2] + 1; // A[1]에 대한 WAR 의존성
i=3: A[2] = oldA[3] + 1; // A[2]에 대한 WAR 의존성루프 전이 WAW 의존성
// 루프 전이 WAW 의존성
for(int i=0; i<N; i++)
B[0] = A[i] + i;
// 루프 전이 WAW 의존성 해결
for(int i=0; i<N; i++)
tempB[i] = A[i] + i;
B[0] = A[i] + i;루프 전이 의존성 제거를 통한 병렬화
어떤 루프에서 루프 전이 의존성이 제거되면 이 루프는 병렬화가 가능해진다. 즉 각 루프의 순환이 여러 스레드에서 동시에 실행 가능해진다.
루프 전이 WAR, WAW는 알고리즘의 근본적인 변화보다는 프로그래밍 테크닉으로 회피할 수 있는 특징이 있다. 컴파일러는 이런 의존성 분석을 통해 루프에 의존성이 없다면 자동으로 병렬화할 수도 있다. 루프 병합(loop fusion)이나 루프 바꾸기(loop interchange)같은 최적화도 의존성 분석을 반드시 해야만 가능하다.
의존성 결론
데이터, 컨트롤, 메모리 의존성은 프로그램 코드의 실행 순서를 함축한다. 데이터 의존성은 루프에 걸쳐 나타날 수도 있다. 이 가운데 WAR, WAW 의존성은 다른 변수를 잠시 사용함으로써 해결할 수 있다. 그러나 RAW 의존성은 반드시 지켜야만 했다. 두 명령어 사이에 의존성이 없다는 의미는 서로 순서에 상관없이 혹은 병렬화 가능함을 의미한다.
=> 순서를 바꿀 수 있다. => '명령어 재배치'가 가능하다. => 레이턴시를 줄일 수 있다.
reference:
RAW 의존성 완화 관련 value prediction, 투기적 실행. STORY 05 마지막 페이지 참고.
