컴퓨터구조

[컴퓨터 구조]제 4장. Pipeline(2)

촙발자 2023. 4. 9. 16:52

Pipelined Datapath

RISC-V has a five - stage pipeline (IF, ID, EX, MEM, and WB)

Pipelining을 Datapath로 나타내면 위 그림과 같습니다.

Pipeline Registers

Pipeline에서는 각 stage 사이에 레지스터를 필요로 합니다!

→ 이전 cycle에서 만들어진 정보를 가지고 있어야 하기 때문이죠.

이를 Pipeline Register이라고 합니다.

이 레지스터들은 들어오는 모든 data들을 저장할 수 있을 만큼 충분히 커야 합니다!

예를 들어,

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

만약 32-bit architecture라면, 해당 레지스터는 64bit(32-bit instruction + 32-bit PC address)의 크기를 가지고 있습니다.

ID/EX Register라면 32 + 32 + 32 + 32 = 128 - bit의 크기를 가져야 합니다.
ID/EX Register라면 32 + 32 + 32 + 32 = 128 - bit의 크기를 가져야 합니다.

이제 한 번 알아봅시다.

우리는 Load Instruction을 한다고 생각하고 진행할 것입니다.

먼저 IF단계입니다.

해당 stage에서는 PC 안에 있는 주소를 가지고 오며 branch나 jump가 아니기에 동시에 PC안에 PC+4 값이 들어갑니다.

그러고 나서 IF/ID register에 write 합니다.

다음은 ID 단계입니다.

해당 단계에서는 IF/ID Register에 있는 명령어와 PC 값을 읽습니다.

(그래서 64bit)

IF/ID는 명령어의 immediate field와 register numbers을 제공하는데 이때 I-TYPE에서는 immediate field가 12bit죠? 이것을 ImmGen에서 32bit로 sign-extended 확장합니다.

→ 그러고 나서 Immediate 정보와 레지스터 정보 2개 총 3개의 값들을 ID/EX registers에 저장합니다.

이제 EX 단계입니다.

해당 단계에서는 ALU가 연산을 수행합니다.

만약 주솟값이라면 덧셈을 진행하고 R-TYPE이라면 그에 맞는 명령을 수행합니다.

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

우리가 하고 있던 건 Load였죠?

그러면 ALU에서는 register value와 32bit로 sign-extended 된 immediate 값을 더하고 이 값은 EX/MEM 레지스터에 저장됩니다.

다음은 MEM단계입니다.

load 명령어는 EX/MEM 레지스터로 부터 가져온 address를 사용하여 data memory에서 값을 읽습니다.

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

마지막으로 WB단계입니다.

해당 단계에서는 값을 register에 넣어줍니다.

하지만 그림에서 보이듯이 문제점이 하나 생겼죠?

예를 들어 add x3, x5, x6라는 명령어가 현재 ID단계에 있으면 lw의 rd가 아닌 잘못된 레지스터에 data가 들어가게 되는 것입니다!

따라서, WB를 할 때엔 lw가 지정한 register number가 따라오도록 해야 합니다!

고로 위 Datapath를 수정해 보도록 하겠습니다.

Corrected Pipelined Datapath for Load Instruction

추가된 파란색 선들이 보이시나요?

Pipeline Register에선 rd를 위한 또 다른 path가 존재하고 최종적으로 WB stage에서 올바른 register number가 들어가게 됩니다.

Load가 이렇다면 Store는 어떨까요??

Store Instruction

사실 Store 같은 경우에는 IF와 ID stages가 load와 거의 동일합니다.
EX stage에서는, load와 달리 second register value가 EX/MEM 레지스터에 들어가게 됩니다.

Memory for Store Instruction

load와 차이점은 data가 따라서 Data memory의 Write data에 값이 들어간다는 게 차이점이라고 할 수 있습니다.

Write Back for Store Instruction

store 명령어 같은 경우, WB stage는 아무 일도 일어나지 않습니다. (nothing happen)

그렇다고 WB stage를 뺄 수는 없습니다.

다른 명령어들도 필요하고 파이프라인 5단계를 다 맞춰놓았기에 할 일이 없으면 그냥 바로 넘어가는 것입니다.

Single Clock Cycle Pipeline Diagram

위 그림은 multiple cycle pipeline diagram입니다.

처음 pipeline을 설명할 때 와 다른 게 없죠?

이 Times들 중 CC5 당시의 single clock cycle pipeline diagram을 보여드리겠습니다.

