C++: 1개의 피연산자를 레지스터에 유지하는 것이 불가사의할 정도로 고속화됨

C++: 1개의 피연산자를 레지스터에 유지하는 것이 불가사의할 정도로 고속화됨

다음 코드를 사용하여 어레이 요소를 스케일링하고 합산하는 루틴을 타이밍으로 설정함으로써 어레이가 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() 루틴은 간결성을 위해 포함되어 있지 않습니다.코드를 실행하는 경우는, 다음의 URL 에 그 풀 소스를 참조해 주세요.

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 캐시에 저장되어야 하는 상황에서 단일 메모리 위치 액세스를 레지스터로 대체하면 왜 이렇게 코드 속도가 빨라지는가 하는 것입니다.이를 가능하게 하는 아키텍처 요소는 무엇입니까?1개의 스택로케이션을 반복해서 쓰는 것이 캐시의 효과를 완전히 파괴하는 것은 매우 이상하다고 생각됩니다.

부록

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는 다음과 같습니다.

인텔 Xeon X5650

긴 의존관계 체인과 로드 미스프레딕션*의 조합일 가능성이 높습니다.

---

긴 의존 관계 체인:

우선 중요한 의존관계 경로를 특정합니다.다음으로 http://www.agner.org/optimize/instruction_tables.pdf (117페이지)에서 제공되는 명령 지연에 대해 살펴보겠습니다.

최적화되지 않은 버전에서는 중요한 의존관계 경로는 다음과 같습니다.

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

내부적으로는, 다음과 같이 분류됩니다.

• 로드(2사이클)
• addsd(3사이클)
• 스토어(3사이클)

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

• addsd(3사이클)

즉, 8 사이클이 3 사이클이 됩니다.거의 3배입니다.

Nehalem 프로세서 제품 라인은 저장 부하 의존성에 얼마나 민감하고 전송 성능이 어느 정도인지 잘 모르겠습니다.하지만 그게 0이 아니라고 믿는 게 타당해

---

로드 스토어 오류:

최신 프로세서는 사용자가 상상할 수 있는 다양한 방식으로 예측을 사용합니다.그 중 가장 유명한 것은 아마도 분기 예측일 것이다.잘 알려지지 않은 것 중 하나는 부하 예측입니다.

프로세서는 로드를 인식하면 보류 중인 모든 쓰기가 완료되기 전에 로드를 즉시 실행합니다.이러한 쓰기가 로드된 값과 충돌하지 않는다고 가정합니다.

이전의 쓰기가 부하와 경합하는 것으로 판명되면 부하를 재실행하고 부하 지점까지 계산을 롤백해야 합니다.(브런치 오보가 롤백되는 것과 거의 같은 방법으로)

여기서의 관련성:

말할 필요도 없이 최신 프로세서는 이 루프를 여러 번 동시에 실행할 수 있습니다.(「부하addsd -72(%rbp), %xmm0)에(점포 완료 전)movsd %xmm0, -72(%rbp)를 참조해 주세요를 참조해 주세요.

결과는?이전 저장소가 로드와 충돌하므로 잘못 예측되어 롤백됩니다.

_{* "부하 예측"이라는 이름은 잘 모르겠습니다.인텔 문서에서만 읽었을 뿐 이름은 밝히지 않은 것 같습니다.}

캐시/메모리 액세스가 아니라 프로세서(코드 실행)에 문제가 있는 것 같습니다.여기에는 몇 가지 눈에 보이는 병목 현상이 있습니다.

여기의 퍼포먼스 수치는 사용하고 있는 박스(sandybridge 또는 westmere)에 근거하고 있습니다.

프로세서가 덧셈과 곱셈을 동시에 수행할 수 있기 때문에 스칼라 산술의 피크 성능은 2.7Ghz x2 FLOPS/Clock x2입니다.코드의 이론적인 효율은 0.6/(2.7*2) = 11%입니다.

필요한 대역폭: (+)당 2배, (x) -> 4바이트 / Flop 4바이트 * 5.4GFLOPS = 21.6GB/초

최근에 읽은 것을 알고 있다면 캐시 B/W를 제외할 수 있도록 L1(89GB/s), L2(42GB/s), L3(24GB/s) 중 하나일 가능성이 높습니다.

메모리 서스 시스템은 18.9 GB/s이므로 메인 메모리에서도 피크 퍼포먼스는 18.9/21.6에 달합니다.GB/s = 87.5%

• 가능한 한 빨리 (언롤링을 통해) 요청을 일괄 처리하기를 원할 수 있습니다.

추측 실행 시에도 tot(n+1)을 시작하려면 tot(n)을 평가해야 하므로 tot += a *X[i] 추가가 직렬화됩니다.

첫 번째 언롤 루프
i를 8만큼 옮기고 하다

{//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
}

여러 개의 축전지 사용
이렇게 하면 의존 관계가 해소되어 추가 파이프라인에서 지연을 피할 수 있습니다.

{//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;
}

업데이트 SandyBridge 박스에서 실행한 후 다음 항목에 액세스할 수 있습니다. (2.7)GHZ SandyBridge (-O2 - march= - - - mtune = - ghz)

원래 코드:

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

개선된 코드:

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

제 컴파일러(gcc 4.7.2)는 이 파일을total등기부에

속도가 느린 주된 이유는 L1 캐시 때문이 아니라 저장소의 데이터 의존성 때문일 수 있습니다.

movsd   %xmm0, -72(%rbp)

및 후속 반복 시 부하:

addsd   -72(%rbp), %xmm0

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