Sunday, June 7, 2009

컴퓨터는 정확한가?



컴퓨터는 일상적인 일에 많이 많이 사용되지만 실제로 하는 일은 계산하는 것. Computer니까.

실제로 전자회로를 이용한 컴퓨터가 사용되기 전에는 천문대나 군이나 연구소에서는 아래 그림 처럼 사람들이 계산을 했더랬다.


현대의 컴퓨터는 매우 성공적으로 각종 분야에서 사용되어 왔고 큰 발전을 이루어 왔지만, 기본적으로 하는 일은 그리 달라지지 않았다. 더하기 빼기 곱하기 나누기.

문제는 오래 전이나 지금이나 컴퓨터는 수를 정확히 표현하지 못한다는 것. 2진수표현을 사용하기 때문에 분모가 2의 지수가 아닌 유리수를 제외한 수는 정확히 표현하지 못한다.

사실 이것은 사람이 10진수를 사용한다고 해서 달라지는 것은 아니지만, 수학의 세계에서는 '무한히 긴' 소수를 감당할 수 있기 때문에 큰 문제가 되지 않는다. 그렇지만 컴퓨터는 그렇게 하지 못하는 것이 문제.

cuda 구현시 precision에 따른 문제가 있나 싶어 돌아다니다 본 흥미로운 발표자료.
http://www.mathematik.uni-dortmund.de/lsiii/static/showpdffile_GoeddekeStrzodka2006.pdf
막연히 갖고 있던 고정 관념 중 몇가지를 깨는 것이라 흥미롭다.

1) 컴퓨터가 부동소수점을 사용하여 계산한 결과는 언제나 어느 정도의 범위안에서라도 정확하다.

발표자료안에서 보여준 예. 다음과 같은 함수가 있다고 하자.
f(x,y) = (333.75-x^2)*y^6+x^2*(11*x^2*y^2-121*y^4-2)+5.5*y^8+x/(2y)
x=77617, y=33096일 때 함수값은?

아무 문제 없는 단순한 함수인데, 컴퓨터는 어떤 precision을 막론하고 1.17260~~~의 결과를 계산해낸다.
정답은 -0.82739605994682136814116509547981629….
부호마저 틀린 답을 계산했다.

컴퓨터는 항상 정확하지는 않다.

2) 더 많은 bit를 사용한 수 표현은 항상 더 정확하다.
결과의 정확도가 중요한 계산의 경우에는 double precision을 사용해야 한다는 것이 일반적인데, 해당 발표자료의 6페이지 결과는 이마저도 사실이 아님을 보여준다.
어떤 경우에는, double precision의 계산 결과가 single precision보다도 부정확한 경우가 있다는 것.

high precision이 더 나은 정확도를 항상 보장하는 것은 아니다.

그렇지만 보통 골라서 사용할 수 있는 경우에는 double precision이 더 나은 결과를 보여주는 경우가 많은 것도 사실이긴 하지만.

cuda의 경우에는, 32bit의 fpu를 사용하는 것이 일반적이므로 항상 single precision이라고 가정하는 것이 옳다. 최신의 gpu를 활용하는 경우 double precision을 지원하지만, double precision용의 fpu는 한 개만 들어있으므로 그 만큼의 속도 저하를 감수해야 한다. double형 계산은 serialize된다고 보아야 하므로.

cuda 결과를 cpu의 single precision 결과와 비교해볼때도 차이가 발생할 때가 있음에 주의하자.

1) MAD 최적화

계산 오차가 발생했다면 이 때문일 확률이 높다. cuda compiler는 매우 공격적으로 최적화를 수행하는데, 곱해서 더하는 operation을 대부분 MAD로 치환하는 것으로 보인다.
문제는 nvidia gpu의 fpu에 들어있는 레지스터 셋이 32비트라는 점인데, 곱하고 더하는 것을 한 번에 수행할 경우에는 미리 round-off되는 비트가 많다. 이것은 cuda 2.0 manual에 간단히 설명되어 있는데, 곱하기 연산을 해서 register에 넣었다가 다시 더하기 연산을 하는 것과 차이가 꽤나 크게 날 수 있다.

cpu의 경우에는 계산 레지스터의 길이가 80비트정도로 긴 경우가 많아서 이런 현상이 문제가 되지 않으므로 계산 결과가 중요하다면 확인해야 한다.

MAD최적화를 수행하지 않음으로써 cuda에서 이 문제를 해결할 수 있는데, 곱하기를 수행할 때 fmul_rz 함수를 불러서 하면 MAD최적화 없이 컴파일되어 오차가 크게 줄어든다.

2) summation순서

큰 수와 작은 수의 덧셈을 반복적으로 수행하는 경우에 더하기 순서에 따라 결과가 달라진다. 이는 cuda의 경우에도 마찬가지고, 32 bit 크기의 레지스터 내에서 이 영향을 줄이는 방법을 고려할 필요가 있다.

보통은 Kahan summation을 사용해서 오차를 줄인다.