→ Single Clock Cycle Pipeline Diagram은 single cycle 동안의 datapath 전체의 상황을 보여줍니다.

여기에 추가적으로 이제 Pipelined Control이 추가되어야 합니다.

Pipelined Control

control line들은 존재하는 datapath위에 덧붙여집니다.

처음은 Control 신호입니다.

위 그림을 보면, Control Path가 추가되었습니다.

우리는 중간고사때와 똑같은 ALU control logic, branch logic, control lines을 사용합니다!

하지만 그림을 잘 보시면 Pipeline register와 PC에 대한 control은 존재하지 않습니다.

이는 매 Clock Cycle당 값이 항상 들어가므로 컨트롤이 필요하지 않기 때문입니다!

Control Lines

각 stage별로 어떤 신호들이 들어가는지 보겠습니다.

IF : nothing special
ID : nothing special
EX : ALUOP , ALUSrc
MEM : MEMRead , MemWrite , Branch
WB : MemtoReg , RegWrite

ALUop : 어떤 연산을 수행할 것인지에 대한 값
ALUSrc : Imm을 사용할 것인가에 대한 값. 만약 값이 0이라면 Register 2의 값을 사용합니다.
MemtoReg : Memory의 값을 Register에 쓸 것인지에 대한 값. 만약 값이 0이라면 ALU의 연산 결과를 Register에 입력합니다.

Control Lines for the Final Three Stages

우린 ID stage 동안 control information을 만들 수 있습니다.
- 뒤의 스테이지들에게 전달하는 contorls을 포함하기 위해 Pipeline register를 확장합니다.

위의 ID/EX 파이프라인 레지스터 위에 8 bits가 더 들어갑니다!

Pipeline registers
- ID/EX : all 7 control lines
- EX/MEM : 5 control lines
- MEM/WB : 2 control lines

EX에 있는 ALUOp가 2bit이기 때문에 7bit가 아닌 8bit가 더 들어갑니다.

Pipelined Datapath with Control Signals

따라서 Control Signals들을 포함한 datapath는 아래와 같습니다.

이제 저희는 앞서 배운 Hazards에 관하여 더욱 자세히 배워 볼 것입니다.

Data Hazards in ALU Instructions

위 그림을 보시면 아래 4개 명령어들은 첫 번째 명령어의 결과인 x2 값에 대한 dependency를 가지고 있습니다.

4개 중 위 두 개의 명령어는 Hazard가 발생하게 됩니다.

하지만 아래에 있는 두 개 명령어는 Hazard가 발생하지 않습니다!

아래 두 개는 Forwarding이 발생해서 인데요. 이제 Forwarding을 더 자세히 알아보겠습니다.

Detecting the Need to Forward

우선 우리는 Forward가 필요한 상황인지 먼저 detection(검사)를 해야 하는 상황입니다.

Register에 Write contorl이 왔는가.
- EX/MEM.RegWrite , MEM/WB.RegWrite
아무리 계산을 해도 레지스터에 작성이 되지 않는다면 말짱 도루묵일 것입니다. 그렇기에 Register에 Write를 하는지 확인을 해봐야 합니다.
명령어에 Rd가 x0 이 아닌가.
- EX/MEM.RegisterRd ≠ 0, MEM/WB.RegisterRd ≠ 0
예를 들어, sub x0, x2, x3 같은 명령어가 있다고 합니다. x0 은 어차피 0이 돼버리니 아무 의미가 없겠죠?
아래 참고

바로 위 4개의 상황이 Forward가 필요한 상황입니다.

위 그림에 있던 and 명령어가 1a 상황이겠죠?

이 세 조건이 만족되면 비로소 Forwarding이 실행됩니다.

Forwarding Unit

Datapath에 Forwarding Unit이 들어갑니다.
MUX는 register file values 또는 forwarded values 중 하나를 선택합니다.

MUX에는 3개가 input 되면 한 갯값이 나옵니다. (3 to 1)

해당 Unit은 앞의 조건들을 확인하고, MUX를 통하여 어떤 값을 사용할지 정합니다.

위 그림은 Forwarding Unit이 보내는 신호들입니다.

10은 EX/MEM에서 값을 보내고 01은 MEM/WB에서 값을 보내줍니다.

Load-Use Hazard

자 그럼 이제 Load-Use도 알아봐야겠죠?

앞에서는 Forwarding Unit을 넣었었죠? 거기에 추가하여 이번엔 hazard detection unit을 추가해 줍니다.

