분기 예측의 중요성

분기 예측(Branch Prediction)은 CPU 아키텍처에서 중요 한 요소로, CPU의 성능을 크게 향상시킬 수 있다. 분기 명령어(Branch Instruction)가 실행될 때, 프로그램의 흐름은 두 가지 혹은 그 이상의 경로 중 하나로 분기된다. 분기 예측은 CPU가 분기 명령어를 미리 예측하여 올바른 경로로 실행을 지속할 수 있도록 한다.

만약 분기 예측이 틀리면, CPU는 예측 오류 지점으로 되돌아가 잘못 실행한 명령어들을 취소하고 올바른 경로의 명령어를 다시 읽고 실행해야 하기 때문에 성능이 크게 저하된다.

분기 예측의 종류

분기 예측은 크게 두 종류의 기법으로 나눌 수 있다: 정적 예측과 동적 예측

정적 예측

정적 예측(Static Prediction)은 분기가 발생하기 전에 특정 규칙에 따라 분기 결과를 예측하는 방법이다. 이는 주로 컴파일러나 하드웨어에서 다음과 같은 고정된 규칙을 사용하여 예측을 수행한다.

• 정방향 예측(Forward Prediction): 분기 명령어가 프로그램 카운터(PC)보다 나중의 주소를 참조하면 taken으로 예측.
• 후방향 예측(Backward Prediction): 분기 명령어가 프로그램 카운터보다 이전의 주소를 참조하면 not-taken으로 예측.

이 기법은 간단하지만 예측의 정확도가 낮을 수 있다.

동적 예측

동적 예측(Dynamic Prediction)은 분기 실행 정보를 실시간으로 수집하여 예측을 수행하는 방법이다. 이는 하드웨어에 기반하여 다양한 기법들이 사용될 수 있다. 대표적인 동적 예측 기법들은 다음과 같다:

히스토리 기준 예측

• 단일 비트 히스토리 기반 예측: 각각의 분기 명령어에 대해 하나의 비트로 Taken 또는 Not-Taken을 기록한다. 예측 비트의 상태가 예측 결과를 나타내며, 분기 결과가 달라질 경우 그 비트를 반전시킨다.

• 이중 비트 히스토리 기반 예측: 두 개의 비트를 사용하여 Strongly Taken, Weakly Taken, Weakly Not-Taken, Strongly Not-Taken의 네 가지 상태를 관리한다. 예측 오차가 발생했을 때, 상태 변화를 통해 좀 더 유연한 예측이 가능하다.

패턴 히스토리 테이블(Pattern History Table, PHT)

PHT는 특정한 분기 패턴을 기반으로 분기를 예측한다. 최근의 분기 결과를 기반으로 N 비트의 히스토리 레지스터를 사용하여 분기 패턴을 생성하고 이를 PHT에서 조회하여 예측을 수행한다.

여기서, History는 최근 분기 결과, PC bits는 프로그램 카운터의 일부 비트를 의미한다.

지연 분기(Delayed Branch)

지연 분기(Delayed Branch)는 컴파일러가 분기 명령어 이후에 실행되는 명령어를 재구성하여, 분기 명령어가 수행된 후 실제 분기가 일어나기 전, 일정한 명령어들이 실행되도록 하는 방법이다.

이를 통해 분기가 발생하는 동안 파이프라인의 명령어들이 빈번하게 차단되는 것을 줄일 수 있다.

분기 예측 기법의 구현

동적 분기 예측은 구현 복잡도가 높지만, 일반적으로 정적 분기 예측보다 우수한 성능을 제공한다. 히스토리에 기반한 예측과 PHT는 특히 널리 사용되는 대표적인 방법이다.

스미스 예측기(Smith Predictor)

스미스 예측기는 분기 예측의 한 방법으로, 단일 비트 예측기에서 발전되어 여러 비트를 사용하는 구조다. 분기 예측 비트를 상태 머신으로 관리하여 좀 더 정확한 예측이 가능케 한다.

