[system programming] program optimization (compiler와 최적화 기법)

본 게시글은
서울대학교 데이터사이언스대학원 성효진 교수님의
데이터사이언스 응용을 위한 컴퓨팅 시스템 강의를
학습을 목적으로 재구성하였습니다

---

이번 시간에 정리할 내용은

프로그램 최적화에 관련된 내용이다

 

컴파일 언어에서는 컴파일러가 우리가 작성한 코드를

자체적으로 최적화를 해주는 역할을 한다

그렇다면 컴파일러는 어떤 방법으로 최적화를 진행할까?

또한 컴파일러 이외에

우리가 코드 레벨에서 코드를 작성할 때

어떻게하면 최적화된 코드를 작성할 수 있을까?

이 프로그램 최적화는 이와 관련된 내용이다

 

이런 컴파일러의 최적화 과정을 이해해야

우리가 어떻게 프로그램을 짜야하는지 알 수 있다고 한다

 

이번 시간에 배울 목차이다

 

 

우리가 보통 알고리즘을 공부할 때는

asymptotic complexity라고 해서

흔히 빅오 표기법으로 시간 복잡도를 계산한다

 

asymptotic complexity란

하드웨어의 요소를 고려하지 않고

우리가 해결하고자하는 문제 자체의 크기를 측정하는 것이다

따라서 하드웨어를 고려하지 않기 때문에 정확하지 못하다

내가 프로그램을 돌리는 컴퓨터의 하드웨어나

동일한 알고리즘을 어떤 코드로 작성하는지는

프로그램의 성능에서 굉장히 중요한 요소인데

asymptotic complexity는 이러한 점들을 고려하지 않는다

 

 

컴파일러에 대해서 간단하게 알아보자

 

컴파일러는 우리가 코드를 작성해서

실행하기까지의 모든 과정을 담당한다

 

위 ppt에서 보면 컴파일러가 하는 역할을

register allocation

code selection and ordering

dead code elimination

eliminating minor ineffciencies

이렇게 4가지로 구분하는데

여기서 register allocation + code selection and ordering은

최적화 과정은 아니다

 

register allocation은 우리가 이전에 배웠는데

어떤 변수가 몇 번 register에 갈지 정해주는 것이고

code selection and ordering도 앞에서 배웠는데

instruction의 순서를 변경해서 dependency를 최소화해주는 것이다

여기서 특히 code selection은 어떤 작업이냐면

같은 연산도 구현할 수 있는 instruction은 여러개일 수가 있다

거기서 cycle이 가장 작거나

가장 효율적인 instruction을 선별해서 수행하는 작업이다

 

dead code elimination과 eliminating minor inefficiencies가

컴파일러가 수행하는 최적화와 관련된 부분이다

말 그대로 사용되지 않는 코드를 제거하고

비효율적인 코드를 제거해주는 작업이다

 

생각해야할 점은 컴파일러 최적화를 한다고

알고리즘적인 성능이 좋아지는 것은 절대 아니다

따라서 프로그래머는 반드시

asymptotic한 성능을 먼저 좋게 만들어야한다

 

따라서 프로그래머가 수행할 수 있는

코드 레벨에서의 최적화와

컴파일러의 최적화가 조화롭게 결합되어서

좋은 성능의 프로그램이 나오게 되는 것이다

 

 

 

그렇다면 최적화라는 것은 정확하게 무엇일까?

사전적인 정의의 최적화에 대해서 알아보자

 

컴퓨터 시스템에서 말하는 최적화는 보통

improving the system performance..

이런 것들을 의미한다고 한다

effectiveness에 초점을 맞춘 최적화이다

 

보통 우리가 최적화라고 하면 단순히 실행시간을 줄여주는 것 정도로만 생각하는데

사실 최적화는 여러 가지 목표를 갖고 있다

대표적인 예시로 코드 사이즈를 줄이는 것이 있는데

임베디드 시스템의 경우 실행시간도 중요하지만

작은 메모리에서 돌아가는 코드를 작성해야하기 때문에

코드 사이즈도 최적화 목표 중에 하나로 들어간다

 

또한 요즘 중요하게 생각하는 최적화 목표는

파워와 에너지이다

성능은 빠른데 전력을 많이 소모하면

파워 budget 측면에서 불리할 수밖에 없다

 

하지만 우리는 우리가 한 이 기법이

optimal 하다는 것을 증명할 수는 없다

따라서 이러한 최적화 기법들은

수학적으로 증명하는 것이 아니고

더 최적에 가까운 솔루션으로 다가가는 과정이다

 

 

앞에서 말한 여러 최적화 목표이다

 

 

최적화에는 여러가지 대표적인 기법들이 있다

이런 것들에 대해서 구체적으로 살펴보자

 

대표적으로 다섯가지 방법이 있는데

