루프를 벡터화하면 성능이 향상되지 않는 이유

Question

프로그램의 성능에 미치는 벡터화의 영향을 조사하고 있습니다. 이와 관련하여 다음 코드를 작성했습니다.

#include <stdio.h> 
#include <sys/time.h> 
#include <stdlib.h> 

#define LEN 10000000 

int main(){ 

    struct timeval stTime, endTime; 

    double* a = (double*)malloc(LEN*sizeof(*a)); 
    double* b = (double*)malloc(LEN*sizeof(*b)); 
    double* c = (double*)malloc(LEN*sizeof(*c)); 

    int k; 
    for(k = 0; k < LEN; k++){ 
     a[k] = rand(); 
     b[k] = rand(); 
    } 

    gettimeofday(&stTime, NULL); 

    for(k = 0; k < LEN; k++) 
     c[k] = a[k] * b[k]; 

    gettimeofday(&endTime, NULL); 

    FILE* fh = fopen("dump", "w"); 
    for(k = 0; k < LEN; k++) 
     fprintf(fh, "c[%d] = %f\t", k, c[k]); 
    fclose(fh); 

    double timeE = (double)(endTime.tv_usec + endTime.tv_sec*1000000 - stTime.tv_usec - stTime.tv_sec*1000000); 

    printf("Time elapsed: %f\n", timeE); 

    return 0; 
} 

이 코드에서는 두 벡터를 초기화하고 곱하기 만합니다. 결과는 벡터 c에 저장됩니다. 두 번째 명령이 성공적를 벡터화 이후 성능 향상을 기대할

1) icc -O2 TestSMID.c -o TestSMID -no-vec -no-simd 
2) icc -O2 TestSMID.c -o TestSMID -vec-report2 

:

for(k = 0; k < LEN; k++) 
    c[k] = a[k] * b[k]; 

내가 두 명령을 사용하여 다음 코드를 컴파일 : 내가 주로 관심은 루프 다음 ​​벡터화의 효과 고리. 그러나 필자의 연구에 따르면 루프가 벡터화되면 성능이 향상되지 않습니다.

주제에 익숙하지 않아서 뭔가를 놓친 것 같습니다. 따라서, 제 코드에 문제가 있다면 알려주십시오.

미리 도움을 주셔서 감사합니다.

추 신 : 저는 Mac OSX를 사용하고 있습니다. 따라서 할당 된 모든 메모리가 16 바이트 정렬이므로 데이터를 정렬 할 필요가 없습니다.

편집 : 여러분의 의견과 답변에 모두 감사드립니다. @Mysticial이 제안한 대답에 대해 생각해 보았습니다. 여기에 언급해야 할 몇 가지 추가 사항이 있습니다. 먼저 @Vinska가 언급했듯이 c[k]=a[k]*b[k]은 한 사이클 만 거치지 않습니다. 루프 인덱스 증분과 k이 LEN보다 작도록 비교하는 작업 외에도 작업을 수행하기 위해 수행해야 할 다른 작업이 있습니다. 컴파일러에 의해 생성 된 어셈블리 코드를 살펴보면, 간단한 곱셈은 훨씬 더 많은 사이클을 필요로한다는 것을 알 수 있습니다.

L_B1.9:       # Preds L_B1.8 
     movq  %r13, %rax         #25.5 
     andq  $15, %rax          #25.5 
     testl  %eax, %eax         #25.5 
     je  L_B1.12  # Prob 50%      #25.5 
           # LOE rbx r12 r13 r14 r15 eax 
L_B1.10:      # Preds L_B1.9 
     testb  $7, %al          #25.5 
     jne  L_B1.32  # Prob 10%      #25.5 
           # LOE rbx r12 r13 r14 r15 
L_B1.11:      # Preds L_B1.10 
     movsd  (%r14), %xmm0         #26.16 
     movl  $1, %eax          #25.5 
     mulsd  (%r15), %xmm0         #26.23 
     movsd  %xmm0, (%r13)         #26.9 
           # LOE rbx r12 r13 r14 r15 eax 
L_B1.12:      # Preds L_B1.11 L_B1.9 
     movl  %eax, %edx         #25.5 
     movl  %eax, %eax         #26.23 
     negl  %edx           #25.5 
     andl  $1, %edx          #25.5 
     negl  %edx           #25.5 
     addl  $10000000, %edx        #25.5 
     lea  (%r15,%rax,8), %rcx       #26.23 
     testq  $15, %rcx          #25.5 
     je  L_B1.16  # Prob 60%      #25.5 
           # LOE rdx rbx r12 r13 r14 r15 eax 
