Data Hazards : Forwarding vs Stalling

파이프라이닝은 성능을 높이기 위한 강력한 기법이지만, 실제 프로그램에는 명령어 간의 데이터 의존성(data dependence)이 빈번히 존재하며, 이는 파이프라인 해저드(hazard)를 유발할 수 있다. 특히 데이터 해저드는 한 명령어의 결과가 아직 계산되지 않았는데, 다음 명령어가 그 값을 필요로 할 때 발생한다.

sub $2, $1, $3     # $2 ← $1 - $3
and $12, $2, $5    # $12 ← $2 & $5
or  $13, $6, $2    # $13 ← $6 | $2
add $14, $2, $2    # $14 ← $2 + $2
sw  $15, 100($2)   # Memory[$2+100] ← $15

• 위 코드에서 sub 명령어가 계산한 $2 값은 이후의 모든 명령어에서 사용된다.
• sub는 5번째 사이클(WB)에서 $2에 값을 기록한다.
• 하지만 and, or 명령어는 그 이전에 EX 단계에 도달하므로, 이 때는 아직 $2 값이 쓰이지 않았다.
• 이처럼 데이터가 시간상 뒤에 생성되는데 먼저 필요할 경우, 이를 pipline data hazard라고 한다.

sub가 $2에 -20을 쓴다고 가정하면, and, or는 아직 -20이 기록되기 전인 초기값 10을 읽게 된다.(잘못된 동작) add, sw는 올바른 시간에 $2를 읽게 된다.(정상 동작)

Dependencies & Forwarding

위 그림에서 색깔 선(color lines)은 데이터 의존성을 의미한다. 그 중 시간을 거슬러 올라가는 선들은 Hazard를 나타낸다. 파이프라인에서 이전 명령의 결과를 나중 명령어가 EX 단계에서 필요로 하는 경우, 해당 값이 레지스터에 기록되기 전이라도 ALU 결과나 MEM 결과를 즉시 전달해야 하며, 이를 위해 forwarding 경로가 하드웨어에 존재해야 한다.

레지스터 파일은 쓰기와 읽기가 한 클럭 내에서 구분되어 처리된다.

• 쓰기: 클럭 사이클 전반부
• 읽기: 후반부

따라서 같은 클럭 사이클 내에서 쓰고 읽는 경우, 새로 쓴 값이 바로 읽힌다. -> 일부 hazard 자동 회피
하지만 대부분의 hazard는 이전 사이클 결과를 필요로 하는 EX 단계에서 발생한다.(명시적 forwarding 유닛 + 제어 논리 필요)

Forwarding이 필요한 경우 감지하기

파이프라인에서 데이터 해저드(data hazard)가 발생하지 않도록 하려면, 앞선 명령어의 연산 결과를 다음 명령어의 ALU 연산에 전달해 줄 수 있는 Forwarding(우회 전달)이 필요하다. 하지만 모든 상황에서 forwarding이 필요한 것은 아니며, 이를 위해 forwarding이 필요한 상황을 감지(detect)하는 하드웨어 로직이 필요하다.

1. 레지스터 번호 추적
   먼저, 파이프라인 내 각 단계에서 어떤 레지스터 번호(register number)들이 사용되는지를 추적해야 한다. 특히 EX 단계에서 ALU가 사용할 입력 레지스터 번호는 다음과 같다.

• ID/EX.RegisterRs : 첫 번째 ALU 피연산자(보통 rs)
• ID/EX.RegisterRt : 두 번째 ALU 피연산자(보통 rt)

이들은 현재 EX 단계에 있는 명령어가 참조하는 레지스터 읽기 대상들이다.

2. 데이터 헤저드 조건
   이제 이 피연산자들이 파이프라인의 다른 단계에서 앞선 명령어가 결과를 쓰려는 레지스터와 같은지 비교한다.

Forwarding이 필요한 두 가지 주요 상황은 다음과 같다.

✅ EX → EX (가장 최근 명령어로부터 전달)

• EX/MEM.RegisterRd == ID/EX.RegisterRs(조건 1a)

• Ex/MEM.RegisterRd == ID/EX.RegisterRt(조건 1b)

  즉, 바로 앞선 명령어가 EX 단계에서 ALU 연산을 완료했고, 그 결과가 MEM 단계로 넘어간 상태이며, 그 결과를 지금 EX 단계에서 필요로 할 때이다.

✅ MEM → EX (두 단계 앞 명령어로부터 전달)

• MEM/WB.RegisterRd == ID/EX.RegisterRs(조건 2a)
• MEM/WB.RegisterRd == ID/EX.RegisterRt(조건 2b)

앞서 두 단계 전에 실행된 명령어가 WB 단계에 있으며, 그 결과가 아직 레지스터에 쓰이지는 않았지만, EX 단계의 명령어에서 그 값을 사용해야 할 경우이다.

