[ 컴퓨터 구조 ] 18. Hazard

Hazard : 다음에 실행되어야 하는 명령어가 실행될 수 없는 상황

 

그에 관한 원인은 다음 3가지가 있다.

 

1. Structural Hazard

: 하드웨어가 한 번에 2가지 일을 할 수 없기 때문에 발생한다.

( 화장실 칸이라고 생각하면 됨. 같이 사용하는 건 절대 용납 X )

( 대신 물내리고 나오는 순간에 들어가는 건 가능 )

 

예)

- Multi CLK Cycle에서는 Mem이나 Adder가 하나만 있어도 문제가 없다. (동시에 작동할 일 X)

 

- Pipeline에서는 같은 시간동안 일을 하는 곳이 있기 때문에

  하나의 하드웨어에 접근하는 시간이 겹치면 Hazard가 발생한다.

 

 

Mem과 Adder가 하나씩만 있다면 표시된 부분에서 같은 하드웨어를 사용해야한다.

 

 

→ 해결법 : 하드웨어를 분리한다. 

      ex) Inst Mem / Data Mem , PC 전용 Adder / 연산 전용 Adder

 

메모리는 Data / Inst 용으로 나누고

Adder는  PC값 /  연산용으로 나누고

Register File은 Write / Read 영역을 나누어서 동시(?)에 쓸 수 있게 한다.  

 

 

 

 

---

2. Data Hazard

 

 : 이전 명령어와 현재 명령어의 Dependency가 있을 때

  →  이전 명령어의 결과가 구해져야 현재 명령어를 실행할 수 있기 때문에 Hazard 발생

 

 

sub의 결과는 CLK cycle 5일 때 2번 reg에 업데이트가 되는데

and가 그 값이 필요할 때는 CLK cycle 3일 때이다.

 

sub의 결과값을 갖고 and연산을 해야하는데 그 값이 아니라 이상한 값을 가지고 and연산을 함.

 

 

---

추가 예시)

 

 

ADD의 결과가 1번 레지스터에 들어가기 전에

SUB에서 1번 레지스터 값을 사용한다.

 

사용자 목적에 맞추려면 1의 결과를 이용하여 SUB를 하는 것인데

그렇지 않게 돌아가게 된다.

 

• 해결법 : 뒤에 따라오는 명령어의 실행을 늦춘다. = Stall

 

Stall 구현법 :

1. Freezing the pipeline
2. (Internal) Forwarding
3. Compiler scheduling

 

Freezing

 

방금 예시에서는 이렇게 2CLK stall 하여

ADD의 결과가 Write된 다음 SUB에서 Read하게 만든다.

 

 

이 예시도 마찬가지로 LW의 결과가 Write된 다음 그 값을 SUB에서 가져가 사용한다.

 

---

Forwarding

 

결과값이 Rd에 들어가는 건 WB stage이지만, LW제외 다른 명령어들의 결과값이 언제인지 알 수 있는 건 EX stage이다.

(LW는 MEM읽고 나와야 알 수 있음)

 

→ 따라서 그 결과를 다음에 오는 명령어에게 알려주고 다음 stage로 넘어간다면

   Stall = Frezzing(줄이거나) 없이 진행할 수 있다.

 

비유하자면 라면공장에서 라면 끓여 먹을거면 포장 굳이 안 해도 됨

그냥 면이랑 스프 만들어지면 바로 주방 가져감,

=레지스터에 안 넣어줘도 됨 그냥 날것으로 줘도 된다 이말이야

 

 

 

 

주황색 줄이 값을 넘겨주는 거다. 우린 그냥 이론만 알자 어떻게 구현하는지는 알기 힘들다고 하신다.

 

EXE stage가 끝나고 그 다음에 가기 전에 뒤에 오는 명령어에 넘겨주는 모습~!

 

- and 명령어에서 2번 Reg값을 읽었지만, 그 값을 사용하지 않고, 앞 Inst에서 pass받은 값을 사용하는 모습~!

 

  reg 2번에 값이 업데이트 되기 전 : 읽더라도 그 값이 아닌 pass받은 값 사용

   "              "                  "         " 후 : 2번 Reg값 사용 

 

Forward 관련해서는 이렇게 생겼음. 그냥 그렇다고 알기만 하면 될 것 같다.

 

---

Compiler Scheduling

 

 

이와 같은 명령어는 Data hazard가 발생한다.

따라서 Compiler가 중간 순서에 개입을 한다.

 

1) NOP

 

이렇게 $1에 값이 들어갈 때까지 기다렸다가

그 주소의 값이 유효해졌을 때 다음 명령어를 실행한다.

 

2) Rearrange (NOP도 아깝다 할 때 사용)

 

 

ADD와 SUB 사이에 결과,Dependency에 영향을 주지 않을 명령어들을 먼저 넣어서

NOP 대신 이따가 수행했어야 하는 명령어를 사용한다.

 

 

 

---

 3. Control Hazard

 

