age-ordered issue: 준비된 분기가 다섯 번 밀리는 큐

실행할 수 있는 명령이 여러 개라면 어느 것을 먼저 보내야 할까. 단순한 선택 회로는 큐의 앞 슬롯부터 찾을 수 있다. 하지만 앞 슬롯에 있는 명령이 프로그램에서 먼저 나온 명령이라는 보장은 없다. age-ordered issue는 위치의 우선순위를 명령의 나이와 연결해, 오래된 준비 완료 명령을 먼저 실행하도록 만드는 정책이다.

같은 준비 상태에서도 기다리는 시간이 달라진다

정수 실행 포트가 하나이고, 큐에 세 슬롯이 있는 가상 설계를 생각해 보자. 슬롯 우선순위는 0, 1, 2 순서다. 가장 오래된 분기 B는 슬롯 2, 그보다 젊은 Y1은 슬롯 1, 더 젊은 Y0은 슬롯 0에 있다. 세 명령 모두 입력이 준비되었고 같은 포트에서 실행할 수 있다고 가정한다.

슬롯 위치만 보는 회로는 Y0을 고른다. 다음 사이클에 빈 슬롯 0에 새 Y2가 들어오면 Y2가 또 먼저 나간다. 같은 방식으로 Y3, Y4까지 들어오면 다음과 같은 차이가 생긴다. 각 보충 명령은 다음 선택 전까지 들어와 준비된 것으로 가정한다.

슬롯 우선순위: Y0 → Y2 → Y3 → Y4 → Y1 → B
나이 우선순위: B가 첫 번째 선택

첫 줄은 Y4 이후 새 보충을 멈춘 경우다. B가 준비되었는데도 다섯 번의 다른 선택 뒤에 실행된다. B가 잘못 예측된 분기라면, 그동안 잘못된 경로에서 가져온 명령이 더 많이 처리될 수 있다. B가 단순히 “오래되었다”는 사실만 문제가 아니라, 늦게 실행한 B의 결과가 이후 경로를 정한다는 점이 지연을 키운다.

이것은 BOOM의 실제 성능 수치를 재현한 예가 아니다. 준비 상태와 포트 조건을 동일하게 고정하고, 우선순위 하나의 효과를 보려는 계산이다. 실제 코어에서는 큐와 ROB 용량, 입력 의존성과 포트 종류가 추가로 선택을 제한한다.

슬롯을 고정하는 방식과 나이를 움직이는 방식

BOOM이 설명하는 unordered queue는 새 명령을 빈 슬롯에 넣고, 실행될 때까지 그 자리에 둔다. 선택 회로의 정적 슬롯 우선순위 때문에 예측하기 어려운 분기가 낮은 우선순위에 들어가면, ROB가 차서 새 유입이 멈추고 창이 비워질 때까지 실행이 지연되는 나쁜 경우가 생길 수 있다. BOOM, Un-ordered Issue Queue

반면 해당 문서의 age-ordered queue는 오래된 명령이 높은 우선순위에 오도록 명령을 이동시키는 collapsing queue다. 새로운 명령은 낮은 우선순위 쪽으로 들어간다. 결과적으로 동일하게 준비된 명령 중에서는 먼저 들어온 쪽을 먼저 선택하게 된다. 앞의 예에서 B는 슬롯 2라는 우연한 위치 때문에 기다리지 않는다. BOOM, Age-ordered Issue Queue

여기서 unordered라는 이름을 무작위 선택으로 읽으면 안 된다. 그 설명의 선택 회로에는 명확한 우선순위가 있다. 순서가 없는 것은 프로그램 나이와 슬롯 위치의 관계다. 또 age-ordered라는 정책 자체가 반드시 모든 구현에서 같은 이동 회로를 요구하는 것은 아니다. 위 비용 설명은 BOOM 문서의 collapsing 방식에 대한 것이다.

가장 오래된 명령을 무조건 실행하는 정책은 아니다

가장 오래된 명령의 소스가 아직 준비되지 않았다면 어떻게 될까. 나이 우선순위는 준비되지 않은 명령을 억지로 실행시키지 않는다. 준비되어 request를 내는 후보 중에서, 해당 포트가 처리할 수 있는 명령을 고른다. 예를 들어 가장 오래된 B가 load 결과를 기다리는 동안, 입력이 준비된 Y1은 먼저 실행할 수 있다. BOOM, Issue Slot와 Issue Select Logic

이 구분을 놓치면 age-ordered issue를 앞 명령이 막힐 때 뒤 명령도 모두 멈추는 정책으로 착각한다. 계산을 시작할 자격과 자격이 있는 후보들의 선택 순서는 별개다. 포트가 여러 개라면 연산 종류의 호환성과 이미 선택한 후보의 중복 방지도 함께 고려해야 한다.

반대로 unordered 방식에서 낮은 우선순위 명령이 반드시 영원히 굶는다는 결론도 지나치다. 실제 코어의 저장 공간은 유한하므로, 오래된 명령이 확정을 막으면 ROB가 차고 새 명령 유입이 멈출 수 있다. 그 뒤 높은 우선순위 슬롯이 비면서 B에도 기회가 온다. 실행이 결국 된다는 사실과, 그때까지 필요한 정보를 늦게 얻어 성능을 잃었다는 사실은 함께 성립한다.

공정한 선택에는 배선과 이동 비용이 따른다

오래된 분기와 load를 일찍 처리하면 경로 결정과 대기 중인 의존 명령에 도움이 될 수 있다. 하지만 모든 사이클에 큐 내용을 이동시키면 많은 슬롯의 상태를 읽고 쓰게 된다. BOOM 문서도 성능상의 이점과 함께 이 잠재적 에너지 비용을 지적한다. 나이가 높은 우선순위가 공짜로 만들어지는 것은 아니다.

나이만으로 모든 실행 시간을 최적화할 수도 없다. 젊은 명령이 중요한 긴 계산의 시작점일 수 있고, 오래된 명령은 이미 준비되어도 다른 자원 때문에 결과를 빨리 확정하지 못할 수 있다. 나이 정책은 이런 모든 미래를 예측하는 알고리즘이 아니라, 오래된 준비 완료 작업이 위치 때문에 계속 밀리는 상황을 줄이는 기준이다.

age-ordered issue를 평가할 때는 선택된 명령의 수만 세는 대신 무엇의 발견이 늦어졌는지 봐야 한다. 오래된 분기 B를 첫 번째에 실행하는 가치가 큰 상황이라면 나이와 우선순위를 맞추는 효과가 분명하다. 그 효과를 얻기 위해 큐를 얼마나 움직이고 어떤 회로를 두어야 하는지까지 보면, 오래된 명령을 먼저 고르는 정책의 장점과 비용을 함께 설명할 수 있다.