4. Data Hazard

Data Hazards

뒤의 instruction이 앞의 instruction의 결과를 사용할 때 발생한다.

• EX hazard : 바로 앞의 instruction의 결과를 사용할 때
• MEM hazard : 2번째 앞의 instruction의 결과를 사용할 때
• Load-use data hazard : 바로 앞의 instruction이 lw인 경우

 

---

EX Hazard and MEM Hazard

원인

Forwarding이 없을 경우 instruction의 결과는 WB가 끝나야 update된다.

그렇기 때문에 앞의 instruction의 연산 결과를 바로 뒤의 instruction에서 사용할 수는 없다.

 

Data hazard에서는 값을 write 한 후 read해야 하는 RAW(read after write) data dependency가 발생한다.

 

아래 예시에서 2번째 cycle에 바로 sub가 실행되면 3번째 cycle에서 register의 값을 읽어야 하지만, 아직 add에서의 연산 결과가 register file에 update 되지 않았다. 그렇기에 불가능하다.

마찬가지 이유로 3번째 cycle에서 sub를 실행하는 것도 안된다.

따라서 2개의 bubble이 들어가야 한다. 즉 2개의 cycle의 손실을 야기한다.

 

 

 

해결

5-stage pipeline에서는 3개의 instruction 이상 떨어지면 data hazard가 발생하지 않는다.

그러나 이는 성능의 손실을 야기하기 때문에 forwarding을 이용하여 해결한다.

 

Data hazard는 2 cycle 동안 발생하므로, 현재 실행되는 instruction을 기준으로, 바로 전에 실행된 것과 두 번째 전에 실행된 것을 확인해야 한다.

• 바로 전의 instruction의 결과가 필요한 경우 : EX/MEM register에서 가져다 씀
• 두 번째 전의 instruction의 결과가 필요한 경우 : MEM/WB register에서 가져다 씀

 

ALU 연산 자체는 EX stage에서 완료되기 때문에 가능한 것이다.

이 결과가 register에 쓰이기 전에 pipeline register에서 가져와서 사용한다.

 

EX Hazard vs. MEM Hazard

EX hazard는 바로 앞의 instruction에서 값을 받아오는 경우이고,

MEM hazard는 2번째 앞의 instruction에서 값을 받아오는 경우이다.

 

lw instruction에서 data memory의 값을 읽어오는 것은 MEM stage에서 끝난다.

따라서 EX hazard가 발생한 경우, 바로 앞의 instruction이 lw라면 값을 forwarding 해와서는 안된다.

아직 memory read가 끝나지 않았기 때문이다.

이를 load-use data hazard라고 한다.

 

load-use data hazard는 한 cycle이 지나면 사라지기 때문에 MEM hazard가 발생한 경우에는 두 번째 앞의 instruction이 무엇인지 고려안해도 된다.

 

아래 예시에서 맨 마지막 instruction은 바로 앞의 instruction에서만 forwarding을 받으면 된다.

따라서 double data hazard가 발생하지 않도록 EX hazard가 발생하지 않았을 때만 forwarding 되도록 MEM hazard의 조건을 설정해야 한다.

<pre>add $1, $1, $2

add $1, $1, $3

add $1, $1, $4</pre>

 

Datapath for Forwarding

EX/MEM register로부터 앞의 instruction에서 수행된 결과를 받을 수 있고,

MEM/WB register로부터 2번째 전의 instruction에서 수행된 결과를 받을 수 있다.

 

EX Hazard 인 경우의 조건

다음과 같은 조건이 충족되면 바로 앞의 instruction의 값을 forwarding 한다.

• EX/MEM.MEMRead = 0
  • 이전의 instruction이 lw instruction이 아닌지
  • lw instruction은 load한 값을 MEM stage가 끝나야 알 수 있다.
  • 따라서 바로 앞의 instruction이 lw이면 안된다.
• EX/MEM.RegWrite = 1
  • 이전의 instruction이 register에 write를 하는지 
  • ALU instruction이나 lw instruction인지를 확인
  • beq, sw인 경우 $rd에 write하지 않기 때문에 새로운 값을 만들어내지 않는다.
  • 따라서 이들은 다른 instruction에 forwarding 할 수 없다.
• EX/MEM.RegisterRd != 0
  • 이전의 instruction이 write 하는 register가 0가 아닌지
  • 컴파일러는 필요 시 nop과 같이 rd가 $zero인 instruction을 만들어낸다.
  • 이런 instruction으로부터는 forwarding 받으면 안된다.
• EX/MEM.RegisterRd = ID/EX.RegisterRs
  • 내가 읽는 register 번호 == 이전의 instruction이 write하는 register 번호

 

정리

