it-gundan.com

정렬되지 않은 배열보다 정렬 된 배열을 처리하는 것이 더 빠른 이유는 무엇입니까?

매우 특이한 C++ 코드 조각이 있습니다. 이상한 이유로 데이터를 기적적으로 정렬하면 코드가 거의 6 배 더 빠릅니다.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::Rand() % 256;

    // !!! With this, the next loop runs faster
    std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}
  • std::sort(data, data + arraySize);이 없으면 11.54 초가 걸립니다.
  • 정렬 된 데이터를 사용하면 코드가 1.93 초 만에 실행됩니다.

처음에는 이것이 언어 또는 컴파일러 예외 일 수 있다고 생각했습니다. 그래서 나는 자바로 시도했다.

import Java.util.Arrays;
import Java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i)
        {
            // Primary loop
            for (int c = 0; c < arraySize; ++c)
            {
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

다소 유사하지만 덜 극단적 인 결과.


나의 첫 번째 생각은 정렬이 캐시에 데이터를 가져 왔지만 배열이 방금 생성 되었기 때문에 이것이 얼마나 어리석은 것인지 생각했습니다.

  • 무슨 일 이니?
  • 정렬되지 않은 배열보다 정렬 된 배열을 처리하는 것이 더 빠른 이유는 무엇입니까?
  • 이 코드는 몇 가지 독립적 인 용어를 요약 한 것이며 순서는 중요하지 않습니다.
22968
GManNickG

당신은 분기 예측 실패의 희생자입니다.


분기 예측이란 무엇입니까?

철도 교차점을 고려하십시오.

Image showing a railroad junction Image by Mecanismo, 위키 미디어 공용 CC-By-SA 3. 라이센스에 따라 사용됩니다.

이제 논쟁의 여지가 있기 위해, 이것이 장거리 또는 무선 통신 전에 1800 년대에 다시 시작되었다고 가정하십시오.

당신은 정션의 운영자이며 기차가 오는 소리를 듣습니다. 당신은 그것이 어느 방향으로 가야할지 모른다. 열차를 멈 추면 운전자에게 원하는 방향을 물어볼 수 있습니다. 그런 다음 스위치를 적절하게 설정하십시오.

열차는 무겁고 많은 관성이 있습니다. 그래서 그들은 시작하고 속도를 늦추기 위해 영원히 걸립니다 .

더 좋은 방법이 있습니까? 당신은 기차가 어느 방향으로 갈지 추측합니다!

  • 당신이 올바르게 추측하면 계속됩니다.
  • 당신이 틀렸다고 생각하면, 선장이 멈추고, 백업하고, 스위치를 뒤집으라고 소리 칠 것입니다. 그런 다음 다른 경로를 다시 시작할 수 있습니다.

매번 올바르게 추측하면 기차를 멈추지 않아도됩니다.
너무 잘못 생각하는 경우 , 기차는 정지, 백업 및 다시 시작하는 데 많은 시간을 소비합니다.


if-statement 고려 : 프로세서 수준에서는 분기 명령입니다.

Screenshot of compiled code containing an if statement

당신은 프로세서이고 지점을 볼 수 있습니다. 당신은 어떤 길로 갈지 모른다. 당신은 무엇을합니까? 실행을 중단하고 이전 지침이 완료 될 때까지 기다립니다. 그런 다음 올바른 경로를 계속 진행하십시오.

현대 프로세서는 복잡하고 파이프 라인이 길다. 그래서 그들은 "온난화"하고 "느리게"하기 위해 영원히 걸립니다 .

더 좋은 방법이 있습니까? 당신은 지점이 어느 방향으로 갈지 추측합니다!

  • 올바르게 추측하면 계속 실행합니다.
  • 잘못 추측 한 경우 파이프 라인을 플러시하고 분기로 롤백해야합니다. 그런 다음 다른 경로를 다시 시작할 수 있습니다.

매번 올바르게 추측하면 실행을 중단 할 필요가 없습니다.
너무 잘못 생각하는 경우 시간이 많이 걸리며, 정지, 롤백 및 다시 시작합니다.


이것은 분기 예측입니다. 나는 기차가 깃발로 방향을 알릴 수 있기 때문에 그것이 가장 좋은 비유가 아니라는 것을 인정한다. 그러나 컴퓨터에서 프로세서는 지점이 마지막 순간까지 어느 방향으로 갈지 알 수 없습니다.

그렇다면 열차가 백업하고 다른 경로로 내려가는 횟수를 최소화하기 위해 어떻게 전략적으로 추측 할 것입니까? 당신은 과거의 역사를 봅니다! 기차가 시간의 99 %를 왼쪽으로 가면 왼쪽으로 추측됩니다. 그것이 번갈아 가면 추측을 번갈아 가며 나타냅니다. 세 번마다 한 가지 방법으로 진행된다면 같은 생각입니다.

즉, 패턴을 식별하고 따라갑니다 . 이것은 분기 예측기의 작동 방식입니다.

대부분의 응용 프로그램에는 올바르게 동작하는 분기가 있습니다. 따라서 최신 지점 예측자는 일반적으로 90 % 이상의 적중률을 달성합니다. 그러나 인식 할 수있는 패턴이없는 예측할 수없는 분기에 직면 할 때 분기 예측기는 사실상 쓸모가 없습니다.

추가 참고 자료 : "Wikipedia의"지점 예측 자 "기사 .


위에서 암시 한 바와 같이 범인은이 if 문입니다.

if (data[c] >= 128)
    sum += data[c];

데이터는 0과 255 사이에 균등하게 분배됩니다. 데이터를 정렬 할 때 대략 절반의 반복이 if 문에 들어 가지 않습니다. 그 후, 그들은 모두 if 문에 들어갑니다.

분기가 연속적으로 같은 방향으로 여러 번 이동하기 때문에 분기 예측 변수에 매우 친숙합니다. 간단한 포화 카운터조차도 방향 전환 후 몇 번의 반복을 제외하고 분기를 정확하게 예측합니다.

빠른 시각화 :

T = branch taken
N = branch not taken

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (easy to predict)

그러나 데이터가 완전히 랜덤 인 경우, 분기 예측기는 랜덤 데이터를 예측할 수 없으므로 쓸모가 없게됩니다. 따라서 약 50 %의 잘못된 예측이있을 것입니다 (임의 추측보다 낫지 않음).

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ...
branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ...

       = TTNTTTTNTNNTTTN ...   (completely random - hard to predict)

그래서 무엇을 할 수 있습니까?

컴파일러가 분기를 조건부 이동으로 최적화 할 수없는 경우 성능에 대한 가독성을 기꺼이 희생하려는 경우 해킹을 시도 할 수 있습니다.

바꾸다:

if (data[c] >= 128)
    sum += data[c];

와:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

이렇게하면 분기가 제거되고 일부 비트 단위 작업으로 대체됩니다.

(이 해킹은 원래 if 문과 완전히 동일하지는 않지만이 경우 data[]의 모든 입력 값에 유효합니다.)

벤치 마크 : Core i7 920 @ 3.5 GHz

C++-Visual Studio 2010-x64 릴리스

//  Branch - Random
seconds = 11.777

//  Branch - Sorted
seconds = 2.352

//  Branchless - Random
seconds = 2.564

//  Branchless - Sorted
seconds = 2.587

Java-NetBeans 7.1.1 JDK 7-x64

//  Branch - Random
seconds = 10.93293813

//  Branch - Sorted
seconds = 5.643797077

//  Branchless - Random
seconds = 3.113581453

//  Branchless - Sorted
seconds = 3.186068823

관찰 :

  • 지점과 : 정렬 된 데이터와 정렬되지 않은 데이터 사이에는 큰 차이가 있습니다.
  • The Hack : 정렬 된 데이터와 정렬되지 않은 데이터 사이에는 차이가 없습니다.
  • C++의 경우 해킹은 데이터를 정렬 할 때 실제로 분기보다 느리게 느립니다.

일반적인 경험 법칙은 중요한 루프에서 데이터 종속 분기를 피하는 것입니다 (이 예와 같이).


업데이트 :

  • X64에서 -O3 또는 -ftree-vectorize를 사용하는 GCC 4.6.1은 조건부 이동을 생성 할 수 있습니다. 따라서 정렬 된 데이터와 정렬되지 않은 데이터 사이에는 차이가 없습니다. 둘 다 빠릅니다.

  • VC++ 2010은 /Ox 아래에서도이 분기에 대한 조건부 이동을 생성 할 수 없습니다.

  • Intel C++ Compiler (ICC) 11은 기적적인 일을합니다. 두 루프를 교환 함 을 통해 예측할 수없는 분기를 외부 루프로 들어 올립니다. 따라서 오해를 막을 수있을뿐만 아니라 VC++ 및 GCC가 생성 할 수있는 것보다 두 배 빠릅니다! 다시 말해 ICC는 벤치 마크를 물리 치기 위해 테스트 루프를 활용했습니다.

  • 인텔 컴파일러에 분기없는 코드를 제공하면 코드를 벡터화하여 분기와 마찬가지로 (루프 인터체인지) 빠릅니다.

이것은 성숙한 현대 컴파일러조차도 코드를 최적화하는 능력이 크게 다를 수 있음을 보여줍니다 ...

30545
Mysticial

분기 예측.

정렬 된 배열을 사용하면 data[c] >= 128 조건이 값 줄무늬에 대해 처음 false되고 모든 이후 값에 대해 true이됩니다. 그것은 예측하기 쉽습니다. 정렬되지 않은 배열을 사용하면 분기 비용을 지불하게됩니다.

3879
Daniel Fischer

데이터를 정렬 할 때 성능이 크게 향상되는 이유는 Mysticial 's answer 에 설명 된대로 분기 예측 패널티가 제거 되었기 때문입니다.

이제 코드를 보면

if (data[c] >= 128)
    sum += data[c];

이 특정 if... else... 분기의 의미는 조건이 충족 될 때 무언가를 추가하는 것임을 알 수 있습니다. 이 유형의 분기는 조건부 이동 문으로 쉽게 변환 될 수 있으며, 조건부 이동 명령으로 컴파일되는 cmovlx86 시스템. 분기 및 잠재적 분기 예측 패널티가 제거됩니다.

C에서 C++에서 x86의 조건부 이동 명령으로 직접 (최적화없이) 컴파일되는 명령문은 3 진 연산자 ... ? ... : ...입니다. 따라서 위의 문장을 동등한 문장으로 다시 작성합니다.

sum += data[c] >=128 ? data[c] : 0;

가독성을 유지하면서 속도 향상 요소를 확인할 수 있습니다.

Intel Core i7 -2600K @ 3.4GHz 및 Visual Studio 2010 릴리스 모드에서 벤치 마크는 다음과 같습니다 (Mysticial에서 복사 한 형식).

x86

//  Branch - Random
seconds = 8.885

//  Branch - Sorted
seconds = 1.528

//  Branchless - Random
seconds = 3.716

//  Branchless - Sorted
seconds = 3.71

x64

//  Branch - Random
seconds = 11.302

//  Branch - Sorted
 seconds = 1.830

//  Branchless - Random
seconds = 2.736

//  Branchless - Sorted
seconds = 2.737

결과는 여러 테스트에서 강력합니다. 분기 결과를 예측할 수 없을 때 속도가 크게 향상되지만 예측 가능할 때 약간의 어려움을 겪습니다. 실제로 조건부 이동을 사용하면 데이터 패턴에 관계없이 성능이 동일합니다.

이제 생성 된 x86 어셈블리를 조사하여보다 자세히 살펴 보겠습니다. 간단히하기 위해 max1max2의 두 가지 기능을 사용합니다.

max1는 조건부 if... else ...을 (를) 사용합니다.

int max1(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}

max2은 삼항 연산자 ... ? ... : ...를 사용합니다.

int max2(int a, int b) {
    return a > b ? a : b;
}

X86-64 시스템에서 GCC -S는 아래 어셈블리를 생성합니다.

:max1
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    -8(%rbp), %eax
    jle     .L2
    movl    -4(%rbp), %eax
    movl    %eax, -12(%rbp)
    jmp     .L4
.L2:
    movl    -8(%rbp), %eax
    movl    %eax, -12(%rbp)
.L4:
    movl    -12(%rbp), %eax
    leave
    ret

:max2
    movl    %edi, -4(%rbp)
    movl    %esi, -8(%rbp)
    movl    -4(%rbp), %eax
    cmpl    %eax, -8(%rbp)
    cmovge  -8(%rbp), %eax
    leave
    ret

max2는 명령어 cmovge의 사용으로 인해 훨씬 ​​적은 코드를 사용합니다. 그러나 실제 이득은 max2에 분기 점프 jmp이 포함되어 있지 않다는 것입니다. 이는 예상 된 결과가 맞지 않으면 성능이 크게 저하 될 수 있습니다.

그렇다면 조건부 이동이 더 나은 이유는 무엇입니까?

일반적인 x86 프로세서에서 명령 실행은 여러 단계로 나뉩니다. 대략, 우리는 다른 단계를 다루는 다른 하드웨어를 가지고 있습니다. 따라서 새로운 명령어를 시작하기 위해 하나의 명령어가 완료 될 때까지 기다릴 필요가 없습니다. 이것을 pipelining이라고합니다.

분기의 경우 다음 명령이 이전 명령에 의해 결정되므로 파이프 라이닝을 수행 할 수 없습니다. 기다리거나 예측해야합니다.

조건부 이동의 경우, 실행 조건부 이동 명령은 여러 단계로 나누어 지지만 FetchDecode과 같은 이전 단계는 이전 명령의 결과에 의존하지 않습니다. 후자의 단계 만 결과가 필요합니다. 따라서 하나의 명령 실행 시간의 일부를 기다립니다. 이것이 예측이 용이 할 때 조건부 이동 버전이 분기보다 느린 이유입니다.

이 책 컴퓨터 시스템 : 프로그래머의 관점, 제 2 판에서 이에 대해 자세히 설명합니다. 조건부 이동 명령 에 대해서는 3.6.6 절, 프로세서 아키텍처 에 대해서는 4 장 전체를, 및 지점 예측 및 오해에 대한 특별 처우 .

때로는 일부 최신 컴파일러가 더 나은 성능으로 코드를 어셈블리에 맞게 최적화 할 수 있고 때로는 일부 컴파일러에서는 그렇지 않을 수도 있습니다 (문제의 코드는 Visual Studio의 기본 컴파일러를 사용하고 있음). 예측할 수 없을 때 분기 및 조건부 이동 간의 성능 차이를 알면 시나리오가 너무 복잡해 컴파일러가 자동으로 최적화 할 수 없을 때 성능이 향상된 코드를 작성하는 데 도움이됩니다.

3180
WiSaGaN

이 코드에서 수행 할 수있는 더 많은 최적화에 대해 궁금한 점이 있다면 다음을 고려하십시오.

원래 루프로 시작 :

for (unsigned i = 0; i < 100000; ++i)
{
    for (unsigned j = 0; j < arraySize; ++j)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

루프 교환을 사용하면이 루프를 다음과 같이 안전하게 변경할 수 있습니다.

for (unsigned j = 0; j < arraySize; ++j)
{
    for (unsigned i = 0; i < 100000; ++i)
    {
        if (data[j] >= 128)
            sum += data[j];
    }
}

그런 다음 if 조건이 i 루프의 실행 과정에서 일정하다는 것을 알 수 있으므로 if을 끌어 올 수 있습니다.

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        for (unsigned i = 0; i < 100000; ++i)
        {
            sum += data[j];
        }
    }
}

그런 다음 부동 소수점 모델에서 허용하는 것으로 가정하면 내부 루프를 단일 표현식으로 축소 할 수 있습니다 (예 :/fp : throw)

for (unsigned j = 0; j < arraySize; ++j)
{
    if (data[j] >= 128)
    {
        sum += data[j] * 100000;
    }
}

그 중 하나는 이전보다 100,000 배 빠릅니다.

2143
vulcan raven

의심 할 여지없이 우리 중 일부는 CPU의 분기 예측기에 문제가되는 코드를 식별하는 방법에 관심을 가질 것입니다. Valgrind 도구 cachegrind에는 분기 예측기 시뮬레이터가 있으며 --branch-sim=yes 플래그를 사용하여 활성화됩니다. 이 질문의 예제를 통해 실행하면 외부 루프 수를 10000으로 줄이고 g++로 컴파일하면 다음과 같은 결과가 나타납니다.

정렬 :

==32551== Branches:        656,645,130  (  656,609,208 cond +    35,922 ind)
==32551== Mispredicts:         169,556  (      169,095 cond +       461 ind)
==32551== Mispred rate:            0.0% (          0.0%     +       1.2%   )

정렬되지 않음 :

==32555== Branches:        655,996,082  (  655,960,160 cond +  35,922 ind)
==32555== Mispredicts:     164,073,152  (  164,072,692 cond +     460 ind)
==32555== Mispred rate:           25.0% (         25.0%     +     1.2%   )

문제의 루프에 대해 cg_annotate에 의해 생성 된 줄 단위 출력으로 드릴 다운합니다.

정렬 :

          Bc    Bcm Bi Bim
      10,001      4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .      .  .   .      {
           .      .  .   .          // primary loop
 327,690,000 10,016  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .      .  .   .          {
 327,680,000 10,006  0   0              if (data[c] >= 128)
           0      0  0   0                  sum += data[c];
           .      .  .   .          }
           .      .  .   .      }

정렬되지 않음 :

          Bc         Bcm Bi Bim
      10,001           4  0   0      for (unsigned i = 0; i < 10000; ++i)
           .           .  .   .      {
           .           .  .   .          // primary loop
 327,690,000      10,038  0   0          for (unsigned c = 0; c < arraySize; ++c)
           .           .  .   .          {
 327,680,000 164,050,007  0   0              if (data[c] >= 128)
           0           0  0   0                  sum += data[c];
           .           .  .   .          }
           .           .  .   .      }

이렇게하면 문제가있는 행을 쉽게 식별 할 수 있습니다. 정렬되지 않은 버전에서는 if (data[c] >= 128) 행이 cachegrind의 분기 예측기 모델에서 잘못 예측 된 조건부 분기 (Bcm)를 164,050,007 발생시키는 반면 정렬 된 버전에서는 10,006 만 발생합니다.


또는 Linux에서 성능 카운터 하위 시스템을 사용하여 동일한 작업을 수행 할 수 있지만 CPU 카운터를 사용하여 기본 성능으로 수행 할 수 있습니다.

perf stat ./sumtest_sorted

정렬 :

 Performance counter stats for './sumtest_sorted':

  11808.095776 task-clock                #    0.998 CPUs utilized          
         1,062 context-switches          #    0.090 K/sec                  
            14 CPU-migrations            #    0.001 K/sec                  
           337 page-faults               #    0.029 K/sec                  
26,487,882,764 cycles                    #    2.243 GHz                    
41,025,654,322 instructions              #    1.55  insns per cycle        
 6,558,871,379 branches                  #  555.455 M/sec                  
       567,204 branch-misses             #    0.01% of all branches        

  11.827228330 seconds time elapsed

정렬되지 않음 :

 Performance counter stats for './sumtest_unsorted':

  28877.954344 task-clock                #    0.998 CPUs utilized          
         2,584 context-switches          #    0.089 K/sec                  
            18 CPU-migrations            #    0.001 K/sec                  
           335 page-faults               #    0.012 K/sec                  
65,076,127,595 cycles                    #    2.253 GHz                    
41,032,528,741 instructions              #    0.63  insns per cycle        
 6,560,579,013 branches                  #  227.183 M/sec                  
 1,646,394,749 branch-misses             #   25.10% of all branches        

  28.935500947 seconds time elapsed

또한 해체와 함께 소스 코드 주석을 수행 할 수 있습니다.

perf record -e branch-misses ./sumtest_unsorted
perf annotate -d sumtest_unsorted
 Percent |      Source code & Disassembly of sumtest_unsorted
------------------------------------------------
...
         :                      sum += data[c];
    0.00 :        400a1a:       mov    -0x14(%rbp),%eax
   39.97 :        400a1d:       mov    %eax,%eax
    5.31 :        400a1f:       mov    -0x20040(%rbp,%rax,4),%eax
    4.60 :        400a26:       cltq   
    0.00 :        400a28:       add    %rax,-0x30(%rbp)
...

자세한 내용은 성능 튜토리얼 을 참조하십시오.

1784
caf

방금이 질문과 답변을 읽었으며 대답이 누락되었다고 생각합니다.

관리 언어에서 특히 잘 작동하는 것으로 발견 된 분기 예측을 제거하는 일반적인 방법은 분기를 사용하는 대신 테이블 조회입니다 (이 경우 테스트하지는 않았지만).

이 접근법은 일반적으로 다음과 같은 경우에 작동합니다.

  1. 작은 테이블이고 프로세서에 캐시 될 가능성이 높습니다.
  2. 당신은 꽤 빡빡한 루프에서 일을하고 있거나 프로세서가 데이터를 미리로드 할 수 있습니다.

배경 및 이유

프로세서 관점에서 볼 때 메모리가 느립니다. 속도의 차이를 보완하기 위해 프로세서 (L1/L2 캐시)에 몇 가지 캐시가 내장되어 있습니다. 그래서 당신이 좋은 계산을하고 있다고 생각하고 당신이 기억의 조각을 필요로 알아보십시오. 프로세서는 '로드'연산을 수행하고 캐시에 메모리 조각을로드 한 다음 캐시를 사용하여 나머지 계산을 수행합니다. 메모리가 비교적 느리기 때문에이 '로드'는 프로그램 속도를 저하시킵니다.

분기 예측과 마찬가지로, 이것은 펜티엄 프로세서에서 최적화되었습니다. 프로세서는 데이터 조각을로드해야하며 캐시에 실제로로드되기 전에 캐시에로드하려고 시도합니다. 우리가 이미 본 것처럼, 분기 예측은 때로는 끔찍하게 잘못됩니다 - 최악의 시나리오에서 돌아가서 실제로 메모리로드를 기다릴 필요가 있습니다. 이것은 영원히 (실패한 분기 예측이 잘못되었습니다. , 브랜치 예측이 실패한 후 메모리로드가 무서운 것입니다.).

다행스럽게도 우리에게 메모리 액세스 패턴이 예측 가능한 경우 프로세서는 빠른 캐시에로드하므로 모든 것이 잘됩니다.

우리가 알아야 할 첫 번째 것은 small ? 일반적으로 크기는 더 작 으면 좋지만, 크기가 4096 바이트 미만인 조회 테이블을 사용하는 것이 좋습니다. 상한선 : 조회 테이블이 64K보다 큰 경우 재검토 가치가 있습니다.

테이블 만들기

그래서 우리는 작은 테이블을 만들 수 있다는 것을 알아 냈습니다. 다음으로 할 일은 조회 기능을 제자리에 놓는 것입니다. 조회 함수는 대개 몇 가지 기본 정수 연산 (및 또는, xor, shift, add, remove 및 아마도 곱하기)을 사용하는 작은 함수입니다. 조회 기능을 통해 테이블의 '고유 키'에 대한 입력을 번역하려는 경우 원하는 모든 작업에 대한 대답을 제공하기 만하면됩니다.

이 경우 :> = 128은 값을 유지할 수 있음을 의미하고 <128은 제거한다는 의미입니다. 가장 쉬운 방법은 'AND'를 사용하는 것입니다 : 우리가 그것을 지키면 7FFFFFFF와 AND합니다. 우리가 그것을 제거하고 싶다면 우리는 0과 함께합니다. 128은 2의 거듭 제곱입니다 - 그래서 우리는 32768/128 정수의 테이블을 만들어 하나의 0과 많은 값으로 채울 수 있습니다 7FFFFFFFF의.

관리되는 언어

왜 이것이 관리되는 언어로 잘 작동하는지 궁금 할 것입니다. 결국, 관리되는 언어는 분기가있는 배열의 경계를 확인하여 혼란스럽지 않게합니다.

음, 정확히는 ... :-)

