Pipeline CPU(4)- Data Forwarding

Pipeline-CPU 목차

• Pipeline CPU(1) : Single-Cycle vs Multi-Cycle CPU
• Pipeline CPU(2) : Pipeline-CPU의 간략한 이해
• Pipeline CPU(3) : Data Hazard(RAW)
• Pipeline CPU(4) : Data Forwarding
• Pipeline CPU(5) : Control Hazard

STALL을 통한 Data Hazard 해결

RAW Hazard를 해결하는 가장 간단한 방법은 RAW가 발생한 두 Instruction간의 거리를 3보다 멀어지도록 두 Instruction 사이에 STALL을 추가해주는 방법이 있습니다.

STALL을 함으로써 I_OLD가 WB단계를 거쳐서 레지스터에 값을 저장할 때까지 충분히 기다려준 이후에, i.e dis(I_OLD,I_YOUNG) > 3이 되도록, I_YOUNG의 Read가 순차적으로 실행되도록 하는 것 입니다.

하지만 STALL을 사용하는 것의 단점은 매번 RAW Hazard가 발생될 때마다, STALL이 생겨남으로 인해서 CPU의 성능이 저하가 된다는 단점이 있습니다. 성능의 저하없이 더욱 효율적인 해결방안은 없을까요?

Data Forwarding Logic(=Register Bypassing)

STALL을 사용하는 방법보다 더욱 효과적인 방법이 Data Forwarding을 사용하는 방법입니다. 결론부터 말하자면, Data Forwarding을 통해서 dist(i,j)=1 인 LD(i.e. Load Instruction)을 제외한 모든 RAW Hazard를 해결할 수가 있습니다.

Feature3. Pipeline diagram

매번 새로운 Instruction이 Pipeline을 통과하는 구조를 잘 살펴봅시다. 위의 Feature3을 보면 순서대로 Instruction이 들어오는 것에 따라 각 시간 별로, 어떤 Instruction이 어느 State에서 수행되고 있는지를 확인할 수가 있습니다.

sub x2, x1, x3
and x12, x2, x5

위의 두 Instruction을 예시로 살펴봅시다. x2에서 dist=1 인(i.e. 거리가 1)인 RAW Hazard가 발생하였다는 사실을 알 수 있습니다. 이전에 STALL을 이용한 해결방법을 생각한다면, EX단계에서 ALU를 수행한 값을 MEM단계에서 x2에 저장할 때까지 두 번째 Instruction의 ID단계는 STALL을 통해 멈춰있어야만 합니다.

하지만 만약, EX단계의 ALU에서 계산된 값을 곧바로 두 번째 Instruction에서의 ALU의 Input으로 꽂아 줄 수 있다면 굳이 두 번째 Instruction이 ID단계에서 레지스터로 부터 x2를 읽지 않아도 잘 계산된 값을 받아올 수 있지 않을까요? 이러한 생각이 바로 Data Forwarding Logic 입니다.

Feature3에서 확인할 수 있듯이, 첫 번째 Instruction에서 EX단계에서 계산된 값을 곧바로 STALL없이 두 번째 Instruction의 ALU의 Input으로 Forwarding 해주는 것을 확인할 수가 있습니다. 마찬가지로 dist=2(i.e. 거리가 2)인 경우에도 비슷한 방법으로, MEM에서 가진 x2의 값을 세 번째 Instruction의 ID단계에 곧바로 읽도록 Forwarding 해주었습니다.

dist=3(i.e. 거리가 3)인 경우는 아래의 Feature4를 통해 쉽게 이해하여 봅시다.

Feature4. Forwarding diagram

거리가 3인 경우에는 첫 번째 Instruction이 WB단계에서 x2 레지스터에 값을 Write하는 동시에 네 번째 Instruction이 같은 위치의 x2 레지스터의 값을 Read 하면서 발생하는 RAW Hazard 입니다. 하지만 이때, WB(Write Back)하려고 들어오는 값을 그대로 받아서 ID단계에서 사용하도록 Forwarding 함으로써 Hazard를 해결할 수가 있습니다.

if(rs1_EX != 0) && (rs1_EX == rd_MEM) && RegWrite_MEM then
forward operand from MEM stage // dist=1
else if(rs_EX != 0) && (rs_EX == rd_WB) && RegWrite_WB then
forward operand from WB stage // dist=2
else
use the operand from register file //dist=3

대략적인 코드 구조는 위와 같습니다.

Data Forwarding 을 이해하는데 필요한 다음의 두가지 세부 사항을 한번 살펴보자.

1. 가장 최근의 값을 먼저 Forwarding 해주어야 한다.
2. Data forwarding으로 모든 instruction(RAW)을 해결할 수 있을까?

1. 가장 최근의 값을 먼저 Forwarding 해주어야 한다.

다음의 예시의 경우를 한 번 살펴봅시다.

sub x2, x1, x3
add x2, x2, x5 // dist(1,2)=1 (x2)
add x4, x2, x7 // dist(1,3)=2 (x2), dist(2,3)=1(x2)

위의 예시와 같은 경우에 만약 3 번째 줄을 수행할 때, Data forwarding을 dist=1 보다 dist=2를 먼저 수행한다고 가정하여 봅시다. 올바른 계산은 3 번째 줄에게 가장 최근인 add를 한 결과를 x2가 받아와야 할 것입니다. 하지만, add를 수행하기 전인 sub의 결과로 부터 x2를 읽어오는 forwarding을 수행하기 때문에 올바른 결과값을 갖지 못하게되는 오류가 발생합니다.

따라서 위의 Data Forwarding Logic에서 확인할 수 있듯이, dist를 1,2,3 순서대로 즉 가장 가까운 값으로 부터 forwarding을 먼저 수행해 주어야 합니다.

2. Data forwarding으로 모든 instruction(RAW)을 해결할 수 있을까?

ld x2, x3, x4
add x6, x2, x7 //dist(1,2)=1 RAW(x2)
sub x8, x9, x10

위의 경우 add에서 dist=1 이므로 data forwarding을 해주면 되지만 LD instruction이기 때문에 문제가 발생합니다. LD instruction의 경우, ALU로 부터 계산된 값이 아닌 메모리를 Read 한 값을 Forwarding 해주어야 하므로 dist=1일때 한 번의 STALL을 꼭 예외적으로 필요로 합니다.

따라서 위의 DataForwarding Logic과 함께 다음의 STALL 조건을 추가해 주어야 합니다.

//Stall 조건
if([(rs1_ID == rd_EX) && use_rs1(IR_ID) || (rs2_ID == rd_EX) && use_rsw(IR_ID)]
&& MemRead_EX) then stall
//MemRead_EX : op=LD/LW/...

전체적인 구현 Design

RAW Hazard를 고려한 Data Forwarding 구현은 다음과 같습니다.

1. Data forwarding
2. Hazard Detection(LD의 경우, STALL)

Feature3. Pipeline CPU design(Data Forwarding)

Post의 참고자료와 이미지의 출처는 아래와 같습니다.

Computer Organization and Design RISC-V edition
Computer Architecrue Lecture Note @ Carnegie Mellon University, University of, Michigan, Purdue University, University of Pennsylvania, University of Wisconsin and POSTECH.