⛓️‍ 파이프라인

파이프라인(Pipelining)이란?

파이프라이닝은 프로세서의 처리 효율을 극대화하기 위한 설계 방식이다.

핵심 아이디어는 "명령어를 구성하는 여러 단계들을 분리하고 병렬적으로 실행하는 것"으로,
SEQ 구조에서는 모든 명령어가 한번의 클럭사이클에 한번의 인스트럭션이 실행되었지만,
Pipeline에서는 서로 다른 명령어가 CPU 내 각기 다른 단계에서 동시에 실행된다.

✅ 파이프라이닝의 특징

• 클럭 사이클 단축: 각 단계에 맞는 최적화된 동작만 수행하므로 클럭 주기를 줄일 수 있다.
• 명령어 처리량 증가: 명령어를 동시에 처리할 수 있어 전체 Throughput 상승한다.
  • 다만, 또 다른 지연시간이 발생할 수도 있다.
• 하드웨어 자원 활용률 증가: 모든 유닛(ALU, 메모리 등)이 매 사이클마다 바쁘게 일한다.

비파이프라인 구조

🔼 Unpipelined Hardware (비파이프라인 구조)

• 단일 조합 논리 회로(Comb. logic)가 300ps 동안 작동
• 출력값은 레지스터에 저장하는데 20ps 소요된다.

📌 문제점

• 다음 명령어는 이전 명령어가 완전히 끝나야만 시작 가능하다.
• 조합논리 전체가 한 번에 동작해야 하므로 클럭 속도 느리고 자원 낭비도 크다.

파이프라인 구조

🔼 3단계 파이프라인 구조

• 동일한 작업을 100ps짜리 3개의 논리 블록(A, B, C) 으로 분할
• 각 단계 사이에는 레지스터(20ps) 존재하여 클럭에 따라 값 넘김
• 총 명령어 지연 시간은 360ps지만, 이는 latency (한 명령어가 끝나는 시간)일 뿐!

✅ 이점

• 3단계가 독립적으로 돌아가므로 각 명령어가 겹쳐 실행됨
• 자원 낭비 없이 모든 논리 블록이 바쁘게 일함
• latency는 더 길어도 throughput은 훨씬 높다.

🔥 즉, 우리는 일부 하드웨어를 추가하는 대신 시스템의 처리량을 개선할 수 있다.

개념	의미	누가 유리?
Latency	한 명령어가 시작해서 끝날 때까지 걸리는 시간	비파이프라인 구조가 유리
Throughput	단위 시간당 몇 개 명령어를 처리할 수 있는가	파이프라인 구조가 유리

---

🧩 파이프라인 동작

🔗 상세 동작

1️⃣ Time = 239 : 클럭 신호가 작동하기 직전
I1 : Stage B에서 연산 중
register A 🔗 B : A와 관계 없이 B의 이전 값 저장 중
I2: Stage A에서 연산 중
register B 🔗 C : 데이터 x
I3 : 아무 동작도 안함
register C 🔗 : 데이터 x

📌 클럭 상승이 발생하기 전 까지는 연산이 끝났다고 해도 레지스터에 저장이 안됨

2️⃣ Time = 241 : 클럭 상승이 발생한 직후
I1 : Stage C로 들어가 연산 시작
register A 🔗 B : A의 연산 결과 즉, I2의 A연산 처리가 저장됨
I2: Stage B로 들어가 연산 시작
register B 🔗 C : B의 연산 결과 즉, I1의 B연산 처리가 저장됨
I3 : Stage A로 들어가 연산 시작중
register C 🔗 : 데이터 x

📌 클럭 상승이 발생 했기 때문에 모든 파이프라인 레지스터가 입력값을 캡쳐하고 다음 스테이지로 넘어옴

3️⃣ Time = 300 : 조합 논리 연산 중
I1 : Stage C의 조합 논리 안에서 연산 중
register A 🔗 B : 변화 발생 없음
I2: Stage B의 조합 논리 안에서 연산 중
register B 🔗 C : ㅋ변화 발생 없음
I3 : Stage A의 조합 논리 안에서 연산 중
register C 🔗 : 변화 발생 없음