이 hazard detection unit은 ID stage에서 동작을 합니다.

Load-Use 같은 경우에는 MEM/WB register에서 값이 나오기 때문에 한 번의 stall이 불가피하게 일어날 수밖에 없었습니다.

그렇다면 최대한 빠르게 stall을 하는 게 좋겠죠?

아래는 stall을 하는 조건입니다.

일단

ID/EX에서 명령어가 load 인지 확인을 합니다.
→ load명령어만이 유일하게 메모리에서 read를 하기 때문에 확인가능
dependency를 가지고 있는지 확인한다.

이제 stall을 하기 위해서 어떤 일이 일어나는지 설명하겠습니다.

PC와 IF/ID 레지스터가 update 되는 것을 막습니다. (+4가 되지 않게)
그렇게 되면 현재 명령어가 다시 ID stage에서 decode 됩니다.
즉 (PC+4+4)가 아니라 다시 (PC+4)가 IF stage에서 fetch 됩니다.
ID/EX 레지스터의 control signal을 0으로 만듭니다.
즉, NOP(no operation)이 되게 하는 겁니다.
이렇게 하면 뒤의 EX, MEM, WB는 아무 일을 하지 않습니다.

stalling이 발생하면 이제 forwarding logic을 실행하면 됩니다.

Control Hazard

branch는 MEM stage에 도달하기 전까지 발생하지 않습니다.

만약 Branch 하지 않겠다고 예측했다가 Branch가 실행된다면 MEM단계 이전의 명령어들은 전부 버려야 합니다.

→ control signal을 0으로 하여 전부 flush 하는 것.

예측에 실패하더라도 flush 되는 양을 줄이면 좋겠죠?

Reducing the Delay of Branches

우리는 branch결과를 구하는 것을 ID stage에서 미리 구하도록 하드웨어를 옮길 수 있습니다.
1. target address adder → branch target address를 계산합니다.
2. register compator → branch decision을 결정합니다.
또한 IF stage에 있는 명령어를 flush 하기 위해 IF.Flush control line을 추가했습니다.

예시)

36 sub x10, x4, x8
40 beq x1, x3, 16
44 and x12, x2, x5
48 or x13, x2, x6
52 add x14, x4, x2
56 sub x15, x6, x7
...
72 lw x4, 50(x7)

만약 40 be1 x1, x3, 16 이 taken 된다면 우린 40+16*2의 결과인 72 Label (lw x4, 50(x7))로 가야 합니다.

이를 그림으로 나타내겠습니다.

파란색 네모들이 새로 생긴 Unit입니다.

맨 오른쪽 Unit은 레지스터 두 개가 같은지를 판단합니다.

저는 처음에 빼기 연산으로 하여 Zero signal을 사용하는 줄 알았는데

XOR 연산을 실행하여 시간을 빠르게 단축한다고 합니다!

3번째 네모는 ImmGen에서 생성된 Imm 값이 PC값과 더해지는 모습을 볼 수 있습니다.

마지막으로 Branch Taken 된다면 IF.Flush에서 signal을 0으로 하여 flush를 실시하며, 새로운 PC값을 업데이트합니다.

MEM stage에서 branch 결정이 나던걸 IDstage에서 나는 걸 볼 수 있습니다.

그리고 위에서 말한 것처럼 레지스터 두 개의 값을 빼서 0인지 확인하는 게 아닌 XOR연산을 하기 때문에 ALU에 zero signal이 없는 걸 볼 수 있습니다.

위 그림에 Clock이 들어가면 이제 아래와 같은 그림이 됩니다.

ID stage가 NOP으로 바뀌고 PC값에 새로운 명령어가 fetch 된 것을 볼 수 있습니다.

Dynamic Branch Prediction

파이프라인이 커지면 커질수록 branch penalty는 중요해집니다.

위에 있는 예시들은 사실상 Static branch prediction입니다.

사전에 Untaken 일 것이라고 결정을 해놨기 때문이죠.

우린 Dynamic Branch Prediction을 사용해 보도록 하겠습니다.

이 방법은 branch prediction buffer 혹은 branch history table을 사용합니다.
- branch prediction buffer은 IF stage에 위치해 있습니다.
- 이 버퍼는 branch가 최근에 taken 되었는지 되지 않았는지에 관한 bit를 담고 있습니다.
- 저장되어있는 bit에 따라 수행하고 예측에 실패하면 앞의 명령어를 flush 합니다.