효율적으로 손

Question

내가이 C 코드가 언 롤링 루프 : 나는 손으로이 4 마디해야하는, 그래서 시도 컴파일러 최적화 이유로

for (k = 0; k < n_n; k++) { 
    if (k == i || k == j) continue; 
    dd=q2_vect[k]-q1_vect; 
    d2=dd*dd; 
    if (d2<0) { 
     a=1; 
     break; 
    }  
} 

(셀 프로세서의 SPE에 일) :

dd=q2_vect[0]-q1_vect; 
d2=dd*dd; 
if (d2<0)goto done; 

dd=q2_vect[1]-q1_vect; 
d2=dd*dd; 
if (d2<0)goto done; 

dd=q2_vect[2]-q1_vect; 
d2=dd*dd; 
if (d2<0)goto done; 

..... 
..... 

// end 
goto notdone; 

done: 
ok=0; 

notdone: 
..... 

하지만 난

if (k == i || k == j) continue; 

로하고 lopp는 "n_n"에 각 실행에 의존한다는 사실에 대처하는 방법을 알고하지 않으며,에 의해 손 "나는 최대 값"n_n "을 얻을 수 있기 때문에 코드를 여러 번 작성해야합니다.

어떻게 고칠 수 있다고 생각하십니까?

Answer 1

작성한 코드가 정확합니까? dd이 부호있는 정수 유형이고 d2이 부호가없는 경우 또는 dd 및 d2이 부동 소수점 유형 인 경우 현재 코드는 동작이 정의되지 않습니다. 첫 번째 인덱스 k이 i 또는 j이 아닌 다른 인덱스 검색을 수행하는 것처럼 보입니다. q2_vect[ k]-q1_vect이 제곱 된 경우 오버플로가 발생합니다. 효율적으로 i 및 j 반복을 건너 뛰는으로

, 내가 대신 그냥 풀려 "루프"중지 된 위치에서보고, i 또는 j 동일했다 k+1k 경우에 다시 시작합니다. 이것은 루프의 코드가 부작용/누적 합계가없는 것으로 가정합니다.이 코드는 쓰여진 것처럼 사실이지만, 코드가 다른 작업 (예 : 사각형 합계)을 수행했음을 의미 할 수도 있습니다.

마지막으로, 나는 작업 코드가없는 것 같아도 수동으로 루프를 풀기를 원한다는 회의론 적으로 고도입니다. 좋은 컴파일러라면 루프를 풀 수 있지만 루프 언 롤링 유형을 사용하면 성능이 저하 될 수 있습니다. 제 생각에는 코드가 올바르게 작동하고, (컴파일러에서 생성 된 asm을보고) 정확하게 측정하고, 을 개선하려고 시도한 후에에 문제가 있다고 판단한 것이 좋습니다.n_n 가정

Answer 2

첫 번째 문제의 경우 조건이 충족 될 때 루프 본문을 "실행"하지 않아야합니다. 이 특정 문제에 대해서는 문법의 조건 인 if 안에 해당 조건의 논리 부정을 넣을 수 있습니다.

일반적으로 언롤은 요인에 의한 것입니다. 언 롤드 코드는 여전히 루프에 존재합니다 (루프 경계가 매우 작지 않은 경우 제외). 또한, 루프 밖에서 작업의 "나머지"(언 롤 요인으로 나눈 문제 크기의 나머지 부분에 해당)를 수행해야합니다. 그래서

루프 언 롤링 예 :

for (i = 0; i < n; ++i) do_something(i); 

하는 것은 2 배 풀려 될 수있다 : 두 번째 루프는 "나머지"수행

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

