레지스터 이름 변경

3. 레지스터 리네이밍의 필요성

프로그램 실행 속도를 높이기 위해 현대 프로세서는 명령어를 순서대로 처리하지 않고 가능한 병렬로 처리하는 아웃 오브 오더 실행(비순차적 실행) 방식을 사용한다. 또한, 빠른 데이터 접근을 위해 메인 메모리보다 훨씬 빠른 프로세서 레지스터를 활용한다.

하지만 명령어 집합 아키텍처에서 사용할 수 있도록 정의된 레지스터(아키텍처 레지스터)의 수는 제한적이다. 이 때문에 프로그램 내에서 동일한 레지스터를 반복해서 사용(재사용)하는 경우가 필연적으로 발생한다.

이렇게 제한된 레지스터를 재사용하면서 명령어를 비순차적으로 실행하려고 할 때 문제가 생긴다. 서로 다른 연산에 속한 명령어들이 단지 같은 이름의 레지스터를 사용한다는 이유만으로 실행 순서에 제약을 받게 되는 가짜 종속성(False Dependency)이 발생하기 때문이다. 예를 들어, 아직 이전 명령어가 읽어야 할 값을 가진 레지스터에 다음 명령어가 새로운 값을 덮어쓰려 하거나(쓰기 후 읽기, WAR), 두 명령어가 같은 레지스터에 쓰려고 경쟁하는(쓰기 후 쓰기, WAW) 경우가 이에 해당한다.

이러한 가짜 종속성은 실제 데이터 처리 흐름과는 무관하게 명령어의 병렬 실행을 방해하여 아웃 오브 오더 실행의 성능 향상 효과를 크게 저해한다. 레지스터 리네이밍(Register Renaming)은 바로 이 문제를 해결하기 위해 필요하다. 하드웨어적으로 명령어에 명시된 레지스터 이름을 내부적으로 더 많은 물리적 레지스터 중 하나로 동적으로 바꿔 할당함으로써, 이름으로 인한 충돌(가짜 종속성)을 제거하고 명령어 수준 병렬성(ILP)을 극대화하여 프로세서 성능을 높이는 핵심 기술이다.

3. 1. 명령어 집합의 제약

레지스터 수가 많으면 더 많은 임시 값을 저장하여 메모리 접근 횟수를 줄일 수 있어 성능 향상에 도움이 된다. 하지만 레지스터 수가 많아질수록 머신 코드 명령어 내에서 각 레지스터를 구분하기 위해 더 많은 비트가 필요하다. 예를 들어 32개의 레지스터를 구분하려면 5비트(2의 5제곱 = 32)가 필요하고, 64개의 레지스터를 구분하려면 6비트(2의 6제곱 = 64)가 필요하다. 명령어의 길이는 제한되어 있으므로, 레지스터 지정에 더 많은 비트를 사용하면 연산 종류나 다른 정보를 인코딩할 공간이 줄어든다. 따라서 프로세서 설계에서는 레지스터 파일 크기와 명령어 인코딩 효율성 사이의 균형을 맞추어야 한다.

이렇게 아키텍처 레지스터 수가 제한되어 있기 때문에 컴파일러가 코드를 최적화하는 데 어려움을 겪는다. 컴파일러는 제한된 수의 레지스터를 효율적으로 재사용해야 하는데, 이 과정에서 문제가 발생할 수 있다. 예를 들어, 어떤 레지스터가 특정 연산에 사용된 후, 그 결과가 필요한 다른 연산이 완료되기 전에 같은 레지스터에 다른 값을 저장하는 명령이 실행되면 프로그램 오류가 발생할 수 있다 (이를 '의존성 문제'라고 한다). 컴파일러는 가능한 경우 서로 다른 레지스터를 할당하여(일종의 레지스터 이름 변경) 이러한 문제를 피하고 명령어 실행 순서를 최적화하려 하지만, 사용 가능한 아키텍처 레지스터 수가 적으면 이러한 최적화는 제한적일 수밖에 없다. 즉, 컴파일러 수준에서 레지스터 재사용을 피하기 위해 코드를 재구성하면 코드 크기가 불필요하게 커지거나 성능 향상에 한계가 있을 수 있다.

