[컴퓨터구조] Pipelining(5): 제어 해저드 (Control Hazard)

이전 글에서는 데이터 해저드에 대해 알아보았다.

[컴퓨터구조] Pipelining(4): 데이터 해저드 (Data Hazard)

[컴퓨터구조] Pipelining(4): 데이터 해저드 (Data Hazard)

 

데이터 해저드는 산술 연산과 데이터 전송과 관련된 해저드이다. 이번 글에서는 조건부 분기와 관련된 해저드인 제어 해저드(control hazard)에 살펴보도록 하자.

 

파이프라인이 계속 일을 하기 위해서는 매 클럭마다 명령어가 인출되어야 한다. 하지만 beq 명령어에서 분기 여부에 대한 결정이 MEM 단계에 가서야 이루어진다. 이렇게 인출할 명령어를 결정하는 일이 늦어지는 현상을 제어 해저드(control hazard)라고 한다.

 

제어 해저드를 해결하기 위한 두 가지 방법을 살펴보자.

 

1. 분기가 일어나지 않는다고 가정

분기 여부가 결정될 때까지, 즉 MEM 단계까지 지연시키면 시간이 너무 오래 걸린다. 분기 지연(branch stalling)보다 좋은 방법은 분기가 일어나지 않는다고 예측하고 일단 명령어들을 순서대로 실행시키는 것이다. 만약 분기가 일어난다면 그 사이에 실행된 명령어들을 버리고 분기 목적지에서 실행을 계속한다.

 

명령어를 버리기 위해서는 원래의 제어값을 0으로 바꾸면 된다. 데이터 해저드(적재 명령어 일 때)의 경우에는 ID 단계의 제어값만 0으로 바꾸었다. 하지만 제어 해저드에서는 분기 여부가 결정되었을 때(MEM 단계에 도달했을 때) IF, ID, EX 단계에 있던 명령어 3개를 버려야 한다. 명령어를 버린다는 것은 파이프라인 IF, ID, EX 단계에 있는 명령어를 쓸어내야(flush) 한다는 것을 의미한다.

 

이번에는 성능 향상의 관점에서 생각해보자. 조건부 분기 성능을 향상시키기 위해서 분기가 일어났을 때의 비용을 줄여야 한다. 앞에서는 분기 명령어가 다음 PC값을 MEM 단계에서 결정한다고 가정했다. 하지만 조건부 분기 결정을 좀 더 앞당겨 할 수 있다면 어떨까?

 

이것을 위해 분기 주소의 계산, 분기 여부의 판단이라는 두 가지 작업을 더 앞으로 끌어올 수 있다.

 

먼저 분기 주소의 계산을 살펴보자. IF/ID 파이프라인 레지스터에는 이미 PC값과 수치 필드가 들어 있다. 따라서 분기 덧셈기를 EX단계에서 ID 단계로 옮겨 구현한다.

 

다음으로 분기 여부에 대한 판단을 살펴보자. beq 명령어는 ID 단계에서 읽은 레지스터 값을 비교해 두 레지스터의 값이 같은지를 확인한다. 분기 테스트를 ID 단계로 옮기는 것은 추가적인 forwarding unit과 해저드 검출 하드웨어를 필요로 한다는 것을 의미한다. 아직 파이프라인 상에 있는 결과값에 종속적인 분기도 제대로 실행할 수 있어야 하기 때문이다. 하지만 여기에는 두 가지 복잡한 문제가 존재한다.

 

첫번째, 모든 과정이 ID 단계 안에 끝나야 한다. 그래야만 PC값을 분기 목적지 주소로 바꿀 수 있다. ID 단계에서 두 피연산자의 값이 같은지를 비교하는 유닛을 도입한다면, 새로운 전방 전달 회로를 필요로 한다. (기존의 전방전달 회로는 EX 단계에 있는 ALU에 대한 것이다)

 