관리되는 언어에 대해이 지점을 제거하는 데 상당한 노력이있었습니다. 예 :

for (int i = 0; i < array.Length; ++i)
{
   // Use array[i]
}

이 경우 컴파일러에서는 경계 조건에 결코 부딪치지 않습니다. 적어도 Microsoft JIT 컴파일러 (하지만 Java가 비슷한 일을 할 것으로 예상 함)는이를 알아 차리고 검사를 완전히 제거합니다. 와우, 그건 가지가 없다는 뜻이야. 마찬가지로 다른 명백한 경우도 처리 할 것입니다.

관리되는 언어로 조회에 문제가 생기는 경우 - 핵심은 경계 검사를 예측 가능하게 만들기 위해 & 0x[something]FFF를 조회 기능에 추가하여 더 빠르게 진행되는 것을 지켜 보는 것입니다.

이 사건의 결과

// Generate data
int arraySize = 32768;
int[] data = new int[arraySize];

Random random = new Random(0);
for (int c = 0; c < arraySize; ++c)
{
    data[c] = random.Next(256);
}

/*To keep the spirit of the code intact, I'll make a separate lookup table
(I assume we cannot modify 'data' or the number of loops)*/

int[] lookup = new int[256];

for (int c = 0; c < 256; ++c)
{
    lookup[c] = (c >= 128) ? c : 0;
}

