1. 개요
Out-of-Order Execution, OoOE일반적인 순차적 파이프라인에서는 어떤 명령어를 처리할 때 forwarding 등으로 데이터 의존성이 해결되지 않으면 앞선 명령어들의 처리에서 필요한 값이 나올 때까지 파이프라인을 중단(stall)하게 되고, 이에 따라 그 다음의 명령어들은 처리되지 못하고 대기하게 됨으로써 효율성이 떨어지게 된다. 이를 해결하기 위해 컴파일러 수준에서 파이프라인 중단을 최소화하도록 명령어를 배치하는 최적화 등을 수행하기도 하였지만, ISA의 각 구현마다 파이프라인 구조가 다르고 또한 컴파일 시간에 모든 의존성을 알 수 없는 등의 여러 한계점이 많았다. 그래서 등장한 것이 명령어를 프로그램에 나타난 순서대로 처리하지 않는 비순차적 실행 기법이다. 비순차적 실행 기법에서는 명령어 해석(Decode) 단계를 발행(Issue)과 피연산자 읽기(Read Operand)의 두 단계로 나눈다. 명령어들은 발행 단계는 순차적으로 거치게 되지만, 피연산자 읽기(Read Operand) 단계에서는 의존성이 해결될 때까지 진입하지 못하고 기다려야 하고(stall), 이 틈을 타서 뒤쪽의 명령어들이 먼저 순서를 바꾸어 실행될 수 있다.
비순차적 실행 기법의 이점은 다음과 같다.
- 컴파일러가 ISA 구현의 세부사항을 몰라도 효율적으로 실행하게끔 하는 것이 가능하다. 이 때문에, 한 ISA에 대해 각 구현마다 최적화된 바이너리를 제공할 필요가 없어졌다.
- 컴파일 시간에 의존성을 알 수 없는 경우도 효율적으로 실행할 수 있다.
- 캐시 미스와 같은 예측 불가능한 지연이 있더라도, 그 동안 다른 명령어들을 처리하고 있음으로써 대응이 가능하다.
2. 기법
2.1. Scoreboarding
CDC 6600에서 도입한 방식이다. 의존성 관리를 위해 중앙집중식의 Scoreboard를 이용하는 것이 특징이다. 동작 방식은 Scoreboarding 참고.2.2. Tomasulo 알고리즘
IBM 360/91에서 도입한 방식이다. 여러 기능 유닛(Functional Unit)들에 분산된 Reservation Station을 통해 레지스터 재명명(register renaming)을 이용하여 WAR/WAW hazard를 해결한다.3. 관련 문서
[1] Read After Write. 같은 대상에 대해 쓰는 명령어와 읽는 명령어가 순서대로 있다고 해 보자. 순차적 파이프라인에서는 레지스터에 쓰는 단계(Write Back)가 레지스터에서 계산에 필요한 값을 가져오는 명령어 해석 단계(Decode) 보다 나중에 나오므로, 명령어들을 서로 '겹쳐서' 실행할 때 어떤 명령어의 실행에 필요한 값이 이전 명령어에서 계산되고 그것이 아직 레지스터에 쓰이지 않았다면 문제가 발생한다.[2] Write After Read. 이번에는 같은 대상에 대해 읽는 명령어와 쓰는 명령어가 순서대로 있다고 해 보자. 순차적 파이프라인에서는 명령어가 겹쳐서 실행되어도 어차피 쓰기 단계가 읽기 단계보다 나중에 실행되므로 문제가 되지 않는다. 하지만 비순차적 파이프라인에서는 두 명령어의 순서가 바뀔 수 있고, 만약 쓰는 명령어가 이전에 수행되었다면 쓰기 전의 값을 읽어와야 하는 읽는 명령어 입장에서는 문제가 생긴다.[3] Write After Write. 만약 같은 대상에 대한 두 쓰기 명령어가 있는데 순서가 바뀌면, 레지스터에 남아 있어야 하는 값이 달라진다.