Out-of-order Processor Pipeline 이란

Out-of-order Processor Pipeline이란

CPU에서 특정 작업이 지연됨에 따라 낭비될 수 있는 명렁 사이클을 이용하기 위한 방식이다. 말 그대로 명령어를 순서대로 처리하지 않는다. 이러한 행동이 어떻게 성능 향상으로 이어질 수 있는지에 대해 다음 설명을 보자.

값 A는 CPU의 캐시에 있고, 값 B는 없어서 메모리를 읽어와야 하는 상황일 때

var c = B;
var d = A;

위와 같은 코드를 만난다면 어떻게 처리하는게 더욱 효과적일까?

1. 순차적 처리

   1. 값 B를 캐시에서 찾음
   2. 캐시 미스가 발생하고 값 B를 메모리에서 읽어 옴
   3. 값 c를 할당한 뒤, 메모리에서 읽어 온 값 B로 초기화 (이 과정에서 값 A가 캐시에서 사라짐)
   4. 값 A를 캐시에서 찾음
   5. 캐시 미스가 발생하고 값 A를 메모리에서 읽어 옴
   6. 값 d를 할당한 뒤, 메모리에서 읽어 온 값 A로 초기화

2. 비순차적 처리

   1. 값 B가 필요한 코드를 만났지만 캐시 미스라 일단 대기
   2. 값 A가 필요한 코드를 만났고 캐시 히트
   3. 값 d를 할당한 뒤, 캐시 히트한 A로 초기화
   4. 값 B를 메모리에성 읽어 옴
   5. 값 c를 할당한 뒤, 메모리에서 읽어 온 값 B로 초기화

답은 당연히 2번이다. 순차적으로 처리하였을 경우라면 두 번의 메모리 IO가 발생하지만 순서를 바꾸는 것만으로 한번에 해결할 수 있다.

이 OoOE 때문에 Lock(...)메서드 while문에서 조건으로 사용되는 g_flags[otherId]값은 아주 가끔씩 g_flags[myId] = true;로 갱신되기 이전의 값일 수 있으며 그 결과 버그가 된다.

비순차 실행은 명령어 수준에서 병렬성(Instruction Level Parallelism)을 찾아서 이를 순차적이 아닌 비순차적, 즉 병렬적으로 처리할 수 있도록 한 기술을 말한다. 명령들을 비순차적으로 병령처리 하기 위해선 다음의 기술들이 필요하다. 

• 명령어 윈도우
• 가짜 의존성 제거
• 동적 명령어 스케줄링
• 순차적 완료

명령어 윈도우

프로세서 파이프라인에서는 명령어들이 스트림으로 처리된다. 명령어의 스트림에서 각 명령어들의 의존 관계를 분석이 필요한데, 만약 하나 하나의 명령어를 순차적으로 분석하면 의존성 검사의 비용이 너무 커진다. 
그래서, 필요한 것이 명령어 윈도우(Instruction Window)개념이다. 명령어 스트림 속에서 일정 숫자만큼의 범위 내에서 ILP 를 검사하여 비순차적으로 처리한다.  즉, 명령어 윈도우의 가장 오래된 명령어부터 약 100 여개(시스템마다 다름) 정도의 명령어를 묶어서 의존성 검사를 진행한다. 처리가 끝나면 가장 오래된 명령어가 윈도우에서 빠지고 동시에 새로운 명령어 하나가 추가되어 같은 과정을 밟습니다. 

명령어 윈도우라는 것은 개념적인 것이고, 그 실체는 아래에서 이야기하게될 Register Renaming, Reservation Station, Reorder Buffer 들이 모두 어우러져서 그러한 개념적 명령어 윈도우의 역할을 하는 것이다.

위 그림은 아래와 같이 동작한다. 

• 1. 명령어 하나가 명령어 윈도우 속으로 들어온다. 이와 동시에 제일 오래된 명령어 하나는 완료되어 빠져나간다.
• 2. 윈도우 내에서 명령어들을 처리한다. (의존성 체크, 스케줄링 후 병렬실행, 이전 명령어 완료 기다림, …)
• 3. 명령어 윈도우 내에서 가장 오래된 명령어가 빠져나가고, 동시에 다른 명령어가 들어온다.

