[컴퓨터구조 요약 정리] 9. Pipelined Architecture 3

9.1. Data Hazards :: Forwarding vs Stalling

다음과 같은 연산이 있다고 가정하자.

sub	x2, x1, x3
and	x12, x2, x5
or	x13, x6, x2
add	x14, x2, x2
sd	x15, 100(x2)

위 코드에서 첫 번째 instruction에서 x2가 계산되지 않으면 hazard가 발생한다.

위 코드에 pipelining을 적용한 diagram은 위와 같다.
상단을 보면, CC5 까지 x2의 값은 변하지 않는다. 따라서 2, 3, 4번째에서 참조한 x2는 쓰레기값이다.

우리는 지난 시간에 data hazard를 막기 위해 forwarding이 필요하다고 배웠다.
우리는 아직 forwarding을 하는 방법에 대해서 배우지 않았으므로 지금부터 다뤄보자.

9.2. Hazard 감지하기

먼저 forwarding을 하기에 앞서, hazard가 발생했는지 여부를 파악하는 것이 우선이다.

혹시 까먹었을까봐 다시 언급한다. Instruction의 두 operand를 rs1, rs2라 하고, 결과를 저장하는 곳을 rd라고 한다.

9.2.1. 판단 기준

1. Operand register 번호를 pipeline으로 넘겨준다
   • rs1과 rs2에 해당하는 register number를 ID/EX.RegisterRs1 & ID/EX.RegisterRs2에 각각을 저장한다.
   • 두 값을 EX stage까지 끌고간다.
2. 두 register 번호와 rd 값을 비교한다
   • EX stage 직전까지 끌고온 두 값 ID/EX.RegisterRs1 & ID/EX.RegisterRs2을 이전 instruction의 MEM stage 또는 WB stage에 저장된 rd값과 비교한다.
   • 즉, 이번 instruction의 operand를 저번 instruction의 destination과 비교한다.
3. 아래와 같은 경우 data hazard가 발생했다고 판단한다
   1. EX/MEM.RegisterRd == ID/EX.RegisterRs1
   2. EX/MEM.RegisterRd == ID/EX.RegisterRs2
   3. MEM/WB.RegisterRd == ID/EX.RegisterRs1
   4. MEM/WB.RegisterRd == ID/EX.RegisterRs2

9.2.2. 주의사항

하지만, 위 조건에 해당한다고 모두 hazard라고 판단헤서는 안된다.
왜냐하면, 단순히 store 또는 branch 처럼 rd에 어떤 값을 write하는 게 아니라면 forwarding이 불필요하기 때문이다.

따라서 forwarding은 오로지 rd에 어떤 값을 write할 때만 hazard 여부를 검사해야 한다.

• 이 정보는 EX/MEM.RegWrite 또는 MEM/WB.RegWrite control signal이 알려준다.
• Register에 값을 write 하기 위해서는 위 control signal이 HIGH여야 하기 때문이다.

9.2.3. 실제 적용

• 위 그림은 Forwarding Unit이 추가된 diagram이다. 3x1 MUX를 좌측부터 ⓐ, ⓑ, ⓒ라고 불러보자.
• 먼저, Forwarding Unit을 보자. Forwarding Unit은 위에서 다룬 Rs1, Rs2, EX/MEM.RegisterRd, MEM/WB.RegisterRd 4가지 입력을 받는다. 우리는 앞서 이 4가지 입력을 비교해서 data hazard를 발견할 수 있음을 배웠다. Output으로 ForwardA와 ForwardB control signal을 보내는데, 각각 MUX의 control bit로 들어간다.
  • 3x1 MUX이므로 ForwardA와 ForwardB는 2-bit로 돼있다.
  • 00이면 ID/EX의 출력값을, 10이면 이전 cycle의 EX/MEM 출력값을, 01이면 이전 cycle의 MEM/WB 출력값을 선택한다.
• 다음으로 ⓐ와 ⓑ를 살펴보자. 입력 신호가 동일하다.
  • 하나는 ID/EX로부터 나오는 Read Data (Source register가 가지고 있는 데이터 혹은 주소에 해당하는 데이터)다.
    • Forwarding이 불필요한 경우 MUX는 이 신호를 선택해서 ALU는 일반적인 연산을 수행하게 될 것이다.
  • 하나는 이전 clock의 EX/MEM 값이다. 이전 clock에서 ALU에서 계산된 결과가 여기 들어간다.
    • Forwarding이 필요한 경우 MUX는 이 신호를 선택할 것이며 forwarding이 일어나게 된다.
  • 하나는 이전 clock의 MEM/WB 출력값이다. 마찬가지로 forwarding이 일어나게 된다.