세번째에 나와있는

compute it as few times as possible

이 부분이 굉장히 일반적이고 많이 사용되며

효과가 좋은 최적화 기법이라고 한다

앞에서 한 번 사용한 코드를 최대한 재사용해서

불필요한 연산을 줄이는 방법이다

 

네번째인

compute it with as little code space as possible

이 부분은 성능보단 코드 사이즈에 영향을 준다

이게 dead code elimination과 관련된 부분이다

 

 

그렇다면 우리는 컴파일러의 최적화에게

어디까지 기대할 수 있을까?

 

사실 컴파일러는 굉장히 보수적으로 최적화를 진행한다

컴파일러는 우리의 코드가 최적화 후에

다른 방식으로 동작하는 것을 용납하지 않는다

따라서 최적화 전과 후의 semantic이

반드시 동일하게 유지되도록 하며

코드가 바뀌지 않는다는 것을 증명할 수 없으면

컴파일러는 최적화를 진행하지 않는다

 

따라서 우리의 코드가 굉장히 복잡하다면

컴파일러 입장에서는 최적화를 위해 코드를 변경했을 때

안전한지 아닌지를 알 수가 없어서

최적화를 진행하지 않는다

따라서 코드를 복잡하게 짜게 되면 컴파일러가 할 수 있는 일은 줄어드는 것이다

 

또한 컴파일러는 파일 단위로 최적화를 진행한다

optimization option을 높여서 전체 파일을 대상으로 할 수는 있지만

많은 경우에는 그냥 파일 단위로 진행한다

link type optimization을 이용하면

전체를 대상으로 할 수는 있지만 거의 사용하지 않는다고 한다

 

 

 

그렇다면 이제부터 컴파일러가

구체적으로 어떤 방법을 통해

코드를 최적화시키는지 알아보자

 

 

첫 번째는 Arithmetic Simplication이다

이는 컴파일러가 굉장히 쉽게 할 수 있는 최적화인데

컴파일 타임에 이미 연산할 수 있는

단순한 연산들은 미리 해버리는 것이다

 

위 ppt를 보면

x + -1은 그냥 x - 1로 변경해서 실행해버리는 것이다

 

 

 

두 번째는 constant folding이다

 

실제로 저렇게 코드를 작성하는 경우는 잘 없지만

3 + 6과 같이 코드를 작성해놓으면

그걸 그냥 9로 자체적으로 계산해서 실행해버린다

그 이후에 우리가 코드를 작성할 때

원래는 변수였는데 이 변수 값을 알게되면

그냥 해당 변수의 상수값을 가지고

컴파일러가 미리 계산을 한다

이게 constant folding이다

 

하지만 주의해야할 점은

정수값일 때는 계산결과가 똑같은데

floating point일 경우

runtime 계산값과 조금 다른 값이 나올 수 있다

 

 

 

그 다음은 constant propagation이다

위와 같은 상황에서 x = 9가 되었는데

뒤에서 x가 사용되는 곳이 있으면

모든 x에 상수값을 대체시킨다

 

 

위 코드를 실행시키면서

이전에 했던 constant folding을

다시 반복해서 시키는 것을 보여주는 slide이다

 

 

 

다음은 strength reduction이다

 

앞의 비트표현 수업 내용에서 배웠는데

multiple, divison 연산은

shift 연산으로하면 훨씬 더 빠르고 간편하다

 

따라서 위의 ppt slide같은 경우가

가장 많이 사용되는 경우인데

8을 곱하는 대신에 왼쪽으로 3번 shift를 해주었다

 

보통의 경우 실제로 multiple 연산이

cycle 수가 더 많이 걸리는 연산이라

shift로 변경하면 1 cycle 이내에 가능해지지만

이게 얼마나 효율적인지는

하드웨어 dependent하다

 

 

다음은 copy propagation이다

 

어떤 변수를 처음 할당한 다음

그 변수를 계속 할당해서 사용하는 것이다

 

위 ppt 예시를 잘 보면

위 코드를 정석대로 실행하기 위해서는

x도 레지스터에 할당해야하고

y도 레지스터에 할당해야한다

 

그런데 코드를 봤더니 x랑 y가 동일하고

뒤에가서도 달라지지 않는다

그런데 x는 쓰이고 y는 안쓰이고 있다는 것도 알게 될 것이다

그러다가 끝에가서 y에 다른 값이 할당이 될 수 있는데

이 말은 즉 y에 대한 새로운 할당이 일어나기 전까지

y에 대한 레지스터를 둘 필요가 없다는 뜻이다

왜냐면 x를 쓰면 되니까..

이런 경우 모든 y를 x로 대체해서 실행시키게 되는데

이게 copy propagation이다

 

 

 

그 다음은 dead code elimination이다

꽤나 직관적인 최적화 방법인데