📌 파이프라인의 병렬성이 드러나는 구간으로 모든 인스트럭션이 동시에 다른 스테이지에서 작업 중

4️⃣ Time = 359 : 다음 클럭 상승 직전
I1 : 인스트럭션 결과가 C 레지스터의 입력단에 도착
register A 🔗 B : 변화 발생 없음
I2: 인스트럭션 결과가 B 레지스터의 입력단에 도착
register B 🔗 C : 변화 발생 없음
I3 : 인스트럭션 결과가 A 레지스터의 입력단에 도착
register C 🔗 : 변화 발생 없음

⏱️ 클럭 신호

사진을 보면 한 사이클 내에서 클럭이 상승했다가 하강하는 것을 볼 수 있다.
이걸 rising edge-triggered 라고 하는데,
클럭이 오를때에만 레지스터가 입력단에 들어온 데이터를 캡쳐하고 이후 동작을 시행한다.
클럭이 하강하는건 명령어를 실행하라는 신호를 종료한다는 의미일 뿐, 그 순간에는 아무 의미가 없다.

즉, 사실상 클럭이 상승한 순간만 중요하고, 나머지는 조합 논리를 통해 신호를 전파 하는 시간이다.

‼️ 단, 클럭이 너무 빠르면 아직 연산 중인 인스트럭션이 있는 경우
레지스터에 입력이 유효하지 않게 되어 치명적인 결과를 낼 수 있다.

예시

⏱️ 조합 논리 연산 시간이 100ps 걸리고
레지스터 + 셋업 시간까지 고려하면 전체 클럭 주기는
"120ps 정도로 설정해야 안정적이다"

셋업 시간 참고

T_clock ≥ T_comb + T_setup + T_clk_to_q

항목	설명
T_comb	조합 논리의 최대 연산 지연 시간
T_setup	레지스터가 입력을 안정적으로 받기 위한 최소 준비 시간
T_clk_to_q	이전 레지스터의 출력이 변하는 데 걸리는 시간 (출력 딜레이)

---

⚠️ 파이프라인의 한계

다음은 파이프라인의 효과를 축소시키는 요인들이다.

🗂️ 비균일분리 Nonuniform Partitioning

앞에서 봤던 예시와 달리 위의 그림은 각 단계에서 발생하는 지연시간이 다양하다.

효율적이지 못한 클럭 속도

모든 인스트럭션이 올바른 타이밍에 결과를 내는 것을 보장하기 위해서는 클럭 속도를 고려할 때
가장 늦게 끝나는 단계의 시간지연을 고려해야 한다.
즉, 총 연산 시간은 동일하더라도 클럭 속도로 인하여 성능이 떨어진다.

📉 줄어드는 Deep Pipelining의 효과

무시할 수 없는 레지스터 시간 지연

작업의 단계를 여러개로 쪼개는 것은, 즉 매우 깊은 파이프라인을 이용하는 경우 같은 작업에 대해서도
연산의 양이 줄어들기 때문에 속도가 증가한다.

단, 깊은 파이프라인은 그만큼 중간에 레지스터도 많다는 것을 의미하고
레지스터에 저장해야 하는 지연 시간을 무시할 수 없게 된다는 것이다.

🛠️ 파이프라인형 Y86-64의 구현

☑️ PC 갱신 단계 재배치

기존 SEQ

Fetch → Decode → Execute → Memory → Writeback → PC update

• 현재 명령어의 실행 결과를 기반으로, 다음 명령어 주소를 결정함

🔁 실행 흐름 (사이클 N 기준)

1. instruction a의 전체 단계 수행 (Fetch ~ Writeback)
2. 싸이클 끝에서 a의 실행 결과로 PC 계산
3. 계산된 PC는 다음 싸이클에 적용
4. 따라서 instruction b의 Fetch는 한 싸이클 늦게 시작