비순차 실행(Out-of-execution)을 이해하기 위해선 명령어 윈도우 내에서 어떠한 과정이 진행되는지 알아야 한다. 

명령어 윈도우 내에선 다음의 과정이 일어난다. 가짜 의존성 제거를 위한 Register Renaming, Reservation Station 을 이용한 명령어 동적 스케줄링, 순차적 완료를 위한 Reorder Buffer 이다.

가짜 의존성 제거 : Register Renaming

가짜 의존성이라는 것은 코드에 사용된 레지스터를 보면 상하 코드가 의존적인 것처럼 보이지만, 의미적으로 따져보면 실제로는 의존성이 존재하지 않는 경우를 말한다.
아래 코드를 보면, (다)명령과 (라)명령은 마치 r1 때문에 (가)명령과 의존성이 있는 것처럼 보인다.
하지만, (다)명령과 (라)명령은 r1 이라는 레지스터를 다른 레지스터로 변경해도 무방합니다. 반드시 r1 을 사용할 필요는 없다.

1. add r1, r1, #5 -> add F1, r1, #5 (가)
2. add r2, r1, #4 -> add F2, F1, #4 (나)
3. add r1, r2, #3 -> add F3, F2, #3 (다) @ r1 은 (가)와 의존성 없으므로 F3 으로 변경
4. add r1, r3, #2 -> add F5, F4, #2 (라) @ (가)와는 의존성 없으나 (마)와 의존성 존재
5. add r4, r1, #1 -> add F6, F5, #1 (마) @ (라)와의 의존성 고려하여 F5 로 변경

그렇다면, 이를 어쩌죠? 그냥 r3 나 r4 등으로 변경하면 되나 ? 그냥 변경하면 안된다. 뒤에 나올 명령어에서 사용하는 레지스터의 의존성까지 따져볼 수 있는 형태가 되어야한다. 그렇지 않고 무작정 지금까지 사용하지 않은 레지스터로 바꾸어 버린다면 뒤에서 뜻하지 않은 의존성이 생길 수 있다.
그리고, 분명히 이러한 가짜 의존성을 제거하기 위해 다른 레지스터로 갈아치는 것이 많아지면 r 로 표시되는 범용 레지스터의 수도 부족하게 느껴질 것이다. 그래서 필요한 것이 논리레지스터 파일(구조레지스터 파일, Architecture Register File, ARF) 또는 물리레지스터 파일(Physical Register File, PRF)의 개념이다. 우리가 보통 명령어 상에서 볼 수 있는 r(번호)에 해당하는 레지스터는 논리레지스터입니다. 사용자(프로그래머)에게 보이는 이름이라고 보시면 됩니다. 이러한 논리레지스터들의 이름은 사용자와의 인터페이스이니 한번 결정되면 마음대로 바꿀 수 없습니다. 그런데, 프로그래머에게 보이지 않는 물리레지스터 파일이라는 개념을 두어서, 프로그래머 모르게 마음대로 바꿀 수 있는 영역을 가지고 있다.
위의 코드의 우측 부분을 보면, r 레지스터 이름을 가짜 의존성 제거를 위해 F 레지스터(물리레지스터)로 변경한 것을 알 수 있다. 이러한 변경은 프로그래머의 영역이 아닌 하드웨어 설계자의 영역이다. 
이렇게 의존성 체크 과정에서 가짜 의존성이 발견되어 레지스터의 이름을 살짝 바꾸어주는 과정을 Rester Renaming 이라고 부른다.
추가로, 잊지 말아야할 것은 이렇게 두 부류의 레지스터 파일을 이용해서 프로그래머가 모르는 채로 내부적인 레지스터의 변경작업을 하려니까, 당연히 양쪽 레지스터 간의 매핑 관계를 어딘가에 기록해두어야한다는 것입니다. 이렇게 기록을 해두어야 이미 사용한 물리레지스터를 다시 사용하지 않을 수 있고, 선후 명령어 간의 의존성도 잘 따져볼 수 있겠지요.
이렇게 논리레지스터와 물리레지스터의 매핑정보를 유지하는 장소를 RAT(Register Alias Table)이라고 부른다.