x를 한 번도 access 안된 상태에서

값이 이후에 다시 덮어써졌다

그렇다면 x를 할당할 필요가 없는 것이다

그래서 해당 코드를 지워버리는데

이게 전형적인 dead code elimination이다

 

 

 

또한 위의 경우도 DCE인데

아무도 코딩을 저렇게 하지는.. 않겠지만

if (false)와 같이 코드를 작성하면

절대 if문 내부의 코드는 실행될 수가 없다

따라서 이렇게 unreachable한 코드도 제거해버린다

 

하지만 보통 일반적으로는 저런 식으로 코딩을 하지는 않기 때문에

보통 컴파일러가 최적화를 진행한 다음

남는 부산물같은 코드들을 제거하는데에서 주로 진행된다

 

 

 

컴파일러가 가장 많이 수행하는

최적화 중에 하나인

Common Subexpressiom Elimination이다

 

기존에 나온 연산을 기억해놨다가

계속 쓰는 방법인데

이걸 수행하고 나면 dead code가 많이 생기게 된다

 

이렇게 최적화를 수행하면

코드가 굉장히 단순해지고

copy propagation도 계속해서 가능해지고

아무튼 많이 효율적이라고한다

 

 

 

위는 gcc compiler가

o1옵션으로 최적화를 수행했을 때

변하는 코드라고 한다

 

 

 

다음은 code inlining이다

 

이는 함수 호출을 하는 부분에 있어서

함수를 그냥 함수 안의 body로 대체해버리는 것이다

이걸 function inline이라고 하는데

실제로 c/c++에서 함수 뒤에 Inline을 붙이면 코드레벨에서도 가능하다

 

실제로 이건 컴파일러가 많이 수행하는 최적화이기도 하며

성능효과가 굉장히 크다고 한다

 

우리가 이것도 앞에서 배웠지만

함수가 호출되면 내부에서 어떤 일이 발생하나?

code영역에 코드가 있고

코드를 실해하면서 heap, stack에 데이터들이 쌓이게된다

그러고 stack에는 해당 함수에 대한 정보를 쌓는

stack frame이 생기게 되는데

실제로 함수들은 다 linking이 되어있고

함수를 호출하게 되면 레지스터 값을 저장해놨다가

다른 함수 부르는 동안에 사용하고

해당 함수가 끝나면 다시 레지스터에서 메모리를 복원해서 사용하는데

이런 방식으로 함수를 수행하면 overhead가 늘어난다

그런데 inlining을 하면 위 과정을 생략할 수 있는 것이다

 

그렇다면 inline을 무조건 하면 되는거 아닌가?

이걸 하면 안되는 경우가 있을까?

 

함수 body가 너무 큰 경우

함수 사이즈가 너무 커지기 때문에

이런 경우는 보통 inlining을 하지 않는다

 

왜냐하면 함수가 크면 클수록

계속 register를 사용하면서 연산을 하게 되는데

register pressure라고 해서

모든 변수들을 다 register에 올릴 수가 없어서

원래 있던 값들을 쫓아내고 다시 load하는 것을 반복하게 된다

따라서 컴파일러가 휴리스틱하게

어느정도 기준이면 함수가 크다고 판단해서

inlining을 진행하지 않는다

 

 

이번에는 반복문에서 사용되는

최적화 기법에 대해서 알아보자

 

 

 

가장 먼저 Loop Invariant Code Motion이라고 해서 LICM이 있다

이건 loop이지만 연산을 여러번 반복하지 않는 방법이다

 

이게 어떻게 가능하냐하면

반복문 안의 연산은 항상 같다

그렇기 때문에 이 연산을 밖으로 뺄 수있는 것이다

loop invariant라는 말 자체가

loop안에서 값이 변하지 않는 것을 뜻한다

이것도 굉장히 많이 수행되는 최적화 기법 중 하나이며

최적화 효과가 굉장히 크다

 

위 ppt에 그 예시가 나와있는데

loop 내부에서 array access를 하거나 struct access를 하면

loop 내부에서 base address로 access를 하는 코드가 생성된다

그래서 for문 내부에 위처럼 srtlen(s) 이런 코드가 들어가면

매 Loop을 돌때마다 해당 array에 접근해서 길이를 가져와야하는 것이다

 

 

 

따라서 이러한 방식으로

미리 size_t len = strlen(s)와 같이

정의를 해놓은 다음 해당 변수를 사용해야한다

 

 

이건 순서를 바꾸는 최적화 방법이다

loop의 구조를 바꾸는 것인데

우리가 지금까지 본 최적화 기법과는 약간 결이 다르다

예를 들면 반복문이 2개가 있는데 그걸 하나로 합친다던지

아니면 반복문의 순서를 바꾼다던지 하는 방법이다

 

