컴퓨터구조

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

촙발자 2023. 4. 8. 22:36

Overview of Pipelining

Pipelining은 실행 시에 여러 명령들이 중첩되는 구현 기술입니다.

현재 pipelining기술은 보편적으로 사용되고 있습니다.

예를 들어,non-pipelined Version에서 세탁물을 예시로 든다면

Non-pipelined Version

이렇게 되지만

Pipelined Version에선

Pipelined Version

이런 식으로 시간이 훨씬 줄어든 것을 볼 수 있습니다.

Pipelining에선 stages라고 불리는 모든 단계들이 동시에 작동합니다.

그래서 위의 Non-pipelined Version에선 총 16 times이 걸렸고, 아래의 pipeline에선 총 7 times이 걸렸습니다.

→ 따라서 16/7= 약 2.3배가 빨라졌고 이러한 빨래물들의 양이 무한하다면 4n/(n+3) = 약 4배 가량 빨라집니다.

 

Pipelining은 throughput(단위 시간동안 처리하는 양)을 늘려줍니다!

  • Pipeline은 각 stage의 시간을 줄이지는 않습니다.
  • 위 예시에서도 총시간은 짧아졌지만 각 step들의 시간은 짧아지지 않았습니다.
  • 우리가 해야 할 일이 많을수록 (빨래물들의 양이 많을수록) 총시간은 감소할 것입니다!

 

RISC-V Pipeline

RISC-V 명령들은 5개 steps을 가집니다.

  1. IF : 메모리로부터 instruction을 fetch 합니다.
  2. ID : 레지스터들을 읽고 명령어를 해석합니다! 또한 컨트롤 신호가 생성됩니다.
  3. EX : 연산을 실행하거나 주소를 계산합니다.
  4. MEM : 데이터 메모리에 있는 피연산자에 접근합니다.
  5. WB : 결괏값을 레지스터에 입력합니다.

5단계마다 수행하는 하드웨어가 있는데

위의 Non-pipelined Version에서는 자신의 일이 아닐 때는 각 하드웨어가 아무 일도 하지 않고 쉬고 있습니다.

하지만, 아래에서는

각 하드웨어를 계속 사용하고 있고 시간이 줄어드는 것을 한눈에 볼 수 있습니다.

 

만약 3번째 time에서 작업을 한다면, EX stage에서는 x11의 값과 x12의 값을 연산하고 있을 것이고 ID stage에선 x14와 x15를 읽고 명령어를 해석하고 있을 겁니다.

또한, IF stage에서는 and x5, x6, x7 명령어를 fetch 하고 있을 겁니다.

 

 

Single-Cycle vs Pipelined Performance

각 stage별 실행 시간을

  • register file read or write = 100ps
  • other stages = 200ps

라고 가정합니다.

  • Single-cycle은 가장 느린 명령어까지 가능하게 설계되었습니다.
    • 즉 lw가 800ps 걸리기에 모든 instruction은 800ps가 걸립니다.(부 정확)
    • 그러므로, 3 lw를 실행하는데 총 3 x 800 ps = 2400ps = 2.4ns가 걸리게 됩니다!
  • pipeline은 한 stage당 하나의 clock cycle이 소요됩니다. 그렇기에 clock cycle은 가장 느린 operation을 실행할 만큼 충분히 커야 합니다!
    • pipelined exectuon은 clock cycle 중 가장 최악의 경우인 200ps를 가지고 있어야 합니다.

아래쪽에 그림으로 더욱더 정확한 설명이 되어 있습니다.

Single - cycle은 3 lw를 위해 800ps x 3 = 2400ps가 소요되지만

pipelined는 총 1400ps가 걸렸습니다! (한 instruction은 1000ps 소요)

중요한 것은, pipelined에서 Id stage는 100ps지만 가장 최악의 경우에 맞춰야 하므로 200ps가 소요되었습니다!

 

 

Pipeline Speed-up

  • 만약 stages들이 완벽하게 같은 시간이 걸린다면

 

이런 공식이 성립합니다.

  • 만약, 완전히 같지 않다면 speed-up(성능 향상)은 줄어듭니다.
  • 위의 예시는 3개의 명령어라 성능향상이 매우 작아 보입니다.
    • (위 예시) 2400ps/1400ps = 1.74
    하지만 우리가 100만 개의 명령어들을 더한다면
      1. Pipelined : 1,000,000 * 200ps + 1400ps = 200,001,400 ps
      1. Nonpipelined : 1,000,000 * 800ps + 2400ps = 800,002,400 ps
    • 즉 Speedup = 800,002,400 ps / 200,001,400 ps = 약 800/200 = 약 4배가 됩니다!!

 

  • Pipelining기법은 각 명령어의 수행시간을 줄이진 못하더라도 (늘어날 때도 있음) throughput을 향상해 줍니다!

 

 

