오늘 하루종일 해맸다.
#그런데 아직도 모르겠다. 이 글은 내 추측성이 난무하는 정리 글이다.
단일 지연과 루프 지연의 차이를 방금 살짝 이해한듯 하여, 간단하게 정리하고자 한다.
단일 지연의 경우, 말그대로 더 하는 순서대로다.
double poly(double a[], double x, long degree)
{
long i;
double result = a[0];
double xpwr = x; /* Equals x^i at start of loop */
for (i = 1; i <= degree; i++) {
result += a[i] * xpwr;
xpwr = x * xpwr;
}
return result;
}
double polyh(double a[], double x, long degree)
{
long i;
double result = a[degree];
for (i = degree-1; i >= 0; i--)
result = a[i] + x*result;
return result;
}
예를 들어 이런 두가지 함수가 있다고 하자.
단일 지연의 경우에는 loop에서 발생하지 않는 경우다.
latency 가 double에서 add일 때 3, mul일 때 5가 걸린다고 했을 때,
poly의 경우 result += a[i] * xpwr이 loop 밖에 있다면 총 8의 지연이
polyh의 경우 result = a[i] + x * result의 경우에도 8의 지연이다.
하지만, 루프 안에 존재했을 때는 최신 프로세서 때문에 다른 결과가 발생한다.
최신 프로세서는 병렬로 처리하는 Out-of-Order Execution 방식을 취하는데, 이 경우에는 선형적인 순서와 상관없이 프로세스를 부르며, 또한 cache에서 instruction을 가져와서 decode하고 선입하는 시간이 execution unit에서 실행하는 시간 보다 엄청나게 빠르다. 따라서 cpu가 놀지 않게 하기 위해서, 앞으로 수행해야할 내용을 미리 처리하는데 이때 branch를 예측한다.
우리가 코드를 작성하다 보면, if문, cmp같은 조건 분기문에서는 조건이 1이냐 0이냐에 따라서 수행해야할 연산이 달라진다.
최신 프로세서는 이 부분을 예측하면서 다음 fetch를 선정한다고 한다.
이 배경 지식 속에서 내가 루프 속에서 새롭게 알게 된 사실은 다음과 같다.
우선 poly의 경우에는 데이터 의존성이 있기 때문에 latency가 8이라고 볼 수 있고
polyh의 경우 각각의 연산이 독립적이기 때문에 5라고 볼 수 있겠다. 이게 가능한 이유는 branch 예측이 있기 때문이다. 그니까 데이터 의존성이 없는 경우에는 각각의 독립적으로 연산을 수행해도 문제가 발생하지 않는다. 따라서 각각의 연산을 대량으로 미리 수행한다. 그리고 나서 3을 더하는 방식이다. 반면에 ploy의 방식에서는 무조건 result의 *이 수행되고 나서 더해져야 그 다음 *을 처리해야할 수 있다. 즉, polyh의 경우, 미리 *를 독립적으로 수행할 수 있기 때문에 곱셈 연산장치가 많다면 막힘없이 진행된다. 하지만 poly의 경우에는 무조건 add의 cluck 시간이 3만큼을 기다릴 수 밖에 없는 구조다.
이 점이 loop latency에서 poly와 polyh가 차이가 나는 결정적이 요소였다.