비순차 프로세서 파이프라인 (Out-of-order Processor Pipeline)의 핵심기술 (1)

비순차 실행은 명령어 수준에서 병렬성(Instruction Level Parallelism)을 찾아서 이를 순차적이 아닌 비순차적, 즉 병렬적으로 처리할 수 있도록 한 기술을 말합니다.
그러면, 큰 그림에서 이러한 비순차적 명령어 처리를 하려면 어떤 기술들이 필요한지 살펴봅시다.
이를 위해 비순차 실행에서 필요한 기술의 키워드들을 한번 나열해볼까요 ?

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

명령어 윈도우(Instruction Window)

프로세서 파이프라인에서는 명령어 처리가 물흐르듯이 스트림으로 처리됩니다. 이러한 명령어의 스트림 속에서 각 명령어들의 의존 관계를 분석해야하는데, 하나하나의 명령어를 순차적으로 각개격파하면 앞뒤 관계를 따져야하는 의존성 검사는 수행하기 어려울 것입니다.
그래서, 필요한 것이 명령어 윈도우(Instruction Window)개념입니다. 명령어 스트림 속에서 일정 숫자만큼의 범위 내에서 ILP 를 검사하여 비순차적으로 처리할 수 있어야 합니다. 즉, 명령어 윈도우의 가장 오래된 명령어부터 약 100 여개(시스템마다 다름) 정도의 명령어 범위 내에서 의존성 검사를 하여 처리합니다. 처리가 끝나면 가장 오래된 명령어가 윈도우에서 빠지고 동시에 새로운 명령어 하나가 추가되어 같은 과정을 밟습니다. 이 100 이라는 숫자가 명령어 윈도우의 크기를 말합니다.
명령어 윈도우라는 것은 개념적인 것이고, 그 실체는 아래에서 이야기하게될 Register Renaming, Reservation Station, Reorder Buffer 들이 모두 어우러져서 그러한 개념적 명령어 윈도우의 역할을 하는 것이라고 보면 되겠습니다.
즉, 아래와 같이 간단히 설명될 수 있겠네요.

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

우리는 이러한 명령어 윈도우 내에서 지지고 볶기 위한 기술들을 이해해야 비순차 실행(Out-of-execution)을 제대로 이해할 수 있습니다. 이러한 기술들이 가짜 의존성 제거를 위한 Register Renaming, Reservation Station 을 이용한 명령어 동적 스케줄링, 순차적 완료를 위한 Reorder Buffer 입니다.

가짜 의존성 제거 : Register Renaming

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

add r1, r1, #5    ->    add F1, r1, #5  (가)
add r2, r1, #4    ->    add F2, F1, #4  (나)
add r1, r2, #3    ->    add F3, F2, #3  (다)  @ r1 은 (가)와 의존성 없으므로 F3 으로 변경
add r1, r3, #2    ->    add F5, F4, #2  (라)  @ (가)와는 의존성 없으나 (마)와 의존성 존재 
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 만 기다리고 있으면 되겠네요. 그리고, 그렇게 기다리던 operand 가 준비되면 곧 바로 실행장치(Execution Unit)에게 계산하라고 던져주면 될 것입니다.
이렇게 주구장창 operand 를 기다리기 위해 눌러앉는 곳이 Reservation Station 이라는 Queue입니다.
Reservation Station 에 눌러 앉은 명령어는 두 가지 핵심 작업을 합니다.

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

Wake-up 작업은 어떤 선행 연산이 끝나서 operand 가 준비가 됐는데, Reservation Station 에서 기다리는 어떤 명령어가 이 operand 를 기다리고 있었나 찾는 것을 말합니다. 이것을 찾으려면 매번 Reservation Station Queue 에 있는 명령어들이 필요로 하는 Operand 들을 모두 체크해봐야하겠죠. (이 작업이 복잡하고 부하가 많아서 병목 지점이 됩니다.)
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 으로 명령어를 넣는 시점과 정확히 같아야 합니다. 즉, 순차적으로 들어온 명령어를 Reservation Station 으로 밀어넣을 때 Reorder Buffer 에도 일단 같이 넣어줍니다.
이렇게 Reorder Buffer 에 넣어두고 실행(연산)이 끝난 것들만 표시를 해두면 되겠지요. 그리고, 그렇게 끝나서 표시가 된 놈들 중에서 Reorder Buffer 에서 제일 오래된 놈은 빼내서 그 결과를 레지스터 등에 차례로 Commit 해주면 될 것입니다.
이것이 Reorder Buffer 의 핵심 기능이라고 할 수 있습니다.

이제 위의 핵심기술에 대한 이해를 바탕으로 비순차 프로세서의 파이프라인을 그림으로 표현해 보았습니다. 위의 내용을 읽고 그림을 보면 아래쪽 Store Buffer 나 Cache 쪽을 제외하고 중간 위쪽의 것들은 확연히 이해가 갈 것입니다.
Store Buffer 에 대한 내용은 Cache 와 함께 다루어야하기 때문에 다른 포스팅으로 추가로 올려야할 것 같네요. 그림에 대한 좀더 자세한 설명도 별도의 포스팅으로 마련하겠습니다.