Designing Instruction Sets for Pipelining

  • RISC-V 명령어들은 pipelined exection을 위해 설계되었습니다!
  • 모든 RISC-V 명령어들은 같은 크기를 가지고 있습니다! 이러한 점은
      1. 첫 번째 stage에서 명령어 fetch를 쉽게 만들어줍니다.
      1. 두 번째 stage에서 그것들을 decode 하는 것을 쉽게 만들어 줍니다.
  • RISC-V는 적은 명령어 format들을 가지고 있습니다.(R-type, I-type….)
    • 게다가 source and destination register field는 각 명령어에서 같은 곳에 위치해 있습니다!
  • RISC-V에서 Memory operands는 오직 loads와 stores에서 나타납니다!

 

Pipeline Hazards

Pipeline Hazards는 next Instruction이 다음 cycle에서 수행되지 않는 경우가 생기는 것을 뜻합니다!

이러한 경우는 3가지의 경우가 있는데

  1. Structural Hazard
  2. Data Hazard
  3. Control Hazard (branch Hazard)

입니다.

 

 

Structural Hazard

Structural Hazard는 간단하게 stage는 다르지만 동시에 동일한 H/W에 접근할 때 발생합니다.

  • RISC-V는 pipeline에서 structural hazard를 피하기 위해 설계되었습니다.
  • 아래 예시에선 Instruction fetch cycle에서 한 번 stall 합니다.
    • stall을 함으로써 실행을 한 번 늦추게 하여 충돌을 막는데 이것을 pipeline bubble이라고 부릅니다.
  • Load/store는 data access를 요구합니다.

해결 방법

stall 시키는 것도 하나의 해결책이라고 할 수 있습니다.

하지만 stall 하는 것은 성능면에서 좋다고 볼 순 없죠.

간단하게 single memory를 두 개의 memory로 분할하면 됩니다.

즉, 메모리 하나에 Data, Insturction을 담는 것이 아니라 둘을 나누는 것이죠.

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

혹은 Caches를 사용하여 해결하기도 합니다.

 

 

Data Hazard

  • Data hazards는 뒤의 stage에 있는 instruction이 앞의 instruction이 끝나기도 전에 결과를 사용하려 할 때 발생합니다.

→ 뒤의 Insturction이 앞의 Instruction에 대하여 dependency를 가지고 있다.

(참고로 오른쪽 회색은 read, 왼쪽 회색은 write입니다.)

위 그림은 x19에 add의 결괏값이 들어가기 전에

아래 sub instruction의 Id stages에서 x19를 read 하려는 모습입니다.

이러한 것을 Data hazards라고 부릅니다.

 

이를 해결하기 위해서 간단하게 생각하면 3 clock cycle만큼 stall을 하면 됩니다.

하지만 그렇게 되면 그만큼 성능적으로 손해가 발생하게 됩니다.

 

이러한 것을 컴파일러가 해결해주기도 하지만, 만족스럽지는 않습니다.

해결 방법

 

Forwarding (Bypassing)

사이클 낭비가 없다!

Forwarding 방식은 ALU가 add에 대한 합을 구하자마자 sub에게 결과를 제공합니다.

add 명령어이기 때문에 어차피 MEM단계를 거칠 이유가 없습니다.

따라서 연산이 끝나고 바로 다음 명령어에 값을 전달해 줄 수 있는 거죠.

 

그림 상으로는 이렇게 표현되어 있지만 사실상 하나의 하드웨어 이기 때문에 ALU에서 나온 값이 다시 ALU에 들어가는 것입니다.

Forwarding은 오직 destination stage가 source stage보다 뒤에 있어야지만 가능합니다!

 

 

Load-Use Data Hazard

  • Bubble이 불가피하다.

위의 예시는 add, sub가 같은 R-type이었습니다

이 것을 x1 이 add의 합이 아닌 load의 x1이라고 가정해 봅시다.

lw에서 x1의 값은 add가 EX에서 값이 나오는 것과 달리 MEM 단계를 가야지 값이 나오기 때문에 forwarding을 해도 한 번의 pipeline stall이 불가피합니다.

 

이러한 것을 load-use data hazard라고 합니다.

 

이러한 것도 혹시 해결이 가능할까요??

