[컴퓨터 구조] 8. 파이프 라인 해저드

파이프 라인 기술로 구현된 명령 처리 과정에서 발생할 수 있는 해저드 종류는 다음과 같다.

 

1. 구조적 해저드

CPU 자원의 한계로 사용할 수 있는 내부 버스는 동시에 사용될 수 없다. 동일한 레지스터/메모리 조각에 동시에 쓰려고 하는 경우가 그 예가 된다.

 

2. 데이터 해저드

두 명령어에서 사용되는 레지스터들이 의존적 관계가 있을 때 성립한다.

 

다음 명령어들을 보자.

 

sub x2, x1, x3

and x12, x2, x5

or x13, x6, x2

add x14, x2, x2

sd x15, 100(x2)

 

마지막 네 명령어 모두 첫 번째 명령어의 레지스터 x2의 결과에 종속적이다. 실제 파이프라인 과정에서 정상적으로 읽고 써지는 단계는 마지막 두 단계, add와 sd인데 add의 경우 x2를 읽으려 할 때 x2에 첫 번째 sub 결과가 쓰기가 완료되기 때문이다. sd는 IF 단계 전에 이미 데이터가 완성되어 있다.

5개의 시퀀스 명령어에서 종속성

데이터가 레지스터 파일에서 읽히기 전에 계산된 결과가 바로 전달되면 지연 없이 명령어를 실행할 수 있다. 이를 전방전달이라고 한다.

주로 이전 명령어에서 EX/MEM의 목적지 레지스터 혹은 MEM/WB의 목적지 레지스터가 다음 ID/EX 레지스터의 src 레지스터(rs1, rs2)로 사용될 경우 데이터 해저드를 발견할 수 있다.

 

두 명령어 쌍에서 발견될 수 있는 데이터 해저드 조건

EX/MEM.RegisterRd = ID/EX.RegisterRs1

EX/MEM.RegisterRd = ID/EX.RegisterRs2

MEM/WB.RegisterRd = ID/EX.RegisterRs1

MEM/WB.RegisterRd = ID/EX.RegisterRs2

즉 이전 명령어에서 Write 대상 레지스터가 다음 명령어에서 Read 대상이 된다면 데이터 해저드가 발생한다. 때문에 위 조건이 만족하는 경우 전방 전달을 실현하면 된다.

전방전달

추가 전방전달 조건

- 이전 명령어가 레지스터 쓰기를 실행하지 않는다면 전달할 값이 없으니 전방 전달하지 않는다.

- x0 레지스터 값은 항상 0이다. 목적지 레지스터 주소가 0인 경우는 전방전달하지 않는다.

- 전방전달은 EX 단계에서 계산된 결과 혹은 MEM 단계에서 계산된 결과를 전방 전달할 수 있다. 그중 EX 단계 이후 전방 전달을 하였다면 MEM 단계 이후에서는 전방 전달하지 않는다.

 

EX 해저드 조건 : EX 이후에 전방전달하는 조건

EX 해저드 조건

MEM 해저드 조건 : MEM 단계 이후에 전방전달하는 조건 

MEM 해저드 조건

MEM 해저드 조건은 그 EX/MEM.RegWrite 가 1이 아닐 때 즉 그전에 전방 전달될 수 있는 경우가 아닐 조건이 추가된다. 

 

데이터 해저드와 지연 (stall)

LOAD와 같은 적재 명령어는 전방 전달로 지연없이 해결하는 것이 불가능하다. 실제 메모리에서 적재될 때와 다음 명령어가 피연산자로 요구하는 시점이 1 사이클 정도 차이가 있기 때문이다. 따라서 다음 해저드 검출 유닛에 의한 조건을 만족한다면 지연을 추가할 수 있도록 한다.

적재 명령어 검출

지연이 실행되면 예정되어 있던 다음 명령어는 nop 상태가 되어 아무 명령도 실행하지 않는다. 그 이후 명령어들은 차례대로 한 사이클 지연된다.

해저드 검출에 의한 지연

3. 제어 해저드

조건부 분기에 따른 다음 명령어가 바뀔 수 있을 때 발생한다. 분기 여부가 MEM 단계에서 알 수 있을 때 다음 인출할 명령어를 결정하는 일이 늦어진다.

제어/분기 해저드

위 그림과 같이 조건이 false되어 16 x 4 = 32 -> 40 + 32 -> 72번지로 분기하는 경우 그 사이의 명령어 들은 모두 버려진다.(flush) 

 

제어 해저드를 해결하기 위한 방법

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

조건부 분기가 항상 일어나지 않는다고 예측하고 명령어들을 순차적으로 실행하는 것이다. 확률적으로 반 정도는 맞는다.

 

- 분기에 따른 지연을 줄이는 바법

분기 결과 판단을 EX 단계에서 계산된 결과를 사용하기 때문에 이미 IF 단계에서 수치 필드와 PC값을 알고 있다면, 명령어를 기존 단계보다 앞 단계로 넘겨 ID 단계에서 판단하는 것이 가능하다.

하지만 ID 단계에서 판별되기 위해 ID 단계의 비교 회로에 전방 전달되는 것이 구현되어야 한다.

 

- 동적 분기 예측

하드웨어 자원을 좀 더 사용하여 과거 분기 명령 결과를 기록해두었다가 다음 분기 예측에 사용하는 방법이다. 이를 동적 분기 예측(dynamic branch prediction)이라고 한다.

 

1) 1비트 분기 예측 버퍼

구현하는 방법 중 하나는 분기 예측 버퍼(branch prediction buffer)라는 자료구조를 사용하는 것이다. 분기 예측 버퍼는 분기 명령어 주소의 하위 비트에 의해 인덱스 되는 작은 메모리로 분기가 일어났었는지 아닌지를 기록하고 있다.

 

하위 비트에 의해 인덱싱 되므로 하위 비트가 동일한 분기 명령어 주소에 의해 overwrite가 될 수 있지만 여전히 위 정적 조건에 의한 예측보다 더 좋은 예측을 보인다.

 

간단한 1 비트 예측은 문제점이 있을 수 있는데, 반복문의 끝에서 다시 처음으로 돌아가는 예측은 전체 반복이 10이라고 하면 8번 정도는 맞는다. 마지막은 마지막에 빠져나갈 때 기존 8번은 처음으로 돌아갔으므로 예측이 틀리고 처음 들어올 때는 그 이전 실행에서 나간 케이스로 기록되었기 때문에 예측이 빗나간다.

 

2) 2비트 분기 예측 버퍼

규칙적인 분기에 대한 정확도를 올리기 위해 예측이 두 번 잘못되었을 때만 예측이 바뀐다. 분기 예측 버퍼는 2비트를 사용하여 작은 특수 버퍼로 구성되고 IF 파이프라인 단계에서 명령어 주소를 인덱스로 사용하여 접근한다.

2 비트 예측 방법의 상태도

3) 분기 목적지 버퍼 (branch target buffer)

분기 예측기 버퍼는 다음 분기가 일어날 것인지 아닌지 참/거짓만 판별한다. 실제 분기 주소를 얻기 위해서는 1 사이클을 소비하여 다음 주소를 얻어와야 한다. 분기 목적지 버퍼는 분기할 PC 값이나 목적지 명령어 주소를 캐시 한다.

 

참고 : Computer Organization and Design RISC-V edition