3. 2. 비순차적 명령어 처리 (Out-of-Order Execution)

명령 #4, #5, #6은 명령 #1, #2, #3과 서로 독립적이다. 즉, 수행하려는 작업 자체에는 의존 관계가 없다. 그러나 위 코드에서는 명령 #4가 명령 #3이 완료될 때까지 실행될 수 없다. 만약 명령 #3이 완료되기 전에 명령 #4가 실행되어 레지스터 1(r1)의 값을 바꿔버리면, 명령 #3은 잘못된 값을 메모리 1032번지에 저장하게 될 위험이 있다 (이는 쓰기 후 읽기 (WAR) 종속성 문제이다). 또한, 명령 #5는 명령 #4가 레지스터 1(r1)에 새로운 값을 로드한 후에 실행되어야 올바른 연산을 수행할 수 있다 (이는 읽기 후 쓰기 (RAW) 종속성 문제이다). 이는 두 명령어 그룹이 동일한 레지스터 'r1'을 사용하기 때문에 발생하는 문제이다.

이러한 제약은 레지스터 할당 과정에서 다른 레지스터를 사용함으로써 제거할 수 있다. 만약 컴파일러가 코드를 생성할 때, 또는 하드웨어가 동적으로 레지스터 이름을 변경(리네이밍)하여 아래와 같이 코드를 수정한다면, 두 명령어 그룹은 병렬로 실행될 수 있다.

이제 명령 #4, #5, #6은 명령 #1, #2, #3과 독립적으로 병렬 실행될 수 있다. 프로그램은 불필요하게 동일한 레지스터를 사용하여 발생했던 데이터 종속성 문제를 해결함으로써 더 빠르게 실행될 수 있다.

많은 고성능 CPU는 명령어 집합에 정의된 것보다 더 많은 물리적 레지스터를 가지고 있으며, 하드웨어 수준에서 명령어에 명시된 논리 레지스터(예: r1)를 내부의 물리 레지스터(예: rA, rB)로 동적으로 매핑하는 레지스터 리네이밍을 수행한다. 이를 통해 위 예시처럼 r1만 사용하는 원래 코드도 내부적으로는 다음과 같이 처리하여 병렬성을 높인다.



rA ≔ m[1024] ; r1 -> rA 로 이름 변경

rA ≔ rA + 2

m[1032] ≔ rA

rB ≔ m[2048] ; r1 -> rB 로 이름 변경

rB ≔ rB + 4

m[2056] ≔ rB



=== 데이터 종속성 문제 ===

데이터 종속성

둘 이상의 명령어가 특정 레지스터나 메모리 위치를 피연산자로 참조할 때, 이 명령어들을 원래 프로그램 순서와 다르게 실행하면 세 가지 종류의 데이터 종속성 문제(해저드)가 발생할 수 있다.

; 읽기 후 쓰기 (Read After Write, RAW): 레지스터나 메모리 위치에서 값을 읽을 때는 프로그램 순서상 가장 마지막에 해당 위치에 기록된 값을 읽어야 한다. 즉, 이전 쓰기 명령의 결과가 완전히 반영된 후에 읽기 명령이 수행되어야 한다. 이는 진정한 종속성(True Dependency) 또는 흐름 종속성(Flow Dependency)이라고 하며, 명령어 실행 순서를 반드시 지켜야 하므로 레지스터 리네이밍으로 해결할 수 없다.

; 쓰기 후 쓰기 (Write After Write, WAW): 특정 레지스터나 메모리 위치에 여러 번의 쓰기 명령이 연속될 경우, 프로그램 순서상 가장 마지막의 쓰기 결과가 최종적으로 남아야 한다. 이전의 쓰기 명령 결과는 무시될 수 있다. 이는 출력 종속성(Output Dependency)이라고 하며, 이름 때문에 발생하는 가짜 종속성(False Dependency)이다. 레지스터 리네이밍을 통해 각 쓰기 명령이 서로 다른 물리 레지스터를 사용하게 함으로써 동시에 실행될 수 있도록 해결할 수 있다. 필요하다면 순서상 앞선 쓰기 명령을 무효화(취소)하여 해결할 수도 있다.

