|
이 글은 조만간 출판될 Game Programming Gems 2 한국어판(류광 역, 정보문화사)의 일부입니다. 이 글에 대한 모든 권리는 정보문화사가 가지고 있으며, 사전 허락 없이는 웹 사이트 게시를 비롯한 어떠한 형태의 재배포도 금지되어 있습니다. 이 글은 최종 교정 전의 상태이므로 오타나 오역이 있을 수 있습니다. 또한 웹 페이지의 한계 상, 실제로 종이에 인쇄된 형태와는 다를 수 있습니다. Game Programming Gem 2 한국어판에 대한 정보는 GPG 스터디(http://www.gpgstudy.com/)에서 얻을 수 있습니다. |
2.1 부동소수점 비법들: IEEE 부동소수점을 통한 성능 향상
개요
정수(integer, 整數)는 고정된 정밀도(precision, 유효자리수)와 크기(magnitude)를 가진다. 부동소수점(floating-point, 浮動小數點) 수는 말 그대로 소수점(decimal point)의 위치가 떠다니는(floating, 부동) 수를 말하며, 크기도 가변적이다. 역사적으로, 정수는 빠르고 부동소수점수는 느렸으므로, 대부분의 게임 프로그래머들은 부동소수점수를 피하고 대신 정수를 사용했는데, 사실 일반적인 계산을 정수로만 수행하는 것은 번거로운 일이 아닐 수 없었다. 그래도 얻을 수 있는 이득은 많았다. 그러나 하드웨어 비용이 대단히 낮아지고, PC와 게임 콘솔들이 부동소수점 덧셈, 뺄셈, 곱셈, 나눗셈을 단 몇 사이클 만에 처리하게 됨에 따라, 이제는 게임 프로그래머들이 손쉬운 부동소수점 연산의 장점을 취할 수 있는 시절이 도래하게 되었다.
기본적인 부동소수점 연산이 빨라지긴 했지만, 복잡한 함수들은 여전히 느리다. 부동소수점 라이브러리들이 더 최적화될 수도 있으나, 그런 라이브러리들은 일반적으로 성능이 아닌 정확성을 위해 구현된 것들이다. 게임에서는 정확성보다 성능이 더 중요한 경우가 많다.
이 글은 정확성을 희생함으로써 부동소수점 연산 속도를 빠르게 하는 여러 가지 비법들을 제시한다. 정수 연산에는 오랫동안 테이블 참조 기법이 즐겨 쓰였다. 이 글에서는 임의의 부동소수점 함수의 최적화를 위한 일반화된 선형 및 대수적(logarithmic, 對數的) 참조 테이블 기법들을 소개한다.
이 글에서 이야기하는 주제들은 다음과 같다.
- IEEE 부동소수점 표준
- 빠른 float/int 변환, 비교, 제한
- 사인.코사인 최적화를 위한 선형 참조 테이블 방법
- 임의의 부동소수점 함수의 최적화를 위한 일반화된 참조 테이블 기법
- 성능 측정의 중요성
IEEE 부동소수점 형식
부동소수점 수에 대한 IEEE 표준에는 부동소수점의 이진(binary) 표현과 반올림, 정확성, 예외적 결과(0으로 나누기 등)에 대한 규약들이 명시되어 있다. 이 글에서 다루는 기법은 이진 표현에 근거한 것이며, 반올림이나 예외 처리와는 큰 관련이 없다. IEEE의 표준 이진 표현을 사용하는 컴퓨터나 콘솔이라면 부동소수점 처리에 대한 IEEE 표준을 완전히 만족하지 않는다 해도 이 글의 기법들을 적용할 수 있다. 펜티엄 III Streaming SIMD Extensions(SSE)와 PS2 벡터 유닛은 둘다 IEEE 표준의 부분집합을 만족한다. 그 부분집합은 예외 처리를 완전히 지원하지는 않으나, 이진 표현만큼은 표준을 따르므로 이 글의 기법들을 문제없이 적용할 수 있다.
IEEE 표준은 부동소수점 수를 하나의 부호 비트, 하나의 바이어스된 지수(biased exponent, -指數), 하나의 정규화된 가수(mantissa, 假數) 또는 유효수(significand, 有效數)로 표현한다. 단정도(single precision, 單程度) 32 비트 부동소수점 수(C의 float)는 그림 2.1.1과 같은 방식으로 저장된다.
s = 부호
e = 바이어스된 지수
m = 정규화된 가수
부동 소수점 수는 s x 1.m x 2(e-127)
지수는 바이어스된 형식의 양수(positive number, 陽數)로서 저장된다(이와는 달리 정수의 경우 지수는 2의 보수(complement, 補數)로 표현된다). 여기서 바이어스되었다는 것은 실제 지수에 127이 더해졌다는 뜻이다. 가수는 23 비트 소수에 1을 붙이는 방식으로 정규화된 형태로 저장된다. 이런 방식의 정규화는 사용할 수 있는 비트들로부터 최대의 정밀도를 얻기 위한 것이다.
따라서, 하나의 부동소수점 수는 1에서 2 사이의 값으로 정규화된 유효수 하나, 이진 소수점의 위치를 가리키는 바이어스된 지수 하나, 그리고 부호 비트 하나로 구성된다. 하나의 부동 소수점 수는 다음과 같은 공식으로 표현할 수 있다.
n = s x 1.m x 2(e -127)
예를 들어서 십진수 -6.25는 이진수로 -110.01이며, 이를 위의 공식으로 표현하면 -1 x 1.1001 x 22가 된다. 이는 s = 1, e = 2 + 127 = 10000001, m = [1.]1001에 해당한다(그림 2.1.2).
지수에는 약간의 예외적인 규칙들이 존재한다. e = 255일 때, m에는 숫자 아님(not-a-number, NaN), 정의할 수 없는 결과, 양의 무한대 또는 음의 무한대 같은 특별한 조건들이 들어간다. e = 0은 숫자의 역정규화(denormalize)된 숫자, 즉 숫자가 너무 작아서 지수가 8 비트를 넘어갔을 때의 경우를 위해 쓰인다.
배정도(double precision, 倍程度) 64비트 부동소수점 수도 앞에서 설명한 방식과 비슷한 구조를 지니고 있다. 차이는 지수가 11 비트이고 유효수가 52 비트라는 점이다. 지수의 바이어스 값은 127이 아니라 1023이다. 배정도 수는 저장 공간이 단정도의 두 배이므로 메모리로부터 로드하거나 처리하는 것이 더 느릴 수 있다. 그런 이유로 게임에서는 배정도를 잘 쓰지 않는다. 이 글에서도 단정도 부동소수점수에 대해서만 이야기한다.
부동소수점 트릭
참조 테이블 기법으로 들어가기 전에, 부동소수점 수의 비트 패턴을 조작함으로써 부동소수점 연산의 속도를 높일 수 있는 몇 가지 비법들을 이야기하겠다.
float/int 변환
이후에 나올 참조 테이블 기법은 부동소수점 수를 정수로 변환함으로써 참조 테이블 색인들을 생성한다. 이러한 작업의 속도는 느릴 수 있다. 예를 들어서, 펜티엄 II에서 (int)f라는 코드를 통해 하나의 float을 하나의 int로 변환할 때에는 약 60 사이클 정도가 걸린다. 이처럼 많은 사이클이 소비되는 이유는, ANSI C 표준에서는 float에서 int로의 형변환 도중 소수부는 잘려나가야 되는 것으로 명시하고 있지만, 정작 FPU는 가장 가까운 정수로 반올림하기 때문이다. int로의 변환을 위해서는 FPU 반올림(rounding) 모드를 변경하는 루틴을 호출하고, 변환을 수행하고, 다시 반올림 모드를 원래 대로 바꾸는 과정을 거쳐야 하는데, 이는 대단히 번거로운 작업이다.
int와 float 사이의 형변환에 걸리는 시간은 컴파일러나 프로세서에 따라 다를 수 있다. 모든 최적화 옵션들을 켜놓은 상태에서 이러한 변환을 일반적인 형변환과 비교해보고, 생성된 어셈블리 코드를 살펴보면 실제로 어떤 일이 일어나는지 알 수 있을 것이다.
부동소수점에서 정수로의 형변환을 수행하는 좀 더 빠른 방법은, 부동소수점 수에 1 x 223을 더하고 그 결과에서 상위 지수 비트들을 버리는 것이다. 그럼 코드를 먼저 살펴보고 어떻게 작동하는지 설명하겠다.
편의를 위해, 하나의 32 비트 수를 int 형으로도, 그리고 float 형으로도 접근할 수 있도록 하는 공용체(union)을 정의한다.
typedef union
{
int i;
float f;
} _INTORFLOAT;
INTORFLOAT 형은 이 글의 모든 예제 코드에서 쓰인다. 이 공용체를 통해서 수의 비트 패턴에 접근하는 것은 매우 간단해 보이지만, 실제로는 컴파일러가 예상 외로 많은 코드를 생성해야 할 수도 있다. 예를 들어서 펜티엄 II의 경우 부동소수점과 정수 레지스터들은 개별적인 하드웨어 유닛에 존재하며, 데이터를 한 쪽에서 다른 쪽으로 옮기려면 반드시 메모리를 거쳐야 한다. 따라서 INTORFLOAT 공용체의 수에 접근하려면 추가적인 메모리 로드-저장 과정이 일어날 수 있다. 다음은 하나의 float을 int로 변환하는 코드이다.
INTORFLOAT n; // 변환할 부동소수점 수 INTORFLOAT bias; // "마법의" 수 bias.i = (23 + 127) << 23; // 바이어스 상수 = 1 x 2^23 n.f = 123.456f; // 부동소수점 수 n.f += bias.f; // 부동소수점으로서 더하고 n.i -= bias.i; // 정수로서 뺀다. // n.i는 123이 된다. 이는 n.f의 정수 부분과 일치한다.
마법과도 같은 일이 일어났는데, 왜 그런지 살펴보자. 부동소수점 수에 1 x 223을 더하면 가수가 하위 23비트 쪽으로 밀려나며, 지수는 알려진 값인 (23 + 127)로 설정된다. 거기서 알려진 값 (23 +127)을 정수로서 빼면 불필요한 상위 비트들은 사라지고 하위비트들, 즉 정수부만 남게 된다. 그림 2.1.3은 43.25에 대해 이러한 과정이 일어나는 예를 보여주고 있다.
펜티엄 II에서(모든 것들이 캐시 안에 있다고 할 때) 이 기법을 사용하면 변환 시간이 60 사이클에서 5 사이클로 줄어든다. 물론 인라인 어셈블리 코드를 이용하면 float를 int로 변환할 때 FPU가 반올림 모드를 바꾸지 않도록 만드는 것도 가능하긴 하다. 이는 일반적인 형변환보다는 빠르나, 이 글에서 설명하는 바이어스 기법보다는 일반적으로 느리다.
이 기법은 변환할 부동소수점 수가 더해질 바이어스 상수와 겹치지 않는다는 가정 하에서만 작동한다. 구체적으로 말해서, 수가 223보다 작다면 문제 없이 작동하게 된다.
음의 수를 제대로 처리하려면 bias = ((23 + 127) << 23) + (1 << 22)를 사용해야 한다. 추가된 (1 << 22)는 1.5 x 223에 해당하는데, 이 부분에 의해 음수에 대한 정확한 반올림이 일어나게 된다(그림 2.1.4). 여분의 비트들은 뺄셈의 빌려오기 연산이 가수의 최상위 비트(비트 23)에 영향을 미치지 않도록 하기 위한 것이다. 이 경우 9개가 아니라 10개의 상위 비트들이 제거되므로, 이 기법은 양수보다 1비트 작은 범위에만 적용된다. 즉 변환할 수가 222보다 작아야 하는 것이다.
float를 임의의 소수부 비트들을 가진 고정소수점(fixed-point) 형식으로 변환할 때에는 bias = (23 - 소수부_비트수 + 127) << 23을 사용한다. 음수를 처리하기 위해서는 바이어스에 (1 << 22)를 더해야 한다. 그림 2.1.5는 부동소수점 수 192.8125를 소수부가 2비트인 고정소수점 수로 변환하는 예이다.
정수를 부동소수점 수로 변환할 때에는 위에서 이야기한 과정을 역으로 적용하면 된다.
n.i = 123; // 변환할 정수 n.i += bias.i; // 정수로서 더하고 n.f -= bias.f; // 부동소수점 수로서 뺀다. // n.f는 원래의 n.i를 부동소수점으로 변환한 결과인 123.0이 된다.
일반적으로 int를 float로 바꾸는 작업은 일반적인 형변환으로도 충분히 빠르게 수행할 수 있으므로, 이 기법을 사용할 필요는 별로 없을 것이다.
부호 판정
부동소수점 수의 부호 비트는 31번째 비트이다. 이는 정수에서도 마찬가지이다. 따라서 정수 유닛을 통해서도 부동소수점 수의 음과 양을 구분할 수 있다. f를 부동소수점 수라고 할 때, 다음의 두 코드 조각들은 (거의)동일한 의미를 지닌다.
if ( f < 0.0f ) // 부동소수점 비교 ... INTORFLOAT ftmp; ftmp.f = f; if (ftmp.i < 0) // 정수 비교 ...
의미는 같으나 속도는 다를 수 있다. 정수 비교가 더 빠를 수 있는데, 이는 정수의 명령 스트림 파이프라이닝이 더 우월하기 때문이다. 구체적인 성능 평가를 해보면 알 수 있을 것이다("거의"라고 표현한 이유는, 음의 0에 대한 처리 방식이 조금 다르기 때문이다).
비교
부동소수점 형식은 부호, 지수, 가수 순서로 비트들을 저장하므로, 정수 유닛을 통해서 부동소수점 수들을 비교하는 것이 가능하다. a의 지수가 b의 지수보다 크면 가수에 상관없이 a는 b보다 크다. 따라서 다음 두 코드 조각들의 의미는 동일하다.
if ( a < b ) // 부동소수점 비교 ... INTORFLOAT atmp, btmp; atmp.f = f; btmp.f = b; if (atmp.i < btmp.i) // 정수 비교 ...
부호 판정에서와 마찬가지로, 정수의 파이프라이닝이 더 우월하므로 정수 비교가 더 빠르다. 단 이 기법은 a와 b가 모두 음수인 경우에는 적용되지 않는다. 이는 부동소수점에서 지수와 가수 비트들이 정수처럼 2의 보수 형식으로 저장되는 것이 아니기 때문이다. 두 수 중 적어도 하나가 양인 것이 틀림없는 경우라면 이 기법이 두 수를 비교하는 가장 빠른 방법이다.
제한
게임 프로그래밍에서 하나의 값을 특정한 범위로 제한(clamping)해야 하는 경우는 흔히 생긴다. 특히 3D 프로그래밍이라면 수를 [0, 1] 범위로 제한해야 하는 일이 많다. 부동소수점 수 f를 0으로 제한하는 것(즉 f<0이면 f=0)은 부호 비트를 하나의 마스크로 만드는 식으로 처리할 수 있다. 다음 코드를 보자.
INTORFLOAT ftmp; ftmp.f = f; int s = ftmp.i >> 31; // 부호 비트 마스크를 만든다. s = ~s; // 마스크의 비트들을 뒤집는다. ftmp.i &= s; // ftmp = ftmp & mask f = ftmp.f;
s에는 f의 비트들을 오른쪽으로 31번 이동(shift)시킨 값이 들어간다. 이에 의해 32개의 비트들 모두 부호 비트로 채워진 마스크가 만들어진다. 이것을 NOT 시키면 f가 음수이면 0, 양수이면 1로 채워진 값이 된다. 다시 이것을 f와 AND 시키면 f는 변하지 않거나 0이 된다. 정리하자면, f가 음수이면 0이 되고, 양수이면 그냥 그대로 변하지 않는 것이다.
이 코드는 완전히 정수 유닛으로 실행되며, 비교나 분기(branching, 分岐)가 없다. 코드를 벤치마크해봤을 때, 부동소수점 비교화 제한에서는 18 사이클 정도가 소요되었으나, 정수 제한 방식에는 5 사이클 이하만 소요되었다(이 사이클들은 루프의 추가부담도 포함한 것임을 주의할 것).
양수를 0으로 제한하는 경우(f>0이면 f = 0)는 음수를 0으로 제한하는 경우보다 사용 횟수가 적지만, 마스크 비트들을 뒤집을 필요가 없으므로 기법 자체는 더 쉽다.
INTORFLOAT ftmp; ftmp.f = f; int s = ftmp.i >> 31; // 부호 비트 마스크를 만든다. ftmp.i &= s; // ftmp = ftmp & mask f = ftmp.f;
1로의 제한(f > 1이면 f = 1)은 1을 빼고, 0으로 제한하고, 다시 1을 더해서 수행한다.
INTORFLOAT ftmp; ftmp.f = f 1.0f; int s = ftmp.i >> 31; // 부호 비트 마스크를 만든다. ftmp.i &= s; // ftmp = ftmp & mask f = ftmp.f + 1.0f;
일반적으로, 어셈블리에서 조건부 load 명령을 사용하면 분기할 필요가 없어지므로(분기의 필요성이 존재하면 명령 파이프라인 안에서의 분기 예측 로직이 깨진다) 제한 연산의 속도가 올라가게 된다.
절대값
이건 쉽다. 부동소수점 수는 2의 보수를 사용하지 않으므로, 그냥 부호 비트를 0으로 설정하기만 하면 절대값을 얻을 수 있다.
INTORFLOAT ftmp; ftmp.f = f; ftmp.i &= 0x7fffffff; f = ftmp.f;
f가 0인지 비교할 필요가 없으므로 속도가 매우 빠르다.
사인 및 코사인을 위한 선형 참조 테이블
게임에서 삼각함수는 유용하게 쓰인다. 예를 들어서 거리나 각도를 계산한다던가, 원호를 만든다던가, 물결 메시를 움직이는 경우 등에서 삼각함수는 중요한 역할을 담당한다. 표준 math 라이브러리에는 모든 일반적인 삼각함수들이 포함되어 있으나, 매우 느리며, float이 아니라 double을 다루기 때문에 메모리도 많이 잡아먹는다. 게임의 경우 정밀도가 낮은 float을 사용해도 충분한 경우가 많다.
사인과 코사인 값을 효율적으로 얻고자 할 때 주로 쓰는 것이 참조 테이블(lookup table)이다. 일반적인 접근방식은 각도를 정수 색인으로 참조하고(예를 들면 360도 한바퀴를 0에서 1023으로 표현하는 등) 각 색인의 사인 또는 코사인 값을 고정소수점으로 계산하는 것이다. 그러나 이를 위해서는 게임 프로그래머가 사인과 코사인에 대한 라이브러리 구현을 이해해야 하며, 또 표준적인 라디안(radian) 각도 대신 인위적인 정수 색인을 사용해야 한다는 단점이 존재한다. 효율적인 색인을 위한 부동소수점 트릭을 이용하면, 삼각함수의 구현에 대한 세부를 알지 못해도 표준 라디안 각도를 받아들여서 부동소수점 값을 돌려주는 삼각함수 기능을 얻을 수 있다.
사인
목표는 이런 함수이다.
float fsin( float theta );
이는 참조 테이블을 이용해서 쉽게 구현할 수 있다. 0에서 2pi를 256 단계로 나눠서 저장하는 참조 테이블을 만드는 것은 간다하다. 루프로 i 값을 증가시키면서 다음의 코드를 수행하면 된다.
sintable[i] = (float)sin((double)i * 2.0*3.14159265/256.0)
i를 0에서 255까지 변화시켜 가면서 sintable 배열을 채우면 해상도가 256이며 float의 정밀도를 가지는 사인값을 담는 사인 참조 테이블이 생긴다.
fsin에서 할 일은 매개변수로 주어진 float 값을 0에서 255 사이의 정수 색인으로 바꾸고 그 색인에 해당하는 float 값을 돌려주는 것뿐이다.
float fsin( float theta )
{
i = (unsigned int)(theta * 256.0f/
(2.0f*3.14159265f));return table[i];
}
그러나 이 구현은 두 가지 문제를 가지고 있다. 우선 이 함수는 느린 float->int 변환을 수행하며, 두 번째로 theta가 범위 [0, 2pi) 바깥이면 정수 색인이 배열의 범위를 넘어가게 된다.
두 문제를 해결한 버전은 다음과 같다.
#define FTOIBIAS 12582912.0f // 1.5 * 2^23
#define PI 3.14159265f
float fsin( float theta )
{
int i;
INTORFLOAT ftmp;
ftmp.f = theta * (256.0f/(2.0f*PI)) + FTOIBIAS;
i = ftmp.i & 255;
return table[i];
}
이 버전은 앞에서 이야기한 부동소수점 바이어스 트릭을 이용해서 빠른 부동소수점-정수 변환을 수행한다. 또한 변환된 정수를 255로 마스킹하므로 색인이 배열의 범위 안에서만 순환된다. 단 f가 2^22를 넘으면 float->int 변환 트릭이 실패하므로, 주기적으로 f를 감소시켜서 [0, 2p) 범위 안에 들어가도록 해야 할 필요는 여전히 존재한다.
이 버전의 fsin은 펜티엄 II에서(모든 코드와 데이터가 기본 캐시에 들어있다고 할 때) 약 10 사이클을 소비하는데, 이는 표준 math 라이브러리의 sin이 거의 140 사이클인 것에 비하면 엄청난 향상이다(sin이 하드웨어 FPU의 사인 명령을 사용한다는 점을 생각하면 더욱 그렇다).
256 항목의 부동소수점 참조 테이블은 1K의 메모리를 차지하는데, 이 정도면 내부 루프 안에서 캐시에 안전하게 머무를 수 있는 크기이다. 항목이 256개이므로 이 테이블에 의한 사인 값의 정확도는 8 비트이다. 최악의 경우에서의 오차는 참조 테이블을 분석함으로써 알아낼 수 있다(부록 CD의 코드를 참고할 것). 참조 테이블의 크기가 클 수록 정확도가 올라가나, 캐시 적중률이 낮아지므로 속도는 떨어진다.
코사인
코사인 함수도 따로 참조 테이블을 만들어서 사인 함수와 동일한 방법으로 구현하면 된다. 그러나 cos(q) = sin(q + pi/2)라는 성질을 이용하면 사인과 코사인이 같은 참조 테이블을 공유하게 만들 수 있다. 참조 테이블 색인을 만들 때 256/4(pi/2 는 25도에 해당하므로)를 더하면 되는 것이다. 다음 코드가 이를 구현하는 예이다.
float fcos( float theta )
{
int i;
INTORFLOAT ftmp;
ftmp.f = theta * (256.0f/(2.0f*PI)) + FTOIBIAS + 64f;
i = ftmp.i & 255;
return table[i];
}
상황에 따라서는 동시에 사인과 코사인 값을 모두 구하는 것이 유용할 때가 있다. 그런 경우 하나의 함수 안에서 사인 값을 구하고, 그 때 쓰인 색인에 64를 더하는 식으로 코사인 값을 구하게 되면 성능이 더욱 향상될 것이다. 마찬가지로, 여러 사인들과 코사인들을 한 번에 구해야 하는 경우라면 불필요한 반복 계산을 줄이는 방향으로 코드를 수정하면 된다.
제곱근에 대한 대수적 최적화
제곱근(square root)은 거리 계산이나 벡터 정규화, 이차방정식의 해 구하기 등에서 흔히 쓰인다. FPU에도 제곱근을 구하는 명령이 있긴 하지만, 펜티엄 II CPU에서 표준 C 라이브러리의 sqrt 함수는 여전히 80 사이클 정도를 소비한다. 따라서 최적화를 시도할 먹이감으로 충분히 선정될 만 하다.
제곱근 최적화 역시 부동소수점 비트들을 이리 저리 조작하는 방식으로 이루어진다. 제곱근은 지수에 관련된 것이며 가수와는 상관이 없기 때문에, 지수 비트들만 적당히 조작하면 제곱근을 얻을 수 있다. 부동소수점의 제곱근에 관련된 공식들은 다음과 같다.
f = 1.m x 2e
sqrt(f) = sqrt(1.m x 2e) = sqrt(1.m) x 2e/2
이들을 자세히 보면, 가수는 그대로 놔두고 지수만 2로 나누면 된다는 것을 알 수 있다. 그러나 지수는 정수이므로, 지수가 홀수이면 2로 나눴을 때 하위 비트를 잃게 된다. 이 문제는 지수의 하위 비트를 가수로 넘겨줌으로써 해결할 수 있다. 결론적으로 해답은 바로 다음과 같은 공식이 된다.
sqrt(f) = sqrt(1.m x 2e0) x 2[e/2]
여기서 e0은 지수의 하위 비트이다.
사인에서와 마찬가지로 제곱근도 256 항목의 테이블을 만들어서 참조하는 방식으로 구현할 수 있다. 이 때 테이블에는 가수만 담아두고, 지수는 비트 조작을 통해서 얻으면 된다.
float fsqrt( float f )
{
INTORFLOAT ftmp;
unsigned int n, e;
ftmp.f = f;
n = ftmp.i;
e = (n >> 1) & 0x3f800000; // 지수를 2로 나눈다.
n = (n >> 16) & 0xff; // 테이블 색인은 e0+m22-m16
ftmp.i = sqrttable[n] + e; // 결과들을 합한다.
return ftmp.f;
}
테이블 색인은 가수의 상위 비트들과 지수(e0)의 하위 비트를 조합한 것이다. 참조 테이블은 미리 계산된 제곱근의 가수를 담고 있다.
제곱근의 지수는 f의 지수를 오른쪽으로 1비트 이동시키면 얻을 수 있다(결과적으로는 2로 나누는 것임). 지수는 바이어스된 것이므로 1비트 이동시키면 결과적으로는 지수뿐만 아니라 바이어스 또한 2로 나눠지게 된다. 이는 원치 않는 결과이므로, sqrttable의 항목에 추가적인 인수를 더함으로써 지수를 다시 바이어스시켜야 한다.
이 fsqrt 함수는 펜티엄 II CPU에서 약 16 사이클을 소모하는데, 이는 표준 C 라이브러리의 구현보다 5 배 정도 빠른 것이다. 물론 이것은 모든 것들이 캐시 안에 들어있다는 가정 하의 이야기이다.
알고리즘에 대한 좀 더 상세한 설명은 부록 CD의 예제 코드를 참고하기 바란다.
임의의 함수의 최적화
하나의 매개변수를 가지는 임의의 부동소수점 함수를 생각하보자.
y = f(x)
앞에서 살펴 본 기법들을 통해서, 일반적인 함수에 대한 테이블 기반 최적화의 두 가지 기본적인 방법을 배울 수 있다. 사인과 코사인의 경우, x의 값은 알려진 범위에 대해 선형적으로 수량화(quantize)되며, y를 참조하기 위한 테이블 색인으로 쓰인다. 제곱근의 경우, x의 값은 대수적으로 수량화되며 어떠한 하나의 값(그 즉시 y 값이 되는 것이 아니다)을 참조하기 위한 테이블 색인으로 쓰인다. 그 하나의 값은 x의 지수의 함수에 의해 비례되며, 그 결과로 최종적인 y의 값이 나온다.
선형적 접근에서, 하나의 부동소수점 수는 재비례 된 후 하나의 정수로 변환되며, 그 정수는 선형 수량화를 통해서 하나의 참조 테이블 색인이 된다. 이는 정수 참조 테이블과 매우 비슷한 간단한 기법으로, 다른 점이라면 부동 소수점 값을 정수로 효율적으로 변환하기 위해 약간의 트릭을 사용하는 것 뿐이다. 대수적 접근의 경우에는 부동소수점 비트 패턴을 직접 테이블 색인으로 사용함으로써 대수적인 수량화를 수행한다.
이 두 기법을 일반화하면 임의의 함수에 대한 최적화를 구현할 수 있다. 선형적 수량화를 사용할 것이냐 대수적 수량화를 사용할 것이냐는 함수의 성격에 따라 달라진다.
선형적 수량화
앞에서 이야기한 fsin 함수는 선형적 수량화를 통한 최적화의 틀로 쓰일 수 있다. 어떤 함수의 정의역(x의 범위)이 고정되어 있다고 하자(즉 x E [A, B) ). 그러면 그 범위를 균일하게 포괄하는 하나의 참조 테이블을 만들 수 있으며, 그 범위 안의 x를 테이블에 대한 적절한 색인으로 만들 수 있다. 그렇다고 할 때 최적화된 함수 f는 다음과 같은 모습일 것이다.
#define FTOIBIAS 12582912.0f // 1.5 * 2^23
#define TABLESIZE 256
#define INDEXSCALE ((float)TABLESIZE / (B A))
float flut( float x )
{
int i;
INTORFLOAT ftmp;
ftmp.f = x * INDEXSCALE + (FTOIBIAS A * INDEXSCALE);
i = ftmp.i & (TABLESIZE 1);
return ftable[i];
}
참조 테이블은 다음과 같은 식으로 초기화된다.
ftable[i] = f( (float)i / INDEXSCALE + A );
여기서 f는 완전한 정밀도를 가진 부동소수점 값을 돌려주는 "진짜" 함수이다. flut는 두 번의 부동소수점 연산(곱셈, 뺄셈)과 한 번의 정수 비트단위 마스킹, 그리고 한 번의 테이블 참조만으로 끝난다. 펜티엄 II CPU의 경우 약 10 사이클 정도가 소비된다.
인접한 두 테이블 항목들을 선형으로 보간함으로써(CPU 사이클이 약간 더 소비되겠지만) 정확성을 높이는 것도 가능하다. 일반적인 함수에 대한 이러한 최적화를 지원(정확성 향상을 추가적인 선형 보간도 포함되어 있다)하는 API가 부록 CD에 들어 있다.
대수적 수량화
선형적 수량화는 범위 [A,B)를 균일하게 다룬다. 함수에 따라서는 대수적 취급이 더 적합한 경우가 있다(제곱근 등). 기본적인 개념은, 부동소수점 x를 정수 범위로 변환하는 대신 부동소수점 표현의 비트들을 직접 테이블 색인으로 사용한다는 것이다. 기본적인 접근 방식은, 부호나 지수, 가수의 일부 비트들을 추출하고 조작함으로써 IEEE 1:8:23 형식의 부동소수점을 그 보다 덜 정밀한 또 다른 임의의 부동소수점 형식으로 변환하는 것이다.
제곱근 예에서는 8개의 비트들을 추출함으로써 0:1:7의 대수적으로 수량화된 값을 얻었다. 이 때 1 비트는 지수로, 7 비트는 가수로 사용되었다. 부호는 폐기했는데, 실수 공간에서 음의 제곱근은 정의되지 않기 때문이다. 0:1:7 형식은 8 비트의 가수(IEEE 표현에서는 항상 가수 앞에 1이 붙는다는 점을 기억할 것)와 1 비트의 지수로 이루어지므로, [1].0000000 x 20에서 [1].1111111 x 21 사이의 값들을 표현할 수 있다. 이는 [1,4)에 해당한다.
제곱근 함수의 작동 과정은 0:1:7 형식으로 수량화된 수에 대한 연산(한 번의 테이블 참조)과 지수에 대한 또 다른 연산으로 나뉘어진다. 그리고 추가적인 작업을 통해서 두 개의 개별적인 연산들을 최적화하고, 최종적으로 가수와 지수를 하나의 32 비트 부동소수점 수(이것이 함수의 결과이다)로 결합한다. 다른 함수들 역시 이러한 대수적 수량화 방법으로 최적화할 수 있다. IEEE 형식에서는 한 번의 이동과 한 번의 마스크 연산만으로도 지수의 하위 비트들과 가수의 상위 비트들을 뽑아낼 수 있다. 지수로부터 ebits 개의 비트들을 뽑고 가수로부터 mbits 개의 비트들을 뽑아내는 방법은 다음과 같다.
bits = (n >> (23 - mbits)) & ((1 << (ebits + mbits)) - 1)
이 코드는 수 n의 가수와 지수 중 원하는 만큼의 비트들을 수 n의 가장 오른쪽으로 밀어서 이동시키고, 불필요한 비트들을 없애기 위해(마스킹) AND 연산을 수행하는 것이다.
부호 비트 역시 손쉽게 조작할 수 있다. 매개변수가 항상 양임이 확실하다던가, 또는 함수의 결과가 항상 양임이 확실하다면 부호 비트는 무시할 수 있다. 결과의 부호가 매개변수의 부호와 같다면(즉 f(-x) = -f(x)), 부호 비트를 저장해 두었다 다시 복원시키기만 하면 된다.
매개변수 값이 특정 범위로 제한되어 있는 함수의 경우, 지수와 대수로부터 뽑아낸 비트들을 마스킹함으로써 직접 테이블 색인을 구할 수 있다. 예를 들어서 정의역이 [1,16)이라면 지수에서 2 비트, 대수에서 4 비트(예를 들자면)를 뽑아내면 된다. 그러면 0:2:4 형식의 비트들이 되는데, 이는 1.0000 x 20에서 1.1111 x 23 사이의 이진 값들을 의미하며, 십진수로는 1.0에서 15.5 사이가 된다. 이 비트들만 뽑아내면 그 즉시 64 항목의 테이블에 대한 색인이 되는 것이다. 이러한 연산은 단 몇 사이클로 수행할 수 있으므로 속도가 빠르다. 그러나 정밀도가 더 많이 필요하다면 테이블을 키워야 하며, 테이블이 어느 정도 이상 커지면 캐시 적중률이 떨어지게 된다.
또 다른 방법은 제곱근 예에서와 같이 지수와 대수 연산을 분해하는 것이다. 함수 f(x)를 다음과 같이 분해할 수 있다고 하면:
f(x) = f(1.m x 2e) = f1(1.m) x 2f2(e)
8 비트의 가수 m을 이용해서 f1을 256 항목의 참조 테이블로 근사하고(approximate), f2는 지수 e에 대한 정수 연산으로서 직접 계산할 수 있다. 본질적으로 이것이 제곱근 예에서 쓰였던 기법이다.
대수적 수량화는 강력한 도구이나, 함수마다 비트들을 조작하는 방식이 서로 다를 경우가 많다. 완전히 일반화된 방법이 항상 가능한 것은 아니나, 이 글에서 설명한 방법들이 특정한 최적화 문제를 해결하는 데에는 도움이 될 수 있을 것이다.
성능 측정
코드를 최적화할 때에는 최적화 전과 최적화 후의 성능을 세심하게 측정해야 한다. 이론상으로는 멋진 최적화 기법도 실제 구현에서는 캐시의 행동방식이라던가 분기 예측 실패, 컴파일러의 멍청한 코드 생성 같은 요인들 때문에 '안하느니만 못한' 결과를 낳을 수 있다. 뭔가를 변경했다면 정말로 성능이 향상되었는지를 꼭 짚어봐야 한다.
컴파일러 최적화 옵션들을 활성화시키는 것도 중요하다. 적당한 곳이라면 인라인 함수들을 사용할 것. 또한, 인라인 함수를 사용했거나 컴파일러 설정을 바꿨다면 그 결과를 측정해 봐야 한다.
코드를 벤치마킹할 때 컴파일러 최적화가 테스트에 방해가 되지 않도록 해야 한다. 코드를 디스어셈블해 보고 의도한 대로 코드가 만들어졌는지 자세히 점검해야 할 것이다. 타이밍이 중요한 부분이라면 루프를 돌려서 시간을 끄는 것도 유용한 방법이 될 수 있다. 그러나 컴파일러의 최적화에 의해 루프 내부가 컴파일에서 제외되어 버린다면 시간 측정 결과는 믿을 수 없게 되어버린다.
펜티엄 컴퓨터의 경우 rdtsc(read time stamp counter) 명령을 이용해서 현재의 CPU 사이클 카운트를 얻을 수 있다. 인텔은 이 명령이 결과를 얻기 시작하기 전에 두 번 더 실행된다고 경고하고 있다. 인텔은 또한 좀 더 일관적인 타이밍 결과를 얻기 위해서는 cpuid 처럼 명령 캐시를 비우는 명령을 사용하도록 권장하고 있다. 절대적 시간을 얻어야 하는 경우, 사이클 카운트를 프로세스의 실행 속도(MHz)로 나누면 초 단위 시간을 얻을 수 있다.
세밀한 성능 측정에서 가장 신뢰할 수 있는 수단이 바로 사이클 카운터들이다. VTune이나 TrueTime 같은 도구들도 고수준 프로파일링에 유용하다(PC의 경우). 어떠한 밴치마킹이든 메모리 행동 방식은 최대한 실제 상황과 같게 만들어야 한다. 메모리 병목 현상은 요즘 프로세서에서 성능을 떨어뜨리는 주범이기 때문이다. 캐시 역시 마찬가지이다. 벤치마크에서의 캐시 상태는 실제 상황과 최대한 비슷해야 한다. 벤치마크의 경우 실제 시간 측정에 들어가기 전에 대상 알고리즘을 몇 번 정도 실행해 줘서 캐시를 미리 채워두는 방법도 고려해 보기 바란다. 그러나 그런 방법으로도 항상 실제 상황이 정확하게 반영되는 것은 아니다. 가장 좋은 방법은 실제로 게임을 돌리는 도중에 직접 성능을 측정하는 것이다. 좀 더 신뢰할 만한 결과를 얻기 위해서는 인터럽트들을 비활성화시키거나, 또는 결과를 여러 번 추출하고 비정상적인 결과는 제외시키는 등의 방법을 사용할 수도 있을 것이다.
이 글에서 언급한 모든 사이클 결과들은 인텔 펜티엄 II 450-MHz 컴퓨터에서 얻은 것이다. 각 연산은 하나의 루프 안에서 1000 번 반복되었으며, 그 전에 함수들을 미리 실행해서 명령 캐시와 데이터 캐시를 미리 채워두었다. 사이클 결과에는 루프에 의한 추가부담도 포함되어 있다. 벤치마크에 쓰인 실제 코드가 부록 CD에 들어 있다.
이 글에서 이야기한 참조 기법들은 참조 테이블이 캐시 안에 남아 있는 경우에만 효과가 있다. 대체로 렌더링 파이프라인이나 역학(physics, 力學) 엔진 내부 루프의 경우라면 테이블이 캐시 밖으로 밀려나지 않을 것이다. 그러나 코드 여기 저기에서 함수(테이블을 사용하는)를 호출한다면 테이블이 캐시 밖으로 밀려날 가능성이 많다. 참조 테이블을 캐시 안에 유지시키기 힘든 경우라면, 다항식 근사(polynomial approximation, 多項式 近似. 이에 대한 내용은 [Edwards00]에 잘 소개되어 있다)처럼 연산이 많고 메모리 접근이 적은 기법이 더 효율적일 수도 있다.
결론
이 글에서는 부동소수점 최적화라는 빙산의 일각만이 소개되었을 뿐이다. 이 글은 참조 테이블 기법을 주로 다루고 있다. 참조 테이블 기법을 사용하면 상당한 성능 향상을 얻을 수도 있지만, 캐시의 작동 방식을 주의해야 하며, 항상 구체적인 성능 측정도 잊지 말아야 한다. 때로는 좀 더 계산적인, 그리고 메모리를 덜 건드리는 방법(다항식 근사 등)을 통해 더욱 빠른 결과를 얻을 수도 있다. 이 글에서 살펴 본 기법들은 여러 가지 방식으로 확장, 개선될 수 있다. 또한 다른 기법들도 탐구해 볼 수 있을 것이다. 어떤 유명한 책의 제목에서처럼, 코드 최적화 기술에는 선(禪)이라는 것이 존재하며, 이 글처럼 짧은 개요를 통해서는 모든 가능성들을 가늠하기가 불가능하다.
참고자료
- [Abrash94] Abrash, Michael, Zen of Code Optimization, Coriolis Group, 1994.
- [Edwards00] Edwards, Eddie, "Polynomial Approximations to Trigonometric Functions", Game Programming Gems, Charles River Media, 2000. 번역서는 "삼각 함수들에 대한 다항식 근사", Game Programming Gems, 정보문화사, 2000.
- [Intel01] 부동소수점 유닛과 FPU 데이터 형식에 대한 Intel 웹 페이지. PC를 중점으로 하고 있으나 기타 다른 IEEE 호환 컴퓨터에도 적용될 수 있다. http://developer.intel.com/design/intarch/techinfo/Pentium/fpu.htm
- [Lalonde98] Lalonde, Paul, and Dawson, Robert, "A High Speed, Low Precision Square Root", Graphics Gems, Academic Press, 1998.
'Development > C/C++' 카테고리의 다른 글
| [64비트 윈도우 프로그래밍] ① 32비트 프로그램을 엄호하라 (0) | 2011.08.13 |
|---|---|
| /LARGEADDRESSAWARE (Handle Large Addresses) (0) | 2011.05.23 |
| Windows XP 및 Windows Server 2003의 64비트 버전에서 32비트와 64비트 메모리 아키텍처 비교 (0) | 2011.05.23 |
| wsprintf 에서 __int64 표현 (0) | 2010.11.17 |
| 부동 소수점 연산의 정밀도와 정확도 (0) | 2010.11.16 |
