파이프라인과 위험

세탁기, 건조기, 개는 일을 차례로 하는데, 첫 빨래를 다 개고 나서야 다음 빨래를 세탁기에 넣는다면 세탁기와 건조기는 대부분의 시간을 쉬게 됩니다. 첫 빨래를 건조기로 옮기자마자 둘째 빨래를 세탁기에 넣으면, 빨래 하나에 걸리는 시간은 그대로여도 빨래가 끝나는 간격은 짧아집니다. CPU의 파이프라인(pipeline)도 명령어 실행을 여러 단계로 나누고, 서로 다른 명령어의 서로 다른 단계를 동시에 진행합니다. 다만 빨래는 서로를 기다릴 일이 없지만, 명령어는 앞 명령어의 결과를 기다려야 할 때가 있다는 점이 다릅니다. 이 글에서는 CPU 데이터 경로의 실행 단계를 겹치는 방법과, 겹칠 때 생기는 문제를 다룹니다.

다섯 단계 파이프라인

명령어 실행을 인출(IF, instruction fetch), 해독과 레지스터 읽기(ID, instruction decode), 계산(EX, execute), 데이터 메모리 접근(MEM, memory), 결과 기록(WB, write back)의 다섯 단계로 나누고, 단계마다 클록 한 주기씩 걸린다고 하겠습니다. 단계와 단계 사이에는 파이프라인 레지스터(pipeline register)를 두어, 앞 단계가 만든 중간 결과를 다음 주기에 다음 단계가 쓸 수 있게 담아 둡니다. 서로 의존하지 않는 명령어 세 개를 넣으면 주기마다 각 명령어가 다음 단계로 한 칸씩 나아갑니다.

STAGES = ["IF", "ID", "EX", "MEM", "WB"]


def pipeline_cycles(instructions, stages=5, stalls=0):
    return 0 if instructions == 0 else stages + instructions - 1 + stalls


def diagram(count):
    total = pipeline_cycles(count)
    print("   " + "".join(f"{c:<4}" for c in range(1, total + 1)))
    for i in range(count):
        row = ["    "] * total
        for j, stage in enumerate(STAGES):
            row[i + j] = f"{stage:<4}"
        print(f"I{i + 1} " + "".join(row))


diagram(3)
print(pipeline_cycles(3), 20 * 10, pipeline_cycles(20) * 2.5, pipeline_cycles(20, stalls=4) * 2.5)

   1   2   3   4   5   6   7
I1 IF  ID  EX  MEM WB
I2     IF  ID  EX  MEM WB
I3         IF  ID  EX  MEM WB
7 200 60.0 70.0

맨 윗줄은 클록 주기의 번호이고, 그 아래 줄은 각 명령어가 주기마다 어느 단계에 있는지입니다. 첫 명령어는 5주기 뒤에 끝나지만, 그다음부터는 주기마다 명령어가 하나씩 끝납니다. 마지막 줄은 뒤의 계산 절에서 설명합니다. 일반적으로 k단계 파이프라인에서 서로 의존하지 않는 명령어 n개는 k + n − 1주기에 끝나는데, 첫 명령어가 파이프라인을 채우는 데 k주기가 걸리고 나머지 n − 1개가 한 주기씩 이어서 끝나기 때문입니다.

파이프라인은 명령어 하나가 끝나기까지의 시간, 곧 지연(latency)을 줄이지 않습니다. 오히려 파이프라인 레지스터를 지나는 시간이 더해져 조금 늘어납니다. 줄어드는 것은 명령어가 끝나는 간격이고, 그래서 일정한 시간에 끝내는 명령어의 수, 곧 처리량(throughput)이 늘어납니다.

명령어가 서로를 기다리는 세 가지 위험

명령어들이 늘 겹쳐 실행될 수 있는 것은 아닙니다. 다음 명령어를 다음 주기에 시작할 수 없게 만드는 상황을 위험(hazard)이라 하고, 원인에 따라 세 가지로 나눕니다.

구조 위험(structural hazard)은 두 명령어가 같은 주기에 같은 부품을 쓰려고 할 때 생깁니다. 메모리 출입구가 하나뿐이라면 한 명령어의 IF와 다른 명령어의 MEM이 같은 주기에 메모리를 쓰려고 다툽니다. 부품을 늘리거나, 명령어용과 데이터용 메모리 통로를 나누거나, 한쪽을 한 주기 늦추어 해결합니다.

데이터 위험(data hazard)은 다음 명령어가 앞 명령어의 결과를 써야 하는데 그 결과가 아직 레지스터에 기록되지 않았을 때 생깁니다. ADD R1, R2, R3 다음의 SUB R4, R1, R5는 R1이 필요한데, ADD는 WB 단계에 가서야 R1을 기록합니다. 결과를 기다리는 대신, ADD의 EX 단계가 끝나자마자 그 결과를 SUB의 EX 입력으로 바로 보내는 방법을 전달(forwarding)이라고 합니다. 하지만 LOAD처럼 MEM 단계가 끝나야 값이 준비되는 명령어 바로 뒤에서 그 값을 쓰면, 전달을 해도 값이 한 주기 늦어서 뒤 명령어를 멈추고 기다려야 합니다. 이렇게 한 주기 멈추는 것을 정지(stall)라 하고, 그 자리에 생기는 빈칸을 버블(bubble)이라고 합니다.

