기억창고

고속 그래픽 계산을 위한 고정소수점 연산

- 고정 소수점 연산이란

 이미지 처리, 3D 렌더링 등 그래픽 연산에서는 아주 많은 부동소수점 연산을 필요로 한다. 대부분의 프로세서는 배정도 부동소수값(double)을 IEEE754라는 규격의 포맷을 사용해 기억장소에 저장하는데, IEEE754는 부동소수를 정수 부분과 지수 부분으로 나누어 기억장소에 저장한다. IEEE754는 전체 62비트 중 첫 번째 비트에는 부호를, 두 번째 비트부터 11개의 비트는 10의 승수부분을, 그리고 나머지는 유효숫자(mantissa)를 저장하는 형태로 되어 있다.(오늘날의 프로세서들은 거의 모두 IEEE 부동소수 형식을 지원한다.) 예를 들어 1234.5678라는 값이 있다면 이 값은 다음과 같은 형태로 바뀐다.

      1.234567 × 10^3

 부동소수값이 들어있는 62비트 중 첫 번째 비트는 양의 부호를 나타내는 0, 두 번째부터 11개의 비트에는 10의 승수인 3, 그리고 나머지 부분에는 유효자리수인 1234567이 들어가게 된다. 이처럼 컴퓨터에서 실수형 숫자를 저장하는 방식은 정수형에 비해 매우 복잡하다. 그러니 실수형 연산이 정수형 연산에 비해 연산속도가 매우 느린 것은 당연하지 않을까?

 그래픽에서 부동소수 계산은 아주 필수적이고 계산량이 많기 때문에 많은 사람들이 보다 빠른 방법으로 부동소수를 처리하는 방법을 고안해 냈다. 그중 대표적인 것이 바로 고정소수점 연산이다. 고정소수점 연산이란 정수형을 이용해 소수의 정수부와 소수부를 저장하도록 하는 수치해법적인 방법이다. 다시 말해 고정소수점 연산이란 실수형 연산을 정수형 타입의 변수를 이용해 연산하는 방법을 말한다.

- 수행 시간을 측정하는 프로파일링

 속도를 빠르게 하려면 계산하는 속도를 측정해야 하므로 프로그램의 연산속도를 측정하기 위한 방법들을 먼저 살펴보자. 프로그램의 수행시간을 측정하기 위해 쓸 수 있는 첫 번째 방법으로 clock() 함수를 이용하는 것이 있다.

 <리스트 1>을 잘 살펴 보자. clock() 함수는 현재 시스템의 클럭을 리턴하는데, 계산시간과 끝난 뒤, 이 클럭의 차이값과 초당 몇 개의 클럭이 지나갔는지를 따져보면 계산하는 동안 얼마의 시간이 흘렀는지 확인할 수 있다. 그러나 PC의  Win32 환경에서 시간 계산은 이론적으로 1/1000초까지 측정이 가능하지만 실제로는 1/18초 단위까지만 가능하다. 또한 윈도우 95나 NT와 같은 멀티태스킹 운영체제에서는 수행할 때마다 약간씩 다르게 측정되기 때문에 이 방법으로는 Win32 환경에서의 수행시간을 정확하게 측정하기 힘들다. 하지만 유닉스와 같은 시스템에서는 상당히 정확하게 계산되어 종종 사용된다.

 이렇게 프로그램 자체에서 시간을 측정하는 방법이 유용할 때도 있지만 보다 정교한 측정을 위해서는 프로파일링(profiling)을 이용하는 것이 좋다. 비주얼 C++에 기본으로 포함돼 있는 프로파일링은 각 함수의 수행시간을 측정해 주는 도구로 전체 프로그램의 어떤 부분에 부하가 많이 걸리는지를 알아낸다. 따라서 전체 시스템의 수행속도를 높이고자 할 때 유용하게 사용된다.

 비주얼 C++ 4.x에서 프로파일링을 사용하려면 프로그램을 컴파일하기 전에 다음과 같은 조치를 취해야 한다.(비주얼 C++ 5.0 이상에서는 Project 메뉴 아래에서 Settings...을 선택하면 된다.)

 ■ Release 모드면 프로파일링이 제대로 되지 않기 때문에 반드시 디버그 모드여야 한다.
 ■ Build/Settings 메뉴에서 Project Settings 다이얼로그, Link 탭을 선택하면 Enable Profiling이 보이는데, 이를 체크하고 컴파일한다.

 그 다음 Tools/Profile 메뉴를 선택하고 'function timming' 라디오 버튼을 선택해 OK를 누른다. 그러면 실제 프로그램이 돌아가면서 각 함수를 수행하는데 경과된 시간을 Output 윈도우에 보여준다.

 <리스트 2>는 템플릿을 이용해 double, float, int의 타입에 대한 사칙연산을 각각 백만 번씩 수행하는 프로그램이다. 이것을 프로파일링해 보면 정수형과 실수형 연산의 속도차이를 확인할 수 있다.

