[컴퓨터 구조] 18. Pipeline MIPS (2) - Hazard

Pipeline 의 표현

 

IF, ID, EX, MEM, WB 다섯개 stage를 위 그림과 같이 표현해보자.

이제 모든 명령어는 5개 단계를 거쳐야 실행되며, 만약 각 단계를 처리하는데 1cycle이 소모된다면, 총 5사이클을 필요로 한다.

얼핏보면 안좋은 것 같지만, 이렇게 하면 1 cycle의 주기를 짧게 가져갈 수 있고, 2번째 명령어부터는 1 cycle만에 명령어를 실행할 수 있기 때문에 전체적인 throughput은 매우 크게 향상된다.

 

이때 왼쪽 반을 색칠한 것은 '그 단계에서 전반부에 데이터를 쓰는 행위를 한다' 라는 것을 의미한다.

반면 오른쪽 반을 색칠한 것은 '그 단계에서 후반부에 데이터를 읽는 행위를 한다' 라는 것을 의미한다.

다 색칠한 경우에는 색칠한 자원을 사용하고 있다는 의미이다.

 

위 그림에서 ID 단계의 네모와 WB 단계의 네모는 모두 레지스터 파일을 의미한다.

이때 색칠된 곳 반대편을 점선으로 표시했는데, 이는 이 두 단계에서 가리키는 레지스터 파일이 같은 레지스터파일임을 의미한다. 각자 반쪽씩 쓰고 있는 것이다.

 

예를 들어 lw 명령어의 경우,

IF 단계에서는 PC가 가리키는 주소로부터 Instruction Memory 안에 있는 명령어를 '읽는다'

ID 단계에서는 명령어를 해석하고, 전반부에는 아무것도 하지 않다가 후반부에 명령어가 가리키는 레지스터의 값을 '읽는다'

EX 단계에서는 ALU라는 자원을 사용하고 있으므로 ALU를 온전히 색칠했다.

MEM 단계에서는 lw 명령어의 경우 후반부에 메모리의 데이터를 '읽으므로' 오른쪽만 색칠한다.

WB 단계에서는 레지스터에 값을 써야하므로 왼쪽을 색칠했다.

 

add 명령어도 동일하지만, 메모리에 값을 읽고, 쓰는 행위를 하지 않기 때문에 색칠은 하지 않았다.

 

각 단계를 수행하는데 2ns 가 소모된다면 lw 명령어를 수행하는데는 10ns의 시간이 소모된다.

add 명령어는 2ns 만 추가로 소모하면 수행할 수 있다.

 

 

이제 이 그림을 기반으로 파이프라인으로 CPU를 설계할 때 만나게 되는 3가지 해저드를 정리해본다.

Hazard

해저드는 말 그대로 '위험' 이라는 뜻이다.

그렇다면 어떤 위험을 갖고 있다는 것일까?

파이프라인에서 해저드는 '다음 사이클에 다음 명령어를 시작할 수 없는 상황' 을 의미한다.

 

크게 Structure hazards, Data hazards, Control hazards 3가지가 있다.

 

Structure Hazard

구조적 해저드는 하나의 하드웨어에 동시에 접근하려고 할 때 발생하는 해저드이다.

위 그림과 같이 MIPS CPU가 메모리에 접근하는 port를 1개만 갖고 있다고 해보자.

 

 

Load 명령어와 Store 명령어는 MEM 스테이지에서 데이터에 접근해야하고

그때 IF 스테이지에서는 메모리에서 명령어를 가져와야 한다.

 

이때 하나의 메모리에 명령어와 데이터가 모두 들어있고, 데이터를 가져올 수 있는 통로 (port) 도 하나라고 한다면 IF 스테이지와 MEM 스테이지는 동시에 실행될 수 없을 것이다.

 

이와 같은 문제를 해결하려면 한 스테이지에서 사용하는 동안 다른 스테이지는 기다렸다가 그 스테이지의 사용이 끝나면 이어서 사용해야 할 것이다.

 

