파이프라이닝, 비순차적 실행, 분기 예측, 추측 실행

(주로 unmanaged 고급 언어-ex. C언어)명령어 한 줄은 그 과정을 자세히 뜯어보면 cpu를 통해서 총 4단계로 이루어진다.

바로 데이터를 "인출"하고 "해석"하고 "실행"하고 "저장"하는 과정으로 말이다.

그리고 이 "인출-해석-실행-저장" 4단계를 "cpu 명령어 사이클"이라고 한다.

(그리고 이 프로세스(단계)들 조차도 또 단계별로 나누어서 실행한다. 그리고 이 각각의 단계를 "스레드"라고 한다.

이러한 프로세스의 구조(아키텍처)는 cpu를 만드는 회사마다 다르며 아키텍처는 진화를 거듭하고 있다.)

https://www.youtube.com/watch?app=desktop&t=714&v=Fg00LN30Ezg&feature=youtu.be

---

 

 

파이프라이닝이란 고정된 크기의 여러 명령어들을 동일한 크기로 나누어, 겹쳐서 실행하여 최종적인 실행 시간을

줄이는 방법이다. 명령어 사이클이 4단계로 구성되어 있으므로 이해하기 편리하도록 각 프로세스가 실행되는 시간을

1초로 잡아서, 하나의 명령어 사이클이 실행되는 시간을 4초로 맞추었다.

 

예를 들어서 위와 같이 실행하는데 4초가 걸리는 명령어 3개가 실행시킨다고 가정해보자.

명령어 하나가 실행될 때까지 기다렸다가 다음 명령어를 실행한다면, 총 12초가 걸린다.

지금은 명령어가 3개 밖에 없어서 작아보일 수 있지만, 만약 명령어의 개수가 늘어나고 

실행하는 걸리는 시간이 늘어난다면 최종적인 시간은 기하급수적으로 커질 것이다.

 

파이프라이닝은 위와 같은 문제점을 해결하기 위한 것이다.

하나의 명령어를 실행하기 위한 내부적인 단계를 4개로 쪼개고, 그 한 부분을 실행하는데 1초씩 걸린다고 가정해보자.

그리고 똑같이 명령어 3개를 실행시키는데 4등분한 명령어 3개를 하나씩 엇갈리도록 겹쳐서 실행한다고 해보자.

그러면 명령어 하나가 실행되는 시간인 4초와 명령어의 개수가 한 개씩 추가될 때마다 1초가 늘어난다.

따라서 3개의 명령어를 실행시키는데 고작 6초밖에 걸리지 않았다. 아까와 비교하면 최종적인 시간이 반으로

줄어든 것이다.

 

그리고 이는 명령어의 개수가 많아지고 실행 시간이 길어진다면 엄청난 시간 단축을 일으킬 것이다.

이게 바로 파이프라이닝이고, 위와 같이 시간 단축을 목적으로한 기법이다.

 

파이프라이닝을 사용하지 않고 명령어를 하나씩 순차적으로 실행한 시간과 파이프라이닝을 사용하여

병렬로 처리한 시간을 공식으로 나타내면

파이프라이닝 X: 개당 소요 시간 x 명령어의 개수

파이프라이닝 O: 개당 소요 시간 + 명령어의 개수 - 1

이다.

 

파이프라이닝을 적용했을 때 몇 배로 빨라지는지 계산하고 싶다면

파이프라이닝 X / 파이프라이닝 O 를 해보면 알 수 있다.

예시에서는 2배 차이가 나는 것을 확인할 수 있다.

 

물론 모든 경우에서 파이프라이닝을 할 수 있는 것은 아니다.

대표적으로 CISC의 경우 명령어의 크기가 가변적(변하기 때문에)이기 때문에 위와 같이 명령어들을 등분하고,

하나씩 엇갈리도록 하고, 쭉 겹쳐서 실행할 수가 없다.

