'최적화'에 해당되는 글 3건

블로그 정리중 발견한 글(2008년 8월 27일 글)

프로젝트를 진행하다보면, 규모와 상관없이 거의 대부분의 경우 if, else나 switch, case문등과 같은 조건문을  사용하게 된다.

이런 조건문들은 프로그램의 논리적인 처리를 위해서 없어서는 안될 문법들이지만, 이들이 너무 많아지거나, 빈번하게 실행되어야 한다면, 다른 방법을 생각해봐야 한다.

소스 코드를 분석할때 다음과 같이 조건문들을 사용하게 된다.

if ~~~

else if~~

else ~~

switch ~~~

case

case

이런 코드는 디버깅이나 코드 분석의 의도로 작성된 경우라면, 굉장히 쉽고 잘 짜여져있으며, 아무런 고민없이 if나 case만 추가하면 되기 때문에유지 보수하기에도 무척 편하다.하지만, 시스템의 성능에 민감한 프로젝트라면 위와 같은 방법을 계속 사용해서는 안되며, 시스템의 응답시간또한 각각에 따라 다르게 나올것이다.

잦은 분기문의 사용은 분기 예측이 가능하지 않은 아키텍쳐의 경우, 생각보다 많은 비용을 요구한다. 이런 연산 비용을 줄이기 위해서는 메모리를 추가적으로 더 사용하면서, 메모리  IO를 최소화 하는 것으로 대체할 수 있다.
즉, 각 조건이나, case들을 처리할때, 하나의 분리된 Memory Table을 사용해서 분기를 고정된 연산비용으로 처리할수 있게 하는 것이다.

예를 들면 다음과 같은 경우이다.
분기해야하는 case가 매우 많은 switch문의 경우 case 내부의 처리하는 부분은 함수를 사용해서 빼낼수 있도록 구성함.

switch(condition)
{

case 1:

break;

case 2:

break;

..........

..........

..........

case N: 
break;
}

위의 코드는 condition의 값으로 각 case에서 각각 정해진 서로 다른 작업들을 하도록 작성되어있다.
이런 경우는 Function Pointer를 사용함으로해서 생각보다 쉽게 해결할 수 있다.
각 case에 해당하는 함수들을 모두 만들어 두고, 하나의 함수 테이블에 등록해놓은 상태에서 바로 호출하는 방법을 사용하거나, 거의 같은 기능을 하는데, condition의 값에 따라 처리하는 값이 차이가 나는 경우라면, 함수만 하나 만들고 그 condition에 의해 처리되어야 하는 값들을 저장하는 Data Table을 만드는 것도 가능하다.

아래는 Function Pointer를 사용하는 방법에 대해서 설명하고 있다.

case를 처리하는 함수들

int case_function1(DWORD dwParam1,DWORD dwParam2)

{

함수 구현

}

int case_function2(DWORD dwParam1,DWORD dwParam2)

{

}

......

......

int case_functionN(DWORD dwParam1,DWORD dwParam2)

{

}

Function pointer Table

static const  int (*case_function[MAX_CASE_NUMS])(DWORD dwParam1,DWORD dwParam2)=

{

case_function1, //이름은 중요하지 않다, 다만 그 순서만 의미가 있을 뿐.(다른 방법으로 enum형을 사용하여 인덱싱 하도록 할수도있다)

case_function2,

.......

.......

case_functionN,

};

실제 case에 대한 처리 부분
case_function[index](dwParam1,dwParam2);

이런작업들을 통해서, 조건문을 모두 제거했다. 물론 방어차원에서, memory fault를 막기 위해, 최대값을 걸러내는 예외처리를 위한 조건문은 추가할 수도 있다.

메모리 구조를 좀 더 효율적으로 설계한다면, 다른 여러가지 case를 처리하여야 하는 경우에 대응할 수 도 있을 것이다. 

블로그 정리중 발견한 글 옮김(2008년 8월 26일 글)

두개의 32비트 Register에서 상하위 의 16비트 값씩을 조합해서 새로운 값을 만들어 낼때 유용하게 사용할수 있는 명령어가 바로 PKHBT,TB 명령어 이다.