L_B1.13:      # Preds L_B1.12 
     movl  %eax, %eax         #25.5 
           # LOE rax rdx rbx r12 r13 r14 r15 
L_B1.14:      # Preds L_B1.14 L_B1.13 
     movups (%r15,%rax,8), %xmm0       #26.23 
     movsd  (%r14,%rax,8), %xmm1       #26.16 
     movhpd 8(%r14,%rax,8), %xmm1       #26.16 
     mulpd  %xmm0, %xmm1         #26.23 
     movntpd %xmm1, (%r13,%rax,8)       #26.9 
     addq  $2, %rax          #25.5 
     cmpq  %rdx, %rax         #25.5 
     jb  L_B1.14  # Prob 99%      #25.5 
     jmp  L_B1.20  # Prob 100%      #25.5 
           # LOE rax rdx rbx r12 r13 r14 r15 
L_B1.16:      # Preds L_B1.12 
     movl  %eax, %eax         #25.5 
           # LOE rax rdx rbx r12 r13 r14 r15 
L_B1.17:      # Preds L_B1.17 L_B1.16 
     movsd  (%r14,%rax,8), %xmm0       #26.16 
     movhpd 8(%r14,%rax,8), %xmm0       #26.16 
     mulpd  (%r15,%rax,8), %xmm0       #26.23 
     movntpd %xmm0, (%r13,%rax,8)       #26.9 
     addq  $2, %rax          #25.5 
     cmpq  %rdx, %rax         #25.5 
     jb  L_B1.17  # Prob 99%      #25.5 
           # LOE rax rdx rbx r12 r13 r14 r15 
L_B1.18:      # Preds L_B1.17 
     mfence             #25.5 
           # LOE rdx rbx r12 r13 r14 r15 
L_B1.19:      # Preds L_B1.18 
     mfence             #25.5 
           # LOE rdx rbx r12 r13 r14 r15 
L_B1.20:      # Preds L_B1.14 L_B1.19 L_B1.32 
     cmpq  $10000000, %rdx        #25.5 
     jae  L_B1.24  # Prob 0%      #25.5 
           # LOE rdx rbx r12 r13 r14 r15 
L_B1.22:      # Preds L_B1.20 L_B1.22 
     movsd  (%r14,%rdx,8), %xmm0       #26.16 
     mulsd  (%r15,%rdx,8), %xmm0       #26.23 
     movsd  %xmm0, (%r13,%rdx,8)       #26.9 
     incq  %rdx           #25.5 
     cmpq  $10000000, %rdx        #25.5 
     jb  L_B1.22  # Prob 99%      #25.5 
           # LOE rdx rbx r12 r13 r14 r15 
L_B1.24:      # Preds L_B1.22 L_B1.20 

그리고 비 vectoized 버전은 다음과 같습니다 : 같은 벡터화 버전 보이는이 옆에

L_B1.9:       # Preds L_B1.8 
     xorl  %eax, %eax         #25.5 
           # LOE rbx r12 r13 r14 r15 eax 
L_B1.10:      # Preds L_B1.10 L_B1.9 
     lea  (%rax,%rax), %edx        #26.9 
     incl  %eax           #25.5 
     cmpl  $5000000, %eax        #25.5 
     movsd  (%r15,%rdx,8), %xmm0       #26.16 
     movsd  8(%r15,%rdx,8), %xmm1       #26.16 
     mulsd  (%r13,%rdx,8), %xmm0       #26.23 
     mulsd  8(%r13,%rdx,8), %xmm1       #26.23 
     movsd  %xmm0, (%rbx,%rdx,8)       #26.9 
     movsd  %xmm1, 8(%rbx,%rdx,8)       #26.9 
     jb  L_B1.10  # Prob 99%      #25.5 
           # LOE rbx r12 r13 r14 r15 eax 

, 프로세서는 24 바이트를로드하지 않습니다. 메모리에 액세스 할 때마다 전체 행 (64 바이트)이로드됩니다. 더 중요한 것은 a, b 및 c에 필요한 메모리가 연속적이므로, 프리 페처는 확실히 많은 도움을 주며 다음 블록을 미리로드합니다. 그런데, 나는 @Mysticial에 의해 계산 된 메모리 대역폭이 너무 비관적이라고 생각합니다.

또한 SIMD를 사용하여 매우 간단한 추가 프로그램의 성능을 향상시키는 방법은 Intel Vectorization Guide에 나와 있습니다. 따라서 우리는이 간단한 루프에 대한 성능 향상을 얻을 수 있어야합니다.

