레지스터 리네임 (Register Renaming)

개요

레지스터 리네임(Register Renaming)은 프로세서가 명령어 세트 아키텍처(ISA)에 정의된 제한된 수의 논리적 레지스터(logical registers)를, 내부적으로 훨씬 많은 수의 물리적 레지스터(physical registers)에 동적으로 매핑하는 하드웨어 기술이다. 이 기술은 Out-of-Order 실행에서 거짓 의존성(false dependency)을 제거하여 명령어 수준 병렬성(ILP)을 극대화하는 핵심 메커니즘이다.

컴파일러가 생성한 코드는 레지스터 수가 제한되어 있어 동일한 레지스터를 반복적으로 사용한다. 그러나 실제 데이터 의존성이 없는 명령어들이라도 같은 레지스터 이름을 공유하면 프로세서는 이를真正的 의존성으로 오인하여 불필요하게 명령어 실행을 순서대로 제한하게 된다. 레지스터 리네임은 이러한 WAR(Write-After-Read)와 WAW(Write-After-Write) 의존성을 하드웨어가 자동으로 제거하여 병렬 실행 기회를 확보한다.

핵심 개념

데이터 의존성 유형

Out-of-Order 실행에서 명령어 간 의존성은 세 가지 유형으로 분류된다:

RAW (Read-After-Write): 명령어 B가 명령어 A의 결과를 읽어야 하는 경우. 이는 실제 데이터 흐름 의존성이므로 리네임으로 제거할 수 없고,Operand Forwarding이나 타이밍 대기로 해결한다.

WAR (Write-After-Read): 명령어 A가 레지스터 R1을 읽은 후, 명령어 B가 R1에 쓰는 경우. B가 먼저 실행되면 A가 잘못된 값을 읽게 된다. 리네임을 통해 A와 B를 서로 다른 물리적 레지스터에 매핑하면 해결된다.

WAW (Write-After-Write): 명령어 A와 B가 모두 같은 레지스터 R1에 쓰는 경우. 최종적으로 B의 결과가 남아야 하는데, A가 늦게 실행되면 B의 값을 덮어쓸 수 있다. 리네임을 통해 각각 다른 물리적 레지스터에 매핑하면 해결된다.

논리적 레지스터 vs 물리적 레지스터

예시:

; x86-64 코드 (논리적 레지스터 16개)
ADD R1, R2, R3    ; R1 = R2 + R3
SUB R1, R4, R5    ; R1 = R4 - R5 (WAW 의존성)
MUL R6, R1, R7    ; R6 = R1 * R7 (RAW 의존성)

; 리네임 후 (물리적 레지스터 P0~Pn)
ADD P10, P2, P3   ; P10 = P2 + P3
SUB P11, P4, P5   ; P11 = P4 - P5 (WAW 제거)
MUL P12, P11, P7  ; P12 = P11 * P7 (RAW는 유지)
; 결과: WAW 의존성 제거, SUB와 MUL 사이 병렬 실행 가능

리네임 테이블 (Register Alias Table, RAT)

리네임 테이블은 논리적 레지스터에서 현재 유효한 물리적 레지스터로의 매핑을 저장하는 테이블이다. 명령어가 디코딩될 때마다 이 테이블을 참조하여:

1. 소스 피연산자: 현재 매핑된 물리적 레지스터 번호를 명령어에 기록
2. 대상 피연산자: 새로운 물리적 레지스터를 할당하고 테이블 업데이트

동작 과정:

초기 상태: R1 → P5, R2 → P3, R3 → P7

ADD R1, R2, R3  디코딩:
  - 소스 R2 → P3 확인
  - 소스 R3 → P7 확인
  - 대상 R1 → 새 물리적 레지스터 P10 할당
  - 테이블 업데이트: R1 → P10

SUB R1, R4, R5  디코딩:
  - 소스 R4, R5 → 각각 매핑 확인
  - 대상 R1 → 새 물리적 레지스터 P11 할당
  - 테이블 업데이트: R1 → P11
  (이 시점에서 R1은 P11을 가리키므로, 이전 ADD의 P10과 독립)

물리적 레지스터 파일 (Physical Register File, PRF)

물리적 레지스터 파일은 리네임된 결과값을 저장하는 실제 하드웨어 레지스터 집합이다.

