[컴퓨터구조] 14-2. Pipelined MIPS - hazard

전에 배운 single cylce에 pipeline을 더해서 성능을 획기적으로 상승시킨다. 그러나 이 과정에서 발생하는 문제, 혹은 위험(hazard)이 있는데 이는 다음과 같다.

• Structural hazard
  • HW는 하나인데 같은 cycle에 두 개의 명령어를 쓰려고 함.
• Data hazard
  • 두 개의 명령어가 같은 storage에 접근
  • 명령어가 정순서로 뽑아질 때 나옴
• Control hazard
  • 한 명령어가 다음 명령어에 영향을 끼친다.

 

Structural hazard

모든 instruction의 수행이 IF-ID-EX-MEM-WB으로 이루어진다고 가정했을 때 4번째 Cycle에서는 첫 번째 instruction의 Memory Access와 네 번째 instruction의 IF가 동시에 Memory Access를 요구하는 것을 볼 수 있다. 메모리는 당연히 어디서 해당 signal을 받았는지 알 수 없기 때문에 결론적으로 Resource Conflict 현상이 발생하는 것이다.

• 이에 대한 해결책으로는 Stalling으로, 저렇게 중복해서 쓰는 부분에 대해서는 다른 instruction을 처리 할 때는 쉬어주게끔 고려하는 것이다. 즉, 기기적으로 이상이 없음에도 일부러 수행을 멈추게 하여 비용적인 측면에서는 더 효율적이겠지만 아무래도 성능이 좋을 순 없다.

 

Data Hazard

Data에 대한 Read/Write Sequence가 엇갈리면서 발생하는 문제이다. 간단히 두 번째 instruction 결과가 첫 번째 instruction에 dependent하기에 발생하는 문제인 것이다.

 

이에 따른 경우는 다음 3가지와 같이 정의된다.

• Read After Write(RAW)
• Write After Write(WAW)
• Write After Read(WAR)

위를 보면 Write 과정이 data hazard를 야기하는 주된 원인임을 알 수 있을 것이다.

 

Load-use hazard

lw의 계산 결과는 memory의 값이기 때문에 DM과정의 뒤에서 가져올 수 있기 때문에 이전의 hazard와 같이 forwading 방식으로 ALU에서 가져와도 그 연산 결과는 메모리의 주소값일 뿐 실질적으로 원하는 값이 아니기 때문에 그 방식으로는 해결할 수 없다.

 

Stalling

앞의 데이터가 준비 되기 전까지 그 데이터를 쓰는 공간을 아무것도 하지 않고 가만히 냅둔다. (stall)

즉, 그 상태를 그대로 유지하는 것이다.

• 그러기 위해선 다음 두 조건을 만족해야 한다.
  • 새로운 명령어가 들어오지 않는다.
  • register file에 data가 update되지 않는다.

 

Stalling Hardware

)

StallF와 StallD 신호를 통해 IF와 ID의 register를 disabled 시키는 것이다.

그렇게 되면 E방에는 데이터가 한 clock 동안 비워 주어야 하는데 이 과정을 flush라고 하고 해당 동작을 FlushE signal이 관할하여 clear 시키는 역할을 한다.

 

Stalling Logic

lw 명령어에서 쓰이던 rt가 R type의 rs나 rt에 사용되면 lwstall이 enable된다.

lw 명령어인 경우를 판별하기 위해서 MemtoReg를 사용하였다.

Control Hazards

• beq:
  
  • branch not이 pipeline의 4번째 stage까지 결정된다.
    • pipeline penalty
  • Instructions after branch fetched before branch occurs
    • branch가 fetch된 후에 branch가 발생하기 전에 명령어
  • 만약 branch가 발생하면 이러한 명령어들은 flush돼야 한다.
• Branch misprediction penalty
  
  • branch가 수행될 때 flushed되는 명령어의 수
  • branch가 더 일찍 결정되므로써 감소될 것이다.

 

Control Hazards: Origianl Pipleine

비교를 M방에서 하면 앞에서 만들어진 데이터가 모두 버려져야 하기 때문에 비효율적인 동작이 발생하게 된다.

 

Control Hazards

beq 명령어로 인해 jump하고자 하는 label과 beq 명령어 사이에 들어왔던 instruction 들은 쓸모가 없어지기 때문에 Flush 되어야 한다.

 

Early Branch Resolution

그래서 조금이라도 이 penalty를 줄이기 위해서 M방에서 zero를 check하던 AND gate 대신에 D방에 comparator를 추가하여 해결할 것이다.

또한 BTA를 계산하던 ALU 모듈 역시 D방으로 옮겨서 조금이라도 빨리 비교하여 뒤의 필요없는 instruction이 낭비 되지 않으면서 jump를 할 수 있도록 한 것이다.

Introduced another data hazard in Decode stage

• BTA 계산 하는 모듈
• 같은 지를 비교하기 위한 comparator

그런데 이렇게 하자니 새로운 hazard가 다시 발생한다.

 

Early Branch Resolution

• 왼쪽의 code는 두 개 앞에 가고있는 clock이 add이기 때문에 forwarding으로 해결 가능한 문제이다.
  • 다음 다음 clock에서는 ALU에서 이미 계산이 완료 되었기 때문에

• 그런데 만약 오른쪽의 code처럼 두 clock 앞에 가는 명령(M방)이 lw 이거나
• 바로 앞에 가는 clock(E방)에서 add와 같은 register write이 일어난다면
• 그 때는 ALU 계산을 하기도 전이라서 새로운 data hazard를 발생하기 때문에 이 경우에는 stall이 필요하다.

 

 

Handling Data Dependency for Branch inst.

 

Control Forwarding & Stalling Logic

• Forwarding logic:

두 개 앞에 가는 명령(M)의 WriteReg와 현재 rs가 같으면서 RegWriteM이 enable일 때

• Stalling logic:

(현재(D) Branch라는 명령이고) AND (한 개 앞에 가는 명령(E)이 RegWrite || 두 개 앞에 가는 명령(M)이 lw )

• (lwstall 인 듯 위에는 표시가 안 되어 있음)
• E방에서는 R-type인지를 알아내고 싶은 것이기 때문에 RegWriteE를 넣었다.
• M방에서는 lw인지를 알아내고 싶기 때문에 MemtoRegM을 넣었다.
  • 이것들이 만족하면서 현재 beq에서 rs 혹은 rd가 저장할 레지스터와 동일한지를 확인한다.

MemtoReg: lw명령어만 갖고 있는 control signal

즉, 두 개 앞에 가고 있는 명령어가 lw일 때를 의미한다.

 

Pipielined Processor with Full Hazard Handling

beq을 check 하기 위해서 ALU를 사용하지 않고 comparator를 사용하였음

 

Handling jump instruction

jump는 condition을 따지지 않고 바로 실행하기 때문에 control 신호가 branch pin과 OR에 들어가서 fetch한 명령어를 clear시킨다.

• fetch stage should be flushed.
• 이미 들어와 있는 것을 clear 시킴
• 그러고 나서 새로운 명령어가 fetch된다.

---

Branch Prediction

• branch가 언제 수행될지를 추측 하기
  
  • Backward branch들이 보통 수행된다. (loops)
  • 추측을 잘하기 위해 history를 고려한다.
  • 좋은 예측은 flush를 요구하는 branch의 조각(fraction)을 감소시킨다.