• EX hazard
  • rs를 forwarding 받아야 하는 경우
    • EX/MEM.MEMRead = 0
    • EX/MEM.RegWrite = 1
    • EX/MEM.RegisterRd != 0
    • EX/MEM.RegisterRd == ID/EX.RegisterRs
  • rt를 forwarding 받아야 하는 경우
    • EX/MEM.MEMRead = 0
    • EX/MEM.RegWrite = 1
    • EX/MEM.RegisterRd != 0
    • EX/MEM.RegisterRd == ID/EX.RegisterRt
• MEM hazard
  • rs를 forwarding 받아야 하는 경우
    
    • MEM/WB.RegWrite = 1
    • MEM/WB.RegisterRd != 0
    • MEM/WB.RegisterRd == ID/EX.RegisterRs
    • and not
      • EX/MEM.RegWrite = 1
      • EX/MEM.RegisterRd != 0
      • EX/MEM.RegisterRd == ID/EX.RegisterRs
  • rt를 forwarding 받아야 하는 경우
    • MEM/WB.RegWrite = 1
    • MEM/WB.RegisterRd != 0
    • MEM/WB.RegisterRd == ID/EX.RegisterRt
    • and not
      • EX/MEM.RegWrite = 1
      • EX/MEM.RegisterRd != 0
      • EX/MEM.RegisterRd == ID/EX.RegisterRt

 

Forwarding Unit Output

Forwarding unit은 위 조건을 확인하여 control signal을 만들어낸다.

Forwarding unit에서 나오는 ForwardA와 ForwardB는 3개 중 하나를 선택해야 하므로 각각 2bit 여야 한다.

 

• EX hazard
  • rs를 forwarding 받아야 하는 경우 : ForwardA = 10
  • rt를 forwarding 받아야 하는 경우 : ForwardB = 10
• MEM hazard
  • rs를 forwarding 받아야 하는 경우 : ForwardA = 01
  • rt를 forwarding 받아야 하는 경우 : ForwardB = 01

 

Datapath and Control with Forwarding

 

---

Load-Use Data Hazard

lw instruction에서 data load는 MEM stage에서 수행된다.

따라서 register에 write 되는 값은 MEM 이후부터 확정된다.

이 때문에 바로 앞의 instruction이 lw instruction인 경우 한 cycle stall이 필요하다.

 

성능

lw가 나올 확률은 5%이므로, CPI는 1.05 (= 1 + 0.05 * 1)이 된다.

 

 

해결

Load-use data hazard는 가능한 빨리 detect 해서 해결하는 것이 좋다.

ID stage 마지막 단계에서부터 현재 instruction이 읽으려고 하는 register(rs, rt)를 알 수 있다.

 

아래 조건이 확인되면 nop instruction을 추가함으로써 해결한다.

• ID/EX.MemRead and
  • ID/EX.RegisterRt = IF/ID.RegisterRs
  • or
  • ID/EX.RegisterRt = IF/ID.RegisterRt

 

nop instruction을 추가하기 위해 clock이 끝시점에 다음과 같은 행동이 일어난다.

• clear control
  • control signal을 0으로 초기화한다.
  • 원래는 decode가 끝나면 control signal을 넘겨주어야 한다.
  • 그러나 모든 contorl signal을 0으로함으로써 RegWrite와 MemWrite를 0으로 한다.
  • 이를 통해 결과를 register나 memory에 쓰지 않는, nop를 만들어낼 수 있다.
• not change IF/ID register
  • fetch의 결과를 바꾸지 않음으로써 현재 실행하려던 instruction을 유보한다.
• not change PC register
  • PC의 값을 바꾸지 않음으로써 이후의 instruction들의 수행을 보장한다.

 

Datapath with Hazard Detection

Load-use data hazard를 detect하기 위한 unit이 추가되어야 한다.

 

---

Data Hazard and Compilers

Data hazard를 software(compiler)를 이용해서 아래와 같이 해결하는 방법이 있다.

 

• 컴파일러가 stall을 추가함으로써 정확성을 보장한다.
  • 그러나 성능이 떨어진다.
  • stall을 없애기 위한 하드웨어 구성이 어렵지 않기 때문에 하드웨어를 이용하여 해결한다.
• 컴파일러가 코드의 순서를 바꿈으로써 hazard나 stall를 피할 수 있다.
  • 그러나 layer violiation과 compiler dependence 문제를 야기한다.
  • 다른 해결책에 대한 하드웨어 구현이 어렵지 않기 때문에 이 방법은 이용하지 않는다.
  • layer violation
    • 컴파일러가 MIPS implementation 정보(pipeline structure)를 알아야 한다.
    • pipeline이 몇개의 stage로 구성되어있고 어떻게 pipeline을 구현하였는가 등
  • compiler dependence
    • ISA가 바뀌지 않더라도 implementation은 자주 바뀔 수 있다. (pipeline 등)
    • implementation이 바뀐다면 compiler를 바꾸어야 한다.
• Dynamic(runtime) out-of-order execution
  • runtime에 하드웨어가 코드의 순서를 바꿔서 수행한다.
  • 이는 compiler가 하는 것이 아니기 때문에 compiler dependence가 없다.