[컴퓨터구조] 파이프라인 해저드 (Pipeline Hazards) 및 해결 방법

Hazard 종류

구조적 해저드 (Structural Hazards)

필요한 하드웨어 자원을 여러 명령어가 동시에 사용하려고 할 때 발생합니다. 즉  하드웨어 자원 부족으로 인해 발생하는 충돌입니다.

 

예 ) 하나의 메모리 포트를 가진 시스템에서 명령어 인출과 데이터 접근이 동시에 일어나려고 할 때 발생합니다.

 

해결방법 : 하드웨어 추가, 파이프라인 정지 (stall) (버블삽입)

 

데이터 해저드 (Data Hazards)

어떤 명령어가 이전에 실행된 명령어의 결과에 의존하는 경우, 이전 명령어가 결과를 생성하기 전에 다음 명령어가 그 결과를 사용하려고 할 때 발생합니다. 데이터 의존성으로 인해 발생하는 문제입니다.

 

RAW(Read After Write) : 어떤 명령어가 이전에 실행된 명령어가 쓴 데이터를 읽으려고 할 때 발생합니다.

WAR(Write After Read) : 어떤 명령어가 이전에 실행된 명령어가 읽은 데이터를 쓰려고 할 때 발생합니다. 파이프라인에서 명령어의 실행 순서가 바뀌는 경우에 발생할 수 잇습니다.

waw (Write After Write) : 두 개의 명령어가 같은 레지스터에 쓰려고 할 때 발생합니다. 

 

해결방법  

포워딩 : 이전 명령어의 결과를 WB단계까지 기다리지 않고, 필요한 단계에서 직접 다음 명령어에 전달하여 해저드를 해결합니다. 이는 ALU 입력단에 MUX가 추가되어서 ALU 출력과 pipeline register 값도 입력으로 되게끔 하는 것입니다.

 

STALL : 필요한 데이터가 준비될 때까지 파이프라인의 진행을 일시적으로 멈춥니다.

 

code scheduling : 프로그램의 실행 속도를 향상시키기 위해 명령어 순서 재배치 

 

제어 해저드(Control Hazards)

분기, 점프, 인터럽트 등으로 인해 실행할 명령어의 주소가 변경되어 발생하는 문제입니다.  파이프라인이 다음에 어떤 명령어를 인출해야 할지 모르는 상황입니다. 

 

예시 ) 조건 분기 명령어가 실행될 때, 조건의 참/거짓 여부가 결정되기 전까지는 다음 명령어를 결정할 수 없습니다. 

 

해결방법 : 

• 파이프라인 플러시 : 잘못 인출된 명령어들을 파이프라인에서 제거합니다.
• 분기 예측 : 분기의 결과를 예측하여 미리 다음 명령어를 인출합니다.
• 지연 분기 : 분기 명령어 바로 뒤에 분기와 관계없이 실행될 명령어를 배치합니다.

구조적 해저드	하드웨어 자원 부족	하드웨어 추가, 파이프라인 정지
데이터 해저드	데이터 의존성 (RAW, WAR, WAW)	포워딩, 파이프라인 정지
제어 해저드	분기, 점프, 인터럽트 등으로 인한 실행 흐름 변경	파이프라인 플러시, 분기 예측, 지연 분기

 

 

Hazard 예시

버블을 사용하여 데이터 해저드를 해결할 때 예시를 들어보겠습니다.

 

포워딩 없이 버블을 삽입하여 데이터 해저드를 해결하려고 할 때 두 instruction 사이 데이터 hazard가 존재한다는 가정에서 버블을 얼마나 삽입해야할까?

 

핵심은 레지스터 쓰기(WB)와 읽기(ID) 사이의 시간 차이입니다.

 

MIPS에서 레지스터에 값을 쓰는 작업은 WB에서 발생합니다. 반면 값을 읽는 작업은 ID에서 발생합니다. 이 두 단계 사이에는 EX와 MEM이 존재합니다.

• 명령어 1: add $t0, $s1, $s2
• 명령어 2: sub $t3, $t0, $s3

명령어 2는 명령어 1의 결과인 $t0를 필요로 합니다.

 

각 명령어의 파이프라인 진행 상황을 시간 순서대로 표로 나타내면 다음과 같습니다.

 

Clock  Cycle	명령어 1  (add)	명령어 2 (sub)	설명
1	IF		명령어 1 인출
2	ID	IF	명령어 1 해독, 명령어 2 인출
3	EX	ID	명령어 1 실행, 명령어 2 해독 (여기서 $t0 값을 읽으려 함)
4	MEM	EX	명령어 1 메모리 접근
5	WB	MEM	명령어 1 결과 $t0 레지스터에 쓰기, 명령어 2 실행
6		WB	명령어 2 결과 쓰기

여기서 중요한 것은 Clock cycle 3입니다. $t0값을 얻으려고 시도하지만, 명령어 1은 아직 EX단계에 있으므로 $t0은 계산되지 않았습니다. 즉 $t0은 clock cycle 5가 되어야 레지스터에 쓰여집니다.

 

따라서 명령어 2가 올바른 $t0값을 얻기 위해서는 명령어 2의 ID 단계가 clock cycle 5이후에 실행되어야 합니다.

 

 

Clock Cycle	명령어 1 (add)	버블 1	버블 2	버블 3	명령어 2 (sub)
1	IF
2	ID				IF
3	EX				ID
4	MEM				EX
5	WB				MEM
6					WB

