RISC-V 컴퓨터구조 - 4. The Processor - 4.5. An Overview of Pipelining

Pipelining 은 여러개의 instruction이 execute 하면서 overlap되는 것이다. 

이를 빨래에 비유해보자. 빨래의 단계가 세탁, 건조, 정리의 세 단계라고 하면, Single-Cycle Implementation의 경우 첫 번째 빨래의 세탁, 건조, 정리가 끝나고 그 다음 빨래의 세탁, 건조, 정리를 하는 것이다.

하지만 Pipelining이 된 경우 첫 번째 빨래가 세탁이 끝나고 건조로 넘어가면 두 번째 빨래를 바로 세탁으로 넘긴다! 그렇게 순차적으로 기계를 쉬지 않고 돌리는 것이다. 이렇게 할 때 첫번째 빨래의 시작부터 끝까지의 시간은 줄어들지 않는다. 하지만 여러 개의 빨래를 동시에 진행함으로써 같은 시간 내에 많은 빨래를 할 수 있다. 따라서, pipelining은 single task의 시간은 줄어들게 하지 않지만, 전체 세탁 시스템의 throughput을 증가시킨다. 세탁 상황의 그림은 다음과 같다.

Processor에도 똑같은 원리를 적용시킬 수 있다. 전체를 5 stage로 나눌 수 있다.

1. Instruction Fetch(IF) : Fetch instruction from memory

2. Instruction Decode(ID): Read registers and decode the instruction

3. Execution (EX): Execute the operation or calculate an address

4. Memory (MEM): Access memory operand

5. Write Back (WB): Write result back to register

RISC-V는 pipeline에 최적화된  ISA인데, 여기에는 몇 가지 이유가 있다.

첫 번째로, 모든 RISC-V instruction은 같은 길이를 가진다. 이는 pipeline의 첫 stage에서 fetch하고 두 번째 stage에서 decode하는 것을 훨씬 쉽게 한다. x86같은 ISA는 1byte부터 15byte까지의 instruction을 가지기 때문에 pipelining이 더 어렵다. 현재에는 x86을 RISC-V와 같은 더 simple한 operation으로 바꾼 다음에 pipelining을 하고 있다. 

두 번째로, RISC-V는 몇 개의 instruction format만을 가져서 source와 destination register가 instruction들에 대해서 같은 위치에 있다. 이는 읽는 것을 훨씬 쉽게 한다.

세 번째로, memory operand가 load와 store에만 나타난다는 것이다. 만약 x86과 같이 operand를 memory에서 계산해야 했다면, stage 3과 4가 address stage, memory stage, 그리고 execute stage 세개로 나눠졌어야 하는데, RISC-V에서는 execution단계에서 address를 계산하는 것이 가능하다. 그 다음 memory stage에서 읽으면 되므로 빠르다.

하지만 pipeline에서 문제가 생기는 경우가 있는데, 세 가지로 나눌 수 있다. Structural Hazard, Data Hazard, Control Hazard이다. 

Structural Hazard

Hardware가 instruction을 동시에 execute할 수 없는 상황에서 발생한다. 예를 들면, 같은 clock cycle에 MEM stage와 IF stage가 같이 execute되어야 한다고 해보자. 만약 memory가 한개라면, 이 두개를 동시에 수행할 수 없기 때문에 두 개의 seperate한 memory를 가져야 한다. RISC-V는 pipeline에 최적화된 ISA이기 때문에 이러한 상황이 잘 발생하지 않는다. 

Data Hazard

Data hazard는 pipeline이 한 step이 끝날 때까지 stall되어야 할 경우 발생한다. 예를 들면 다음 경우가 있다. 

add x19, x0, x1

sub x2, x19, x3

이 두개의 instruction이 순차적으로 실행될 경우, add에서 x19의 값이 update된 후에 subtraction 단계가 진행되어야 한다. 

그런데 update가 되려면 WB단계를 지난 후에 ID를 거쳐야 하므로, 3단계 동안 Stall이 되어야 한다. 

원래는 (괄호 안에 있는 숫자는 동시에 진행되는 다음 instruction의 단계를 의미)

1 2(1) 3(2) 4(3) 5(4) (5) 이렇게 진행되었다면, 위의 경우에는 1 2 3 4 5(1) (2) (3) 이런식으로 진행되어야 하므로 3 단계가 느리다.

Complier에게 instruction의 순서를 바꾸게 함으로써 이러한 문제를 방지할 수 있긴 하지만, 이러한 상황이 너무 빈번하기 때문에 모든 경우를 다 해결할 수는 없을 것이다. 

Solution : Forwarding!!!

생각해보면 WB 단계까지 기다릴 필요가 없다. add가 ALU에서 계산된 직후에 그 값을 subtract의 input으로 넣어주면 된다. 

일단 설명하기 전에 pipeline을 설명하는 그림을 먼저 소개해야 한다.

 

만약 색이 칠해져 있다면 그 단계가 instruction에 의해 사용된다는 것을 의미한다. add의 경우에는 memory stage를 사용하지 않기 때문에 색이 칠해져 있지 않다. 색이 오른쪽에 칠해져있다면 그 stage에서 read한다는 것을 의미하고, 색이 왼쪽에 칠해져 있다면 그 stage에서 written이 된다는 것을 의미한다. add의 경우 write back에서는 write만 하고, execution stage에서는 register에 read도 하고 write도 하므로 전체가 칠해져 있다. Forwarding을 위의 그림으로 표현하면 다음과 같다. 따라서 한 번도 stall 할 필요없이 그냥 진행하면 되는 것을 알 수 있다. Forwarding 하려면 destination stage가 source stage보다는 뒤에 있어야 한다. 

 

load의 경우에도 똑같이 forwarding이 가능한데, 이 경우에는 한 단계의 stall이 필수적이다. 뒤에 가서 좀 더 자세히 살펴볼 것이다. 이를 load-use data hazard라고 부른다. 이 때 stall 되는 것을 bubble이라고 부르기도 한다. 

Control Hazards

beq와 같은 instruction이 있으면 branch 되는 주소로 갈 지 안 갈지 결정하려면 execution 이후에 다음 instruction을 fetch해야 한다. 만약 hardware를 늘려서 두 번째 instruction decoding 단계에서 이를 해결한다고 해도 한 단계의 bubble은 필수적이다. 만약 hardware를 늘리는 것이 힘들다고 하면 필요한 clock cycle은 더 늘어난다. 

이를 해결할 수 있는 방법이 한 가지 있는데, prediction을 하는 것이다. 모든 branch instruction이 맞다고 하거나, 틀리다고 가정하고 진행한 후에, 만약 틀리게 되면 다시 redo를 한다. 

이 경우 맞게 prediction 한다면 delay가 하나도 발생하지 않지만, 틀리게 prediction 할 경우 delay가 발생한다. 

다른 방법으로는 몇 개에 대해서는 true라고 생각하고, 몇 개에 대해서는 false라고 생각하는 것이다. For 문과 While문과 같이 backward로 가는 경우에는 대부분 taken이므로 taken이라고 하고, if문의 경우에는 대부분 not taken이므로 not taken으로 한다. 

또 다른 방법으로 Dynamic hardware predictor가 있는데, 예전에 나왔던 결과들을 바탕으로 다음 결과를 예측하는 경우를 말한다. 잘 짜면 accuracy가 90프로도 넘는다고 한다.

 

출처 : Patterson, David A., and John L. Henessy. Computer Architecture and design the hardware/software interface. Cambridge, MA: Morgan Kaufman Publishers, 2018. Print.