[Lecture 14] Pipeline Handling Branches

#Branch Hazards

파이프라인에서 다음 명령 시퀀스들을 실행하는 것을 고려해보자.

• beq가 ID stage로 갈때:
  • 44번으로 instruction를 가져와야 할까?
  • $1 == $3인지에 따라 다음에 실행될 수도 있고 실행되지 않을 수도 있다
  • 어쨌든 우리는 아직 branch target 명령의 주소를 모른다

beq가 ID 단계에 들어가면 우리는 그것이 conditional branch인지도 모른다.

그리고 beq가 EX가 끝날 때까지 branch를 가져가야 하는지 알 수 없다.

따라서 우리는 이미 다음 (순차적인) instruction을 가져왔을 것이다

#Stalling for Branch Hazards

branch를 가져갈지 알 때까지 stall을 사용하면된다. beq가 MEM 단계에 도달하기 전에는 해당 정보에 대해 조치를 취할 수 없다.

#Stalling Until Branch Decision

branch를 가져갈지 알 때까지 stall을 삽입.

하지만 그렇게 까지 하기위해선 (CPU / 메모리) 비용이 많이든다. 만약 우리가 branch를 받지 않는다면, 우리는 불필요하게 2 사이클 동안 and instruction을 지연 시켰다.

#Rollback for Branch Hazards

branch를 빼앗기지 않을 것처럼 진행하면 된다. 틀리면 mis-fetched instruction들은 nops로 바꾸면 된다

#여기서 질문

branch decision이 더 빨리 내려질 수 있도록 데이터 경로를 재조정할 수 있을까?

 

branch target 주소를 계산하는 것은 어떨까? 그건 ID 단계에서 할 수 있을까?

 

레지스터 비교는 어떤가? 그건 ID 단계에서 할 수 있나?

다른 종류의 conditional branch(예: bgez)는 어떨까?

#Making Branch Decisions Earlier

branch를 가져간 경우 stall하고, 그렇지 않은 경우 정상적으로 진행하면된다

이제 비용은 branch를 가져간다면 하나의 stall이고, branch를 가져가지 않았다면 아무것도 아니다.

간단한 하드웨어는 두 레지스터를 비교하기에 충분하다. branch adder은 비교적 쉽게

 

우리는 beq가 EX 단계에 도달하기 전에 브랜치를 가져갈지 여부를 결정할 수 있다. 하지만 우리는 또한 한 사이클을 위한 스톨을 만들어야 한다

#Stall-on-Branch

• beq 명령을 디코딩할 때마다:
  • 우리는 beq에 따르는 지시를 지연시킬 필요가 있다
  • 우리는 ID 단계의 지시를 nop으로 바꿀 수 있는 능력이 있다
  • 하지만 우리는 beq를 디코딩한 후에 그 한 사이클을 트리거해야 한다

#The Big (but not quite final) Picture

#Data Hazards for Branches

beq의 비교 레지스터가 2차 또는 3차 선행 R-type 명령의 대상인 경우. stall 없이 fowarding을 사용하여 해결할 수 있다

비교 레지스터가 바로 앞의 형식 명령 또는 두 번째 선행 load 명령의 대상인 경우. 1사이클 동안 beq를 stall해야 한다

비교 레지스터가 바로 앞의 로드 명령의 대상인 경우 2사이클 동안 stall해야 한다

• 따라서 최신 버전의 데이터 경로에는 더 많은 수정이 필요하다:
  • 이러한 위험은 ID 단계에서 새로운 하드웨어에 의해 감지되어야 한다
  • 실제 포워딩(대체) 작업도 ID 단계에서 새로운 하드웨어가 필요하다.
  • 이러한 해저드를 다루는 것은 lw와 마찬가지로 지연을 필요로 하지만
    • 만약 write instruction이 beq보다 한 사이클 앞이라면 우리는 두 번의 stall 사이클이 필요하다.
    • 또한 write instruction이 beq보다 두 사이클 앞서 있다면 우리는 하나의 stall 사이클이 필요하다.