보관/컴퓨터구조

파이프라이닝 pipelining(2) - hazard

unhyepnhj 2024. 11. 20. 16:37

Pipelining and ISA Design

RISC-V는 파이프라이닝에 유리한 ISA인데, 모든 명령어들이 32bit 길이이므로 한 사이클 내에 fetch 및 decode하기가 용이하다.

 

파이프라이닝(1)의 빨래 예시에서 확인할 수 있듯, 파이프라이닝 기법을 사용하면 명령어 처리 시간을 줄이지 않고 같은 시간 안에 더 많은 데이터를 처리할 수 있다. 하지만 빨래 예시와는 다르게 매 clock cycle마다 명령어를 처리할 수 없는 경우가 존재한다.

 

양말 한 켤레를 실수로 빨래 더미 A와 B에 나누어 넣었을 때, A에서 짝을 맞춰 양말을 개고 넣기 위해서는 아래 그림과 같이 B 더미의 건조 과정이 끝날 때까지 한 사이클만큼의 공백이 생긴다.

이때 명령어를 처리하지 않고 대기하도록 하는 것을 bubble이라고 하며, 이 예시와 같이 명령어들을 사이클마다 연속적으로 처리하지 못하는 경우를 hazard라 한다. 

Hazards

 

hazard가 발생하면 다음 명령어를 다음 사이클에 처리할 수 없고, 아래와 같이 3가지의 hazard가 일어날 수 있다.

  1. Structural hazard: A required resource is busy: 하드웨어적인 이유; 동일한 하드웨어 자원에 접근해야 할 때
  2. Data hazard: Need to wait for previous instruction to complete its data read/write: "data dependency"; 앞의 명령어가 수행된 후 데이터를 read/write해야 할 때
  3. Control hazard: Decoding on control action depends on previous instruction: Control이 앞의 명령어에 dependent할 때

1. Structural Hazards: Conflic for use of a resource, 하드웨어 자원(메모리 또는 레지스터)에 동시에 접근할 때

 

Memory Hazard:

파이프라이닝 시 단일 메모리를 사용하고 lw/sw 명령어를 수행한다면 아래 그림과 같이 MEM과 IF 단계에서 메모리에 동시에 접근하게 된다. 이 경우 inst.04의 IF 단계를 stall하여(bubble을 만들어) inst.01의 MEM 단계와 충돌하지 않게 해야 하고, 이때 structural hazard가 발생한다.

Structural Hazard: Single Memory

 

Register Hazard:

메모리뿐 아니라 레지스터에 동시에 접근해야 할 때도 structural hazard가 발생한다. 아래 그림처럼 inst.04의 ID 단계에서 inst.01에서 레지스터에 작성 완료된 값을 사용해야 할 때, inst.04의 ID 단계를 stall하여 inst.01의 WB 단계가 완료될 때까지 대기하도록 해야 한다.

Structural Hazard: Registers

 

위와 같은 structural hazards를 해결하는 방법은 아래와 같다.

 

1. Memory hazard: instruction memory와 data memory를 분리하거나, instruction cache와 data cache를 분리한다(하드웨어적으로 해결). cache에 대해서는 추후 자세히 설명한다.

 

2. Register hazard: WB 단계는 clock cycle의 전반(first-half)에, ID 단계는 clock cycle의 후반(second-half)에 수행하도록 하여 write(WB)와 read(ID)를 한 clock cycle 안에 처리할 수 있게 한다.

2. Data Hazards: An instruction depends on the completion of data access by a previous instruction

instruction 01: add x1,x2,x3
instruction 02: sub x4,x1,x5

위 명령어들을 연속적으로 실행하는 경우 파이프라이닝을 사용하면 data hazard가 발생한다. inst.01에서 WB 완료된 1번 레지스터를 inst.02의 연산에 사용해야 하기 때문이다. 

 

이 문제를 해결하기 위해 forwarding(또는 bypassing)을 사용할 수 있다.

forwarding: Adding extra hardware to retrieve the missing item early from the internal resources

 