은 (또한 i 설정 펼쳐진 루프와 같은 것이지만,이 후에 i이 필요하지 않은 경우 전체 줄은 단지 if (i < n) etc이 될 수 있습니다.

Answer 3

이 일정 컴파일 시간, 루프는 하찮게과 같이 언 롤링 할 수 있습니다

는

do 
{ 
    k=0 
    if (k == i || k == j) 
    ; 
    else 
    { 
    dd=q2_vect[ k]-q1_vect; 
    d2=dd*dd; 
    if (d2<0) 
    { 
     a=1; 
     break; 
    } 
    } 

    k=1 
    if (k == i || k == j) 
    ; 
    else 
    { 
    dd=q2_vect[ k]-q1_vect; 
    d2=dd*dd; 
    if (d2<0) 
    { 
     a=1; 
     break; 
    } 
    } 

    /* and so on, n_n times */ 

    k= n_n-1 
    if (k == i || k == j) 
    ; 
    else 
    { 
    dd=q2_vect[ k]-q1_vect; 
    d2=dd*dd; 
    if (d2<0) 
    { 
     a=1; 
     break; 
    } 
    } 

} while (0); 

기본적으로, 모든 것이 계속 후

if 문 편집의 else 부분으로 이동 : n_n은 컴파일 타임 상수가 아니기 때문에 루프의 루프를 여러 번 실행하여 루프를 풀고 switch-case 문으로 끝낼 수 있습니다. 사실, 당신이 그렇게처럼 그들을 결합 할 수 있습니다, 이것은 일반적으로 Duff's device.

#define LOOP_BODY    \ 
do{       \ 
    if (k == i || k == j)  \ 
    ;       \ 
    else       \ 
    {       \ 
    dd=q2_vect[ k]-q1_vect; \ 
    d2=dd*dd;     \ 
    if (d2<0)     \ 
    {       \ 
     a=1;      \ 
     break;     \ 
    }       \ 
    } while (0)   


k = 0; 
switch(n_n % 8) 
{ 
    case 0: for (; k < n_n; k++) { LOOP_BODY; k++; 
    case 7:      LOOP_BODY; k++; 
    case 6:      LOOP_BODY; k++; 
    case 5:      LOOP_BODY; k++; 
    case 4:      LOOP_BODY; k++; 
    case 3:      LOOP_BODY; k++; 
    case 2:      LOOP_BODY; k++;  
    case 1:      LOOP_BODY; k++;} 
} 

Answer 4

루프 언 롤링은 루프가 적은 번 실행되도록 몇 반복을 포함하고 의미라고합니다. 그렇게 지사 무거운이기 때문에 예를 들어,

for(i=0;i<count;i++) { 
    printf("%d", i); 
} 

이

i=0; 
if(count%2==1) { 
    printf("%d", i); 
    i=1; 
} 
while(i<count) { 
    printf("%d", i); 
    printf("%d", i+1); 
    i+=2; 
} 

Answer 5

작성된이 코드에 언 롤링 할 수는 SPE에 대한 매우 적합하다. 또한 관련된 변수의 유형에 대한 정보가 도움이 될 것입니다. 작성된 테스트는 (심지어 >0 수정으로도) 상당히 불분명 한 것처럼 보입니다. 그러나 C 코드의 코드는 평균 벡터 빼기로 operator -을 오버로드하고 내적을 계산하는 두 벡터로 operator *을 오버로드하는 일종의 벡터 클래스를 사용하는 것처럼 보입니다.

SPE에서 이와 같은 간단한 루프와 함께 할 첫 번째 일은 분기가 없도록 (적어도 내부 루프, 즉 몇 차례 언롤하고 N 회 반복마다 초기 종료 만 확인) SIMD 명령을 사용하는 것입니다. SPE 은 SIMD 명령어 만 가지고 있으므로 루프에서 SIMD 프로세싱을 사용하지 않으면 사용 가능한 레지스터 공간과 계산 능력의 75 %가 즉시 낭비됩니다. 마찬가지로, SPE는 한 번에 정렬 된 q 워드 (16 바이트) 만로드 할 수 있습니다. 더 작은 데이터 유형을 사용하면로드하려는 값이 "기본 슬롯"으로 끝나도록 레지스터 내용을 섞는 데 추가 작업이 필요합니다.

if (k == i || k == j)은 다음 분기없는 형식을 사용하여 루프의 첫 번째 부분을 다시 작성함으로써 제거됩니다 (의사 코드이므로 int에 즉시 적용되지만 내장 함수를 사용하여 부동 소수점에 비트 연산을 가져와야 함).) cmp_equal(a,b) == (a == b) ? ~0u : 0)

여기

dd = q2_vect[k] - q1_vect; 
d2 = dd * dd; 
d2 &= ~(cmp_equal(k, i) | cmp_equal(k, j)); 

, cmp_equal는 각각의 SPE 내장 함수 (의미론에 대응한다. k == i 또는 k == j 일 때 d2이 0으로 설정됩니다. 마다 몇 루프 반복을

a |= cmp_greater(d2, 0); 

및 a이 0이 아닌 경우에만 (초 아웃에) 확인 :

는 다음을 수행, 내부 루프에서 if (d2 > 0) 지점을 방지하기 위해. d2에 대해 계산 된 모든 값이 음수가 아닌 경우 (유형이 정수, 실수 또는 실수 벡터 클래스 인 경우),이를 더 간단하게 할 수 있습니다. 그냥 할 : 개별 모든 용어가 0 인 경우

결국

a |= d2; 

, a은 제로가 아닌 것입니다. 그러나 정수 오버플로 (int를 사용하는 경우) 및 NaN (부동 소수점을 사용하는 경우)에주의하십시오. 이러한 경우를 처리해야한다면 위의 단순화로 인해 코드가 손상됩니다.

Answer 6

이 루프를 풀면 많은 도움이되지 않습니다. 내부 루프 소프트웨어 언 롤링은 소프트웨어 파이프 라인을 사용하여 실행시 높은 IPC를 달성하는 데 도움이됩니다. 여기에서 언 롤링으로 논리를 손상시킬 수 있습니다.