Pipeline Overview

Performance Issues(성능 문제)

컴퓨터의 성능은 주어진 시간 동안 얼마나 많은 명령어를 실행할 수 있느냐에 따라 결정된다. 이 성능은 주기적으로 동작하는 클럭의 속도에 영향을 받는데, 클럭 주기는 명령어 실행 중 가장 오래 걸리는 경로, 즉 크리티컬 패스(critical path)에 의해 결정된다. MIPS 구조에서는 lw (load word) 명령어가 이 크리티컬 패스를 형성하는 대표적인 예다. 이 명령은 명령어 메모리에서 시작하여 레지스터 파일을 거쳐 ALU 연산을 하고, 데이터 메모리를 통해 값을 읽은 뒤 결과를 다시 레지스터에 저장하는 과정을 포함하기 때문이다.

이처럼 하나의 명령어가 너무 많은 단계를 거쳐야 한다면, 전체 클럭 주기를 이 경로에 맞추어야 하기 때문에 비효율적이다. 특히 대부분의 명령어는 lw보다 훨씬 간단한 동작을 수행하므로, 이러한 방식은 자주 실행되는 명령어들을 느리게 만들어 "공통적인 경우를 빠르게 처리하라(Make the common case fast)"라는 설계 원칙에 어긋난다. 이러한 문제를 해결하기 위한 방법이 바로 파이프라이닝(pipelining)이다.

Pipeline(MIPS)

파이프라이닝은 세탁소의 세탁, 헹굼, 건조 과정에 비유할 수 있다. 세탁기를 하나만 쓴다면 전체 세탁을 순차적으로 처리해야 하지만, 각 단계를 나누어 동시에 처리하면 전체 시간을 단축할 수 있다. 마찬가지로 명령어 실행을 여러 단계로 나누어 병렬로 실행하면 처리량(throughput)이 증가하고 성능이 향상된다.

MIPS 구조에서는 명령어 실행 과정을 다음 다섯 단계로 나눈다.
1. IF(Instruction Fetch) : 명령어를 메모리에서 가져온다.
2. ID(Instuction Decode & Register Fetch) : 명령어를 해석하고 레지스터 값을 읽는다.
3. EX(Execute) : 연산을 수행하거나 주소를 계산한다.
4. MEM(Memory Access) : 메모리에서 데이터를 읽거나 쓴다.
5. WB(Write Back) : 결과를 레지스터에 저장한다.

각 단계는 독립적으로 처리되므로, 하나의 명령어가 EX 단계에 있는 동안 다음 명령어는 ID 단계에 들어올 수 있다. 이처럼 파이프라인은 여러 명령어가 동시에 서로 다른 단계에서 처리되도록 하여 처리량을 극대화한다.

파이프라인의 성능 향상

단일 사이클 구조에서는 lw 명령어에 맞춰 전체 클럭 주기를 800ps로 설정해야 한다. 하지만 파이프라이닝 구조에서는 각 단계가 평균 200ps 내외로 분리되므로, 전체 클럭 주기를 200ps로 설정하고 매 주기마다 새로운 명령어를 시작할 수 있다. 이렇게 되면 이론적으로 파이프라인의 단계 수만큼 성능 향상이 가능하다.

Time between Instructions(pipelined) =
Time between instructions(nonpipelined)/Number of stages

물론 현실에서는 각 단계의 수행 시간이 균일하지 않고, 여러 종류의 Hazard(위험 요소)가 존재하므로 성능 향상은 제한적이다.

MIPS ISA와 파이프라이닝의 조화

MIPS ISA는 처음부터 파이프라이닝을 고려하여 설계되었다. 모든 명령어는 32비트로 고정되어 있으며, 형식이 단순하고 일정하여 해석과 디코딩이 간단하다. 또한 load/store 명령어의 주소 계산은 파이프라인의 EX 단계에서 이루어지고, 메모리 접근은 MEM 단계에서 처리된다. 이는 메모리 접근이 단 한 클럭 사이클만 소요되도록 하여 파이프라인 처리에 유리한 구조를 제공한다. 이처럼 MIPS ISA는 파이프라이닝을 효과적으로 구현할 수 있도록 설계된 대표적인 명령어 집합 구조이다.