⛔ PC 계산과 Fetch가 순차적으로 일어나기 때문에,
다음 명령어 실행이 항상 지연됨

SEQ⁺

PC update → Fetch → Decode → Execute → Memory → Writeback

• PC 연산을 클럭 싸이클 시작 시점으로 앞당긴 구조
• instruction a가 실행되는 동안 다음 명령어(b)의 주소 계산에 필요한 정보를
  → pIcode, pCnd, pValP 같은 상태 레지스터에 저장해둠
• 다음 싸이클이 시작되자마자 → 이 값을 이용해 b의 주소를 즉시 계산
• 계산된 주소는 그 싸이클 안에서 즉시 Fetch에 사용

🔁 실행 흐름 (사이클 N 기준)

1. instruction a가 실행되며 필요한 신호들을 상태 레지스터에 저장
2. 동시에, 이전에 저장해 둔 신호들로 PC 계산 + instruction b Fetch 수행
3. instruction b는 a와 겹쳐서 실행되기 시작함

✅ PC 연산과 Fetch가 같은 싸이클 안에서 동시에 이루어지므로,
다음 명령어를 빠르게 시작할 수 있음

‼️ SEQ → SEQ⁺

-Circuit retiming 기법 사용

• 리타이밍(retiming): 회로의 논리적 동작은 유지하면서도 상태 요소(레지스터)의 위치를 재배치하는 기술

☑️ 파이프라인 레지스터 삽입

• 사진에서 보이는 하늘색 박스들이 파이프라인 레지스터이며,
  해당 유닛들을 제외하고는 SEQ와 거의 동일한 하드웨어 유닛들로 구성되어 있다.

🔩 Pipeline 레지스터 구조 (F, D, E, M, W)

각 명령어가 다음 스테이지로 이동할 때 필요한 정보는 Pipeline Register에 저장된다.

레지스터	포함 정보
F	프로그램 카운터의 예측값을 저장
D	해독 단계가 처리하기 위해 가장 최근에 선입한 인스트럭션에 관한 정보 저장
E	레지스터 파일로부터 읽어들인 값, 가장 최근에 해독한 인스트럭션에 관한 정보 저장
M	가장 최근에 실행한 인스트럭션의 결과 및 분기조건, 분기 목적지에 관한 정보 저장
W	레지스터 파일에 기록 할 계산 결과와 ret 인스트럭션을 위한 리턴주소 저장

각 Pipeline Register는 클럭 상승 시점에 업데이트되며, 명령어들이 스테이지 간 정확히 연결될 수 있도록 정보를 전달한다.

---

📌 신호의 재배치 및 재명명

PIPE−는 SEQ, SEQ⁺와 달리 여러 명령어가 동시에 파이프라인을 따라 흐르도록 설계된 구조이다.
즉, 각 명령어가 동일한 신호 이름을 동시에 사용할 수 있기 때문에,
정확한 신호 구분 및 명시적 파이프라인 레지스터 구성이 중요하다.

☑️ 파이프라인 신호 명명 규칙

• 파이프라인 레지스터에 저장되는 신호는 해당 레지스터 이름의 대문자 접두어를 붙인다:

  • 예: D_stat, E_stat, M_stat, W_stat

• 해당 스테이지에서 방금 계산된 신호는 소문자 접두어를 붙인다:

  • 예: f_stat (Fetch), m_stat (Memory)

• 프로세서 전체 상태 (Stat)는 W 레지스터에 저장된 상태를 기반으로 Writeback 단계에서 결정된다.

  • stat는 프로세서가 명령어 실행 도중 해당 인스트럭션의 상태를 나타내는 코드이다.
  • 즉 만약 어떤 단계에서(예를 들어, decode 단계) SADR/SINS 등의 오류가 발생하면 일단 무시하고 넘어간 뒤, write_back의 stat 에서 오류를 감지한다.

🔒 명령어 정보 일관성 유지 원칙

• SEQ⁺에서는 dstE, dstM 등의 신호를 바로 레지스터 파일에 연결할 수 있었지만,
• PIPE−에서는 이러한 목적지 정보도 파이프라인을 타고 흐르도록 한다.

