분기 예측(branch prediction) - BHT, BTB, RAS

분기 예측(branch prediction)이 왜 필요하고 무엇인지 알아보고, RISC-V CPU인 SiFive E31이 분기 예측 방법인 BHT, BTB, RAS를 어떻게 사용하는지 알아보자.

이 포스팅에 어셈블리로 설명하는 부분이 있는데, 어셈블리 명령어가 궁금하면 아래 포스팅을 참고하자.

파이프라인 관련 내용을 알고 싶다면 아래 링크를 참고하자.

제어 해저드(control hazard)

현대 CPU는 성능을 위해 대부분 파이프라인(pipeline)을 사용한다. 파이프라인을 사용하면 구조적 해저드(structural hazard), 데이터 해저드(data hazard), 제어 해저드(control hazard)가 발생하는데, 분기 예측은 제어 해저드를 줄이기 위한 방법이다. 제어 해저드가 뭔지 알아보자.

아래 예제의 파이프라인 단계별 동작은 아래와 같다.
  • IF(instruction fetch) : 명령어를 fetch 한다.
  • ID(instruction decode) : fetch한 명령어를 decoding 한다.
  • EX(execute) : decoding한 명령어를 수행한다.
  • MEM : data memory에 접근한다.
  • WB : 수행 결과를 register에 write-back 한다.

stall 없는 파이프라인 예제
해저드가 없는 경우에는 명령어가 차례대로 파이프라인에 들어간다.

제어 해저드로 stall이 발생한 파이프라인 예제
반면에 분기 명령어가 있는 경우에는 어느 번지로 분기할지 EX 단계에서 결정되기 때문에 그 다음 명령어가 2 cycle stall 된다. 이렇게 분기문으로 인해 제어해저드가 발생한다.

분기 예측(branch prediction)

분기 예측은 제어 해저드를 줄이기 위한 방법으로써 분기 예측을 해서 예측 실행(speculative execution)을 한다.

분기문이 있지만 분기 예측이 성공하여 제어해저드가 없는 파이프라인 예제
beq 명령어는 EX 단계에서 분기가 결정되는데, 분기를 타지 않는다고 예측해서 4번지, 8번지 명령어를 예측 수행했다. beq 명령어의 EX 단계에서 분기 예측 성공이 확인되면 계속 명령어를 수행한다.

분기 예측이 실패해서 이미 실행한 명령어를 flush 하여 원상 복구하는 파이프라인 예제
beq 명령어의 EX 단계에서 분기 예측 실패가 확인되면 수행중인 4번지, 8번지의 명령어를 flush해서 원상 복구한다. 위의 예제에서는 flush 하는데 1 clock이 소모되었고, 분기 예측 실패시에 총 3 cycle penalty가 발생했다. flush 후에 beq 명령어로 인해 80번지로 분기해서 명령어를 수행한다.

SiFive E31의 분기 예측 방법

분기 예측은 이전의 분기 결과가 다음 분기에도 동일할 가능성이 높다는 점을 이용한다. 분기 예측 방법은 여러 가지가 있고 고성능 CPU일수록 복잡하고 정확한 분기 예측 방법을 사용한다. 그중에 RISC-V CPU인 SiFive E31에서 사용되는 분기 예측 방법을 알아보자.

SiFive E31은 SiFive homepage에 따르면 ARM의 Cortex-R4/R5의 대응 모델이다.
SiFive E31 manual은 아래 download link에서 받으면 된다.

아래는 SiFive E31 Manual에 있는 분기 예측 관련 내용이다.
  • 5단계 파이프라인을 가지고 있다.
    • instruction fetch (IF)
    • instruction decode and register fetch (ID)
    • execute (EX)
    • data memory access (MEM)
    • register write-back (WB)
  • 분기 예측기는 아래와 같이 구성되어 있다.
    • 동적 분기 예측(dynamic branch prediction)
      • A 28-entry branch target buffer (BTB), which predicts the target of taken branches.
      • A 512-entry branch history table (BHT), which predicts the direction of conditional branches.
      • A 6-entry return address stack (RAS), which predicts the target of procedure returns
    • 정적 분기 예측(static branch prediction)
      • conditional branch 명령어인데 한번도 타지 않은 경우에는 history가 없으므로 정적 분기 예측을 한다. 역방향 분기(backward branch)는 분기하고 순반향 분기(forward branch)는 분기하지 않는다.
  • 분기 예측기(branch predictor)는 IF 단계에서 동작하며, 분기 예측이 성공한 경우에는 penalty 가 없고 분기 예측이 실패한 경우에는 3 cycle penalty가 발생한다.
