[컴퓨터 구조][Out of order]

[컴퓨터 구조][Parallel]

 

 

 

 

 

지난 포스팅을 보시면, Parallel에 대해서 알아보며 ILP, DLP, TLP에 대해서 알아봤었습니다.

 

결국에는 "병렬로 수행해서 성능을 향상시키기 위해서라는 것"이라는 공통의 목표로 병렬성을 증가시킨 것 입니다.

 

 

지난 시간에 ILP에 대해서 배우며 그 예시로, 기존에 배웠던 것에서는 Pipelining과 Branch predictor, Hazard detector등을 이용하면 CPI가 줄일 수 있기 때문에 전체적인 CPU time을 줄일 수 있다고 했었습니다. 결국 수행능력이 올라가는 거죠.

 

 

$\text{CPU Time =} \frac{Instruction}{Program} \; * \; \frac{Cycle}{Instruction} \; * \; \frac{Time}{Cycle}$

 

 

결국에는 위의 CPU time을 줄일 수 있는 방법이 있다면 수행능력이 올라가게 되는 것인데,

하드웨어 관점에서 하드웨어 생산과정말고, 저희가 올릴 수 있는 부분은 CPI입니다.

그래서 저희가 어떻게 해서는 CPI를 줄이기 위해서 Pipelining도 하고,

Parallelism을 통해서 CPI를 줄이고자 노력하는 것 입니다. 

 

 

지금까지 저희가 minimize시켜서 성능을 최적화 시켰던 항목을 보자면

 

 

· Minimize clock cycle 

  pipelining의 stage를 늘린다.

 

· Minimize CPI

  pipelining 활용

 

· Minimize IC(Instruction Count)

  프로그램이 실행하는 총 명령어의 개수를 줄여서 성능 향상

 

 

위와 같은데, 여기서 pipelining의 단계를 계속해서 늘린다면 성능이 계속해서 좋아질까요?

 

일부 관점에서는 성능이 안좋아질 수도 있습니다. 그 이유는 control hazard와 data hazard가

더 빈번하게 발생해서 성능이 오히려 안좋아질 수도 있기 때문입니다.

 

'CPI = 1'일 수 있을 때는 Hazard가 발생하지 않았을때 만족할 수 있습니다.

 

 

여기서 그렇다면 Pipelining은 계속해서 늘리는 것은 오히려 좋지 않으니까 다른 방법을 찾게됩니다.

ILP를 증가시키는 방법인 Superscalar를 사용하는 것인데, Superscalar를 통해서 IPC > 1 를 만들기 위해서

Pipelining 전체를 다 Superscalar를 활용할 수 있도록 변경해줘야 합니다. 만약에 Execution단계에서만 적용한다면

다른 곳에서는 어차피 하나의 명령어만 처리할 수 밖에 없기 때문에 병목현상이 발생하게 됩니다.

 

 

이제 IPC를 1보다 크게 하기 위해서 Superscalar를 적용했으니까 문제가 없을거라고 생각할 수 있지만,

여전히 여기에서도 명령어의 의존성때문에 문제가 발생하기 때문에 문제가 될 수도 있습니다.

Pipelining을 더 나눠도 문제가 생기고, 해결하려고 ILP의 Superscalar를 통해서도

명령어 간의 의존성 문제가 발생하기 때문에 이를 해결해주기 위해서 Out of order를 사용하게 되는 것입니다.

 

 

Out of order를 이용하게 되면, instruction을 "실행 가능한 명령어를 먼저 찾아서 실행"함으로써

수행하기 때문에 명령어간의 의존성을 해결할 수 있게 됩니다.

 

 

아직 위의 말로는 쉽게 이해가 가지 않으니까 아래에서 세 가지 경우를 살펴보면서 이해해보겠습니다.

 

 

 

우선, 의존성에서 True dependency와 false dependency가 존재합니다.

 

 

 

 

 

 

 

True dependency

 

 

 

 

 

True dependency는 RaW(Read afrter write)로 실제로 위 아래 명령어가 의존성을 가질 때 입니다.

 

 

$\text{(7) r5} \; \leftarrow \; MEM[r2]$

$\text{(9) r6} \; \leftarrow \; r4+r5$

 

두 명령어를 보면, 실제로 두 명령어 사이에는 의존성이 존재합니다.

(7)명령어가 실행이 다 된 이후에 (9)명령어가 실행되어야 hazard가 발생하지 않습니다.

즉, r2에 해당하는 메모리의 데이터를 r5에 써주고 난 이후에 r5의 값을 가지고 덧셈을 수행해야 하기 때문에

실제로 레지스터 r5에 대한 데이터의 값이 의존성을 가지고 있습니다.

 

 

 

 

 

 

 

False dependency

 

 

 

 

 

여기에는 두 가지 False dependency가 존재합니다. Anti dependency와 Output dependency입니다.

 

 

 

 