그리고 파이프라이닝의 성능을 저해하는 요소들이 있다.

그리고 이것들을 파이프라인 해저드(Pipeline Hazard)라고 한다.

파이프라인 해저드에도 종류가 있다.

 

하드웨어적으로 필요한 무언가를 지원하지 않아서 생기는 경우가 있는데,

예를 들어서 메모리에서 데이터를 두 번 접근하는 것이 있다. 물론 지원하는 cpu도 있지만 그렇지 않은 cpu도 있다.

이런 하드웨어적인 문제가 있는 경우를 "구조 해저드" 라고 부른다.

 

또 이전 명령어의 결과값을 이용해서 명령어를 처리해야하는 경우가 있다.

좀 더 자세히 설명하자면, 이전 명령어의 결과값이 필요한데, 이전 명령어가 아직 끝나지 않은 것이다. 그럼 바로 실행하지

못하고 기다려야한다. 즉 전에 있는 명령어의 결과값에 종속되는 경우이다! 

이처럼 어떤 명령어가 전에 있던 명령어의 결과값을 받아서 처리를 해야하는데, 아직 전에 있는 명령어가 끝나지 않은

경우를 "데이터 해저드" 라고 부른다.

 

만약 분기명령이 있다면 어떨까?

데이터를 인출하고, 해석해서 실행할 준비가 끝났는데 분기명령어(ex. goto)를 만나서 기존에 했던 일들이 쓸모없게

되어버린다면? 분기명령으로 인해 그동안의 것은 무로 돌려버리고 다시 명령어 사이클을 돌아야할 것이다. 

이러한 점으로 인해 발생하는 경우를 "제어 해저드" 라고 한다.

 

그리고 제어 해저드를 해결하기 위한 방법으로 "분기예측"이라는 것이 있다.

간단한 개념인데, 분기명령으로 인해 지연이 발생하는 이유는 분기명령이 있을 거라는 것을 예측하지 못하고

분기명령으로 인해 어처피 필요없어질 과정들을 수행하기 때문이다. 따라서 분기명령이 있을 거라는 걸 예측한다면

앞선 필요없어질 과정들을 수행하느라 시간을 들이지 않아도 된다.

분기명령을 예측하여, 무의미해질 과정들에 시간을 소비하지 않고 바로 분기명령을 실행하는 것을 분기예측이라고 한다.

 

 

 

 

데이터 해저드가 발생하는 이유는, 어떤 데이터를 처리해야 하는데 그 데이터가 앞선 명령의 결과값이고 아직 처리 중이기 때문이다. 이와 같이 '이전 명령의 결과값에 묶여있는 성질이다.'라고  해서, "종속성"이라고 부른다. 

그런데 여러 명령을 처리해야 하는데, 명령들이 종속성으로 인해 묶여있지 않다면 굳이 순차적으로 처리해야 할까?

cpu의 속력을 높이기 위해 연구하는 사람들이 내린 결론은 '아니오!' 이다. 그리고 이를 활용해서 cpu 속력을 높이는

기법이 바로 "비순차적 실행"이다.

 

비순차적 실행을 통해서 종속성이 없는 명령어들은 굳이 순서대로 처리하지 않고, 더 빠른 속력을 낼 수 있도록

비순차적으로 실행해서 최종적인 시간을 단축한다.

 

비순차적 실행을 하기 위해서는, '이 명령이 종속성이 있는가?'를 판단해야 한다. 다른 말로하면 병렬성을 찾는 것이다.

'명령어 수준에서 병렬성'이라고 해서 영어로 ILP (Instruction Level Parallelism)라고 한다.

하지만 명령어를 하나하나 ILP를 검사한다면 비용(시간 등)이 너무 많이 소비된다. 그래서 명령어 윈도우라는 개념이

필요하다. 명령어 스트림 속에서 일정한 범위만큼 ILP를 수행하는 것이다. ILP가 완료되면 새로운 명령어가 

