Culprit : False Data Dependency (컴파일러도 인식하지 못함)

Sandy / Ivy Bridge 및 Haswell 프로세서에서 다음 명령을 수행하십시오.

popcnt  src, dest

대상 레지스터에 대한 종속성이 잘못된 것으로 보입니다 dest. 명령은 명령에만 쓰지만 dest실행 전에 준비가 될 때까지 기다립니다 . 이 잘못된 종속성은 Intel에서 정오표 HSD146 (Haswell) 및 SKL029 (Skylake) 로 문서화했습니다.

Skylake가 lzcnt및에 대해이 문제를 해결했습니다tzcnt .
캐논 레이크 (및 아이스 레이크)가이 문제를 해결했습니다 popcnt.
bsf/ bsr실제 출력 종속성이 있습니다 : input = 0에 대해 수정되지 않은 출력. (그러나 내장 함수를 사용하는 방법 은 없습니다. AMD 문서 만 해당하며 컴파일러는이를 공개하지 않습니다.)

(예, 이러한 명령어는 모두 동일한 실행 단위에서 실행됩니다 ).

이 의존성은 popcnt단일 루프 반복에서 4 초를 유지하지 않습니다 . 루프 반복을 수행 할 수 있으므로 프로세서가 다른 루프 반복을 병렬화 할 수 없습니다.

unsigned대 uint64_t및 기타 비틀기 직접 문제에 영향을 미치지 않습니다. 그러나 레지스터를 변수에 할당하는 레지스터 할당 자에 영향을줍니다.

귀하의 경우, 속도는 레지스터 할당자가 수행하기로 결정한 것에 따라 (거짓) 종속성 체인에 붙어있는 것의 직접적인 결과입니다.

• 13기가바이트 / s는 체인을 가지고 : popcnt– add– popcnt– popcnt→ 다음 반복
• 15기가바이트 / s는 체인을 가지고 : popcnt– add– popcnt– add→ 다음 반복
• 20GB / s에는 체인이 있습니다 popcnt.- popcnt→ 다음 반복
• 26GB / s에는 체인이 있습니다 popcnt.- popcnt→ 다음 반복

20GB / s와 26GB / s의 차이는 간접 주소 지정의 사소한 것으로 보입니다. 어느 쪽이든,이 속도에 도달하면 프로세서가 다른 병목 현상을 시작합니다.

이것을 테스트하기 위해 인라인 어셈블리를 사용하여 컴파일러를 무시하고 원하는 어셈블리를 정확하게 얻었습니다. 또한 count변수를 분할 하여 벤치 마크에 혼란을 줄 수있는 다른 모든 종속성을 해제했습니다.

결과는 다음과 같습니다.

Sandy Bridge Xeon @ 3.5 GHz : (전체 테스트 코드는 하단에 있습니다)

• GCC 4.6.3 : g++ popcnt.cpp -std=c++0x -O3 -save-temps -march=native
• 우분투 12

다른 레지스터 : 18.6195 GB / s

.L4:
    movq    (%rbx,%rax,8), %r8
    movq    8(%rbx,%rax,8), %r9
    movq    16(%rbx,%rax,8), %r10
    movq    24(%rbx,%rax,8), %r11
    addq    $4, %rax

    popcnt %r8, %r8
    add    %r8, %rdx
    popcnt %r9, %r9
    add    %r9, %rcx
    popcnt %r10, %r10
    add    %r10, %rdi
    popcnt %r11, %r11
    add    %r11, %rsi

    cmpq    $131072, %rax
    jne .L4

동일한 레지스터 : 8.49272 GB / s

.L9:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # This time reuse "rax" for all the popcnts.
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L9

체인이 파손 된 동일한 레지스터 : 17.8869 GB / s

.L14:
    movq    (%rbx,%rdx,8), %r9
    movq    8(%rbx,%rdx,8), %r10
    movq    16(%rbx,%rdx,8), %r11
    movq    24(%rbx,%rdx,8), %rbp
    addq    $4, %rdx

    # Reuse "rax" for all the popcnts.
    xor    %rax, %rax    # Break the cross-iteration dependency by zeroing "rax".
    popcnt %r9, %rax
    add    %rax, %rcx
    popcnt %r10, %rax
    add    %rax, %rsi
    popcnt %r11, %rax
    add    %rax, %r8
    popcnt %rbp, %rax
    add    %rax, %rdi

    cmpq    $131072, %rdx
    jne .L14