Anti dependence ( WaR(Write after Read) )

 

 

 

이전 명령어가 읽기 작업을 수행하고, 다음 명령어가 쓰기 작업을 수행할 때 발생합니다.

레지스터의 이름이 동일하기 때문에 의존성이 있는 것 처럼 보이지만 실제로는 아닙니다.

 

 

$\text{LDUR X2, [X3, #0]}$

$\text{ADD X3, X4, X5}$

 

위의 두 명령어를 보면, 메모리에서 읽어오고 난 이후에 ADD를 명령어를 실행하게 되는데,

X3 레지스터의 충돌로 인해 의존성이 있는 것처럼 보이지만, 실제로는 데이터 간의 종속성은 없습니다.

 

왜냐하면 실제로 LDUR은 데이터를 읽어오는 것이고, ADD는 그 이후에 실행되는 것이기 때문에 문제가 없습니다.

 

 

 

 

 

 

Output Dependence( WaW(Write after Write) )

 

 

 

두 개의 명령어가 같은 레지스터에 값을 쓸 때 발생하게 됩니다.

먼저 실행된 명령어의 결과가 나중에 실행된 명령어의 결과로 덮어씌워질 수 있기 때문입니다.

 

$\text{MUL X1, X2, X3}$

$\text{ADD X1, X4, X5}$

 

MUL에 의한 결과가 X1 레지스터에 들어가고, ADD가 실행되면 X1 이전 MUL의 결과값이 덮어씌어지게 됩니다.

이 경우에도 데이터의 의존성은 없지만 레지스터의 이름 때문에 의존성이 있는 것 처럼 보이기 때문에

충돌이 발생하고 병렬 실행을 할 수 없게 되는 문제가 발생하게 됩니다.

 

 

 

 

결론적으로 False dependency는 레지스터의 이름으로 인해서 발생하기 때문에

Register Renaming으로 해결할 수 있게 됩니다.

 

Reorder와 같이 compiler를 통해서 명령어의 순서를 바꾸고 hazard를 없애주는 것을

Data forwarding이 있는 포스팅에서 확인해본적이 있는데, out of order는 같다고 할 수 없지만

일종에 reorder와 같다고 생각하시면 될 것 같습니다. 실행 가능한 명령어를 먼저 수행해서

수행 능력을 향상시키는 방법이기 때문입니다.

 

 

 

 

 

지금까지 Out of order를 사용하는 이유와 기본적인 배경을 살펴봤습니다.

 

위의 내용을 조금 간략하게 정리해보자면,

 

수행능력을 올리기 위해서 ILP를 증가시키는 Pipelining을 할 수는 있지만

파이프라이닝만으로는 아무리 쪼개서 파이프라이닝을 하더라도 hazard가 존재해서 CPI가 1보다 작아질 수 없다.

왜냐하면 파이프라이닝을 한 상태에서 hazard가 아예 없는 경우에만 CPI는 1이 될 수 있기 때문이다.

 

그래서 또 다른 방법이 없을까? 명령어를 병렬로 수행해보자. 그러면 수행능력이 올라간다.

ILP의 Superscalar를 사용해보자. 하지만 Superscalar로 수행하게 된다면 데이터에 대한 의존성 문제가 더 발생한다.

왜냐하면 명령어를 병렬로 수행하게 된다면 하나씩 수행하더라도 생기는 instruction에 대한 hazard가 발생하는데

더 많은 hazard가 발생하게 된다. 그렇다면 이 부분을 어떻게 해결할 수 있을까?

 

명령어를 수행가능한 순서(의존성 없는)대로 compile하는 과정에서 스케쥴링한 다음에 수행하면 되지 않을까?

스케쥴링을 하려다보니까 hazard가 발생하는 부분이 생기는데, 실제로는 데이터간의 의존성이 없는데

레지스터 이름 때문에 의존성이 있어 보이는 False dependency가 존재하고,

실제로 데이터간의 의존성이 있어서 발생하는 True dependency가 존재한다.

 

False dependency는 우리가 out of order과정에서 Renaming을 통해서 해결할 수 있다.

하지만 True dependency같은 경우에는 out of order으로는 해결할 수 없지만,

Data forwarding같은 방법이나 Out of order의 하드웨어를 이용해서 순서를 조정하거나

Speculative Execution(추론 실행)으로 True dependency에 대한 성능 저하를 최소화 할 수 있다.

 

이렇게 간략화해서 흐름을 정리해보면 이해가 쉽습니다.

 

 

 

---

 

 

 

 

지금까지는 Out of order의 기본적인 배경에 대해서 살펴봤습니다.

이제 다음 시간에는 Out of order의 Renaming에 대한 하드웨어 구조와 실행 과정을 살펴보고

Speculative Execution이나 순서를 조정하는 부분을 추가적으로 살펴보겠습니다.

 

 

감사합니다.