<표 1> 프로그램의 프로파일링 결과 (숫자는 연산에 걸린 시간, 작을수록 빠름)

 이 프로파일링의 결과 (<표1>)는 펜티엄 166MHz에서 수행한 것이다. 자세히 살펴보면 int와 float 두 타입의 덧셈, 뺄셈은 차이가 거의 없지만 곱셈과 나눗셈은 확연히 차이가 난다는 것을 알 수 있다. 곱셈의 경우 거의 3.5~4배, 나눗셈의 경우 1.5배 정도 정수형 연산이 빠르다. 그리고 double 타입과 비교해 보면 최소 3배에서 곱셈의 경우 무려 9배까지 연산속도의 차이를 보이고 있다.

 수행할 때에 따라 혹은 시스템에 따라 약간의 차이가 있지만 펜티엄 프로세서의 경우 int 형과 float형의 덧셈과 뺄셈 연산은 거의 차이가 없다. 하지만 486의 경우는 float의 덧셈, 뺄셈이 int형의 경우에 비해 확연히 느리다.

 앞서 이야기했듯 고정소수 연산은 정수형을 이용해 실수 연산을 대신하는 방법인데, 이 실험을 통해 알 수 있는 것처럼 부동소수 연산대신 정수연산만 사용하면 약 3~4.5배 정도의 속도 향상을 기대할 수 있다. 구성상의 문제이지만 그보다 훨씬 빠른 속도를 얻을 수도 있다.

(참고로 다음의 표는 PII - 233에서의 프로파일링 결과이다.- float 형의 곱셈의 경우 int 형의 13.5 배, 나눗셈의 경우 거의 3배 정도 차이가 난다.)

- 고정소수점 연산과 포맷

 예를 들어 32비트 정수형 변수가 있다면 위쪽의 16비트를 정수 부분, 아래쪽 16비트를 소수부분을 가정해 보자. <그림 1>과 같이 생각할 수 있는데, 여기서 S는 정수 부분의 비트로, X 부분은 소수점 이하 부분의 비트들로 볼 수 있다. 실제로 소수점이 존재하는 것이 아니라 가상으로 있다고 가정하는 점이라는 것을 잊지 말기 바란다.

 이해를 돕기 위해 10진수 4자리를 정수형으로 사용하는 가상의 기계를 생각해 보자. 예를 들어 처음 두 자리는 정수부분이고 나중 두 자리는 소수 부분이라면 0, 8, 4, 3 이라고 저장된 내용은 8.43을 뜻하게 되는 것이다. 이것을 형식을 부를 때 2.2라는 식으로 부른다. 즉, 처음 두 자리가 정수 부분, 나중 두 자리가 소수 부분이란 뜻이 된다. 그렇다면 4.0은 어떤 뜻이 될까? 소수 부분이 없으니 네 자리 모두 정수 부분이란 뜻이 된다. 즉, 정수형 변수임을 뜻한다. 이런 네 자리수의 사칙연산에 대해 알아보자.

   04.00          05.00
+  03.00        - 07.00
--------    ----------
   07.00        - 02.00

<그림 1> 32비트 정수, 16.16 포맷의 고정소수

