C ++ : 레지스터에 피연산자 하나를 유지하여 놀라운 속도 향상

C ++ : 레지스터에 피연산자 하나를 유지하여 놀라운 속도 향상

---

다음 코드를 사용하여 배열의 요소를 확장하고 합산하는 루틴을 타이밍하여 L1 캐시에 배열을 갖는 것이 메모리에 미치는 영향에 대한 아이디어를 얻으려고 노력해 왔습니다 (결과를 '로 확장해야한다는 것을 알고 있습니다. 마지막에 a '; 요점은 루프 내에서 곱하기와 더하기를 모두 수행하는 것입니다. 지금까지 컴파일러는'a '를 제거하지 못했습니다.)

double sum(double a,double* X,int size)
{
    double total = 0.0;
    for(int i = 0;  i < size; ++i)
    {
        total += a*X[i];
    }
    return total;
}

#define KB 1024
int main()
{
    //Approximately half the L1 cache size of my machine
    int operand_size = (32*KB)/(sizeof(double)*2);
    printf("Operand size: %d\n", operand_size);
    double* X = new double[operand_size];
    fill(X,operand_size);

    double seconds = timer();
    double result;
    int n_iterations = 100000;
    for(int i = 0; i < n_iterations; ++i)
    {
        result = sum(3.5,X,operand_size);
        //result += rand();  
    }
    seconds = timer() - seconds; 

    double mflops = 2e-6*double(n_iterations*operand_size)/seconds;
    printf("Vector size %d: mflops=%.1f, result=%.1f\n",operand_size,mflops,result);
    return 0;
}

간결함을 위해 timer () 및 fill () 루틴은 포함되어 있지 않습니다. 코드를 실행하려면 여기에서 전체 소스를 찾을 수 있습니다.

http://codepad.org/agPWItZS

자, 여기가 흥미로운 부분입니다. 다음은 출력입니다.

Operand size: 2048
Vector size 2048: mflops=588.8, result=-67.8

이것은 X의 모든 요소가 루프 반복 사이에 캐시에 보관되어야한다는 사실에도 불구하고 완전히 캐시되지 않은 성능입니다. 다음에 의해 생성 된 어셈블리 코드보기 :

g++ -O3 -S -fno-asynchronous-unwind-tables register_opt_example.cpp

sum 함수 루프에서 한 가지 이상한 점이 있습니다.

L55:
    movsd   (%r12,%rax,8), %xmm0
    mulsd   %xmm1, %xmm0
    addsd   -72(%rbp), %xmm0
    movsd   %xmm0, -72(%rbp)
    incq    %rax
    cmpq    $2048, %rax
    jne L55

지시:

    addsd   -72(%rbp), %xmm0
    movsd   %xmm0, -72(%rbp)

스택의 sum ()에 "total"값을 저장하고 모든 루프 반복에서 읽고 쓰고 있음을 나타냅니다. 이 피연산자가 레지스터에 유지되도록 어셈블리를 수정했습니다.

...
addsd   %xmm0, %xmm3
...

이 작은 변화는 생성 엄청난 성능 향상을 :

Operand size: 2048
Vector size 2048: mflops=1958.9, result=-67.8

tl; dr 내 질문은 : 단일 위치가 L1 캐시에 저장되어야하는데 왜 단일 메모리 위치 액세스를 레지스터로 대체하면 코드 속도가 너무 빨라지 는가? 이를 가능하게하는 아키텍처 요인은 무엇입니까? 하나의 스택 위치를 반복적으로 작성하면 캐시의 효율성이 완전히 파괴된다는 것은 매우 이상해 보입니다.

부록

내 gcc 버전은 다음과 같습니다.

Target: i686-apple-darwin10
Configured with: /var/tmp/gcc/gcc-5646.1~2/src/configure --disable-checking --enable-werror --prefix=/usr --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin10 --with-gxx-include-dir=/include/c++/4.2.1 --program-prefix=i686-apple-darwin10- --host=x86_64-apple-darwin10 --target=i686-apple-darwin10
Thread model: posix
gcc version 4.2.1 (Apple Inc. build 5646) (dot 1)

내 CPU는 다음과 같습니다.

인텔 제온 X5650

---

Load Misprediction *과 함께 더 긴 종속성 체인의 조합 일 수 있습니다.

---

더 긴 종속성 체인 :

먼저 중요한 종속성 경로를 식별합니다. 그런 다음 http://www.agner.org/optimize/instruction_tables.pdf(117 페이지)에서 제공하는 지침 대기 시간을 살펴 봅니다.