// Test
DateTime startTime = System.DateTime.Now;
long sum = 0;

for (int i = 0; i < 100000; ++i)
{
    // Primary loop
    for (int j = 0; j < arraySize; ++j)
    {
        /* Here you basically want to use simple operations - so no
        random branches, but things like &, |, *, -, +, etc. are fine. */
        sum += lookup[data[j]];
    }
}

DateTime endTime = System.DateTime.Now;
Console.WriteLine(endTime - startTime);
Console.WriteLine("sum = " + sum);
Console.ReadLine();
1247
atlaste

배열이 정렬 될 때 데이터가 0에서 255 사이로 분산되기 때문에 반복의 처음 절반은 if- 문을 입력하지 않습니다 (if 문은 아래에 공유됩니다).

if (data[c] >= 128)
    sum += data[c];

질문 : 정렬 된 데이터의 경우처럼 위의 명령문이 특정 경우 실행되지 않는 이유는 무엇입니까? 여기에 "분기 예측 자"가옵니다. 분기 예측자는 분기 (예 : if-then-else 구조)가 확실하게 알려지기 전에 어떤 방식으로 진행되는지 추측하려고하는 디지털 회로입니다. 분기 예측기의 목적은 명령 파이프 라인의 흐름을 개선하는 것입니다. 분기 예측자는 높은 효율을 달성하는 데 중요한 역할을합니다!

