[컴퓨터구조] 프로세서 3. RISC-V Hazard (Data, Control)

CSE/컴퓨터구조

[컴퓨터구조] 프로세서 3. RISC-V Hazard (Data, Control)

minkylee 2024. 6. 15. 15:50

Data Hazard

만약 다음과 같은 명령어가 있다고 하자

sub x2, x1,x3
and x12,x2,x5
or x13,x6,x2
add x14,x2,x2
sd x15,100(x2)

모든 실행 결과들이 x2의 결과에 의존하고 있는 것을 알 수 있다.

and 명령어와 or 명령어는 x2 값이 결정되기도 전에 x2를 사용하기 때문에 data hazard가 발생한다.

이를 앞서 배웠던 파이프라인으로 구현하면 다음과 같다.

이를 Datapath에서는 어떻게 처리해야 할까

Detecting the Need to Forward

Data Hazard는 Forward 기법을 이용하여 해결한다.

그렇다면 우선 Forward가 필요한 상황부터 검사해야 한다.

EX/MEM Register RD = ID/EX Register RS1
- 설명 : Execute 단계에서 계산된 결과가 다음 명령어의 첫 번째 소스 레지스터(RS1)에 필요하다.
EX/MEM Register RD = ID/EX Register RS2
- 설명 : Execute 단계에서 계산된 결과가 다음 명령어의 두 번째 소스 레지스터(RS2)에 필요하다.

sub x2, x1, x3
and x12, x2 ,x5

// EX/MEM Register RD = ID/EX Register RS1 의 예시

MEM/WB Register RD = ID/EX Register RS1
- 설명 : Memory Access 단계에서 계산된 결과가 두 번째 이후 명령어의 첫 번째 소스 레지스터(RS1)에 필요하다.
MEM/WB Register RD = ID/EX Register RS2
- 설명 : Memory Access 단계에서 계산된 결과가 두 번째 이후 명령어의 두 번째 소스 레지스터(RS2)에 필요하다.

sub x2, x1, x3
and x12, x2 ,x5
or x13, x6, x2

// or 명령어에서 봤을 때의 MEM/WB Register RD = ID/EX Register RS2 상황

위 두개는 바로 이전의 stage에서 dependancy가 발생한 상태이므로, EX/MEM에서 forward를 해야 한다.

아래의 두개는 이전 이전의 stage에서 dependancy가 발생한 상태이므로 MEM/WB에서 forward를 해야한다.

하지만 만약 바로 위 명령어가 Register에 Wirte를 하지 않는다면 아무 의미도 없을 것이다.

ex.

명령어1: sd x1, 0(x2) (x1 값을 x2가 가리키는 메모리 위치에 저장)
명령어2: sub x1, x4, x5 (x3 = x4 - x5)

// 이 경우 명령어 2가 실행될 때 명령어 1의 값을 사용하지 않으므로 forwarding이 필요 없다.
// 그렇다면 forwarding이 필요한 경우는 실제로 레지스터의 값을 쓰는 load와 R-format이 있다.

따라서 아래의 검사도 추가로 진행한다.

EX/MEM RegWrite, MEM/WB RegWrite

만약 RD의 번호가 0이라면 zero register에 넣는 것으로 아무 의미가 없기 때문에 해당 조건도 검사한다.

EX/MEM Register RD != 0
MEM/WB Register RD != 0

따라서 dependancy가 발생했는지 확인하는 조건 하나, 실제로 데이터가 Register에 입력되는지 확인하는 조건 둘

총 3개의 조건을 만족해야 Forwarding을 한다.

R-Type의 경우에는 EX/MEM과 MEM/WB의 값이 같다. (완벽히 같은 건 아님)

그렇기 때문에 EX/MEM의 값이 ID/EX로 Forward를 할 수 있는 것

Forwarding unit이 보내는 신호는 위와 같다.

이 표는 ALU에서 사용할 피연산자가 어디에서 오는지를 제어하기 위해 사용한다.

ALU가 연산할 때 어떤 값을 사용할지를 결정하는 것

ForwardA : ALU의 첫번째 피연산자의 값 제어
ForwardB: ALU의 두번째 피연산자의 값 제어
00 : 레지스터 파일에서 가져와라
10: 이전 ALU 결과에서 포워딩된다.
01: 데이터 메모리에서 가져오거나, 더 이전의 ALU결과에서 포워딩된다.