이 명령어는 ARM v6 ARCH에 추가된 명령어로  v6 아키텍쳐를 지원하는 모든 ARM cpu에서 사용할수 있다.

아래의 예제를 보면, 실제 사용예를 이해할수 있다.

참고: H : 상위 16비트
        L  : 하위 16비트

r9 == C(H)A(L)  : r9 레지스터의 상위 16비트에 C가, 하위 16비트에 A가 저장되어 있다.
r1 == D(H)B(L)  : r1 레지스터의 상위 16비트에 D가, 하위 16비트에 B가 저장되어 있다.
 
PKHTB  r12,r1,r9, ASR #16 ; 
PKHBT  r9,r9,r1, LSL #16 ; r9 = B ,A

결과 >
r12 = D(H)C(L) , 즉, r1의 TOP(상위16비트)와 r9를 16비트 ASR한 BOTTOM(하위 16비트)를 packaging!
r9 == B(H)A(L) , 즉, r9의 BOTTOM(하위 16비트)과 r1를 16비트 LSL한 TOP(상위16비트)을 packaging!

이런 방법을 사용하지 않고 다르게 할수 있는 방법은 Register를 하나 더 사용해서, AND연산과 ORR연산을 사용하는 방법이 있다. 그러나, 위의 두방법처럼 하나의 명령어로 처리되지는 못하므로, LOOP사용시 훨씬더 많은 비용을 소모하게 된다.

이런 방법을 그래픽 렌더링 엔진쪽에서 ASM 코딩으로 최적화 해주면, 지금 나오는 Embedded 단말보다 훨씬 빠른 UI를 경험할수 있을것이다. 

아주 오래전에 적어두었던 글을 블로그 정리중 발견하여 옮겨적습니다.(2008년 8월 27일 글)

그래픽 처리하는 루틴이나 라이브러리의 경우 C언어나 CPP로 아무리 컴팩트하게 프로그래밍을 했다고 해도, 컴파일러가 사람만큼 스마트 하지 못하기 때문에 비효율적이게 되는 부분이 발생하게 된다. 

컴파일러의 첫 목적은 사용자가 의도한 대로 안전하게 어셈블링 해주는 것이기 때문에 이런 비효율은 피할 수 없는 것이다.

만약 사용자가 어셈블리에 관한 지식과 해당 H/W에 대한 지식이 조금이라도 있다면, 어셈블리 레벨에서 최적화를 시도해 볼 수 있는데, 그 실제적인 예를들어 설명하겠다.

<C CODE>

typedef _DWORD DWORD
struct _DWORD
{
    unsigned short  a ;  
    unsigned short  b ;  
    unsigned short  c ;  
    unsigned short  d ;  
};

typedef _DWORD2 DWORD2
struct _DWORD2
{
    unsigned int   A;  
    unsigned int   C ;  
};

void Loop(DWORD2 *dst,DWORD *src,int loopsize)
{
    while(loopsize--)
    {
         int d = 256 - src->d;
         dst->A=(DWORD2*)src->A+((dst->A*d)>>8)&0x1F001F00;
         dst->C=(DWORD2*)src->C+((dst->C*d)>>8)&0x1F001F00;
         dst++;
         src++;
   }       
}

위의 코드를 C언어 레벨에서 분석하였을때, 구조체가 사용이 덜 최적화 되었다는 것을 알수 있다.
즉, (DWORD2*)src->C값은 src->d 값을 포함하고 있기 때문에, C코드상에서도 메모리 Access를 1회 제거하는데 큰 공헌을 할수는 있다. 

CPU상에서 연산되는 것보다, 메모리 IO에 의한 성능저하가 상당하기 때문에 위와 같이 메모리 IO를 1회 줄이는것만으로도 성능향상을 확인할 수 있다.

앞으로, 우리가 튜닝을 할때에는 C언어로 무결한 코드를 완전히 컴팩트하게 구성한다음에 어셈블리 언어로 최적화 하면 된다.

위 C코드의 컴파일 결과 : ASM 코드(armcc 사용,LE, arm1136j-S)