더 잘 이해하기 위해 벤치 마킹을 해보 죠

if- 문의 성능은 조건에 예측 가능한 패턴이 있는지 여부에 따라 달라집니다. 조건이 항상 참이거나 항상 거짓이면 프로세서의 분기 예측 논리가 패턴을 선택합니다. 반면 패턴이 예측할 수없는 경우 if- 문이 훨씬 더 비쌉니다.

다른 조건에서이 루프의 성능을 측정합시다.

for (int i = 0; i < max; i++)
    if (condition)
        sum++;

다음은 서로 다른 true-false 패턴을 사용하는 루프의 타이밍입니다.

Condition                Pattern             Time (ms)
-------------------------------------------------------
(i & 0×80000000) == 0    T repeated          322

(i & 0xffffffff) == 0    F repeated          276

(i & 1) == 0             TF alternating      760

(i & 3) == 0             TFFFTFFF…           513

(i & 2) == 0             TTFFTTFF…           1675

(i & 4) == 0             TTTTFFFFTTTTFFFF…   1275

(i & 8) == 0             8T 8F 8T 8F …       752

(i & 16) == 0            16T 16F 16T 16F …   490

" bad "true-false 패턴은 " good "패턴보다 최대 6 배까지 if- 구문을 만들 수 있습니다! 물론 어떤 패턴이 좋고 어떤 패턴이 나쁜지는 컴파일러와 특정 프로세서에서 생성 된 정확한 명령어에 달려 있습니다.

따라서 분기 예측이 성능에 미치는 영향에 대해서는 의심의 여지가 없습니다!

1118
Saqlain

분기 예측 오류를 방지하는 한 가지 방법은 조회 테이블을 작성하고 데이터를 사용하여 색인을 생성하는 것입니다. Stefan de Bruijn은 그의 대답에서 그것을 토의했다.

그러나이 경우 값은 [0, 255] 범위에 있으며 값> = 128 만 신경 씁니다. 즉, 값을 원하는지 아닌지를 알려주는 단일 비트를 쉽게 추출 할 수 있습니다. 즉, 오른쪽 7 비트의 데이터는 0 비트 또는 1 비트로 남게되며 1 비트가있을 때만 값을 추가하려고합니다. 이 비트를 "결정 비트"라고합시다.

결정 비트의 0/1 값을 배열의 인덱스로 사용하여 데이터 정렬 여부에 상관없이 똑같은 속도의 코드를 만들 수 있습니다. 우리의 코드는 항상 값을 추가하지만 결정 비트가 0 일 때 우리는 걱정하지 않는 값을 추가 할 것입니다. 코드는 다음과 같습니다.

// Test
clock_t start = clock();
long long a[] = {0, 0};
long long sum;

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        int j = (data[c] >> 7);
        a[j] += data[c];
    }
}

double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
sum = a[1];

이 코드는 추가의 절반을 낭비하지만 분기 예측 실패는 결코 발생하지 않습니다. 실제 if 문을 사용하는 버전보다 무작위 데이터가 훨씬 빠릅니다.

그러나 내 테스트에서 룩업 테이블에 대한 인덱싱이 비트 이동보다 약간 빠르기 때문에 명시 적 조회 테이블이 이보다 약간 빨랐습니다. 이 코드는 내 코드가 설정되고 조회 테이블을 사용하는 방법을 보여줍니다 (코드에서 "LookUp Table"에 lut이라고 상상하지 못합니다). C++ 코드는 다음과 같습니다.

// declare and then fill in the lookup table
int lut[256];
for (unsigned c = 0; c < 256; ++c)
    lut[c] = (c >= 128) ? c : 0;

// use the lookup table after it is built
for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
        sum += lut[data[c]];
    }
}