그렇다면 컴파일러에 어떤 문제가 있습니까?

GCC 나 Visual Studio 모두 popcnt그러한 잘못된 종속성 이 있음을 인식하지 못하는 것 같습니다 . 그럼에도 불구하고 이러한 잘못된 의존성은 드문 일이 아닙니다. 컴파일러가 인식하고 있는지 여부는 문제입니다.

popcnt정확히 가장 많이 사용되는 명령은 아닙니다. 따라서 주요 컴파일러가 이와 같은 것을 놓칠 수 있다는 것은 놀라운 일이 아닙니다. 이 문제를 언급 한 문서는 어디에도 없습니다. 인텔이 공개하지 않으면 누군가 외부에 우연히 들어 오기 전까지는 아무도 외부에서 알 수 없습니다.

( 업데이트 : 버전 4.9.2 부터 GCC는 이러한 잘못된 종속성을 인식하고 최적화가 활성화 될 때이를 보상하는 코드를 생성합니다. Clang, MSVC 및 인텔 자체 ICC를 포함한 다른 공급 업체의 주요 컴파일러는 아직 인식하지 못하고 있습니다. 이 미세 아키텍처 정오표는이를 보완하는 코드를 생성하지 않습니다.)

CPU가 왜 이러한 잘못된 종속성을 가지고 있습니까?

우리는 추측 할 수는 같은 실행 장치에서 실행 bsf/ 수행 출력 의존성을 가지고있다. ( 하드웨어에서 POPCNT는 어떻게 구현됩니까? ). 이러한 지침에 대해 인텔은 input = 0의 정수 결과를 “정의되지 않은”(ZF = 1)로 기록하지만 인텔 하드웨어는 실제로 오래된 소프트웨어 (출력 수정되지 않은)를 깨뜨리지 않도록 더 강력하게 보장합니다. AMD는 이러한 행동을 기록합니다.bsr

아마도이 실행 장치에 대한 일부 uops를 출력에 의존하게 만드는 것은 다소 불편했지만 다른 것은 그렇지 않았습니다.

AMD 프로세서는이 잘못된 종속성을 가지고 있지 않습니다.

전체 테스트 코드는 다음과 같습니다.

#include <iostream>
#include <chrono>
#include <x86intrin.h>

int main(int argc, char* argv[]) {

   using namespace std;
   uint64_t size=1<<20;

   uint64_t* buffer = new uint64_t[size/8];
   char* charbuffer=reinterpret_cast<char*>(buffer);
   for (unsigned i=0;i<size;++i) charbuffer[i]=rand()%256;

   uint64_t count,duration;
   chrono::time_point<chrono::system_clock> startP,endP;
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %4  \n\t"
                "add %4, %0     \n\t"
                "popcnt %5, %5  \n\t"
                "add %5, %1     \n\t"
                "popcnt %6, %6  \n\t"
                "add %6, %2     \n\t"
                "popcnt %7, %7  \n\t"
                "add %7, %3     \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "No Chain\t" << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Chain 4   \t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }
   {
      uint64_t c0 = 0;
      uint64_t c1 = 0;
      uint64_t c2 = 0;
      uint64_t c3 = 0;
      startP = chrono::system_clock::now();
      for( unsigned k = 0; k < 10000; k++){
         for (uint64_t i=0;i<size/8;i+=4) {
            uint64_t r0 = buffer[i + 0];
            uint64_t r1 = buffer[i + 1];
            uint64_t r2 = buffer[i + 2];
            uint64_t r3 = buffer[i + 3];
            __asm__(
                "xor %%rax, %%rax   \n\t"   // <--- Break the chain.
                "popcnt %4, %%rax   \n\t"
                "add %%rax, %0      \n\t"
                "popcnt %5, %%rax   \n\t"
                "add %%rax, %1      \n\t"
                "popcnt %6, %%rax   \n\t"
                "add %%rax, %2      \n\t"
                "popcnt %7, %%rax   \n\t"
                "add %%rax, %3      \n\t"
                : "+r" (c0), "+r" (c1), "+r" (c2), "+r" (c3)
                : "r"  (r0), "r"  (r1), "r"  (r2), "r"  (r3)
                : "rax"
            );
         }
      }
      count = c0 + c1 + c2 + c3;
      endP = chrono::system_clock::now();
      duration=chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "Broken Chain\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
            << (10000.0*size)/(duration) << " GB/s" << endl;
   }

   free(charbuffer);
}