📌 Why?:

• Writeback 시점에서 **값(valE, valM)**과 **레지스터 ID(dstE, dstM)**가 같은 명령어에 속한 값이어야 하기 때문
• 그렇지 않으면 다른 명령어의 결과를 엉뚱한 레지스터에 쓰는 심각한 오류가 발생한다

✅ 하나의 명령어에 관련된 모든 정보는 동일한 파이프라인 레지스터에 담아서 흐르게 한다.

---

🔧 Select A 블록

• SEQ, SEQ⁺에는 valP 또는 레지스터 파일에서 가져온 값을 직접 사용하는 Data 블록이 있었음
• PIPE−에서는 이를 제거하고 Decode 스테이지에 "Select A" 블록을 도입함

Select A의 동작

• valP (D 레지스터로부터) 또는 Register File에서 읽은 값을 선택하여 valA 생성
• valA만 파이프라인으로 전달하여 필요한 스테이지에서 사용함
  즉, 둘 다 넘기는게 아니고 필요한 것만 넘긴다 !

장점

• 레지스터에 저장되는 데이터 양 줄어듦 → 하드웨어 저장 용량 축소 및 설계 간소화
• 불필요한 신호 분산 방지 → 파이프라인 레지스터에 필요한 값만 보냄

---

🔄 제어 의존성 처리

PC 값 추정

결국 파이프라인 설계를 함으로써 한번에 한 인스트럭션만 처리할 수 있는 시스템에서 한번에 여러 인스트럭션을 처리함으로써 매 클럭 사이클마다 새로운 인스트럭션을 실행하고 궁극적으로는 완료시키는 목적을 다룰 수 있는 것이다.

다만, 이런 목적을 위해서는 현재 인스트럭션을 선입한 직후 바로 다음 선입할 명령어의 주소를 결정해야 한다.

목표:

• 매 싸이클마다 새로운 Fetch가 수행되어야 함

문제:

• 조건 분기(jXX)는 **실행 결과(분기 여부)**를 Execute 스테이지에서야 알 수 있음
• ret은 return 주소를 Memory 스테이지에서야 알 수 있음

해결 전략:

1. 분기 예측(branch prediction) 사용
2. ret은 예측 불가 → stall 발생 허용

분기 예측 정책

• 조건 분기(jXX)는 항상 taken으로 예측
  • 즉, 다음 PC는 valC로 설정
• 이 예측이 틀리면 → 나중에 파이프라인을 flush하고 다시 fetch함

ret 처리

• return address는 스택 꼭대기에 있기 때문에 예측 불가
• ret이 Writeback을 완료할 때까지 이후 인스트럭션을 처리하지 않도록 하는 방법을 사용

---

Fetch 스테이지

주요 블록:

• Select PC:

  • instruction memory에서 사용할 주소 선택

  • 선택지:

    1. 예측된 PC (predicted_pc)
    2. 이전 분기 명령어의 valP (M_valA)
    3. ret 명령어의 return address (W_valM)

• Predict PC:

  • 다음 명령어 주소 예측
  • 조건 분기는 항상 taken → valC 반환
  • 그 외는 valP 반환

• F 레지스터:

  • 예측된 PC(predicted_pc)를 저장해 다음 Fetch 기준 주소로 사용

---

PIPE−는 SEQ⁺와는 달리 여러 명령어가 동시에 흐르는 구조이기 때문에,
신호의 명확한 구분, 예측 기반의 제어 흐름 처리, 일관된 상태 관리가 필수이다.

🧨 해저드(Hazard)와 해결 전략

위에서 본 것 처럼 파이프라인을 도입하는 경우 연속되는 인스트럭션들 간에 의존성으로 인해 문제가 발생할 수 있다.
이렇게 파이프라인이 의존성에 의해 잘못된 계산을 야기할 가능성이 있을 때 이들을 해저드라고 부른다.

🔶 Data Hazard

