4.5 An Overview of Pipelining

🔑Table of Contents

1. Pipeling Analogy
2. MIPS Pipeline
3. Pipeline 성능
4. Pipeline Speedup
5. Pipelining and ISA Design
6.  Hazards
7. Structure Hazards (구조적 해저드)
8. Data Hazards(데이터 해저드)
9. Data Hazards -- Forwarding (aka Bypassing(전방전달))
10. Data Hazards -- Fowarding --- Load-Usw Data Hazard
11. Code Scheduling to Avoid Stalls
12. Control Hazards
13. Control Hazards -- Stall on Branch 
14. control Hazards --- Branch Prediction
15. control Hazards --- MIPS with Predict Not Taken
16. control Hazards --- More-Realistic Branch Prediction
17. Pipeline Summary

---

📌 Pipeling Analogy

유추

• 파이프화된 빨래 : 겹치는 실행
• 병렬처리는 성능을 향상시켜준다

 

 

 

 

 

 

 

 

 

 

 

 

 

• 4번의 연속된 작업  = 속도향상 =기존실행시간/개선된시간
  • = 8/3.5 = 2.3배 속도향상됨

 

• 파이프라인 작업에서 속도향상
  • = 비 파이프라인 처리시간/ 파이프라인 처리시간
    • (작업수:n, 작업에 걸리는시간(예시) :2)
    • (파이프라인이 채워질 때까지의 초기시간 : 1.5, 단계마다 걸리는시간 : 0.5)
  • 2n / (1.5 + 0.5n)  ≒ 4 (파이프라인 단계 수가 4로 가정되어있기에 이론적으로 최대 4배의 성능향상이 가능함)

 

 

📌 MIPS Pipeline

• 5개의 stage. stage마다 하나의 단계를 수행함
  • IF : 메모리로부터 명령어를 불러옴 (Instruction Fetch)
  • ID : 명령어해석, 레지스터 read       (Instruction Decode & register read)
  • EX : EXcute operation(작업실행) 혹은 calculate address(주소계산)
  • MEM : access MEMory operand (메모리에 접근)
  • WB : Write result Back to register(레지스터에 결과기록) 

📌 Pipeline 성능

각 stage별 시간을 측정하면 register read나 write에는 100 p(=10^-12) second 소요

다른 stage들은 200ps

instruction	instr fetch	Register read	ALUop	Memmory access	Register write	Total time
lw	200ps	100ps	200ps	200ps	100ps	800ps
sw	200ps	100ps	200ps	200ps		700ps
R-format	200ps	100ps	200ps		100ps	600ps
beq	200ps	100ps	200ps			500ps

 

• 파이프라인화된 데이터경로와 single사이클의 데이터경로를 비교해보면
  • single사이클에서는 총 소요시간이 800ps
  • 파이프라인에서는 가장 긴 소요시간이  200ps

 

📌  Pipeline Speedup

• 만약 모든 stage들이 비슷한처리시간을 가지면 ( = 같은시간이라면)
  • (stage의 수)배의 성능향상효과

파이프라인 명령어 간 시간 = 비파이프라인 명령어 간 시간 / stage

• 모든 stage가 균등하지 않으면 속도향상의 효과는 더 적을것이다
  • 가장 느린 stage에 맞춰지므로
• 속도향상은 처리량을 늘려서 얻은 결과이다
  • 병렬식으로 동시에 여러 명령어를 실행시킴으로써
  • 지연시간(각 명령어 하나 실행에 걸리는 시간) 자체는 줄어들지 않음

📌 Pipelining and ISA Design

