BTB aliasing: 항상 taken인 두 분기도 서로를 방해하는 이유

두 분기는 둘 다 항상 taken이고, 각자의 목적지도 바뀌지 않는다. 이런 쉬운 분기라도 작은 branch target buffer에서 서로의 기록을 밀어내거나 잘못 공유하면 다음 명령을 엉뚱한 주소에서 가져올 수 있다. BTB aliasing은 분기 방향이 어려워서 생기는 문제가 아니라, 목적지 기록을 어떤 주소의 기록으로 인정하느냐에서 생기는 문제다.

이 현상을 볼 때 같은 entry에 부딪혔다는 사실과, 다른 분기의 기록을 자기 기록으로 믿었다는 사실을 구분해야 한다. 전자는 저장 공간의 경쟁이고 후자는 식별의 실패다. 둘이 모두 프런트엔드의 비용을 만들지만 해결책은 다를 수 있다.

같은 index와 같은 분기는 다르다

가상의 직접 사상 BTB를 만들자. entry는 8개이며 이 예의 명령은 모두 4바이트 정렬이다. index를 (PC>>2) AND 7로 정하고, 각 entry에 valid와 목적지를 저장한다고 하자. 분기 A의 PC가 0x100, 분기 B의 PC가 0x120이면 둘의 index는 모두 0이다.

A의 목적지가 0x180이고 B의 목적지가 0x300이라고 가정하자. A를 실행한 뒤 entry 0에는 0x180이 기록된다. 이후 B를 가져올 때 index만 보고 이 entry를 믿으면 A의 목적지 0x180을 B의 목적지로 사용한다. taken 판단은 맞더라도 다음 fetch 주소는 틀린다.

여기에 tag를 넣어 보자. 이 단순한 주소 분할에서 index 위의 PC 비트, 즉 PC>>5를 tag로 저장하면 A의 tag는 8, B는 9다. B가 조회할 때 저장 tag 8과 요청 tag 9가 다르므로 hit로 인정하지 않는다. 목적지를 모른다는 상태로 처리하고, 나중에 실제 분기를 확인하여 B의 기록을 넣을 수 있다.

하지만 완전한 tag도 entry 수를 늘려 주지는 않는다. A와 B가 번갈아 실행되고 각각의 결과를 다음 조회 전에 갱신한다면, 같은 자리의 tag와 목적지를 계속 교체한다. 틀린 목적지를 hit로 쓰는 문제는 막았지만 반복적인 miss는 남는다. 식별이 정확해진 것과 저장 용량이 충분해진 것은 다른 성질이다.

tag를 줄이면 다시 같은 이름이 된다

면적을 줄이려고 위 tag의 맨 아래 한 비트만 저장한다고 하자. A의 tag 8은 0, PC가 0x140인 분기 C의 tag 10도 0이다. index도 둘 다 0이다. 두 분기의 목적지가 다른데 A의 기록이 남아 있다면, C는 index와 짧은 tag가 모두 같아 거짓 hit를 낼 수 있다.

이 계산은 실제 특정 CPU의 BTB 구조가 아니라 tag의 역할을 보기 위한 예다. 실제 설계에서는 여러 way, 주소 해시, 압축된 주소 정보 또는 fetch 묶음 단위의 tag를 사용할 수 있다. 주소 공간이나 문맥 정보도 기록의 해석에 영향을 준다. 그래서 단순히 “tag가 있다”는 설명만으로 aliasing 가능성을 판단할 수 없다.

BOOM의 NLP 문서는 그 안의 BTB를 완전 연관 구조로 설명하고, Fetch PC의 tag match를 통해 entry를 찾는다고 명시한다. 상위 주소 비트는 압축해 저장하며, 하나의 entry가 fetch 묶음 안의 한 제어 흐름 명령 정보를 제공한다. 앞의 8-entry 직접 사상 모델을 그대로 BOOM 구현이라고 읽어서는 안 된다. BOOM NLP의 Predictions 및 Superscalar Predictions

방향 오류와 목적지 충돌을 따로 센다

분기 방향 예측이 taken으로 맞았는지와 목적지 주소가 맞았는지는 별도의 질문이다. BTB가 틀린 주소를 제공했을 때 실행 단계가 실제 주소를 계산하여 차이를 발견하고 명령 흐름을 되돌릴 수 있다. 그동안 가져온 명령과 투기 작업은 버려질 수 있으므로 시간과 에너지가 든다. 예측이 최종 프로그램의 분기 의미를 바꾸도록 두는 것이 정상적인 설계는 아니다.

실험에서는 두 주소를 번갈아 실행하는 작은 패턴이 유용하다. 처음 한 번은 두 분기 모두 기록이 없어서 miss할 수 있으므로 warm-up과 이후를 나눈다. 이후 기록이 밀려나는지, 잘못 hit하는지, 방향이 틀렸는지를 따로 추적해야 한다. 특정 주소 간격에서 느려졌다는 관측만으로 물리적인 index 비트를 확정하기도 어렵다. 여러 해시와 다른 구조의 경쟁이 같은 현상을 만들 수 있다.

연관도를 늘리면 같은 index의 두 분기가 함께 머물 수 있다. tag를 늘리면 다른 분기를 자기 기록으로 믿는 경우를 줄일 수 있다. 총 entry 수를 늘리면 더 많은 분기를 기억한다. 각각 비교 논리, 저장 공간, 전력과 조회 지연의 비용이 있으며 모든 충돌을 한 번에 없애는 단일 손잡이는 아니다.

BTB aliasing을 분석할 때는 entry 하나에 여러 PC가 대응하는 순간부터 살펴보면 된다. 이어 그 PC들을 tag가 구별하는지, 동시에 저장할 자리가 있는지 확인한다. 이 구분을 유지하면 항상 taken인 쉬운 분기조차 목적지 예측에서 실패하는 이유를 설명할 수 있다.