버블 3개를 삽입함으로서 명령어 2의 id 단계는 Clock Cycle 6에서 사용됩니다. 이 시점에는 명령어 1이 WB단계를 완료하여 $t0에 값이 쓰여진 후이므로, 명령어2는 올바른 값을 읽을 수 있습니다.

 

즉 wb단계에서 결과값이 레지스터에 쓰이고 그 다음 싸이클되어야 하므로 세 개의 버블이 되어야 하는 것입니다.

 

Load-use 데이터 해저드

Load-use 해저드는 load 명령어 직후에 해당 load 명령어가 읽어온 값을 사용하는 명령어가 오는 경우 발생하는 데이터 해저드입니다. Load 명령어는 메모리에서 데이터를 읽어오는 데 시간이 걸리기 때문에, load 명령어 직후에 바로 그 값을 사용하려고 하면 데이터가 아직 준비되지 않은 상태에서 사용하는 문제가 발생합니다.

 

Forwarding : 이전 명령어의 결과를 WB단계까지 기다리지 않고 다음 명령어로 전달하는 기술

하지만 load 명령어의 경우, MEM 단계에서 데이터를 읽어오기 때문에 load 명령어 바로 다음 명령어는 포워딩을 사용하더라도 필요한 데이터를 얻을 수 없습니다.

 

이는 load 명령어 바로 다음 instruction에서 사용할 때 발생합니다.

 

반드시 bubble을 삽입할 필요는 없습니다.

 

포워딩을 사용하면 load 명령어 결과를 MEM/WB 레지스터에서 다음 명령어의 EX 단계로 전달할 수 있습니다. 하지만 LOAD 명령어 바로 다음 명령어는 id 단계에서 값을 읽으려고 시도하기 때문에, forwarding 만으로 해결되지는 않습니다. 
따라서 하나의 버블을 삽입하여 다음 명령어가 EX단계에서 값을 받을 수 있도록 해야합니다.

Clock Cycle	명령어 1 (lw)	명령어 2 (add)	설명
1	IF		lw 명령어 인출
2	ID	IF	lw 명령어 해독, add 명령어 인출
3	EX	ID	lw 명령어 주소 계산, add 명령어 해독 (여기서 $t0 값을 읽으려 하지만 아직 없음)
4	MEM	EX	lw 명령어 메모리 접근 (여기서 $t0 값을 읽어옴), add 명령어는 bubble로 인해 실행되지 않음
5	WB	MEM	lw 명령어 결과 $t0에 쓰기, forwarding을 통해 $t0 값을 다음 단계로 전달, add 명령어는 $t0 값을 받아서 실행
6		WB	add 명령어 결과 쓰기

 

branch hazard의 동적 분기 예측

분기 해저드

분기 명령어는 프로그램의 실행 흐름을 변경하는 명령어입니다. 파이프라인 구조에서 분기 명령어를 만나면, 분기의 결과가 결정되기 전까지는 다음에 어떤 명령어를 실행해야 하는지 알 수 없기에 파이프라인이 멈추거나 잘못된 명령어를 실행할 수 있습니다. 

 

이러한 문제를 분기 해저드라고 합니다.

 

동적 분기 예측이란?

동적 분기 예측은 과거의 분기 실행 결과를 이용하여 다음에 분기가 어떻게 될지 예측하는 기술입니다. 정적인 방법과 달리, 프로그램 실행 중에 분기 패턴을 학습하여 예측 정확도를 높입니다.

 

동적 분기 예측은 가장 최근의 분기 결과를 활용하여 예측합니다. 분기 명령어 바로 앞의 명령어를 분석하는 것은 분기 예측의 일반적인 방법이 아닙니다. 분기 명령어 자체의 과거 실행 이력을 분석하는 것이 핵심입니다. 

 

동적 분기 예측은 예측을 위한 추가적인 하드웨어를 필요로 하기 위해서 자원이 증가한비다. 

 

1-bit predictor는 가장 최근의 분기 결과만 저장합니다. 반면 2-bit predictor는 최근 두 번의 분기 결과를 저장하여 예측의 정확도를 높일 수 있습니다.

 

2-bit predictor는 두 비트를 사용하여 네 가지 상태를 나타냅니다. 연속 두 번 예측이 틀린 경우에만 예측 방향이 변경됩니다. 즉 한 번, 예측을 틀리더라도 바로 예측 방향을 바꾸지 않고, 두 번 연속으로 틀려야 예측 방향을 바꾸기에 안정성을 높입니다.

 

분기 주소를 계산하는 것은 일반적으로 PC값과 분기 offset을 더하는 연산입니다. 이 연산은 ID 단계에서 수행 가능하며, 추가적인 하드웨어 비용을 발생시키지 않습니다 

 

분기 여부를 판단하는 것은 두 값을 비교하는 연산입니다. 비교 연산은 ALU를 사용하여 수행할 수 있지만 반드시 ALU를 사용해야 하는 것은 아닙니다. 두 값이 같은지 판단하는데 XOR와 NOR로도 충분합니다. ALU 전체를 필요로하는 것은 아닙니다. 

 

분기 시점을 ID단계로 앞당기면, 분기 명령어 바로 앞에 있는 명령어를 알지 못한 상태에서 분기 여부를 판단해야 합니다. 이런 경우 Data Hazard가 발생할 수 있습니다. 

 

기존 분기가 MEM에서 결정되었기에 분기 예측이 틀린 경우 IF, ID, EX 단계의 명령어 3개의 flush해야 했습니다. 하지만 분기 시점을 ID로 옮기면 분기 예측이 틀린 경우 IF 단계 하나만 flush하면 됩니다. 따라서 flush 해야하는 명령어의 수가 줄어 성능 향상에는 도움이 됩니다.