하지만 단순히 레지스터 번호가 같다고 무조건 forwarding을 해서는 안 된다. 다음 조건도 함께 만족해야 한다.

1. 해당 명령어가 실제로 레지스터에 값을 쓰는 명령어여야 한다. -> EX/MEM.RegWrite == 1 또는 MEM/WB.RegWrite == 1
2. 쓰는 대상 레지스터가 레지스터 $0이 아니어야 한다. -> EX/MEM.RegisterRd != 0 또는 MEM/WB.RegisterRd != 0

$Zero는 항상 값이 0으로 고정된 레지스터이므로, 결과를 전달할 이유도, 할 수도 없다.

Forwarding 경로 요약

경로	조건	설명
EX → EX	1a / 1b + RegWrite + RegisterRd ≠ 0	직전 명령어 결과를 바로 ALU에 전달
MEM → EX	2a / 2b + RegWrite + RegisterRd ≠ 0	두 단계 앞 명령어의 결과를 ALU에 전달

해당 조건이 만족되면 MUX가 레지스터 파일 대신 EX/MEM 또는 MEM/WB 파이프라인 레지스터로부터 값을 받아서 EX 단계의 입력으로 사용하게 된다.

• Forwarding 없는 기본 구조 : ALU의 두 입력은 오직 ID/EX 파이프라인 레지스터에서 가져온 RegisterRs, RegisterRt 값만 사용한다. EX 단계에서 필요한 피연산자가 아직 이전 명령어에 의해 계산되지 않았다면, 데이터 해저드가 발생하고, 별도의 대응이 없기 때문에 Stall이 불가피하다.

• Forwarding이 적용된 구조 : 각 ALU 입력 앞에 MUX가 삽입되었다. 이 MUX는 다음 세 가지 중에서 적절한 값을 선택할 수 있다.

  1. **ID/EX의 레지스터 값(기본값)
  2. EX/MEM의 ALU 결과(가장 최근 명령어에서 나온 값)
  3. MEM/WB의 결과(그보다 한 단계 앞서 완료된 값)

  이 선택은 Forwarding Unit이 판단하여 MUX의 제어 신호를 설정한다.

• Forwarding Unit의 동작 : 현재 EX 단계에 있는 명령어가 사용하는 rs 또는 rt 값이 EX/MEM 또는 MEM/WB 단계에 있는 명령어가 결과를 쓰려는 대상 레지스터(rd)와 같을 때, 이 비교를 통해 MUX에 다음과 같은 제어 신호를 보낸다. : ForwardA, ForwardB(각각 ALU의 두 입력)

예: ForwardA 설정 기준

ForwardA 값	의미	입력 경로
00	기본 경로 사용 (ID/EX)	레지스터 파일에서 직접
10	EX/MEM → EX	직전 명령어 결과 전달
01	MEM/WB → EX	두 단계 전 명령어 결과 전달

Forwarding과 Hazard Detection

MIPS 파이프라인은 명령어들을 빠르게 처리하기 위해 여러 단계를 병렬로 실행하지만, 그 과정에서 명령어 간의 데이터 의존성이 성능을 방해할 수 있다. 예를 들어, 어떤 명령어가 계산한 결과가 아직 레지스터에 쓰이기도 전에, 다음 명령어가 그 값을 필요로 한다면 문제가 발생한다. 이를 데이터 해저드(data hazard)라고 하며, 이를 해결하기 위한 대표적인 방법이 Forwarding(우회 전달)과 Hazard Detection(정지 감지)이다.

기본적으로, 한 명령어가 EX 단계에서 계산한 결과는 WB 단계에 가서야 레지스터에 저장된다. 하지만 그 이전에 다음 명령어가 같은 값을 필요로 한다면 어떻게 해야 할까? 이럴 때 사용하는 방법이 Forwarding이다.

Forwarding Unit은 파이프라인에서 명령어들이 사용하는 레지스터 번호들을 추적하고, 현재 EX 단계에서 사용하려는 레지스터 값이 바로 앞의 명령어에서 나왔는지를 확인한다. 예를 들어, EX/MEM 단계의 명령어가 $5에 값을 쓰려고 하고, ID/EX 단계의 명령어가 $5를 읽으려 한다면, Forwarding Unit은 이를 감지하고 EX/MEM에 있는 결과를 직접 ALU로 전달한다. 이렇게 하면 굳이 레지스터 파일까지 결과가 전달될 때까지 기다릴 필요가 없다.

MUX(멀티플렉서)가 ALU의 입력에 연결되어 있어, ForwardA와 ForwardB 신호를 통해 ALU가 입력값을 어디서 가져올지 선택하게 된다. 이 구조는 EX/MEM 또는 MEM/WB 단계의 결과를 바로 전달할 수 있도록 하며, 불필요한 스톨(stall)을 방지한다.

