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