루프 언롤링(Loop Unrolling)

  이전 포스트에서 루프 언롤링을 통해 최적화 하는 코드를 잠깐 보았습니다.

루프언롤링이란 for문이나 while문과같은 루프문을 직접적인 명령어의 나열로 바꾸는 기법입니다. 루프를 코드의 나열로 바꾸게 되면 루프 제어를 위한 증가연산, 비교연산이 생략되어 연산량을 감소 시킬 수 있습니다. 또한, GPU에서 실행하는 코드를 컴파일하게 되면 명령어를 묶어 덩어리로 실행하게 되는데, 루프를 사용하지 않으면 명령어가 끊기지않고 담기게 되어 연산속도가 향상됩니다. 코드로 간단히 살펴보면 다음과 같습니다. 먼저 Not unrolled 코드 입니다. 보시는 바와 같이 일반적인 for문입니다.

1
2
3
4
5
6
7
// Not unrolled
        for(int i = localRow; i < localRow+filterWidth; i++) {
           int offset = i*localWidth;
           for(int j = localCol; j < localCol+filterWidth; j++){
               sum += localImage[offset+j] * filter[filterIdx++];
           }
        }
cs

다음은 이중루프 중 안쪽의 루프만 unrolled한 것입니다. 코드에 따라 다르지만 약 20%정도의 속도 향상을 볼 수 있습니다.

1
2
3
4
5
6
7
8
9
// Unrolled
for(int i = localRow; i < localRow+filterWidth; i++) {
    int offset = i*localWidth+localCol;
    sum += localImage[offset++] * filter[filterIdx++];
    sum += localImage[offset++] * filter[filterIdx++];
    sum += localImage[offset++] * filter[filterIdx++];
    sum += localImage[offset++] * filter[filterIdx++];
    sum += localImage[offset++] * filter[filterIdx++];
}
cs

다음은 완전히 unrolled한 것입니다. 안쪽의 루프만 unroll한 것에 비해 약 20%정도의 속도 향상을 볼 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Completely unrolled
int offset = localRow*localWidth + localCol;
sum += localImage[offset + 0] * filter[filterIdx++];
sum += localImage[offset + 1] * filter[filterIdx++];
sum += localImage[offset + 2] * filter[filterIdx++];
sum += localImage[offset + 3] * filter[filterIdx++];
sum += localImage[offset + 4] * filter[filterIdx++];
offset += localWidth;
sum += localImage[offset + 0] * filter[filterIdx++];
sum += localImage[offset + 1] * filter[filterIdx++];
sum += localImage[offset + 2] * filter[filterIdx++];
sum += localImage[offset + 3] * filter[filterIdx++];
sum += localImage[offset + 4] * filter[filterIdx++];
offset += localWidth;
sum += localImage[offset + 0] * filter[filterIdx++];
sum += localImage[offset + 1] * filter[filterIdx++];
sum += localImage[offset + 2] * filter[filterIdx++];
sum += localImage[offset + 3] * filter[filterIdx++];
sum += localImage[offset + 4] * filter[filterIdx++];
offset += localWidth;
sum += localImage[offset + 0] * filter[filterIdx++];
sum += localImage[offset + 1] * filter[filterIdx++];
sum += localImage[offset + 2] * filter[filterIdx++];
sum += localImage[offset + 3] * filter[filterIdx++];
sum += localImage[offset + 4] * filter[filterIdx++];
offset += localWidth;
sum += localImage[offset + 0] * filter[filterIdx++];
sum += localImage[offset + 1] * filter[filterIdx++];
sum += localImage[offset + 2] * filter[filterIdx++];
sum += localImage[offset + 3] * filter[filterIdx++];
sum += localImage[offset + 4] * filter[filterIdx+
cs

간단한 방법으로 약 40~50%정도의 속도 향상 효과를 볼수있기때문에 unrolling은 개발의 마지막단계에서 코드를 점검하면서 꼭 적용해야 할 최적화 기법입니다.

pragma 지시문을 이용한 unrolling

직접 코드를 통해서 unrolling 할 수도 있지만 루프의 횟수가 백 단위를 넘어가게 되면 코딩하는데 있어 상당히 애로사항이 있겠죠? 코드를 생성하는 프로그램을 써야할 정도록 루프의 횟수가 많아진다면 코딩하는데 큰 어려움이 있습니다. 그래서 있는 기능이 #pragma 지시문을 이용한 루프 언롤링입니다. OpenCL 2.0 버전 부터 사용 할 수 있는 기능으로 다음 코드와 같이 루프 위쪽에 지시문을 써 주는 것 만으로도 unrolling이 가능합니다.

1
2
3
4
5
6
7
8
#pragma unroll
for(int i = localRow; i < localRow+filterWidth; i++) {
   int offset = i*localWidth;
   #pragma unroll
   for(int j = localCol; j < localCol+filterWidth; j++){
       sum += localImage[offset+j] * filter[filterIdx++];
   }
}
cs

다만, 두개이상의 루프를 pragma 지시문을 이용해서 unrolling하는 경우에는 직접 unrolling 하는 것보다 효율이 약간 떨어 질 수 있습니다. pragma문을 사용 하면 루프를 덮고있는 루프 때문에 직접 쓰는 것보다 많은 양의 코드가 생성 된다고 합니다. 만약 for문이 하나라면 직접 unrolling하는 것과 거의 비슷한 효과를 가진다고 합니다.

삼항연산자를 이용한 최적화

간단한 방법으로 해줄 수 있는 또다른 최적화 기법도 하나 알아보고 넘어가도록 하겠습니다. 바로 3항연산자입니다. 실제로 CPU에서 작동하는 코드를 생성할떄도 아주 타이트하게 최적화를 한다면 사용하는 기법인데요, GPU에서도 마찬가지로 사용 할 수 있습니다.if else문은 3항연산자에비해 약 1.3배 정도의 GPU clock time을 소비 한다고 합니다. 만약 모든 픽셀에 대해 if else를 적용하는 연산이라면 단순히 삼항연산자를 사용하는것 만으로도 20~30%의 속도 향상을 볼 수 있습니다. 다섯개의 연산을 한다면 CPU에서는 1.3*5지만 GPU에서는 1로 줄어들기 떄문이죠. 간단한 예는 다음과 같습니다.

1
2
3
4
5
6
7
if(nTemp < 0)
    imageOut[dstIndex] = 0;
else
    imageOut[dstIndex] = nTemp;
nTemp = (nTemp < 0) 0 : nTemp;
imageOut[dstIndex] = nTemp;
cs

OpenCL specification에서 소개하고있는 최적화 기법들 중 Median Filter와 같이 필터 커널 내의 픽셀간의 순위를 정하거나 또는 정렬을 해야 할 일이 있을떄 사용 하는 최적화 기법인 bitonic sort에 대해서는 다음에 소개해 보도록 하겠습니다. 최적화 기법은 GPU를 활용하는 방법을 배우는 것과 같습니다. 이후에 소개할 메모리 관련 최적화 기법 등은 GPU의 구조에 대해 어느정도 이해하고 있어야 적용이 가능하게 됩니다. 최적화 기법들을 공부하면서 GPU의 구조와 활용 방법에 대해 잘 학습할 수 있었으면 좋겠습니다.

출처: http://hoororyn.tistory.com/10?category=712666 [후로린의 프로그래밍 이야기]