SiFive E31 manual에는 BHT, BTB, RAS 등의 분기 예측기의 세부 동작까지는 나와 있지 않아 위의 SiFive E31 manual 내용을 토대로 세부 동작은 아래에 추정해서 썼으니 참고 바란다.

추가로, RISC-V의 분기(branch) 명령어는 아래의 3가지 유형이 있으니 참고 바란다.
  • conditional branch : beq, bne, blt, bge, bltu, bgeu
  • unconditional jump
    • direct jump : jal
    • indirect jump : jalr

BHT(branch history table)

BHT는 conditional branch를 분기 예측한다.

branch history table update

conditional branch가 분기 여부가 EX 단계에서 결정되면 conditional branch 명령어에 해당하는 *PC[10:1]를 branch history table의 512 entry의 index로 사용해서 분기 여부(taken, not taken)를 update 한다. 이렇게 PC 값에 따라 하나의 entry로 mapping 하는 방법을 direct mapping이라고 한다. RISC-V는 모든 명령어가 4byte이나 compressed extension을 지원하는 경우에는 일부 명령어가 2byte로 압축되기 때문에 PC가 4 또는 2씩 증가하므로 PC의 하위 1bit는 항상 0이므로 하위 1bit는 제외하고 그 다음 bit부터 9bit를 index로 사용했다.

* PC(program counter)는 다음에 실행할 명령어의 주소를 가리킨다.

   4:	bnez	a4,100
명령어의 PC 값으로 branch history table의 index를 계산하는 방법

위의 어셈블리 코드 예제를 보면 PC 값은 4이고 PC[9:1]는 2이므로 branch history table의 index는 2가 되어 해당 위치에 분기 여부를 update 한다.


분기 예측

IF 단계에서 PC에 해당하는 명령어가 conditional branch 명령어면 PC[9:1]를 index로 사용해서 분기 여부(taken, not taken)를 확인해서 예측 수행을 한다. taken이면 명령어에서 decoding한 분기 주소로 분기를 하고 not taken이면 분기를 하지 않고 다음 명령어를 수행한다.

1-bit 예측 vs 2-bit 예측

branch history table의 entry에 분기 여부를 1bit로 표현하는 경우와 2bit로 표현하는 경우를 비교해보자.

<C 코드>
for (int i=0; i<5; i++) {
    // 뭔가를 수행
}
<어셈블리 코드>
   1000:	li	a4,5
   1004:	addi	a4,a4,-1
   1008:	# 뭔가를 수행
   100c:	bnez	a4,1004 # a4가 0이 아니면 1004번지로 분기
for 반복문을 위해 C 코드에서 up count를 썼으나 최적화 되면서 down count가 사용됐다. a4를 5에서 1씩 감소시키면서 a4가 0이 아니면 loop을 타고 아니면 loop을 탈출한다.

T : taken, N : not taken
예측 : N T T T T - N T T T T - N T T T T - ...
결과 : T T T T N - T T T T N - T T T T N - ...

1bit를 사용하는 경우는 1은 taken, 0은 not taken이며, 한 번이라도 분기 여부가 바뀌면 분기 예측이 변경되므로 어쩌다가 한 번 분기 결과가 바뀌는 경우에 분기 예측이 두 번 실패한다. 예제의 분기 예측 성공률은 60%이다.

2비트 분기 예측 상태 변화 방법
* reference : Computer Architecture: A Quantitative Approach Fifth Edition, Figure C.18

2bit를 사용하는 경우는 위의 그림과 같아서 두 번 연속으로 바뀌는 경우에만 분기 결과가 바뀌기 때문에 어쩌다가 한 번 분기 결과가 바뀌는 경우에 분기 예측이 한 번 실패한다.

T : taken, N : not taken
예측 : T T T T T - T T T T T - T T T T T - ...
결과 : T T T T N - T T T T N - T T T T N - ...

예제의 분기 예측 성공률이 80%이다. 3bit, 4bit 등으로 bit 수를 늘릴 수 있겠지만 2bit도 충분히 성능이 좋아서 보통 2bit를 사용하며 SiFive E31도 2bit를 사용한다고 추정한다.

분기 예측 실패

EX 단계에서 conditional branch의 분기 여부가 결정되면, 분기 예측이 틀린 경우에는 기존에 수행했던 것을 flush하고 올바른 분기를 수행한다.

branch history table의 index 충돌(collision)

PC[9:1]는 같으나 PC[31:10]이 달라도 branch history table의 같은 index로 mapping 되기 때문에 충돌이 발생한다. 충돌이 발생하면 분기 예측 성공률이 떨어질 가능성이 높다.
0004:	bnez  a4,100
...
1004:	beq   a2,1024
위의 예는 서로 다른 branch 명령어지만 PC[9:1]은 둘 다 2여서 branch history table의 index가 충돌한다.

