상세 컨텐츠

본문 제목

BigFloat로 Pi를 구해보자-8. 어셈블리어로 최적화하기

프로그래밍/Multi precision

by ∫2tdt=t²+c 2012. 11. 5. 00:54

본문


요즘 컴파일러들은 매우 똑똑합니다. 어지간한 코드는 알아서 최적화시켜주지요. 그래서 대부분의 경우에는, 힘들여 어셈블리어 코드를 써서 최적화해놔도 컴파일러에 의한 최적화보다 못한 경우가 많습니다.

하지만! 이렇게 큰 수끼리 연산을 하는 코드는 최적화할 가능성이 많습니다.


우리가 예전에 덧셈과 뺄셈을 어떻게 구현했는지 한번 떠올려볼까요?(2. 덧셈, 뺄셈 구현하기)


긴 정수의 덧셈을 다음과 같이 구현했었죠.

1. 먼저 두 정수를 더한다.

2. 더한 결과가 원래 정수보다 작으면 받아올림이 발생한거다.

3. 윗 자리를 더할때 받아올림된 1도 같이 더해준다.


이를 위해서 n자리의 정수라면 총 n번의 덧셈과 n번의 비교와, 받아올림이 있다면 n번의 추가적인 덧셈이 필요했습니다. 즉 최악의 경우 3n번의 덧셈/비교 연산이 필요했다는 얘기지요.

하지만 x86 CPU에는 받아올림 플래그(carry flag, CF)라는 것이 있습니다. 두 수끼리 더해서(혹은 빼서) 그 결과가 오버플로우(overflow)가 발생하면 세트가 되고, 그렇지 않으면 클리어되는 플래그이지요.

또한 두 수끼리 더할 때 CF가 세트되어있으면 1을 더 더해주는 adc instruction도 있습니다. 이를 이용하면 굳이 위의 방법처럼 복잡하게 받아올림을 구현하지 않고도 간단하게 연산을 할수 있지요.

(설명이 장황해지는 것을 막기위해서 매우매우 기초적인 CPU구조와 어셈블리어는 알고 있다고 가정하겠습니다.)


자 이제 한 번 코드를 볼까요? (편의상 MSVC 스타일의 인라인 어셈블리 문법을 사용했습니다. 제가 딱히 마소빠라서 그런게 아니라, 그냥 익숙해서... )



몇가지 x86 instruction 소개가 있어야겠네요.


lodsd : esi 레지스터가 가리키는 지점에서 dword(4바이트)를 읽어와 eax에 넣는다. (c스타일로 쓰자면 eax = *esi;인셈)

명령어를 수행한 후에는 esi를 4바이트 뒤로 이동한다.(esi = 4)

stosd : edi 레지스터가 가리키는 곳으로 eax에서 dword(4바이트)를 읽어와 넣는다. (c스타일로 쓰자면 *edi = eax;인셈)

명렁어를 수행한 후에는 edi를 4바이트 뒤로 이동한다. (edi = 4)


adc : CF를 반영하여 덧셈 연산을 한다. (adc dest, src; 는 dest = src (CF ? 1 : 0) 의 의미인셈.)

pushf : 스택에 플래그 상태를 저장한다.

popf : 스택에 저장해뒀던 플래그 상태를 가져온다.


std : DF(방향 플래그)를 설정한다. 이게 설정되면 lodsd, stosd 명령어에서 edi, esi가 뒤로 이동하는게 아니라 앞으로 이동한다.

cld : DF를 해제한다.



연재2 에서 구현했던 두 RRU32배열을 더해주는 함수입니다.


제일 앞에서 std를 하는 이유는, 우리가 처음에 정의내리기를 배열에서 뒤로 갈수록 아래자리를 표현한다고 그랬기 때문이지요. 덧셈은 제일 아랫자리에서부터 위로 올라오면서 해야하므로, DF를 세트하여, esi, edi가 거꾸로 움직이도록해야합니다.

불행히도 sub 명령어는 CF를 변경시키므로, 만약 pushf, popf를 하지 않는다면 CF가 맘대로 바뀌어 원하는 결과가 안나오겠지요.

이건 실은 최적화가 전혀 안된 코드라고 할 수 있습니다. 매번 반복할때마다 sub도 해야하고, pushf, popf까지... 이는 엄청난 비용입니다. 고전적인 최적화 방법중에 루프문 풀기(Loop Unrolling)이 있는데, 이는 반복문을 반복하는 대신 이를 풀어써서 반복하는데 사용되는 연산을 최소화하는 것입니다. 지금은 이를 사용하기에 딱 좋은 상황이죠. 먼저 최적화시킨 코드를 볼까요?



코드가 매우 길어졌지요... 개략적인 구조는 다음과 같습니다.

큰 줄기는 32번을 한 단위로 반복하는 것입니다. 그러면 32번 덧셈할 동안, popf 한번, pushf 한번, sub 한두번 하면 되니깐요. 단순 명령어 수로 비교해도 최적화 이전에 루프문 32번 도는것은 명령어수가 7*32 = 224개인데 비해, 32번을 한 세트로 실행하는 코드는 명령어수가 100개 밖에 되지 않습니다.


게다가 현대 CPU의 파이프라인 구조 상 분기예측이 실패할 경우에는 IPC(사이클 당 명령어 실행수)가 급격하게 떨어지므로, 분기가 적어야 효율이 높아집니다.


근데 문제는 len이 32의 배수가 아닐 경우는 처리할 수가 없다는 것이지요. 그래서 1,2,4,8,16번 반복하는 경우를 작성해두고, 32로 나누어 떨어지지 않을 경우는 1,2,4,8,16을 조합하여 사용하는 것입니다. (32미만의 자연수는 1,2,4,8,16을 조합하여 표현할 수 있지요.)


test 명령어는 레지스터가 특정 비트를 가지고 있는지 확일할때 사용합니다. 이 명령을 이용해 먼저 len의 아래 5비트를 조사하고, 1,2,4,8,16번 중 적당한 곳으로 점프합니다. 그리고 그 다음부터는 32번을 세트로 반복하는 것이지요.


마찬가지 방법을 뺄셈에서도 적용할 수 있습니다. 받아내림을 고려하여 뺄셈을 수행하는 명령어는 sbb입니다.


i_adds함수에서 adc를 sbb로 바꾼 정도입니다.ㅋ


글이 길어지는 관계로 시프트 연산 최적화는 다음으로 패-스.

관련글 더보기

댓글 영역