S

S

S

S

S

S

S

S

S

S

S

S

S

S

S

S

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

X

 더하기 빼기는 아주 쉽다. 그러나 곱셈과 나눗셈의 경우는 조금 문제가 있다. 즉 소수점이 없기 때문에 곱한 결과의 소수 이하 부분이 확대돼 나타난다(이 문제에 대해서는 뒤에서 좀더 자세하게 다룬다).

12.34 × 67.89 = 838.10205
1234 × 6789 = 83810205
07.00 × 03.00 = 21.0000

 M.N 포맷이면 두 수를 곱한 뒤에 N번만큼 오른쪽으로 이동하면 되는데, 이 때 잘려나가는 값이 생기게 된다.

 서로 다른 포맷 간의 고정소수점 연산에도 적용이 가능하다. 예를 들어 2.30 포맷을 사용하는 사인값에 18.14 포맷과 곱셈을 하면 결과는 20.44 포맷이 된다. 이 결과를 18.14 포맷으로 바꾸려면 뒤부분 30비트만큼의 소수 부분과 정수 부분의 끝부분 2비트를 잘라내야 한다.  

 나눗셈에서는 몫과 나머지를 구해야 한다. 1 나누기 3을 하면 0.333 이지만 정수로 연산을 하면 소수 이하 부분이 버려져서 0이 되고 만다. 별로 바람직한 결과는 아니다. 나누려는 수 1에 0을 붙여 10을 만들고 나서 3으로 나눈 다음 그 결과를 다시 10으로 나눈다. 결과는 3이다. 즉, 나누기를 하기 위해 원래 피연산자보다 확대된 형태를 저장할 수 있어야 한다.

 만일 2.2 포맷의 1을 4.0 포맷의 3으로 나누면 어떻게 될까? 01.00/0003. 이면 00.33이 된다. 이는 고정소수점 연산에서도 실수와 정수 연산은 실수가 된다는 점을 보여준다. 고정소수 숫자를 고정소수로 나누려면, 예를 들어 2자리 소수 부분을 얻으려면 피젯수를 두 번 왼쪽으로 이동시켜야 한다.

0100/0300 = 0000
01000/0300 = 0003
010000/0300 = 0033

 지금까지 설명했던 내용을 정리해 보면 다음과 같다.

 ■ 결과의 자리수는 곱해지는 두 수의 자리수를 더한 것보다 작거나 같다.
 ■ 결과의 소수 자리수는 두 수의 소수 부분 자리수를 더한 것과 같다.
 ■ 정수라는 것은 소수 부분이 없다(4.0고정 소수점).

 32비트 환경이라면 일반적으로 16.16을 사용하겠지만 오버플로우 등을 막고 보다 큰 값을 저장하려면 17.15 나 18.14 포맷을 사용하는 것이 좋다.

 이 외에도 다양한 포맷을 생각해 볼 수 있다. 예를 들어 0과 1 사이의 값을 아주 정밀하게 표시하기 위해 1.31 포맷을 사용할 수도 있다.

 또 하나 고려할 것이 있는데, 64비트 정수를 사용할 수 없는 상황이라면 8.8 이나 8.16 과 같은 포맷도 고려해 볼만하다. 특히 윈도우 3.1과 같은 16비트 환경에서는 유용하게 사용할 수 있다. 그러나 비주얼 C++에서는 __int32와 __int64란 타입을 지원하고 있어 32비트 정수형과 64비트 정수형을 자유롭게 쓸 수 있다.

 이상에서 짤막하게 살펴 본 몇 가지 문제점은 뒤에서 좀 더 자세히 다루도록 하고, 실제 32비트로 만들어진 16.16 포맷을 어떻게 구현하고 사용하는지 알아보자.

-Fixed 타입과 int, double 사이의 변환

 간단하게 다음과 같은 새로운 타입을 지정할 수 있다.

 typedef    __int32   Fixed;

 정수형값을 Fixed 타입으로 바꾸려면 다음과 같이 하면 된다. __int32는 32비트 정수형으로 비주얼 C++에서 기본으로 제공하는 타입이다. int나 long으로 바꾸어 써도 마찬가지다.