; 쓰기 후 읽기 (Write After Read, WAR): 레지스터나 메모리 위치에서 값을 읽은 후, 프로그램 순서상 나중에 오는 명령이 해당 위치에 새로운 값을 쓰는 경우이다. 읽기 명령은 나중의 쓰기 명령이 실행되기 전에 완료되어, 쓰기 전의 원래 값을 읽어야 한다. 이는 반대 종속성(Anti-dependency)이라고 하며, 이것 역시 이름 때문에 발생하는 가짜 종속성(False Dependency)이다. 레지스터 리네이밍을 통해 쓰기 명령이 새로운 물리 레지스터를 사용하도록 하여 읽기 명령과의 충돌을 피함으로써 해결할 수 있다.

레지스터 리네이밍은 WAW과 WAR 같은 가짜 종속성을 제거하는 핵심 기술이다. 모든 읽기가 완료될 때까지 쓰기를 지연시키는 대신, 이전 값과 새 값의 두 복사본을 유지할 수 있다. 새 값을 쓰기 전에 프로그램 순서상 앞서는 읽기에는 이전 값을 제공하고, 쓰기 이후의 읽기에는 새 값을 제공한다. 가짜 종속성이 제거되면 비순차적 실행의 기회가 늘어난다. 이전 값을 필요로 하는 모든 읽기가 완료되면 이전 값 복사본은 폐기될 수 있다. 이것이 레지스터 리네이밍의 본질적인 개념이다.

읽고 쓸 수 있는 모든 것은 이름 변경이 가능하다. 주로 범용 레지스터나 부동 소수점 레지스터가 대상이지만, 플래그나 상태 레지스터, 심지어 개별 상태 비트도 이름 변경 대상이 될 수 있다. 메모리 위치도 이름 변경이 가능하지만, 레지스터 리네이밍만큼 일반적으로 수행되지는 않는다. (트랜스메타의 크루소 프로세서에 구현된 스토어 버퍼는 메모리 이름 변경의 한 예이다.)

프로그램이 레지스터를 즉시 재사용하지 않도록 컴파일러가 코드를 최적화하면 레지스터 리네이밍의 필요성이 줄어든다. 일부 명령어 집합(예: IA-64)은 이러한 이유로 매우 많은 수의 레지스터를 제공한다. 그러나 이 접근 방식에는 다음과 같은 한계가 있다.

• 컴파일러가 코드 크기를 크게 늘리지 않고 레지스터 재사용을 피하기는 어렵다. 특히 루프 내에서 각 반복마다 다른 레지스터를 사용하려면 코드를 복제(루프 언롤링)하거나 자기 수정 코드를 사용해야 할 수 있다. (단, IA-64는 레지스터 로테이션이라는 기술로 이를 일부 회피한다.)
• 레지스터 수가 많아지면 명령 내에서 레지스터를 지정하는 데 더 많은 비트가 필요해져 코드 크기가 커진다.
• 많은 기존 명령어 집합은 역사적으로 적은 수의 레지스터를 정의했으며, 하위 호환성 문제로 이를 변경하기 어렵다.

4. 레지스터 리네이밍의 종류

컴퓨터 프로그램은 명령어 집합 아키텍처(ISA)에 정의된 제한된 수의 레지스터를 사용하여 데이터를 읽고 쓴다. 예를 들어 알파 ISA는 32개의 64비트 정수 레지스터와 32개의 64비트 부동소수점 레지스터를 정의하는데, 이를 아키텍처 레지스터라고 부른다. 프로그래머나 디버거는 이 아키텍처 레지스터를 통해 프로그램의 상태를 확인한다.

