backing predictor: 늦게 온 예측도 실행보다 빠르면 도움이 된다

정확한 분기 예측을 만드는 데 시간이 더 걸린다면, CPU는 매번 그 답을 기다려야 할까? 기다리는 동안 명령 공급이 끊기면 정확도의 이득이 사라질 수 있다. backing predictor는 먼저 빠른 예측으로 fetch를 진행한 다음, 더 많은 정보를 사용하는 뒤쪽 예측이 그 경로를 보완하도록 하는 구조다.

여기서 늦게 도착한 답의 가치는 단순한 최종 정확도와 다르다. 빠른 예측을 언제 수정하는지에 따라 버리는 명령의 양과 복구 시간도 달라진다. 예측기의 성능은 맞힌 비율과 응답 시점을 함께 읽어야 한다.

빠른 길 안내와 뒤쪽 판단을 연결한다

BOOM 문서는 한 사이클의 Next-Line Predictor와 더 복잡한 Backing Predictor를 함께 둔다고 설명한다. NLP는 목적지와 간단한 방향 정보 등을 활용해 다음 fetch를 빠르게 정한다. BPD는 더 많은 분기와 복잡한 패턴을 다루기 위해 여러 fetch 단계에 걸쳐 접근할 수 있다. BOOM Branch Prediction 개요

BPD가 항상 완성된 다음 PC를 보내는 것은 아니다. BOOM의 BPD 인터페이스는 예측의 유효 여부와 조건 분기들의 taken/not-taken 비트들을 제공한다. 이후 단계에서 명령을 해독해 분기와 목적지를 알아낸 뒤, 그 방향 정보로 redirect를 결정한다. 따라서 BPD의 방향이 맞더라도 목적지가 아직 준비되지 않았거나 명령 식별이 잘못되면 다음 PC를 곧바로 고칠 수는 없다. BOOM BPD, Making Predictions

이 분리는 저장 구조에도 영향을 준다. 방향 표가 목적지와 완전한 PC tag를 모두 담지 않으면 더 조밀한 기억장치를 사용할 여지가 생긴다. 대신 조회와 명령 정보의 결합에 시간이 필요하다. BOOM 문서는 BPD를 fetch 과정에서 명령 캐시와 병렬로 접근하며 SRAM에 배치할 수 있는 이유를 설명한다. 모든 설정이 동일한 지연이나 동일한 면적을 갖는다는 뜻은 아니다.

같은 오답을 일찍 고치면 달라지는 것

가상의 파이프라인을 시간 순서로 보자. 사이클 0에 빠른 예측기가 분기를 taken으로 판단하여 목적지 쪽 fetch를 시작한다. 실제 방향은 not-taken이다. 사이클 1과 2에도 틀린 경로의 요청이 진행된다.

사이클 3에 BPD의 올바른 not-taken 답과 그 분기의 정보가 함께 준비되면, 사이클 4의 fetch를 올바른 다음 주소로 돌릴 수 있다고 가정하자. 반대로 뒤쪽 예측이 없고 실행 단계가 사이클 8에 분기 결과를 확정한다면, 같은 조건에서 올바른 fetch는 사이클 9부터 시작한다. 뒤쪽 판단이 여전히 첫 예측보다 늦어도 다섯 사이클 먼저 경로를 수정한 셈이다.

이 숫자는 BOOM의 단계 이름을 실측 시간으로 옮긴 것이 아니라, 두 수정 시점을 비교하기 위한 가상 일정이다. 명령 캐시 miss나 redirect 처리 지연이 있으면 실제 요청 시점은 달라진다. 중요한 관계는 ‘빠른 예측보다 늦다’와 ‘실행 결과보다 빠르다’가 동시에 성립할 수 있다는 것이다.

반대 사례도 생각해야 한다. 빠른 예측이 맞았는데 BPD가 틀린 방향을 제시하면, 이미 맞는 경로를 따라가던 프런트엔드를 뒤쪽 오답이 돌려 놓을 수 있다. 또는 두 예측이 모두 틀릴 수도 있다. BPD가 더 복잡하다는 이름만으로 매번 우월한 답을 낸다고 가정할 수 없다.

추가 정확도가 아니라 추가 효용을 센다

두 구조를 평가하려면 빠른 예측만 틀린 경우, BPD가 그 오류를 바로잡은 경우, 오히려 맞는 경로를 바꾼 경우를 나누어 보는 것이 좋다. BPD가 예측을 제공하지 못한 경우도 별도다. 전체 방향 정확도 하나는 어느 시점의 명령 흐름을 개선했는지 설명하지 못한다.

회로 자원도 그 효용과 함께 비교한다. 큰 표의 읽기, 이력 처리, 응답에 붙는 정보와 대기 중인 요청을 관리하는 상태가 필요하다. 조회가 여러 사이클 걸리면 답이 어느 fetch 요청의 답인지 정확하게 연결해야 한다. 이미 취소한 요청의 늦은 답으로 새 경로를 바꾸는 일도 막아야 한다. 이것은 산술적인 예측 정확도와 별개로 인터페이스의 정확성에 속한다.

BOOM의 fetch 문서는 실행 파이프라인 또는 예측기가 redirect를 요청하면 프런트엔드가 새 명령 경로를 가져온다고 설명한다. 또한 fetch 묶음에는 예측 정보와 유효한 명령을 표시하는 정보가 함께 이동한다. 예측 답을 내는 표만으로 시스템이 완성되지 않고, 경로 변경과 명령의 수명을 관리하는 부분이 이어져야 한다. BOOM Instruction Fetch

정확한 예측을 늦게 받는다고 항상 기다릴 필요는 없다. 빠른 추측을 먼저 사용하고, 뒤쪽 답이 실행 확정보다 이른 시점에 필요한 경우를 바로잡을 수 있다. backing predictor의 설계 질문은 얼마나 똑똑한 표를 붙일까에 더해, 그 답이 언제 도착하여 어떤 명령 공급을 개선하는가다.