Tomasulo’s Algorithm(토마슬로 알고리즘)은 현대 CPU 아키텍처에서 동적 명령어 스케줄링(Dynamic Instruction Scheduling)을 실현하는 대표적인 기술입니다. 이 알고리즘은 명령어 사이의 의존성을 효율적으로 처리하며, Out-of-Order Execution(비순차 실행)을 가능하게 하는 기반이 됩니다. 특히 레지스터 충돌을 해소하고, 실행 유닛의 활용도를 높여 병렬 성능을 극대화하는 데 핵심 역할을 합니다. 본 글에서는 Tomasulo 구조의 구성 요소와 동작 방식, 그리고 그것이 동적 명령어 스케줄링과 어떻게 연관되어 있는지를 구체적으로 설명합니다.
Tomasulo 알고리즘의 기본 구조
1967년 IBM System/360 Model 91에서 처음 도입된 Tomasulo 알고리즘은 명령어를 하드웨어 수준에서 동적으로 스케줄링하여, 프로그램의 논리적 순서와 무관하게 실행할 수 있도록 설계되었습니다. 이 구조의 핵심 구성요소는 다음과 같습니다:
- Reservation Stations: 실행 유닛 앞단에 존재하는 버퍼로, 명령어가 실행될 준비가 되었는지를 판단하고 대기시킵니다.
- Common Data Bus (CDB): 실행 결과를 모든 Reservation Station 및 Register에 브로드캐스트하는 공유 버스입니다.
- Register Tagging: 명령어 간의 의존성을 추적하기 위해 레지스터에 태그(Tag)를 부여하는 기법입니다.
명령어는 디코딩 후 곧바로 실행되지 않고, Reservation Station에 등록되어 오퍼랜드가 준비될 때까지 대기합니다. 모든 오퍼랜드가 준비되면 실행 유닛으로 전달되고, 계산 결과는 CDB를 통해 다른 유닛과 레지스터로 전파됩니다.
명령어 의존성 해소와 태그 기반 스케줄링
Tomasulo 알고리즘은 다음과 같은 의존성 문제를 동적으로 해결합니다:
- RAW (Read After Write): 이전 명령어가 값을 쓰기 전, 다음 명령어가 읽으려는 경우 — CDB를 통해 해결
- WAR (Write After Read): 읽기가 끝난 후에만 쓰기 실행
- WAW (Write After Write): 결과 충돌 방지를 위한 명령어 분리
각 오퍼랜드는 실제 값 대신 태그(Tag)를 보유할 수 있으며, 이 태그는 결과가 언제 도착할지를 추적합니다. 실행 유닛은 태그와 결과를 CDB에 브로드캐스트하며, 이를 통해 여러 명령어가 동시에 결과를 공유할 수 있게 됩니다.
이 구조 덕분에 명령어는 오퍼랜드가 준비되는 즉시 실행 가능하며, 스케줄링은 하드웨어가 동적으로 수행합니다. 결과적으로 명령어 실행 순서를 유연하게 조정할 수 있고, 전체 파이프라인의 활용률을 극대화할 수 있습니다.
동적 명령어 스케줄링과의 연계
Tomasulo 구조는 동적 명령어 스케줄링(Dynamic Instruction Scheduling)의 대표 사례입니다. 기존의 정적 방식은 컴파일러가 명령어 순서를 고정했지만, Tomasulo 알고리즘은 실행 시점에서 실제 데이터를 기준으로 실행 순서를 조정합니다.
이 방식의 장점은 다음과 같습니다:
- 최대 병렬성 확보: 독립적인 명령어를 먼저 실행함으로써 CPU 유휴 시간을 줄입니다.
- 하드웨어 의존성 해소: 레지스터가 부족하거나 명령어 간 충돌이 있어도, 태그 시스템으로 관리됩니다.
- 예외 처리와 롤백 용이: 실행 결과가 확정되기 전까지 실제 레지스터에 쓰이지 않기 때문에 복구가 간편합니다.
또한 Tomasulo 알고리즘은 Register Renaming과 유사한 효과도 제공합니다. 명령어 간 이름 충돌(Name Dependency)을 태그로 대체함으로써, 병렬 실행을 방해하는 요인을 제거합니다.
결론적으로, Tomasulo 구조는 현대 고성능 CPU에서 필수적인 Out-of-Order Execution을 구현하는 기반이며, 동적 명령어 스케줄링의 실제 구현 사례 중 하나입니다. 이 기술을 통해 CPU는 더 많은 명령어를 동시에 실행하고, 복잡한 연산을 효율적으로 처리할 수 있게 됩니다.