[컴퓨터구조#2-1] 파이프라인(Pipelining) - 기초

참고: Computer Architecture: A Quantitative Approach (5th edition) - Appendix C. Pieplining: Basic and Intermediate Concepts

책의 부록 내용을 바탕으로, 이번 글에서는 파이프라인에 대한 내용을 되짚어 볼 것이다. 파이프라인을 왜 적용해야 하는지, 이점이 무엇인지, speedup은 어떻게 되는지, MIPS 아키텍처에 파이프라인을 적용하는 경우 datapath가 어떻게 되는지 알아볼 것이다. 

목차

1. Basic Pipelining

- Performance factors, Amdahl's law

- MIPS datapath with and without pipeline

- benefits, speedup

2. Pipeline Hazards

3. Branch Prediction

---

1. Basic Pipelining

파이프라이닝이란, execution에서 여러 명령어들이 겹치게 하는 구현 기술이다.  한 명령어를 실행하는 데 존재하는 액션을 병렬적으로 활용하는 것이다. 파이프라인의 서로 다른 단계는, 명령어의 서로 다른 부분을 병렬적으로 처리한다.

성능 측정: Performance Factor, Amdahl's law

파이프라인 설계자의 목표는 각 파이프라인 단계의 길이의 균형을 맞추는 것이다. 만약 각 단계들이 완벽하게 균형 맞춰져 있다면, 파이프라인 프로세서의 명령어 당 수행 시간은 (이상적인 경우) Unpipelined machine의 명령어당 시간 / 파이프라인 단계 수가 될 것이다. 이 경우 파이프라이닝을 통한 speedup은 정확히 stage 개수가 된다. 하지만, 일반적인 경우에서 각 단계는 이처럼 완벽하게 균형 잡혀 있지 않고, 심지어는 오버헤드도 포함하고 있다. 즉 파이프라인 프로세서에서 명령어당 수행 시간은 minimum possible value에 가까워질 수는 있어도 정확히 일치할 수는 없다.

모든 명령어들이 수행되는 데 동일한 시간이 걸리는 것은 아니다. 즉, 수행 시간(execution time)은 수행된 명령어 수와 명령어당 평균 수행 시간을 곱해서 생각해볼 수 있다.

→ #CPU clock cycles for a prgoram = #Instructions for a program * Average clock cycles per instruction

 파이프라이닝은 명령어당 평균 수행 시간을 줄여준다. 관점에 따라서 이는 CPI를 줄인다고 볼 수도 있겠다. 

• CPI, Clock cycles Per Instruction: 각 명령어가 실행되는 데 드는 평균 클럭 사이클 수

 

성능 측정(CPU time)을 위한 일반적인 방벙식은 다음과 같다.

• CPU time = #Instructions * CPI * clock_cycle
  • 혹은, CPU time = #Instructions * CPI / clock_rate

이는 성능에 영향을 주는 세 가지 주요 factor로 이루어져 있다.

- CPU 실행 시간: 프로그램을 돌려서 확인할 수 있음

- clock cycle(clock rate): 보통 주어짐

- #Instructions: 구현 디테일을 몰라도, profiler나 simulator를 통해 측정 가능

- CPI: 명령어 종류와 ISA 구현 방식에 따라 달라짐

 

암달의 법칙: 컴퓨터의 특정 부분을 향상시킴으로써 전반적인 성능의 부분적 개선을 기대하는 것

T_improved = T_affected / (improvement factor) + T_unaffected

(예시) 전체 100s의 실행 시간 중, 80s를 차지하는 부분을 개선 → T_imp = 80 / n + 20

즉, make the common case fast

 

MIPS Datapath

RISC 아키텍처는 다음과 같은 특징을 가진다.

• 데이터에 대한 모든 연산은 레지스터에 있는 데이터에 적용되며 보통 전체 레지스터를 바꾼다(32/64bit).
• 메모리에 영향을 주는 연산은 load와 store뿐이다.
• 명령어 형식은 개수가 매우 적고 모든 명령어는 하나의 사이즈이다.

RISC를 기반으로 하는 MIPS ISA는 다음 세 종류의 명령어를 가진다.

(1) ALU 연산: 1~2개의 레지스터와 sign-extended immediate를 받아 연산하여 결과를 레지스터에 저장

(2) Load와 Store 연산: base register를 source로 삼고, immediate field(오프셋)을 받아 둘의 합을 effective address로 삼아, effective address에 있는 데이터를 destination register에 불러오거나(load), source register에 있는 데이터를 effective address에 저장한다(store).

(3) Branch와 Jump 연산: 조건에 따라서 control을 통제하거나(branch), 조건 없이 다른 명령어로 이동시킨다.

 

이를 바탕으로, MIPS는 보통 5단계의 clock cycle로 구현된다: IF, ID, EX, MEM, WB

• IF (Instruction Fetch): PC를 바탕으로 메모리에서 현재 명령어를 fetch해온다. 이후 PC+4를 통해 PC가 다음 명령어를 가리킬 수 있도록 업데이트.
• ID (Instruction Decode): 명령어를 해독(decode)하고 register source specifier에 해당하는 레지스터 값들을 읽어온다.
• EX (Execution): ALU 연산인 경우, ID에서 준비된 레지스터 값을 바탕으로 계산을 수행
• MEM (Memory): load/store 연산인 경우
• WB (Write Back): 값을 레지스터에 저장하는 ALU 연산이거나 load인 경우, 연산 결과를 레지스터 파일에 저장

이를 바탕으로 파이프라인 없이 구현된 MIPS Datapath는 다음과 같다. 

간단한 MIPS Datapath

이 상태에서는 한 번에 하나의 명령어만 실행된다. 각 단계(IF/ID/EX/MEM/WB)마다 한 사이클이 걸린다고 하면, 하나의 명령어를 수행하는 데 4~5 사이클이 소요되는 것이다. 

하지만, 하나의 단계가 수행되는 동안 나머지 단계는 하는 일 없이 기다려야 하기 때문에 비효율적이다. 다음과 같이 단계를 쪼개고, 각 단계에서 연속적으로 서로 다른 명령어를 처리하도록 만들 수 있다.

이것이 파이프라인이 적용된 MIPS의 Datapath이다.

Pipelined MIPS Datapath

 

Pipelining Benefits & Speedup

즉, 다음과 같이 5개의 명령어를 수행하는 데 9번의 사이클만이 소요되는 것을 알 수 있다. 기존 파이프라인이 없는 아키텍처에서는 각 명령어당 4~5 사이클이 필요했으므로, 최소 20번의 사이클이 소요되었을 것이다.

간단한 RISC 파이프라인

수식으로 다음과 같이 생각해볼 수 있다.

파이프라인 적용 전	t_clk = t_F + t_R + t_X + t_M + t_W
파이프라인 적용 후	t_clk = max(t_F, t_R, t_X, t_M, t_X) + t_latch

만약 모든 단계에 같은 시간이 걸리는 균형 잡힌 이상적인 상태라면, 다음과 같이 stage 수에 비례하여 가속된다. 

• 명령어 수행 시간_pipelined = 명령어 수행 시간_nonpipelined / #Stages

만약 균형 잡혀 있지 않은 상태라면, 이보단 덜 가속될 것이다. 또한, 이 가속(speedup)은 throughput을 늘림으로써 이루어진 것이지 latency(명령어당 시간)이 줄어서 가속되는 것이 아니다.