한개의 인스트럭션이 계산한 결과가 다음에 오는 인스트럭션을 위한 데이터로 사용되는 경우 데이터 의존성이 발생한다.

한 명령어가 아직 결과를 레지스터에 쓰기 전에, 다음 명령어가 그 값을 필요로 할 때 발생

예시:

1: mrmovq 0(%rbx), %rax   # 아직 %rax에 값이 안 들어감
2: addq %rax, %rcx        # %rax를 읽으려 함 → forwarding or stall 필요

해결:

• Forwarding: 값이 아직 쓰기 전 단계에 있어도 ALU 결과를 바로 다음 명령어에 제공
• Stalling: 값을 기다릴 때까지 Decode 단계를 멈추고 nop을 삽입

🔶 Control Hazard

한개의 인스트럭션이 다음에 따라오는 인스트럭션의 위치를 결정하는 경우 제어 의존성이 발생한다.

분기 명령어 (jXX, call, ret)의 결과가 나오기 전에 다음 명령어의 PC를 알 수 없음

해결:

• 정적 분기 예측 (예: 안 튄다고 가정)
• 분기 실패 시 flush (D, E 단계에 nop 삽입)

파이프라인 실행 예시

☑️ 특징

• 중간에 세개의 nop 인스트럭션이 존재한다.

🚨 문제

• 발생하지 않는다.
  • nop 인스트럭션이 데이터 의존성을 갖는 인스트럭션들 간에 시간지연을 발생시키고 있기 때문
    

☑️ 특징

• nop 인스트럭션이 2개로 줄었다.

🚨 문제

• 레지스터 %rax에 잘못된 값이 들어간다.
  • add 인스트럭션이 실행되는 사이클에서 %rax 레지스터에 값을 넣는 인스트럭션이 마무리가 되지 않았기 때문
    

☑️ 특징

• nop 인스트럭션이 1개로 줄었다.

🚨 문제

• 레지스터 %rax, %rdx 모두 잘못된 값이 들어간다.
  • add 인스트럭션이 실행되는 사이클에서 %rax, %rdx 모두 작업이 완료되지 않았기 때문
    

☑️ 특징

• nop 인스트럭션이 존재하지 않는다.

🚨 문제

• 여전히 레지스터 %rax, %rdx 모두 잘못된 값이 들어간다.
  • add 인스트럭션이 실행되는 사이클에서 %rax, %rdx 모두 작업이 완료되지 않았기 때문

---

✋🏻 해저드 회피 by Stalling

🔹 Stalling이란?

Stalling: 해저드가 발생했을 때, 해당 명령어를 Decode 단계에서 정지시키고, 후속 명령어들도 정지시켜 소스 오퍼랜드를 제대로 생성할 수 있을때까지 멈추는 방법

📌 스톨 조건 감지

• 파이프라인 컨트롤 로직은 Decode 단계에 있는 명령어가 사용하는 소스 레지스터(%rdx, %rax)가
  • Execute, Memory, Write-back 중 어느 단계에서라도 갱신될 예정이라면,
• 그 명령어를 Stall한다.

🕓 예시: addq 명령어

• Decode 단계에서 addq가 있을 때,
  • 앞선 명령어가 %rdx 또는 %rax를 Write 중이라면 → addq는 Decode에 멈춘다.
  • prog2에서는 1 사이클 동안 스톨 발생한다.

🚫 Fetch도 멈춤

• Decode가 멈췄다면 Fetch도 멈춰야 한다.
• 이때는 Program Counter(PC)를 고정시켜서 같은 명령어를 반복적으로 fetch하게 한다.

💨 버블(Bubble) 주입

Bubble은 동적으로 삽입된 nop 명령어와 같다
레지스터, 메모리, Condition Codes, 프로그램 상태에 영향을 주지 않음

✔️ 왜 버블이 필요한가?

• Decode에서 명령어가 멈췄다면,
  • Execute 단계는 비게 됨
  • 이때 해당 자리에 Bubble을 삽입해서 파이프라인 흐름을 유지함