Fixed fix;
int iValue = 123;

fix = (Fixed)(iValue << 16);

 실수형값을 fixed로 바꾸려면 16자리만큼 왼쪽으로 이동한다. 즉 65536을 곱한 값이 된다. 실수형의 경우도 마찬가지로 65536을 곱하면 된다. 이때는 시프트 연산을 쓰지 못한다.

Fixed fix;
double dValue = 123.0f;

fix = (Fixed)(dValue * 65536.0);

 거꾸로 Fixed 타입의 정수를 int나 double형으로 바꾸려면 다음과 같이 한다.

double dValue;
dValue =  ((double)fix) / 65536.0;


int iValue;
iValue = fix >> 16;

- Fixed 타입의 사칙연산

 Fixed 타입 변수의 덧셈과 뺄셈은 int 나 double과 같은 기본적인 타입과 똑같다.

Fixed fix1, fix2, fix3;
fix3 = fix1 + fix2;
fix3 = fix1 - fix2;

 덧셈, 뺄셈은 아무런 문제가 없지만 곱셈의 경우는 좀 다르다.

Fixed fix1, fix2, fix3;
fix3 = fix1 * fix2;

 이 경우 fix1과 fix2는 각각의 수에 65536이 곱해진 수를 다시 곱하므로 비례확대가 일어난다. 이 정수형이 2.2 포맷의 고정소수로 돼 있다면, 덧셈의 경우 12.0 + 4.6은 다음과 같이 표시될 수 있다.

   1200                   12.00
 + 0460               +   4.60
--------            --------
   1660                   16.60

그러나 곱하기 연산의 경우는 약간의 문제가 있다.

   1200                   12.00
x 0460                x   4.60
--------            --------
552000                   55.2000

 즉, 두 수를 곱하면 결과가 4자리수를 넘으면서(오버플로우), 소수 부분 자리수가 4자리가 된다(이런 현상을 '비례확대'라 한다). 따라서 계산한 뒤에 혹은 계산하기 전에 다음과 같이 소수 부분의 자리를 이동시켜 주어야 한다.

fix3 = (fix1 * fix2) >> 16;         // ①
fix3 = (fix1>>16 * fix2);           // ②

 그러나 여기에도 문제가 있다. 이 코드에서 ①의 경우 32비트 정수형을 곱하는 과정에서 오버플로우가 생긴다. 최악의 경우에 32비트 숫자의 곱은 64비트 결과를 만든다(피연산자 둘 중 하나가 1.0보다 크면 항상 오버플로우가 생긴다).

 ② 의 경우는 곱셈을 하기 전에 자리수를 이동시키지만 fix1의 소수 부분을 모두 없애므로 정확성이 감소하게 된다. 정확성을 어느 정도 유지하면서 오버플로우를 막을 수 있도록 fix1, fix2의 두 수를 각각 8비트만큼씩 오른쪽으로 시프트한 후 곱하는 방법을 사용할 수도 있다.

fix3 = (fix1 >>8) × (fix2>>8);

 그러나 가장 정확한 방법은 32비트 정수형을 곱할 때 64비트 정수형 곱셈을 사용하는 것이다. 64비트 정수형 곱셈 연산은 float보다 2배,double 보다 3배 이상 빠르다.

 나눗셈의 경우도 곱셈의 경우와 비슷하다.

fix3 = (fix1<<16) / fix2;
fix3 = (fix1<<8) / (fix2<<8);

 이와 같이 쓸 수 있지만 시프트하는 도중에 fix1에 저장된 정수값의 일부를 잃어버릴 수 있기 때문에 별로 바람직하지 않다. 나눗셈의 경우도 곱셈과 마찬가지로 64비트연산을 사용하는 것이 바람직하다.