이 경우 룩업 테이블은 256 바이트 였으므로 캐시에 적합하여 모두 빠릅니다. 데이터가 24 비트 값이고이 중 절반 만 원한다면이 기술은 잘 작동하지 않을 것입니다 ... 룩업 테이블이 너무 커서 실용적이지는 않을 것입니다. 반면에 우리는 위에 표시된 두 가지 기술을 결합 할 수 있습니다. 먼저 비트를 이동 한 다음 찾아보기 테이블을 인덱싱합니다. 상반부 값만 원하는 24 비트 값의 경우 데이터를 12 비트 오른쪽으로 이동하고 테이블 인덱스의 12 비트 값으로 남겨 둘 수 있습니다. 12 비트 테이블 인덱스는 실용적 일 수있는 4096 값의 테이블을 의미합니다.

if 문을 사용하는 대신 배열에 인덱싱하는 기술을 사용하여 사용할 포인터를 결정할 수 있습니다. 나는 2 진 트리를 구현 한 라이브러리를 보았고 두 개의 명명 된 포인터 (pLeftpRight 또는 무엇이든) 대신 포인터의 길이 2 배열을 사용하고 "결정 비트"기술을 사용하여 어떤 것을 따르는 지 결정했습니다. 예를 들어, 대신 :

if (x < node->value)
    node = node->pLeft;
else
    node = node->pRight;

이 라이브러리는 다음과 같은 것을 할 것이다 :

i = (x < node->value);
node = node->link[i];

다음은이 코드에 대한 링크입니다 : 적색 검은 나무 , 외설적으로 혼란

1039
steveha

정렬 된 경우 성공적인 분기 예측이나 분기없는 비교 트릭에 의존하는 것보다 더 잘할 수 있습니다. 분기를 완전히 제거하십시오.

실제로 배열은 data < 128가있는 연속 영역과 data >= 128가있는 영역으로 분할됩니다. 따라서 파티션 포인트는 이분법 검색 (Lg(arraySize) = 15 비교를 사용)을 찾아서 그 포인트에서 직선적으로 누적시켜야합니다.

같은 (확인되지 ​​않음)

int i= 0, j, k= arraySize;
while (i < k)
{
  j= (i + k) >> 1;
  if (data[j] >= 128)
    k= j;
  else
    i= j;
}
sum= 0;
for (; i < arraySize; i++)
  sum+= data[i];

또는 약간 더 난독 화 된

int i, k, j= (i + k) >> 1;
for (i= 0, k= arraySize; i < k; (data[j] >= 128 ? k : i)= j)
  j= (i + k) >> 1;
for (sum= 0; i < arraySize; i++)
  sum+= data[i];

정렬 된 또는 정렬되지 않은 두 가지 모두에 대해 approximate solution을 제공하는보다 빠른 접근법은 다음과 같습니다. sum= 3137536; (진정한 균일 분포를 가정하면 예상 값 191.5의 16384 샘플) :-)

942
Yves Daoust

위의 동작은 분기 예측으로 인해 발생합니다.

분기 예측을 이해하려면 먼저 명령 파이프 라인 을 이해해야합니다.

모든 명령은 일련의 단계로 나뉘어 서로 다른 단계를 동시에 실행할 수 있습니다. 이 기술을 명령 파이프 라인이라고하며 최신 프로세서의 처리량을 높이는 데 사용됩니다. 이것을 더 잘 이해하려면 다음을 참조하십시오 Wikipedia의 예 .

일반적으로 최신 프로세서에는 파이프 라인이 상당히 길지만 쉽게 4 단계 만 고려해 봅시다.

  1. IF-메모리에서 명령어를 가져옵니다
  2. ID-명령어 해독
  3. EX-명령 실행
  4. WB-CPU 레지스터에 다시 쓰기

일반적으로 2 개의 명령에 대한 4 단계 파이프 라인.  4-stage pipeline in general

위의 질문으로 돌아가서 다음 지침을 고려하십시오.

                        A) if (data[c] >= 128)
                                /\
                               /  \
                              /    \
                        true /      \ false
                            /        \
                           /          \
                          /            \
                         /              \
              B) sum += data[c];          C) for loop or print().

분기 예측이 없으면 다음이 발생합니다.

명령어 B 또는 명령어 C를 실행하려면 명령어 B 또는 명령어 C로가는 결정이 명령어 A의 결과에 따라 달라지기 때문에 프로세서는 명령어 A가 파이프 라인의 EX 단계까지 도달하지 않을 때까지 기다려야합니다. 이렇게 보일 것입니다.

조건이 true를 반환하는 경우 :  enter image description here

조건이 거짓을 반환하는 경우 :  enter image description here

명령어 A의 결과를 기다린 결과, 위의 경우에 사용 된 총 CPU주기 (분기 예측없이, 참과 거짓 모두)는 7입니다.

분기 예측이란 무엇입니까?

브랜치 예측기는 브랜치 (if-then-else 구조)가 어떤 방식으로 진행 될지 추측하려고 시도합니다. 명령 A가 파이프 라인의 EX 단계에 도달 할 때까지 기다리지는 않지만 결정을 추측하고 해당 명령 (이 예에서는 B 또는 C)으로 이동합니다.

정확한 추측의 경우 파이프 라인은 다음과 같습니다.  enter image description here

나중에 추측이 잘못되었다는 것이 감지되면 부분적으로 실행 된 명령이 삭제되고 파이프 라인이 올바른 분기로 시작하여 지연이 발생합니다. 분기 잘못 예측 된 경우 낭비되는 시간은 파이프 라인의 페치 단계에서 실행 단계까지의 단계 수와 같습니다. 최신 마이크로 프로세서는 파이프 라인이 매우 길기 때문에 오 탐지 지연이 10 ~ 20 클럭주기입니다. 파이프 라인이 길수록 좋은 분기 예측기 의 필요성이 커집니다.

OP의 코드에서 조건부, 분기 예측기는 처음으로 예측을 기반으로 할 정보가 없으므로 처음으로 다음 명령을 임의로 선택합니다. 나중에 for 루프에서 히스토리를 기반으로 예측할 수 있습니다. 오름차순으로 정렬 된 배열의 경우 세 가지 가능성이 있습니다.

  1. 모든 요소는 128보다 작습니다
  2. 모든 요소가 128보다 큽니다.
  3. 일부 새로운 시작 요소는 128보다 작으며 나중에 128보다 큽니다.

예측자가 항상 첫 번째 실행에서 실제 분기를 가정한다고 가정합시다.

따라서 첫 번째 경우 역사적으로 모든 예측이 정확하기 때문에 항상 진정한 분기를 취합니다. 두 번째 경우 처음에는 잘못 예측하지만 몇 번의 반복 후에 올바르게 예측합니다. 세 번째 경우에는 요소가 128보다 작을 때까지 처음에 정확하게 예측합니다. 그 후 일정 시간 동안 실패하고 히스토리에서 분기 예측 실패를 볼 때 자체가 올바른 것입니다.

이러한 모든 경우에 실패 횟수가 너무 적으므로 결과적으로 부분적으로 실행 된 명령어를 버리고 올바른 분기로 다시 시작하면 CPU주기가 줄어 듭니다.

그러나 임의의 정렬되지 않은 배열의 경우 예측은 부분적으로 실행 된 명령어를 버리고 대부분의 올바른 분기로 다시 시작하여 정렬 된 배열에 비해 더 많은 CPU주기를 가져와야합니다.

789
Harsh Sharma

