파이프라인과 병렬 처리

같은 클럭 속도에서도 여러 일을 겹쳐서 처리하면 처리량이 늘어난다. 파이프라인은 CPU 내부에서 명령어 단계를 겹치는 기법이고, 벡터·배열 처리는 많은 데이터를 한꺼번에 다루는 기법이며, 다중 프로세서는 프로세서 자체를 여러 개 묶는 구조다.

병렬 처리의 분류 (Flynn's Taxonomy)

동시에 처리하는 명령어 흐름과 데이터 흐름의 수로 나눈다.

분류	명령어	데이터	예
SISD	1	1	전통적인 단일 프로세서(내부적으로 파이프라인 사용)
SIMD	1	다수	하나의 제어 장치가 여러 처리 장치를 지휘: 벡터 연산, GPU
MISD	다수	1	주로 이론적인 분류
MIMD	다수	다수	멀티프로세서, 멀티코어, 분산 시스템(아래 「다중 프로세서」)

구현 관점으로는 파이프라인 처리, 벡터 처리, 배열 프로세서로 나눠 볼 수 있다.

파이프라인의 원리

작업을 여러 세그먼트(단계)로 나누고, 각 단계가 서로 다른 데이터를 동시에 처리하게 한다. 세그먼트 사이에는 중간 결과를 담는 레지스터가 있다. 세탁기 → 건조기 → 개기를 여러 빨래에 겹쳐서 돌리는 것과 같다.

flowchart TB
  subgraph hrow[" "]
    direction LR
    h["시간 →"] ~~~ t1["1"] ~~~ t2["2"] ~~~ t3["3"] ~~~ t4["4"] ~~~ t5["5"] ~~~ t6["6"]
  end
  subgraph row1[" "]
    direction LR
    i1["명령 1"] ~~~ a1["S1"] ~~~ a2["S2"] ~~~ a3["S3"] ~~~ a4["S4"] ~~~ s1[" "] ~~~ s2[" "]
  end
  subgraph row2[" "]
    direction LR
    i2["명령 2"] ~~~ s3[" "] ~~~ b2["S1"] ~~~ b3["S2"] ~~~ b4["S3"] ~~~ b5["S4"] ~~~ s4[" "]
  end
  subgraph row3[" "]
    direction LR
    i3["명령 3"] ~~~ s5[" "] ~~~ s6[" "] ~~~ c3["S1"] ~~~ c4["S2"] ~~~ c5["S3"] ~~~ c6["S4"]
  end
  hrow ~~~ row1 ~~~ row2 ~~~ row3

파이프라인이 한 번 채워지면 매 클럭마다 결과 하나가 나온다.
이론상 최대 속도 향상은 세그먼트 수(k)와 같다.
실제로는 단계마다 걸리는 시간이 달라 클럭을 가장 느린 단계에 맞춰야 하고, 아래의 해저드 때문에 이론치에 못 미친다.

속도 향상 계산

단계가 k개이고 각 단계가 한 클럭이면, 명령어 N개를 실행하는 데 걸리는 클럭 수는 다음과 같다.

파이프라인 없음:  T1 = k × N
파이프라인:       Tk = k + (N − 1)     첫 명령어가 k클럭, 나머지는 한 클럭에 하나씩
속도 향상:        Sp = T1 / Tk = kN / (k + N − 1)

4단계, 클럭 1GHz(단계당 1ns)로 명령어 10개를 돌리면 Tk = 4 + 9 = 13ns, Sp = 40 / 13 ≈ 3.08배다. N이 100이면 3.88배, 1000이면 3.988배로 N이 커질수록 k(= 4)에 다가간다. 파이프라인을 채우는 첫 k − 1클럭이 고정 비용이라, 짧은 명령어 열에서는 이득이 작다.

이론치에 못 미치는 이유는 해저드 말고도 있다.

단계 시간의 불균형: 클럭은 가장 오래 걸리는 단계에 맞춘다. 인출·실행 2단계 파이프라인이 두 단계 시간이 다르면 2배가 안 나오므로, 단계를 잘게 나눠 시간을 고르게 맞춘다. 단계를 늘리면 k가 커져 이론적 속도 향상도 커진다.
모든 명령어가 모든 단계를 쓰지는 않는다: 오퍼랜드 인출이 필요 없는 명령어도 하드웨어를 단순하게 하려고 그 단계를 빈 채로 통과한다.

산술 파이프라인

부동 소수점 덧셈을 네 단계로 나눌 수 있다.

지수 비교
가수 정렬(지수를 맞추기 위해 시프트)
가수 덧셈/뺄셈
결과 정규화

명령어 파이프라인

명령어 사이클(fetch → decode → 유효 주소 계산 → 피연산자 fetch → 실행 → 저장)을 겹쳐서 수행한다. 4단계 예:

단계	하는 일
FI	명령어 fetch
DA	디코드 + 유효 주소 계산
FO	피연산자 fetch
EX	실행

단계를 몇 개로 나누는지는 설계와 교재마다 다르다. 인출·실행 2단계, 인출·해석·실행·저장 4단계, 고전 RISC의 5단계(인출·해독·실행·메모리 접근·쓰기)가 흔한 예다. 파이프라인이 없으면 명령어 하나를 끝까지 마친 뒤에야 다음 명령어를 인출하므로, 명령어가 많을수록 걸리는 시간이 파이프라인을 쓸 때의 단계 수 배에 가까워진다.

해저드: 파이프라인이 멈추는 이유

종류	원인	대표적 해결책
자원 충돌	두 단계가 동시에 메모리 등 같은 자원을 사용. 예: IF 단계와 OF 단계가 같은 클럭에 메모리를 읽으려 함	명령어 메모리와 데이터 메모리(캐시) 분리
데이터 의존성	앞 명령어의 결과가 아직 나오지 않았는데 다음 명령어가 그 값을 필요로 함	하드웨어 인터락, 오퍼랜드 포워딩, 지연 로드
분기	분기로 PC가 바뀌면 미리 가져온 명령어가 무효	분기 예측, BTB, 루프 버퍼, 지연 분기

책에 따라 자원 충돌은 구조적 위험(자원 위험), 데이터 의존성은 데이터 위험, 분기는 제어 위험이라고도 부른다.

데이터 의존성 해결

I1: R1 ← R2 + R3
I2: R4 ← R1 + R5    ; I1이 R1을 써야 I2가 올바른 값을 읽는다

I2를 I1 바로 뒤에 겹쳐 넣으면 I2가 R1을 읽는 시점에 I1의 결과가 아직 없다. 이런 의존 관계가 데이터 해저드다.

하드웨어 인터락: 의존성을 감지하면 값이 준비될 때까지 뒤 명령어를 지연시킨다(stall).
오퍼랜드 포워딩: 결과가 레지스터에 기록되기 전에 별도 경로로 다음 단계에 바로 전달한다.
지연 로드: 컴파일러가 의존성을 찾아 사이에 NOP을 넣거나 명령어 순서를 바꾼다.

분기 처리

조건 분기가 실제로 일어나면 그 뒤에 미리 인출해 처리하던 명령어들을 모두 버려야 한다. 이 손실을 줄이는 방법은 다음과 같다.

분기 목적지 선인출: 조건 분기를 알아보면 바로 다음 명령어와 분기 목적지 명령어를 둘 다 인출해 두고, 조건이 판명되면 맞는 쪽을 실행한다.
BTB(Branch Target Buffer): 최근 실행한 분기 명령어와 그 목적지 명령어들을 저장한 연관 메모리. 같은 분기를 다시 만나면 파이프라인을 멈추지 않고 이어 간다.
루프 버퍼: 가장 최근에 인출한 명령어 n개를 fetch 단계의 작은 고속 버퍼에 순서대로 담아, 작은 루프는 메모리 접근 없이 반복한다.
분기 예측: 분기 방향을 예측해 그 경로의 명령어를 미리 읽는다. 최근 분기 결과를 기록한 분기 역사 표(branch history table)를 참고하는 확률적 방법이며, 맞으면 손실이 없다.
지연 분기: 컴파일러가 명령어 위치를 재배치한다(아래 「RISC 파이프라인」).

슈퍼스칼라와 비순차 실행

오늘날 CPU는 파이프라인을 여러 개 두어 매 클럭 여러 명령어를 내보내고(슈퍼스칼라), 의존성이 풀린 명령어부터 먼저 실행한다(비순차 실행). 구조와 동작은 현대 CPU의 마이크로아키텍처에 있다.

파이프라인을 m개 둔 m-way 슈퍼스칼라는 매 클럭 명령어 m개를 동시에 인출·실행한다. k단계 파이프라인 m개로 명령어 N개를 실행하면 첫 묶음에 k클럭, 나머지 (N − m)개는 클럭마다 m개씩 끝난다.

T(m) = k + (N − m) / m
Sp   = (k + N − 1) / T(m)      → N이 커지면 m에 다가간다 (단일 파이프라인 대비)

실제 이득이 m보다 작은(Sp < m) 이유는 두 가지다. 명령어끼리 데이터 의존 관계가 있으면 동시에 내보낼 수 없고, 여러 명령어가 레지스터·캐시·메모리 같은 하드웨어를 놓고 다투면 한쪽이 기다린다. 앞의 것은 명령어 실행 순서를 바꿔(아래 비순차 실행, 컴파일러 스케줄링), 뒤의 것은 실행 유닛·포트 같은 하드웨어를 여러 벌 두어 줄인다.

비순차 실행(OoOE, Out-of-Order Execution)은 의존성이 없는 명령어끼리만 순서를 바꾼다. 바꾼 뒤의 결과가 프로그램 순서대로 실행한 결과와 같아야 하기 때문이다.

1: M[100] ← 1
2: M[101] ← 2
3: M[102] ← M[100] + M[101]   ; 1·2의 결과가 필요
4: M[103] ← M[102] + 1        ; 3의 결과가 필요
5: M[150] ← 1                 ; 어디에도 의존하지 않음
6: M[151] ← 2                 ; 어디에도 의존하지 않음

순서대로 실행하면 3은 1·2가 끝날 때까지 기다리느라 파이프라인이 빈다. 5·6을 3 앞으로 당기면 그동안 1·2의 결과가 정해져 3이 멈추지 않는다. 반대로 1과 3, 3과 4처럼 앞 명령어의 결과를 쓰는 쌍은 바꿀 수 없다.

RISC 파이프라인

명령어가 단순하고 대부분 한 사이클에 끝나므로 단계 수가 적은 파이프라인을 깔끔하게 구성할 수 있다. 피연산자가 레지스터에 있어 메모리에서 피연산자를 가져오는 단계가 필요 없다. 3단계 예: I(명령어 fetch) → A(ALU 연산) → E(결과 저장/메모리 접근).

RISC는 해저드를 하드웨어 대신 컴파일러로 해결하는 경우가 많다.

지연 로드: load 바로 다음에 그 값을 쓰는 명령어가 오면 NOP을 넣어 한 사이클을 비운다.
지연 분기: 분기 결과에 영향을 주지 않는 앞쪽 명령어를 분기 직후의 슬롯으로 옮겨 빈 사이클을 유용하게 채운다. 옮길 것이 없으면 NOP을 넣는다.

벡터 처리

벡터(1차원 배열)나 행렬을 다루는 과학 계산에서는 같은 연산을 대량의 원소에 반복한다.

; 스칼라 방식: 100번 반복하며 매번 명령어 fetch/decode
for i in 0..99: C[i] = A[i] + B[i]
 
; 벡터 방식: 명령어 하나로 전체 처리
C(0:99) = A(0:99) + B(0:99)

명령어 fetch·decode 오버헤드가 사라지고 연산을 파이프라인으로 흘려보낼 수 있어, 행렬 곱셈처럼 곱셈·덧셈이 많은 작업에서 특히 효과가 크다.

메모리 인터리빙

파이프라인과 벡터 프로세서는 메모리에 동시에 여러 번 접근하려 한다. 메모리를 여러 모듈로 나누고 연속된 주소를 모듈에 번갈아 배치하면 여러 접근을 동시에 처리할 수 있다.

모듈 3개일 때
주소 0 → 모듈 0   주소 3 → 모듈 0
주소 1 → 모듈 1   주소 4 → 모듈 1
주소 2 → 모듈 2   주소 5 → 모듈 2

각 모듈은 자체 주소 레지스터와 데이터 레지스터를 가지고 공통 버스에 연결된다.

배열 프로세서

부가 배열 프로세서: 호스트 컴퓨터에 붙여 수치 계산만 전담하게 하는 보조 프로세서.
SIMD 배열 프로세서: 여러 처리 장치가 같은 명령을 동시에 수행. 범용성이 낮아 전용 장비로는 거의 쓰이지 않지만, 그 개념은 오늘날 CPU의 SIMD 명령어와 GPU로 이어졌다.

다중 프로세서

프로세서 여러 개가 프로그램 여러 개, 또는 한 프로그램을 나눈 조각들을 동시에 처리하는 구조다. 작고 싼 프로세서를 많이 만들 수 있게 된 반도체 기술이 전제였고, 대신 세 가지 비용이 생겼다. 문제를 어떻게 쪼갤지(분할), 조각끼리 데이터를 어떻게 주고받을지(프로세서 간 통신), 공유 자원을 어떻게 지킬지(상호 배제)다.

병렬 처리의 단위

단위	나누는 기준	예	조각 사이 통신
작업(job)	서로 무관한 프로그램	빌드 서버가 여러 저장소를 동시에 빌드	거의 없음
태스크(task)	한 작업을 기능별로 나눈 부분	로봇의 팔·다리·센서 제어를 따로	필요함
스레드(thread)	동시에 실행 가능한 가장 작은 독립 흐름	웹 서버의 요청 처리 스레드	공유 메모리
명령어(ILP)	의존성이 없는 명령어	슈퍼스칼라 CPU가 한 사이클에 여러 명령 실행	하드웨어가 처리

아래로 갈수록 조각이 작아지고, 병렬화를 하드웨어가 더 많이 떠맡는다. 명령어 수준 병렬성은 현대 CPU의 마이크로아키텍처에 있다.

MIMD의 두 갈래

위 Flynn 분류에서 여러 프로세서가 각자 다른 명령과 데이터를 처리하는 MIMD는, 프로세서끼리 얼마나 밀접하게 붙어 있는지로 다시 나뉜다.

구분	밀결합(tightly coupled)	소결합(loosely coupled)
메모리	모두가 하나의 주기억장치를 공유	프로세서마다 자기 지역 메모리
통신	공유 메모리에 읽고 쓰기	메시지 전송(message passing)
이름	다중 프로세서 시스템	다중 컴퓨터 시스템

메모리 접근 모델

모델	구조	접근 시간	한계
UMA	모든 프로세서가 상호연결망 하나로 주기억장치를 공유	어느 주소든 같다	공유 자원 경합 때문에 규모를 키우기 어렵다. 공유 버스면 수십 개가 한계
NUMA	UMA 묶음 여러 개를 상호연결망으로 잇고, 전체를 한 주소 공간으로 본다(분산 공유 메모리)	내 노드 메모리는 빠르고, 다른 노드 메모리는 느리다	데이터를 어느 노드에 두느냐가 성능을 좌우한다
NORMA	프로세서가 다른 노드의 메모리를 직접 읽을 수 없다(분산 메모리)	원격 데이터는 메시지로 받아 와야 한다	프로그래머가 통신을 직접 짠다

2소켓 이상 서버는 NUMA다. 스레드와 그 스레드가 쓰는 메모리를 같은 노드에 두어야 하는 이유는 메모리 계층 구조의 NUMA 절에 있다.

시스템 구성 방법

구성	특징	지금의 예
SMP (대칭형 다중 프로세서)	비슷한 프로세서 수십 개 이하가 메모리와 I/O를 모두 공유(shared-everything). OS가 하나이고, 어느 프로세서든 OS 코드를 실행하며 권한이 같다	멀티코어 PC·스마트폰
MPP (대규모 병렬 프로세서)	노드 수백~수천 개가 아무것도 공유하지 않는다(shared-nothing). 노드마다 OS가 있고 메시지로 통신한다	전용 슈퍼컴퓨터
CC-NUMA	NUMA 노드들의 캐시와 메모리 사이에 일관성을 하드웨어가 유지한다. SMP용 소프트웨어를 고치지 않고 더 크게 키울 수 있다	다중 소켓 x86 서버
분산 시스템	독립된 컴퓨터를 일반 네트워크로 잇고, 필요할 때만 통신한다	마이크로서비스, 분산 DB
클러스터	PC나 서버를 고속 LAN으로 묶어 하나의 시스템처럼 보이게 한다(single system image). 싸게 만들 수 있고, 한 대가 고장 나도 다른 노드가 대신해 가용성이 높다	HPC 클러스터, Kubernetes 클러스터

SMP에서 프로세서마다 캐시를 따로 가지므로, 같은 주소의 사본들을 맞추는 캐시 일관성 프로토콜(MESI)이 필요하다. 이것이 거짓 공유 같은 성능 문제로 이어지는 과정은 캐시를 고려한 코드에, SMP에서 OS가 작업을 나누는 방법은 프로세스 상태와 CPU 스케줄링에 있다.

공유 메모리 시스템의 상호연결

구조	원리	장점	단점
공유 버스	모든 프로세서와 메모리가 버스 하나에 붙는다	하드웨어가 가장 단순하다	버스 경합으로 지연이 커진다. 캐시로 버스 사용을 줄여 보완
다중·계층 버스	버스를 여러 개 두거나 용도별로 층을 나눈다	경합이 줄어든다	버스 사이 연결이 복잡해진다
크로스바 스위치	프로세서 N개와 메모리 M개의 모든 교차점에 스위치를 둔다	서로 다른 메모리를 향한 요청은 동시에 처리된다(완전 연결)	스위치가 N×M개라 비싸다
다단계 상호연결망(MIN)	작은 스위치(2×2)를 여러 단으로 엮는다. 예: 오메가 네트워크는 log₂N단	비용과 성능이 버스와 크로스바의 중간	경로가 겹치면 막힌다

공유 메모리 시스템은 데이터 교환 장치를 따로 두지 않아도 되고, 실행 중에 일을 프로세서들에 고르게 나눠 이용률을 높이기 쉽다. 하지만 프로세서가 늘면 메모리로 가는 통로에서 경합이 커져, 프로세서 수에 비례해 빨라지지 않는다. 버스 중재 방식은 입출력 구조와 시스템 버스에 있다.

분산 메모리 시스템의 토폴로지

노드마다 메모리를 가지면 공유 자원 경합은 줄지만, 통신 프로토콜 때문에 지연이 생긴다. 노드를 어떻게 잇느냐가 통신 거리를 정한다. 비교 기준은 두 가지다.

네트워크 지름: 가장 멀리 떨어진 두 노드 사이의 링크 수. 최악의 통신 거리다.
차수(degree): 노드 하나에 붙은 링크 수. 클수록 지름은 줄지만 배선이 늘어난다.

토폴로지	구조	지름 (노드 N개)	비고
선형 배열	일렬로 연결	N − 1	가장 길다. 버스보다는 동시 통신이 많다
링	양 끝을 이은 선형 배열	양방향 ⌊N/2⌋, 단방향 N − 1	링크를 더한 코달 링(chordal ring)은 지름이 줄어든다
이진 트리	층 k개, N = 2ᵏ − 1	2(k − 1)	위층으로 갈수록 통신이 몰려 병목
팻 트리	위층으로 갈수록 링크를 굵게(많이)	트리와 같음	트리의 병목을 해결. 데이터센터 네트워크의 Clos 구조로 이어진다
2차원 메시	n×n 격자 (N = n²)	2(n − 1)	확장이 쉽다
토러스	메시의 행·열 끝을 이음	2⌊n/2⌋	메시보다 지름이 절반 정도
하이퍼큐브	N = 2ᵐ개 노드, 주소가 한 비트만 다른 노드끼리 연결	log₂N	차수도 log₂N

하이퍼큐브의 이웃은 주소에서 비트 하나를 뒤집어 구한다. 3차원(노드 8개)이라면 다음과 같다.

노드 000의 이웃: 001, 010, 100      (비트 0, 1, 2를 각각 뒤집음)
000 → 111 경로: 000 → 001 → 011 → 111   (다른 비트 수 = 3 = 지름)

두 노드 사이 거리는 주소를 XOR한 결과에서 1인 비트 수(해밍 거리)와 같다.

핵심 정리

파이프라인은 지연 시간이 아니라 처리량을 늘린다. 명령어 N개에 k + N − 1클럭이 걸려, N이 클수록 k배에 다가간다.
해저드는 자원·데이터·분기 세 가지이며, 하드웨어(포워딩, 예측)와 컴파일러(지연 로드·분기)로 완화한다.
슈퍼스칼라는 파이프라인을 여러 개 두고, 비순차 실행은 의존성 없는 명령어를 먼저 처리해 멈춤을 줄인다.
대량 데이터에는 벡터 처리와 메모리 인터리빙이 효과적이다.
다중 프로세서는 밀결합(공유 메모리, UMA·NUMA)과 소결합(메시지 전송, NORMA)으로 나뉜다. 멀티코어 PC는 SMP, 다중 소켓 서버는 CC-NUMA, 슈퍼컴퓨터와 서버 팜은 MPP·클러스터다.
상호연결은 비용과 동시성의 맞바꿈이고(버스 < MIN < 크로스바), 분산 메모리 토폴로지는 네트워크 지름과 차수로 비교한다.

버그 제보