두번째, 분기 비교에 사용할 값이 ID 단계보다 더 나중에 생성될 수도 있다. 이 경우 데이터 해저드가 일어나거나, 지연(stalling)이 필요하게 될 수 있다. 예를 들어, 분기 명령어 바로 앞의 ALU 명령어가 조건부 분기의 피연산자를 생성할 때 지연이 필요하다.(ALU 명령어를 위한 EX단계가 분기 명령어의 ID단계보다 뒤에 일어나기 때문) 또한, 적재 명령어 바로 뒤에 적재 결과를 사용하는 조건부 분기 명령어가 뒤따르면 두 사이클의 지연이 필요하다.(적재 명령어의 결과가 나오는 MEM 단계가 분기 명령어의 ID 단계보다 뒤에서 일어나기 때문)

 

이러한 어려움에도 불구하고, 분기 손실을 단 하나의 명령어로 줄일 수 있기 때문에 조건부 분기 실행을 ID 단계로 옮기는 것이 효율적이라고 할 수 있다.

 

 

IF 단계의 명령어를 버리기 위해 IF.Flush 제어선이 추가되었다. 이 제어선이 인가되면, IF/ID 파이프라인 레지스터의 명령어 필드를 0으로 만든다. 즉, nop을 삽입한다.

 

2. 동적 분기 예측 (dynamic branch prediction)

앞서 살펴본 '분기가 일어나지 않는다고 가정'하는 방식은 파이프라인이 깊어질 수록 분기 손실이 증가한다. 따라서 좀 더 많은 하드웨어를 사용해 프로그램 실행 중 분기 행동을 예측하는 방법을 시도해 볼 수 있다.

 

한 가지 방법은 명령어의 주소를 조사해 이 분기 명령어가 지난번 실행되었을 때 분기했는지를 알아본다. 만약 분기했다면 지난번과 같은 주소에서 새로운 명령어를 가져오도록 한다. 이것을 동적 분기 예측(dynamic branch prediction)이라고 한다.

 

이 방식은 분기 명령어 주소의 하위 비트에 의해 인덱스되는 작은 메모리인 분기 예측 버퍼(branch prediction buffer)라는 자료구조를 이용한다. 이 메모리는 최근 분기 여부를 나타내는 비트를 가진다. 예측대로 명령을 실행하고, 예측이 틀리다면 잘못 예측된 명령어를 삭제하고 예측 비트를 바꾼 후 올바른 명령어를 인출해 실행한다.

 

가장 간단한 1비트 예측 방법은 성능에 문제가 있다. 항상 분기하다가 어쩌다가 한 번 분기하지 않을 때를 가정하면, 한 번이 아니라 두 번 틀리게 된다. 이는 예측 비트를 더 많이 사용해서 해결할 수 있다. 2비트 예측 방법을 사용하면 예측이 두 번 잘못되었을 때만 예측값이 바뀐다.

2비트 예측 방법을 위한 finite state machine

 

지금까지 살펴본 동적 예측 기법은 예측하려는 분기 명령어에 대한 정보만을 이용한다. 그 이외에도 다른 명령어들의 정보를 함께 이용할 경우 같은 예측 비트들을 사용하고도 더 정확한 예측이 가능한데, 이러한 예측기를 연관 예측기(correlating predictor)라고 한다. 예를 들어, 각 분기에 대해 2개의 2비트 예측기를 사용해 직전에 실행된 분기 명령어의 분기 여부에 따라 예측기 하나를 선택한다.

 

또 다른 기술은 각각의 분기에 대해 다수의 예측기를 사용해 어떤 예측기가 가장 좋은 결과를 내는지 추적하는 토너먼트 예측기(tournament predictor)가 있다. 예를 들어, 각 분기 인덱스에 대해 2개의 예측을 한다. 하나는 해당 분기 명령어에 대한 정보만을 이용하고, 하나는 그 주변 명령어를 포함한 정보에 기반해 예측한다. 선택기가 두 예측기 중 더 정확했던 예측기를 선택한다. 

 

---

지금까지 살펴본 파이프라이닝을 하나의 그림으로 나타내었다.

 

 

다음 글에서는 제어 해저드의 다른 한 종류인 예외(exception)에 대해 살펴보자.