공식적인 대답은

  1. 인텔 - 지점 미스 비용 피하기
  2. Intel - 예측 오류를 방지하기위한 분기 및 루프 재구성
  3. 과학 논문 - 분기 예측 컴퓨터 아키텍처
  4. 책 : J.L. Hennessy, D.A. 패터슨 : 컴퓨터 아키텍처 : 정량적 접근
  5. 과학 출판물의 기사 : T.Y. Yeh, Y.N. Patt는 분기 예측에 대해 이러한 작업을 많이 수행했습니다.

이 멋진 diagram branch predictor가 혼란스러워하는 이유를 볼 수 있습니다.

 2-bit state diagram

원래 코드의 각 요소는 임의의 값입니다.

data[c] = std::Rand() % 256;

그래서 예측자는 std::Rand() 타격으로 측면을 바꿀 것입니다.

반면에 일단 정렬되면 예측자는 먼저 강하게 받아 들여지지 않는 상태로 바뀌고 값이 높은 값으로 바뀌면 예측자는 강하게 잡히지 않은 상태에서 강하게 수행 된 상태로 변화를 통해 3 단계로 진행됩니다.


669
Surt

같은 줄에서 (나는 이것이 어떤 대답으로도 강조 표시되지 않았다고 생각한다) 때로는 (특히 리눅스 커널과 같은 성능 문제가있는 소프트웨어에서) 다음과 같은 if 문을 찾을 수 있다고 언급하는 것이 좋다 :

if (likely( everything_is_ok ))
{
    /* Do something */
}

또는 유사하게 :

if (unlikely(very_improbable_condition))
{
    /* Do something */    
}

likely()unlikely()은 사실 GCC의 __builtin_expect와 같은 것을 사용하여 정의 된 매크로입니다. 컴파일러가 사용자가 제공 한 정보를 고려하여 조건을 선호하는 예측 코드를 삽입하는 데 도움이됩니다. GCC는 실행중인 프로그램의 동작을 변경하거나 캐시 지우기 등과 같은 저수준 명령을 내릴 수있는 다른 내장 명령을 지원합니다. 이 설명서 는 사용 가능한 GCC 내장 명령을 참조하십시오.

일반적으로 이러한 종류의 최적화는 주로 하드 실시간 응용 프로그램이나 실행 시간이 중요한 중요한 임베디드 시스템에서 찾아 볼 수 있습니다. 예를 들어 1/10000000 번 발생하는 오류 조건을 확인하는 경우 컴파일러에 알리지 않는 이유는 무엇입니까? 이 방법은 기본적으로 분기 예측은 조건이 거짓이라고 가정합니다.

634
rkachach

C++에서 자주 사용되는 부울 연산은 컴파일 된 프로그램에서 많은 분기를 생성합니다. 이러한 분기가 루프 내부에 있고 예측하기 어려운 경우 실행 속도가 크게 느려질 수 있습니다. 부울 변수는 false의 경우 _0_ 값과 true의 경우 _1_ 값을 갖는 8 비트 정수로 저장됩니다.

부울 변수를 입력으로 사용하는 모든 연산자는 입력에 _0_ 또는 _1_ 이외의 값이 있는지 확인하지만 부울을 출력으로 사용하는 연산자는 다른 값을 생성 할 수 없다는 점에서 부울 변수가 과도하게 결정됩니다. _0_ 또는 _1_. 따라서 부울 변수를 입력으로 사용하여 필요한 것보다 효율성이 떨어집니다. 예를 들어 보자.

_bool a, b, c, d;
c = a && b;
d = a || b;
_

이것은 일반적으로 다음과 같은 방식으로 컴파일러에 의해 구현됩니다.

_bool a, b, c, d;
if (a != 0) {
    if (b != 0) {
        c = 1;
    }
    else {
        goto CFALSE;
    }
}
else {
    CFALSE:
    c = 0;
}
if (a == 0) {
    if (b == 0) {
        d = 0;
    }
    else {
        goto DTRUE;
    }
}
else {
    DTRUE:
    d = 1;
}
_

이 코드는 최적이 아닙니다. 잘못 예측할 경우 지점에 시간이 오래 걸릴 수 있습니다. 피연산자에 _0_ 및 _1_ 이외의 다른 값이없는 것으로 확실하게 알려진 경우 부울 연산을 훨씬 효율적으로 만들 수 있습니다. 컴파일러가 이러한 가정을하지 않는 이유는 변수가 초기화되지 않았거나 알 수없는 소스에서 온 경우 다른 값을 가질 수 있기 때문입니다. 위 코드는 ab이 유효한 값으로 초기화되었거나 부울 출력을 생성하는 연산자에서 온 경우 최적화 될 수 있습니다. 최적화 된 코드는 다음과 같습니다.

_char a = 0, b = 1, c, d;
c = a & b;
d = a | b;
_

부울 연산자 대신에 비트 연산자 (_&_ 및 _|_)를 사용할 수 있도록 char 대신 bool이 사용됩니다 (_&&_ 및 _||_). 비트 연산자는 하나의 클럭 주기만 수행하는 단일 명령어입니다. OR 연산자 (_|_)는 ab에 _0_ 또는 _1_ 이외의 다른 값이있는 경우에도 작동합니다. AND 연산자 (_&_) 및 EXCLUSIVE OR 연산자 (_^_)는 피연산자가 _0_ 및 _1_ 이외의 다른 값을 갖는 경우 일관되지 않은 결과를 제공 할 수 있습니다. .

_~_는 NOT으로 사용할 수 없습니다. 대신 _0_로 XOR하여 _1_ 또는 _1_로 알려진 변수에 부울 NOT을 만들 수 있습니다.

_bool a, b;
b = !a;
_

다음에 최적화 될 수 있습니다.

_char a = 0, b;
b = a ^ 1;
_