Pipeline 특성상 branch 판단을 하고 행동으로 옮길 때까지 뒤에 작업들이 따라오며 수행된다.

 

하지만 branch를 한다면 그 따라오며 수행했던 것들이 낭비가 되기때문에 Hazard라고 판단한다.

 

 

- 40번 주소에 있는 beq 명령어가 Branch 하는 시점은 CC4 가 끝난 이후이다.

 

- CC4까지 가는동안 44,48,52 명령어가 실행되고 있고 그 이후에는 branch가 되기때문에 그 명령어들은 소용이 없어진다.

 

- 따라서 44,48,52는 Flush되어야 한다.

 

→ 이러한 낭비도 Hazard로 판단한다.

 

 

BEQ가 CC4 이후에 정해지는 이유...

CC 4에 끝나는 이유

 

해결법

1. Stall
   → 문제가 해결될 때까지 실행 중지
   
   
2. Optimized branch processing
   → 손실을 최소화하는 방법 
   → Branch 에서 Hazard가 발생하면 3CLK을 낭비하게 됨.
   → 3CLK 손실을 1CLK으로 바꿈
   
   
3. Branch Predicition
   → Branch 가 될 지될지 안 될지 먼저 예측하여, Branch 될 데이터만 가져오기
   
   

 

1) Stall

 

해당 Inst가 Branch 명령어면, 그 다음 명령어는 Fetch만 하고 branch 여부가 확인 될 때까지 stall한다.

 

(그 밑에 3Cycle그건 아직 우리가 볼 단계가 아니라고 하심)

 

 

 

 

2) Optimized branch processing

(김칫국 마시며 준비하기)

1. Branch 되는지 미리 좀 확인하기!

  →  Adder 하나 땡겨와서 Branch 확인 일찍하기

 

2. Branch target address 미리 계산하기

  → 비교기를 하나 Register file 뒤에 넣는다. 여기에서 반응이 오면 beq 하는거니까

 

 

즉, 브랜치 할지 안 할지 미리 알아내고

할 수도 있으니 Branch target address도 미리 계산해두자.

 

 

 따라서, Execution 에서 하는 일들을 ID로 조금 땡겨오자.

 

●  Branch Target address 계산용 Adder 가져오기.

 

●  Beq 조건에 맞는지 비교만 하는 Compare 하드웨어하나 Reg file 뒤에 놓기 

 

파란색으로 표시한 부분들의 역할이 ID단으로 넘어가야한다.

 

 

넘어간 모습

 

 

 

이렇게 하면 방금 막 fetch된 Inst만 같이 실행되고 있으므로 그건 Flush

+ ID단에서 Exe stage로 넘어감.

  그렇다면 Branch가 진행되었을 때,

   명령어는 EX단에 하나(branch 명령어), IF단에 하나(새로 branch해서 가져온 거).

    ID단에만 비어있다 => 하나만 Delay된 형태로 남는다. 

 

 

3) Branch Prdiction

 

Branch 하지 않을 것이라고 가정하고 가는 것.

그렇다면 그 뒤 명령어들을 그냥 진행한다.

 

가정이 틀렸을 땐 Bubble (= flush) 을 집어넣고, branch 주소에 맞게 fetch한다.

 

그렇게 가정하고 가면 아무 Delay없이 진행되고

가정이 틀렸다고 해도 1 CLK의 손해만 본다.  

 

 

주로 어떻게 예상할지 정해져있는 양식이 있다.

 

1) 절대 branch X

2) 절대 branch O

3) OP code에 따라 , Beq면 절대 branch X / Bne면 절대 branch O

 

 

---

 

State diagram으로 하는 방법도 있다.

 

prediction과 결과가 달라지면 prediction state를 바꾼다.

 

초기값 = predict taken

branch taken > 상태 유지...

branch not-taken >  state가 not-taken으로 넘어감.

 

 

초기 predict값에서 바뀌기 위해서는 두 번 연속으로 같은 값이 나와야 한다.

 

주로 이런 방법은 몇 백만번 돌아가는 반복문에 있는 BEQ에 효과적이다.

10000번 중에 한 두번 BEQ에 들어간다면 현재 상태에 있다가 state가 변하는 조건이 되었을 때만 살짝 바꾸고

다시 돌아올 수 있기 때문이다!

 

Loop 위에 또 다른 Loop하나가 있었다고 생각하자.

 

반복문이 돈다는 것은 S가 계속 1인 상태였다는 것.

그리고 우리가 원래 갖고 있던 Loop에 들어올 때는 0인 상태로 들어온다.

 

그리고 BEQ를 만나고 S는 0에서 1로 다시 바뀐다.

그렇게 반복문을 돌 때는 1이었다가 조건이 되면 branch를 하면서 0으로 변한다.

 

 

Loop의 개수 = S가 틀린 횟수 = S가 변하는 횟수 = S가 0이 되는 횟수

 

---

 

모든 Hazard는 Stall( = Frezze, Delay )로 해결된다.

 

 

(출처)

한동대학교 용환기교수님 - 컴퓨터구조