Dynamic branch prediction 설명

Dynamic branch prediction은 컴퓨터 아키텍처에서 실행 중인 명령어의 분기(Branch)가 실제로 발생할지 여부를 예측하는 방식입니다. 프로그램의 흐름 제어(조건부 분기나 반복문 등)에 있어서 성능을 높이기 위한 주요 기법 중 하나로, CPU가 명령어 파이프라인에서 분기 명령어를 미리 예측하여 연산을 더 효율적으로 수행할 수 있게 합니다.

주요 특징과 방식은 다음과 같습니다:

1. 히스토리 기반 예측: CPU가 이전의 분기 패턴을 기록하여 향후 분기를 예측합니다. 이를 위해 분기 히스토리 테이블(BHT, Branch History Table)과 같은 구조를 사용하여, 분기가 이전에 어떻게 처리되었는지를 바탕으로 다음 분기 여부를 추측합니다.
2. 2-bit 예측기: 간단한 형태로 많이 사용되는 방식으로, 두 비트를 사용하여 분기의 발생 여부를 추적합니다. 두 비트는 네 가지 상태를 나타낼 수 있으며, 이를 통해 ‘강하게 분기’와 ‘약하게 분기’를 포함한 상태를 정의하여 분기 예측의 신뢰도를 향상시킵니다.
3. 연관된 분기 히스토리: 분기 히스토리와 더불어 글로벌 분기 히스토리(Global Branch History)를 사용하기도 합니다. 이는 특정 분기뿐만 아니라 이전의 여러 분기 명령어에 대한 결과를 반영하여 현재 분기를 예측하는 방식으로, 여러 분기 간의 연관성을 분석해 더 정확한 예측이 가능합니다.
4. 패턴 테이블 기반의 예측: 패턴 테이블을 사용하여 복잡한 분기 패턴을 분석할 수 있습니다. 이는 여러 비트 길이의 히스토리를 유지하여, 특정 패턴에 따른 분기를 예측하게 합니다.

동적 분기 예측을 통해 CPU는 분기 명령어가 발생하기 전에 미리 예측하여 파이프라인의 흐름을 끊지 않고 연속적으로 처리할 수 있습니다.

분기 히스토리 테이블(BHT, Branch History Table)

분기 히스토리 테이블(BHT, Branch History Table)은 CPU가 이전 분기 명령어의 결과를 기반으로 다음 분기의 방향을 예측하기 위해 사용하는 데이터 구조입니다. 이는 분기 예측 성능을 높여 파이프라인의 효율성을 향상시키는 중요한 요소입니다. BHT는 주로 1비트 또는 2비트 예측기로 구성되어 있으며, 각각의 분기 명령어에 대해 해당 분기가 발생했는지 여부를 기록합니다.

BHT의 작동 원리

BHT는 간단히 말해 분기 명령어 주소와 그 명령어의 최근 실행 결과를 저장하는 테이블입니다. CPU는 특정 분기 명령어의 주소를 인덱스로 사용하여 BHT에서 해당 분기 명령어의 히스토리를 확인하고, 과거의 히스토리 패턴에 따라 현재의 분기를 예측합니다. 이를 통해 CPU가 분기가 발생할지 안 할지를 미리 추측해 이후의 명령어 파이프라인을 준비할 수 있습니다.

BHT의 구조와 예측 방식

1. 1비트 예측기: 각 분기 명령어마다 1비트로 분기 결과를 저장합니다. 1비트 예측기는 단순히 마지막에 분기가 발생했는지 여부만 기록합니다.
   • 예를 들어, 1비트 예측기가 “분기가 일어남” 상태에 있으면 다음 번에도 분기가 발생한다고 예측하고, “분기가 일어나지 않음” 상태에 있으면 다음 번에도 분기가 일어나지 않는다고 예측합니다.
   • 그러나, 분기 상태가 자주 바뀌는 상황에서는 정확도가 떨어질 수 있습니다.
2. 2비트 예측기: 1비트 예측기의 단점을 보완한 방식으로, 두 비트를 사용하여 네 가지 상태를 정의합니다.
   • 이 네 가지 상태는 ‘강하게 분기 발생(Strongly Taken)’, ‘약하게 분기 발생(Weakly Taken)’, ‘약하게 분기 발생 안 함(Weakly Not Taken)’, ‘강하게 분기 발생 안 함(Strongly Not Taken)’입니다.
   • 분기 예측의 성공 및 실패에 따라 상태가 변경되며, 두 번 연속 틀리지 않으면 상태가 바뀌지 않기 때문에, 분기 예측의 안정성을 높이는 데 도움이 됩니다.

BHT 예시

가령, 다음과 같은 분기 명령어가 있다고 해봅시다:

• 분기 명령어 주소: 0x01ABF
• 분기 히스토리 테이블의 인덱스: 이 주소의 일부 비트를 사용하여 인덱스화한다고 가정합니다.

예제 시나리오