이와 같은 해결법을 stall (지연) 또는 bubble 이라고 한다.

또 다른 해결책은 위 그림과 같이 메모리에 접근하는 경로를 2개를 두는 것이다.

하나의 경로는 MEM 스테이지가 사용하고, 나머지 경로는 IF 스테이지에서 사용하도록 하면 구조적 해저드를 해결할 수 있다.

아니면 명령어를 저장하는 메모리와, 데이터를 저장하는 메모리 자체를 구분하여 둘 수도 있다.

 

보통 구조적 해저드는 이렇게 하드웨어 설계를 통해 해결한다.

(실제로 CPU는 외부 데이터 메모리와 1개의 포트로 연결되어있다. 하지만 구조적 해저드가 발생하지 않는데, 그 이유는 메모리와 CPU 사이에 캐시를 두는 디자인으로 이루어져있기 때문이다. 캐시는 명령어를 저장하는 캐시와 데이터를 저장하는 캐시가 구분되어 있어 구조적 해저드 문제를 해결한다.)

 

Data Hazard

데이터 해저드는 명령어를 실행할 때 필요한 데이터가, 그 직전 명령어의 실행 결과에 의존할 때 발생한다.

 

위 그림과 같은 상황을 보자.

s0 에는 처음에 0이 들어있었고, add 명령어를 통해 3과 7을 더해서 10을 저장하는 상황이라고 해보자.

sub 명령어를 실행할 때 프로그래머는 s0 레지스터에 이전 덧셈의 결과인 10이 들어있기를 기대할 것이다.

하지만 파이프라인을 보면 실제 add 명령어의 연산 결과인 10이 레지스터에 쓰이는 시점은 WB 스테이지이고,

그 다음 명령어에서 레지스터의 값을 읽어오는 시점은 그보다 2단계 이전인 EX 단계에서 읽어온다.

따라서 의도와 다르게 s0에 처음 들어있던 0이라는 값을 가져와서 그 값으로 sub 연산을 수행하게 된다.

 

이 문제를 피하기 위해서는 내가 원하는 데이터가 준비될 때까지 파이프라인이 2번 지연되어야 한다. (stall)

이렇게 2번 아무것도 안하고 지연되어 있다가 이후에 EX 단계부터 수행하게 되면 멀리서 봤을 때, 파이프라인 중간에 구멍이 슝슝 뚫린 모양으로 보일 것이다. 이를 가리켜 중간에 거품방울이 생겼다는 의미로 bubble 이 발생했다고도 한다.

 

하지만 이렇게 지연을 주게 되면, 문제는 해결할 수 있지만 sub 명령어를 실행하는 response time 은 2cycle만큼 늦어지고 이는 CPU 성능의 감소로 이어진다.

 

(나는 여기에서 ID 단계에서 데이터를 읽은 후에 (오른쪽 색칠) 2번의 버블이 진행되고 EX를 수행하면 문제가 발생하지 않을까 생각해서 ID 단계 이전에 2번 버블하고나서 ID부터 다시 수행해야 하는 것이 아닌지 교수님께 질문을 드렸다.

교수님의 답변은 내가 생각한게 이 그림상으로는 맞으나, WB 스테이지와 ID 스테이지에서 사용하는 레지스터파일은 동일하기 때문에, WB을 통해 값을 쓴 순간 EX에는 알아서 새로 쓰여진 값이 들어가기 때문에 문제가 없다. 레지스터 파일이 조합회로로 동작하기 때문에 가능한 일이다.)

 

 

따라서 사람들은 성능에 문제가 없으면서도 data hazard를 해결할 수 있도록 forwarding (또는 bypassing) 이라는 기법을 고안했다.

이 기법은 말 그대로 EX 단계가 실행된 이후, 그 값을 ID 단계와 EX 단계 사이로 바로 전달해서 stall 없이 연산한 값을 사용하도록 별도 패스를 만들어주는 방법이다. (즉 ALU에서 나온 값을 다시 ALU로 넣어준다.)