loop의 구조를 바꾸는 최적화는

보통 locality와 관련이 있다

보통 연속적으로 access를 하면 코드 성능에 매우 좋기 때문에

dependency가 없을 때에 

locality를 최대한 보장하도록 코드를 변경하게 된다

이렇게 되면 cache hit ratio가 높아지게 되고

코드의 성능이 향상된다

 

그럼 locality는 일단 코드를 한개만 돌릴 때의 얘기이고

우리가 코드를 병렬로 돌린다고 하면

앞에서 배운 data parallelism으로 코드 성능을 끌어올릴 수도 있다

이건 컴파일러단에서 수행하는 것은 아니고

보통 프로그래머들이 직접 해주는 방식이라고 한다

컴파일러가 해주기는 하는데 굉장히 어렵고

loop은 굉장히 고차원적인 코드 레벨 구조인데

컴파일러는 보통 low 레벨에서 많이 작동한다

loop은 보통 conditional branch instruction으로 Low leveld에서 작성되고

따라서 병렬 최적화를 수행하려면 이게 loop이란 것을

low level에서 알아야하는데 이게 쉽지않다

따라서 이게 loop이란걸 알 수 있는 프로그래머가

코드레벨에서 수행해주는 것이 훨씬 효율적이고

이는 성능에 굉장히 큰 영향을 미친다고한다

 

 

벌써 이번 시스템 프로그래밍 수업을 수강하며

3번이나 들은 내용이다

중첩 loop가 있을 때

locality를 보장하는 순서로 array access를 하면

cache hit ratio가 높아져서

성능에 어마어마한 차이가 발생한다

 

 

이런식으로 하나의 loop안에 있는 코드를

분산시키는 경우도 있다

이렇게 하는 경우는

완벽하게 parallel하게 코드를 수행시킬 수 있기 때문이다

 

하지만 이런 경우는 두 코드 사이에

dependency가 없어야만 가능하다

dependency가 없어야만 반복문에서 코드를 분리해도

결과에 아무런 영향을 미치지 않게 된다

 

locality도 중요하지만 위의 경우처럼

병렬로 수행할 수 있는 것도 매우 중요하다

 

 

 

위는 loop distribution과 반대로

loop fusion

즉, 코드를 합치는 것이다

 

2개의 loop이 왼쪽처럼 따로 있을 때

하나의 loop 안에 넣어버리는 것이다

(그런데 교수님께서 오른쪽 예시가 잘못된 것 같다고 하셨는데

오른쪽처럼 하면 dependency가 발생할 것 같다고..하셨다)

 

아무튼 이런 경우는 당연하겠지만

loop의 bound가 같은 경우일때만 합칠 수 있고

이렇게 하면 좋은 점 중에 하나는

loop overhead가 줄어들고

locality와 데이터 재사용률이 높아진다

 

그렇다면 어떤 경우에는 loop을 분리하는게 좋고

어떤 경우에는 Loop을 합치는게 좋을까?

 

만약 내가 loop을 parallel로 수행을 할 수 있다고 가정하자

그런데 parallel로 수행할 loop의 코드가 너무 작을 수가 있다

보통 병렬로 코드를 수행하는 경우

스레드를 생성하고 코드를 실행하고 또 스레드를 없애는

이런 과정을 반복하게 되는데

병렬로 처리하는 코드의 body가 너무 작을 경우

병렬로 했을 때 얻는 이점보다

스레드 생성 삭제에서 발생되는 overhead가 더 커질 수가 있다

그럴 때 loop fusion을 수행해주면

상대적으로 충분한 양의 연산이 생기기 때문에

병렬에서 발생하는 overhead를 상쇄시킬 수 있다고 한다

 

또한 loop fusion의 장점은

내부에 코드를 길게 작성하게 되면

저 안에서 또 많은 최적화를 수행할 수가 있다

따라서 이 loop fusion은 널리 다양하게 쓰이는 방식이라고 한다

 

추가로 GPU 연산의 경우

nested loop을 사용하는 경우가 굉장히 많은데

이걸 fusion을 하게 되면 

단순 loop fusion을 넘어서

GPU kernel fusion도 수행하게 되기 때문에

효과가 매우 좋아진다고한다

 

 

마지막으로 loop strip-mining을 살펴보고

이번 수업 내용을 정리해보록하자

 

strip mining은 큰 범위의 loop을

작은 단위의 nested loop으로 만드는

즉, 작은 단위로 strip하는 inner loop들을 생성하는 방식이다

 

이걸 이렇게 하는 이유는

vectorization을 하기 위해서라고 하는데

이렇게 만들면 안의 loop이 1개의 vector instruction으로 만들기가 쉬워져서

안의 inner loop을 vector instruction으로 만들고

밖의 loop은 그대로 실행한다고 한다

---