🔁 반복 동작

• Decode가 멈춰 있는 동안마다 → Execute에 Bubble 삽입

📉 Stalling의 한계

• 스톨링 기법은 구현이 쉽다.
  • 성능이 좋지 않음
  • 이유: 연속된 명령어 간에 레지스터 사용이 겹치는 경우가 많아서 스톨이 빈번하게 발생함

---

✋🏻 해저드 회피 by Forwarding

🔹 Forwarding이란?

**Forwarding(또는 Bypassing)**은 계산된 값을 파이프라인의 뒤쪽에서 앞쪽으로 직접 전달함으로써 데이터 해저드를 피하는 방법이다.

즉, 레지스터에 값이 아직 안 써졌더라도, 해당 값이 어딘가 파이프라인에 있으면 그 값을 미리 전달해서 사용하는 방법

이러한 데이터 포워딩은 기본 하드웨어 구조에 추가적인 데이터 연결과 제어로직을 필요로 한다.

🕓 예시: addq 명령어

상황:

• addq 명령어가 Decode 단계에서 %rax를 읽으려 함
• 그런데 Write-back 단계에 %rax에 값을 쓸 예정임

✅ 해결책:

• 레지스터 파일을 기다리지 않고 → Write-back 단계의 W_valE 값을 valB로 사용!
• 결과적으로 stall 없이 명령어가 진행됨

명령 종류	값을 생성하는 단계	포워딩 가능 시점	대표 명령어	예시
연산 계열 (ALU 사용)	E 단계	E 다음 사이클부터 (= D에서 사용 가능)	addq, irmovq, rmmovq, OPq 등	addq %rbx, %rax irmovq $10, %rbx
메모리 읽기 계열	M 단계	M 다음 사이클부터 (= D에서 사용 가능)	mrmovq, popq	mrmovq 0(%rdx), %rax

---

Forwarding vs Stalling 비교

항목	Forwarding	Stalling
동작 방식	뒤 단계에서 앞 단계로 값 전달	명령어 정지 & bubble 삽입
성능	✅ 빠름 (stall 없음)	❌ 느림 (stall 발생)
구현 복잡도	높음 (포워딩 회로 필요)	낮음 (단순 stall 로직)
활용 예시	prog2~prog4	prog2~prog4 (버블 삽입 필요 시)

---

✋🏻 해저드 회피 by Load/Use Hazard와

🧨 Forwarding만으로 해결 불가능한 경우

• 예: mrmovq가 메모리에서 %rax로 값을 로드하고,
  • 바로 다음 명령어(addq)가 %rax를 소스로 사용하면?
• 문제: mrmovq는 메모리(M) 단계에서야 값이 유효한데,
  • addq는 Decode(D) 단계에서 그 값을 필요로 함
• 이건 마치 미래에서 값을 가져오는 것과 같기 때문에, forwarding만으로는 해결 ❌

✅ 해결책: Stalling + Forwarding 조합 → Load Interlock

• mrmovq가 Execute(E) 단계일 때, 컨트롤 로직이 다음 명령어(addq)가 그 값을 필요로 한다고 판단
• Decode(D) 단계의 addq를 1 사이클 스톨
• Execute(E)에는 Bubble 삽입
• 그 다음 사이클에 Memory(M) 단계에서 %rax 값이 나오면 → forwarding으로 전달

📌 Load Interlock

• Forwarding이 불가능한 Load-Use Hazard를 처리하는 유일한 방법
• bubble 1개만 삽입하면 되므로 최소한의 stall로 해결 가능
• forwarding과 함께 사용하면 모든 데이터 해저드를 처리 가능

---

✅ 해저드 회피 요약

“Forwarding + Load Interlock 조합으로 모든 데이터 해저드를 해결할 수 있다!”

• Forwarding은 대부분의 해저드를 해결
• Load-Use Hazard는 예외 → Load Interlock (stall + forward) 필요
• bubble 삽입은 최소 1개 → 높은 throughput 유지 가능 💪