1. loop 최적화
loop unrolling 이 효과를 보는 이유는 다음과 같습니다.
반복문의 경우, 의도한 실제 동작 외에 반복의 증가 및 종료체크가 더 큰 오버헤드를 갖는 다는 것입니다.
memcpy() 를 예로 들겠습니다.
void *memcpy(void *dst, void *src, size_t n)
{
unsigned char *pDst = (unsigned char *)dst;
unsigned char *pSrc = (unsigned char *)src;
for(int i = 0 ; i < n ; ++i)
pDst[i] = pSrc[i];
return dst;
} |
ARM 컴파일러의 경우, 위의 코드를 아래와 같이 해석합니다.
void *memcpy(void *dst, void *src, size_t n)
{
@ r0 = dst
@ r1 = src
@ r2 = n
1: cmp r2, #0 @ if ( cnt == 0 )
2: bxle lr @ return
3: mov ip, #0 @ i=0
4: loop :
5: ldrb r3, [ip, r1] @ r3 = src[i]
6: strb r3, [ip, r0] @ dst[i] = r3
7: add ip, ip, #1 @ i++
8: cmp ip, r2 @ if ( i==cnt )
9: bne loop @ goto loop;
10: bx lr @ return
} |
※ 위의 코드는 ARM asm 이고, AT&T 표기법입니다. ( @ 는 주석입니다.)
ARM 의 경우, argument가 4개 이하일때, arg 는 r0~r3 을 이용하여 passing 됩니다.(ATPCS 참조) r0=dst, r1=src, r2=n
여기서 중요한 부분은...
반복마다 동작해야 하는 실질적인 memcpy 동작(5, 6) 보다도, 범위체크 및 종료판단을 위한 오버해드가 (7,8,9)가 더 많은 실행싸이클을 요구한다는 것입니다. 또한, 이런 오버해드는 반복수가 커질 수록 더 커집니다.
때문에, loop 최적화가 효과를 볼 수 있는 것입니다.
(흠... 자세하게 설명하자니, 귀차니즘이.... 좀 더 자세한 설명은 loop unrolling 및 아래의 링크를 참조하시기 바랍니다.
)
2. 부동소수점
부동소수점이 정수연산에 비해 많은 시간이 소요되는 이유는 normalization 때문입니다.
부동소수점에서 부동이란... "움직이지 않는다"가 아니라, "부유한다"라는 의미입니다.
즉, 0.00001234 와 0.1234 는 동일한 magnitude 를 갖고, 소수점의 위치만 다르게 표현됩니다.
( 유효자리숫자가 고정된 상태에서, 소수점만 떠 다니는 형태입니다.)
때문에, 가감승제 연산을 위해서는 normalization 과정이 필요하고, 이에 대한 결과값 저장에는 denormalization 필요 합니다.
여기서 오버해드가 발생하는 것입니다.
(흠... 자세하게 설명하자니, 귀차니즘이.... 좀 더 자세한 설명은 구글신께 "부동소수점"을 검색해 보시기 바랍니다,)
물론 이런것들이, "부동소수점 전용 H/W 에서 처리 되므로 충분히 빠르다"라고 할 수 도 있지만....
중요한 것은, H/W가 발전하여 부동소수점연산이 빨라지는 만큼, 정수연산은 그보다 훨씬 더 빨라진다는 것입니다.
때문에, 정수연산의 속도를 따라올 수 없습니다.
또한, 이것은 곧, 해당 문제가 고정소수점으로 처리할 수 있는 문제라면, 고정소수점이 훨씬 빠르다는 것입니다.
3. 초월함수
초월함수란... 가감승제만으로 값을 구할 수 없는 함수를 초월함수라고 합니다.
예를 들어, x에 관한 2차 방정식 ax^2 +bx +c 는초월함수가 아닙니다만, sin(x) 는 초월함수 입니다.
주로 지수함수, 삼각함수가 초월 함수에 해당합니다.
이러한 초월함수의 경우, 컴퓨터에서는 값을 구하는 방법이 마땅치 않습니다.
이때, 사용하는 방법이 테일러 급수 입니다. 테일러 급수를 사용하면, 초월함수를 비초월함수로 나타낼 수가 있으므로, math library 는 최적화된 테일러 급수를 통해 초월함수를 계산합니다.
그렇다고 하더라도, 무한급수의 경우 부동소수점에대한 수많은 나눗셈,덧셈이 필요하므로 연산량이 많습니다.
( sin(x) 에대한 테일러 급수를 구글링해 보시기 바랍니다. )
( CPU 중에는 H/W divider 가 없는 것도 있습니다. 이런 경우, S/W emulation 을 통해 나눗셈을 구현하는데, 이때 보통 20~100싸이클정도가 추가로 소요됩니다. )
때문에, sin, cos 에 대한 lookup table 이 상당한 효과를 발휘할 수 있는 것입니다.
4. I/O
전산쪽의 파일처리론을 들어본 분들은 아시겠지만....
일반적인 컴퓨터 시스템의 연산속도 비율은 통계적으로 다음과 같습니다.
CPU : MEMOEY : I/O = 1 : 10 : 1000
CPU의 덧셈연산이 1이 걸린다고 하면, 메모리 access 는 10, I/O 는 1000 의 시간이 소요된다는 것입니다.
이것은, I/O 한번을 줄이는것이 CPU 연산1000 번을 줄이는 효과이므로, 최적화 대상에는 I/O 가 포함되어야 한다는 것입니다.
물론, 최적화 관점에서 파일처리와 이미지 프로세싱과는 좀 거리가 있습니다.
이미지 프로세싱은 I/O 보다는 CPU 연산이 훨씬 많은 응용이므로, I/O 보다는 CPU 최적화가 더 관건입니다.
하지만, I/O가 상당히 큰 병목이라는것을 간과해서는 안됩니다.
하지만, 가장 드라마틱한 최적화는 수식 최적화라고 봅니다.
아주 간단한 예를 들어, 1부터 N 까지 더하는 프로그램을, 제 아무리, loop 최적화 및 여타의 최적화를 한다고 하더라도
N(N+1)/2 보다 빠르게 할 수 는 없습니다.
수학적 short-cut 보다 빠를 순 없습니다.
6. 병렬화
요즘들어, 가장 손쉬운 최적화 중에 하나가 병렬화 입니다.
독립된 job 이라면, 위에서 설명한 고리타분한 지식없이도 아주 손쉽게, 병렬화로 큰 이득을 볼 수 있습니다.
( 그냥 해당, job 을 CPU 갯수로 나눠만 주더라도 큰 효과를 봅니다. )