• MIPS ISA는 파이프라인에 적합한구조임
  • 모든 명령어는 32비트 ( 한 사이클안에 fetch(명령어 가져오기)와 decode(명령어해석)가능
  • 적은 종류의 규격화된 명령어 format (R형식, i 형식)
    • 한번에 decode하고 레지스터를 read가능
  • Load/Store addressing
    • 주소 계산은 3번째 stage에서 , 메모리접근은 4번째 stage에서 이루어짐
    • 즉, stage별로 다른 작업수행가능
  • memory operand의 정렬
    • memory access는 한 싸이클 안에 이뤄짐

※여기서 한 사이클이란 파이프라인에서 하나의 단계(IF, ID,EX,MEM,WB) 중 하나

 

📌 Hazards

• 다음 싸이클에서 다음 명령이 실행되는 것을 막아버리는 상황이 발생 할 수 있다
• 구조적 해저드 (필요한 하드웨어 자원이 이미사용중)
• 데이터 해저드 (다른 명령어가 데이터를 read/write하고있다면 완료까지 기다려야함) → 해결 : 전방전달, 코드 구조변환
• 제어 해저드 (어떤 명령어를 수행하기 위해 다른 명령어 결과에 의존하는경우) → 해결 : 브랜치에서 stall, 분기예측(무조건 아니라고 가정), 더 실제적인 분기예측)

📌 Structure Hazards (구조적 해저드)

• 하드웨어 자원을 이용하는 것에서 충돌
• single메모리를 사용하는 MIPS 파이프라인에서
  • lw/sw명령은 data접근을 위해 메모리에 접근한다
  • instruction fetch도 명령어를 가져오기 위해 메모리에 접근한다
  • 서로 동시에 진행할 수 없어 한 쪽이 대기하고, 해당 사이클을 지연시킨다 (파이프라인에 버블을 야기함)
• 파이프라인화된 데이터패스는 instruction memory와 data memory가 분리되어야한다
• 대부분 구조적 해저드는 자원의 부족으로 발생하며, 자원을 추가하면 해결되는 경우가 많음

 

📌 Data Hazards(데이터 해저드)

명령어는 다른 명령어가 데이터에 접근하는 것이 완전히 끝나는 것에 의존한다

(해당 대이터가 사용중이라면 대기)

add $s0, $t0, $t1
sub $t2, $s0, $t3

2stall, 2 사이클 공백발생

 

 

 

📌 Data Hazards -- Forwarding (aka Bypassing(전방전달))

계산 직후의 결과 바로 사용 (레지스터에 저장되기전 바로)

• 레지스터에 write되는것을 기다리지 않음
• datapath에 추가 연결 필요

 

📌 Data Hazards -- Fowarding --- Load-Use Data Hazard

항상 forwarding으로 모든 stall을 피할 수는 없을 수도 있다

• 결과가 필요한 순간에 아직 계산이 완료되지 않으면 
• 제 값을 끌어올 수도 없이 존재하지도 않으면 활용불가

 

• forwarding으로 해결이 불가능한 이유
  • forwarding은 ALU출력값을 바로 다음 명령어에 전달하는 방식
    • 하지만 Load-Use Data Hazard의 경우 값이 아직 메모리에서 읽히고 있어 ALU에도 값이 존재하지 않음

📝예제

lw  $s0, 20($t1)
add $t2, $s0, $t3

• lw
  • EX: 20 + $t1주소 계산 (ALU에서 사용)
  • MEM : 계산된 주소를 메모리에서 읽음
  • WB : 읽은 값을 $s0에 저장
• add
  • ID 단계 : $s0 값을 읽으려하지만 MEM단계가 끝나지 않아 $s0값이 준비되지않음

 

📌 Code Scheduling to Avoid Stalls

코드의 순서를 바꿔 다음 명령어에 필요한 결과값 load과정에서 발생할 stall 회피

 

예 ) A = B + E;  C = B + F;

WB 단계에서 준비되므로 각각 stall 1사이클 발생 → 2개의 stall발생해 파이프라인 효율이 저하됨

stall 2 → stall 0 

파이프라인 실행 사이클 수 ( 13 → 11)

 

📌 Control Hazards

