Hazard

Data Hazard

아래와 같이 연속으로 같은 레지스터에 값을 쓰고 읽는 경우 data hazard가 발생한다.

WB에서 레지스터에 값을 저장해야 ID에서 저장된 값을 읽어올 수 있기에,

2 cycle 동안 명령어를 정지시키고 실행한다.

참고로 3 cycle을 멈춰야 하는게 아닌가 할 수 있는데, flip-flop이라 하더라도,

전자가 채워지는 시간을 고려하면 2 cycle에도 가능하다고 한다...

 

하지만 이렇게 명령어를 정지하게되면(nop) 성능상에 문제가 생길 수 밖에 없다.

따라서 회로상으로 명령어의 연산 결과를 바로 가져다 쓰도록 구현한 forwarding 기법이 등장했다.

 

하지만, 데이터 로드를 수행하는 명령어를 수행한 경우에는?

ID에서 가져오고자 하는 레지스터의 값은 MEM단계가 끝난 뒤에나 받을 수 있을 것이다.

따라서 이 경우에는 forwarding 기법을 사용하더라도 1 cycle을 정지해야 한다.

 

만약 lw에서도 정지하고 싶지 않을정도로 성능 향상을 꾀하고 싶다면?

명령어의 실행 순서를 바꿔주면 된다.

레지스터를 연속으로 사용할 일 없게 명령어의 순서를 적절히 배치하면 stall(정지)횟수를 줄일 수 있다.

 

- Double data hazard

위와 같은 상황에서는 2, 3에서 동시에 forward가 일어날까?

이런 경우에는 이전에 일어난 forward (2번)는 무시하게 된다.

즉, 가까운 곳(1, 3)이 forward되지 않아야 먼 곳(2)가 forward 할 수 있다는 조건이 추가로 붙는다.

(기본적인 forward 조건은 아래에 바로 나옴)

 

- Detecting forward

그렇다면, 하드웨어가 forwarding을 하기 위해서는 forwarding이 필요하다는 신호를 보내야 하는데,

이를 어떻게 감지할 수 있을까?

아래와 같은 조건이 forwarding이 필요함을 감지하는 상황이다.

 

1. EX/MEM.RegisterRd = ID/EX.RegisterRs
   EX/MEM.RegisterRd = ID/EX.RegisterRt
2. MEM/WB.RegisterRd = ID/EX.RegisterRs
   MEM/WB.RegisterRd = ID/EX.RegisterRt

 

이를 회로로 구현하면 다음과 같아진다.

Forwarding Unit이 00 신호를 던지면 forwarding 없이 평상시대로 하면 되지만,

10 신호를 던지면 EX/MEM에서 forwarding이 일어난 것이고,

01 신호를 던지면 MEM/WB에서 forwarding이 일어난 것이다.

 

- Detecting Load-use hazard (stall condition)

연산 문제는 forward만으로 해결 가능하지만, lw 명령어로 읽어오는 경우에는 반드시 1번의 stall이 일어난다고 했었다.

그렇다면 회로에서 진행 중인 명령어를 무시해버리고 stall을 해줘야 하는데,

Load-use hazard는 어떻게 감지할 수 있을까?

아래와 같은 조건이 Load-use hazard를 감지하는 상황이다.

• ID/EX의 명령어가 lw 명령일 것(MemRead control이 발생할 것)
• ID/EX.RegisterRt = IF/ID.RegisterRs
  ID/EX.RegisterRt = IF/ID.RegisterRt

 

lw 명령어를 해석이 되면 해당 명령어는 ID/EX 레지스터에 있다는 뜻이고,

다음 줄에서 해당 레지스터를 접근하는지 확인하려면 이전 스테이지인 IF/ID 레지스터를 통해 확인해야 한다.

 

- Stall the pipeline

위에서는 간단하게 stall하면 된다. 라고 했지만, 실제로는 어떻게 구현되야 명령어를 무시할 수 있을까?

아래와 같은 처리를 해줘야 명령어를 무시할 수 있다.

 

1. ID/EX 레지스터의 Control 시그널을 강제로 0으로 바꾼다.
   이렇게 해야 EX, MEM, WB stage에서 아무런 기능을 하지 않도록 할 수 있다.
2. PC, IF/ID 레지스터의 업데이트를 막는다.
   이렇게 해야 stall 걸린 명령어가 다음 cycle에서 다시 실행된다.