- 고정소수점 연산의 정밀도

 고정 소수점 연산을 사용하면 경우에 따라 4배이상 빠른 계산속도를 얻을 수 있다(부동소수점 연산 프로세서가 없는 386DX와 같은 프로세서에서는 11배 이상의 속도 차이를 내기도 한다)는 것을 앞에서 이미 밝힌 바 있다.

 그렇다면 고정소수점 연산의 정밀도는 어떨까? 물론 float, double과 같은 부동소수를 사용하는 것에 비해 고정소수점 연산은 계산의 정밀도를 떨어뜨린다. 그러나 결론부터 이야기하자면 고정소수점 연산의 정밀도는 그다지 우려할 만한 것이 아니다. 오히려 정밀도를 높일 수 있다.

 앞에서 고정 소수점을 표현하기 위해 정수와 소수 부분의 자리수를 배정하여 M.N이라는 포맷을 사용했다. M은 정수 부분, N은 소수 이하 부부능ㄹ 나타내는 데 사용되는 비트수이며, int가 32비트인 기계의 경우 M과 N을 더한수는 항상 32가 되게 한다. 16.16포맷을 기준으로 고정소수점의 정밀도에 대해 생각해 보자. 16.16포맷은 정수부분이 16비트, 소수 부분이 16비트로 각각 할당되어 있는 형태이다. 정수 부분의 16비트로 나타낼 수 있는 값의 범위는

부호가 없다고 가정하면(즉, unsigned로 취급) : 0 ~ 2^16 - 1
부호가 있다고 가정하면(즉, signed로 취급) : -2^15 ~ +2^15 - 1

이 된다. 부호가 있어도 값을 다루는데 충분하므로 여기서 부호가 없는 형태는 생각하지 않기로 한다. 즉, -32768 ~ +32767까지의 값의 범위를 가진다. 일반적으로 그래픽 표시장치가 1280×1280의 범위를 넘어서지 않으므로 이 정도의 범위는 그래픽에서 좌표계로 사용하기에 충분한 범위이다.

 이제 소수 부분을 생각해 보자. 소수 부분은 2^n (n은소수 이하 자리수)로 나타낼 수 있다. 예를 들어 2진수 0.011로 표시된 것은

0.011 = 0 x 2^(0) + 0 x 2^(-1) + 1 x 2^(-2) + 1 x 2^(-3) = 0 + 0 + 0.25 + 0.125 = 0.375

로 다시 나타낼 수 있다. 소수 부분을 나타내기 위해 16비트를 사용하면 1/2^(16) = 1/65536 = 0.0000153의 정밀도를 가진다. 다른 예로 만일 18.14 포맷을 사용한다면 소수 이하 정밀도는 1/2^(14) = 1/16384 = 0.000061 이 된다.

 일반적으로 float 타입을 가지고 연산할 때 소수 6자리 이하의 정밀도는 신뢰할 수 없는 것으로 여긴다. 이런 사실을 놓고 볼 때, 16.16 포맷의 고정소수점 연산의 정밀도는 소수 이하 5자리까지 정밀도를 보장하므로 float 타입의 연산에 못지 않게 상당히 정밀하다고 볼 수 있다. 이 글에서는 주로 16.16 포맷을 사용하였으나 프로그래머의 필요에 따라 정수 부분이 많이 필요하면 18.14 포맷이나 24.8 포맷을 사용할 수 있고, 거꾸로 아주 세밀한 정밀도가 요구되어 소수 이하 부분이 많이 필요하면 14.18 포맷이나 8.24 포맷을 사용할 수도 있다. M과 N을 어떻게 정하는지는 전적으로 프로그래머에게 달려있다. 즉 고정 소수점 연산을 사용하면 다음과 같은 이점을 얻을 수 있다.

첫째, float 타입을 이용하는 것보다 빠른 계산속도를 보장해 주며,

둘째, 정밀도도 float 타입을 사용하는 것에 못지 않고,

셋째, 소수 이하 부분 정밀도의 범위를 프로그래머가 정할 수 있다.

 이러한 사실이 그래픽 연산에서 고정 소수점 연산을 사용해야 하는 좋은 이유가 된다.


http://myhome.hanafos.com/~kukdas/doc/mfc/fixed.html