Control Hazards

Control Hazard, 또는 Branch Hazard(분기 위험)는 파이프라인 처리 중 분기 명령어(branch instruction)의 실행 여부가 확정되기 전까지, 어떤 명령어를 다음에 가져와야 할지 결정하지 못하는 상황에서 발생하는 문제를 의미한다.

파이프라인 구조의 프로세서는 성능을 극대화하기 위해 매 클럭 사이클마다 새로운 명령어를 가져와야(fetch) 한다. 그러나 조건 분기 명령어(beq, bne 등)의 경우, 분기가 실제로 발생할지 여부(branch outcome)는 프로그램의 실행 흐름에 따라 달라지므로, 분기 여부를 평가하기 전에는 어떤 명령어를 가져와야 할지 확신할 수 없다.

문제는 이 분기 결과가 파이프라인의 후반부 단계인 MEM 단계에서 결정된다는 점이다. 즉, 이미 그 이전에 가져온 명령어들이 실제로는 실행되지 않아야 할 수도 있는 것이다. 이로 인해 잘못된 명령어가 가져와지고(decode 및 execute까지 진행되는 경우도 있음), 결과적으로 파이프라인이 오염(pipeline pollution)되거나 불필요한 명령어들이 처리되며 성능 저하가 발생한다.

이러한 상황을 해결하기 위한 대표적인 기법은 다음과 같다:

• 분기 예측(Branch Prediction) : 하드웨어가 분기 결과를 미리 예측하고 그에 따라 명령어를 가져오는 방식, 예측이 틀릴 경우 파이프라인을 flush하고 다시 시작해야 한다.
• 파이프라인 지연 슬롯(Delayed Branch) : 분기 명령어 직후의 한 명령어는 항상 실행되도록 보장하며, 분기 지연에 의한 낭비를 줄이는 방식
• 조건 분기 결정(Early Branch Resolution) : 분기 결과를 가능한 빠른 단계(예: ID 단계)에서 결정하도록 하여, 불필요한 명령어 인출을 방지한다.

Branch Hazards

파이프라인 구조에서 제어 해저드(Control Hazard)는 분기(branch) 명령어의 실행으로 인해 다음 명령어의 흐름이 바뀔 수 있는 상황에서 발생한다. 대표적인 분기 명령어인 beq나 bne는 실행 결과에 따라 분기를 할 수도 있고, 하지 않을 수도 있으며, 이를 판단하기 전까지는 다음에 어떤 명령어를 실행해야 할지 알 수 없다.

MIPS의 기본 파이프라인에서는 beq 명령어의 조건 판별(두 레지스터 비교)과 분기 타겟 주소 계산이 MEM 단계에서 이루어진다고 가정하면, 그동안 파이프라인은 다음에 실행할 명령어가 무엇인지 모르기 때문에, 일단 순차적인 다음 명령어들을 가져오게 된다.

하지만 만약 분기 조건이 충족되어 실제로 분기가 일어나는 상황이라면, 이미 가져온 명령어들은 잘못된 명령어가 되며, 이를 버블(bubble) 또는 플러시(flush)해야 한다.

FLUSH? : 이미 IF/ID, ID/EX에 들어와 버린 잘못된 명령어들을 제거하는 것을 의미하며,
해당 명령어의 제어 신호를 모두 0으로 만들어 nop으로 처리한다.

Reduce Branch Delay : ID 단계에서 분기 결정

제어 해저드의 영향을 줄이기 위해, MIPS 파이프라인은 하드웨어적으로 개선을 시도할 수 있다. 그 방법은 분기 결과를 더 빠른 단계인 ID 단계에서 판단하도록 설계를 옮기는 것이다.

이를 위해 필요한 하드웨어 요소는 다음과 같다:

1. 타겟 주소 계산기(Adder)
   • PC + 4 + (sign-extended immediate << 2) 계산
   • 분기할 주소를 미리 계산해 둠
2. 레지스터 비교기(Comparator)
   • beq의 경우, 두 레지스터가 같은지를 판단하는 비교 연산기
   • 비교 결과가 참이면 분기를 수행한다.

이 하드웨어를 ID 단계에 배치하면, 분기 여부를 훨씬 빠르게 알 수 있어 잘못된 명령어를 덜 가져오게 되고, flush가 필요한 횟수가 줄어든다.