이를 회로로 구현하면 다음과 같아진다.

 

Control Hazard

명령어 실행 중 branch가 일어날 경우,

하드웨어는 명령어가 어디로 점프하는지 미리 알아낼 방법이 없기에 문제가 발생할 수 있다.

원래대로라면 ALU 연산이 끝나야 두 레지스터의 값이 같은지 다른지 알 수 있고,

이를 바탕으로 jump가 일어나게 된다.

하지만, MIPS에서는 ID단계에서 작은 연산장치 하드웨어를 추가함으로써

ID stage에서 두 레지스터의 값을 비교하여 jump할 수 있다.

따라서 원래대로라면 2 cycle이 정지되어야 하겠지만 이를 1 cycle로 줄일 수 있었다.

 

하지만, 그림에서도 알 수 있듯이 반드시 1번 이상의 stall이 발생하기에 if문 같은 분기문을 자주 쓰면

성능 하락의 큰 요인이 된다.

하드웨어 개발자도 이 사실을 아는지 성능 하락을 완화할 장치를 개발했다.

바로 Branch predicion이다.

MIPS는 branch의 조건이 맞든 틀리든 일단 다음 명령어를 가져와서 수행한다.

만약 branch가 일어나지 않으면 그대로 수행하면 된다.

만약 branch가 일어난다면, 수행하고 있던 다음 줄의 명령어를 버리고, bubble 처리한다.

그리고 jump한 곳의 명령어를 가져와 수행하게 된다.

 

- Data hazard for branches

branch 명령을 사용할 때도 data hazard가 발생할 수 있는데, 각각의 상황을 살펴보고 해결법 또한 알아보자.

ALU연산이 2, 3 명령어 앞에 있을 때는 forwarding으로 해결 가능하다.

 

ALU연산이 바로 앞에 있거나, Load명령이 2 명령어 앞에 있을 때는

forwarding + 1 stall이 필요하다.

 

Load명령이 바로 앞에 있을 때는 forwarding + 2 stall이 필요하다.

 

- Dynamic branch prediction

Branch predicion buffer을 두어 이전 명령어에 대한 결과를 저장해서

동적으로 다음으로 오는 branch가 yes일지 no일지 예측하는 방법이다.

 

* 1-Bit predictor

0, 1로만 history를 저장하기 때문에 이전 결과를 그대로 따라가는 방식으로 예측한다.

이런 경우에는 한 outer cycle이 도는 동안 inner branch에서 두 번의 예측이 실패하게 되는 경우가 생긴다.

• 1~n-1까지 계속 돌음
• n에서 빠져나감 (예외 발생: 계속 돌다가 갑자기 빠져나감)
• 다음 루프에서 1에서는 다시 돌음 (예외 발생: 전에는 빠져나갔는데 이젠 다시 돌음)
• ...

 

* 2-Bit predictor

두 번 연속 예측이 틀려야 예측을 바꾼다.

 

- Exception

예외도 일종의 branch로서 작동하게 되는데, 예외가 발생하면 다음과 같은 처리를 한다.

 

1. Exception 발생
2. PC값 저장
3. 어떤 exception인지 파악 및 저장
4. Exception handler 또는 내장된 handler로 jump
5. Exception 처리
6. 재개 가능한 exception의 경우 PC로 복귀
   재개 불가능한 경우 강종 및 버그리포트

 

Pipeline을 사용할 때는 아래와 같은 상황을 유의해야 한다.

• exception 발생시 관련 레지스터 값 업데이트 방지
• exception 발생 이전에 실행 중이던 명령어는 완수되어야 함 (별도의 제어가 없다면 알아서 완수될 것)
• exception 발생 이후에 실행 중인 명령어는 무시해야 함

 

회로 그림으로 살펴보자.

4c 라인의 add 명령어 수행 중 exception이 발생한 경우 4c-add, 50-slt, 54-lw 명령어를 flush 해줘야 한다.

그럼과 동시에 exception handler의 주소를 PC의 입력으로 넣어줘야 한다.

 

그렇게 해야 비로소 exception handler가 다음 사이클에 잘 동작하게 된다.

 

정리

결국 Pipeline으로 동작하는 회로에서 오른쪽에서 왼쪽으로 신호가 전달될 때 Hazard가 발생할 수 있다.

발생 시점은 ID에서 사용할 레지스터의 값이 반영이 안된 상황에서 발생한다.

이 점을 유념하고 코딩하면 좋겠다.