주요 특징:
- 논리적 레지스터보다 훨씬 많은 엔트리 보유 (일반적으로 2~4배)
- 여러 명령어가 동시에 다른 물리적 레지스터에 기록 가능
- 읽기/쓰기 포트 수가 명령어 병렬도에 따라 결정
- 면적과 전력 소비가 리네임 테이블보다 큼

크기 결정 요인:
- Out-of-Order 파이프라인의 깊이 (Inflight 명령어 수)
- 동시에 실행되는 명령어 수 (Issue Width)
- 메모리 지연 시간 (캐시 미스 시 추가 레지스터 필요)

비교/분석

리네임 구현 방식 비교

현대 프로세서에서 사용되는 리네임 방식은 크게 두 가지로 분류된다:

태그 인덱스 방식 상세

태그 인덱스 방식은 하나의 큰 물리적 레지스터 파일을 사용하며, 각 태그가 물리적 레지스터를 직접 가리킨다.

동작 흐름:
1. 디코딩 시 리맵 파일에서 논리적 레지스터의 현재 태그를 조회
2. 쓰기 명령어에는 새 태그를 프리 태그 큐(Free Tag FIFO)에서 할당
3. 리맵 파일에 새 매핑을 기록하고 이전 태그는 ROB에 저장
4. 실행 시 태그로 물리적 레지스터 파일을 직접 읽음
5. 실행 결과를 모든 이슈 큐에 브로드캐스트하여 준비 상태 업데이트

복구 메커니즘: 분기 예측 실패나 예외 발생 시, 리맵 파일을 마지막 유효 명령어의 상태로 되돌린다. 이전 태그를 순회하거나 스냅샷을 사용하여 복구할 수 있다.

리저버베이션 스테이션 방식 상세

리저버베이션 스테이션 방식은 각 실행 유닛에 분산된 작은 레지스터 파일을 사용한다.

동작 흐름:
1. 디코딩 시 Future File에서 현재 값을 직접 읽음
2. 읽은 값을 리저버베이션 스테이션에 즉시 기록
3. 쓰기 명령어에는 새 태그를 순차적으로 할당
4. 실행 결과가 CDB(Common Data Bus)에 브로드캐스트되면 매칭되는 모든 RS에 값 전달
5. 실행 완료 시 ROB에 결과를 기록

복구 메커니즘: 예외나 분기 실패 시 아키텍처 레지스터를 Future File로 복사하고 모든 레지스터를 준비 상태로 표시한다. 중간 상태 복구는 일반적으로 불가능하다.

현대 프로세서의 리네임 구현

동작 원리

Tomasulo 알고리즘과 리네임

Tomasulo 알고리즘은 레지스터 리네임의 초기 구현으로, IBM System/360 Model 91(1967)에서 처음 사용되었다.

핵심 구성 요소:
1. 리저버베이션 스테이션 (RS): 각 실행 유닛에 연결된 대기 큐. 명령어의 피연산자가 준비될 때까지 대기
2. 커먼 데이터 버스 (CDB): 실행 결과를 모든 RS에 동시에 브로드캐스트하는 공유 버스
3. 레지스터 상태 테이블: 각 논리적 레지스터가 어떤 RS에서 결과를 기다리는지 추적

Tomasulo의 레지스터 리네임 과정:

Stage 1 — Issue (발행):
  명령어가 Instruction Queue에서 꺼내짐
  소스 피연산자:
    - 레지스터 상태 테이블에서 현재 매핑 확인
    - 매핑이 없으면 → 값이 준비됨 (Vj/Vk에 저장)
    - 매핑이 있으면 → 해당 RS 번호를 태그로 기록 (Qj/Qk)
  대상 피연산자:
    - 새 RS를 할당하고 레지스터 상태 테이블 업데이트

Stage 2 — Execute (실행):
  모든 피연산자의 태그가 0이 되면 (값이 준비되면) 실행 시작
  CDB가 사용 가능할 때 결과를 브로드캐스트

Stage 3 — Write Result (결과 기록):
  CDB를 통해 결과를 모든 RS와 레지스터 파일에 전달
  대기 중인 명령어의 태그를 실제 값으로 교체

리네임 파이프라인 흐름

현대 프로세서에서 명령어가 리네임을 거치는 전체 흐름은 다음과 같다:

