현대 고성능 프로세서는 Instruction Level Parallelism을 극대화하기 위해 Out-of-Order 실행 구조를 적극적으로 활용한다. 이러한 구조에서 핵심적으로 사용되는 기법이 바로 Tomasulo 알고리즘이다. Tomasulo 알고리즘은 명령어 간의 데이터 의존성을 동적으로 분석하고 실행 가능한 명령어를 먼저 수행함으로써 파이프라인의 유휴 시간을 최소화하는 방식이다.
이 알고리즘을 실제 하드웨어에서 구현하기 위해 사용되는 핵심 구조가 예약 스테이션이다. 예약 스테이션은 실행 대기 중인 명령어를 저장하고 피연산자가 준비되는 시점을 감지하여 실행 유닛에 전달하는 역할을 수행한다. 본 글에서는 예약 스테이션의 구조와 Tomasulo 알고리즘의 동작 원리를 분석하고 두 개념이 어떻게 결합되어 Out-of-Order 실행을 가능하게 하는지 살펴본다.
Tomasulo 알고리즘의 기본 개념
Tomasulo 알고리즘은 IBM System 360 Model 91에서 처음 도입된 동적 스케줄링 기법이다. 이 알고리즘의 핵심 목표는 데이터 의존성으로 인해 발생하는 파이프라인 정지를 최소화하는 것이다.
기존의 In-Order 실행 구조에서는 명령어가 순차적으로 실행되기 때문에 이전 명령어가 완료되지 않으면 이후 명령어는 대기해야 한다. 그러나 Tomasulo 알고리즘은 실행 가능한 명령어를 먼저 실행함으로써 이러한 제약을 완화한다.
이 과정에서 중요한 개념이 레지스터 리네이밍이다. Tomasulo 알고리즘은 가상적인 태그를 사용하여 데이터 의존성을 추적하고 WAR 및 WAW 의존성을 제거한다. 이를 통해 더 많은 명령어를 병렬로 실행할 수 있다.
예약 스테이션의 구조
예약 스테이션은 실행 유닛 앞단에 위치한 버퍼 구조로 각 엔트리는 하나의 명령어를 저장한다. 각 엔트리는 연산 종류, 소스 피연산자, 결과 저장 위치, 그리고 피연산자 준비 상태를 나타내는 정보를 포함한다.
예약 스테이션의 가장 중요한 기능은 피연산자의 준비 상태를 추적하는 것이다. 만약 특정 피연산자가 아직 계산되지 않았다면 해당 값 대신 태그를 저장한다. 이후 해당 값이 계산되어 결과가 방송되면 예약 스테이션은 이를 감지하여 피연산자를 갱신한다.
이러한 구조는 중앙 집중식 스케줄링 대신 분산된 방식으로 명령어 실행을 관리할 수 있도록 한다.
Common Data Bus와 데이터 전달
Tomasulo 알고리즘에서 중요한 또 하나의 요소는 Common Data Bus이다. 실행 유닛에서 계산된 결과는 Common Data Bus를 통해 모든 예약 스테이션과 레지스터 파일에 전달된다.
예약 스테이션은 이 버스를 감시하면서 자신이 필요로 하는 데이터가 도착하면 이를 즉시 저장한다. 이를 통해 데이터가 준비되는 즉시 명령어 실행이 가능해진다.
이 방식은 데이터 전달 지연을 최소화하고 파이프라인 효율을 높이는 데 중요한 역할을 한다.
동적 스케줄링 과정
Tomasulo 알고리즘 기반의 실행 과정은 크게 발행, 실행, 결과 기록의 세 단계로 나눌 수 있다.
발행 단계에서는 명령어가 예약 스테이션에 할당된다. 이때 피연산자가 준비되어 있지 않으면 태그 형태로 저장된다.
실행 단계에서는 모든 피연산자가 준비된 명령어가 실행 유닛으로 전달된다. 실행 유닛은 해당 연산을 수행하고 결과를 생성한다.
결과 기록 단계에서는 실행 결과가 Common Data Bus를 통해 전달되며 이를 기다리고 있던 예약 스테이션과 레지스터가 갱신된다.
이러한 과정은 명령어 간 의존성을 동적으로 해결하며 파이프라인의 병목을 줄인다.
리오더 버퍼와의 관계
현대 프로세서에서는 Tomasulo 알고리즘이 리오더 버퍼와 함께 사용된다. 원래 Tomasulo 알고리즘은 결과를 즉시 레지스터에 기록하는 방식이었지만 이는 Precise Exception을 보장하기 어렵다.
따라서 최신 CPU에서는 예약 스테이션과 리오더 버퍼를 결합하여 사용한다. 예약 스테이션은 실행 스케줄링을 담당하고 리오더 버퍼는 결과를 프로그램 순서대로 커밋하는 역할을 수행한다.
이러한 구조를 통해 높은 성능과 정확한 예외 처리를 동시에 달성할 수 있다.
성능 관점에서의 의의
예약 스테이션과 Tomasulo 알고리즘은 Instruction Level Parallelism을 극대화하는 핵심 기술이다. 이 구조를 통해 CPU는 데이터 의존성으로 인한 대기 시간을 최소화하고 실행 유닛 활용률을 높일 수 있다.
특히 메모리 접근 지연이 큰 현대 시스템에서는 독립적인 명령어를 먼저 실행하는 능력이 전체 성능에 큰 영향을 미친다.
결론
예약 스테이션은 Tomasulo 알고리즘을 구현하는 핵심 하드웨어 구조로 명령어의 동적 스케줄링과 데이터 의존성 해결을 담당한다. 두 개념은 결합되어 Out-of-Order 실행을 가능하게 하며 현대 고성능 프로세서의 성능 향상에 중요한 역할을 한다.
앞으로의 CPU 아키텍처에서도 이러한 동적 실행 구조는 더욱 발전하여 더 높은 병렬성과 효율을 제공할 것으로 예상된다.