Layer7 과제 - 하드웨어 2차시(파이프라이닝, 분기 예측, 비순차적 실행, 추측 실행)

목차

---

1. 파이프라이닝 ( pipelining )

2. 분기 예측 ( branch prediction )

3. 비순차적 실행 ( out-of-order execution )

4. 추측 실행 ( specultion execution )

---

1. 파이프라이닝 (pipelining)

---

명령어가 한 번에 하나만 실행된다고 하면 꽤나 비효율적인 프로세서가 될 것이다.
음식을 예를 들어 설명해보자.
우리는 다음의 3가지 동작으로 계란 3개를 모두 구워야 한다.
1. 계란을 프라이팬 위에 올린다.
2. 인덕션을 작동시킨다.
3. 계란을 접시 위에 올린다.

클럭 주기	1	2	3	4	5	6	7	8	9
계란 1	과정 1	과정 2	과정 3
계란 2				과정 1	과정 2	과정 3
계란 3							과정 1	과정 2	과정 3

이렇게 순차적으로 명령어를 실행하게 되면 총 9개의 클럭이 필요하지만, 파이프라이닝이라는 기법을 적용하면 상당한 시간을 줄일 수 있다.
서로 다른 과정을 한 번에 처리하는 방식인데, 말로만 설명하면 이해하기 힘들 것 같으니 표를 통해 설명해보자.

클럭 주기	1	2	3	4	5	6	7	8	9
계란 1	과정 1	과정 2	과정 3
계란 2		과정 1	과정 2	과정 3
계란 3			과정 1	과정 2	과정 3

이런 식으로 서로 다른 명령어를 동시에 처리해 처리 속도를 크게 향상시킨다.
(저 위 표에서도 확인할 수 있겠지만, 거의 절반의 시간이 줄어들었다.)

· 파이프라이닝 기법을 적용했을 때 걸리는 전체 주기

∴ T = k + ( n - 1 )
k = 마지막 개체가 첫 번째 명령어를 실행하는 데 걸리는 주기
n = 명령어 개수

ex) 3 + ( 3 - 1 ) = 5 -> 모든 개체가 명령어를 실행시키는 데 5주기면 충분함 (원래는 9주기)

· 파이프라이닝 기법을 적용했을 때 얻을 수 있는 속도 향상 비율

Sp = ( k * n ) / { k + ( n - 1 ) }
k = 첫 번째 명렁어를 실행하는 데 걸리는 주기
n = 명렁어 개수
식의 의미 : 모든 명령어를 순차적으로 실행했을 때 걸리는 시간을 파이프라이닝을 이용해 명렁어를 실행했을 때 걸리는 시간으로 나눔

ex) ( 3 * 3 ) / { 3 + ( 3 - 1 ) } = 9 / 5 = 1.8 -> 파이프라이닝을 적용했을 때, 적용을 하지 않았을 때보다 속도가 1.8배 빠름

---

여기서 잠깐! 해저드가 뭐야?

---

파이프라인 기법을 통해 명렁어를 실행하던 중, 처리 시간의 차이와 처리 단계의 불균등으로 인해 속도가 느려지는 현상이 발생하기도 하는데, 이를 해저드(Hazard : 위험)라고 한다.

1. 구조적 해저드

· 명령어 실행 시간의 불일치로 발생한다.

클럭 주기	1	2	3	4	5	6	7	8	9
계란 1	과정 1	과정 2	과정 3
계란 2		과정 1	과정 2 (1)	과정 2 (2)	과정 3
계란 3			과정 1	멈춤(stall)	과정 2	과정 3

계란 2가 구워지고 있는 도중, 명령어 실행 시간이 너무 길어 계란 3과 과정이 겹쳤다.
이럴 경우, 잠시 멈췄다가 그 명령어를 실행하게 된다.

클럭 주기	1	2	3	4	5	6	7	8	9
계란 1	과정 1	과정 2	과정 3
계란 2		과정 1	과정 2	과정 3
계란 3			과정 1	멈춤(stall)	과정 3

만일 어떤 개체만 특정 명령어를 실행하지 않아도 될 때, 그 명령어가 빌 때까지 기다렸다가 그 명령어를 실행하게 된다.

2. 데이터 해저드

· 이전에 실행한 명령어의 결과를 다음 명령어가 이용할 때 주기가 지연되어 생기는 해저드이다.

클럭 주기	1	2	3	4	5	6	7	8	9
계란 1	과정 1	과정 2	과정 3
계란 2		과정 1	과정 2	과정 3
계란 3			과정 1	멈춤(stall)	과정 2	과정 3

