[SP] Optimizing a Program with a hardware dependent perspective

※ 질문/내용오류/공유할 내용이 있다면 jinkilee73@gmail.com으로 메일 주세요 :-)

이번 블로깅에서는 하드웨어에 dependent 한 최적화를 해보자. 하드웨어 dependent한 최적화란 무엇인가? 즉, 특정 하드웨어에서 적용가능한 최적화 기법이라는 뜻이다. 에이~ 그럼 의미가 없잖아? 라고 생각하는 사람이 있을 것이다. 아니라고 말도 못 하지만 꼭 그렇다고 말도 못 한다. 왜냐하면 요즘 하드웨어 구조가 뭐 거기서 거기라.. 왠만하면 앞으로 소개할 방법으로 개선이 된다고 한다. 자 어떤 방법이 있는지 알아보자.

우선, 예제는 이전 블로그에서 사용했던 예제를 가지고 사용해보자. 이전의 hardware independent 한 최적화에서 가장 효율이 좋았던 코드는 아래와 같다.

이 코드를 또 어떻게 최적화할까? 루프 한번 돌 때 두번의 연산을 해볼까? 그러면 for문에서 하는 i < length 비교하는 것과 i++하는 회수가 반이 줄겠지?

그래서 이렇게 한번 바꿔봤다. 같은 코드지만 for 문 안에서 i+=2로 바꿨다. 그리고 switch문을 통해서 나머지 부분을 수행해주었다. (C code 자체에 대한 이해는 독자들에게 맞기겠다.) 이렇게 해서 돌려보면 평균적으로 35000us 의 속도를 내던 프로그램이 25000us로 줄어든다. 결국 for 문을 돌때 계산되는 overhead 등을 반으로 줄인 효과이다. 그렇다면 i+=3, i+=4, i+=5 등을해서 더욱이 개선을 할 수 있지 않을까? 한번 해보자.

loop를 10000000번 돌기 때문에 loop 한번당 3개의 연산을 하면 마지막에 하나가 남는다. 따라서 switch 문에 case1만 해줬다. 원래 제대로 된 프로그램이라면 case 0과 case 2가 있어야겠지만 생략하겠다. 이렇게 했을 경우 21000us로 또 속도 개선이 나타난다. 그리고 아래의 표를 보자.

	i+=3	i+=4	i+=5
속도	21000us	18000us	17000us

개선이 나타난다. :-) 특히나 i+=5같은 경우 거의 i++와는 두배의 효율을 보인다. 이러한 방법으로 개선해나가는 방법을 loop unrolling이라고 한다.

그런데 loop unrolling이 항상 효과를 보이는 것은 아니다. float 연산에 대해서 * 연산을 할 때는 효과가 거의 없다. 그 이유를 알기 위해서 우리는 지금껏 열씸히 배운 어셈블리 언어를 이용할 것이다. 아래의 어셈블리 코드는 위에 있는 2-way(i+=2) loop unrolling C코드의 for문에 해당한다.

(아래의 분석한 부분은 순수히 저의 허접한 실력으로 분석한 내용이니 조금은 의심을 가지고 봐도 됩니다.)

점프하는 부분 전부 빼고 순수히 for 문 안에서의 연산을 하는 부분만 고려하여 119번째 줄부터 126번째 줄까지 봐보자. 어셈블리 언어로 보면 복잡하니까 아래와 같이 그림으로 봐보자.

각각의 레지스터 값에 대한 각각의 명령어의 효과를 나타낸 것이다. 예를 들어 flds    (%eax) 명령어는 %eax로부터 값을 로드한 후 그 값을 mov 명령어를 통해서 복사하는 것이다. 따라서 load 명령어가 %eax를 operand로 갖고 그 결과가 mov 연산자로 들어가며 그 결과는 st0~7 레지스터 스택에 쌓이는 것이다.

여기서 잠깐, 위 코드에서 우리가 안 배운 레지스터와 명령어가 있다. st0, st1, ... , st7 이런 레지스터 배운 적 없다. flds? fmuls? fmulp? 배운적 없다. 이 부분에 대해서는 나중에 설명하도록 하자. 지금 다루는 내용을 이해하기 위해 필수적으로 알아야 할 내용은 아니라고 본다. 그래도 궁금한 사람은 아래의 링크를 따라가서 찾아보면 된다.

