걸어가기

1. Basics of Pipelining

* Introduction:

- 파이프라인을 사용하여 CPU 성능을 높일 수 있음

- 여러 개의 instruction이 동시에 실행된다

- 파이프라인의 성능은 'speedup'으로 잰다

* 

- 파이프라인은 하나의 task의 latency 개선에 도움을 주지는 않지만, 전체 workload의 처리량 개선에 도움이 된다.

- 각각 다른 자원을 사용하는 task들이 동시에 여러 개 실행되는 거

- potential speedup = number of pipe stages

- unbalanced length of pipe stages reduces speedup

- time to fill pipeline and time to drain it reduces speedup

- stall for dependences

* Speedup

파이프라인에 k개의 stage가 있으면 n이 무한대로 갈 때 스피드업은 k가 된다.

* Basic Steps of Execution

1. Instruction fetch step (IF)

2. Instruction decode/ register fetch step (ID)

3. Execution/ effective address step (EX)

4. Memory access (MEM)

5. Register write-back step (WB)

* Summary

- multi-clock cycle datapath에서 처럼 인스트럭션을 여러 개의 스텝으로 나눈다.

- 같은 시간에 datapath에 있는 각각의 unit은 각각 다른 step을 실행한다.

- 스피드업은 가장 긴 파이프 stage와 파이프 stage 개수에 영향을 받는다.

2. Hazards

Hazard: The situation when the next instruction cannot execute in the following clock cycle.

하자드: 다음 인스트럭션이 바로 이어지는 클락 싸이클에서 실행되지 못하는 상황

모든 하자드는 기다림으로써 해결될 수 있다.

※ 하자드의 종류:

1) Structural Hazard

: Hardware cannot support combination of instruction (Not enough HW)

ex) the instruction and data should be fetched from the memory at the same time

* Solution

Resource Duplication (아래는 그 예)

- Separate instruction and data caches for memory access conflict

- Time-multiplexed or multi-port register file for register file access conflict

2) Data Hazard

: An instruction depends on the results of a previous instruction still in pipeline

* Solution

- Freezing the pipeline (stall)

- (Internal) Forwarding (계산 결과를 중간에 보내버리기)

- Compiler Scheduling

위의 두 개는 하드웨어적인 솔루션, 아래 하나는 NOT 하드웨어적인 솔루션

3) Control Hazard

: Control may transferred to another instruction based on the results of an instruction (ex. beq, bne)

* Solution

- Stall

- Optimized branch processing

1) Find out branch taken or not early

2) Compute branch target address early

- Reducing Delay by moving Branch execution to the ID stage (그럼 지울 instruction이 두 개가 아니라 하나가 된다, branch address calculation을 옮길 수도 있고 branch test를 옮길 수도 있다.)

- Branch prediction

1) Static: branch가 절대 일어나지 않거나, 언제나 일어나거나, op-code에 따라 다르다고 항상 예상한다.

2) Dynamic: Branch Prediction Buffer나 Branch History Table을 사용한다. 

- Delayed branch

- Delayed Branch always executes the next sequential instruction, with branch taking place after that one instruction delay

- Compiler or Assembler automatically insert the branch delay slot with instruction that is not affected by the branch