[컴퓨터구조] 프로세서 2. RISC-V Pipelining

서론

 단일 사이클 설계는 정확하게 작동하지만, 현대적인 설계에 사용되기에는 부적절하기 때문에 잘 사용되지 않는다.

프로세서에 가장 긴 path가 clock cycle을 결정한다.

 

가장 긴 path는 적재 명령어인데, 적재 명령어는 명령어 메모리, 레지스터 파일, 데이터 메모리, 레지스터 파일의 5개 기능을 모두 사용하기 때문이다.

 

 

---

 

Pipelining

 

여러 개의 명령어를 동시에 수행하는 기법

 

single cycle과 pipeline 비교

 

싱글 사이클과 파이프라인을 아주 잘 비교할 수 있는 예시다.

 

각 사이클은 세탁-건조-옷개기-옷장에 넣기 이렇게 4가지 단계로 이루어지는데 위쪽 그림은 한가지 옷을 옷장에 넣기 전까지는 새로운 세탁을 하지 않는다.

 

하지만 아래 그림을 보면 첫번째 세탁이 끝나고 건조를 하며 바로 다음 번째의 세탁이 이루어지는 것을 볼 수 있다! 

 

실행시간도 위쪽은 새벽 2시까지 빨래를 돌려야하는 반면 아래쪽 파이프라인은 9시 반에 끝이난다!

 

이를 통해 알 수 있는 점은 다음과 같다.

 

각 단계마다 별개의 자원을 이용한다면 작업들을 파이프라이닝 할 수 있다.

 

 

파이프라이닝을 사용했을 때 성능이 향상되는 이유는 각 단계를 병렬로 동작시켜 같은 시간에 더 많은 일을 처리할 수 있도록 하기 때문이다.

 

 

---

 

파이프라인과 데이터패스 제어

 

위에서 세탁, 건조와 같은 하나의 과정을 stage로 구분한다.

그렇다면 RISC-V의 하나의 명령어가 수행되기 위해서는 총 몇 개의 stage가 필요할까?

 

총 다섯개가 필요하다.

 

1. IF(Instruction Fetch) : 명령어 인출
2. ID(Instruction Decode): 명령어 해독 및 레지스터 파일 읽기
3. EX(Excution/Address Calculation): 실행 또는 주소 계산
4. MEM(Memory Access): 메모리 접근
5. WB(Write Back): 쓰기

Datapath with pipeline

 

명령어와 데이터가 이 다섯 단계를 왼쪽에서 오른쪽으로 지나가면서 실행을 마친다.

Single pipe

pipelineing

 

RISC-V의 명령어를 stage 별로 처리하는 모습은 위와 같다.

위에서 본 세탁 예제처럼 시간이 많이 줄어드는 것을 볼 수 있다.

 

이처럼 CPU는 각 명령어를 총 5개의 Stage로 나눠서, 하나의 stage에 하나의 작업을 한다.

만약 3번째 time에서 작업을 한다면, EX stage에서는 add를 수행할 것이고, ID stage에서는 x14, x15 레지스터를 읽고, 명령어를 해독하고 있을 것이다.

또한 IF stage에서 and x5, x6, x7 명령어를 반입하고 있을 것이다.

 

Performace 비교

레지스터를 읽고 쓰는데(ID stage) 100ps, 

다른 스테이지를 실행하는데 200ps가 걸린다고 가정하자.

 

아래의 표는 명령어를 각 stage로 나누어 시간을 계산한 표다

 

 

 

만약 Single cycle이였다면, lw 명령어를 수행하는데 800ps가 걸릴 것이다.

그러면 clock cycle도 800ps가 된다.

따라서 4번째 명령어를 시작하기까지 2.4ns가 걸린다.

 

Pipeline에서는 하나의 stage가 하나의 Clock cycle을 가지고 있으므로, clock cycle은 가장 느린 작업에 맞춰야 한다.

따라서 모든 stage는 200ps의 clock cycle을 가지게 되고, 4번째 명령어를 시작하기까지 600ps, 0.6ns만큼 걸린다. (pipeline 에 넣는 시간은 생략)

 

 

ID stage가 100ps이지만, 느린 시간에 맞춰야 하므로 200ps에 맞춰진다. 

 