계란 3의 과정 2가 계란 2의 과정 3의 결과를 이용한다고 가정했을 때, 계란 2의 과정 3가 실행될 때까지 멈췄다가 실행한다.

3. 제어 해저드

· 명령어의 실행 순서를 변경하는 jmp, jle 등의 분기 명령어들이 사용되고, 다른 명령어들이 한 명령어의 결과 값을 이용해 결정을 해야할 때 발생한다.

---

이런 파이프라인의 효율은 제어 해저드에서도 봤듯이 브랜치나 서브루틴 콜이 많아질수록 떨이지는데, 최신 아키텍처에서는 분기 예측 기법 등을 통해 이런 문제를 회피한다.

 

---

2. 분기 예측 ( branch prediction )

---

앞에서도 봤듯이 파이프라이닝이 등장하면서 CPU는 수행이 채 끝나지도 않은 명령어의 실행 결과를 사용해야 하는 일이 있게 되었는데, 이것이 분기 명령어와 겹치면서 제어 해저드라는 것이 발생하게 되었다.
분기 예측이 나오기 전까지는 실행 결과를 사용할 명령어가 끝날 때까지 기다릴 수 밖에 없었는데, 이를 해결하기 위해 필요한 값을 기다리지 않고 어떻게 분기할지 예측해 파이프라인이 끊기지 않고 계속 수행되도록 하는 기법들이 나오게 되었고, 이것이 분기 예측이다.

그러나 이런 예측만으로는 실행결과를 100% 신뢰할 수 없기 때문에, 나중에 조건을 평가할 수 있을 때 앞에서 내린 예측이 틀렸다면 예측 수행 명령어들을 취소하고 올바른 분기 명령어를 다시 수행한다.

참고로 이렇게 높은 정확도를 가진 예측이 가능한 것은 프로그램 안에 있는 각 분기 명령어가 대부분 분기되거나 분기되지 않거나 둘 중 한 쪽 경우를 훨씬 많이 이용하는 경향이 있기 때문이다.
ex) while문을 생각해보면, 루프를 계속 도는 경우가 루프를 벗어나는 경우보다 훨씬 많으므로, '분기되다'로 예측하는 것이 정확도가 훨씬 높을 것이다.

---

종류

---

1. 분기 방향 예측

    · 1 정적 분기방향 예측
        정해진 규칙에 따라 실행 전에 분기를 지정해준다.
        ex) 모든 분기문을 분기하게 하는 Always taken 기법, 뒤로 가는 분기문은 분기하고, 앞으로 가는 분기문은 분기하지 
              않게 하는 Before taken, forward not taken (BTFNT) 기법

* BTFNT 기법 : 루프의 수행 방식에서 착상한 것으로, 루프에서는 계속 루프를 수행하는 경우가 더 많은데, 이는 이전 코드로 돌아가는 역방향 분기이므로 분기를 타는 경우로 예측하고, break 문과 같이 루프를 벗어나 다음 흐름을 실행하는 순방향 분기는 루프를 도는 와중에는 잘 일어나지 않으므로 분기를 타지 않는 경우로 예측한다.

    · 2. 동적 분기방향 예측

        정적 분기방향 예측과 달리 실행 중 정보를 활용해 분기 예측을 수행한다.
        정적 예측보다 정확도가 훨씬 높다.

        · 1. 분기 예측 버퍼
            각 분기 명령어마다 지난번에 그 분기가 실행됐는지 여부를 저장해 그 여부를 따라가는 기법이다. 보통 분기 명령어는 분기하는 경우와 아닌 경우 둘 중에 하나를 더 많이 이용하는 경향이 있으므로, 이번 경우엔 지난번에 수행된 결과와 같을 것이다라는 추측을 통해 예측을 행한다. 따라서 지난번에 분기했냐, 안 했냐 둘만 저장하면 되므로 버퍼에 1비트만 사용해 예측이 가능하다.

           분기 예측 버퍼의 문제점으로는 분기 예측이 한 번 틀렸을 때, 다음 분기 예측에도 틀릴 가능성이 있다는 것이다. 이를 해결하기 위해 버퍼당 버퍼당 2비트를 사용하여 두 번 연속으로 틀렸을 때만 예측을 바꾸게 하면 더 좋은 성능을 낼 수 있다.

        · 2. 연관 분기 예측

            연관 분기 예측은 앞의 분기 예측 버퍼와 달리 다른 분기 명령어의 수행 결과까지 반영해 분기 여부를 결정한다.

            ex) if else 구조의 경우, if에서 분기하면 else에선 분기하지 않는다는 특성이 있는데 분기 예측 버퍼에서는 전에 분기문에서 분기했는지 안 했는지를 보지만, 연관 분기 예측에선 if에서 분기했는지 안 했는지와 전에 여기서 분기했는지 안 했는지를 함께 고려한다.