이렇게하면 WB 단계까지 기다리지 않고 다음 명령어가 필요로 하는 연산된 값을 가져다가 사용할 수 있다.

 

물론 항상 이 경로를 사용하면 안되고, 데이터 해저드가 발생했을 때만 이 경로를 사용해야 할 것이다.

이를 고려하여 회로를 수정하는 것은 뒤에서 따로 정리한다.

---

그런데 사실은 forwarding 만으로는 항상 stall을 피할 수 있지 않다.

다음과 같은 상황을 생각해 보자.

 

lw 를 해서 메모리에서 데이터를 가져온 뒤, 그 다음 명령어에서 바로 그 데이터를 피연산자로 연산을 수행하는 경우이다.

위와 같은 상황을 Load-Use Case 라고 한다.

 

이전 상황과 달리 Load - Use 케이스는 3번째 단계에서 감지할 수 없다. 세번째 단계에서는 사실 주소값 계산만 한 것이고, 4번째 스테이지를 가서야 실제로 WB하고 싶은 값을 알게 된다.

4번째 스테이지에서 그 다음 명령어는 EX 스테이지를 실행하고 있으므로 이때는 메모리에서 읽은 값을 포워딩하고 싶어도 이미 ALU가 작동하고 있어 포워딩을 하는 의미가 없다.

그래서 이때는 어쩔 수 없이 stall을 할 수 밖에 없다.

 

그래서 CPU에는 stall이 발생할 수 밖에 없음을 감지하고, 이를 처리하는 기능이 추가되어야 한다.

이렇게 하드웨어적으로 stlal이 일어날 수 밖에 없다는 것을 감지하고, 처리하는 것을 Hardware Interlock 이라고 한다.

(이 역시 나중에 MIPS 회로를 보면서 수정할 것이다.)

 

---

 

그런데 load-use  케이스는 사실 프로그램을 어떻게 짜느냐에 따라 발생하지 않을 수도 있다.

 

위와 같은 코드를 어셈블리로 작성한다고 해보자.

 

먼저 첫번째 경우, B, E를 lw 로 가져오고 그 값을 더해서 A를 구하여 저장하고,

다시 F 를 lw로 가져온 뒤 B와 더해서 C 값을 구하여 메모리에 저장하는 코드이다.

 

하나의 명령어를 실행하는데 5개의 cycle이 필요하고, 이후 실행하는 명령어에 대해서는 추가적으로 1개씩의 사이클이 필요하기 때문에, 5 + 1 + 1 + 1 + 1 + 1 + 1 = 11 cycle 이 기본적으로 사용된다.

 

그런데 위 상황에서는 t2 레지스터에 값을 lw로 가져온 직후에 add 명령어로 t2의 값을 가져와 사용하고 있다.

load-use 케이스가 발생한 것이다.

이때는 stall이 발생하므로 1cycle이 추가적으로 소모된다.

F 를 lw로 가져와서 B와 더하는 상황에서도 t4 레지스터의 값을 가져오자마자 바로 덧셈의 피연산자로 활용하기 때문에 stall이 한번 발생하여 1 cycle이 추가적으로 소모된다.

(위 이미지에서 빨간색 동그라미)

 

따라서 이 7개 명령어를 모두 실행하는데에는 11cycle + 2cycle (stall) =  13 cycle이 소모된다.

 

 

반면 명령어를 실행하는 순서를 바꿔서 일단 lw를 다 해두고 그 다음에 연산하고 저장하는 과정을 한다고 해보자.

이렇게 어셈블리 코드를 재배치해서 작성하는 경우에는 stall이 발생하지 않으므로 총 11 cycle 만에 모든 명령어를 실행할 수 있다.

 

이렇게 코드를 재배치해서 load-use 케이스를 해소하는 방법을 '코드 스케줄링' 이라고 한다.

물론 코드 스케줄링을 항상 적용할 수 있는 건 아니다.