만약 모든 stage가 같은 시간이라면 pipeline의 instruction clock cycle 공식은 다음과 같다.

 

 

다만 stage가 모두 같은 시간이 아니라면 성능 향상은 저하된다.

 

pipeline 기법은 각 명령어의 수행 시간을 줄이지 않고서도, 명령어 처리량을 향상시킨다.

 

 

그래도 파이프라인을 사용하면 일정 수준 이상의 성능향상은 무조건 보장된거아냐? 라고 생각할 수 있다.

 

과연 그럴까?

 

 

---

Hazard

다음 명령어가 다음 클럭 사이클에 실행될 수 없는 상황이 있다.

 

이런 사건을 Hazard 라고 부르는데 Hazard에는 3가지 종류가 있다.

 

• Structual Hazard(구조적 해저드): 같은 자원을 써야 할 때
• Data Hazard(데이터 해저드): 데이터를 read, write 해야 할 때, 앞의 명령어가 수행될 때까지 기다려야 할 때
• Control Hazard(제어 해저드): 앞의 명령어에 의해 Control이 좌우될 때

하나하나 자세히 알아보자~!

 

 

Structaual Hazard

 

메모리가 한 개라고 생각한다면 load 혹은 store 명령어를 수행할 때 메모리에 접근하게 되는데, 이 경우 다음 명령어를 fetch하기 위해서도 메모리에 접근하게 되므로 Structual Hazard가 발생한다.

 

레지스터의 경우에도 읽기와 쓰기가 동시에 발생하는 경우에는 Structual hazard를 피할 수 없다.

 

MEM과 IF에서 동시 접근하는 모습

 

 

따라서 4번째 명령어인 instruction fetch를 stall(bubble)하여, 충돌을 피해야 한다.

• stall(bubble) 명령어를 의도적으로 한 단계 지연시켜서 실행하는 것

그렇게 된다면 4번째 명령어는 한 번 늦게 실행이 되므로 충돌을 피할 수 있다.

 

해결법

 

single memory 대신에 두 개의 memory로 분할하면 된다.

 

따라서 명령어를 stall 할 필요가 없다.

그러므로 pipeline datapath에서는 instruction memory와 data memory를 분리해놓았다.

 

혹은 cache를 사용하여 해결하기도 한다. (미리 메모리에서 cache 메모리로 올려놓음)

 

 

Data Hazard

add x19, x0, x1
sub x2, x19, x3

 

위 상황에 별 다른 조치가 없다면 Data Hazard가 발생한다.

 

add 명령어에서는 5번째 단계에서 x19에 계산 결과를 쓰기 때문에, 2번째 단계에서 레지스터를 읽어야 하는 sub 명령어의 경우 3개의 클럭 사이클을 낭비하게 된다.

 

위와 같이 어떤 명령어가 아직 파이프라인에 있는 앞선 명령어에 종속성을 가질 때 Data Hazard가 발생한다. 

 

이러한 Data Hazard를 해결하기 위한 방법으로는 forwarding이 있다.

 

해결법

사실 이러한 문제는 컴파일러가 대부분 해결해준다.

의존성 문제가 발생할 것 같다면, 컴파일러는 중간에 x19를 참조하지 않는 명령어를 넣음으로써 이를 해결한다.

하지만 이러한 의존성은 너무 자주 발생하고, 만약에 긴 명령어가 있을 때 컴파일러가 해결하지 못한다면 손해가 크다.

 

이러한 문제는 하드웨어에서 발생하는 문제이기 때문에, 소프트웨어로 해결하기에는 충분하지 않다. 따라서 하드웨어적으로 문제를 해결하는데, 이것이 forwarding

 

forwarding은 Data hazard를 해결하기 위한 기법이다.

ALU 단계(EX)에서 add를 계산하고 난 후에 곧바로 sub에게 결과를 제공한다.

 

forwarding

 

 

어차피 add이기 때문에 memory는 참조할 필요가 없다. 

따라서 곧바로 다음 명령어에게 값을 전달하면 해결할 수 있다.

 

다만 해당 그림은 시간축을 따라 표현한 것이기에, 실제로는 EX에서 나온 선이 곧바로 ID와 EX 사이로 들어간다고 보면 된다.

 