똑같이 흥미로운 벤치 마크는 여기에서 찾을 수 있습니다 : http://pastebin.com/kbzgL8si

이 벤치 마크는 popcnt(거짓) 의존성 체인에있는의 수를 변경합니다.

False Chain 0:  41959360000 0.57748 sec     18.1578 GB/s
False Chain 1:  41959360000 0.585398 sec    17.9122 GB/s
False Chain 2:  41959360000 0.645483 sec    16.2448 GB/s
False Chain 3:  41959360000 0.929718 sec    11.2784 GB/s
False Chain 4:  41959360000 1.23572 sec     8.48557 GB/s

답변

unsigned    41950110000 0.811198 sec    12.9263 GB/s
uint64_t    41950110000 0.622884 sec    16.8342 GB/s

unsigned    41950110000 0.623406 sec    16.8201 GB/s
uint64_t    41950110000 0.623685 sec    16.8126 GB/s

   uint64_t* bfrend = buffer+(size/8);
   uint64_t* bfrptr;

// ...

   {
      startP = chrono::system_clock::now();
      count = 0;
      for (unsigned k = 0; k < 10000; k++){
         // Tight unrolled loop with uint64_t
         for (bfrptr = buffer; bfrptr < bfrend;){
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
            count += __popcnt64(*bfrptr++);
         }
      }
      endP = chrono::system_clock::now();
      duration = chrono::duration_cast<std::chrono::nanoseconds>(endP-startP).count();
      cout << "uint64_t\t"  << count << '\t' << (duration/1.0E9) << " sec \t"
           << (10000.0*size)/(duration) << " GB/s" << endl;
   }

$LL5@main:
        mov     r10, rdi
        cmp     rdi, r15
        jae     SHORT $LN4@main
        npad    4
$LL2@main:
        mov     rax, QWORD PTR [r10+24]
        mov     rcx, QWORD PTR [r10+16]
        mov     r8, QWORD PTR [r10+8]
        mov     r9, QWORD PTR [r10]
        popcnt  rdx, rax
        popcnt  rax, rcx
        add     rdx, rax
        popcnt  rax, r8
        add     r10, 32
        add     rdx, rax
        popcnt  rax, r9
        add     rsi, rax
        add     rsi, rdx
        cmp     r10, r15
        jb      SHORT $LL2@main
$LN4@main:
        dec     r13
        jne     SHORT $LL5@main

[1829] /tmp/so_25078285 $ cat /proc/cpuinfo |grep CPU|head -n1
model name      : Intel(R) Core(TM) i3-3225 CPU @ 3.30GHz
[1829] /tmp/so_25078285 $ g++ --version|head -n1
g++ (Ubuntu/Linaro 4.7.3-1ubuntu1) 4.7.3

[1829] /tmp/so_25078285 $ g++ -O3 -march=native -std=c++11 test.cpp -o test_o3
[1829] /tmp/so_25078285 $ g++ -O3 -march=native -funroll-loops -fprefetch-loop-arrays -std=c++11     test.cpp -o test_o3_unroll_loops__and__prefetch_loop_arrays

[1829] /tmp/so_25078285 $ ./test_o3 1
unsigned        41959360000     0.595 sec       17.6231 GB/s
uint64_t        41959360000     0.898626 sec    11.6687 GB/s

[1829] /tmp/so_25078285 $ ./test_o3_unroll_loops__and__prefetch_loop_arrays 1
unsigned        41959360000     0.618222 sec    16.9612 GB/s
uint64_t        41959360000     0.407304 sec    25.7443 GB/s

  uint64_t subset_counts[4] = {};
  for( unsigned k = 0; k < 10000; k++){
     // Tight unrolled loop with unsigned
     unsigned i=0;
     while (i < size/8) {
        subset_counts[0] += _mm_popcnt_u64(buffer[i]);
        subset_counts[1] += _mm_popcnt_u64(buffer[i+1]);
        subset_counts[2] += _mm_popcnt_u64(buffer[i+2]);
        subset_counts[3] += _mm_popcnt_u64(buffer[i+3]);
        i += 4;
     }
  }
  count = subset_counts[0] + subset_counts[1] + subset_counts[2] + subset_counts[3];