ex.

명령어1: add x5, x1, x2는 x1과 x2를 더해서 x5에 결과를 저장합니다.
명령어2: sub x6, x5, x3는 x5와 x3를 빼서 x6에 결과를 저장합니다.
명령어3: or x7, x6, x4는 x6과 x4의 논리합(OR)을 계산하여 x7에 결과를 저장합니다.

이런 예시가 있다고 할 때

명령어 1은 포워딩이 필요가 없다. -> x1, x2는 레지스터 파일에서 읽는다.

Forwarding unit의 값 : ForwardA = 00, ForwardB = 00

명령어 2는 명령어 1의 결과를 필요로 한다. (EX/MEM 레지스터에 있을 때)

Forwarding unit의 값 : ForwardA = 10, ForwardB = 00

명령어 3은 명령어 2의 결과(x6) 이 필요하다. (EX/MEM에 있을 때)

Forwarding unit의 값 : ForwardA = 10, ForwardB = 00

경우의 수를 나눠보면 다음과 같다.

R-format의 rd 값을 바로 다음 명령어의 rs1 또는 rs2에서 사용하는 경우

포워딩 신호: 10 (EX/MEM 레지스터에서 포워딩)

R-format의 rd 값을 다음 다음 명령어의 rs1 또는 rs2에서 사용하는 경우

포워딩 신호: 01 (MEM/WB 레지스터에서 포워딩)

Load의 rd 값을 다음 다음 명령어의 rs1 또는 rs2에서 사용하는 경우

포워딩 신호: 01 (MEM/WB 레지스터에서 포워딩)

Load의 rd 값을 다음 store 명령어의 rs2에서 사용하는 경우

포워딩 신호: 01 (MEM/WB 레지스터에서 포워딩)

Store 명령어의 주소를 계산하기 위해 이전 명령어의 결과가 필요한 경우

포워딩 신호: 10 (EX/MEM 레지스터에서 포워딩) 또는 01 (MEM/WB 레지스터에서 포워딩)

Double Data Hazard

만약 다음과 같은 명령어가 들어왔다고 생각해보자

add x1 ,x1,x2
add x1 x1 ,x3
add x1, x1 ,x4

보기만해도 정말 복잡하다.

각각의 명령어는 x1을 업데이트하고, 다음 명령어는 이 업데이트 된 값을 이용한다.

각각의 명령어는 어디서 가져와야 할까?

이전 ALU 결과에서 가져오는 것을 EX 단계에서의 Forwarding이라고 하고

데이터 메모리나 더 이전 ALU 결과에서 가져오는 것을 MEM 단계에서의 hazard 라고 할 때 각각의 명령어는 조건에 따라 Fowording 값을 가져와야 한다.

조건 : EX 해저드 조건이 참이 아닐때 MEM 해저드 조건이 사용된다.

첫 번째 명령어는 hazard가 발생되지 않는다.
두 번째 명령어는 EX 단계에서의 Forwarding 발생한다. -> ForwardA = 10
세 번째 명령어는 EX 단계에서의 Forwarding 발생한다 -> ForwardA = 10

어? 근데 세 번째 명령어는 MEM단계에서의 hazard도 발생된다. 조건이 없었다면 잘못된 데이터를 참조하는 일이 발생할 뻔 했다.

가장 최근의 결과를 사용하려면, EX/MEM Forwording 이 우선이고, 필요 시 MEM/WB Forwarding을 사용한다.

Load-Use Hazard Detection

Load-Use Data Hazard는 앞서 얘기한 Forwarding 방식으로는 해결할 수 없다.

Memory에서 값을 읽기 때문이다. -> 정상적인 값은 MEM/WB Register에 들어있다.

이런 경우에는 어쩔 수 없이 Pipeline stall 을 해야한다.

그렇다면 최대한 빨리 stall을 하는 것이 손실을 줄일 수 있다!

ID/EX MemRead = 1 (현재 실행중인 명령어가 메모리에서 데이터를 읽어야 한다는 것, load 인 경우)
ID/EX Register RD = IF/ID Register RS 1 (현재 load 명령어의 목적 레지스터가 다음 명령어의 RS1일 때)
ID/EX Register RD = IF/ID Register RS 2 (현재 load 명령어의 목적 레지스터가 다음 명령어의 RS2일 때)