forwarding은 목적지가 Source data 보다 늦게 있어야 가능하다
시간을 거슬러 갈 수는 없으니까!

 

 

이렇게 forwarding을 통해서 register간의 Data Hazard는 해결했다.

 

하지만 MEM에서 나온 값을 바로 뒤에서 참조해야 한다면?

 

 

Load-Use Data Hazard

 

MEM에서 나온 값은 ID/EX 사이로 들어갈 수 없다.

왜냐면 MEM에서 나온 값은 시간상으로 ID/EX보다 먼저 수행된 값이기 때문이다.

따라서 이런 경우에는 pipeline stall을 해야한다.

 

 

 

그러므로 load-use data hazard가 발생하면 stall을 해야한다.

그나마 fowarding을 사용해서 1 clock cycle만 delay되었다.

 

하지만 이것도 해결할 수 있지 않을까?

 

위에서 컴파일러는 의존성 문제를 해결하기 위해 코드를 재구성 한다고 했다.

 

아래 예제를 보면

 

 

원래 2번의 stall이 발생하는 코드였는데 재구성 이후 stall이 사라졌다!

따라서 기존의 버전보다 2 cycle 적게 사용한다.

 

만약 의존성문제가 없는 명령어가 없다면 No Operation 명령어를 실행한다. (프로그램에 해를 끼치지 않는 더미 instruction)

 

 

 

Control Hazard

 

control hazard는 분기 명령어를 통해 PC 값을 바꿀 때, 이미 pipeline에 들어와 있는 명령어가 flush 되는 현상,

즉 pipeline에 이미 반입된 다음 명령어를 버려야 한다는 뜻이다

 

이게 무슨 뜻이지?

 

 

우리가 보통 if-else를 사용하여 분기할 때 조건에 맞거나 / 맞지 않을 때 다음 명령어로 가지 않고 건너뛰게 되는데

 

if a == b
// 수행 코드 c
else
// 수행 코드 d

명령어는 순차적으로 들어오기 때문에 a == b를 확인하면서도 c를 다음 명령어로 fetch 중이다.

 

이미 c를 fetch하고 계산하고 있는데 사실 a와 b가 같지 않아서 d를 바로 수행해야 한다면? c는 그냥 버려지는 것이다...

게다가 a와 b가 같은지 결정하는 타이밍이 굉장히 뒷쪽에 있기 때문에 파이프라인 정체가 일어날 수 있다.

 

전체 명령어 중 20% 정도가 분기명령어를 수행하는데 이 때마다 정체가 일어난다면? 데미지가 너무 심하다

 

 

해결법

 

branch가 될지, 안 될지 미리 test하는 register를 추가로 사용해보자

그러면 이 명령어가 branch이다 라는 고전과 Reg 두 개의 값이 같다 라는 조건이 맞으면 되므로, ID 단계에서 register를 추가로 사용하여 문제를 해결한다.

 

 

이처럼 MEM 단계에서 branch가 결정되던 기존의 datapath와는 달리 ID 단계에서 결정이 일어나서 1 cycle만 손해를 본다.

beq 가 False라면 그냥 실행하지만, beq가 True라면 branch를 다시 계산해서 멀리 있는 명령어를 재반입한다.

 

하지만 명령어가 길다면 어떻게 될까?

예를 들어 pipeline이 20 cycle이고, 중간에 branch를 한다는 것을 알아낸다 하더라도 10 cycle은 손해본다.

그리고 재반입하여 수행한다.

register를 추가한다 하더라도, stall로 인해 발생하는 패널티는 너무 크다.

 

 

그렇기 때문에 CPU는 prediction(예측)을 한다.

반복문 등을 생각하면 실제로 사용되는 분기의 경우 성공하는 케이스가 많겠지만 구현이 복잡해지기에 RISC-V의 경우 실패한다고 예측한다.

 

만일 분기가 일어난다면 인출되고 해독되었던 명령어들은 버리고 분기 목적지에서 실행을 계속한다.

 

 

위에는 beq가 false, 아래는 true일 때

 

 

Prediction

 

예측은 Static Branch Prediction과 Dynamic Branch Prediction으로 나뉜다.

 

Static은 branch의 일반적인 행동을 기반으로 예측한다.

loop 같은 경우에는 항상 branch가 taken된다고 예측한다.

