[Computer Architecture] Pipelined MIPS - hazard

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

• Structural hazard
  • HW는 하나인데 같은 cylce에 두 개의 명령어가 쓰려고 함.
• 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 determined until 4th stage of pipeline
    • pipeline penalty
  • Instructions after branch fetched before branch occurs
  • These instructions must be flushed if branch happens
• Branch misprediction penalty
  • number of instruction flushed when branch is taken
  • May be reduced by determining branch earlier

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이 필요하다.

Q) 만약에 lw 명령어에서 rt에 load 하는 명령 바로 다음 beq에서 그 레지스터를 사용하면 stalling을 두 클락동안 해야 하나요?

(위와 같은 코드를 주고) 이랬을 때 어떤 문제(hazard)가 발생하느냐? -> 시험문제

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된다.

위 그림에서 control input/output에 대해 생각해 보기(0503 강의 마지막 부분)

---

Branch Prediction

• Guess whether branch will be taken
  • Backward branches are usually taken (loops)
  • Consider history to improve guess
  • Good prediction reduces fraction of branches requiring a flush