ID 단계 (명령어 해독) 에서 해당 조건을 만족한다면 stall을 진행

stall을 하기 위해서는 두 가지의 행동이 필요하다.

PC의 업데이트를 막고, IF/ID pipeline Register의 업데이트를 막는다.
ID/EX Register의 값을 모두 0으로 만든다. (레지스터 값과 제어 신호 둘 다)

우선 PC, IF/ID Register의 업데이트를 막아야 한다. (새로운 명령어가 들어오지 않게 하고 현재 명령어를 계속 해독하도록)

다만 그렇다 해도, ID Stage에서는 Instruction Decode를 진행하고, IF Stage에서는 다시 한 번 명령어를 반입한다.

또한 ID/EX Register의 값을 0으로 만드는데, 이렇게 해야만 뒷 단계에서는 아무것도 하지 않기 때문이다.

따라서 EX, MEM, WB stage에서는 아무것도 하지 않는다.

Data Hazard가 발생하면 기존의 Register 값은 아무런 쓸모가 없기 때문이다.

IF/ID register에서 Hazard detection unit으로 신호를 보내면, 해당 unit에서 stall을 결정한다.

만약 stall을 하기로 결정했다면, 첫 번째로 PC의 update를 막고, 두 번째로 ID/EX Register를 모두 0으로 초기화한다.

네모칸의 MUX는 Control 신호를 보낼 것인가, 아니면 0으로 초기화 할 것인가를 결정한다.

만약 PC Write 신호가 0이라면 Update를 하지 않는다.

Control Hazard

Branch는 MEM Stage에 도달하기 전까지 발생하지 않는다.

따라서 만약 Branch를 해야한다, MEM Stage의 이전의 모든 Stage 값을 날려야한다.

하지만 ID Stage에서 미리 비교를 함으로써 한 번의 Stall로 손실을 최소화 할 수 있다.

36: sub x10, x4, x8
40: beq x1, x3, 16 // PC relative branch
			// to 40+16*2=72
44: and x12, x2, x5
48: orr x13, x2, x6
52: add x14, x4, x2
56: sub x15, x6, x7
72: ld x4, 50(x7)

Branch 명령어를 빠르게 처리하기 위해 하드웨어를 이동한다. 다음 두 가지를 ID Stage에 추가하면 된다.

Target Address Adder
- 브랜치 명령어가 분기하는 주소를 계산한다.
Register comparator
- 브랜치 조건을 평가한다.

다음과 같이 실행하게 된다.

40: beq x1, x3, 16 명령어 해독
브랜치 조건 계산 : x1, x3 이 같으면 분기한다.
타겟 주소 계산 => 현재 주소가 40이고 offset이 16이므로 타겟 주소는 72
분기 여부 결정 : 2번 계산 결과가 같다고 나오면 PC는 72로 설정된다, 그렇지 않다면 다음 명령어 주소인 44로 진행된다.

Datapath로 확인해보자

파란색 네모가 Branch 여부를 ID Stage에서 결정하기 위해 새로 생긴 Unit이다.

맨 우측이 조건을 평가하는 Register comparator 이고 그 전 네모가 target 주소를 계산하는 Target Address Adder이다.

ALU에서는 zero signal이 사라진 것을 볼 수 있다.

Data Hazards for Branches

comparison register가 두 번째 혹은 세번째 앞에 있는 ALU 명령어의 목적 레지스터 (rd)일 때 Data Hazard가 발생할 수 있다.

그러나 이는 forwarding으로 해결이 가능하다.

하지만 위와 같이 load 명령어와 ALU 명령어 뒤에 붙어 온다면 어쩔 수 없이 1번의 stall이 필요하다.

load 뒤에 바로 온다면 2번의 stall이 필요하다.

Dynamic Branch Prediction

앞에서 알아본 Dynamic Branch Prediction 을 더 자세히 살펴보자!

분기 패널티를 줄이기 위해 동적 분기 예측을 사용한다.

분기 명령어의 실행 결과를 미리 예측하여 분기 예측 결과에 따라 명령어를 미리 가져오는 것

