[Compiler] Simple example of Code Optimization

컴파일러 수업을 듣다보면 계속 Parallelism과 Vectorization에 대한 이야기를 나눈다. 그와중에 어떻게 하면 조금더 빠르게 결과를 뽑을 수 있을지가 관건이 된다. 사실 Parallelism을 구현하는데 가장 먼저 고려해야 될 상황이 코드내의 Loop가 얼마나 자원을 소비하냐이고, 또 얼마나 반복되는 작업을 하냐는 것이다. 그냥 이런 이야기를 나누고 개선시킬 수 있는 방법을 구현하는 프로젝트도 한다.

사실 Parallelism을 테스트하는데 가장 효과적인 방법이 위와 같이 이미지를 blending 처리하는 예제다. 어차피 이미지를 나타내기 위해서는 모니터상의 픽셀을 처리해야 되며, 해당 픽셀을 처리하기 위해서는 해당 이미지의 height과 width를 알아서 하나씩 접근해 색을 접근하는 방식으로 된다.예를 들어 이런거다.

for(y = 0; y < height; y++){

for(x = 0; x < width; x++){

....

// define the pixel

...

}

}

그런데 이렇게 해버리면 픽셀에 접근하기 가장 쉬운 방법이고, 어차피 이 코드를 컴퓨터가 알기 위해서는 다들 잘 아는 것처럼 assembly 로 바뀌어야 한다. 그러면 당연한 이야기겠지만 컴파일러가 그걸 얼마나 효율적으로 분석하냐가 관건이 된다. 이걸 보통 code optimization이라고 한다. optimization 기법은 참 다양하다. 위의 예시에서도 간단하게 두가지를 적용해볼 수 있다. 

for(z = 0; z < height * width; z++){

....

// define the pixel

...

}

앞에서 말했던 것처럼 Parallelism을 막는 가장 큰 요소는 Loop다. 그도 그럴것이 앞의 예시처럼 Loop의 depth가 증가하게 되면 dependence에 의한 영향이 커져버리기 때문에 그만큼 컴파일러에 부하를 준다. 그래서 최소한 Loop를 없애는 방향으로 최적화할 수 있다. 이런 방법을 Loop Coalescing 이라고 표현한다. 단어가 말하는 것처럼 여러개의 Loop를 하나로 합치는 개념이다. 

또 다른 방법으로는 이런것도 고려해볼 수 있다. 만약 Loop안에 Memory에 Access하는 코드가 있다고 치자. 그런데 위처럼 하면 z값이 증가할 때마다 매번 Memory에 Access하게 될 것이다. 물론 정상적으로 Memory에 Access하면 좋겠지만, 우리는 CPU와 Memory사이에 Cache가 있다는 걸 또 고려해야 한다. Cache를 거칠때 당연히 원하는 정보가 없으면 Miss가 발생하면서 또 부하로 작용하게 된다. 이때는 한번에 Memory로부터 읽어오는 양을 늘리면 된다.

for(z = 0; z < height * width; z += 4){

....

// define the pixel

// define the pixel

// define the pixel

// define the pixel

...

}

위처럼 Loop한번 들어올때 Memory Access를 하는 범위를 크게 하는 것이다. 이렇게 하면 전체적으로도 Loop가  관여하는 비중도 줄어들 것이다. 하지만 앞의 예제와 동일하게 맞춰주기 위해서는 pixel이 define 될때마다 Memory Access Point를 증가시켜줘야 한다. 보통 이런 기법을 Loop Unrolling 이라고 한다. 그리고 사실 이렇게 하면 최적화 성능이 많이 개선되기는 하다.

 사실 이걸 테스트하는 수업프로젝트를 하고 있다. 그런데 앞의 그림에서도 보이는 것처럼 왼쪽이 정상적인 답안인데 결과가 잘못나오면 오른쪽처럼 색깔이 누르스름하게 나온다. 분명 pixel을 define할때 잘못 접근해서 발생하는 문제인듯한데.. 좀 더 봐야 할것 같다.