Pipelining 장애 요소 : Hazards

파이프라이닝은 여러 명령어를 병렬로 실행해 성능을 극대화하는 기술이지만, 모든 명령어가 항상 순조롭게 동시에 실행될 수 있는 것은 아니다. 특정 상황에서는 다음 명령어가 바로 다음 사이클에 시작되지 못하고 지연(stall)되어야 할 경우가 있다. 이런 상황을 Hazard(위험 요소)라고 한다. Hazards는 크게 세 가지로 나뉜다: 구조적(Structural), 데이터(Data), 제어(Control) Hazard이다.

Structual Hazard

구조적 Hazard는 하드웨어 자원이 부족할 때 발생한다. 예를 들어, MIPS 파이프라인이 명령어와 데이터를 같은 메모리 공간에 저장한다면, 하나의 명령어가 데이터를 읽는 동안 다른 명령어가 명령어 메모리에서 새로운 명령어를 가져오지 못하는 상황이 생긴다.

예를 들어 lw 명령어가 데이터 메모리를 사용하는 동안, 다음 명령어가 명령어를 가져오기 위해 같은 메모리를 필요로 하면 충돌이 발생하고 파이프라인은 한 사이클 지연되어야 한다. 이러한 문제를 해결하기 위해 일반적으로 명령어 메모리와 데이터 메모리를 분리하거나, 캐시를 따로 구성하여 자원 충돌을 방지한다.

Data Hazard

데이터 Hazard는 한 명령어가 사용하는 데이터가 이전 명령어에 의해 아직 갱신되지 않은 상태일 때 발생한다. 예를 들어 다음과 같은 코드가 있다고 하자:

add $s0, $t0, $t1
sub $t2, $s0, $t3

두 번째 명령어 sub는 첫 번째 명령어 add의 결과 $s0를 필요로 하지만, add 명령어가 아직 결과를 레지스터에 쓰기 전에 sub 명령어가 실행된다면 잘못된 값을 읽게 된다. 이를 해결하는 대표적인 방법은 Forwarding (혹은 Bypassing)이다. 이는 결과가 레지스터에 기록되기 전에 바로 다음 단계로 전달되는 경로를 추가하여 데이터를 우회시켜주는 기법이다.

그러나 모든 경우에 Forwarding이 가능한 것은 아니다. 예를 들어 lw 명령어는 메모리에서 데이터를 읽어오는 시간이 필요하기 때문에, 그 결과를 사용하는 다음 명령어는 값을 사용할 수 있는 시점까지 한 사이클 지연되어야 한다. 이 경우는 Load-Use Hazard 라고 하며, 보통 1사이클 정지(stall)로 해결한다.

Reordering Code to Avoid Pipeline Stalls(코드 재배치)

파이프라인에서 연산 간의 데이터 의존성 때문에 발생하는 스톨(stall)은 성능 저하의 주요 원인 중 하나이다. 특히 lw 명령어 이후 바로 이어지는 연산 명령어는 데이터가 메모리에서 로드되기 전이므로 아직 유효하지 않은 값을 사용할 위험이 있다. 이를 load-use hazard라고 부르며, 보통 1사이클의 정지가 필요하다. 하지만 이러한 정지를 피할 수 있도록 명령어의 순서를 재배치하면 성능을 높일 수 있다.

예제 코드와 문제점 분석

//c code
a = b + e;
c = b + f;

lw  $t1, 0($t0)    # b를 $t1에 로드
lw  $t2, 4($t0)    # e를 $t2에 로드
add $t3, $t1, $t2  # t3 = b + e
sw  $t3, 12($t0)   # 결과 저장
lw  $t4, 8($t0)    # f를 $t4에 로드
add $t5, $t1, $t4  # t5 = b + f
sw  $t5, 16($t0)   # 결과 저장

