Computer Architecture - Pipeline

processor는 여러 종류가 존재한다.

1. Single cycle processor

2. Multi cycle processor

3. Pipeline processor

 

각 종류별 장단점을 확인해 보자

종류	Single cycle processor	Multi Cycle Processor	Pipeline Processor
장점	1. 하드웨어 설계가 간편하고, 구성이 간단함	1. Clock Cycle Time이 짧아진다. 2. functional unit(e.g. ALU)을 한 명령어에서 여러번 사용 가능하다. 3. 단순 명령에는 더 빠르게 동작할 수 있다. 4. Processor 구성에 더 적은 하드웨어를 사용한다.	1. 한 명령어의 IF(instruction fetch)가 끝나면 바로 다음 명령어를 IF 하므로 각각의 FU(Functional Unit)들을 독립적으로 사용하여 하드웨어 활용률을 높인다. 2. 그로인해 성능이 향상되고 Ideal Pipeline의 경우 CPI가 1로 수렴
단점	1. 가장 느린 명령어에 의해 Clock Cycle Time이 결정된다. 2. 모든 명령어의 CPI가 1이다. 즉 일찍 끝나는 명령어의 경우 HW 활용도가 떨어진다.	1. 추가적인 register를 사용해야 한다. 2. control signal이 많아진다.	1. 명령어들을 구분해주기 위해 추가적인 register가 필요하다. 2. Hazard가 발생하기 때문에 이를 처리해줘야 한다.

 

 

 

Pipeline Processor에 대해 더 알아보면

-Pipelined Processing: 현재 작업 set 중 첫 번째 작업이 끝나면 새로운 작업이 시작될 수 있음

 

Pipeline Processor 예시

 

즉 Pipelining이란,  여러 명령어가 겹쳐서 수행되는 프로세서를 구현한 것이다.

 

- Advantages

• FU 사용률 증가
• 성능 향상

- Disadvantages

• 하드웨어 추가 필요(register)
• Hazard 발생

---

Hazard

---

 

Hazard에는 총 3가지가 있다

1. Structural hazard:  두개 이상의 명령어가 같은 리소스(FU or Memory)를 사용하는 경우

2. Data hazard: 어떤 명령어가 현재 Pipeline 안에서 수행 중인 다른 명령어의 결과에 의존하는 경우

3. control hazard: 명령어의 실행 결과에 따라 PC 값이 변경되는 경우(e.g. branch)

 

 

Structural Hazard

- resource 충돌로 인해 서로 다른 명령어가 동시에 수행되지 못할 수 있음

- 일부 FU이 완전히 Pipeline 되지 않았을 때(=각 stage에서 독립적으로 사용되지 않았을 경우) 발생

 

Structural Hazard 발생 예시

 

Structural Hazard Solution

1. 모든 명령어 조합을 동시에 수행할 수 있도록 FU를 더 복잡하게 만드는 것

• E.g. 동시에 두 개 write 작업을 수행할 수 있도록 register file을 수정함
• 하지만 핀이 추가되고 하드웨어가 복잡해지며 비싸진다는 문제가 발생함

2. FU가 사용 가능해질 때까지 명령어 실행을 지연시키기

• Processor에서 명령어 실행을 지연시키기 위한 pipline stall 혹은 bubble을 삽입해서 해결

 

---

Data Hazard

- Pipeline에 의해서 Read / Wirte의 순서가 바뀌게 됐을 때, 그로 인해 프로그램에서 중요한 Data의 context가 바뀔 때 발생하는 Hazard이다.

- 서로 다른 Data Dependency가 그 원인이다.

 

 

이러한 Data Dependency Types 에는 

RAW, WAW, WAR, RAR 4가지가 있지만  

- 대부분의 경우 RAW(Read After Write)를 Data Hazard라고 말하고 있고

 

- WAW(Write After Wirte)의 경우는 Structural Hazard 때문에 WB를 동시에 하지 않으므로 발생할 일이 없기 때문에 Hazard로 취급하지 않으며

 