하지만 실제 CPU 내부에는 아키텍처 레지스터보다 훨씬 많은 수의 물리 레지스터가 존재할 수 있다. 예를 들어 알파 ISA를 구현한 알파 21264 프로세서는 80개의 정수 물리 레지스터와 72개의 부동소수점 물리 레지스터를 가졌다. 물리 레지스터를 더 많이 두는 주된 이유는 아웃 오브 오더 실행 과정에서 발생하는 데이터 의존성 문제, 특히 쓰기 후 읽기(Write-After-Read, WAR)나 쓰기 후 쓰기(Write-After-Write, WAW)와 같은 가짜 종속성(False Dependencies^eng)을 해결하여 명령어 수준 병렬성을 높이기 위해서다. 이를 위해 아키텍처 레지스터 이름을 내부적으로 사용하는 물리 레지스터 이름(또는 태그)으로 바꾸는 기술이 바로 레지스터 이름 변경(Register Renaming^eng)이다.

레지스터 이름 변경은 크게 두 가지 방식으로 나눌 수 있으며, 이는 주로 실행 유닛에 데이터를 저장하는 레지스터 파일의 구조적 차이에 따라 구분된다. 두 방식 모두 명령어에서 사용된 아키텍처 레지스터를 내부적인 태그(Tag^eng)로 변환하여 물리 레지스터를 식별하는 과정을 포함한다. 이 태그는 일반적으로 아키텍처 레지스터 번호보다 더 많은 비트를 사용하여 더 많은 수의 물리 레지스터를 구별할 수 있게 해준다.

레지스터 이름 변경의 주요 두 가지 스타일은 다음과 같다.

• 태그 인덱싱된 레지스터 파일: 모든 태그에 대응하는 물리 레지스터를 하나의 큰 중앙 레지스터 파일(물리 레지스터 파일, PRF)에 두고, 태그를 직접 인덱스로 사용하여 데이터에 접근하는 방식이다.
• 예약 스테이션: 각 실행 유닛마다 비교적 작은 크기의 레지스터 파일(예약 스테이션)을 여러 개 두어 데이터를 분산하여 관리하는 방식이다.

4. 1. 태그 인덱싱된 레지스터 파일 (Tag-Indexed Register File)

• 만약 해당 레지스터에 값을 쓸 예정인 이전 명령어가 아직 완료되지 않았다면, 레디 비트는 '준비되지 않음(not ready)' 상태를 나타낸다.
• 읽기 피연산자의 경우, 명령어의 아키텍처 레지스터 지정자는 리맵 파일에서 얻은 태그로 교체된다.
• 쓰기 피연산자의 경우, '''자유 태그 FIFO'''(Free Tag FIFO)에서 새로운 태그를 할당받는다. 이 새로운 태그와 아키텍처 레지스터 간의 매핑 정보가 리맵 파일에 기록되며, 상태는 '준비되지 않음'으로 표시된다. 이전에 해당 아키텍처 레지스터에 할당되었던 물리 레지스터(이전 태그)는 명령어와 함께 '''재정렬 버퍼'''(Reorder Buffer, ROB)에 저장된다. 재정렬 버퍼는 명령어를 프로그램의 원래 순서대로 유지하는 FIFO 구조이다.

4. 2. 예약 스테이션 (Reservation Stations)

• 지연 시간 감소:
• 리네이밍 단계에서 실행까지의 지연 시간이 짧다. 이는 리네이밍 단계에서 물리 레지스터 번호를 찾고 다시 값을 찾는 대신, 미래 파일에서 직접 값을 조회하기 때문이다. 이 지연 시간 단축은 특히 분기 예측 실패 시 복구 시간을 줄이는 데 기여한다.
• 명령어 발행에서 실행까지의 지연 시간도 짧다. 각 실행 유닛에 연결된 로컬 예약 스테이션의 레지스터 파일이 태그-인덱싱 방식의 큰 중앙 레지스터 파일보다 작기 때문이다.
• 단순화된 처리: 태그 생성 및 예외 처리가 태그-인덱싱 방식보다 상대적으로 간단하다.

