rename checkpoint: 이름을 되돌렸는데 빈 레지스터가 줄어드는 이유
잘못 예측한 분기를 복구하면서 레지스터 이름을 예전 매핑으로 돌려놓았다. 그런데 실행을 반복할수록 새 목적지로 배정할 수 있는 물리 레지스터가 줄어든다. 값의 이름은 맞게 돌아왔지만, 잘못된 경로가 사용한 저장 공간을 제대로 돌려받지 못한 상황이다. rename checkpoint에는 이름의 복구와 자원의 복구라는 두 책임이 있다.
매핑을 되돌려도 새 번호가 자동으로 반환되지는 않는다
분기 B 시점에 x5가 p10을 가리켰다고 하자. 예측한 경로의 명령이 x5에 쓰면서 새 번호 p20을 배정받으면 현재 매핑은 x5→p20이 된다. B가 틀렸다면 그 뒤 명령은 취소하고 x5→p10으로 돌아가야 한다.
그러나 map table을 복원하는 동작은 p20을 free list에 넣는 동작과 다르다. p20은 새 값의 소유자로 배정되었으므로, 취소된 경로에서 사용했던 번호라는 정보를 이용해 반환해야 한다. 반대로 p10은 올바른 복구 상태에서 계속 필요하다. 눈에 보이는 새 매핑을 모두 비우는 식의 처리는 살아 있어야 할 값까지 잃을 수 있다.
BOOM은 분기별 rename map snapshot과 함께, 그 분기 이후에 배정된 물리 번호를 기록하는 allocation list를 설명한다. 잘못 예측한 경우 그 목록을 free list에 OR하여 반환한다. BOOM, The Rename Map Table와 The Free List
분기 때 빈 번호의 사진만 남기면 빠지는 경우
왜 free list도 그냥 사진을 찍어 두면 안 될까. 가상의 작은 번호 집합으로 시간 순서를 추적해 보자. 여기서는 그 밖의 번호와 새로운 배정은 생략한다.
분기 B보다 오래된 명령 U는 x2의 새 값 p11을 가지고 있고, 이전 값 p7을 대체했다. B 시점에는 U가 아직 commit하지 않았으므로 p7은 반환되지 않았다. 현재 x2는 p11을 가리킨다. p20만 빈 번호라면 snapshot의 free 집합은 {p20}이다.
이후 사건을 다음 순서로 진행한다.
- 잘못된 경로의 W가 p20을 배정받는다.
- B보다 오래된 U가 commit하여 이전 번호 p7을 반환한다.
- 잘못된 경로의 V가 이제 빈 p7을 배정받는다.
- B의 오예측을 발견한다.
발견 시점의 free 집합은 빈 집합이다. 분기 당시의 {p20}과 현재의 빈 집합을 OR하면 p20은 돌아오지만 p7은 돌아오지 않는다. p7은 snapshot 때 사용 중이었고 지금도 배정된 상태라서, 중간에 한 번 반환되었다는 사실이 양쪽 사진에 없다.
그러나 p7의 현재 사용자인 V는 취소된다. 복구된 x2는 p11을 가리키므로 p7을 잡아 둘 이유가 없다. 이 번호는 누수가 된 것이다. BOOM 원문의 주석도 “분기 때 배정됨→반환됨→다시 배정됨”이라는 순서에서 snapshot 방식이 번호를 놓치는 반례를 명시한다. BOOM, The Free List 주석 5
배정의 이력을 남기면 두 번의 변화가 보인다
B의 allocation list에는 W가 받은 p20과 V가 받은 p7이 기록된다. 복구 시 현재 free 집합에 {p20,p7}을 더하면 두 번호가 모두 반환된다. 분기 시점에 빈 번호였는지가 아니라, 분기 이후 취소될 명령에 배정되었는지를 기준으로 삼은 것이다.
반면 U의 p11은 B보다 오래된 명령이 만드는 살아 있는 값이므로 이 반환 집합에 넣지 않는다. U가 이미 commit한 사실도 되돌리지 않는다. B의 잘못된 추측을 취소하는 범위와, B보다 오래된 정상 진행의 범위가 구별되어야 한다.
bit-vector에 OR하는 동작은 같은 비트를 두 번 넣어도 개수를 두 번 늘리지 않는다. 그렇지만 이 성질만으로 반환이 안전한 것은 아니다. 살아 있는 번호를 잘못 목록에 넣으면 그 번호도 빈 것으로 표시한다. 올바른 소유자를 취소한다는 조건과 목록의 범위가 먼저 맞아야 한다.
복구 기준과 취소 범위를 함께 맞춘다
여러 분기가 동시에 남아 있으면 한 명령이 둘 이상의 분기에 추측적으로 속할 수 있다. 바깥 분기가 틀리면 안쪽 분기 뒤의 배정도 함께 반환되어야 한다. 반대로 안쪽 분기만 틀렸다면 그보다 앞의 살아 있는 배정은 유지해야 한다. 번호를 한 번 배정했다는 기록을 어느 미해결 분기의 목록에 반영하는지가 복구 범위를 정한다.
checkpoint의 위치도 명확해야 한다. 복구되는 매핑과 반환되는 배정의 경계가 서로 어긋나면, 올바른 매핑이 가리키는 번호를 빈 것으로 표시하거나 취소된 번호를 계속 잡아 둘 수 있다. 분기 자체가 만드는 정상적인 결과가 있다면 그것 역시 올바른 경계에 속해야 한다. 원문이 설명하는 map 복구와 자원 반환을 서로 독립된 임의 시점의 사진으로 이해하면 안 된다.
분기 복구와 architectural exception에서 확정된 상태로 돌아가는 처리도 같은 기준의 snapshot 하나로 모두 설명할 수는 없다. BOOM은 예외·flush를 위한 committed map 또는 ROB 되감기를 별도로 설명한다. 어느 상태로 돌아갈지에 따라 남겨야 할 값이 달라지기 때문이다. BOOM, Resets on Exceptions and Flushes
rename checkpoint를 검증할 때는 복구된 x5가 p10인지 확인한 다음, 잘못된 경로가 받은 번호도 다시 배정할 수 있는지 확인해야 한다. 위 예에서 p7을 놓치지 않는 기준은 빈 번호의 과거 사진이 아니라 배정의 이력이다. 이름과 소유권을 같은 취소 경계로 되돌릴 때, 결과가 정확하면서 오래 실행해도 자원이 줄어들지 않는 복구가 된다.