명령어 윈도우에 들어오는데 이때 가장 오래된 명령어가 빠져나간다.

(예를 들어서 4개의 명령어가 모두 종속성으로 묶여있다면, 명령어 하나 실행시키고 다음 하나 실행시키고...

계속 이렇게 해서 총 4번, 즉 4cycle에 실행할 수 있고, 4개 명령어 / 4cycle를 하면 1 이므로, 이때의 ILP는 1이라고 말할 수 있다. 다시말해 병렬로 처리할 수 없다는 뜻이다. 만약 4개의 명령어가 있고 그 중에서 2개씩 서로 다른 종속성으로

엮여있다면, 서로 다른 종속성을 가진 명령어 2개를 한 번에 실행시키고(=1cycle에 실행) 각각의 종속성을 가진

명령어 2개를 다음으로 실행시킨다면(=2cycle때 실행) 2cycle에 명령어 4개를 처리할 수 있다.

즉 이때의 ILP는 2라고 말할 수 있고, 4개의 명령어들을 2병렬로 처리할 수 있다는 말이다.

그리고 이와 같이(스레드가) 서로 독립적인 관계라면 동시에 실행된다.

+같은 종속성 있는 것들끼리 몇 개로 묶을 수 있냐라고 생각하면 쉽다.)

 

 

명령어 윈도우에서는 하는 일은 가짜 의존성 제거(Register Renaming)와 동적 명령어 스케줄링(Reservation Station),

그리고 순차적 완료(Reorder Buffer)이다.

 

가짜 의존성이란 코드(즉 명령)에 사용된 레지스터를 보면 의존성이 없는 경우를 말한다. (의미를 따져봤을 때 종속성이 X)

즉 가짜 의존성을 확인하는 과정에서 이가 발견되면 병렬로 처리하기 위해 사용하지 않는 다른 레지스터로

변경하는(즉 이름을 바꾸는) 과정을 가짜 의존성 제거, Register Renaming이라고 한다.

 

Reservation Station이란 연산의 대상이 되는 데이터, 즉 피연산자(operand)가 준비되기를 기다리기 위해 명령어를

임시로 저장하는 큐(자료구조-Queue)이다.

Reservation Station에서 기다리는 어떤 연산이 준비가 끝난 피연산자를 필요로 하는지 찾는 것을 wake-up 작업 이고

피연산자가 준비되어서 실행 가능한 명령어들의 개수가 사용 가능한 실행 장치의 개수보다 많다면, 효과적을 처리할 수 

있도록 뭐부터 할당할지 순서를 정하는 것(스케줄링)이 select 작업이다. 비순차적일 수도 순차적일 수도 있다.

즉, wake-up 작업과 select 작업을 함으로써 피연사자를 효율적으로 명령어들에 할당하기 위해 스케줄링 하는 작업이다.

 

명령어의 실행까지는 비순차적일 수도, 순차적일 수도 있다. 하지만 마지막에는 프로그래머가 요구했던 순서대로 

결과를 보여주는 과정이 필요하다. 이때 사용되는게 Reorder Buffer이다. 실행이 끝난 것들(결과값)을

원래 프로그램 순서대로 차례차례 쌓아두었다가 총 결과를 레지스터 등에 commit(저장, 할당받은 자원 반환)하는 것이다.

 

 

추측 실행은 상대적으로 간단한 개념이다.

마찬가지로 속력을 높이기 위해서 다음에 실행될 명령어를 미리 실행해 놓는 기법을 말한다.

(분기 예측이 이에 포함된다.)

 

예를 들어서

if (a > 1)
	b = 2;

이런 코드가 있다고 가정했을 때,

a > 1을 판단하기 위해서는 a를 불러와야 하므로, 이때 읽어오는 시간이 걸린다. 그래서 미리 b = 2를 실행해 두고,

후에 a > 1의 결과값에 따라서(예측이 맞냐, 틀리냐에 따라서) 처리하는 것이다.