명령어 파이프라인 (Instruction Pipeline)
명령어 파이프라인이란 CPU 성능향상을 위해 명령어를 여러 단계로 나누어 동시에 실행하는 병렬 처리 기법이다.
명령어 처리 과정을 클럭 단위로 나누어보면 일반적으로 명령어 인출(IF, Instruction Fetch), 명령어 해석(ID, Instruction Decode), 명령어 실행(EX, Execute Instruction), 메모리 인출(MEM, Memory Fetch) 그리고 결과 저장(WB, Write Back)으로 나눌 수 있다.
CPU 명령어 파이프라인은 아래 그림과 같이 각 단계를 동시에 실행한다.
파이프라인 위험(Pipeline Hazard)
파이프라이닝이 높은 성능을 가져오지만, 성능 향상에 실패하거나 오히려 성능이 저하되는 상황이 발생할 수 있다.
이를 파이프라인 위험 혹은 파이프라인 해저드라고 부른다.
파이프라인 위험에는 3가지 종류가 있다.
- 구조적 위험(Structural Hazard)
- 데이터 위험(Data Hazard)
- 제어 위험(Control Hazard)
구조적 위험(Structural Hazard)
구조적 위험은 서로 다른 명령어가 동시에 ALU, 레지스터와 같은 자원을 사용해야할 때 발생한다.
예를 들어 MEM 단계가 1클럭에 끝나지 않았다면 다음 파이프라인의 MEM 단계에서 멈춤(stall)이 발생한다.
다른 예시로 MEM 단계가 생략되는 명령어인 경우 WB 단계가 겹칠 수 있다.
데이터 위험(Data Hazard)
데이터 위험은 이전 명령어의 결과가 다음 명령어의 입력으로 사용될 때 발생한다.
예를 들어 다음과 같은 명령어를 수행한다면
add x19 x0 x1
sub x2 x19 x3
명령어 파이프라인은 아래와 같이 작동할 것이다.
제어 위험(Control Hazard)
제어 위험은 주로 분기 등으로 인한 프로그램 카운터(PC)의 갑작스러운 변화에 의해 발생한다.
기본적으로 프로그램 카운터(PC)는 현재 실행중인 명령어의 다음 주소로 갱신된다. 하지만 프로그램 실행 흐름이 바뀌어 프로그램 카운터(PC) 값에 갑작스러운 변화가 생긴다면, 명령어 파이프라인에 미리 가지고와서 처리 중이던 명령어들이 쓸모가 없어진다.
파이프라인 위험 해결방안
프로세서 관점에서는 nop 명령어를 사용하여 명령을 지연하는 등 위와 같은 파이프라인 위험을 해결하는 여러 방법이 있다.
구조적 위험 같은 경우에는 하드웨어 자원을 추가하거나, 하버드 아키텍처(데이터와 명령어의 메모리 분리)를 사용할 수 있고, 데이터 위험에서는 Forwarding이나 Code Relocation 등의 방법이 있으며, 제어 위험같은 경우에는 분기예측과 같은 방법으로 위험을 최소화할 수 있다.
하지만 응용 프로그램 관점에서는 구조적 위험이나 데이터 위험을 최소화하기는 쉽지 않다.
다만 제어 위험의 경우에는 프로그래밍적으로 분기를 최소화하는 방식이나 분기 예측의 hit-rate을 고려하여 분기문을 작성하여 제어 위험을 최소화할 수 있다.
다음은 제어위험을 최소화하여 속도를 개선할 수 있는 방법이다.
- 분기문을 최대한 지양한다.
- 분기 이력(branch history)이 충분히 쌓일 수 있도록 분기문을 편향되게 작성한다. gcc에서는
__builtin_expect매크로를 고려할 수 있다. - 분기를 예측하는 코드를 작성하기 힘든 경우 inline 방식(절댓값을 비트연산으로 구하는 등)으로 코드를 작성하거나, 메모리 보다 시간복잡도가 중요한 상황이라면 loop unrolling을 고려한다.
wikipedia - Branch_predictor
BlockQuicksort: How Branch Mispredictions don't affect Quicksort