64비트 요소를 통해 루프를 벡터화하는 것이 대용량 버퍼에 비해 성능이 향상되지 않는 이유는 무엇입니까?
벡터라이제이션이 프로그램의 성능에 미치는 영향을 조사하고 있습니다.이와 관련하여 다음과 같은 코드를 작성하였습니다.
#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을 가지는 은 다음과 루프를 제가 주로 관심을 가지는 것은 다음과 같은 루프를 벡터화하는 효과입니다.
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
나는 다음 두 가지 명령을 사용하여 코드를 컴파일합니다.
1) icc -O2 TestSMID.c -o TestSMID -no-vec -no-simd
2) icc -O2 TestSMID.c -o TestSMID -vec-report2
두 번째 명령어는 성공적으로 루프를 벡터화하기 때문에 성능 향상을 기대합니다.하지만 제 연구 결과에 따르면 루프를 벡터화했을 때 성능 향상이 없습니다.
제가 주제를 잘 몰라서 여기서 놓친 부분이 있을 수도 있습니다.그래서 혹시 제 코드에 문제가 있다면 알려주시기 바랍니다.
당신의 도움에 미리 감사드립니다.
추신: 저는 Mac OSX를 사용하고 있기 때문에 할당된 메모리가 모두 16바이트로 정렬되어 있기 때문에 데이터를 정렬할 필요가 없습니다.
편집: 먼저 여러분의 의견과 답변에 감사드립니다.@Mystial에서 제안한 답변에 대해 생각해봤는데 여기서 추가로 언급해야 할 사항들이 있습니다.언급한 것처럼째, @Vinsk가,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
그리고 백신이 없는 버전은 다음과 같습니다.
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바이트)이 로드됩니다.더 은에 ea,b,그리고.c는 연속적이고, 프리페처는 분명히 많은 도움이 될 것이며, 다음 블록을 미리 로드합니다.그럼에도 @Mystial에서 계산한 메모리 대역폭은 너무 비관적인 것 같습니다.
또한 SIMD를 사용하여 매우 간단한 추가를 위한 프로그램의 성능을 향상시키는 것은 Intel Vectorization Guide에서 언급합니다.따라서 우리는 이 간단한 루프에 대해 어느 정도 성능 개선을 얻을 수 있을 것으로 보입니다.
편집2: 다시 한번 의견을 주셔서 감사합니다.또한 @Mystatic sample code 덕분에 SIMD가 성능 향상에 미치는 영향을 드디어 보았습니다.마이스티셜이 언급한 것처럼 문제는 메모리 대역폭이었습니다. 작은 사이즈 a,b,그리고.cL1 캐시에 맞는 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: 내 컴퓨터는 Macbook Procore i5 @2.5입니다.GHz(듀얼 코어)
이 원래 답변은 지난 2013년에도 유효했습니다.2017년 하드웨어 기준으로 질문과 답변이 모두 구식일 정도로 상황이 바뀌었습니다.
2017년 업데이트에 대해서는 이 답변의 끝을 참조하십시오.
원본 답변(2013):
메모리 대역폭으로 인해 병목 현상이 발생하기 때문입니다.
벡터화 및 기타 마이크로 최적화는 계산 속도를 향상시킬 수 있지만 메모리 속도를 향상시킬 수는 없습니다.
예에서:
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
당신은 일을 거의 하지 않고 모든 기억을 한 번에 통과하고 있습니다.이것은 메모리 대역폭을 최대화하고 있습니다.
따라서 최적화 방식에 관계없이 (벡터화, 언롤 등) 훨씬 더 빨라지지는 않을 것입니다.
2013년의 일반적인 데스크톱 컴퓨터는 10GB/s의 메모리 대역폭*을 갖추고 있습니다.
루프가 24바이트/반복에 닿습니다.
벡터라이제이션이 없다면 현대 x64 프로세서는 한 주기에 약 1번의 반복 작업을 수행할 수 있을 것입니다.*
4GHz 속도로 실행 중이라고 가정합니다.
(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.2GHz
- 컴파일러:비주얼 스튜디오 2012
- 시간 : 6.55초
이번 테스트에서 저는 불과 6.55초 만에 256억 회를 반복했습니다.
6.55 * 4.2 GHz= 27,510,000,000 사이클27,510,000,000 / 25,600,000,000= 1.074 사이클/슬롯
다음과 같은 작업을 수행할 수 있는 방법이 궁금하다면,
- 2로드
- 1점
- 1 곱하기
- 증분 카운터
- 비교 + 가지
모두 한 주기로...
현대식 프로세서와 컴파일러가 훌륭하기 때문입니다.
이러한 각 작업은 지연 시간(특히 곱셈)을 가지지만, 프로세서는 여러 번의 반복을 동시에 실행할 수 있습니다.저의 테스트 머신은 Sandy Bridge 프로세서로, 2x128b 로드, 1x128b 스토어, 1x256b 벡터 FP를 매 주기마다 곱할 수 있습니다.그리고 부하가 마이크로퓨즈 웁스를 위한 메모리 소스 피연산자인 경우, 또 다른 하나 또는 두 개의 벡터 또는 정수 ops가 될 가능성이 있습니다.(256b AVX 로드/스토어를 사용하는 경우에만 로드 2개 + 처리량 1개가 저장되며, 그렇지 않으면 사이클당 총 메모리 작업 수가 2개(최대 1개의 스토어)에 불과함).
간략하게 설명하자면 컴파일러가 루프를 풀어서 루프 오버헤드를 줄인 것 같습니다.하지만 그것을 벡터화하는데 성공하지 못했습니다.
메모리 대역폭은 10GB/s입니다.
이것을 테스트하는 가장 쉬운 방법은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 2600K @ 4.2GHz
- 컴파일러:비주얼 스튜디오 2012
- 시간 : 5.811초
따라서 100GB의 메모리에 쓰는 데 5.811초가 걸립니다.초당 약 17.2 GB입니다.
그리고 제 프로세서는 고급에 있습니다.Nehalem과 Core 2세대 프로세서는 메모리 대역폭이 적습니다.
2017년 3월 업데이트:
2017년을 기점으로 상황은 더욱 복잡해졌습니다.
DDR4와 쿼드채널 메모리 덕분에 메모리 대역폭을 포화시키는 하나의 스레드가 더 이상 불가능합니다.하지만 대역폭 문제가 반드시 사라지는 것은 아닙니다.대역폭은 증가했지만 프로세서 코어도 개선되었습니다. 그리고 프로세서 코어도 더 많습니다.
수학적으로 표현하자면:
- 제한 Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ,
X. - 은 Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ 입니다.
Y. - 시스템에서는 에서는
X > Y. - 에서는 에서는 에서는
X < Y.그렇지만X * (# of cores) > Y.
2013년: Sandy Bridge @ 4GHz + 듀얼 채널 DDR3 @ 1333MHz
- 벡터화 없음(8바이트 로드/스토어):
X = 32 GB/s그리고.Y = ~17 GB/s - 벡터화된 SSE*(16바이트 로드/스토어):
X = 64 GB/s그리고.Y = ~17 GB/s
2017년 현재: Haswell-E @ 4GHz + 쿼드채널 DDR4 @ 2400MHz
- 벡터화 없음(8바이트 로드/스토어):
X = 32 GB/s그리고.Y = ~70 GB/s - 벡터화된 AVX*(32바이트 로드/스토어):
X = 64 GB/s그리고.Y = ~70 GB/s
Sandy Bridge와 Haswell 모두에서 캐시의 아키텍처 제한은 SIMD 폭에 관계없이 약 16바이트/사이클로 대역폭을 제한합니다.
따라서 요즘에는 단일 스레드가 항상 메모리 대역폭을 포화시킬 수는 없습니다. Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ Δ ΔΔ Δ ΔΔ,X은 . 은 입니다 에 입니다 에 은 Y실이 2개 이상 있는
하지만 한 가지는 변하지 않았고 아마도 오랫동안 변하지 않을 것입니다.전체 메모리 대역폭을 포화시키지 않으면 모든 코어에서 대역폭 호깅 루프를 실행할 수 없습니다.
Mystic이 이미 설명했듯이, 메인 메모리 대역폭 제한은 큰 버퍼의 병목 현상입니다.이를 해결하려면 캐시에 맞는 청크에서 작동하도록 처리를 재설계하는 것입니다. (200MiB를 2배로 곱하는 대신 128kiB만 곱하면 됩니다.)따라서 곱셈의 출력을 사용하는 코드는 여전히 L2 캐시에서 찾을 것입니다.L2는 일반적으로 256kiB이며, 최신 Intel 설계에서 각 CPU 코어에 대해 비공개입니다.)
이 기법을 캐시 차단 또는 루프 타일링이라고 합니다.일부 알고리즘의 경우 까다로울 수 있지만 L2 캐시 대역폭과 메인 메모리 대역폭의 차이가 보상이 됩니다.
합니다( 가 하지 합니다 를 합니다 하지 를 ).movnt...이러한 쓰기 작업은 적합하지 않은 데이터로 인해 캐시가 오염되지 않도록 캐시를 우회합니다.해당 데이터를 다음에 읽을 때는 메인 메모리를 터치해야 합니다.
편집: 답을 많이 수정했습니다.그리고 이전에 Mystic의 답변이 완전히 정확하지 않다는 것에 대해서 제가 쓴 글은 대부분 무시해주세요.하지만 매우 다양한 테스트를 수행했음에도 불구하고 원래 코드가 메모리 속도에 구속되는 징후를 볼 수 없었기 때문에 메모리에 의해 병목 현상이 발생하는 것에 대해서는 여전히 동의하지 않습니다.그 동안에도 CPU에 묶여 있는 분명한 징후를 보였습니다.
여러 가지 이유가 있을 수 있습니다.그리고 그 이유는 하드웨어에 의존적일 수 있기 때문에 추측을 바탕으로 추측해서는 안 된다고 생각했습니다.나중에 테스트할 때 만났던 이러한 것들에 대해 간략히 설명해 보겠습니다. 훨씬 더 정확하고 안정적인 CPU 시간 측정 방법과 루프를 1000번 사용했습니다.저는 이 정보가 도움이 될 것이라고 믿습니다.하지만 하드웨어에 따라 다르니 조금만 참고 드세요.
- SSE 계열의 명령어를 사용할 때 벡터화된 코드는 비 벡터화된 코드에 비해 10% 이상 빠릅니다.
- SSE-패밀리를 이용한 벡터화 코드와 AVX를 이용한 벡터화 코드는 동일한 성능으로 어느 정도 실행되었습니다.
- AVX 명령을 사용할 때, 벡터화되지 않은 코드가 가장 빨리 실행되었습니다 - 다른 모든 시도보다 25% 이상 빠르게 실행되었습니다.
- 결과는 모든 경우에서 CPU 클럭에 따라 선형적으로 확장됩니다.
- 결과는 메모리 클럭의 영향을 거의 받지 않았습니다.
- 결과는 메모리 지연 시간(메모리 클럭보다 훨씬 더 많은)에 상당한 영향을 받았지만 CPU 클럭이 결과에 영향을 미친 만큼은 아니었습니다.
WRT Mystical의 클럭당 거의 1회 반복 실행 예제 - CPU 스케줄러가 그렇게 효율적일 줄은 예상하지 못했고 1.5-2회 클럭 틱당 1회 반복을 가정하고 있었습니다.하지만 놀랍게도, 그건 사실이 아닙니다. 저는 분명히 틀렸습니다, 죄송합니다.제 CPU는 1.048 사이클/반복으로 훨씬 더 효율적으로 작동했습니다.그래서 미스틱의 대답 중 이 부분이 확실히 옳다는 것을 증명할 수 있습니다.
a[] 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으로 단축됩니다.
언급URL : https://stackoverflow.com/questions/18159455/why-vectorizing-the-loop-over-64-bit-elements-does-not-have-performance-improvem
'programing' 카테고리의 다른 글
| Spring Boot - EnableAutoConfiguration with Exclude not working (0) | 2023.09.06 |
|---|---|
| Oracle의 데이터베이스 스키마를 덤프 파일로 내보내는 방법 (0) | 2023.09.06 |
| date_format 시간이 ":"인 경우 경고가 생성됩니다. (0) | 2023.09.06 |
| flexviews test_demo change 로그 테이블이 생성되지 않은 이유 (0) | 2023.09.06 |
| mariadb의 SQL 쿼리 (0) | 2023.09.06 |