[Programming] Instruction Level Parallelism(ILP), Pipelining

Instruction Level Parallelism(ILP), Pipelining

---

포스트 난이도: HOO_Junior

[Notice] 포스트 난이도에 대한 설명

---

 

# Pipelining

ILP(Instruction Level Parallelism)은 명령 Sequence를 병렬 처리하는 방식을 의미한다.

명령을 병렬처리 한다는 것은 특정 명령이 실행되는 도중에 새로운 명령이 실행 준비를 한다거나 동시 실행이 가능한 걸 말한다.

이러한 기능을 Insturciton pipelining 또는 Pipelining이라고 한다.

Pipelining이라는 단어의 의미를 생각해보면 연속적으로 연결되어 있는 파이프라인이 연상된다.

이와 마찬가지로 Instruction pipelining이라는 것은 processing unit 또는 system을 multiple stages로 나누어서 명령어를 병렬 처리하는 방식을 나타낸다.

이를 통해 특정 명령들이 연속적으로 Processing 될 수 있는데 이것이 마치 파이프라인과 비슷하다.

ILP 또는 Pipelining 방식을 컴퓨터에서 사용하는 이유는 Hardware의 성능과 별개로 Processing 효율성을 높일 수 있는 또 다른 방법이기 때문이다.

---

# Pipeline 계산 공식

Pipeline에 대한 Examples들을 보기 전에 미리 알고 있으면 편한 공식을 살펴보도록 하자.

Pipeline에 대해서는 기본적으로 각 stage에 대한 pipline process를 알아야 하며, 이에 따른 Speed up에 대한 부분도 산출해낼  줄 알아야 한다.

문제를 보고 계산해낼 수도 있지만 다음 공식을 알고 있으면 쉽게 파악할 수 있다.

How many ns will the N operations take the K stage pipeline to process?
a * (K + N - 1) / K

Speed up
K * N / (K + N - 1)

---

# Pipelining Examples

IF	ID	OF	EX	WB
1
2	1
3	2	1
4	3	2	1
5	4	3	2	1
6	5	4	3	2
7	6	5	4	3
...	...	...	...	...
				K

위와 같은 Pipelining example이 있다고 가정해보자.

IF는 Instruction fetching, ID는 Instruction decoding, OF는 Operand fetching, EX는 Execution, WB는 Write back을 의미한다.

이때 아래와 같은 조건이 있을때 Speed up을 산출해보자.

1000 operations
1000 operands
5 sub-ops
1 Cycle

이 경우 Cycle 한번만 돌기 때문에 5*1 = 5이 최종 Cycle 수가 된다.

따라서 5번의 Cycle 동안 하나의 명령 Process가 나온다는 걸 알 수 있다.

5 = a(1) + b

6 = a(2) + b

이런 식의 계산식을 도출해낼 수 있다.

Linear 계산식을 계산해보면 a와 b에 대한 값을 산출할 수 있다.

그래서 y = 1x + 4라는 식을 이 문제에서 찾아낼 수 있다.

최종적으로 1000번의 작업을 수행해야 하기 때문에 x값에 1000을 대입할 경우 y = 1000 + 4 = 1004라는 y 값을 얻을 수 있다.

결과적으로 1000 * 5 / 1004는 대략 5의 결과를 산출해낼 수 있다.

한마디로 5배와 가까운 Speed up이 발생한다는 것이다.

이 과정이 전체 Pipenlining을 보여주지만 간단하게는 위의 공식을 대입하면 결과를 바로 산출해낼 수 있다.

또한 Cycle이 2일 경우에는 최종 Cycle 10이 되고 2008의 과정을 거쳐서 최종 작업이 수행된다는 걸 알 수 있다.

그럼에도 불구하고 결과는 대략 5배의 Speed up이라는 비슷한 값을 산출해낼 수 있다.

---