이 코드에는 두 번의 load0-use hazard가 존재한다.
1. add $t3, $t1, $t2는 바로 앞의 lw $ t2, 4($t0)의 결과가 필요하므로 1사이클 스톨 필요
2. add $ t5, $ t1, $ t4는 바로 앞의 lw $ t4, 8($t0)의 결과가 필요하므로 또 1사이클 스톨** 필요

총 2사이클의 지연이 발생

Stall 없는 코드 재배치
위 문제를 해결하는 가장 간단한 방법은 세 번째 lw 명령어를 앞쪽으로 이동시키는 것이다.

lw  $t1, 0($t0)
lw  $t2, 4($t0)
lw  $t4, 8($t0)    # <- f를 미리 로드
add $t3, $t1, $t2
sw  $t3, 12($t0)
add $t5, $t1, $t4
sw  $t5, 16($t0)

이렇게 하면 모든 add 명령어는 앞선 lw로부터 충분한 시간이 경과한 뒤 실행되므로, load-use hazard가 발생하지 않고 스톨이 제거된다. 또한, sw 명령어들은 메모리 쓰기이므로 forwarding 기법에 의해 hazard 없이 수행될 수 있다.

성능 향상
원래의 명령어 순서에서는 2개의 스톨 사이클로 인해 총 13 사이클이 소요되었지만, 재배치된 코드에서는 이를 제거하여 11 사이클로 줄일 수 있다. 이는 약 15%의 성능 향상에 해당한다. 특히 forwarding 기능을 갖춘 파이프라인 구조에서는 명령어 순서 조정만으로도 성능 최적화가 가능하다는 점에서 매우 중요한 기법이다.

Control Hazard

파이프라인에서 분기(branch) 명령어는 명령어 흐름에 큰 영향을 미친다. beq, bne와 같은 분기 명령어는 조건에 따라 프로그램의 흐름을 바꾸므로, 이 명령어의 결과가 확정되기 전까지 어떤 명령어를 다음에 가져올지 알 수 없다는 불확실성이 존재한다. 이를 제어 위험(control hazard)이라고 하며, 파이프라인의 성능에 직접적인 영향을 준다.

예를 들어 beq $s0, $s1, target라는 명령어가 있을 때, $s0과 $s1의 값이 같은지 비교해서 분기를 할지 말지를 결정해야 한다. 하지만 분기 결과가 확정되기 전, 이미 다음 명령어를 가져왔다면 그 명령어는 잘못된 명령일 수 있다. 이로 인해 파이프라인은 branch outcome을 알 때까지 stall을 하거나, 분기가 일어나지 않는다고 예측하여 다음 명령어를 미리 가져오는(branch prediction) 전략을 사용한다.

가장 단순한 예측 방식은 "분기 안 함(Predict Not Taken)" 방식이다. 이 경우 예측이 틀리면 잘못 가져온 명령어들을 파이프라인에서 제거(flush)해야 하며, 이로 인해 성능 손실이 발생한다. 더 진보된 방식으로는 최근 분기 결과를 바탕으로 예측하는 Static 혹은 Dynamic Branch Prediction 기법들이 있다.

Stall on Branch: 결과 나올 때까지 기다리기

가장 직관적인 해결책은 분기 결과가 확정될 때까지 다음 명령어를 가져오지 않고 대기(stall)하는 것이다. 예를 들어, MIPS 파이프라인에서는 ID 단계에서 분기 조건을 확인할 수 있도록 비교 연산과 분기 대상 주소 계산을 수행한다. 이 방식은 분기 명령어가 EX나 MEM 단계에서 조건을 판별하는 것보다 빠르지만, 여전히 한 사이클 이상 정지가 필요하다. 이러한 정지는 파이프라인의 처리량(throughput)을 감소시키며 성능 저하를 유발한다.