Edit2 : 의견을 보내 주셔서 다시 한 번 감사드립니다. 또한, @ 미스테리 샘플 코드에 감사드립니다, 나는 마침내 성능 향상에 SIMD의 효과를 보았다. Mysticial이 지적한 바와 같이이 문제는 메모리 대역폭이었다. a, L1 캐시에 맞는 b 및 c의 작은 크기를 선택하면 SIMD가 성능을 크게 향상시키는 데 도움이 될 수 있음을 알 수 있습니다.

icc -O2 -o TestSMIDNoVec -no-vec TestSMID2.c: 17.34 sec 

icc -O2 -o TestSMIDVecNoUnroll -vec-report2 TestSMID2.c: 9.33 sec 

그리고 루프를 줄이기 것은 더욱 성능을 향상 : 또한

icc -O2 -o TestSMIDVecUnroll -vec-report2 TestSMID2.c -unroll=8: 8.6sec 

, 나는 그것이 반복을 완료하는 나의 프로세서에 대해 하나의 사이클을 소요 언급해야 여기에 내가 가진 결과는 -O2으로 컴파일 할 때.

PS :이 원래의 대답은 다시 2013 년 2017 하드웨어로 유효 내 컴퓨터가 맥북 프로 코어 I5의 @의 2.5GHz의에게있다 (듀얼 코어)

Answer 1

은 상황이 충분히 변경된 것을 질문과 대답 모두 구식입니다.

2017 년 업데이트에 대한 대답의 끝 부분을 참조하십시오.

---

원래 대답 (2013) :

당신은 메모리 대역폭 병목 현상이 있기 때문에.

벡터화 및 기타 마이크로 최적화가 계산 속도를 향상시킬 수 있지만 메모리 속도를 높일 수는 없습니다. 당신의 예에서

: 당신은 아주 작은 일을하는 모든 메모리를 통해 하나의 패스를하고 있습니다

for(k = 0; k < LEN; k++) 
    c[k] = a[k] * b[k]; 

. 이것은 귀하의 메모리 대역폭을 극대화하고 있습니다.

이렇게 최적화 된 방법에 관계없이 (벡터화 된, 펼쳐지는 등 ...) 훨씬 더 빨리 진행되지는 않습니다.

---

2013 일반적인 데스크탑 컴퓨터는 * 메모리 대역폭의 10기가바이트/s의의 순서에 있습니다.
루프가 24 바이트/반복에 닿습니다.

벡터화를 사용하지 않으면 최신 x64 프로세서에서 약 1 회 반복 할 수 있습니다 *.

는 4 GHz에서 실행중인 가정 :

• (4 * 10^9) * 24 bytes/iteration = 96 GB/s

거의 10 배의 메모리 대역폭을의 그 - 벡터화없이.

---

* 놀랍지 않게도, 인용하지 않았기 때문에 위에 적은 숫자를 의심하는 사람이 일부 있습니다. 그 것들은 내 머리 꼭대기에서 떨어져있었습니다. 그래서 그것을 증명할 몇 가지 벤치 마크가 있습니다.

루프 반복 최대한 빨리 1주기/반복으로 실행할 수 있습니다 : 우리가 캐시에 맞도록 LEN을 줄일 경우

우리는 메모리 병목 현상을 제거 얻을 수 있습니다.
(C++에서이 테스트를 더 쉽습니다.그러나이 차이가 없습니다)

#include <iostream> 
#include <time.h> 
using std::cout; 
using std::endl; 

int main(){ 
    const int LEN = 256; 

    double *a = (double*)malloc(LEN*sizeof(*a)); 
    double *b = (double*)malloc(LEN*sizeof(*a)); 
    double *c = (double*)malloc(LEN*sizeof(*a)); 

    int k; 
    for(k = 0; k < LEN; k++){ 
     a[k] = rand(); 
     b[k] = rand(); 
    } 

    clock_t time0 = clock(); 

    for (int i = 0; i < 100000000; i++){ 
     for(k = 0; k < LEN; k++) 
      c[k] = a[k] * b[k]; 
    } 

    clock_t time1 = clock(); 
    cout << (double)(time1 - time0)/CLOCKS_PER_SEC << endl; 
} 

• 프로세서 :. 인텔 코어 i7의 2600K 4.2 GHz의
• 컴파일러 @ : 비주얼 스튜디오 2012
• 시간 : 6.55 초

이 테스트에서

, 6.55 초만에 256 억 번 반복 실행했습니다.

• 6.55 * 4.2 GHz = 27510000000 사이클
• 27,510,000,000/25,600,000,000 = 1.074 사이클/이제