네 가능합니다.

 

 

Reordering Code to Avoid Pipeline Stalls

예를 들어 아래의 C언어 코드가 있다고 가정해 봅시다.

a = b + e;  // x3 = x1 + x2
c = b + f;  // x5 = x1 + x4

위 코드를 어셈블리어로 변환하면 아래와 같이 나옵니다.

이렇게 되면 lw 다음에 add가 나오는 게 2번이나 나오기에

stall이 두 번이나 발생합니다.

 

위 식을 컴파일러는 pipeline stall을 막기 위하여 재구성(reorder) 합니다!

아래에 있던 lw를 위로 끌어올림으로써 문제를 해결하였습니다!

이렇게 되면 data hazard가 발생하지 않으므로 원래의 코드보다 2 cycles을 절약하게 되었습니다!

 

 

Control Hazard

(branch hazard)

Control Hazard는 conditional branch(beq…)를 통하여 PC값을 바꿀 때, 이미 pipeline에 있던 명령어들이 flush 되는 현상입니다.

→ 즉, 만약 Branch가 된다면 우리 했던 Instruction fatch들이 쓸모가 없어지는 것입니다.

Branch가 될지 말지는 MEM단계에서 나오는데 만약 Branch가 된다면 위 그림에서 3개의 잘못 fetch 된 것들을 flush(폐기처분)해버립니다.

→ 즉, 최소 3 cycle bubble이 발생한 것입니다.

 

 

해결 방법

  1. 첫 번째 방법은 하드웨어를 추가하여 Branch의 판별 시점을 ID stage로 앞당기는 것입니다.

기존 MEM stage에서 판별하던 것을 ID stage에 Adder(연산) Comparator(비교)를 추가하여 ID stage에서 판단하고 결과를 알아내는 것입니다.

그렇게 되면 다음과 같이 Cycle 손해를 줄일 수 있습니다.

비록 1 Cycle-Flush 가 생기긴 했지만 3 Cycle-Flush 손해가 일어난 것에 비하면 훨씬 좋은 결과입니다.

 

하지만, pipelines이 길어진다면 어떻게 될까요?

branch 결과를 일찍 알아내기도 쉽지 않을 것이고 Stall로 인한 부작용이 엄청나게 커집니다.

이를 해소하는 두 번째 방법이 있습니다.

해결 방법 두 번째는 아예 큰 단원으로 소개하겠습니다.

 

Branch Prediction

  • 컴퓨터는 실제로 Conditional branches를 다룰 때 Prediction을 합니다.

→ 미리 예측하여 conditional branch가 taken 할지 untaken 할지 정하는 것입니다.

예측이 실패해도 본전이고 예측이 성공하면 성능이 훨씬 좋아지기 때문에 예측을 해도 상관없는 것입니다.

오직 prediction이 실패할 때만 pipeline stall이 발생하는 것이죠.

한 가지 간단한 접근 방법은 항상 branches가 untaken 할 것이라고 예측하는 것입니다.

위 그림처럼

  • Prediction이 성공한다면 (untaken) 바로 다음 instruction으로 넘어가고 stall이 발생하지 않는 것이고
  • Prediction이 실패한다면 (taken) branch가 되고 stall이 발생하는 것입니다.

 

More Realistic Branch Prediction

Branch Prediction 종류로는 2가지를 들 수 있습니다.

Static branch prediction과 Dynamic branch prediction입니다.

  • loop문 같은 경우에는 항상 branch가 taken 된다고 가정해봅시다. 만약 Loop가 100번 실행된다고 한다면 99번은 맞추고 1번은 틀리게 됩니다.
  • Static Branch predicti`on은 실행하기 전 얻은 정보를 토대로 합니다. (실행 전에 정해놓는 것이죠.)
    • Static branch prediction은 backward branch (코드로 가정하면 위로)는 일어난다고 가정합니다.
    • forward branch(코드로 가정하면 아래)는 일어나지 않는다고 가정합니다.
  • Dynamic branch prediction은 runtime때 일어난 정보들을 토대로 합니다.
    • 하드웨어가 실제로 branch 동작들을 측정합니다.
    • e.g.) 각 branch의 최근 기록을 record(기록) 합니다.
    • 미래의 동작들은 최근 경향을 따를 것으로 가정합니다.
      • 그 가정이 틀린다면?
        • stall이 발생합니다.
        • re-fetching이 일어납니다.
        • history가 업데이트됩니다.
    • 생각보다 간단히 예측하고 현대엔 90%의 정확성이 나온다고 합니다.