거의 모든 컴퓨터 프로그램에는 별도의 경로로 분기되는 코드 부분이 있습니다. 예를 들어 if-then-else 문에는 두 가지 가능한 결과가 있습니다. 이러한 명령문은 CPU가 모든 명령을 순서대로 처리하기 때문에 순차 프로세서에 문제가 되지 않습니다. 여러 명령이 한 번에 실행되기 때문에 분기는 파이프라인 프로세서에 큰 문제를 나타냅니다.
시나리오
두 가지 가능한 결과를 가진 분기문이 있는 프로그램의 경우 두 가지 가능한 코드 경로가 같은 위치에 있을 수 없습니다. 두 옵션 중 하나를 완료하는 데 필요한 처리는 다릅니다. 그렇지 않으면 프로그램이 분기되지 않습니다. if 문과 같이 한 번만 사용되는 상당한 수의 분기 문이 있을 것입니다.
루프를 형성하는 분기 명령문도 있습니다. 이것들은 일회용 진술만큼 수치적으로 일반적이지 않을 수 있지만 일반적으로 통계적으로 반복됩니다. 분기가 루프를 돌지 않을 가능성이 더 높다고 가정할 수 있습니다.
이것이 왜 문제인가?
이 문제가 완전 순차 프로세서에서 어떻게 표현되는지는 중요하지 않습니다. 단순히 문제가 아닙니다. 다음 명령의 첫 번째 부분이 처리되기 전에 어떤 분기를 사용할지 알 수 있습니다.
그러나 파이프라인 프로세서에서는 다음 명령이 대기열에 추가됩니다. 프로세서가 사용 중인 분기를 알 때 이미 처리되고 있습니다. 그렇다면 프로세서는 이 시나리오를 어떻게 처리해야 할까요? 몇 가지 옵션이 있습니다. 최악의 경우는 단순히 대기하고 파이프라인을 유휴 상태로 두는 동시에 어떤 분기가 걸릴 것인지에 대한 응답을 기다리는 것입니다. 즉, 분기 문이 있을 때마다 항상 파이프라인에 있는 단계 수만큼의 프로세서 시간 주기가 손실됩니다.
또는 파이프라인에서 두 옵션을 모두 실행하고 잘못된 선택을 취소할 수 있습니다. 이것은 아무 것도 하지 않을 때 절반의 페널티를 가지지만 여전히 모든 분기 문에서 성능 페널티를 발생시킵니다. 최신 CPU가 명령을 순서 없이 실행할 수도 있다는 점을 감안할 때 잠재적으로 모든 분기 명령을 가능한 한 빨리 실행하려고 시도할 수 있습니다. 따라서 그 결과는 필요하기 전에 알려져 있습니다. 이 옵션은 확장할 수 없다는 점을 제외하면 도움이 될 수 있습니다. 상대적으로 밀도가 높은 분기 명령문이 있다고 가정합니다. 이 경우 유휴 시간 없이는 모든 작업을 일찍 실행할 수 없습니다.
이 문제가 실제로 해결되는 방법
실제로 프로세서에는 분기 예측기가 포함되어 있습니다. 분기 예측기는 분기 선택의 결과를 추측하려고 시도합니다. 그런 다음 프로세서는 예측이 정확하다고 가정하고 명령을 예약합니다. 분기 예측자가 정확하면 성능 저하가 없습니다.
분기 예측자가 실수하면 파이프라인을 플러시하고 실제 결과 처리를 시작해야 합니다. 이것은 아무것도 하지 않고 결과를 기다리는 것보다 약간 더 나쁜 성능 저하를 초래합니다. 최상의 성능을 얻으려면 분기 예측기가 가능한 한 정확한지 확인하는 것이 중요합니다. 이에 대한 다양한 접근 방식이 있습니다.
매칭 코드
기계어 코드에서 분기는 항상 다음 명령어를 읽거나 다른 곳에서 명령어 세트로 점프하는 것 사이에서 선택됩니다. 분기 예측자의 일부 초기 구현에서는 단순히 모든 분기가 항상 사용되거나 사용되지 않을 것이라고 가정했습니다. 컴파일러가 이 동작을 알고 있고 가장 가능성 있는 결과가 프로세서의 일반 추정. 이를 위해서는 소프트웨어 개발 습관을 조정하고 조정하는 데 많은 노력이 필요합니다.
또 다른 대안은 일반적으로 루프를 사용하고 분기가 뒤로 갈 경우 항상 점프한다는 통계를 통해 배우는 것입니다. 명령 스트림을 사용하고 점프가 앞으로 이동하면 일반적으로 통계적으로 떠날 가능성이 적기 때문에 절대 점프하지 않습니다. 고리. 이들은 두 가지 유형의 정적 분기 예측이며 분기 결과는 컴파일 시간에 예측됩니다.
동적 분기 예측자
최신 분기 예측기는 동적이며 현재 실행 중인 프로그램의 통계를 사용하여 더 나은 예측 성공률을 달성합니다. 포화 카운터는 모든 현재 분기 예측자의 기초입니다. 첫 번째 추측은 정적으로 또는 무작위로 결정됩니다. 분기를 가져오거나 가져오지 않으면 그 결과가 메모리의 일부에 저장됩니다. 다음에 동일한 분기가 올 때 분기 예측기는 이전과 동일한 결과를 예측합니다.
이것은 자연스럽게 루프에 대한 좋은 예측률을 가져옵니다. 이 두 가지 버전이 있습니다. 초기 버전은 단순히 단일 비트의 데이터를 사용하여 분기를 가져왔는지 여부를 나타냅니다. 이후 버전은 약하거나 강하게 선택되거나 선택되지 않은 것을 나타내기 위해 2비트를 사용합니다. 이 설정은 프로그램이 반환되는 경우 루프를 취하는 결과를 여전히 예측할 수 있으므로 일반적으로 성공률이 높아집니다.
추적 패턴
패턴을 추적하기 위해 일부 분기 예측자는 선택한 항목의 기록을 추적합니다. 예를 들어, 루프가 계속 호출되지만 루프에서 벗어나기 전에 4번 정도만 루프가 반복된다고 가정합니다. 이 경우 2단계 적응형 예측기가 이 패턴을 식별하고 다시 발생할 것으로 예측할 수 있습니다. 이것은 단순한 포화 카운터보다 성공률을 훨씬 더 높입니다. 최신 분기 예측기는 신경망을 사용하여 패턴을 찾아내고 예측함으로써 이를 더욱 발전시킵니다.
일부 분기 예측자는 여러 알고리즘을 사용한 다음 결과를 비교하여 사용할 예측을 결정합니다. 일부 시스템은 로컬 분기 예측이라고 하는 것에서 각 분기 명령을 개별적으로 추적합니다. 다른 사람들은 글로벌 분기 예측 시스템을 사용하여 모든 최근 분기 명령을 추적합니다. 둘 다 용도와 단점이 있습니다.
결론
분기 예측기는 파이프라인 CPU의 특별한 부분입니다. 실제 명령어가 처리되기 전에 분기 명령어의 결과를 예측하려고 시도합니다. 이것은 어떤 명령을 실행해야 하는지 확신할 수 없는 경우에도 CPU가 파이프라인을 포화 상태로 유지할 수 있도록 하는 파이프라인 CPU의 핵심 기능입니다. 그것들은 정확할 때 성능 저하를 제공하지 않습니다. 최신 알고리즘은 시간의 97%까지 비교적 예측 가능한 워크로드에서 정확할 수 있습니다.
완벽한 예측 방법은 없으므로 구현이 다양합니다. 잘못된 예측이 성능에 미치는 영향은 파이프라인의 길이에 따라 다릅니다. 특히, 예측이 잘못된 경우 결정될 수 있기 전의 파이프라인 길이입니다. 또한 각 파이프라인 단계에 얼마나 많은 명령어가 있는지에 따라 다릅니다. 최신 고급 데스크톱 CPU에는 약 19개의 파이프라인 단계가 있으며 각 단계에서 동시에 최소 4개의 명령을 실행할 수 있습니다.