st0~7 : http://cs.smith.edu/~thiebaut/ArtOfAssembly/CH14/CH14-3.html

flds, fmuls, fmulp : http://cs.smith.edu/~thiebaut/ArtOfAssembly/CH14/CH14-4.html#HEADING4-104

위의 그림은 명령어를 그대로 해석해놓은 것이기 때문에 따로 설명은 하지 않겠다. 아무튼 저 그림에서 오른쪽의 명령어를 보기 좋게 왼쪽으로 끌면 아래와 같은 그림이 나온다.

이제 본격적으로 왜 성능 개선이 없는지 이야기를 해보자. 위의 그림은 아까 말했다시피 for 문 안의 연산 부분이다. 즉 위에서 밑으로 연산들을 타고 내려가면서 data[i]에서 data[i+1]을 거쳐서 가장 밑에 있는 data[i+2]로 가는 것이다. 여기에서 st0~7 레지스터를 보자. data[i] ~ data[i+2]까지 갈 때 mul 연산이 두 개이다. 첫번째 mul 연산의 결과가 끝나야 그 값으로 두번째 mul 명령어를 수행할 수가 있다. 즉, 병렬 연산이 불가능하다는 것이다. (컴퓨터 구조에서 파이프라인 구조를 공부하면 이 부분을 자세하게 다룰 수 있다.)

그러면 어떻게 하면 병렬로 연산이 가능하게 만들 수 있을까? 사실 이 부분을 실패했다.-_- 포스팅이 여기서 끊키고 몇 일동안 정체되어있었던 이유가 바로 그것이었다. 내가 뭘 알아야 포스팅을 하지?! 자, 다시 본론으로 들어와서. 프로그래밍의 효율이 다른 방법으로 좋아지기는 했다. 아래의 코드를 보자.

사실 효율이 그렇게 좋아지지는 않고 조금 좋아졌다. 그 이유를 생각해보자. for 문 안을 보면 acc 하나가 아니라 acc1과 acc2 두개를 사용하여 따로 계산을 하고 있다. 그리고 마지막에 *dest = acc1 OP acc2 로 마무리를 해주는 방식이다. 이렇게 하면 다음의 어셈코드가 나오게 된다.

가장 눈에 띄는 변화는 곱하기하는 함수의 변화와 flds 함수를 fmulp를 하기 전에 두 번 수행한다는 것이다. (사실 그 두 개 빼고는 변한게 없다.) 역시 어셈블리 코드는 한 눈에 보기는 어렵다. 그림으로 바꾸면 아래와 같이 바꿀 수가 있다.

추측하건데, 프로그램의 성능이 개선된 이유는 곱하기 함수의 종류 때문이라고 생각한다. 이전의 버전에서는 어셈블리코드에서 곱하기 함수가 fmuls와 fmulp였다.

fmuls        -16(%ebp)

fmulp        %st, %st(1)

반면, 이번의 코드에서는fmulp가 두 개이다.

fmulp        %st, %st(1)

fmulp        %st, %st(1)

무슨 차이일까? 바로 메모리 접근 회수의 차이라고 본다. 이전 버전에서 fmuls를 할 때는 -16(%ebp)라는 메모리 접근을 하는 반면, 현재의 combine1함수에서는 레지스터에 있는 값을 직접 사용하여 곱하기를 하는 것이기 때문에 곱셈 속도가 미약하지만 개선되는 것이 아닌가 싶다.

그런데 사실 내가 바랬던 개선 원인은 이것이 아니다. 내가 원했던 개선 원인은 새로운 레지스터, 예를 들어 %ebx,를 사용하여 첫 번째 곱셈이 끝나기 전에 두 번째 곱셈을 실행할 수 있도록 하는 것이다. 즉 병렬 처리를 통한 개선이었다. 그런데 floating point 연산을 리눅스에서는 꼭 st0~7 레지스터를 사용하여 연산을 해버리니 병렬 처리가 불가능했던 것이다.

아무튼 중요한 점은 변수 하나를 더 써서 레지스터를 더 많이 활용할 수 있는 효과를 낼 수 있다면 프로그램 개선을 기대할 수 있다는 사실이다.

p.s. 이래저래 포스팅을 마무리 할 수는 있게 되었다. 뭐랄까? 이 찝찝하면서도 시원한 기분은...