- WAR(Write After Read)의 경우에는 값을 읽는 것은 ID/IF 에서, 쓰는 것은 WB에서만 발생하므로 Dependency가 발생하지 않는다( ID가 WB보다 훨씬 먼저 하기 때문에 먼저 일어날 일이 없음)

 

-RAR(Read After Read)의 경우는 문제가 없기 때문에 상관없다.

 

 

Data Hazard Solutions

1. Stall

- Data가 준비될 때까지 다음 명령어를 지연

 

2. Change Clock Cycle

- Reg.file에 쓰는 것을 clock cycle의 first half cycle에 읽는 것을 second half cycle에 수행

 

3. Forward or Bypassing

- 값이 Reg.file에 써지는 것은 WB stage이지만, 해당 값은 EX stage에 이미 준비되어 있음

- 준비된 data를 WB stage까지 기다리지 않고, 미리 전달해 줌

 

4. Restrict Software

- complier가 Data hazard가 발생하지 않도록 아무런 작업을 수행하지 않는 nop 명령어를 추가하거나 Data Hazard가 발생하지 않도록 명령어 실행 순서를 다르게 할 수 있음

 

 

Change Clock cycle과 Forwarding 방법을 사용해 모든 Data Hazard를 해결한다면 좋겠지만 그럴 수 없기 때문에 그런 경우 어쩔 수 없이 Stall을 사용해야 한다.

 

Forwarding을 사용했을 때 예시

---

Control Hazard

- 주로 Branch (e.g. beq, bne) 명령어에 의해 발생함

 

- 만약 Branch가 안된다면 (= Branch is not taken), control은 PC + 4로 자연스럽게 진행하면 된다.

 

- 하지만 Branch가 된다면 (= Branch is taken), Control은 새로운 PC 주소로 변해야만 함

   → 문제는, Branch가 taken 여부를 3단계 (EX)에서 알 수 있기 때문에 문제가 발생함

 

 

Control Hazard Solution

1. Stall

- Branch 명령어가 있을 때, 새로운 명령어가 시작되는 것을 막음 → 기존에 실행되던 명령어들은 계속 실행함

 

2. Branch Prediction(분기예측)

- 결과를 미리 예측하고, 예측 결과로 수행(e.g. 저번에 taken이었으니 이번에도 taken 일거야) 만약 예측이 틀리면, 원상복구

 

3. Delayed decision(결정 지연)

- Branch 명령어 예후에 control과 상관없는 것들을 먼저 수행하도록 함

 

---

Advanced Pipelining

---

ILP(Instruction Level Parallelism)라고 부르는 명령어들 사이의 병렬성을 활용하는 것에 Pipeline이 있다.

 

이런 Pipeline의 Limitations에는

1. 겹쳐서 수행되는 명령어를 다루기 위한 FU가 필요하다

2. HW수준에서 병렬적으로 수행 가능한/수행할 수 없는 명령어를 탐지하는 능력이 필요하다.

3. 명령어 병렬화를 위한 컴파일러 기술이 필요하다.

 

Superpipelining

- 기존 pipeline에서 stage를 더 쪼갠 pipeline이다, 일반적으로 12 - 13 stage로 쪼개져 있다.

- stage를 더 많이 쪼갬으로써 Clock frequency를 높여 성능을 높일 수 있다.

- 하지만 stage를 더 잘게 나누기 때문에 register가 더 많이 필요하다.

- 더 복잡한 Hazard issue가 발생할 수 있다.

 

Superpipelining

 

Super-Scalar

- 한 사이클에 여러 개의 명령어를 수행하는 pipeline이다.

- N-way pipeline이라면 이상적일 경우 1 Cycle에 N개의 명령어를 처리한다.

- Superpipelining과 마찬가지로 더 많은 Hazard가 발생할 것이기 때문에 Hazard 방지 회로가 필요하다.

 

Super-Scalar

---

Dynamic Scheduling

- 지금까지 다룬 것들은 in-order execution (순차 실행) 구조를 사용하여 stall 발생 시 모든 instruction이 stall 되는 구조

- Out-of-Order Execution(비순차 실행)은 순서에 상관없이 끝낼 수 있다. (stall 할 필요 없는 instruction 먼저 실행)

※ Out-of-Order Execution을 OoO, O3라고도 함