ba (_a && b_이 (가) _를 평가하지 않으면 false이 평가되지 않아야하는 표현식 인 경우 _a & b_를 _&&_로 대체 할 수 없습니다 b, _&_입니다. 마찬가지로 batrue 인 경우 평가하지 않아야하는 표현식 인 경우 _a || b_을 _a | b_로 바꿀 수 없습니다.

피연산자가 비교 인 경우보다 피연산자가 변수 인 경우 비트 연산자를 사용하는 것이 더 유리합니다.

_bool a; double x, y, z;
a = x > y && z < 5.0;
_

_&&_식이 많은 분기 오판을 생성 할 것으로 예상하지 않는 한 대부분의 경우 최적입니다.

630
Maciej

그건 확실합니다!...

분기 예측은 코드에서 발생하는 전환으로 인해 로직이 느리게 실행됩니다! 마치 똑바로 서거나 길을가는 것과 같습니다. 똑바로 가려면 더 빨리 할 수 ​​있습니다! ...

배열이 정렬 된 경우 첫 번째 단계에서 조건이 false가됩니다. data[c] >= 128는 길 끝까지가는 모든 곳에서 참값이됩니다. 이것이 논리의 끝을 빨리 얻는 방법입니다. 반면에 정렬되지 않은 배열을 사용하면 코드를 더 느리게 실행할 수 있도록 터닝 및 처리가 많이 필요합니다.

아래에서 내가 당신을 위해 만든 이미지를보십시오. 어느 거리가 더 빨리 끝날 것입니까?

 Branch Prediction

그래서 프로그래밍 방식으로 분기 예측 프로세스가 느려지 게됩니다 ...

또한 결국에는 각기 다른 방식으로 코드에 영향을 미칠 두 종류의 분기 예측이 있음을 알면 좋습니다.

1. 정적

2. 동적

 Branch Prediction

정적 분기 예측은 조건부 분기가 처음 발견 될 때 마이크로 프로세서에 의해 사용되며 동적 분기 예측은 조건 분기 코드의 후속 실행에 사용됩니다.

이러한 규칙을 효과적으로 활용하도록 코드를 작성하려면 if-else 또는 switch 문을 작성할 때 가장 일반적인 경우를 먼저 확인하고 점차적으로 가장 일반적인 것으로 확인하십시오. 루프 반복자의 조건 만 정상적으로 사용되기 때문에 루프는 정적 분기 예측을 위해 특수한 코드 순서를 반드시 요구하지는 않습니다.

280
Alireza

이 질문은 여러 번 이미 훌륭하게 답변되었습니다. 여전히 흥미로운 또 다른 분석에 그룹의 관심을 끌고 싶습니다.

최근에이 예제 (약간 수정)는 Windows에서 프로그램 자체 내에서 코드 조각을 프로파일 링하는 방법을 보여주기위한 방법으로도 사용되었습니다. 또한 저자는 정렬 된 & 정렬되지 않은 경우에 코드가 대부분의 시간을 보내는 곳을 결정하기 위해 결과를 사용하는 방법을 보여줍니다. 마침내이 부분은 HAL (Hardware Abstraction Layer)의 조금 알려진 기능을 사용하여 정렬되지 않은 경우에 얼마나 많은 분기 예측 오류가 발생 하는지를 확인하는 방법을 보여줍니다.

링크는 여기에 있습니다 : http://www.geoffchappell.com/studies/windows/km/ntoskrnl/api/ex/profile/demo.htm

262
ForeverLearning

이미 다른 사람들이 언급했듯이, 수수께끼 뒤에 숨은 것은 지점 예측 자 입니다.

나는 무언가를 추가하지 않고 다른 방법으로 개념을 설명하려고합니다. 위키에 텍스트와 다이어그램이 포함 된 간결한 소개가 있습니다. 나는 다이어그램을 사용하여 지점 예측자를 직관적으로 정교하게하는 아래 설명을 좋아합니다.

컴퓨터 아키텍처에서 브랜치 예측기는 브랜치 (예 : if-then-else 구조)가 어떤 방식으로 진행 될지 추측하려고 시도하는 디지털 회로입니다. 분기 예측기의 목적은 명령 파이프 라인의 흐름을 개선하는 것입니다. 지점 예측자는 x86과 같은 많은 최신 파이프 라인 마이크로 프로세서 아키텍처에서 높은 효과적인 성능을 달성하는 데 중요한 역할을합니다.

양방향 분기는 일반적으로 조건부 점프 명령으로 구현됩니다. 조건부 점프는 "취득되지 않음"일 수 있고 조건부 점프 직후에 오는 첫 번째 코드 분기로 실행을 계속하거나 "취득"하여 프로그램 메모리에서 두 번째 코드 분기가있는 다른 위치로 점프 할 수 있습니다. 저장되었습니다. 조건이 계산되고 조건 파이프가 명령 파이프 라인의 실행 단계를 통과 할 때까지 조건부 점프가 수행되는지 여부는 확실하지 않습니다 (그림 1 참조).

figure 1

설명 된 시나리오를 기반으로 다양한 상황에서 파이프 라인에서 명령이 실행되는 방법을 보여주는 애니메이션 데모를 작성했습니다.

  1. 지점 예측기가 없습니다.

분기 예측이 없으면 프로세서는 조건부 점프 명령이 실행 단계를 통과 할 때까지 기다려야 다음 명령이 파이프 라인의 페치 단계에 들어갈 수 있습니다.

이 예제에는 세 개의 명령어가 포함되어 있으며 첫 번째 명령어는 조건부 점프 명령어입니다. 후자의 두 명령어는 조건부 점프 명령어가 실행될 때까지 파이프 라인으로 들어갈 수 있습니다.

without branch predictor

3 개의 명령이 완료 되려면 9 클럭주기가 걸립니다.

  1. Branch Predictor를 사용하고 조건부로 점프하지 마십시오. 예측이 조건부 점프를 취하는 not 이라고 가정합니다.

enter image description here

3 개의 명령이 완료 되려면 7 클럭주기가 걸립니다.

  1. Branch Predictor를 사용하고 조건부로 점프하십시오. 예측이 조건부 점프를 취하는 not 이라고 가정합니다.

enter image description here

3 개의 명령이 완료 되려면 9 클럭주기가 걸립니다.

분기 잘못 예측 된 경우 낭비되는 시간은 파이프 라인의 페치 단계에서 실행 단계까지의 단계 수와 같습니다. 최신 마이크로 프로세서는 파이프 라인이 매우 길기 때문에 오 탐지 지연이 10 ~ 20 클럭주기입니다. 결과적으로 파이프 라인을 더 길게 만들면 고급 분기 예측기의 필요성이 높아집니다.

보시다시피 지점 예측기를 사용하지 않는 이유는 없습니다.

Branch Predictor의 매우 기본적인 부분을 설명하는 매우 간단한 데모입니다. 해당 GIF가 성가신 경우 답변에서 자유롭게 제거하고 방문자는 BranchPredictorDemo 에서 데모를 얻을 수 있습니다.

200
Gearon

분기 예측 이득!

분기 예측이 프로그램을 느리게하지 않는다는 것을 이해하는 것이 중요합니다. 누락 된 예측의 비용은 분기 예측이 존재하지 않는 것과 마찬가지로 표현식의 평가가 실행될 코드를 결정하기를 기다렸던 것과 같습니다 (다음 단락에서 추가 설명).

if (expression)
{
    // Run 1
} else {
    // Run 2
}

if-else\switch 문이있을 때마다 식을 평가하여 어떤 블록을 실행해야하는지 결정해야합니다. 컴파일러에서 생성 된 어셈블리 코드에서 조건부 branch instructions가 삽입됩니다.

브랜치 명령은 컴퓨터가 다른 명령 시퀀스를 실행하기 시작하여 명령을 순서대로 실행하는 기본 동작 (즉, 표현식이 false 인 경우 프로그램이 if 블록의 코드를 건너 뜁니다)에서 벗어나는 경우가 발생할 수 있습니다. 우리의 경우 표현식 평가입니다.

즉, 컴파일러는 실제로 평가되기 전에 결과를 예측하려고합니다. if 블록에서 명령어를 가져올 것이고, 그 표현이 사실이라면, 훌륭합니다! 우리는 코드를 평가하는 데 걸린 시간을 얻었으며 코드에서 진전을 이루었습니다. 그렇지 않다면 우리는 잘못된 코드를 실행하고, 파이프 라인은 플러시되고 올바른 블록이 실행됩니다.

심상:

경로 1 또는 경로 2를 선택해야한다고 가정 해 봅시다. 파트너가지도를 확인하기를 기다렸다가 ##에서 멈추고 기다렸거나 route1을 선택하고 운이 좋다면 (경로 1이 올바른 경로 임) 그때 당신은 당신의 파트너가지도를 확인하기를 기다릴 필요가 없었습니다. (당신이지도를 확인하는 데 걸렸을 시간을 절약했습니다.) 그렇지 않으면 되돌릴 것입니다.

파이프 라인을 플러싱하는 것이 매우 빠르지 만, 요즘이 도박을하는 것은 가치가 있습니다. 정렬 된 데이터 또는 천천히 변화하는 데이터를 예측하는 것은 빠른 변경을 예측하는 것보다 항상 쉽고 빠릅니다.

 O      Route 1  /-------------------------------
/|\             /
 |  ---------##/
/ \            \
                \
        Route 2  \--------------------------------
168
Tony Tannous

분기 예측에 관한 것입니다. 이게 뭐야?

  • 분기 예측기는 현대 아키텍처와 관련성이 높은 고대 성능 향상 기술 중 하나입니다. 간단한 예측 기술은 빠른 검색 및 전력 효율성을 제공하지만 높은 예측 오류율로 인해 어려움을 겪습니다.

  • 반면, 복잡한 분기 예측 - 신경 기반 또는 2 수준 분기 예측의 변형 -은 더 나은 예측 정확도를 제공하지만 더 많은 전력과 복잡성을 기하 급수적으로 증가시킵니다.

  • 이 외에도 복잡한 예측 기술에서 분기를 예측하는 데 걸리는 시간 자체가 실제 분기의 실행 시간과 비슷하게 2 ~ 5 사이클에서 매우 높습니다.

  • 분기 예측은 본질적으로 최소 가능한 누락 률, 낮은 전력 소비 및 최소의 리소스로 낮은 복잡성을 달성하는 데 중점을두고있는 최적화 (최소화) 문제입니다.

실제로 가지의 3 개의 다른 종류가있다 :

조건부 브랜치 - 실행 시간 조건에 따라 PC (프로그램 카운터)가 명령 스트림의 전방 주소를 가리 키도록 변경됩니다.

뒤로 조건부 분기 - PC가 명령 스트림에서 역방향을 가리 키도록 변경됩니다. 브랜치는 루프의 끝에서 테스트를 수행하면 루프가 다시 실행되어야한다고 프로그램 루프의 시작 부분으로 뒤로 분기하는 것과 같은 일부 조건을 기반으로합니다.

무조건 분기 - 특정 조건이없는 점프, 프로 시저 호출 및 리턴을 포함합니다. 예를 들어, 무조건 점프 명령은 단순히 어셈블리 언어로 "jmp"로 코딩 될 수 있으며 명령 스트림은 점프 명령이 가리키는 대상 위치로 즉시 지정되어야하며 반면에 "jmpne" 이전의 "비교"명령에서 두 값을 비교 한 결과 값이 같지 않음을 나타내는 경우에만 명령 스트림을 리디렉션합니다. (x86 아키텍처에서 사용하는 세그먼트 화 된 주소 지정 체계는 점프가 세그먼트 내에서 "가까이"(세그먼트 내에서) 또는 "멀리"(세그먼트 외부)에있을 수 있기 때문에 복잡성을 추가합니다. 각 유형은 분기 예측 알고리즘에 다른 영향을줍니다.)

정적/동적 분기 예측 : 정적 분기 예측은 조건 분기가 처음 발생할 때 마이크로 프로세서에 의해 사용되며 동적 분기 예측은 조건 분기 코드의 후속 실행에 사용됩니다.

참고 문헌 :

113
Farhad

분기 예측으로 인해 속도가 느려지는 것을 제외하고 정렬 된 배열은 또 다른 장점이 있습니다.

값을 확인하는 대신 중지 조건을 설정하여 관련 데이터를 반복 만하고 나머지는 무시할 수 있습니다.
분기 예측은 한 번만 실패합니다.

 // sort backwards (higher values first), may be in some other part of the code
 std::sort(data, data + arraySize, std::greater<int>());

 for (unsigned c = 0; c < arraySize; ++c) {
       if (data[c] < 128) {
              break;
       }
       sum += data[c];               
 }
107
Yochai Timmer

모든 명령어에는 0 비트 비용으로 테스트되는 4 비트 조건 필드가 있기 때문에 ARM에서는 분기가 필요하지 않습니다. 이렇게하면 짧은 분기가 필요하지 않으므로 분기 예측 히트가 발생하지 않습니다. 따라서 정렬 된 추가 버전의 오버 헤드로 인해 정렬 된 버전이 ARM의 정렬되지 않은 버전보다 느리게 실행됩니다. 내부 루프는 다음과 같이 보입니다.

MOV R0, #0     // R0 = sum = 0
MOV R1, #0     // R1 = c = 0
ADR R2, data   // R2 = addr of data array (put this instruction outside outer loop)
.inner_loop    // Inner loop branch label
    LDRB R3, [R2, R1]     // R3 = data[c]
    CMP R3, #128          // compare R3 to 128
    ADDGE R0, R0, R3      // if R3 >= 128, then sum += data[c] -- no branch needed!
    ADD R1, R1, #1        // c++
    CMP R1, #arraySize    // compare c to arraySize
    BLT inner_loop        // Branch to inner_loop if c < arraySize
103
Luke Hutchison

정렬 된 배열은 분기 예측이라고하는 현상으로 인해 정렬되지 않은 배열보다 빠르게 처리됩니다.

Branch predictor는 브랜치 (branch)가 어느 방향으로 갈지를 예측하여 명령 파이프 라인의 흐름을 향상시키는 디지털 회로 (컴퓨터 아키텍처)입니다. 회로/컴퓨터는 다음 단계를 예측하고 실행합니다.

잘못된 예측을하면 이전 단계로 돌아가고 다른 예측으로 실행됩니다. 예측이 정확하다고 가정하면 코드는 다음 단계로 계속 진행됩니다. 잘못된 예측은 올바른 예측이 발생할 때까지 동일한 단계를 반복합니다.

귀하의 질문에 대한 답변은 매우 간단합니다.

정렬되지 않은 배열에서 컴퓨터는 여러 예측을 수행하여 오류 가능성을 높입니다. 반면 정렬 된 컴퓨터는 오류 확률을 줄이는 예측 횟수를 줄입니다. 더 많은 예측을하려면 더 많은 시간이 필요합니다.

정렬 된 배열 : 직선 도로

____________________________________________________________________________________
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

정렬되지 않은 배열 : 곡선 도로

______   ________
|     |__|

지점 예측 : 어떤 도로가 직선인지 추측/예측하고 확인없이 추적

___________________________________________ Straight road
 |_________________________________________|Longer road

두 도로가 같은 목적지에 도착하더라도 직선 도로는 짧아지고 다른 도로는 더 길어집니다. 실수로 다른 하나를 선택하면 되돌릴 수 없으므로 긴 도로를 선택하면 시간이 더 많이 걸립니다. 이것은 컴퓨터에서 일어나는 것과 유사하며, 이것이 당신이 더 잘 이해하는 데 도움이되기를 바랍니다.


또한 나는 @Simon_Weaver 덧글에서 인용하고 싶다 :

예측이 적지 않아 예측 오류가 줄어 듭니다. 그것은 여전히 ​​루프를 통해 매번 예측해야합니다 ..

92
Omkaar.K

데이터를 정렬해야하는 다른 대답에 의한 가정은 정확하지 않습니다.

다음 코드는 전체 배열을 정렬하지 않고 200 개의 요소로 구성된 세그먼트 만 정렬하므로 가장 빠르게 실행됩니다.

K 요소 섹션 만 정렬하면 n.log(n)이 아닌 선형 시간으로 사전 처리가 완료됩니다.

#include <algorithm>
#include <ctime>
#include <iostream>

int main() {
    int data[32768]; const int l = sizeof data / sizeof data[0];

    for (unsigned c = 0; c < l; ++c)
        data[c] = std::Rand() % 256;

    // sort 200-element segments, not the whole array
    for (unsigned c = 0; c + 200 <= l; c += 200)
        std::sort(&data[c], &data[c + 200]);

    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i) {
        for (unsigned c = 0; c < sizeof data / sizeof(int); ++c) {
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    std::cout << static_cast<double>(clock() - start) / CLOCKS_PER_SEC << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

이것은 또한 정렬 순서와 같은 알고리즘 문제와는 아무런 관련이 없다는 것을 "증명합니다", 실제로는 분기 예측입니다.

14
user2297550

그것은 분류 되었기 때문에!

정렬되지 않은 것보다 정렬 된 데이터를 검색하고 조작하기 쉽습니다.

그냥 내가 상점에서 옷을 주문하는 법 (주문한 옷)과 옷장에서 옷을 입히는 것과 마찬가지입니다.

0
Arun Joshla