최적화되지 않은 버전에서 중요한 종속성 경로는 다음과 같습니다.

• addsd -72(%rbp), %xmm0
• movsd %xmm0, -72(%rbp)

내부적으로는 다음과 같이 나뉩니다.

• 부하 (2주기)
• 추가 (3주기)
• 저장 (3주기)

최적화 된 버전을 보면 다음과 같습니다.

• 추가 (3주기)

따라서 8주기 대 3주기가 있습니다. 거의 3 배입니다.

Nehalem 프로세서 라인이 부하 의존성을 저장하는 데 얼마나 민감한 지, 그리고 얼마나 잘 전달 하는지 잘 모르겠습니다 . 그러나 그것이 0이 아니라고 믿는 것이 합리적입니다.

---

로드 스토어 오류 :

Modern processors use prediction in more ways you can imagine. The most famous of these is probably Branch Prediction. One of the lesser known ones is Load Prediction.

When a processor sees a load, it will immediately load it before all pending writes finish. It will assume that those writes will not conflict with the loaded values.

If an earlier write turns out to conflict with a load, then the load must be re-executed and the computation rolled back to the point of the load. (in much the same way that branch mispredictions roll back)

How it is relevant here:

Needless to say, modern processors will be able to execute multiple iterations of this loop simultaneously. So the processor will be attempting to perform the load (addsd -72(%rbp), %xmm0) before it finishes the store (movsd %xmm0, -72(%rbp)) from the previous iteration.

The result? The previous store conflicts with the load - thus a misprediction and a roll back.

_{*Note that I'm unsure of the name "Load Prediction". I only read about it in the Intel docs and they didn't seem to give it a name.}

---

I would surmise the problem isn't in the cache/memory access but in the processor (execution of your code). There are several visible bottlenecks here.

Performance numbers here were based on the boxes I was using (either sandybridge or westmere)

Peak performance for scalar math is 2.7Ghz x2 FLOPS/Clock x2 since processor can do an add and multiply simultaneously. Theoretical efficiency of the code is 0.6/(2.7*2) = 11%

Bandwidth needed: 2 doubles per (+) and (x) -> 4bytes/Flop 4 bytes * 5.4GFLOPS = 21.6GB/s

If you know it was read recently its likely in L1 (89GB/s), L2 (42GB/s) or L3(24GB/s) so we can rule out cache B/W

The memory susbsystem is 18.9 GB/s so even in main memory, peak performance should approach 18.9/21.6GB/s = 87.5 %

• May want to batch up requests (via unrolling) as early as possible

Even with speculative execution, tot += a *X[i] the adds will be serialized because tot(n) need to be eval'd before tot(n+1) can be kicked off

First unroll loop
move i by 8's and do

{//your func
    for( int i = 0; i < size; i += 8 ){
        tot += a * X[i];
        tot += a * X[i+1];
        ...
        tot += a * X[i+7];
    }
    return tot
}

Use multiple accumulators
This will break dependencies and allow us to avoid stalling on the addition pipeline

{//your func//
    int tot,tot2,tot3,tot4;
    tot = tot2 = tot3 = tot4 = 0
    for( int i = 0; i < size; i += 8 ) 
        tot  += a * X[i];
        tot2 += a * X[i+1];
        tot3 += a * X[i+2];
        tot4 += a * X[i+3];
        tot  += a * X[i+4];
        tot2 += a * X[i+5];
        tot3 += a * X[i+6];
        tot4 += a * X[i+7];
    }
    return tot + tot2 + tot3 + tot4;
}

UPDATE After running this on a SandyBridge box I have access to: (2.7GHZ SandyBridge with -O2 -march=native -mtune=native

Original code:

Operand size: 2048  
Vector size 2048: mflops=2206.2, result=61.8  
2.206 / 5.4 = 40.8%

Improved Code:

Operand size: 2048  
Vector size 2048: mflops=5313.7, result=61.8  
5.3137 / 5.4 = 98.4%  

---

I can't actually reproduce this because my compiler (gcc 4.7.2) keeps total in a register.

I suspect the main reason for the slowness doesn't have to do with the L1 cache, but rather is due to the data dependency between the store in

movsd   %xmm0, -72(%rbp)

and the load on the subsequent iteration:

addsd   -72(%rbp), %xmm0

참고URL : https://stackoverflow.com/questions/15665433/c-mysteriously-huge-speedup-from-keeping-one-operand-in-a-register