• 복잡한 하드웨어: 예약 스테이션에서 사용되는 레지스터 파일 시스템은 사용되지 않는 항목을 채우는 기능과 발행 큐 처리를 병행해야 하므로, 태그-인덱싱 방식의 레지스터 파일보다 구조가 더 복잡하다.
• 많은 바이패스 네트워크: 예약 스테이션의 각 항목은 모든 결과 버스(Result Bus^eng)로부터 쓰기가 가능해야 한다. 예를 들어, 기능 유닛당 8개의 발행 큐 항목을 가진 예약 스테이션 구조는 동등한 태그-인덱싱 구조보다 훨씬 많은 바이패스 네트워크(결과를 필요한 곳으로 전달하는 경로)를 요구한다. 이로 인해 결과 전달에 더 많은 전력과 칩 면적이 소모된다.
• 분산된 결과 저장 위치: 결과 값이 미래 파일, 예약 스테이션, 재정렬 버퍼, 아키텍처 레지스터 파일 네 곳에 저장될 수 있다. 반면 태그-인덱싱 방식은 물리 레지스터 파일 한 곳에만 저장한다. 여러 위치로 결과를 브로드캐스트하고 관리해야 하므로 더 많은 전력, 면적, 시간이 소요된다.

5. 관련 기술

레지스터 이름 변경 기술은 현대 CPU의 성능을 높이기 위해 다른 여러 기술과 함께 사용된다. 특히 명령어 처리 순서를 최적화하여 명령어 수준 병렬성(Instruction-Level Parallelism, ILP)을 높이는 비순차적 실행(Out-of-Order Execution)과 밀접한 관련이 있다. 비순차적 실행 과정에서 발생할 수 있는 거짓 종속성(false dependency) 문제를 해결하는 데 레지스터 이름 변경이 중요한 역할을 수행한다.

5. 1. 비순차적 명령어 처리 (Out-of-Order Execution)

여기서 4, 5, 6번 명령어는 1, 2, 3번 명령어와 내용상으로는 독립적이다. 하지만 4번 명령어는 3번 명령어가 완료될 때까지 기다려야 한다. 만약 4번 명령어가 먼저 실행되어 레지스터 1의 값을 바꿔버리면, 3번 명령어가 잘못된 값을 메모리에 저장할 수 있기 때문이다. 이는 실제 데이터 의존성이 아닌, 같은 레지스터 이름(`레지스터 1`)을 재사용하면서 발생하는 거짓 종속성(false dependency) 또는 이름 종속성(name dependency) 때문이다.

이러한 거짓 종속성은 레지스터 이름 변경을 통해 해결할 수 있다. 즉, 서로 다른 명령어 그룹에 다른 레지스터를 할당하는 것이다.

이렇게 레지스터를 분리하면, 4, 5, 6번 명령어는 1, 2, 3번 명령어의 완료를 기다릴 필요 없이 병렬로 실행될 수 있다. 이를 통해 명령어 수준 병렬성(Instruction-Level Parallelism, ILP)을 높여 프로그램 실행 속도를 향상시킨다.

컴파일러는 코드 생성 단계에서 레지스터 할당을 통해 이러한 이름 변경을 시도할 수 있다. 하지만 프로그래머가 직접 접근할 수 있는 아키텍처 레지스터(예: x86의 8개 정수 레지스터, AMD64의 16개 등)의 수는 제한적이므로 컴파일러만으로는 한계가 있다. 따라서 많은 고성능 CPU는 명령어 집합에 정의된 아키텍처 레지스터보다 더 많은 수의 물리적 레지스터를 내부에 가지고 있다. 그리고 하드웨어 수준에서 동적으로 명령어의 레지스터 이름을 내부의 물리적 레지스터로 재할당(이름 변경)하여 거짓 종속성을 제거하고, 비순차적 실행을 통해 명령어 수준 병렬성을 극대화한다.

참조

_[1] 웹사이트 Cyrix 6x86 Processor https://web.archive.[...]
_[2] 간행물 NexGen Details Sixth Generation Nx686 Processor Technology http://www.cpushack.[...]
_[3] 논문 100 MHz and Beyond https://books.google[...] Ziff Davis 1994-12-06
_[4] 논문 The design space of register renaming techniques http://www.eecs.umic[...] IEEE 2000-09