Full beginner lecture
Pipeline Hazards
목표
Pipeline Hazards는 "여러 RISC-V instruction을 겹쳐 실행할 때 언제 기다리고, 언제 값을 전달하고, 언제 잘못 가져온 instruction을 버리는가"를 판단하는 단원입니다. 시험에서는 긴 설명보다 pipeline timing grid를 정확히 그리는 능력이 중요합니다. German term은 Pipeline, Stufe, Forwarding, Stall, Flush, Datenhazard, Kontrollhazard처럼 그대로 익혀 두면 문제 문장을 빠르게 읽을 수 있습니다.
직관
5-stage pipeline은 한 instruction을 IF, ID, EX, MEM, WB로 나눕니다. IF는 instruction fetch, ID는 decode와 register read, EX는 ALU 계산 또는 branch 비교, MEM은 data memory 접근, WB는 register writeback입니다. 한 instruction의 latency가 마법처럼 1 cycle로 줄어드는 것이 아니라, 여러 instruction이 서로 다른 Stufe에 동시에 들어가 Durchsatz가 좋아지는 구조입니다.
문제는 instruction들이 독립적이지 않다는 점입니다. add t0, t1, t2 바로 뒤의 sub t3, t0, t4는 t0를 필요로 합니다. 앞 instruction이 값을 만들기 전에 뒤 instruction이 그 값을 쓰려고 하면 RAW data hazard가 생깁니다. branch는 다음 PC가 아직 확정되지 않은 상태에서 이미 다음 instruction을 가져오기 때문에 control hazard가 생깁니다.
핵심 규칙
- 먼저 표를 그립니다. 행은 instruction, 열은 cycle입니다. 기본은
IF ID EX MEM WB가 cycle마다 한 칸씩 오른쪽으로 이동합니다. - producer와 consumer를 찾습니다. producer는
rd에 값을 쓰는 older instruction이고, consumer는 그 register를 rs1 또는 rs2로 읽는 younger instruction입니다. - ALU 결과는 EX 끝에서 준비됩니다. 다음 instruction의 EX 입력으로 forwarding할 수 있으면 stall이 필요 없습니다.
lw의 loaded data는 MEM 끝에서 준비됩니다. 바로 다음 instruction이 그 값을 EX에서 쓰면 보통 1-cycle stall이 필요합니다.- taken branch에서 이미 가져온 younger wrong-path instruction은 stall이 아니라 flush입니다.
Visual Block: Forwarding, Stall, Flush
ALU -> ALU forwarding, no stall
Cycle: C1 C2 C3 C4 C5 C6
add t0,t1,t2 IF ID EX result MEM WB
sub t3,t0,t4 IF ID EX uses t0 MEM WB
^-------- Forward EX/MEM -> EX
결론: RAW dependency는 있지만 ALUResult가 제때 forwarding되므로 bubble은 0개입니다.
Load-use hazard, one stall
Cycle: C1 C2 C3 C4 C5 C6 C7
lw t0,0(sp) IF ID EX addr MEM data WB
add t1,t0,t2 IF ID hold stall EX uses t0 MEM WB
sub t3,t1,t4 IF hold stall ID EX MEM
^ bubble ^ MEM/WB -> EX
결론: `lw`의 EX 결과는 address일 뿐이고, 실제 loaded data는 MEM 뒤에 준비됩니다.
Taken branch, flush wrong path
Cycle: C1 C2 C3 C4 C5
beq s0,t0,done IF ID EX decide taken
addi s1,s1,1 IF ID -> FLUSH
addi s2,s2,1 IF -> FLUSH
done: add s3,s3,s0 IF ID EX
결론: PC 경로가 틀렸기 때문에 기다리는 것이 아니라 wrong-path instruction을 제거합니다.
Worked Example 1: ALU Forwarding
문제:
add t0, t1, t2
sub t3, t0, t4
or t5, t3, t6
풀이:
add는 t0를 쓰고 sub는 t0를 읽습니다. add -> sub RAW hazard입니다.sub는 t3를 쓰고 or는 t3를 읽습니다. sub -> or RAW hazard입니다.- 기본 timing grid를 그리면
add의 EX는 C3, sub의 EX는 C4, or의 EX는 C5입니다. - ALU 결과는 EX 끝에 준비되므로 C4의
sub EX로 add 결과를 forwarding할 수 있습니다. - 같은 이유로 C5의
or EX로 sub 결과를 forwarding할 수 있습니다.
정답·검산 확인
RAW hazard는 2개이지만 stall은 0개입니다. 마지막 WB는 C7입니다.
Worked Example 2: Load-Use Stall
문제:
lw t0, 0(sp)
add t1, t0, t2
sub t3, t1, t4
풀이:
lw -> add는 t0에 대한 RAW hazard입니다.- 이 hazard는 load-use입니다.
lw의 EX는 address를 만들고, loaded data는 MEM 끝에 나옵니다. add가 바로 C4 EX에 들어가면 너무 이릅니다. 그래서 IF/ID를 hold하고 EX에 bubble을 넣습니다.add의 EX를 C5로 미루면 lw data를 MEM/WB에서 EX로 forwarding할 수 있습니다.add -> sub는 ALU forwarding으로 해결됩니다.
정답·검산 확인
1-cycle stall이 필요하고 마지막 WB는 C8입니다.
Worked Example 3: Branch Flush
문제:
beq s0, t0, done
addi s1, s1, 1
addi s2, s2, 1
done:
add s3, s3, s0
branch decision이 EX에서 나고 branch가 taken이라고 가정합니다.
풀이:
beq가 C3 EX에서 taken 여부를 확정합니다.- 그때
addi s1은 ID에 있고 addi s2는 IF에 있습니다. - taken이면 두 instruction은 wrong path입니다.
- register state를 바꾸면 안 되므로 control을 무효화하고 flush로 표시합니다.
정답·검산 확인
addi s1, addi s2가 flush 대상입니다. beq 자체를 flush하는 것이 아닙니다.
Branch Prediction: 맞을 경로를 먼저 가져오기
입문 설명
Branch instruction이 EX 같은 뒤쪽 Stufe에 도착할 때까지 기다렸다가 다음 instruction을 fetch하면 Pipeline이 자주 비게 됩니다. Sprungvorhersage(Branch Prediction)는 branch 결과가 아직 확정되지 않았을 때 다음 PC를 먼저 추측합니다. 예측이 맞으면 이미 가져온 instruction을 계속 쓰고, 틀리면 wrong-path instruction을 Flush하고 올바른 PC에서 다시 시작합니다. 즉 prediction은 branch를 없애는 기술이 아니라 misprediction으로 인한 flush 횟수를 줄이는 기술입니다.
- 정적 예측(statische Sprungvorhersage): 실행 이력을 저장하지 않고 고정 규칙을 씁니다. 현재 강의의 예는 backward branch는 taken, forward branch는 not taken으로 예측합니다.
- 동적 예측(dynamische Sprungvorhersage): Branch Target Buffer 같은 구조에 이전 결과와 target을 저장하고 다음 예측에 씁니다.
- 1-bit predictor: 직전 결과를 그대로 다음 결과로 예측합니다. 반복 loop에서는 exit에서 한 번 틀린 뒤, 다음 loop 진입에서도 직전 exit 결과 때문에 다시 틀릴 수 있습니다.
- 2-bit predictor: 한 번의 반대 결과만으로 즉시 예측 방향을 바꾸지 않는 여러 상태를 사용합니다. 그래서 대부분 같은 방향이고 가끔 한 번만 반대가 되는 loop에 더 안정적입니다.
정확히 몇 instruction을 flush하는지는 branch decision이 어느 Stufe에서 나오는지에 따라 달라집니다. 이 강의 파일의 기존 5-stage 그림에서는 EX decision 예를 썼지만, 다른 문제에서는 반드시 주어진 Pipeline diagram을 우선합니다.
Worked Trace: forward beq의 실제 결과
현행 Übung 10의 다음 핵심 loop를 봅니다.
addi s0, zero, 0
addi t0, zero, 3
loop:
beq s0, t0, done
addi s0, s0, 1
j loop
done:
beq는 forward branch이므로 강의의 정적 규칙은 매번 N(not taken)을 예측합니다.
beq 실행 | 비교 전 s0 | 실제 결과 | 정적 예측 | 판정 |
|---|
| 1 | 0 | N | N | correct |
| 2 | 1 | N | N | correct |
| 3 | 2 | N | N | correct |
| 4 | 3 | T | N | misprediction |
정답·검산 확인
beq는 4회 실행, 실제 taken은 1회, 이 forward-not-taken 정적 규칙의 misprediction은 1회입니다. 검산은 s0=0,1,2,3 네 비교를 모두 적는 것입니다.
같은 N,N,N,T 결과에서 1-bit predictor의 초기 예측을 N이라고 명시하면 첫 세 번은 맞고 마지막 T에서 틀린 뒤 상태가 T로 바뀝니다. 같은 loop가 다시 시작되어 첫 결과가 N이면 직전 T 때문에 한 번 더 틀립니다. 2-bit predictor가 loop에서 보통 더 나은 이유가 이 단일 exit에 대한 hysteresis입니다.
변형 문제
addi t0, zero, 3
loop:
addi t0, t0, -1
bne t0, zero, loop
강의의 backward-taken 정적 규칙을 적용할 때 bne의 실제 결과와 misprediction 수를 구하세요.
정답·검산 확인
t0는 비교 시 2,1,0이므로 실제 결과는 T,T,N입니다. 예측은 세 번 모두 T라서 앞의 두 번은 맞고 exit의 N에서 한 번 틀립니다. 따라서 bne 실행 3회, taken 2회, misprediction 1회입니다.
Active Recall
Q1. Prediction과 Flush의 관계는 무엇인가요?
정답 확인
결과 확정 전에 다음 PC를 예측하고, 예측이 틀렸을 때만 이미 들어온 wrong-path instruction을 flush합니다.
Q2. 정적 예측과 동적 예측의 핵심 차이는 무엇인가요?
정답 확인
정적 예측은 고정 규칙을, 동적 예측은 해당 branch의 과거 실행 이력을 사용합니다.
Q3. 왜 2-bit predictor가 loop에서 1-bit보다 보통 안정적인가요?
정답 확인
loop exit의 한 번 다른 결과만으로 즉시 장기 예측 방향을 뒤집지 않기 때문입니다.
근거: current:Vorlesung\Rechnerorganisation - Teil 2.pdf, pages 103-105와 112-117; current:Uebung\Lösung 10.pdf, pages 4-5.
RAW, WAR, WAW와 Out-of-Order dependency
입문 설명
기본적인 in-order 5-stage 문제에서는 instruction이 program order로 움직이므로 주로 RAW(Read After Write)를 찾습니다. 그러나 Out-of-Order Mikroarchitektur는 준비된 younger instruction을 먼저 시작할 수 있으므로 register 이름을 둘러싼 세 종류의 순서를 모두 지켜야 합니다.
- RAW, true dependency: older instruction이 먼저 값을 써야 younger instruction이 그 값을 읽을 수 있습니다.
- WAR, anti-dependence: older instruction이 기존 값을 먼저 읽기 전에 younger instruction이 같은 register를 덮으면 안 됩니다.
- WAW, output dependence: 같은 register에 쓰는 두 instruction의 최종 write 순서가 뒤집히면 안 됩니다.
RAW는 실제 데이터 흐름입니다. WAR와 WAW는 같은 architectural register 이름을 재사용해서 생기는 name dependency입니다. 강의의 Registerumbenennung(register renaming)은 WAR/WAW 제약을 줄일 수 있지만, producer 값이 실제로 필요한 RAW를 제거하지는 않습니다. Out-of-Order는 “마음대로 순서를 바꿈”이 아니라, dependency를 위반하지 않는 준비된 instruction만 먼저 실행하는 방식입니다.
Worked Trace: dependency graph 만들기
강의의 Out-of-Order 예를 번호로 표시합니다.
I1: lw s8, 40(s0)
I2: add s9, s8, t1
I3: sub s8, t2, t3
I4: and s10, s4, s8
I5: or s11, t5, t6
I6: sw s7, 80(s11)
| 관계 | 종류 | 이유 |
|---|
| I1 → I2 | RAW on s8 | I2는 I1이 load한 옛 s8 값을 읽어야 함 |
| I1 → I3 | WAW on s8 | 두 instruction이 모두 s8에 쓰므로 architectural write 순서를 유지해야 함 |
| I2 → I3 | WAR on s8 | I2가 I1의 s8를 읽기 전에 I3가 새 s8를 쓰면 안 됨 |
| I3 → I4 | RAW on s8 | I4는 I3가 계산한 새 s8를 읽어야 함 |
| I5 → I6 | RAW on s11 | I6의 store address base가 I5의 결과임 |
따라서 I1–I4에는 dependency chain이 있지만 I5는 그 chain과 독립적으로 먼저 시작할 후보입니다. I6은 I5의 s11이 준비된 뒤에만 시작할 수 있습니다. 정확한 동시 실행 cycle은 issue width와 functional-unit 조건이 주어져야 정할 수 있으므로 여기서는 dependency graph까지만 닫힌 답으로 삼습니다.
검산법은 각 instruction 옆에 R={읽는 register}, W={쓰는 register}를 적고, program order의 두 instruction에 대해 older.W ∩ younger.R=RAW, older.R ∩ younger.W=WAR, older.W ∩ younger.W=WAW를 적용하는 것입니다.
변형 문제
다음 세 instruction의 모든 dependency를 분류하세요.
I1: add t0, t1, t2
I2: sub t1, t3, t4
I3: addi t0, t0, 1
정답·검산 확인
- I1 → I2: I1이 old
t1을 읽고 I2가 t1을 쓰므로 **WAR on t1**. - I1 → I3: I1이
t0을 쓰고 I3가 읽으므로 **RAW on t0**. - I1 → I3: 둘 다
t0을 쓰므로 동시에 **WAW on t0**. - I2와 I3 사이에는 공통 read/write register가 없으므로 이 세 분류의 dependency가 없습니다.
검산: I1 R={t1,t2}, W={t0}; I2 R={t3,t4}, W={t1}; I3 R={t0}, W={t0}.
Active Recall
Q1. RAW가 true dependency인 이유는 무엇인가요?
정답 확인
younger instruction이 필요로 하는 값 자체를 older instruction이 생산하기 때문입니다.
Q2. WAR에서 반드시 먼저 일어나야 하는 동작은 무엇인가요?
정답 확인
older instruction의 read가 younger instruction의 write보다 먼저 일어나야 합니다.
Q3. Register renaming이 줄일 수 있는 두 dependency는 무엇인가요?
정답 확인
register 이름 재사용 때문에 생기는 WAR와 WAW입니다. RAW 데이터 흐름은 남습니다.
Q4. Out-of-Order processor가 dependency가 없는 I5를 먼저 실행할 수 있다는 말은 program 결과 순서도 무시한다는 뜻인가요?
정답 확인
아닙니다. 실행 시작 순서는 바꿀 수 있어도 architectural dependency와 관찰 가능한 결과의 correctness는 유지해야 합니다.
근거: current:Vorlesung\Rechnerorganisation - Teil 2.pdf, pages 121-124; current:Uebung\Übung 11.pdf와 current:Uebung\Lösung 11.pdf, pages 1-3.
자주 틀리는 점
- RAW가 보이면 무조건 stall한다고 생각합니다. ALU-to-ALU는 forwarding으로 해결되는 경우가 많습니다.
lw의 EX 결과를 loaded data로 착각합니다. EX 결과는 effective address입니다.- stall과 flush를 같은 표시로 씁니다. stall은 맞는 instruction을 기다리게 하는 것이고, flush는 틀린 경로의 instruction을 제거하는 것입니다.
- x0 dependency를 hazard로 셉니다.
x0는 항상 0이고 write가 의미 없으므로 forwarding 조건에서도 보통 rd != x0를 확인합니다. - 1-bit predictor와 2-bit predictor를 “1개 branch와 2개 branch를 기억한다”로 오해합니다. 핵심은 한 번의 반대 결과에 예측 방향이 얼마나 쉽게 바뀌는가입니다.
- Out-of-Order를 program order를 무시해도 되는 구조라고 설명합니다. RAW/WAR/WAW dependency를 위반하지 않는 instruction만 먼저 시작할 수 있습니다.
Active Recall
Q1. 5-stage pipeline의 Stufe를 순서대로 말해 보세요.
정답 확인
IF, ID, EX, MEM, WB입니다.
Q2. add 바로 뒤의 sub가 add.rd를 읽으면 왜 stall이 보통 필요 없나요?
정답 확인
ALU 결과가 EX 끝에 준비되고 다음 cycle의 EX 입력으로 forwarding할 수 있기 때문입니다.
Q3. load-use hazard에서 왜 1-cycle stall이 필요한가요?
정답 확인
lw가 실제 loaded data를 MEM 끝에 얻기 때문에 바로 다음 instruction의 EX 시작에는 값이 아직 늦습니다.
Q4. taken branch에서 flush 대상은 누구인가요?
정답 확인
branch보다 younger이고 이미 잘못 가져온 sequential-path instruction입니다.
Source Grounding
current:Vorlesung\Rechnerorganisation - Teil 2.pdf, pages 88-105: pipeline hazards, forwarding, stalling, flushing.current:Vorlesung\Rechnerorganisation - Teil 2.pdf, pages 103-105와 112-117: Sprungvorhersage, static/dynamic prediction, 1-bit/2-bit loop behavior.current:Vorlesung\Rechnerorganisation - Teil 2.pdf, pages 121-124: Out-of-Order, RAW/WAR/WAW, scoreboard와 register renaming 예.current:Uebung\Übung 9.pdf와 대응 Lösung, pipeline timing, Forwarding, nops, Reordering, Flushing, execution-time comparison.current:Uebung\Lösung 10.pdf, pages 4-5: static/dynamic 및 1-bit/2-bit Sprungvorhersage와 beq 실행 횟수 예.current:Uebung\Übung 11.pdf와 current:Uebung\Lösung 11.pdf, pages 1-3: Out-of-Order에서의 RAW/WAR/WAW 정의와 RISC-V 예.- Branch penalty는 branch decision stage에 따라 달라질 수 있으므로, 정확한 penalty 숫자가 필요한 문제는 해당 Vorlesung diagram을 시각적으로 확인해야 합니다.