BHT 분기 예측 실패율

BHT 분기 예측 실패율
* reference : Computer Architecture: A Quantitative Approach Fifth Edition, Figure C.20

위의 그래프를 보면 BHT의 entry가 4096개, 무제한인 경우의 2-bit prediction을 사용했을 때의 분기 예측 실패율이 나와 있다. etnry가 4096개인 경우나 무제한인 경우나 차이는 별로 없고, 분기 예측 실패율은 항목에 따라 0~18%이다.

BTB(branch target buffer)

BTB는 indirect jump를 분기 예측한다.

bnez  a4,100 # a4가 0이 아니면 100번지로 분기
위의 예제에서 분기 주소는 100번지이다. conditional branch의 분기 주소는 명령어에서 decoding하기 때문에 conditional branch의 taken, not taken만 알면 분기 예측을 할 수 있으므로 BHT로 분기 예측이 가능하다.

jalr  x1,a4,100 # (a4 + 100)번지로 분기
위의 예제에서 분기 주소는 (a4+100)번지이다. a4의 값에 따라 분기 위치가 달라진다. indirect jump는 명령어 decoding만으로 분기 주소를 알 수 없고 레지스터까지 읽어야 분기 주소를 알 수 있다. indirect jump는 분기 주소를 예측해야 하기 때문에 분기의 taken, not taken을 예측하는 BHT로 예측할 수 없고, BTB로 분기 예측이 가능하다.

branch target buffer update

BTB로 indirect jump뿐만 아니라 conditional branch도 분기 예측이 가능하다. 하지만 SiFive E31은 IF단계에서 분기 예측기인 BHT, BTB, RAS가 동시에 동작하며, BHT에서 conditional branch를 담당하기 때문에 BTB는 indirect jump만 담당한다고 추정했다.

branch target buffer를 mapping 하는 방법은 direct mapping, n-way set associative mapping, fully associative mapping 등을 사용할 수 있는데 entry가 28개 밖에 되지 않으므로 fully associative mapping을 사용했을 거라고 추정했다.

EX단계에서 indirect jump의 분기 주소가 계산되면 indirect jump에 해당되는 PC를 tag로 해서 분기 주소를 기록한다. 즉, 분기 주소를 기록할 때 28 entry의 아무 곳이나 저장한다. entry가 꽉 찬 경우에는 여러 방법이 있지만, 가장 오래된 entry를 지우고 새로운 PC와 분기 주소를 update 한다고 추정했다.

1004: jalr  ra,a4,100 # (a4 + 100)번지로 분기, a4 = 1000 이라고 가정
PC와 분기 주소로 이루어진 branch target buffer 예제
위의 어셈블리 코드 예제를 보면 해당 명령어를 수행해서 26번 entry에 PC값인 1004가 저장됐고 분기 주소에 [a4(1000) + 100] = 1100이 저장됐다.

분기 예측

IF 단계에서 PC를 tag로 branch target buffer에 matching 되는 entry가 있는지 확인해서 있으면 해당 주소로 분기한다.

분기 예측 실패

EX 단계에서 indirect jump의 분기 주소가 결정되면, 분기 예측이 틀린 경우에는 기존에 수행했던 것을 flush하고 올바른 분기를 수행한다.

분기 예측의 어려움

indirect jump가 사용되는 예를 몇 개 보면 C언어의 switch, 함수 return 이 있다. 가령 switch의 case가 5개라면 5가지의 주소 중에 하나로 분기한다. 그리고 함수 call이 한 군데라면 함수 return의 분기 주소는 하나지만 함수 call이 다섯 군데라면 함수 return의 분기 주소는 5가지다. conditional branch가 taken, not taken 두 군데 중에 하나로 분기하는 데 반해, indirect jump는 분기 주소가 많기 때문에 분기 예측 성공율이 떨어진다. 하지만 이중에 함수 return은 비교적 간단한 방법으로 분기 예측을 할 수 있다. 아래 내용을 보자.

RAS(return address stack)

함수 복귀시에 indirect jump 명령어를 사용하는데 BTB를 사용하면 분기 예측 실패율이 높기 때문에 해당 경우에는 RAS를 사용한다.

함수 호출 / 복귀 어셈블리 명령어

  b4:	74d1f0ef          	jal	ra,20000 <func1>
  b8:	00c12083          	lw	ra,12(sp)
...
00020000 <func1>:
 20000:	00008067          	ret