Loop
     SUBS    R3,R2,#1
     BXCC   R14
     PUSH   {R14}
     LDRH    R2,[R1,#6]
     LDR      R4,[R0,#0]
     LDR      R12,[R1,#0]
     RSB      R2,R2,#0X100
     SUBS    R3,R3,#1
     MUL     R4,R2,R4
     ADD      R12,R12,R4,LSR #8
     BIC       R12,R12,#0x1F000000
     BIC       R12,R12,#0x1F00
     STR      R12,[R0,#0]
     LDR      R4,[R0,#4]
     LDR      R12,[R1,#4]
     ADD      R1,R1,#8
     MUL     R2,R4,R2
     ADD      R2,R12,R2,LSR #8
     BIC       R2,R2,#0x1F000000
     BIC       R2,R2,#0x1F00
     STR      R2,[R0,#4]!
     ADD      R0,R0,#4
     BCS      {PC} -0x4C
     POP      {R14}
     BX         R14

위의 ASM 코드를 보면 상당히 많은 부분이 개선가능하다는 것을 발견할 수 있다. 

두 말 할 것 업이 바로 최적화 작업에 돌입한다.!!!

개선된 코드

Loop_opt
    SUBS     R3,R2,#1
    BXCC     R14
    PUSH     {R4-R9}   ; 레지스터를 더 많이 쓰기 위해, 스택에 저장
    MOV      R8,#0x1F00
    ORR       R8,R8,R8, LSL #16
    MOV      R9,#0xFF
    ORR       R9,R9,R9 LSL #8
INLOOP
    LDM       R1!,{R6,R7}  ; 한번에 두개씩 읽어오자!!
    LDM       R0, {R4,R5}  ; 역시 한번에 두개 씩  읽어올것!!
    AND       R2,R9,R7, ASR #16   ;위에서 말했던, 메모리 Access 1회 줄이는 방법.!!!!
    RSB       R2,R2,#0x100 
    MUL      R4,R2,R4 ; STALL제거를 위해 위로 올라옴
    MUL      R5,R2,R5 ; STALL제거를 위해 위로 올라옴
    SUBS     R3,R3,#1
    ADD       R6,R6,R4, LSR #8 ;이놈은 줄이고 싶지만... 더 연구해봐야 됨.
    BIC        R6,R6,R8  ; 이런거 말고 방법이 있을거야~~
    ADD       R7,R7,R5, LSR #8 ;이놈도...
    BIC        R7,R7,R8 ; 이런거 말고 방법이 있을거야~~
    STM      R0!, {R6,R7} ; 두개 저장.
    BCS      INLOOP
    POP      {R4-R9}
    BX         R14

적용 테스트 결과 :루틴 자체의 성능이 약 3배 개선되었다. (시스템 점유율 12 % --> 4%로 개선)
최적화 방법 :
1. 메모리 접근 횟수를 줄임
2. LOOP내 인스트럭션의 수를 줄임
3. STALL 발생 횟수를 없앰.
4. BIT 연산을 한번에 가능하도록 함.

그러나, "나는 더 개선하고 싶다." 하는 사람은 아직 한가지 더 방법이 있다.
바로 Cache의 최대한 활용하는 방법을 연구하는 것과 SIMD(Single Instruction Multiple Data)를 사용하는 것이다.  ARM의 경우 Cache Line 사이즈가 32byte이므로 한 라인에 딱 맞는 Loop Code를 작성하면 캐시 Hit Ratio가 증가할것이고 이에 따라 성능향상도 기대할 수 있다.
그러기 위해서는 Thumb code는 16개, ARM code는 8개의 instruction으로 코드를 작성해야 한다. 

그리고 SIMD를 적용한다면, 아래 코드를 개선할수 있다.

MUL      R4,R2,R4 ; 
MUL      R5,R2,R5 ; 
ADD       R6,R6,R4, LSR #8 ;
BIC        R6,R6,R8  ;
ADD       R7,R7,R5, LSR #8 ;
BIC        R7,R7,R8 ;

구조체 구조가 32bit SIMD에서는 못써먹을 구조라서, 64bit SIMD가 되면 바로 적용해 볼 수 있을것 같다.

한줄요약 : RISC에서는 생각 보다 최적화는 어렵지 않다.