분기 명령어 수행 시 파이프라인의 실제 동작
파이프라인 구조에서 분기 명령어는 특별하다. 분기가 발생하면 다음에 실행될 명령어의 주소(PC)가 기존 흐름과 달라지기 때문이다. 이로 인해 분기 이후 이미 가져온 명령어가 무효가 되는 경우가 발생하고, 이때는 해당 명령어를 "버블(bubble)", 즉 nop 명령어로 대체해야 한다.

• 클럭 사이클 3(Cycle 3) : 분기 명령어 beq는 이제 ID 단계에 있다. 이 단계에서 분기 조건이 계산되어, 조건이 참이면 branch target Address(72)가 새로운 PC 값으로 설정된다. 동시에 이미 클럭ㄷ 사이클 3에서 fetch된 명령어는 잘못된 명령어이므로 무효화(=flush)된다.

• 클럭 사이클 4(Cycle 4) : 파이프라인의 IF 단계에서는 주소 72에 위치한 분기 대상 명령어를 fetch하게 된다. 그리고 ID 단계에는 flush된 명령어(nop)가 존재하게 되며, 이 nop은 실질적으로 아무 일도 하지 않는다.(보통 sll $0, $0, 0 이라는 형태로 표현된다.)

참고: flush된 명령어가 nop이므로, 이 명령어를 ID 단게에서 처리해야 할지 말아야 할지는 구현 방식에 따라 다를 수 있다.

사이클	IF 단계	ID 단계	설명
CC 3	명령어 44 fetch	beq ($40)	ID 단계에서 분기 결정됨
CC 4	명령어 72 fetch	flush된 nop	잘못 fetch된 명령어(44)는 무효화

36: sub $10, $4, $8
40: beq $1, $3, 7    # 분기 명령어, 조건 참이라면 → PC = 40 + 4 + (7 × 4) = 72
44: and $12, $2, $5  # 이 명령어는 분기가 일어나면 flush 되어야 함
48: or  $13, $2, $6  # flush
52: add $14, $4, $2  # flush
56: slt $15, $6, $7  # flush
...
72: lw  $4, 50($7)   # 분기 대상 명령어 (실제로 실행되어야 함)

위 예시에서는 beq 명령어가 분기하는 조건을 만족하기 때문에, 이후의 and, or, add, slt 명령어는 모두 플러시(flush)되어야 하며, 대신 주소 72에 있는 lw 명령어로부터 실제로 실행되어야 한다.

Data Hazards for Branches

분기 명령어(beq, bne)는 두 레지스터 값을 비교하여 분기 여부를 결정하므로, 비교 대상이 되는 레지스터의 값이 이전 명령어에서 갱신되는 경우, 데이터가 아직 준비되지 않았을 수 있다. 이 경우를 "Branch 명령어에서의 Data Hazard"라 하며, 분기 결정이 올바르게 수행되지 않을 수 있어 별도의 처리 방식이 필요하다.

Comparison Register가 바로 직전의 ALU 명령어나 두 번째 앞선 load 명령어의 목적지인 경우

add $1, $2, $3   # $1 갱신
add $4, $5, $6   # 독립적인 명령어
beq $1, $4, target  # $1을 비교에 사용

• 이 경우, $1은 add 명령어의 결과로 MEM 단계에서 계산된다.
• beq 명령어는 ID 단계에서 비교가 필요하므로, forwarding 기법을 통해 EX/MEM 레지스터 값을 ID 단계로 전달하면 stall 없이 hazard를 해결 가능하다.(forwarding으로 해결 가능)
  

직전 ALU 명령어가 비교 레지스터를 갱신하는 경우

add $1, $2, $3   # $1 갱신
beq $1, $4, target  # $1을 비교에 사용

• 이 경우, $1의 값은 아직 EX 단계에 있으며, beq 명령어는 곧 ID 단계에서 비교에 사용하려 한다.

• forwarding만으로는 타이밍이 맞지 않아, 1클럭의 stall이 필요하다.

  

직전 load 명령어가 비교 레지스터를 갱신하는 경우

lw $1, 0($2)     # $1 <- memory
beq $1, $0, target  # $1을 비교에 사용

• lw는 메모리로부터 데이터를 불러오므로, $1 값이 MEM 단계까지 지연된다.

• beq 명령어는 ID 단계에서 비교가 필요하므로, 이 경우 forwarding도 불가능하다.

