CPU Pipelining이 작동하는 원리
RISD 프로세서의 특징 중 하나인 파이프라이닝은 자동차 조립 라인과 매우 흡사하다.
프로세서는 다양한 명령어 단계에서 동시에 동작하기 때문에 더 많은 명령어들이 짦은 시간에 실행될 수 있다.
이것을 세탁소에 비유해보면 세척, 건조, 세탁물 접기가 필요한 4개의 더러운 세탁물이 있다. 우리는 첫번째 세탁물을 세탁기에 30분 동안 돌리고 그것을 40분 동안 건초하고 20분 동안 차곡 차곡 접을 수 있다. 그 후 두번째 세탁물을 세탁기에 넣고, 건조하고, 접고 이러한 과정을 반복한다. 그럼 우리가 오후 6시에 일을 시작했다고 한다면 자정이 되어서도 일을 마치지 못한다.
그러나 똑똑한 사람은 첫번째 세탁물을 접는 동안 두번째 세탁물은 건조를 하고 세번째 세탁물은 세탁기에 넣어 돌린다. 이렇게 하면 오후 10시 전에 일을 마칠 수 있다.
RISC 파이프 라인
RISC 프로세서 파이프라인은 이것과 매우 흡사하게 작동한다. 물론 각 단계가 하는 일은 다르지만 말이다. 여러 CPU는 각기 다른 명령어 단계를 가지고 있지만 기본적으로는 아래와 같은 단계는 무조건 가지고 있다.
- 메모리에서 명령어를 가져온다
- 레지스터를 읽고 명령어를 Decode한다.
- 명령어를 실행하거나 주소를 계산한다(유효한 주소 찾기)
- 데이터 메모리에 피연산자에 접근한다.
- 결과를 레지스터에 쓴다.
자세한 것은 이 글을 참고하라.
다시 위의 세탁물 예시를 보면 너는 세탁기에 넣고 돌리는 과정은 30분이 소요되는데 건조를 하는데는 10분 더, 40분이 필요하다는 것을 알아차렸을 것이다. 그럼 세탁기를 놀리고 난 후 축축해진 세탁물이 건조기에 넣기까지 10분을 기다려야 할 것이다. 이와 같이 파이프라인의 길이는 가장 시간이 많이 소요되는 과정(Stage)에 달려있다. RISC 명령어들이 CISC(Complex Instruction Set Computer) 명령어들보다 간소(간략, 짧다)하기 때문에 파이프라이닝에 있어서 RISC 명령어들이 더 효율적이다. CISC 명령어들은 길이가 다양한 반면 RISC 명령어들은 모두 길이가 같고 한 단계(operation)만에 가져올 수(fetch) 있다. 이상적인 경우 RISC 프로세서들은 한 Clock cycle만에 하나의 명령어를 끝낸다.
파이프라이닝의 문제들
그러나 실제로는 RISC 프로세서들은 한 명령어를 처리하는데 하나의 Clock cycle 이상이 필요하다. 데이터 의존성 혹은 분기 명령어로 인해 프로세서는 때때로 지연된다(stall).
데이터 의존성 문제는 한 명령어가 이전 명령어의 결과에 의존할 때 발생한다.
예를 들어보자.
add $r3, $r2, $r1
add $r5, $r4, $r3
more instructions that are independent of the first two
이 예에서 첫번째 명령어는 레지스터 r1과 r2의 데이터를 더해서 레지스터 r3에 저장하라고 말한다. 우리는 이 명령어를 CPU 파이프라인에 넣었다. 그리고 두번째 명령어가 2번 째 단계(레지스터를 읽고 Decode)에 도착했을 때 프로세서는 레지스터 r3와 r4를 읽으려고 한다. 그런데 두번째 명령어 보다 한 단계 먼저 파이프라이닝에 있던 첫번째 명령어는 아직 세번째 단계(명령어를 실행하는, 더하기 연산)에 있기 때문에 결과를 아직 레지스터 r3에 쓰지 못했다. 그럼 두번째 명령어는 첫번째 명령어가 더하기 결과를 레지스터 r3에 쓸 때 까지 기다려야한다. 결과적으로 파이프라인은 지연(stall)되고 비어있는 명령어(bubbles)가 파이프라인에 들어간다. 이렇게 되면 이후 명령어들도 차례 차례 지연되게된다. 데이터 의존성은 짧은 명령어 파이프라인보다 긴 명령어 파이프라인에 영향을 준다. 이는 명령어 파이프라인이 길면 그 만큼 결과를 레지스터에 쓰는 단계도 뒤쪽, 멀리 있기 때문에 결과를 레지스터에 쓰기 까지 시간이 많이 소요되기 때문이다.
이 데이터 의존성 문제에 대한 MIPS의 해결책은 코드 재배열(Code reordering)이다. 위의 예제처럼 만약 이후에 오는 명령어(세번째 명령어)가 앞의 두 명령어와 관련이 없으면 그 명령어들은 첫번째 명령어와 두번째 명령어 사이에 배치해여 데이터 의존성으로 인한 파이프라인 지연을 막을 수 있다. 코드 재배열은 대개 컴파일러에 의해서 이루어지는데 컴파일러가 명령어들간 데이터 의존성을 확인하고 파이프라인 지연을 최소화하려 재배열을 한다.
아래와 같이 말이다.
add $r3, $r2, $r1
add $r6, $r7, $r8 // 이전의 첫번째, 두번째 명령어와 데이터 의존성이 없음
add $r5, $r4, $r3
more instructions that are independent of the first two
분기 명령어는 프로세서에게 다른 명령어의 결과를 바탕으로 다음으로 실행될 명령어를 결정하라고 말하는 명령어를 뜻한다. 만약 분기가 파이프라인 상에서 아직 끝나지 않은 명령어의 결과에 의해 결정된다면 분기 명령어는 간혹 문제가 된다.
예를 보자.
Loop :
add $r3, $r2, $r1
sub $r6, $r5, $r4
beq $r3, $r6, Loop
위의 예제는 프로세서에게 레지스터 r1과 r2를 더해 레지스터 r3에 그 결과를 쓰고 레지스터 r5에서 r4를 빼서 f6에 저장하라고 말한다. 만약 레지스터 r3와 r6의 결과가 같으면 프로세서는 “Loop”라고 이름지어진 명령어를 실행해야한다. 결과가 다를 경우 다음으로 오는 명령어를 그냥 실행하면 된다. 이 예제에서는 프로세서는 레지스터 r3와 r6가 아직 쓰이지 않았기 때문에 두 값이 같은지 아직 결정을 하지 못한다.
이때 프로세서는 r3, r6 값이 쓰일 때 까지 기다릴 수도 있다. 그렇지만 이 분기를 다루는 더 세련된 방식이 있다. 바로 분기 예측이다. ( 분기 예측의 좋은 예제는 이 글에서 볼 수 있다. )
프로세서는 분기 조건문의 결과를 예측하여 하나의 분기를 선택하여 그 분기로 명령어를 진행한다. 만약 그 예측이 틀린 경우 레지스터에 쓰인 모든 값들은 초기화 되고 파이프라인은 다시 옳은 분기를 가지고 명령어를 전개한다. 몇몇 분기 예측 방법들은 어찌 보면 진부해보이는(stereotypical) 행동에 의존한다. 반복문(loop)의 끝에는 대개 반복문의 시작으로 돌아가는 분기가 실행되기 때문에 분기 예측에서 90%의 경우 반복문의 시작으로 돌아가는 분기를 택한다. 90% 확률로 대개 반복문의 시작으로 돌아가기 때문에 어찌보면 반목문의 시작으로 돌아가는 분기를 분기 예측 결과로 선택하는 것은 어찌 보면 논리적이어 보인다.
분기 예측의 다른 방법은 조금 더 유연한데 유동 에측(dynamic prediction)을 사용하는 프로세서들은 각 분기의 결과를 기록해두었다가 후에 분기 예측에 사용하기도 한다. 이러한 프로세서는 분기 예측 때 90% 정도는 옳은 예측을 한다.
파이프라이닝의 발전
프로세서를 더욱 빠르게 만들기 위해 다양한 파이프라이닝 방법들이 고안되었다.
파이프라인을 더 많은 step으로 쪼개는 슈퍼파이프라이닝은 파이프라인 stage가 더 많은수록 각 stage의 길이가 짧아져서 파이프라인이 더욱 빨라진다는 점에서 착안하였다. 이상적인 경우 5단계의 stage를 가진 파이프라이닝은 파이프라이닝이 없는 CPU보다 5배 이상 빠르다. 8 Stage의 파이프라이닝은 5단계 파이프라이닝보다 더욱 빠를 것이다.
슈퍼스칼라 파이프라이닝은 여러 파이프라인들을 병렬적으로 가지고 있다. 프로세서 내부에 파이프라인을 여러개 가지고 있어서 여러 명령어들을 동시에 처리할 수 있다. RISC System/6000 CPU는 floating-point이냐 integer 값이냐에 따라 여러 갈래의 파이프라인을 가지고 있는데 만약 프로그램이 floating-point, intger 두 값을 모두 연산에 사용한다면 두 연산을 동시에 실행할 수 있다. 두 명령어 타입은 두개의 초기 Stage를(Fetch, Decode) 공유한다. 그러나 대개 슈퍼스칼라 파이프라이닝은 모든 파이프라이닝 Stage를 여러개 가지고 있는 프로세서를 뜻한다. 오늘날의 CPU들은 모든 파이프라인 Stage에서 2개에서 6개의 명령어까지를 동시에 처리한다. 그러나 위에서 말한 명령어의 의존성이 있는 경우에는 오직 하나의 명령어만 실행되기도 한다.
다이나믹 파이프라인은 지연(Stall)의 시점을 정하는 능력을 가지고 있는데 다이나믹 파이프라인은 Fetch, Decode, 그리고 5개에서 10개의 실행(Execute), Functional 유닛 그리고 commit 유닛으로 구성되어 있다. 각각의 실행(Execute) 유닛은 Reservation Station들을 가지고 있는데 이 Reservation Station은 피연산자들과 연산을 가지고 있는 버퍼로서의 역할을 한다.
Functional Unit들이 비순차적(out-of-order)으로 실행을 할 수 있는 반면 fetch, decode, commit 유닛들은 심플한 파이프라인 동작을 유지하기 위해 순차적(in-order) 동작한다. 명령어가 실행되고 결과가 계산될 때 commit 유닛은 그 결과를 언제 저장하는 것이 안전한지를 결정한다. 만약 지연(stall)이 발생하면 프로세서는 그 지연이 해결될 때까지 다른 명령어가 실행되는 것을 늦출 수 있다. 명령어를 동시에 실행(전개)하는 다양한 유닛들의 효율성이 더해져서 다이나믹 파이프라인은 매력적인 대안이 되고 있다.
references : https://cs.stanford.edu/people/eroberts/courses/soco/projects/risc/pipelining/index.html