---

반복 당신이 그것을 할 수 얼마나 궁금해하는 경우 :

• 2 lo 광고
• 1 점
• 1 곱셈
• 증가 카운터는
• 는 + 지점 모두 하나의주기

...

최신 프로세서와 컴파일러가 굉장 때문입니다을 비교합니다.

이러한 연산마다 대기 시간 (특히 곱하기)이 있지만 프로세서는 동시에 여러 반복을 실행할 수 있습니다. 내 테스트 기계는 2x128b로드, 1x128b 저장소 및 1x256b 벡터 FP를 매 사이클마다 계속 유지할 수있는 샌디 브리지 프로세서입니다. 그리고로드가 마이크로 융합 uops의 메모리 소스 피연산자 일 경우 잠재적으로 또 하나 또는 두 개의 벡터 또는 정수 연산이 될 수 있습니다. (2로드 + 1 저장소 처리량은 256b AVX로드/저장소를 사용하는 경우에만 해당하며, 그렇지 않은 경우 사이클 당 총 2 개의 메모리 연산 (최대 한 저장소)).

어셈블리를 보면 (간략하게 생략 하겠지만) 컴파일러가 루프를 풀어 루프 오버 헤드를 줄인 것처럼 보입니다. 그러나 그것을 벡터화하는 데는 크게 어려움이있었습니다. memset()를 통해

가장 쉬운 이것을 테스트하는 방법입니다 :

#include <iostream> 
#include <time.h> 
using std::cout; 
using std::endl; 

int main(){ 
    const int LEN = 1 << 30; // 1GB 

    char *a = (char*)calloc(LEN,1); 

    clock_t time0 = clock(); 

    for (int i = 0; i < 100; i++){ 
     memset(a,0xff,LEN); 
    } 

    clock_t time1 = clock(); 
    cout << (double)(time1 - time0)/CLOCKS_PER_SEC << endl; 
} 

• 프로세서 : 인텔 코어 i7

  ---

  메모리 대역폭 10 GB/s의 순서에 2600K @ 4.2GHz

• 컴파일러 : Visual Studio 2012
• 시간 : 5.811 초

는 그래서 메모리 100 GB의 작성 내 컴퓨터를 5.811초 걸립니다.대략 17.2 GB/s입니다.

내 프로세서가 높은쪽에 있습니다. Nehalem 및 Core 2 세대 프로세서는 메모리 대역폭이 적습니다.

---

업데이트 년 3 월 2017 : 2017으로

는 상황이 더 복잡 입수했습니다.

DDR4 및 쿼드 채널 메모리 덕분에 단일 스레드가 더 이상 메모리 대역폭을 포화시킬 수 없습니다. 그러나 대역폭의 문제가 반드시 사라지는 것은 아닙니다. 대역폭이 올라 갔음에도 불구하고 프로세서 코어가 향상되었습니다.

는 수학적으로 말하면 :