프로그램에 따라 적용할 수 있기도, 없기도 하다.

 

그래서 위에서 말한대로 load-use 케이스를 감지해서 stall 하는 기능 (hardware interlock) 은 여전히 필요하다.

 

Control Hazard

제어 해저드는 분기 명령어와 관련이 있다.

 

위 그림에 나와있는대로 분기 명령어는 EX 스테이지 이후에 분기 조건이 참일 경우 분기할 주소값이 결정되고, 그 이후에 분기가 처리된다. MEM, WB 단계는 쓰지 않는다.

만약 분기하는 것으로 결정된다면 EX 단계까지 fetch, decode 했던 내용들은 실행되면 안되기 때문에 버리게 되고, 그 만큼 버블이 발생한다.

위 예시에서는 만약 beq 명령어의 비교 결과가 참이라면, add, sw 명령어는 실행되면 안되기 때문에 버려지고, L1 레이블이 있는 sub 명령어부터 실행하게 된다.

그리고 분기 명령어의 EX 스테이지 이후의 Fetch 단계에서는 분기 결과에 따라 다음 명령어를 가져올 주소값이 달라진다.

 

이 예시를 통해 branch 명령어를 만나는 경우, 조건이 참인지 확인하고, 분기 주소를 계산하려면 EX 스테이지까지 가야하고, 만약 분기를 하게 된다면 2번의 버블이 발생한다는 것을 알 수 있다.

 

그런데 이렇게 분기를 할 때마다 2번의 버블이 생성되는 것은 성능 관점에서 좋지 않다.

그래서 버블의 개수를 2개에서 1개로 줄이는 시도로, ID 단계에서 분기 주소를 계산하고 분기 여부를 알 수 있도록 새로운 하드웨어를 ID 단계에 넣는 것이다.

 

그러면 이 그림과 같이 1번의 버블만 발생하므로 성능 면에서 기존보다 이점을 가져갈 수 있다.

물론 이점만 있는 것은 아니다. 이를 위해 새로운 하드웨어를 추가하였으니 트레이드 오프가 있는 것이다.

 

그런데 여기에서 끝나지 않고, 많은 CPU들은 'delayed branch (지연 분기)' 라는 기법을 적용하여 stall의 발생 횟수를 줄인다.

이 기법은 분기 명령어의 실행 이후에 실행하는 명령어는 분기를 하든 안하든 항상 실행될 수 밖에 없다는 것을 인정하고, 이 위치 (delay slot 이라고 부른다.) 에 분기와 상관없이 실행되어도 되는 명령어를 넣어서 실행하자는 테크닉이다.

 

 

 

예를 들어 위 그림과 같은 코드가 있다고하자.

이 코드를 그대로 어셈블리로 옮기면 아래와 같이 된다.

 

분기 명령어 이후에는 분기여부와 상관없이 명령어가 실행된다. 이때 실행할 명령어가 없으므로 nop 라는 의미없는 명령어를 넣는다.

그리고 그 이후에는 분기 하지 않을 경우 실행할 명령어와 분기할 경우 건너갈 주소를 표기하였다.

 

그런데 bne 명령어 이전에 add 명령어는 분기 여부와 상관없이 항상 실행되는 명령어이다.

따라서 이 코드를 아래와 같이 작성해도 똑같이 기능한다.

 

이렇게 작성하면 전체 명령어 실행 개수가 하나 줄어들었으므로, 전체 프로그램의 throughput은 증가한다.

이와 같은 기법을 delayed branch 라고 부른다.

 

이와 관련하여, 이전에 jal 명령어를 사용할 때, 경우에 따라서는 PC + 4 가 아니라 PC + 8 이 return address 로 지정되는 것을 이해할 수 있을 것이다.

PC + 4 는 delay slot 으로서 항상 실행되기 때문에, 점프 이후에 돌아왔다면 PC + 8부터 이어서 실행하면 되는 것이다.

(싱글 사이클 MIPS라면, PC + 4 를 쓰는 것이 맞을까?)