• 따라서 beq는 2사이클 stall을 삽입해야 한다.

  

동적 분기 예측(Dynamic Branch Prediction)

현대 프로세서 아키텍처는 점점 더 깊은 파이프라인 구조를 가지며, 여러 명령어를 동시에 실행하는 슈퍼스칼라(Superscalar) 설계가 보편화되고 있다. 이러한 구조에서는 분기 명령어로 인한 파이프라인의 손실(branch penalty)이 더욱 치명적이다. 단 하나의 잘못된 분기 예측도 다수의 명령어 흐름을 무효화시키며, 성능 저하로 직결되기 때문이다.

이를 보완하기 위한 대표적인 기법이 바로 동적 분기 예측(Dynamic Branch Prediction)이다. 이 기법은 프로그램 실행 도중의 분기 명령어 결과를 관찰하고, 다음 번에 동일한 분기 명령어가 실행될 때 이전과 같은 결과(분기/비분기)를 기대하여 미리 결정하는 방식이다.

분기 예측 버퍼(Branch Prediction Buffer)

분기 예측의 핵심은 분기 예측 버퍼 또는 분기 이력 테이블(Branch History Table)이다. 이 테이블은 최근 실행된 분기 명령어들의 주소를 인덱스로 사용하여, 해당 분기 명령어의 과거 결과(taken 또는 not taken)를 저장하고 있다.

분기 명령어가 도달하면, 하드웨어는 이 테이블을 참조하여 이전과 같은 결과를 가정하고:

• 분기가 발생하지 않을 것으로 예상되면 -> 다음 연속 명령어(fall-through)를 인출한다.
• 분기가 발생할 것으로 예상되면 -> 분기 대상 주소로부터 명령어를 인출한다.

만약 이 예측이 틀렸을 경우, 파이프라인에 잘못 들어온 명령어들은 모두 flush하고, 해당 분기에 대한 예측 결과를 반다로 뒤집어 업데이트한다.

1-Bit Predictor: Shortcoming

간단한 구현으로는 1비트 예측기가 있다. 이 예측기는 해당 분기가 마지막에 ‘taken’(분기함)이었는지 ‘not taken’(분기하지 않음)이었는지만 저장하며, 다음 번 실행 시 이를 그대로 따르는 방식이다.

그러나 이 방식은 루프 구조에서 오작동하기 쉽다. 예를 들어, 반복 루프의 마지막에서 분기가 한 번은 분기하지 않게 되고, 다음 루프의 첫 번째 반복에서는 한 번은 분기하게 되는 상황이 반복된다. 그 결과, 1비트 예측기는 매번 루프의 끝과 시작에서 두 번의 예측 실패를 초래한다.

2-Bit Predictor

이러한 한계를 해결하기 위해 고안된 것이 2비트 예측기이다. 이 방식은 예측을 바꾸는 데 두 번의 실패가 있어야만 상태를 전환하는 방식이다. 즉, 한 번의 예측 실패로는 예측 상태를 바꾸지 않고, 연속된 두 번의 잘못된 예측이 있어야만 taken ↔ not taken 상태가 바뀐다.

이 덕분에 루프 종료나 반복 구조에서 발생하는 흔한 예측 실패를 줄일 수 있으며, 보다 안정적이고 신뢰성 있는 예측 성능을 제공한다.

분기 대상 주소 계산(Branch Target Calculation)

분기 예측을 통해 분기의 방향(taken/not taken)은 빠르게 결정할 수 있지만, 분기가 실제로 발생한다고 가정한 경우에는 분기 대상 주소(target address)를 계산해야만 해당 위치의 명령어를 가져올 수 있다.

이 주소 계산은 일반적으로 1사이클 정도의 시간이 추가로 소요되므로, 이를 줄이기 위해 Branch Target Buffer(BTB)라는 구조를 활용한다. BTB는 분기 명령어의 주소를 인덱스로 사용하고, 대응되는 분기 대상 주소를 캐시처럼 저장한다.

• 분기 명령어가 인출될 때 BTB를 조회하여 히트(hit)하면, 분기가 예측상 taken이라면, 즉시 해당 분기 대상 주소에서 다음 명령어를 인출할 수 있다.

이로 인해 실제 분기 명령어 실행 시 지연되는 시간을 최소화할 수 있으며, 전체적인 파이프라인 처리 속도도 향상된다.