1. Fetch (인출): 명령어를 I-Cache에서 인출
2. Decode (디코딩): 명령어를 해석하고 레지스터 참조 확인
3. Rename (리네임): RAT를 참조하여 논리적 레지스터를 물리적 레지스터로 매핑
4. Allocate (할당): ROB 엔트리와 RS 엔트리를 할당
5. Dispatch (디스패치): 리네임된 명령어를 RS에 전달
6. Issue (이슈): 피연산자가 준비된 명령어를 실행 유닛으로 전달
7. Execute (실행): 실제 연산 수행
8. Writeback (리턴): 결과를 PRF에 기록하고 CDB로 브로드캐스트
9. Retire/Commit (퇴역): ROB에서 프로그램 순서대로 결과를 아키텍처 레지스터에 반영

복구 메커니즘

분기 예측 실패나 예외 발생 시 리네임된 상태를 정확히 복구해야 한다.

Two-Phase Restore:
1. Fast Restore (빠른 복구): ROB를 순회하면서 리맵 파일의 이전 매핑을 복원
2. Slow Restore (느린 복구): 아키텍처 레지스터를 PRF에서 직접 복원 (예외 처리 시)

Checkpoint 기반 복구:
- 분기 예측 시점의 리맵 파일 스냅샷을 저장
- 실패 시 스냅샷으로 즉시 복구 가능
- 스냅샷 저장 비용이 크므로, 분기 버퍼가 깊지 않은 경우에 적합

장단점

장점

1. 거짓 의존성 제거: WAR, WAW 의존성을 하드웨어가 자동으로 제거하여 병렬 실행 기회 확대
2. 컴파일러 부담 감소: 컴파일러가 레지스터 할당을 최적화하지 않아도 하드웨어가 자동으로 처리
3. 기존 코드 호환: 기존 바이너리 코드에서도 리네임 이점을 누릴 수 있음
4. 유연한 실행 순서: 명령어 실행 순서를 동적으로 변경하여 파이프라인 유휴 시간 최소화

단점

1. 하드웨어 복잡도 증가: 리네임 테이블, 물리적 레지스터 파일, 복구 메커니즘 추가
2. 면적/전력 오버헤드: 물리적 레지스터 파일은 면적과 전력 소비가 상당함
3. 복구 지연 시간: 예외나 분기 실패 시 전체 파이프라인 상태를 복구해야 함
4. 정확한 예외 처리의 어려움: Out-of-Order 실행으로 인해 정확한 예외 시점 파악이 복잡

관련 기술

관련 문서

• Out-of-Order 실행 — 리네임이 적용되는 실행 방식
• 메모리 의존성 판별 — 메모리 레이턴시 히든 기법
• 슈퍼스칼라/와이드 이슈 — 병렬 명령어 발행
• 파이프라인 스톨 — 리네임이 해결하는 문제 유형
• 파이프라인/마이크로아키텍처 기초 — 전체 파이프라인 구조
• 메모리 일관성 모델 — 메모리 접근 순서 보장

참고 문헌

1. Hennessy, J. L.; Patterson, D. A. (2017). Computer Architecture: A Quantitative Approach (6th ed.). Morgan Kaufmann.
2. Simu, D. (2000). "The design space of register renaming techniques". IEEE Micro, 20(5), 70-83.
3. Tomasulo, R. M. (1967). "An Efficient Algorithm for Exploiting Multiple Arithmetic Units". IBM Journal of Research and Development, 11(1), 25-33.
4. Smith, J. E.; Pleszkun, A. R. (1988). "Implementing precise interrupts in pipelined processors". IEEE Trans. Comput., 37(5), 562-573.
5. Intel 64 and IA-32 Architectures Software Developer's Manual. Intel Corporation.
6. Agner Fog. Microarchitecture of Intel, AMD, and VIA CPUs. (https://www.agner.org/optimize/)

핵심 정리

레지스터 리네임은 ISA가 정의한 논리적 레지스터를 하드웨어가 충분한 물리적 레지스터에 동적으로 매핑하여 Out-of-Order 실행에서 WAR/WAW 거짓 의존성을 제거하는 핵심 기술이다. 태그 인덱스 물리적 레지스터 방식과 리저버베이션 스테이션 방식의 두 가지 주요 구현이 있으며, 현대 프로세서는 대부분 태그 인덱스 방식을 채택하고 있다. 리네임은 Tomasulo 알고리즘(1967)에서 비롯되었으며, Intel P6 마이크로아키텍처 이후 x86 프로세서의 표준 기능이 되었다. 물리적 레지스터 파일의 크기는 파이프라인 깊이, 이슈 폭, 캐시 지연 시간에 따라 결정되며, 일반적으로 논리적 레지스터의 2~4배 수준으로 설계된다.