• 각 코어는 대역폭 제한 X 있습니다.
• 주 메모리의 대역폭 제한은 Y입니다.
• 구형 시스템에서는 X > Y입니다.
• 현재의 고급형 시스템에서 X < Y. 그러나 X * (# of cores) > Y. 2013 년 돌아 가기

: X = 32 GB/s 및 Y = ~17 GB/s

: 1,333 MHz의

• 없음 벡터화 (8 바이트로드/저장) @ 4 GHz의 + 듀얼 채널 DDR3 @샌디 브리지 (Sandy Bridge) 벡터화 SSE (* 16 바이트로드/저장) X = 64 GB/s 지금

Y = ~17 GB/s에서 2,017 : 스웰-E 4 GHz의 + 쿼드 채널 DDR4 MHz의 2400 @

• 없음 벡터화 (8 바이트로드/저장) @X = 32 GB/s 및 Y = ~70 GB/s
• 벡터화 AVX * (32 바이트 로드/저장). X = 64 GB/s 및

_{Y = ~70 GB/s (샌디 브릿지와 하 스웰 모두 들어,에 관계없이 SIMD 폭의 약 16 바이트/사이클 대역폭을 제한 할 것이다 캐시의 건축 제한) 012,309,}

요즘에는 단일 스레드가 항상 메모리 대역폭을 포화시킬 수있는 것은 아닙니다. 그리고 제한을 달성하기 위해 벡터화해야합니다 X. 그러나 여전히 2 개 이상의 스레드가있는 Y의 주 메모리 대역폭 제한에 도달하게됩니다. 총 메모리 대역폭을 포화시키지 않고 모든 코어에서 대역폭 호깅 루프를 실행할 수 없습니다.

Answer 2

편집 : 응답 많이 수정. 또한 신비의 대답이 전적으로 정확하지 않다는 것에 대해 내가 전에 쓴 것의 대부분을 무시하십시오. 매우 다양한 테스트를 수행 함에도 불구하고 메모리 속도에 의해 영향을받는 원본 코드의 흔적을 볼 수 없었기 때문에 여전히 메모리에 병목 현상이 있다는 것에 동의하지 않습니다. 그 사이에 CPU 경계에 대한 명확한 징후가 계속 나타났습니다.

---

많은 이유가있을 수 있습니다. 그리고 이유는 하드웨어 의존적 일 수 있기 때문에 추측에 기반해서 추측해서는 안됩니다. 나중에 테스트 할 때 필자가 직면 한 이러한 것들을 요약하면, 훨씬 정확하고 안정적인 CPU 시간 측정 방법과 반복 루프가 1000 번 사용됩니다. 나는이 정보가 도움이 될 수 있다고 생각한다. 그러나 하드웨어에 따라 다르므로 소금 한 알씩 가져 가십시오.

• SSE 제품군의 지침을 사용할 때 벡터화 된 코드는 벡터화되지 않은 코드보다 10 % 이상 빠릅니다.
• SSE 계열 및 AVX를 사용하는 벡터화 된 코드를 사용하는 벡터화 된 코드는 동일한 성능으로 다소 차이났습니다.
• AVX 명령어를 사용하는 경우 벡터화되지 않은 코드가 가장 빠르게 실행되었습니다. 시도한 다른 모든 것보다 25 % 이상 빠릅니다.
• 결과는 모든 경우에 CPU 클럭으로 선형 적으로 조정됩니다.
• 결과는 메모리 클록의 영향을 거의받지 않았습니다.
• 결과는 메모리 대기 시간에 크게 영향을 받았다. 메모리 클럭보다 훨씬 많았지 만 CPU 클럭만큼 영향을받지는 못했다.

WRT 시계마다 거의 1 반복을 실행하는 미스터리의 예 - CPU 스케줄러가 효율적일 것으로 기대하지 않았고 1.5-2 클록마다 똑같은 반복을 가정했습니다. 그러나 놀랍게도 그것은 사실이 아닙니다. 나는 틀렸어. 미안해. 내 자신의 CPU가 더 효율적으로 실행 - 1.048 사이클/반복. 그래서 신비한 대답의이 부분을 확실히 증명할 수 있습니다.

Answer 3

이런 경우에, [η] = B [] 및 C [상기 L2 캐시 ::

#include <string.h> /* for memcpy */ 

... 

gettimeofday(&stTime, NULL); 

    for(k = 0; k < LEN; k += 4) { 
     double a4[4], b4[4], c4[4]; 
     memcpy(a4,a+k, sizeof a4); 
     memcpy(b4,b+k, sizeof b4); 
     c4[0] = a4[0] * b4[0]; 
     c4[1] = a4[1] * b4[1]; 
     c4[2] = a4[2] * b4[2]; 
     c4[3] = a4[3] * b4[3]; 
     memcpy(c+k,c4, sizeof c4); 
     } 

    gettimeofday(&endTime, NULL); 

가 98429.000000 67213.000000 내지 주행 시간을 감소 위해 싸우는; 루프를 8 배 풀면 57157.000000으로 줄어 듭니다.

Answer 4

이미 설명했듯이 주 메모리 대역폭 제한은 큰 버퍼의 병목 현상입니다. 이를 해결하기위한 방법은 캐시에 맞는 청크로 작업하도록 처리를 다시 설계하는 것입니다. (200MiB 전체를 곱하는 대신 128KB를 곱한 다음 그걸로 무언가를하십시오. 따라서 곱셈의 결과를 사용하는 코드는 여전히 L2 캐시에 있습니다. L2는 일반적으로 256KB이며 각 CPU 코어에 전용입니다 , 최근 인텔 디자인에서.)

이 기술은 입니다.이 기술은 cache blocking입니다. 일부 알고리즘의 경우 까다로울 수 있지만 이점은 L2 캐시 대역폭 대 기본 메모리 대역폭의 차이입니다.

이렇게하면 컴파일러에서 스트리밍 저장소 (movnt...)를 계속 생성하지 않는지 확인하십시오.이러한 쓰기는 적합하지 않은 데이터로 데이터를 오염시키지 않도록 캐시를 우회합니다. 그 다음 데이터를 읽으려면 메인 메모리를 터치해야합니다.