9.3. Double Data Hazard

add	x1, x1, x2
add x1, x1, x3
add x1, x1, x4

위 코드는 첫 번째 연산에서 x1이 결정되지 않아서 2, 3번 연산 모두 data hazard가 발생하는 경우다.
이런 경우를 막기 위해서 앞에서 다룬 hazard 조건에 몇 몇 조건을 조금 더 추가해야 한다.

위 코드를 pipeline diagram으로 나타내면 위와 같다. Forwarding unit은 WB stage에 있는 명령어랑 MEM stage에 있는 명령어로부터 forwarding을 동시에 전달하는 double hazard가 발생한 상황이다. 이때 우선권은 MEM에서 오는 forwarding이다.

조건식으로 나타내면 다음과 같다.

if ((MEM/WB.RegWrite && MEM/WB.RegisterRd != 0)		&&
    (MEM/WB.RegisterRd == ID/EX.RegisterRs1)		&&
    !((EX/MEM.RegWrite && EX/MEM.RegisterRd != 0)	&&
      (EX/MEM.RegisterRd == ID/EX.RegisterRs1)
     )
   ) ForwardA = 01

근데 솔직히 말해서 왜 위 조건식이 성립하는지는 모르겠다. EX/MEM 쪽에서 오는 forwarding에 우선권을 준다면 ! 안에 들어가야 하는 게 EX/MEM이 아니라 MEM/WB 쪽이 되야하는 거 아닌가? 게다가 왜 ForwardA = 01 일까? 01은 MEM/WB가 source라는 뜻인데… 미안하다. 이 부분은 이해가 안간다.

9.4. Load-Use Data Hazard

우리는 지금까지 ALU를 사용하는 명령어에 대해서 발생하는 data hazard 상황에 대해 다뤘다.
생각해보면 data hazard가 발생할 수 있는 경우가 한 가지 더 있는데, 바로 load 명령어 (ld)다.

Load 명령어 또한 register에 write하는 명령어 이므로 data hazard를 유발할 수 있다.

• ALU를 사용하는 R-format instruction은 EX stage가 지나서 forwarding.
• Load 명령어는 memory에서 값을 가져와야만 하므로 MEM stage가 지나야 forwarding.

만일 load 명령어와 다음 instruction 사이에서 dependency가 존재한다면, 의도적으로 1-cycle을 쉬어야 한다. 이때 누군가는 dependency를 발견해줘야 하는데, 이 역할을 Hazard detection unit이 맡는다.

• Hazard detection unit은 ID/EX.MemRead signal과 IF/ID.RegisterRs1, IF/ID.RegisterRs2를 input으로 받아서 의존성 여부를 판단한다.
• Hazard가 발생했다면 의도적으로 쉬어주기 위해 현재 decoding 된 instruction을 NOP (No-Operation)로 바꿔준다.

if (ID/EX.MemRead	&&
   	(ID/EX.RegisterRd == IF/ID.RegisterRs1	||
    ID/EX.RegisterRd == IF/ID.RegisterRs2))

1. 지금 decoding 된 instruction을 NOP로 만들기 위해 ID/EX에 있는 모든 control signal을 0으로 초기화한다.
2. PC값을 업데이트 하지 않도록 막아서 해당 operation을 다시 수행하도록 만들어 의도적으로 stall 시킨다.

9.5. Control Hazards

지금까지 data hazard에 집중해서 배웠으니 이번에는 control hazard에 대해서 배워보자.

Branch 계열의 명령은 EX stage를 지나야만 branch를 할지 말지 여부와 target address가 계산된다. 계산 결과를 PC에 update 하는 과정까지 포함하면 총 3-cycle이 소모된다.

즉, 3-cycle 동안 pipeline에 들어온 instruction은 무용지물이다. 왜냐하면, branch로 jump 하게 되면 fetch하고 decode한 다음 instruction들이 전혀 필요없기 때문이다.

이것을 방지하기 위해서는 branch 명령어를 발견했을 때 최대한 빠르게 위 두 가지 항목(branch 여부, address 계산)을 미리 계산해줘야한다. 물론 ALU는 EX와 MEM stage에 있기 때문에 HW를 추가해서 미리 계산한다.

IF/ID와 ID/EX 사이에 target address 계산을 위한 작은 adder와 branch 여부를 판단하기 위한 comparator를 둔 것을 확인할 수 있다. Decoding stage에서 branch에 대한 판단이 완료되므로 control hazard를 최대한 회피할 수 있다.