이 상태 머신에서 강한 예측을 통해 오차를 줄이며 상태 전환을 통해 유동적으로 예측을 수행할 수 있다.

G-셰어 예측기(Gshare Predictor)

G-셰어 예측기는 패턴 기반 예측기의 한 종류로, 글로벌 히스토리를 사용하여 보다 정교한 예측을 제공한다. 프로그램 카운터와 글로벌 히스토리 레지스터(Global History Register, GHR)를 XOR 연산하여 PHT의 인덱스를 생성한다.

이 기법은 분기 예측의 정확도를 높이기 위해 분기 히스토리와 프로그램 카운터의 특성을 조합하여 패턴을 예측한다. G-셰어 예측기는 다양한 프로그램의 분기 행동을 효율적으로 기록할 수 있는 장점이 있다.

분기 목표 버퍼(Branch Target Buffer, BTB)

BTB는 분기 명령어의 목표 주소(target address)를 저장하여 예측의 정확도와 성능을 향상시기 위한 캐시 역할을 한다. BTB는 분기명령어의 PC를 인덱스로 사용하여 분기 목표 주소를 찾는다.

구조

• 태그(Tag): 분기 명령어의 프로그램 카운터(PC) 일부를 저장.
• 타겟 주소(Target Address): 분기 명령어의 목적지 주소를 저장.

BTB는 주로 고속 접근을 위해 캐시처럼 작동하며, 분기 예측기의 예측 결과와 함께 사용되어 분기 목표 주소를 제공한다.

브랜치 타깃 인버전(Branch Target Inversion, BTI)

BTI는 분기가 목표로 하는 주소를 다르게 설정하여 지금까지 존재하지 않는 주소로 결과가 도달되게 만드는 기술이다. 이 기술은 보안적인 측면에서 분기 예측 공격 등을 방어하기 위해 사용되기도 하며, CPU 설계의 복잡성을 증가시키는 요인이 되기도 한다.

분기 예측의 한계와 개선 방향

분기 예측은 일단 개념적으로 분기 명령어의 흐름 예측을 통해 성능을 향상시킬 수 있는 방법을 제공하지만, 몇 가지 한계와 개선 방향도 제시된다.

한계

1. 복잡한 예측 논리: 정확한 예측을 위해 복잡한 알고리즘과 추가적인 하드웨어 자원이 필요하며, 이는 설계와 구현 비용을 증가시킨다.
2. 오류 발생 시 성능 저하: 예측 오류가 발생했을 경우, 파이프라인 클리어링과 회복 오버헤드로 성능 저하가 상당하다.
3. 패턴 미적용 문제: 특정 패턴을 기반으로 수행되기 때문에 패턴이 없는 임의 분기에서는 예측 정확도가 낮아질 수 있다.

개선 방향

1. 하이브리드 예측기: 여러 예측 기법을 조합하여 더 높은 예측 정확도를 달성할 수 있는 하이브리드 예측기 도입.
2. 기계 학습 기법 적용: 최신 인공지능 및 기계 학습 기술을 도입하여 히스토리를 기반으로 더 정확한 예측 모델 개발.
3. 동시 다중 스레드 아키텍처 지원: 멀티코어 및 멀티스레드 아키텍처와의 연동을 통해 예측 성능 향상.

분기 예측은 CPU 아키텍처의 필수적인 요소로, 프로그램의 흐름을 보다 효율적으로 처리하여 전반적인 성능을 크게 향상시킬 수 있다. 정적 예측과 동적 예측, 다양한 패턴 예측 기법 및 BTB와 같은 추가 기술을 통해 예측의 정확도를 높이는 많은 연구가 이루어지고 있다. 그러나 예측의 복잡성과 설계 비용, 오버헤드 등을 고려해야 하며, 지속적인 개선과 연구가 필요하다.

분기 예측 기술의 발전은 향후 CPU 성능의 중요한 동력이 될 것이며, 이러한 분야에 대한 이해와 연구는 매우 중요하다.