---

3. 비순차적 실행 ( out-of-order execution )

---

일반적인 순차적 파이프라인에서는 어떤 명령어를 처리할 때 피연산자 데이터가 아직 계산되지 않으면 앞선 명령어들의 처리에서 필요한 값을 얻을 수 있을 때까지 파이프라인을 중단하게 되고, 이에 따라 그 다음 명령어들은 처리되지 못하고 대기하게 됨으로써 효율성이 떨어지게 된다.
이를 해결하기 위해 컴파일 단계에서 파이프라인 중단을 최소화하도록 명령어를 배치하는 최적화 등을 수행하기도 하지만, ISA마다 파이프라인 구조가 다르고, 컴파일 시간에 모든 데이터 의존성을 알 수 없는 등의 한계점이 많았다.

이에 따라 명령어를 순차적으로 실행하지 않는 비순차적 실행 기법이라는 것이 등장하게 되었다.
비순차적 실행 기법에서는 CPU의 명령어 해석 단계를 발행과 피연산자 읽기의 두 단계로 나누는데, 발행 단계는 순차적으로 거칠 수 있으나 피연산자 읽기 단계에서는 읽을 데이터가 계산될 때까지 진입하지 못하고 기다려야 하고, 이 틈을 타 뒤쪽의 명령어들이 먼저 순서를 바꿔 실행될 수 있다.

---

잠깐! 명령어 발행 단계가 뭐야?

---

Scoreboarding은 비순차적 실행 기법 중 하나인데, 비순차적 실행에 필요한 정보를 각 기능 단위(실제 연산을 수행하는 요소)에 흩어놓지 않고 scoreboard에 모아서 관리한다.
이 scoreborad에서는 처리하고 있는 명령어가 파이프라인의 어느 단계에 있는지에 대한 정보인 명령어 상태, 각 기능 단위가 어떤 상태인지를 나타내는 기능 단위 상태와 레지스터에 값을 쓰던 중, 어떤 기능 단위에서 값을 받아와야 하는지에 대한 정보인 레지스터 결과 상태를 저장한다.

이런 구조에서 읽어온 명령어는 발행, 피연산자 읽기, 실행, 되쓰기라는 다음 4개의 과정을 거치게 된다.

1. 발행(Issue) : 명령어를 해석하고, 앞선 명렁어들과의 구조적 해저드가 있는지 확인한 후, 있다면 발행하지 않고 해저드가 없어질 때까지 기다린다. 따라서 명령어 발행은 순차적으로 진행되어야 한다.

2. 피연산자 읽기(Read Operand) : 피연산자들을 읽기 전에, 레지스터를 쓰는 와중에 읽는 오류를 방지하기 위해 scoreboard에 저장된 모든 기능 단위 상태가 YES가 될 때까지 기다리고, YES가 되면 모든 기능 단위 상태를 NO로 바꾸고 피연산자를 읽는다.

3. 실행 : 기능 단위가 연산을 수행한다.

4. 되쓰기 : 결과를 레지스터에 쓰기 전에 쓰는 동작이 다른 곳에 필요한 결과를 덮어쓰는지 확인하고, 만약 그렇다면 그 행위가 끝날 때까지 기다린 후, 레지스터에 값을 쓴다.

---

이렇게 명령어들을 미리 실행시키며 최적화라는 장점을 가지게 되었으나, 비순차적으로 실행된 명령어들은 비순차적으로 완료하게 되어 예외 발생 시, 정확한 지점에서 재시작하는 것이 어려워 복잡성이 추가된다.

---

4. 추측 실행 ( speculation execution )

---

· 성능을 위해서 다음 실행될 명령어를 예측해 먼저 실행하는 기법이다.
예를 들어 확인해보자.

if ( ! strcmp( "Hello", str) )
    strcat(str, " World!\n" );

이런 명렁어가 있다고 했을 때, 함수 strcmp를 실행하는 데에는 상당한 시간이 걸린다.
이 때 CPU를 대기시키지 않고, 미리 다음 명령어를 실행해두었다가, 분기문이 실행되면 대기시간만큼의 시간적 이득을 보게 되고, 분기문이 실행되지 않았다면 실행 결과를 폐기해 실행되지 않은 것처럼 한다.