[SPARC] 6. Pipelining Hazard

지난 포스팅에서 하나의 명령어를 처리하는 과정을 여러 단계 (Stage) 로 나누어서 처리함으로서

여러 명령어를 처리하는 전체 시간을 줄이는 '파이프라이닝' 에 대하여 정리하였다.

 

이번에는 이 '파이프라이닝'을 사용하였을 때 발생할 수 있는 위험, Hazard, 에는 어떤 것들이 있는지,

그리고 각 Hazard를 어떻게 해결할 수 있는지 정리하고자 한다.

 

0. Hazard

각 명령어의 처리 단계 (F, E, M, W) 하나 하나는 클럭 사이클마다 진행된다.

이때 특정 클럭사이클에서 실행되어야 하는 다음 명령어가 실행되지 못하는 상황을 Hazard 라고 한다.

Hazard는 크게 3가지 종류가 있다.

이제부터 하나씩 정리해보자

1. Structural Hazard (구조적 해저드)

구조적 해저드는 어떤 클럭 사이클에서 두 개의 명령어가 같은 하드웨어를 사용하려는 경우를 말한다.

예를 들어 아래와 같이 명령어가 실행되는 상황을 생각해보자.

F1 > E1 > M1 > W1
     F2 > E2 > M2 > W2
          F3 > E3 > M3 > W3

첫번째 명령어의 M1 단계가 수행되면서 메모리로의 데이터에 접근하는 상황에서

F3 단계가 수행되면서 메모리로부터 명령어를 가져오고 있다.

 

만약 M1 단계에서 값을 가져오는 메모리와 F3 단계에서 명령어를 가져오는 메모리가 같다면

하나의 메모리에 동시에 접근하게 된다.

 

만약 메모리가 두 명령어를 같은 사이클에 실행하는 것을 지원하지 않는다면 두 명령어중 하나는 실행되지 않을 것이다.

이렇게 하드웨어적인 성능의 문제로 명령어가 실행되지 않는 Hazard 를 Structural Hazard 라고 한다.

 

<Structural Hazard Solution>

이 Hazard의 해결방법은 무엇일까?

아주 간단하다. 그저 하드웨어를 더 추가하여 동시에 명령어를 실행할 수 있게 해주면 된다.

 

가령, 위의 예시에서 F3에서 메모리로부터 '명령어'를 가져오고 있고,

M1에서는 메모리의 '데이터' 를 접근하고 있으므로

'명령어'를 저장하는 메모리와 '데이터'를 저정하는 메모리를 분리한다면 이 문제는 해결될 것이다.

구조적 Hazard 는 하드웨어 설계로 해결하는 케이스가 많아 수업 중 강조된 내용은 아니었다.

 

책에 소개되지 않은 다른 방법으로는 한 명령어가 메모리 사용을 끝낼 때까지 기다린 후,

다른 명령어가 메모리 사용을 시작하는 방법도 있다.

(시간은 최고의 자원이다 ^ㅇ^)

 

2. Data Hazard (데이터 해저드)

한 명령어의 실행에 필요한 데이터가, 이전 명령어의 실행 결과에 의존하는 경우를 말한다.

이런 상황을 Data Dependence 라고 한다.

 

예를 들어 아래와 같은 두 명령어가 실행된다고 해보자.

add r1, r2, r3
sub r3, r4, r5

파이프라이닝을 이용하면 위 명령어들은 아래 그림과 같은 순서로 실행될 것이다.

sub 명령어를 실행하는데 필요한 r3 데이터는 add 명령어의 실행 결과로 생성된다.

따라서 W1 단계가 지나야만 E2 단계에서 사용할 수 있다.

sub 명령어가 r3 데이터에 의존하고 있는 것이다.

 

<Data Hazard Solution>

데이터 해저드의 해결방법은 크게 2가지가 있다.

 

1. Pipeline stall (파이프라인 지연)

r3 데이터가 레지스터에 쓰일 때까지, 파이프라인 단계를 중지하였다가 실행하는 것이다.

위 그림과 같은 상황이 될 것이다.

나는 여기에서 한가지 의문점이 들었다.

어떻게 F2 명령어는 W1 명령과 동시에 실행되어도 문제가 없는 것일까?

 

이전 포스팅의 내용을 복습해보자.

F (Fetch) 단계는

 

- 메모리에서 명령어를 가져오고,

- 가져온 명령어를 해석하며,

- 해석한 결과를 토대로 연산에 필요한 데이터를 레지스터에서 가져오는 단계까지 수행한다고 하였다.

 

그렇다면 명령어의 해석까지는 문제가 없는데, 레지스터에서 데이터를 가져오는 것은 어떻게 하는 걸까?

 

그 전에 '레지스터에서 데이터를 가져온다' 라는 과정은 무엇인가?

어차피 레지스터와 ALU 는 물리적으로 연결되어 있지 않은가?