Forwarding으로도 해결할 수 없는 경우: Load-Use Hazard

하지만 모든 데이터 해저드가 Forwarding으로 해결되는 것은 아니다. 대표적인 예외가 Load-Use Hazard이다.

lw  $2, 0($1)
and $4, $2, $3

위의 코드에서 첫 번째 명령어 lw는 메모리에서 값을 읽어 $2에 저장한다. 문제는, 이 값은 MEM 단계에서야 메모리에서 읽혀지므로, and 명령어가 EX 단계에 있을 때는 아직 값이 준비되지 않았다는 점이다. 이 경우엔 Forwarding으로도 해결이 불가능하며, 반드시 파이프라인을 한 사이클 정지(stall)시켜야 한다.

Hazard Detection Unit: Stall을 감지하고 Bubble 삽입

이러한 Load-Use Hazard를 해결하기 위해 필요한 장치가 바로 Hazard Detection Unit이다. 이 유닛은 ID 단계에서 동작하며, 다음 조건을 검사한다:

if (ID/EX.MemRead &&
   ((ID/EX.RegisterRt == IF/ID.RegisterRs) ||
    (ID/EX.RegisterRt == IF/ID.RegisterRt))) {
    // Stall!
}

즉, EX 단계의 명령어가 메모리에서 값을 읽고 있는 lw 명령어이며, 그 결과를 ID 단계 명령어가 읽으려 한다면, 파이프라인을 정지(stall)시킨다. 구체적으로는 다음과 같은 동작을 수행한다:

1. PC의 값 변경을 막는다.(현재 명령어를 계속 유지)
2. IF/ID 레지스터의 갱신을 막는다.(다음 명령어로 넘어가지 않음)
3. ID/EX 레지스터의 제어 신호(Control Signals)를 0으로 만든다 -> nop 명령어 삽입

이처럼 파이프라인 사이에 ‘공기방울(bubble)’을 하나 삽입하여, 위험한 명령어의 EX 단계 진입을 지연시키는 방식이다.

Bubble?

Bubble은 실제 명령어를 실행하지 않는 ‘빈 슬롯’이다. 하드웨어적으로는 ID/EX 단계에 있는 제어 신호를 모두 0으로 만들어 실행을 무력화시키는 방식으로 구현된다. 이후 이 nop은 다음 클럭마다 한 단계씩 파이프라인을 따라 내려가며, 그 뒤의 모든 명령어 실행을 한 사이클씩 밀리게 된다.

예를 들어 and 명령어가 원래 EX 단계에 있어야 할 시점이었더라도, bubble이 삽입되면 EX 단계로 진입이 한 사이클 늦춰지게 된다. 이로 인해 뒤따르는 명령어들도 전반적으로 지연되며, 파이프라인은 일시적으로 느려진다.

버블 삽입의 실제 흐름

클럭 사이클	lw 명령어	and 명령어	or 명령어
CC 1	IF
CC 2	ID	IF
CC 3	EX	ID	IF
CC 4	MEM	nop 삽입	ID (지연됨)
CC 5	WB	EX	ID → EX
CC 6		MEM	EX

• CC4 : 원래 and가 EX 단계로 가야 할 시점이지만, lw가 아직 데이터를 가져오지 못했기 때문에 Hazard Detection Unit이 nop을 삽입한다.
• and 명령어는 실제로 CC2에서 fetch, CC3에서 decode되었지만, EX 단계로의 진입은 CC5로 지연된다.
• 마찬가지로 or는 CC3에 fetch되었지만, ID 단계로 진입도 지연된다.
• 이러한 nop은 공기방울처럼 파이프라인을 따라 흐르며, 그 뒤의 명령어들도 모두 한 사이클씩 밀리게 된다.

Datapath with Hazard Detection & Summary

Forwarding Unit은 ALU 입력 MUX를 제어하여 Stall 없이 실행을 유지하려고 노력한다. Hazard Detection Unit은 load-usr hazard가 발생했을 때 PC, IF/ID, ID/EX 레지스터를 제어하여 파이프라인을 일시 정지시키고 bubble을 삽입한다. 특히 Hazard Detection Unit은 MUX를 통해 실제 제어 신호가 아닌 "모두 0"인 신호(nop)을 삽입함으로써, 안전하게 실행을 지연시킨다.

즉, Forwarding Unit은 성능 최적화를 목표로, 가능한 Stall을 피하고 실행을 유지하려 한다. Hazard Detection Unit은 정확성 보장을 목표로, forwarding으로 해결이 불가능한 상황에서는 과감하게 bubble을 삽입하여 정확한 명령어 실행 순서를 보장한다.