[컴퓨터 구조] 4.9 제어 해저드(Brach Hazard Exception)

'컴퓨터 구조 및 설계 MIPS edition 제 6판' 교재와 국민대학교 임은진 교수님의 강의를 바탕으로 정리한 글입니다.
정리 과정에서의 오류 및 오타가 있을 수 있습니다 :)

Pipeline hazards란?

파이프라인 프로세서에서 명령어의 수행이 끝나기 전에 다른 명령어의 수행이 시작되기 때문에 생기는 문제를 말한다.

• 파이프라인의 종류 3가지
  • Structure hazards -> 회로를 바꾸어 해결
  • Data hazards -> data forwarding(bypassing)으로 해결
  • Control hazards -> 어떻게 해결할까?

이번 글에서는 Pipeline hazard 중에서도 Control hazards에 대해 알아보자

Brach 명령은 flow of control을 변경하므로 Fetch 할 다음 명령어의 주소는 branch 조건에 따라 달라진다.
하지만 branch의 여부는 MEM 파이프라인 단계에 가서 이루어지므로 인출할 명령어가 늦게 결정되는 문제가 발생한다. 이를 Control hazard 혹은 Branch hazard라고 한다.

Control hazard를 해결하는 방법은 두 가지가 있다. 첫 번째 방법은 pipeline stall이다. 단순히 분기가 끝날 때까지 파이프라인을 지연시키는 것이다. 이 방법은 간단하지만 너무 느리기 때문에 성능을 매우 악화시킨다. 더 좋은 해결책은 branch prediction이다. 

• Control hazards의 해결방법
  • pipeline stall
    -> 단순히 분기가 끝날 때까지 파이프라인을 지연시키는 것. 너무 느려지므로 좋은 방법이 x
  • branch prediction

Branch Prediction?

branch가 일어나지 않는다(not taken)고 예측하고 명령어를 순서대로 계속 실행하는 것을 Branch Prediction이라고 한다.
branch가 일어난다면 -> ID, IF, EX 단계에 있는 명령어들을 버리고 BTA의 명령어를 실행해야 한다.
현재 파이프라인에 있는 명령어를 버린다는 것은 Control value들을 모두 0으로 바꾸는 것이다. 이를 Flush한다고 한다.

Branch Delay를 줄이기 위해서 하드웨어를 고칠 수 있는데, 방법은 아래와 같다.

• BTA adder를 ID stage로 옮기기
• Register Comparator를 ID stage로 옮기기

branch delay를 줄이기 위해 수정된 회로

위 이미지에서 주황색으로 표시된 부분이 회로가 변경된 부분이다.

먼저 BTA adder를 ID stage로 옮기는 것에 대해 알아보자.
IF/ID 파이프라인 레지스터에는 이미 PC값과 수치 필드가 들어있으므로, BTA adder를 EX stage에서 ID stage로 옮기면 된다. 이렇게 수정하면 IF.Flush에는 branch instruction의 immediate field에 저장된 offset value도 함께 넘어간다. 이게 PC 값에 더해져서 BTA에 해당하는 instruction이 바로 Fetch될 수 있게 된다.

다음으로는 Register Comparator를 ID stage로 옮겨야 한다. 이렇게 하드웨어를 수정하면 branch instruction이 ID stage에 왔을 때, Register Comparator에 의해 값이 같은지, 다른지를 판단한다. 두 레지스터 값을 bitwise 연산하여 값이 같으면 1, 아니면 0을 넘긴다.

branch instruction이고, Register Comparator에 의해 값이 1이면 IF.Flush가 1이 되어 IF/ID의 instruction 부분에 0x00000000가 써진다. 이는 nop를 의미하며 아무것도 수행하지 않고 지나가게 된다.

 

그런데 여기서 Data hazards가 발생할 수도 있다. branch instruction에서 사용하는 레지스터와 의존성이 있는 레지스터가 위에서 사용될 수 있기 때문이다. 아래 그림으로 ALU instruction 이후에 branch instruction이 등장하여 hazard가 발생한 상황을 볼 수 있다. 이는 다른 data hazard처럼 똑같이 forwarding으로 해결할 수 있다. 

branch 명령어를 수행하면서 발생한 data hazard를 data forwarding으로 해결하였음

---

하지만 만약 아래 그림과 같이 lw 명령어와 함께 발생한 data hazard라면 한 번의 stall이 필요하다.

lw 명령어와 함께 발생한 data hazard는 1번의 stall 후 forwarding을 통해 hazard를 해결한다.

---

더 나아가 아래 그림처럼 lw 명령어 바로 아래에 branch 명령어가 온다면, 이때는 2번의 stall이 필요하다.

바로 앞에서 수행된 lw 명령어와 함께 발생한 data hazard는 2번의 stall 후 forwarding을 통해 hazard를 해결한다.

---

그렇다면 이제 bracn prediction 방법에 대해서 알아보자.

Static Branch Prediction (정적 분기 예측)

일반적인 브랜치에 기반하고, runtime에 결정된다. 반복문일 경우에는 branch가 '일어난다'고 예측하고, if문의 경우에는 branch가 '일어나지 않는다'라고 예측하면 된다.

Dynamic Branch Prediction(동적 분기 예측)

이 방법은 정적 분기 예측보다 더 많이 쓰이고 효과적이다. 이름에서도 알 수 있듯이 dynamic이므로 수행하면서 결정한다. 이 방법은 명령어 주소를 조사해서 이 branch 명령어가 지난번에 실행되었을 때 branch를 했는지 알아보는 것이다. 만약 branch가 일어났다면 지난번과 같은 주소에서 새로운 명령어를 가져오도록 한다.

