루프에 포함된 분기

프로그램에서 if 구문에 의해 수행되는 판단 과정은 나노(nano)초 수준의 시간이 소요되지만 루프 에서와 같이 자주 실행되는 코드 내에서 처리돼야 하는 분기 명령은 코드 성능을 나쁘게 할 수 있다.

코드에서 분기에 의한 영향을 감소시키기 위한 두 가지 처리 방법이 있다.

- 분기를 streamline화 - 루프 밖으로 이동

분기에 의한 성능감소를 막기 위해 루프내의 어떤 분기 들이 재구성 가능한지 불가능한지 알아야 할 것이다. 루프내의 분기들은 다음과 같이 몇 가지 영역으로 구분할 수 있다.

- Loop invariant conditionals

- Loop index dependent conditionals - Independent loop conditionals - Dependent loop conditionals - Reductions

- Conditionals that transfer control

4.2.2.1. Loop Invariant Conditionals

루프내의 계산과 무관한 conditional이다. invariant는 결과가 항상 같다는 것을 의미한다. 다음 코 드에서 N의 값은 A, B, C, I의 값과 무관하다.

클러터 존재 DO I = 1, K

IF(N .EQ. 0) THEN A(I) = A(I) + B(I)*C ELSE

A(I) = 0.

ENDIF ENDDO

클러터 제거

IF(N .EQ. 0) THEN DO I = 1, K

A(I) = A(I) + B(I)*C ENDDO

ELSE

DO I = 1, K A(I) = 0.

ENDDO ENDIF

클러터가 제거된 코드는 K-1회의 테스트가 감소했으며, if구문에 의한 분기 가능성이 사라진 루프 계산은 컴파일러에 의해 파이프라인 처리가 가능해져 많은 성능향상 효과를 볼 수 있다.

4.2.2.2. Loop Index Dependent Conditionals

항상 참 또는 항상 거짓이 아니라 루프 인덱스 값에 따라 판단 결과가 달라지는 경우에 해당된다.

클러터 존재 DO I = 1, N DO J = 1, N

IF(J .LT. I) THEN

A(J,I) = A(J,I) + B(J,I)*C ELSE

A(J,I) = 0.

ENDIF ENDDO ENDDO

클러터 제거 DO I = 1, N DO J = 1, I-1

A(J,I) = A(J,I) + B(J,I)*C ENDDO

DO J = I, N A(J,I) = 0.

ENDDO ENDDO

클러터가 제거된 코드는 N이 충분히 크다면 이전의 코드보다 향상된 성능을 보여 준다. N 값이 작다면, 오히려 클러터가 증가된다고 볼 수도 있지만, 이런 경우엔 코드 실행시간 자체가 매우 작 아지므로 클러터에 의한 성능 효과는 매우 미미해 진다.

4.2.2.3. Independent Loop Conditionals

조건이 루프 인덱스에 직접적으로 의존하지 않는 경우이다.

DO I = 1, N DO J = 1, N

IF(B(J,I) .LT. 1.0) A(J,I) = A(J,I) + B(J,I)*C ENDDO

ENDDO

계산 분리가 불가능하지만, 반복 계산이 서로 독립적이므로 unrolling이나 병렬화에 의한 계산 수 행이 가능하다.

4.2.2.4. Dependent Loop Conditionals

조건이 루프에서 계산되는 값에 의존하는 경우이다. 계산이 완료돼야 어떤 반복 계산으로 코드가 진행될지 결정할 수 있다.

DO I = 1, N

IF(X .LT. B(I)) X = X + A(I)*C ENDDO

이와 같은 경우는 의존성으로 인해 최적화 수행이 일반적으로 어렵다.

4.2.2.5. Reductions

배열로부터 하나의 스칼라 값을 얻게 되는 종류의 계산을 reduction이라 부른다. if 구문에 의해 배열의 원소 중 최대값이나 최소값을 결정하는 것을 생각해 볼 수 있다. reduction 연산이 수행되 는 루프를 다음과 같이 한 번의 반복에서 여러 개를 테스트하도록 재구성해서 병렬성을 증가 시 키고 코드 성능을 증가시킬 수 있다.

클러터 존재

for (i=0; i<n; i++) z = a[i] > z ? a[i] : z;

클러터 제거 z0 = 0.;

z1 = 0.;

for (i=0; i<n-1; i+=2){

z0 = z0 < a[i] ? a[i] : z0;

z1 = z1 < a[i] ? a[i+1] : z1;

}

z = z0 < z1 ? z1 : z0;

일반적으로 이와 같은 루프 재구성은 컴파일러의 유연성에 제한을 줄 수 있어 핸드 튜닝의 방법 으로 부적절하다. 병렬 시스템 환경에서는 컴파일러에 의해 수행되는 reduction 연산의 수행을 권 장한다.

4.2.2.6. Conditionals that Transfer Control

조건문은 테스트 결과에 의해 새로은 할당을 수행하는 경우가 많지만 모든 조건이 할당으로 끝나 는 것은 아니다. 테스트 결과로 서브루틴 호출이나 goto 문에 의한 제어의 흐름을 생각할 수 있 다.

DO I = 1, N DO J = 1, N

IF(B(J,I) .EQ. 0) THEN PRINT*, I, J

STOP ENDIF

A(J,I) = A(J,I) / B(J,I) ENDDO

ENDDO

위의 코드는 반복 계산이 순차적으로 진행되어야 하므로 성능에 나쁜 영향을 미치게 된다.

4.2.3. 기타 클러터