add x1,x2,x3에서 우리는 사실 WB 단계가 완료될 때까지 기다릴 필요가 없다. inst.01의 EX 단계가 종료되면 x1의 갱신된 값을 알 수 있으므로, 아래와 같이 inst.01의 EX와 inst.02의 ID를 연결하는 추가 하드웨어를 삽입하여 WB 이전에 곧바로 값을 전달할 수 있는데, 이것이 forwarding이다.

 

이때 주의할 점은 destination stage가 source stage보다 시간상 나중에 있어야 한다는 것이다. destination stage가 source stage보다 먼저 존재하게 된다면 source에서 destination으로 데이터를 전달하기 위해 시간을 거슬러야 하므로 이는 불가능하다.

ALU가 add 연산을 수행한 결과를 만들어내자마자 이를 sub 연산의 input으로 전달해 stall 없이 명령어를 수행할 수 있다. 다만 forwarding을 사용해도 stall을 완전히 없앨 수 없는 경우가 존재하는데, 이것이 Load-Use Data Hazard이다.

 

Load-Use Data Hazard:

메모리에 접근하는 연산의 경우, 이전과 달리 MEM에서 나온 값을 ID와 EX 사이에 전달할 수 없다. source stage인 MEM이 destination stage인 ID보다 나중에 수행되므로 forwarding이 불가능한 조건이기 때문이다.

 

이 경우 아래와 같이 한 파이프라인 전체를 stall하는 pipeline stall이 필요하다.

 

이처럼 data hazard를 forwarding을 사용해 하드웨어적으로 해결할 수 있지만, 아래 예시처럼 컴파일러가 명령어 순서를 변경해 하드웨어 변경 없이 자체적으로 data hazard를 해결하는 방법도 존재한다.

Code Scheduling to Avoid Stalls

3. Control Hazards: wait until the branch outcome is determined

 

branch 명령어를 수행할 때 분기가 결정되어 PC값을 멀리 떨어진 값으로 변경하게 되면 현재 파이프라인에 들어와 수행 중인 명령어들을 전부 버려야 하는데, 이것이 control hazard이다. 

 

branch 여부는 MEM 단계에서 결정되어 다음 명령어의 IF 단계에 반입되므로 최소 3 사이클의 stall이 발생한다. 이때 아래와 같 branch 여부를 테스트하는 추가 하드웨어(레지스터)를 사용한다면 ID 단계에서 branch 여부를 알 수 있으므로 다음 IF 단계까지 1 사이클의 버블만을 생성하는 것으로 문제를 개선할 수 있다.

 

하지만 위 방법은 명령어의 길이가 길어질 경우 비효율적이므로, CPU는 prediction을 통해 control hazard를 해결한다. control hazard에서는 data hazard에서의 forwarding과 같이 뚜렷한 best solution이 존재하지 않으므로, prediction 또한 완전한 해결법은 아니라는 점에 유의해야 한다.

 

Prediction:

branch가 항상 taken/untaken될 것이라 예측한다.

for(int i=0; i<100; i++){
	...
}

위와 같은 for문에서 항상 for문으로 돌아온다고 예측하면, i=0부터 i=98까지 99개의 케이스에 대해 예측이 적중하고 i=99일 때만 예측이 틀리므로 99%의 정확도를 가진다.

 

이와 동일한 원리로, RISC-V에서는 항상 branch가 untaken될 것을 예측하고 branch가 taken되었을 경우에만 수행 중인 다음 명령어들을 flush한다.

 

Prediction은 branch의 stereotypical behavior 기준으로 예측하는 static branch prediction과 PC값을 기준으로 예측하는 dynamic branch prediction으로 구분된다. static prediction의 경우 특정한 branch에 individuality가 존재하지 않으며, dynamic prediction은 branch의 taken/untaken 예측 여부를 결정할 때 이전 branch의 history를 고려한다.

 

static branch prediction과 dynamic branch prediction은 추후 더 자세히 다뤄 보겠다.