[Introduction of Computer Architecture] Pipelining

[4.5 Pipeline]

> 파이프라이닝(pipelining); 여러 명령어가 중첩되어 실행되는 구현 기술

* 병렬로 동작하여 같은 시간에 더 많은 instrution을 끝낼 수 있다. 

* 하나의 instrunction을 수행하는 시간을 줄이는 것이 아니라, 여러 instruction의 전체 수행 시간을 줄인다. 

-> 지연 시간(execution time 혹은 latency)보다는 처리율을 향상

 

> 단일 사이클 vs. 파이프라인 성능

# 단일 사이클

모든 명령어가 한 클럭 사이클만큼 필요 -> 가장 느린 명령어를 수용 가능할 만큼 클럭 사이클이 길어야 한다. 

 

# 파이프라인

모든 파이프라인 단계가 한 클럭 사이클만큼 필요 -> 가장 느린 동작을 수용 가능할 만큼 클럭 사이클이 길어야 한다.

 

> Pipeline Hazards

프로세서가 다음 명령어(instruction)을 처리할 수 없는 상황

# Structural hazards (구조적 해저드)

같은 클럭 사이클에 실행하기를 원하는 명령어 조합을 하드웨어가 지원할 수 없는 상황

-> 자원(하드웨어)의 충돌로 여러 명령이 동시 수행시 발생한다.

 

# Data hazards (데이터 해저드); by 종속성

명령어를 실행하는 데 필요한 데이터가 준비되지 않아 계획된 명령어가 적절한 클럭사이클에 실행될 수 없는 상황

-> 미수행된 명령의 결과값 참조 시도 발생

 

=> 해결책: 전방전달(forwarding), 우회전달(bypassing)

프로그래머가 볼 수 있는 레지스터나 메모리에 아직 나타나지 않은 데이터를 기다리기보다는 내부버퍼로부터 가져온다.

* 파이프라인에서 내부버퍼는 pipeline registers에 해당

BUT, 전방전달로 모든 파이프라인 지연을 방지할 수 없다. 

적재-사용 데이터 해저드(load-use data hazard)의 경우, 전방전달을 해도 한 단계가 지연(파이프라인 지연, 거품)되어야 한다. 

 

# Control hazards (제어 해저드)

명령어의 실행순서를 변경하는 Branchm Jump 등 분기 명령에 의해 발생하여 처리된 명령 무효화

=> 해결책

1. 분기 시 지연 (stall on branch)

2. 분기 예측 (branch prediction)

실제 분기 결과가 확인될 때까지 기다리는 대신, 분기 결과를 가정하고 그 가정하에 파이프라인을 진행해 나가는 방법

3. 지연 결정 (delayed decision)

 

[4.6 Pipelined Datapath and Control]

> MIPS Pipelined Datapath

명령어를 5단계로 분류

= 다섯 단계의 파이프라인

= 한 클럭 사이클에 최대 5개의 명령어가 실행 중일 수 있다. 

 

# 각 명령어 실행 단계

1. IF: 명령어 인출

2. ID: 명령어 해독 및 레지스터 파일 읽기

3. EX: 실행 또는 주소 계산

4. MEM: 데이터 메모리 접근

5. WB: 쓰기(write back)

 

# Pipeline register

각 명령어 실행 단계 사이 마다 register(flip-flop)이 필요하다.

-> 파이프라인 단계를 분리하는 역할이자, 후속 파이프라인 단계에서 필요한 정보를 필요단계까지 전달

 

> 파이프라인 제어

Instruction마다 control 신호가 다르기 때문에 단계가 넘어갈 떄마다 레지스터에 저장해주어야 한다. 

But, 모든 신호를 매번 다 저장하면 공간낭비이기 때문에, 단계별로 사용하는 신호를 나눈 다음, 더이상 필요없는 신호들은 다음 단계로 갈 때 저장하지 않도록 한다. 

 

[4.7 Pipeline Hazards]

> Data Hazards in ALU Instructions

> Data Hazards를 해결하는 방법

# Bypass

read와 write가 동시에 같은 레지스터에서 발생하는 경우에 사용하는 방법; 첫째줄과 넷째줄처럼!!

Read Register ID와 Write Register ID가 동일하다면 old value가 아니라 updated value를 읽도록 한다. 

 

# Forwarding

-> Arithmeic Operation에서는 bypass와 forwarding으로 data hazard 해결가능하다.

 

# Data Hazard Detection; Forwarding의 조건(Forwarding Conditions - Rs)

• Register ID의 일치 여부 확인
• Register $0은 forwarding 하면 안된다. 
• Register write가 실행되는 명령어인지 확인(앞선 instruction이 register에 write하는 instruction인지 확인)
• Double data hazard가 발생하는지 확인

1. Default (No forwarding)

ForwardA = 00

 

2. EX hazard

if (EX/MEM.RegWrite and (EX/MEM.RegisterRd != 0) and (EX/MEM.RegisterRd = ID/EX.RegisterRs))

ForwardA = 10

 

3. MEM hazard

if (MEM/WB.RegWrite and (MEM/WB.RegisterRd != 0)

and not (EX/MEM.RegWrite and (EX/MEM.RegisterRd != 0)

and (EX/MEM.RegisterRd = ID/EX.RegisterRs))

and (MEM/WB.RegisterRd = ID/EX.RegisterRs))

ForwardA = 01

파이프라인 제어 개략도

> Load-Use Data Hazard

lw가 있는 경우에 bypass와 forwarding이 모두 안될 수 있다. 
해결책: Pipeline stall(Pipeline bubble)

stall(bubble); instruction이 pipeline stage에서 진행하지 않고 멈추는 것(CPI = 1을 포기)

# Bubble을 추가하는 방법

• Hazard가 있는 instruction을 ID stage에서 1 cycle stall
• IF/ID registser 및 PC의 변경을 막음 -> 근데 EX로 넘어감
• ID/EX register에 nop(stage change 없는 instruction) 삽입 -> 9개의 모든 control sig 모두 0

# Load-Use Hazard를 detect하는 방법

# Datapath with Hazard Detection

> Control Hazard; Branch Hazard

# Reducing Branch Delay

Branch execution이 이루어지는 pipeline stage

MEM stage에서 branch에 대한 next PC 값이 결정된다고 가정

-> branch execution을 ID stage로 이동시켜 Next PC 값의 결정을 더 빨리 함으로써 flush instruction 수를 감소

=> 즉, branch penalty가 1 clock cycle로 감소

 

• ID stage에서 branch decision (source끼리 comparison); ID stage에 comparator 추가
• ID stage에서 branch target address 계산; 계산을 위한 adder를 EX stage에서 ID stage로 이동

# Branch Prediction; branch의 결과값을 예측하고, 예측이 틀렸을 때만 stall(중단)한다. 

• Static branch prediction (정적 예측)
  • 후방분기는 분기가 항상 일어난다고 예측(taken); loop (아래에서 위로 되돌아간다)
  • 전방분기는 분기가 항상 일어나지 않는다고 예측(untaken -> default값); if (조건을 위에서 확인하고 아래로 내려온다) 
• Dynamic branch prediction
  • 분기 명령어의 분기 이력을 기록해두고, 분기 예측에 이를 사용하는 방식

# Dynamic Branch Prediction

Branch Prediction Buffer(branch history table)를 사용한다. 

 

1-bit predictor: Limitations; 바로 전의 결과만을 사용한다. 

2-bit predictor; 두번의 연속된 예측실패(misprediction)이 일어나야만 예측 기준의 결과를 바꾼다. 

> Calculating the Branch Target(address)

대상 주소를 계산해야 함; rs(PC+4) + address*4