만약 100번 loop한다고 가정하면, 99번은 맞추고 1번은 틀리게 된다.

다만 Static의 경우에는 backward branch만 가능하고, forward branch는 불가능하다.

• backward branch: 프로그램의 이전 명령어로 점프하는 경우(ex.loop)
• forward branch: 프로그램의 이후 명령어로 점프하는 경우(ex. If-else)

 

Dynamic은 각각의 conditional branch의 과거를 기반으로 예측을 수행한다.

하드웨어에서 각 branch마다 과거를 기억하고 있어서, 해당 branch의 트렌드로 예측을 한다.

만약 예측이 틀리다면 재반입할 때까지 stall하고, 과거를 업데이트 한다.

 

 

Pipeline Datapath

 

위에서 살펴봤던 single cycle datapath는 다음과 같다.

 

여기서 파란색 선은 뒤 stage의 데이터가 다시 앞으로 와야하는 역주행의 경우이다.

 

writeback stage와 Next PC value의 section의 경우이다.

• wirteback : 레지스터에 값을 쓰는 행위 (load, R-Format)
• Next PC value : 다음 명령어 주소 결정 (beq)

 

이 두개가 data hazard와 control hazard의 요인이라고 할 수 있다.

 

이렇게 다섯 단계로 나뉜 pipeline의 중간에는 register가 있어 값을 저장할 수 있어야 한다. 만약에 register의 read와 write signal이 겹쳐도 해결할 방안이 있는데, clock cycle의 first half에는 written 할 수 있게 하고, second half에는 read할 수 있게 하면 된다.

 

뭔 소리일까?

 

앞선 stage의 정보를 저장하는 특별한 register가 필요하다. 이를 pipeline register라고 한다.

 

ID stage에서 사용하는 명령어나 레지스터 번호 등은 IF stage에서는 더 이상 없다. 

왜냐면 ID stage에서 어떤 명령어를 실행하고 있으면, IF stage는 pipeline 기법에 의해 다른 명령어를 반입하고 있기 때문이다.

 

따라서 중간중간 연산의 결과, 명령어 등을 저장하는 Pipeline register가 필요하다. 

 

pipeline register

레지스터는 모든 데이터를 저장할 수 있을만큼 충분히 커야한다. 

IF와 ID 사이에 있는 레지스터를 IF/ID 레지스터라고 한다.

만약 32-bit register라면, 해당 register의 크기는 32bit 명령어 + 32bit PC address를 더하여 64-bit 크기를 가져야 한다.

 

ID/EX라면 128-bit의 크기를 가져야 한다.

 

 

이제 예시로 알아보자

 

instruction memory를 read 하는 경우

참고로 이렇게 오른쪽 반이 칠해져 있는 경우는 read이고, 왼쪽 반이 칠해져 있는 경우는 write이다.

 

IF Stage

IF stage

 

IF stage에서 PC의 주소가 읽혔고, 이 주소를 IF/ID register에 저장한다. 

PC는 4만큼 증가하고 다시 PC에 저장된다. -> 다음 clock cycle이 들어왔을 때 그 주소를 읽는다. 

beq에서 사용될 수도 있으니 이 또한 IF/ID에 저장된다.

 

ID Stage

ID stage

일단 IF/ID register의 명령어와 PC값을 읽는다. 

읽어 들인 명령어를 바탕으로 Register read를 하고 Imm Gen 에서 Immediate 값을 추출한다.

그러고 나서 ID/EX에 레지스터의 정보와 PC address, 복원된 Immediate 정보를 write한다. 

(Imm Gen은 명령어에서 Imm 값을 읽은 후, sign-extension 방식으로 imm 값을 32-bit 확장한다.)

 

여기서 주의할 점은 만약 뒷부분에서 읽어야 할 값이 있다면 뒤까지 전파를 해줘야 한다.

예를 들어, Write register의 경우 ID/EX에 저장된 후에도 MEM/WB에서 또 필요하므로 이 값을 앞으로 propagation 해줘야 한다.

꼭 Write register가 아니라도 필요한 값은 앞으로 propagation 하는 것이 필요하다.

 

propagation 예시

 

EX Stage

EX stage

해당 단계에서는 연산을 수행한다. 

 