RAS 동작을 보기 전에 함수 호출 / 복귀가 어떻게 동작하는지 보자.
b4번지 jal 명령어를 통해 복귀할 주소인 b4(PC)+4를 ra 레지스터에 저장하고 func1 함수 위치인 20000번지로 분기한다. func1은 비어 있는 함수이기 때문에 바로 함수에서 복귀한다. 20000번지 ret는 의사 명령어이고 실제 명령어는 "jalr zero, ra, 0" 이다.(jalr 명령어도 복귀할 주소를 저장하는데, 복귀 주소를 저장할 레지스터로 zero 레지스터를 지정했으므로 저장하지 않는다. 함수 복귀 시에 이렇게 사용하며, zero 레지스터는 hard-wired 되어 0 값인 레지스터다.) ra+0 주소인 b8로 분기하여 함수에서 복귀한다.

return address stack push / pop

함수 호출 시에 EX 단계에서 함수 복귀 주소를 return address stack에 push 하고 함수 복귀 시에 IF 단계에서 return address stack에서 pop 해서 해당 번지부터 명령어를 예측 수행한다. return address stack entry가 무제한이라면 함수 복귀 분기 예측은 100% 성공한다. SiFive E31은 entry가 6개이므로 call depth 6개까지 성공하고 더 깊어지면 실패한다. 분기 예측이 틀린 경우에는 기존에 수행했던 것을 flush하고 올바른 분기를 수행한다.

void func1(void)
{
    func2();
}

void func2(void)
{
    func3();
}

void func3(void)
{
}
func1 함수를 호출했을 때 func1, func2, func3 각 함수의 복귀 주소가 return address stack에 어떻게 push / pop 되는지 보여준다
위의 C 코드 예제에서 func1 함수를 호출하면 func1, func2, func3 함수가 차례대로 호출되면서 차례대로 각 함수의 복귀 주소를 return address stack에 push 하고 func3, func2, func1 함수에서 차례대로 복귀하면서 함수의 복귀 주소를 return address stack에서 pop 한다.

RAS 분기 예측 실패율

RAS 분기 예측 실패율
* reference : Computer Architecture: A Quantitative Approach Fifth Edition, Figure 3.24

항목마다 다르지만 전박적으로 entry가 8개 정도 되면 실패율이 매우 낮아진다.

direct jump

  b4:	74d1f0ef          	jal	ra,20000 <func1>
위의 예제에서 분기 주소는 20000이다. 명령어만 decoding하면 분기 주소를 알 수 있으므로 따로 예측할 필요가 없다. IF 단계에서 분기 예측기가 바로 분기 주소를 계산해서 분기 주소에 해당하는 명령어를 다음에 바로 수행한다.


정적 분기 예측(static branch prediction)

BHT의 entry가 아직 채워지지 않은 경우(해당 branch를 한 번도 타지 않아서 아직 history가 update 되지 않은 경우)에는 정적 분기 예측을 한다.

<C 코드>
for (int i=0; i<5; i++) {
    // 뭔가를 수행
}
<어셈블리 코드>
   1000:	li	a4,5
   1004:	addi	a4,a4,-1
   1008:	# 뭔가를 수행
   100c:	bnez	a4,1004 # a4가 0이 아니면 1004번지로 분기
반복문은 프로그램에서 매우 많이 쓰이는데, 위의 예제의 for 반복문을 보면 100c번지의 bnez는 1004번지로 분기하는 역방향 분기이며, 역방향 분기를 4번 타고 마지막에 1번 역방향 분기를 타지 않는다. 이런 특성을 이용해서 정적 분기 예측은 역방향 분기는 taken으로 예측하고 순방향 분기는 not taken으로 예측한다.

전체 동작

IF 단계에서 branch prediction이 동작한다.
- 먼저 PC 값을 tag로 해서 BTB에 해당 entry가 있는지 확인한다.
  : YES : 해당 주소로 분기한다.
  : NO : 명령어를 decoding 해서 conditional branch 인지, 함수 복귀인지, direct jump인지 확인한다.
     > conditional branch
       - PC 값에 해당하는 entry가 BHT에 있는지 확인한다.
         : YES : 해당 entry의 분기 여부 기록에 따라 분기하거나 하지 않는다.
         : NO : 정적 분기 예측을 한다. 역방향 분기이면 분기하고 순방향 분기이면 분기하지 않는다.
     > 함수 복귀 : RAS에서 함수 복귀 주소를 pop 해서 해당 주소로 분기한다.
     > direct jump : 명령어를 decoding 해서 해당 주소로 분기한다.

정리

제어 해저드를 줄이기 위해 분기 예측이 사용된다. 분기 예측 방법은 여러가지가 있는데 그 중에 SiFive E31의 분기 예측기에서 사용하는 BHT, BTB, RAS, 정적 분기 예측이 같이 어떻게 동작하는지 알아봤다.

* Feedback은 언제나 환영합니다.

Comments

Post a Comment