이 방법은 Branch Prediction Buffer(aka Branch History Table)를 이용해서 구현된다. Branch Prediction Buffer란 branch 명령어의 하위 주소에 의해 인덱스되는 조그만 메모리이다. 이 메모리에는 지난번 실행 시에 branch가 일어났는지 안 일어났는지를 나타내는 비트가 있다. 약자로 BPB라고 부르겠다.

---

먼저 1비트 예측 방법에 대해 알아보자.

10번 반복하는 for-loop 안에 10번 반복하는 inner for-loop가 있다고 해보자. 처음에 BPB는 1이고 taken(branch한다, 분기한다)으로 예측한다. Branch Prediction(BP)을 통해서 BPB의 성공과 실패를 기록한다.

반복문이 시작되어 0번째 outer-loop에 들어온 후 inner for-loop의 반복이 먼저 시작된다. 10번 반복할 것이므로, 9번 branch를 해야한다. 따라서 BPB는 9번의 예측을 성공한다. 그런데 마지막 9번째는 실패이다. inner for-loop의 반복이 10번 모두 완료되었으므로 더 이상 branch를 해서 되돌아가지 않고 반복문을 나가야하는데 BPB는 다시 branch할 것이라고 예측했기 때문이다. 그래서 BP에는 BPB가 한 번 실패한 것이 기록된다. 예측이 실패했으므로 BPB의 값은 업데이트된다. taken으로 예측하고 있었는데, 이제는 untaken으로 업데이트 되었다.

이제는 그 다음 1번째 outer for-loop의 반복을 수행하면서 다시 inner for-loop에 진입한다. 하지만 BPB의 예측은 untaken이므로 첫번째부터 BPB는 실패한다. BP에 실패 1번이 기록되고, BPB는 다시 taken으로 업데이트된다. 그 뒤에는 위와 같은 논리로 BPB는 8번의 예측을 성공한다. 그리고 마지막 반복에서는 예측이 taken이고, 실제가 untaken이기 때문에 실패한다.

이렇게 다음 반복부터는 시작할 때 한 번 실패, 끝날 때 한 번 실패한다. 이렇게 매 loop마다 두 번씩 fail한다.

아래는 inner for-loop에 대한 branch instruction의 주소를 가지고 있는 BPB의 값을 표로 나타내어 본 것이다. 표의 아래는 생략되어 있다.

Outer Loop	Inner Loop	예측	결과	BPB	success	fail
0	0	taken	taken	1 (taken)	1	0
	1	taken	taken	1	2	0
	2	taken	taken	1	3	0
	3	taken	taken	1	4	0
	4	taken	taken	1	5	0
	5	taken	taken	1	6	0
	6	taken	taken	1	7	0
	7	taken	taken	1	8	0
	8	taken	taken	1	9	0
	9	taken	not taken	0 (update!)	9	1	success: 9 fail : 1
1	0	not taken	taken	1 (update!)	9	2
	1	taken	taken	1	10	2
	2	taken	taken	1	11	2
	3	taken	taken	1	12	2
	4	taken	taken	1	13	2
	5	taken	taken	1	14	2
	6	taken	taken	1	15	2
	7	taken	taken	1	16	2
	8	taken	taken	1	17	2
	9	taken	not taken	0 (update!)	18	3	success: 8 fail: 2
2	0	not taken	taken	1	18	4

 

---

하지만 1 bit prediction 방법은 잘못된 예측을 하는 경우가 많을 수 있어서 성능이 좋지 못하다. 따라서 2비트 예측 방법을 이용하는 것이 더 좋다. 

 

그럼 아까 1비트 예측 방법으로 들었던 예시를 2비트 예측에서도 적용해보고, 정확도를 비교해보자.
BPB는 00에서 시작한다. 0번째 inner for-loop을 마치니 예측과 일치한다. 여전히 00이다. 이를 반복해서 9번째 반복이 끝났다. 이때 BPB의 예측은 taken인데 실제로는 not taken이었다. BPB는 01이 된다. 여기까지해서 BP에는 9번의 성공과 1번의 실패가 기록되어 있다.
첫 번째 outer for-loop를 마치니 예측도 taken(01), 실제로는 taken이었다. 01에서 10이 된다. 두 번째 반복에서는 예측은 not taken(10), 실제로는 taken이었다. BPB는 10에서 다시 01이 된다. 반복문을 계속 돌면서 01과 10으로 바뀌는 것이 반복된다.

Outer Loop	Inner Loop	예측	결과	BPB	success	fail
0	0	taken	taken	00	1	0
	1	taken	taken	00	2	0
	2	taken	taken	00	3	0
	3	taken	taken	00	4	0
	4	taken	taken	00	5	0
	5	taken	taken	00	6	0
	6	taken	taken	00	7	0
	7	taken	taken	00	8	0
	8	taken	taken	00	9	0
	9	taken	not taken	01 (update!)	9	1	success: 9 fail: 1
1	0	taken	taken	00 (update!)	10	1
	1	taken	taken	00	11	1
	2	taken	taken	00	12	1
	3	taken	taken	00	13	1
	4	taken	taken	00	14	1
	5	taken	taken	00	15	1
	6	taken	taken	00	16	1
	7	taken	taken	00	17	1
	8	taken	taken	00	18	1
	9	taken	not taken	01 (update!)	19	2	success: 9 fail: 1
2	0	taken	taken	00 (update!)	20	2

이렇게 1비트 대신 2비트를 사용하면 예측이 틀리는 경우를 한 번으로 줄일 수 있다.