동적 명령어 스케줄링 : Reservation Station

명령어를 실행하려면 명령어에서 사용하는 operand 가 준비되어야 합니다. 이를 달리 말하면, operand 만 준비되면 명령어는 수행 가능하다는 말이다.
그렇다면, operand 가 준비안된 명령어는 어떻게 대기 시키며, 기다리던 operand 가 준비되면 곧 바로 실행장치(Execution Unit)에게 계산을 시행시키는 일련의 과정은 어떻게 일어날 까?
이렇게 주구장창 operand 를 기다리기 위해 눌러앉는 곳이 Reservation Station 이라는 Queue입니다.
Reservation Station 에 눌러 앉은 명령어는 두 가지 핵심 작업을 합니다.

• Operand 준비됐다. 깨워. -> Wake-up
• 이제 실행하면 되는데 놀고 있는 실행장치 어떤거야 ? -> Select

Wake-up 작업은 어떤 선행 연산이 끝나서 operand 가 준비가 됐는데, Reservation Station 에서 기다리는 어떤 명령어가 이 operand 를 기다리고 있었나 찾는 것을 말합니다. 이것을 찾으려면 매번 Reservation Station Queue 에 있는 명령어들이 필요로 하는 Operand 들을 모두 체크한다. (Bottle neck point)
Select 작업은 위에 말한대로 operand 가 준비되어 실행가능한 상태의 명령어보다 사용 가능한 실행 장치의 숫자가 적은 상황이 있을 수 있으므로 이러한 실행 장치의 할당을 효과적으로 수행할 수 있도록 스케줄링하는 것을 말한다. (이 부분도 당연히 실행가능한 명령어 수보다 처리 가능한 장치수가 훨씬 적을 수 있는 경우들이 있으므로 역시 병목지점)
이러한 병목 현상과 복잡성 때문에 Reservation Station Queue 의 크기를 무작정 늘려서 병렬성을 높이는 작업에 한계가 있습니다.
결국 이러한 Reservation Station 이 존재함으로 해서 명령어들의 실행이 반드시 순차적이지 않고, operand 가 준비된대로 비순차적으로 스케줄링되어 실행이 가능한 것입니다. Reservation Station 에 명령어가 투입되는 순간부터 실행결과가 나오는 때까지는 비순차적일 수 있는 것입니다.
이렇게 operand 의 준비상태에 따라 동적으로 스케줄링하는 알고리즘이 바로 토마슐로(Tomasulo) 알고리즘입니다.

순차적 완료 : Reorder Buffer

위에 보았듯이 명령어의 실행완료까지는 비순차적일 수 있다. 그래서, 실행은 빠른 놈이 먼저 끝내고, 또 명령어 병렬화로 이리 저리 순서가 뒤섞여서 끝났더라도 결론적으로는 어떻게 해서든 프로그래머에게는 원하던 순서대로 결과를 보이는 과정이 필요한데 이 떄 사용하는 것이 Reorder Buffer다.
Reorder Buffer 에 차곡차곡 실행끝난 놈들을 모아뒀다가 원래의 프로그램 순서대로 차례차례(In-order) 데이터 Commit 을 해주는 겁니다.
그렇게 하려면, Reorder Buffer 에는 당연히 실행순서대로 명령어를 쌓아두는 것이 아니라, 원래 명령어의 순서대로 쌓아두어야 한다. 실행이 끝난 놈들을 마구잡이로 쌓아두면 원래의 순서가 변하기 때문이다. (Reservation Station 등에서는 완료된 것은 Entry 삭제) 그러니, Reorder Buffer 에 명령어를 넣어두는 시점은 초기에 Reservation Station 으로 명령어를 넣는 시점과 정확히 같아야 한다. 이렇게 Reorder Buffer 에 넣어두고 실행(연산)이 끝난 것들만 표시를 해두고, 처리가 종료 되면 표시가 된 놈들 중에서 Reorder Buffer 에서 차례대로 그 결과를 레지스터 등에 Commit 해주면 된다.