---

 

분기와 관련하여 실제 CPU는 지연분기 외에도 `branch prediction (분기 예측)' 이라는 기법을 추가적으로 이용한다.

지금까지 얘기했던 내용의 결론은, 분기 여부를 알아내는 시점을 당겨서 버블을 줄이고, 어쩔 수 없이 발생하는 버블은 인정한 채, 그 위치에 다른 명령어를 채울 수 있다면 채우자는 것이었다.

 

지금까지 했던 이야기는 지금 보고 있는 것처럼 스테이지가 5개일 때는 어느 정도 괜찮지만, 실제 CPU 처럼 스테이지가 10개를 넘어가게 되면 분기 결과를 알게되는 타이밍도 상대적으로 느려지게 된다.

 

이 타이밍, 그러니까 분기 여부를 알기까지 걸리는 스테이지의 숫자가 늘어나면 늘어날수록 stall 페널티는 증가한다.

따라서 지금까지 말한 기법에만 의존하지 않는다.

요즘에는 거의 무조건 분기 여부를 예측해서 진행한다.

 

지금까지는 분기 여부를 알고나서 행동하겠다, 다만 분기 여부를 조금 더 빨리 알아차려 보자는 내용이었다면, 요즘은 100% 맞을지는 몰라도 한번 어디로 분기할 지 예측해서, 그 위치의 명령어를 delay slot에서 미리 실행하자는 방향으로 설계한다. 타이밍상 예측하는 것이 정확하게 알아차리는 것보다는 빠를테니 지금은 다 분기 예측을 사용한다.

 

그런데 이 방법은 꽤 복잡하고 어렵다. (이것만으로도 대학원에서 연구 주제라고 한다..)

컴퓨터 구조를 연구하는 연구실에서는 95%정도는 예측에 성공한다고 하는데, 5%의 확률로 틀릴 때는 Flush를 한다.

지금까지 실행해둔 명령어를 그냥 버리는 것이다.

stall 과는 다르다.

stall은 애초에 실행을 하지 않고 가만히 기다리는 것이고 (멈춤의 의미), flush는 일단 실행해뒀다가 나중에 파이프라인에 들어있는 내용을 비워내는 것이다. (무효화)

 

flush 역시 전체적인 throughput에는 방해가 되는 요소이지만, 요즘 CPU는 flush를 최소화 하기 위해 분기 예측 성공률을 높이고자 신경을 많이 쓴다. 이 성공률을 1%, 2% 높이는 것이 성능 향상에 도움이 많이 된다.

(과거 통계치, 인공지능까지도 써서 예측한다..)

 

하지만 분기 예측은 그것만으로도 꽤 어려운 주제이기 때문에 지금은 매우 간단한 분기 예측으로 살펴보고자 한다.

바로 무조건 분기 에측의 결과는 거짓이라고 예측하는 것이다.

이렇게 했을 때 쉬운 점은, 그냥 delay slot에는 분기 명령어 다음에 실행할 명령어를 가져오면 되기 때문에 지금 구조와 거의 유사하다.

지금 구조에서 만약 분기 예측에 실패했을 경우 flush 하는 하드웨어만 추가하면 된다.

 

 

따라서 만약 분기 예측에 성공(분기 여부가 거짓) 했다면, 다음 명령어를 그대로 실행한다.

 

 

만약 분기 예측에 실패했다면 그 다음 명령어들을 모두 비워낸다 (flush). 그러면 통으로 한 줄의 버블이 생긴다.

 

---

파이프라인에 대해 간단하게 정리하자면 파이프라인 기법은 전체적인 명령어 실행 성능 (throughput) 향상에 크게 기여하였다. 하지만 매 사이클마다 새로운 명령어를 가져와서 실행할 수 없는 3가지 해저드가 있었고, MIPS의 ISA는 이 해저드를 극복하여 쉽게 파이프라인을 구현하는데 유리한 구성을 갖고 있다.