제어 위험(control hazard)은 분기 명령어가 어느 쪽으로 갈지 아직 정해지지 않았는데 다음 명령어를 인출해야 할 때 생깁니다. 결과가 나올 때까지 기다리거나, 어느 쪽으로 갈지 예측해 미리 인출합니다. 예측이 틀리면 잘못 가져온 명령어들을 결과를 남기기 전에 파이프라인에서 지우고 올바른 쪽부터 다시 시작하는데, 이렇게 지우는 것을 플러시(flush)라고 합니다. 정지는 명령어를 멈추어 기다리게 하는 것이고 플러시는 이미 들어온 명령어를 없애는 것이라 서로 다른 동작입니다. 정지와 전달의 시점은 다음 글에서 주기마다 추적합니다.

더 깊이: 분기 지연 슬롯이 없는 RISC-V와 정적 예측의 약속

RISC-V 규격의 개요는 기본 정수 명령어 집합이 초기 RISC 프로세서들과 매우 비슷하지만, 분기 지연 슬롯(branch delay slot)이 없다는 점이 다르다고 소개합니다. 분기 지연 슬롯은 분기 바로 다음 자리의 명령어를 분기가 어느 쪽으로 가든 실행하도록 ISA가 정해 둔 자리입니다. RISC-V의 기본 명령어 규격은 제어 이동 명령어에 아키텍처에서 보이는 지연 슬롯이 없다고 못 박아, 제어 위험을 어떻게 처리할지를 ISA가 아닌 구현에 맡깁니다.

대신 같은 규격은 소프트웨어가 기대해도 되는 예측 방향을 적어 둡니다. 소프트웨어는 자주 지나가는 경로를 분기 없이 이어지는 쪽에 두고, 처음 만나는 분기라면 뒤로 가는 분기는 간다고, 앞으로 가는 분기는 가지 않는다고 예측된다고 가정하라는 것입니다. 반복문의 끝에서 처음으로 되돌아가는 분기가 뒤로 가는 분기이므로, 반복이 이어지는 쪽이 맞는 예측이 됩니다. 또 무조건 이동에는 언제나 참인 조건 분기 대신 jal을 쓰라고 권하는데, 그래야 조건 분기의 예측 표를 어지럽히지 않기 때문입니다.

시간을 계산한다

파이프라인이 없는 CPU에서 명령어 하나에 10 ns가 걸리고, 같은 일을 다섯 단계로 나눈 파이프라인의 클록 주기가 2.5 ns라고 합시다. 서로 의존하지 않는 명령어 20개는 파이프라인 없이 20 × 10 = 200 ns가 걸리고, 파이프라인으로는 (5 + 20 − 1) × 2.5 = 60 ns가 걸립니다. 앞 코드의 마지막 출력 줄이 표의 7주기와 이 두 시간, 그리고 정지가 모두 4주기 생겼을 때의 70 ns입니다.

속도는 200 / 60, 약 3.33배 빨라졌는데, 단계가 다섯이라고 5배가 되지는 않습니다. 파이프라인을 채우는 처음 몇 주기 동안은 모든 단계가 일하지 않고, 이 예에서는 단계를 고르게 나누었다고 했지만 실제로는 가장 느린 단계가 클록 주기를 정하며, 파이프라인 레지스터를 지나는 시간도 더해집니다. 여기에 위험 때문에 생기는 정지가 더해지면 속도는 더 떨어집니다.

정리

• 파이프라인은 명령어 실행을 IF, ID, EX, MEM, WB 같은 단계로 나누어 서로 다른 명령어의 단계를 동시에 진행하며, 단계 사이에 파이프라인 레지스터를 둡니다.
• k단계 파이프라인에서 서로 의존하지 않는 명령어 n개는 k + n − 1주기가 걸립니다.
• 파이프라인은 명령어 하나의 지연을 줄이지 않고, 명령어가 끝나는 간격을 줄여 처리량을 늘립니다.
• 구조 위험은 부품이 겹칠 때, 데이터 위험은 앞 결과가 아직 없을 때, 제어 위험은 분기 결과가 정해지지 않았을 때 생기며, 전달, 정지, 분기 예측과 플러시로 다룹니다.
• 실제 속도 향상은 채우는 시간, 가장 느린 단계, 레지스터를 지나는 시간, 정지 때문에 단계 수보다 작습니다.

연습 문제

1. 시간과 간격

4단계 파이프라인에 명령어 8개를 넣고 클록 주기는 3 ns입니다. 정지가 모두 2주기 생겼다면 전체 시간은 얼마인가요? 명령어 하나의 지연과, 파이프라인이 찬 뒤 명령어가 끝나는 간격도 구하세요. LOAD R1 바로 뒤에 ADD R2, R1, R3이 있으면 정지가 없다고 말할 수 있나요?

2. 고르지 않은 단계

다섯 단계가 각각 2, 3, 2, 2, 1 ns 걸리고 파이프라인 레지스터를 지날 때마다 0.2 ns가 더해집니다. 파이프라인이 없는 CPU가 명령어 하나에 10 ns를 쓴다면, 명령어가 아주 많을 때 파이프라인은 약 몇 배 빠른가요?

3. 분기 예측이 틀리면

분기 결과가 EX 단계에서 정해지고, CPU는 분기가 일어나지 않는다고 예측해 다음 명령어를 계속 인출합니다. 분기가 실제로 일어나면 몇 주기를 잃나요? 명령어의 20%가 실제로 일어나는 분기라면 명령어당 평균 주기 수는 얼마인가요?

파이프라인 문제는 주기 번호를 가로로, 명령어를 세로로 적은 표를 먼저 그리면 어느 명령어가 언제 무엇을 기다리는지 쉽게 보입니다. 다음 글 load-use 정지와 전달 시간표에서는 LOAD 바로 뒤에서 그 값을 쓰는 경우를 주기마다 끝까지 추적합니다.