Branch Prediction: 분기를 미리 예측하기

성능 손실을 줄이기 위해 컴퓨터 구조는 분기 예측(branch prediction)이라는 기법을 활용한다. 이 방식은 분기 명령어가 실행되기 전, 분기가 일어날지 아닐지를 미리 예측하고, 예측된 방향으로 다음 명령어를 가져와 실행을 시작한다. 만약 예측이 맞으면 성능 저하 없이 명령어가 그대로 진행되고, 틀리면 잘못 가져온 명령어들을 파이프라인에서 flush(버리기)하고 올바른 경로로 다시 명령어를 가져온다.

MIPS with Predict Not Taken: "분기 안 한다"로 가정

MIPS 파이프라인에서 구현된 가장 단순한 예측 방법은 Predict Not Taken이다. 이 방식은 기본적으로 분기 명령어는 분기하지 않는다고 가정하고, 그 다음 연속된 명령어를 그대로 가져온다. 예측이 맞으면 스톨 없이 실행되고, 틀릴 경우에만 정지 및 복구가 발생한다.

예를 들어 beq 명령어가 ID 단계에 있을 때, 파이프라인은 다음 명령어를 그대로 가져오고 실행을 준비한다. 이후 분기 조건이 참이라면, 잘못 가져온 명령어들을 무효화하고 분기 주소로 점프한다. 이 방식은 하드웨어 복잡도는 낮지만, 반복문이나 조건문에서 예측 실패가 잦으면 오히려 성능 손해가 발생할 수 있다.

More Realistic Branch Prediction: 정적 및 동적 예측

더 정교한 분기 예측은 정적(static) 또는 동적(dynamic) 방법으로 나뉜다.

정적 분기 예측(Static Prediction)
정적 예측은 분기 명령어의 형태나 위치에 기반하여 미리 정해진 규칙으로 분기 방향을 예측한다. 대표적인 규칙은 다음과 같다:

• 뒤로 가는 분기(backward branch, 반복문 등)는 taken(분기함)으로 예측
• 앞으로 가는 분기(forward branch, 조건문 등)는 not taken(분기하지 않음)으로 예측

이 방식은 간단하지만 모든 상황을 반영하지는 못한다.

동적 분기 예측(Dynamic Prediction)
동적 예측은 실제 실행 결과를 기억하고 그 기록을 바탕으로 다음 분기를 예측하는 방법이다. 대표적으로 branch history table(분기 기록 테이블)을 사용한다. 이 테이블은 최근 분기 명령어의 주소를 기반으로 분기 여부 결과(taken/not taken)를 저장하고, 다음에 같은 명령어가 실행되면 그 경향을 따라 예측한다.

예측이 틀리면, 잘못된 명령어들을 파이프라인에서 제거하고 테이블의 기록도 갱신한다. 반복문처럼 같은 분기가 계속 반복될 때 특히 효과적이며, 보다 높은 예측 정확도를 달성할 수 있다.

Pipeline Summary

정리하자면, 파이프라이닝은 명령어 처리량을 향상시키기 위한 핵심 기술이다. 각 명령어를 여러 단계로 나누어 병렬로 실행하며, 각 명령어의 실행 시간이 짧아지지는 않지만, 단위 시간 내에 더 많은 명령어를 실행할 수 있게 한다. 그러나 성능 향상을 위해서는 구조적, 데이터, 제어 Hazard와 같은 문제들을 해결해야 한다.

특히 분기와 관련된 제어 Hazard는 예측과 회피 전략이 핵심이다. 단순한 정지보다 예측 기반의 실행이 훨씬 효율적이며, 정적 예측보다 동적 예측이 더 높은 정확도를 보장할 수 있다. 결국, 파이프라인 성능의 핵심은 Hazard 관리에 달려 있으며, 그 중 분기 예측은 가장 결정적인 성능 개선 요소 중 하나다.