Branch Prediction Buffer : 최근 분기 명령어의 주소를 인덱스로 사용하여 분기 결과(실행 결과)를 저장하는 테이블이다.
Index : 최근 분기 명령어의 주소로 테이블에 접근한다.
Stores outcome : 분기 명령어가 실행되었을 때의 결과를 저장한다. (taken, not taken)

분기 명령어가 실행되면

테이블 확인 : 분기 명령어를 실행할 때, 분기 예측 버퍼에서 해당 명령어의 주소를 확인한다.
동일한 결과 예상 : 테이블에 저장된 이전 결과(분기 결과)가 taken이면 이번에도 taken으로 예상한다.
명령어 가져오기 : 예상 결과에 따라 다음 명령어를 가져오기 시작한다.

예측이 틀렸을 경우

파이프라인 플러시 : 잘못된 예측으로 인해 파이프라인에 들어간 명령어들을 비운다.
예측 뒤집기 : 예측 결과를 반대로 바꾼다.

깊은 파이프라인과 super scalar pipeline에서는 분기 패널티가 더 크기 때문에 이를 줄이기 위해 Dynamic Branch Prediction을 사용한다.

1-Bit Predictor: Shortcoming

1비트 예측기는 각 분기 명령어에 대해 두 가지 상태를 가진다

Taken(1) : 분기가 발생할 것으로 예측
Not Taken(0) : 분기가 발생하지 않을 것으로 예측

분기 명령어가 실행될 때 예측기는 현재 상태를 확인한다.

예를 들어 현재 상태가 Taken이라면, 예측기는 분기가 발생할 것으로 예측하고 분기 타겟 주소로 명령어를 가져온다.

상태가 Not Taken이라면 예측기는 분기가 발생하지 않을 것으로 예측하고, 다음 연속된 명령어 주소로 명령어를 가져온다.

그리고 예측이 맞았으면 상태를 유지하고 예측이 틀렸으면 상태를 반전시킨다.

하지만 이렇게 설계한다면 루프의 마지막 반복과 첫 번째 반복에서 예측이 틀리기 쉽다.

(루프 안에서는 Taken, 나갈 때 Not Taken, 다음 루프 들어갈 때 다시 Taken 으로 바뀌기 때문에)

2-Bit Predictor

위와 같은 문제를 해결하기 위해 2-Bit Predictor를 만들었다. 2-Bit Predictor는 2개의 비트를 사용해 4개의 상태를 표현한다.

초기 상태 Strongly taken 가 예측이 틀렸을 경우 바로 not taken 상태로 가는 것이 아닌 Weekly Taken(약하게 taken) 으로 바뀐다.
여기서 한 번 더 예측이 틀리면 Strongly Not Taken(약하게 Not taken) 으로 변경된다.
반대의 경우도 같다.
예측을 더 안정적으로 만들기 위해 두 번 연속으로 틀린 예측이 있어야 예측을 바꾸는 방식이다.

Calculating the Branch Target

예측기가 Taken이라고 예측했는데 실제로는 Not Taken 일 결루 1 cycle panelty 가 발생한다.

그래서 Branch Target Buffer(분기 대상 버퍼, 이하 BTB)를 사용한다.

BTB는 자주 사용하는 분기 명령어와 그 타겟 수조를 저장하는 작은 기억 장치(캐시)이다.

자주 가는 주소를 미리 저장해놓고, 필요할 때 빠르게 가져올 수 있다.

BTB의 동작으로는

명령어를 가져올 때 인덱싱
- 새로운 명령어를 가져올 때, 그 명령어의 위치(주소)를 사용해 BTB에서 검색한다.
히트와 미스
- Hit: BTB에 해당 명령어의 타겟 주소가 있으면, 즉시 그 주소로 점프한다.
- Miss : BTB에 없으면 일반적으로 타겟 주소를 계산하고 점프한다.
즉시 패치
- BTB에 타겟 주소가 있다면, 점프할 필요 없이 바로 다음 명령어를 가져올 수 있다.

BTB를 사용하면 명령어를 가져올 때, BTB를 확인해서 타겟 주소를 검색한다. 이미 타겟 주소가 저장되어 있다면 1 cycle panelty 없이 바로 다음 명령어를 실행 가능하다.

참고

https://chatgpt.com/c/4867f3e9-678e-4e5d-b85b-bd50d4fdc3f6

https://oilbeen.tistory.com/23