ALU 의 연산시 사용하는 공간에 레지스터의 데이터를 옮겨두기라도 한다는 것일까?

 

만약 그렇다면, Fetch 단계에서는 r3의 값이 없을텐데,

왜 F2 명령어와 W1 명령어는 동시에 실행되어도 문제가 없는 것일까?

 

만약 ALU 에 임시 공간이 없이 레지스터와 다이렉트로 연결되어 있어,

실제 연산시에는 레지스터에서 바로 값을 읽어낸다면

'레지스터에서 데이터를 가져온다' 라는 과정은 왜 F에서 발생하는 것일까?

E에서 발생하는 것 아닐까?

 

>> 인터넷 자료를 검색해보았을 때는

연산을 하기 위해 레지스터의 값을 읽어 들이는 시점은 E 단계인 것 같았다.

그리고 이 가정이 맞다면 아래 후술할 두번째 해결책이 적용되는 이유도 납득이 되었다.

 

>>> 먼저 어셈을 들었던 분에게 강의자료를 받아봤는데,

그 강의자료에는 W 와 F가 동시에 실행될 수 있는 이유가

W 단계에서 레지스터에 값을 쓰는 것이 먼저 선행되고나서 F 단계가 실행되기 때문이라고 한다.

 

>>>> 교수님께 질문한 결과 아래와 같이 이해하였다.

- 우선 자세한 내용은 컴퓨터 구조를 공부할 때 배운다.

- F2 는 엄밀하게 2사이클 쉬었다가 W1과 함께 실행되는 것이 아니라

기존 순서대로 실행되고나서 2 사이클을 쉬고, W1이 실행되면 E2를 실행한다.

(이때 단순히 쉬는 것이 아니라, 계속 레지스터에서 값을 가져오는 것을 반복 시도한다.)

따라서 W1 이 실행되면 F2가 재실행되는 과정에서 값을 가져오게 되고,

그 이후에 E2가 실행되면 값을 쓸 수 있게 된다.

 

만약 레지스터의 값을 읽어 들이는 시점이 E 단계라면,

사이클을 2사이클 건너 뛰는 것으로 충분히 Data Hazard 를 방지할 수 있다.

E 단계이서 읽어들이는 시점에는 W 단계가 실행된 이후이므로

레지스터에 연산에 필요한 값이 들어있기 때문이다.

 

(그래서 내가 본 포스팅에서는 3사이클 이상 건너가는 경우에는

Data Hazard 가 발생하지 않는다고도 표현한다.)

 

2. Forwarding / Bypassing (전방전달)

이 방법은 하드웨어적인 해결방법이다.

기존 파이프라이닝 방식대로 수행할 때 데이터 해저드가 발생하는 이유는

 

1. 레지스터에 연산 결과가 아직 쓰이지 않은 상태에서

2. 레지스터로부터 연산에 필요한 데이터를 읽으려고 하기 때문이다.

 

즉, 레지스터를 거치는 것이 문제가 되는 것이다.

그렇다면 해결 방법은 레지스터를 거치지 않고, 바로 결과 값을 넘겨주면 된다.

 

그러면 이렇게 E1 이 실행된 이후에 E2 를 바로 실행할 수 있게 된다.

이를 구현하는 방법은, E1 의 연산결과를 바로 다시 ALU에서 사용할 수 있도록, 별도의 회로를 만드는 것이다.

그래서 연산 결과가 레지스터를 거치지 않고, 별도 회로를 통해 다시 ALU로 들어가도록 Bypass 시키는 것이다.

이 별도 회로를 'Forwarding Circuit' 이라고 한다.

 

만약 R3 에 값이 들어있었고, Forwarding Circuit 으로도 값이 왔다면 어떤 값을 연산에 쓸 지

어떻게 판단할까?

F단계든, E단계든 암튼 레지스터에서 값을 읽기는 할텐데

무조건 Forwarding Circuit 을 읽는 것도 이해가 안되는게, 

다음에 실행할 명령어가 현재 데이터에 의존할지 안할지 어떻게 판단해서 Forwarding 하는가?

왠지 일단 무조건 Forwarding 시키고,

E2 연산에서 Forwarding 값과 레지스터 값 중 취사선택을 할 거 같은데 그 기준이 궁금함.

 

>> 교수님 답변은 아래와 같았다.

Forwarding 은 항상 하지 않는다.

위 문제처럼 같은 주소의 레지스터를 읽으려는 시도가 있는 특정상황에서만 Forwarding을  하고

Forwarding 을 한 경우에 레지스터 대신 Forwarding 된 값을 읽는다.

 

3. Control Hazard (제어 해저드)

명령어 중에는 연산 명령어 뿐만 아니라 '분기' 명령어도 있다.

C언어 같은 프로그래밍 언어에서 for, if 와 같은 문법에 해당한다.

반복을 계속할지, 특정 코드를 실행할지 조건을 판단할 때 분기 명령어(Branch Instruction)가 실행된다.

 