• 제어신호로 인해 프로그램의 flow가 바뀔 수 있는 상황 (flow가 바뀔지도 모르기 때문에 직후 명령어 들이 바로 실행되지 못하는 해저드)
• 분기(branch)는 control의 흐름을 결정한다
  • instruction fetch는 분기 결과에 의존적이다 (PC +4일지, beq의 1로 다음 주소결과를 PC에 담을지)
  • 파이프라인은 항상 올바른 명령어를 가져오지 않을 수도 있다 (branch의 ID가 작업중일때)
• MIPS 파이프라인에서 
  • 브랜치 명령어의 레지스터값을 비교하는 것과 점프주소 계산을 미리해야한다

📌 Control Hazards -- Stall on Branch 

브랜치에서 stall

• add 문제없이 실행
• beq 명령어가 ID단계에서 비교작업을 수행
• ID에서 미리 비교하고 주소를 계산하더라도 ID가 끝나야 알수 있으므로 1 사이클 stall

📌 control Hazards --- Branch Prediction

분기예측 (분기명령어의 결과가 확정되기 전에 결과를 미리 예측해 실행하는 방법)

• 긴 파이프라인에서는 분기 결과가 확정될 때까지 여러 사이클의 Stall이 발생할 수있음
•  브랜치 결과 예측 (예측이 틀린경우만 stall발생)
• MIPS 파이프라인에서 브랜치 결과를 일어나지 않은것으로 예측(가정)할 수 있다 
  • 브랜치 명령 이후에 명령어 fetch를 지연없이 가능하다

 

📌control Hazards --- MIPS with Predict Not Taken

beq가 아니라면을 가정해, 연속된 (PC+4) 명령어를 바로 가져옴

branch결과가 맞으면 맞는 명령어를 새로 가져옴

 

 

📌control Hazards --- More-Realistic Branch Prediction

실제로 사용하는 것에 더 가까운 방식(위에서는 무조건 아닐것이라고 예측)

• Static branch prediction
  • 전형적인 분기동작을 기반으로함
  • 하드웨어 자원이 거의 필요하지 않다
  • Backward Branch는 항상 발생한다고 가정
    • loops에서 자주 나타나는 분기 
    • 프로그램의 흐름이 위쪽으로 이동
    • 반복문 종료 전까지 항상 Backward Branch 발생
  • Forward Branch는 발생하지 않는다고 가정
    • 조건문(if)에서 자주 발생
• Dynamic Branch Prediction
  • 실제 분기 동작을 기반으로 함
  • 이전 분기 히스토리를 저장하고 이를 기반으로 미래의 분기 결과를 예측(틀릴경우 :stall → refetching)
  • 프로그램 실행 중 계속 학습하며 성능을 최적화

특징	정적분기예측	동적분기예측
기본원리	고정된 규칙을 기반으로 예측	실행된 프로그램의 분기 결과를 추적하여 예측
예측방법	backward분기는 taken(발생), forward분기는 not taken(발생하지 않음)	분기 결과의 히스토리를 추적하여 예측
정확도	예측 정확도가 낮을수있음	실행 패턴에 따라 예측 정확도가 높음
자원소모	적은 자원소모	많은 자원 소모(히스토리 저장 및 관리 필요)
성능저하	예측 실패 시 성능저하 없음 (하지만 비효율적)	예측 실패시 스톨발생, 성능저하
적용 예시	고정된 패턴(루프(반복문),if(조건문))	동적인 분기 패턴에 적합(다양한 조건문)

 

📌 Pipeline Summary

• pipelining은 CPU에서 명령어를 병렬적으로 처리해 처리량을 증가시키는 기법
  
  • 한 명령어의 실행속도가 아니라 동시에 여러 명령을 가능케하는 양을 늘림
  • 각 명령어는 같은 latency(지연시간)을 갖는다
• 명령어 set의 설계방식(ISA)는 pipeline 구현의 복잡도에 영향을 준다
  • ISA가 간단하면 pipeline 구현도 쉬워진다