만약 주소값이라면 덧셈을 진행하고, R-Type 이라면 그에 맞는 명령을 수행한다.

또한 branch 명령어라면 위에 있는 Add를 실행하여 PC address를 update 한다.

마찬가지로 모든 실행이 끝나면 모든 정보를 EX/MEM에 Write 한다.

 

만약에 명령어가 addi 라면 Register 1번 값과 Immediate 값만 덧셈을 수행한다.

다만 이 때 Register 2번의 값이 EX/MEM에 입력되는데, 멀티플렉서에서 무시되므로 신경쓰지 않아도 된다.

 

MEM Stage

MEM stage

 

계산된 address를 바탕으로 data memory에서 값을 읽는다.

읽힌 data는 MEM/WB에 기록된다. 

 

 

WB Stage

WB stage

 

register에 값을 입력하는 단계

 

앗 근데 어디다가 입력해야하지?

 

위에서 말했던 ID stage의 propagation 이 여기서 쓰인다.

ID stage에서 넣어줬던 값을 바탕으로 메모리에 데이터를 쓴다.

 

 

Store instruction 같은 경우에는 사실 WB를 쓸 필요가 없다. 

그렇다면 WB stage를 건너뛸 수 있는가?

 

Store는 WB stage가 필요 없지만, 그래도 진행은 한다.

다만 아무것도 하지 않는다.

 

 

Pipelined Control

Pipelined Control (Simplified)

그림을 보면 Control path가 추가되었다.

다만 여기에 매번 수행되는 Pipeline Register의 write signal과 PC에 대한 control은 없다.

이는 매 Clock Cycle 마다 수행되므로, 따로 표기하지 않는다.

 

 

Control Lines

각 Stage 별로 어떤 control 신호가 입력되는지 알아보자!

• IF: Nothing Special
• ID: Nothing Special
• EX: ALUOp, ALUSrc
• MEM: MemRead, MemWrite, Branch
• WB: MemtoReg, RegWrite

ALUOp는 어떤 연산을 수행할 것인지에 대한 값

ALUSrc 는 Imm를 사용할 것이냐에 대한 값. 만약 ALUSrc가 0이라면 Register 2의 값을 사용한다.

MemtoReg는 Memory의 값을 Register에 쓸 것이냐에 대한 값이다. 만약 값이 0이라면 ALU의 연산 결과를 Register에 입력한다.

 

하지만 Control은 5개가 아니기 때문에, ID에서 생성된 Control의 신호가 다음 Stage에도 계속해서 흘러가야 한다.

그렇지 않다면 Control은 매번 각 Stage 별로 신호를 생성해야 한다.

매우 비효율적이기 때문에 Control 신호 또한 Pipeline Register를 통해서 다음 Stage에 가야 한다.

 

 

Control Lines for the Final Three Stages

Pipeline regiter를 확장하여 이후 stage의 control 신호가 갈 수 있도록 만든다

 

EX에서 필요한 Control 신호는 2개, MEM은 3개, WB는 2개이다.

따라서 ID/EX에는 7개의 control line이 추가적으로 필요하고, EX/MEM은 5개, MEM/WB는 2개가 추가적으로 필요하다.

Control 신호는 ID stage, 즉 Instruction Decode에서 발생하기 때문에, ID stage 이후로만 Control 신호가 흐른다. 

 

 

 

따라서 Control Signal을 추가한 Pipelined Datapath는 위와 같다.

 

WB stage에서 Regwrite Control Signal은 앞으로 진행되어, ID stage에 도달하게 된다.

ALU의 Zero Signal은 EX stage에서 나온다.

다만 stage의 끝에서 결과가 도출되기 때문에, 한 stage 내에서 zero로 무언가를 하기에는 너무 늦은 상태다

 

따라서 beq 같은 branch instruction이 MEM stage에서 실행된다.

 

 

참고

 

https://hi-guten-tag.tistory.com/272

[컴퓨터 구조] Data Hazard in Pipelined Datapath

https://ttl-blog.tistory.com/1059?category=967479

[컴퓨터 구조] 프로세서[2] - 파이프라이닝

https://jja2han.tistory.com/218?category=583664

[Computer Architecture] - processor(3)-[pipeline, hazard]

https://oilbeen.tistory.com/category/Computer%20Engineering/Computer%20Architecture