중요한 것은 '분기를 할지 말지 판단' 하는 것도 하나의 명령어 실행 주기에 들어간다는 점이다.

여기에서 제어 해저드가 발생한다.

be 명령어가 분기명령어 인데, 조건이 맞으면 test1 으로 넘어가는 명령어이다.

이때 조건이 맞는지 틀린지 판단하는 과정이 F1~W1 까지 수행된다.

이때 궁금한 점은 F1~W1 을 수행하는 동안, 파이프라이닝에 따라 F2~W2 를 수행할 것인가? 에 대한 문제이다.

 

만약 조건이 맞아서 test1 으로 가야한다면 가면된다.

그런데 만약 위 상황처럼 조건이 맞는지 확인하는 과정에서 그 다음 명령어를 실행했고,

그 다음 명령어를 실행하면서 l3 의 값이 쓰여버려서 test1 에서 의도와 다른 l3 값을 사용하게 된다면 어떨까?

이는 매우 크리티컬한 문제가 될 것이다.

 

따라서 분기 조건을 체크하는 동안, F2 ~ W2 부분을 어떻게 처리할 것인지가 제어 해저드의 솔루션이 된다.

 

<Control Hazard Solution>

제어 해저드의 솔루션은 크게 3가지가 있다.

 

1. Pipeline Stall (파이프라인 지연)

데이터 해저드에서도 그랬듯, 분기할지 말지 결정이 되는 그 순간까지 기다린다.

E 단계에서 연산을 하고나면 결정이 되기 때문에, 1cycle이 딜레이된다.

 

2. Branch Prediction (분기 예측)

일단 실행해두고, 분기해야하면 실행했던 데이터를 버린다.

(즉, 이 경우, 분기를 하지 않는다고 예측해서 일단 실행 해두고,

예측이 틀린 경우, 실행했던 것을 버리는 것이다.)

그런데 이 '버린다' 라는 과정의 구현은 별도 하드웨어를 통해 이루어진다고 한다.

 

3. Delayed Branch (분기 지연)

일단 무조건 실행하고 본다.

SPARC 가 채택하고 있는 무식한? 방법이다.

 

분기 명령 다음에 오는 명령어를 무조건 실행하는 것으로,

만약 이 명령어 자리에서 아무것도 실행되어서는 안된다면 이 자리에 NOP를 넣는다.

(NOP = No OPeration)

이것도 결과만 두고보면 1과 동일하기 때문에 퍼포먼스의 낭비인 셈이다.

다만 분기 지연을 피하기 위해, 분기와 관련없는 명령어를 배치하여 실행하는 것으로 효율을 높일 수 있다.

(1과의 차이점은 1은 무조건 쉬는 것, 3은 무조건 실행하는 것이다)

 

이렇게 분기명령어 다음에 무조건 실행되는 명령어 위치를 'Branch Delay Slot' 이라고 부른다.

 

여기에 수업중에 궁금해서 질문을 했었던 내용도 같이 정리하고자 한다.

교수님의 설명을 들으면서 이해한 바로는

분기할지 말지 결정하는 것도 결국 하나의 명령어 처리이고,

그렇다면 분기를 하는 것은 명령어 처리 결과가 레지스터에 있어야 한다는 것인데,

 

솔루션 2번도 그렇고, 솔루션 1번에서 1-Cycle 만 쉬는 것도 그렇고

E 만 실행이 되면 분기를 처리할 수 있는 이유가 궁금했다.

 

Q. 분기를 할 지 말 지 결정하는 것도 결국 연산이고,

그 연산의 결과가 레지스터에 저장이 되어 있어야 분기를 할 수 있는 것 아닌가요?

(즉, W1 의 단계까지 거쳐서 레지스터에 값이 있어야 분기를 할 수 있는 것 아닌가요?)

어떻게 F1~W1 과정이 다 끝나기도 전에 F2 / F3 으로 분기할 수 있는 건가요?

 

A. 분기를 할 지 말 지 연산의 결과는 E 에서 나오기 때문에 E 단계만 거쳐도 알 수 있고,

실제로는 W와 같은 단계가 아니라 회로적으로 다른 단계를 거쳐 처리를 한다.

나중에 수업하면서 보게 되니, 일단 지금은 E 단계에서 분기에 대한 결과가 나온다고 이해하면 된다.

---

참고 사이트

https://talkingaboutme.tistory.com/entry/Study-Pipeline-Hazard

[Study] Pipeline Hazard

https://gofo-coding.tistory.com/entry/Data-Hazard

4. Data Hazard

https://gofo-coding.tistory.com/entry/Structure-Hazard

4. Structural Hazard

https://ezeun.tistory.com/m/183

[컴퓨터구조] #14. Pipeline MIPS(3)

https://ko.wikipedia.org/wiki/%EB%B6%84%EA%B8%B0_%EC%98%88%EC%B8%A1

분기 예측 - 위키백과, 우리 모두의 백과사전