암달의 법칙으로 보는 병렬 처리 성능의 한계
암달의 법칙의 공식과 병렬화 한계, 오버헤드 요인, 구스타프슨의 법칙과의 관점 차이를 정리한다.
2026-08-15 · 최초 발행 2025-12-28
병렬화의 상한은 순차 구간에서 결정된다
암달의 법칙(Amdahl's Law)은 병렬 컴퓨팅에서 성능 향상이 어디서 멈추는지를 설명한다. 1967년 컴퓨터 과학자 진 암달(Gene Amdahl)이 제시한 이 법칙의 핵심은 단순하다. 전체 작업에 순차적으로만 처리할 수 있는 부분이 남아 있다면, 프로세서를 계속 추가해도 성능은 무한히 빨라지지 않는다.
암달은 IBM 시스템 설계자로 IBM System/360 설계를 주도했고, 이후 Amdahl Corporation을 창업했다. 이 법칙은 1960년대 병렬 처리에 대한 기대 속에서 무한한 병렬화라는 생각에 제동을 걸며 순차 부분의 중요성을 드러냈다.
멀티코어 환경에서 이 원리는 시스템 설계와 성능 최적화의 기준이 된다. 병렬 처리 비율만 볼 것이 아니라, 병렬화되지 않는 구간을 얼마나 줄일 수 있는지 함께 봐야 한다.
가속비 계산식
암달의 법칙은 다음과 같이 쓸 수 있다.
형태 1
Speedup = 1 / [(1-t) + (t/n)]
- t: 병렬화 가능한 부분의 비율
- n: 프로세서 개수
- (1-t): 순차적으로 처리해야 하는 부분의 비율
형태 2
Speedup = 1 / [(p/n) + s]
- p: 병렬화 강도(parallelization intensity)
- n: 프로세서 개수
- s: 순차 처리 비율(serial fraction)
프로그램에서 병렬 처리 가능한 비율을 P, 프로세서 또는 코어 수를 N이라 하면 성능 향상은 다음과 같이 계산한다.
Speedup = 1 / ((1 - P) + P/N)
Speedup: 성능 향상 배수
P: 병렬화 가능한 비율 (0 ≤ P ≤ 1)
N: 프로세서(코어) 수
(1 - P): 순차 실행 비율
분자 1은 이상적인 전체 작업 시간을 뜻하고, 분모는 실제 작업 시간이다. (1-t) 또는 s는 프로세서를 늘려도 줄어들지 않는 순차 구간이며, (t/n) 또는 (p/n)은 병렬화로 단축할 수 있는 구간이다. 코어 수가 무한히 늘어나는 상황에서는 병렬 구간의 실행 시간이 0에 가까워지고, 순차 구간만 남는다.
Speedup_max = 1 / (1 - P)
원래 실행 시간을 T로 두면 순차 구간은 T × (1 - P), 병렬 구간은 T × P다. 병렬 처리 뒤의 실행 시간은 다음처럼 표현된다.
T_parallel = T × (1 - P) + (T × P) / N
= T × ((1 - P) + P/N)
따라서 성능 향상은 원래 시간과 병렬화 후 시간의 비율이 된다.
Speedup = T / T_parallel
= T / (T × ((1 - P) + P/N))
= 1 / ((1 - P) + P/N)
대규모 병렬 컴퓨터 논의에서 나온 문제 제기
암달의 법칙은 1967년 AFIPS 봄 합동 컴퓨터 컨퍼런스에서 발표됐다. IBM의 대규모 병렬 컴퓨터 개발 계획을 둘러싼 논의 속에서, 프로세서 수를 무한히 늘려도 성능이 무한히 향상되지는 않는다는 현실적 관점을 제시했다.
이 관점은 하드웨어 확장만으로 성능 문제를 해결하려는 접근에 제약을 만들었다. 병렬 처리의 한계를 인식하게 했고, 하드웨어와 소프트웨어를 함께 최적화하는 시스템 설계, 그리고 최소 비용으로 최적 성능을 얻기 위한 판단의 수학적 근거가 됐다.
프로세서 수에 따른 작업 시간
전체 작업 시간이 100이고, 그중 40은 순차 처리만 가능하며 60은 병렬화할 수 있다고 하자. 4개 CPU를 사용하면 순차 부분은 그대로 40이지만, 병렬 부분은 60 ÷ 4 = 15가 된다. 총 시간은 55이고 가속비는 100 ÷ 55 = 1.82x다. CPU 수를 무한대로 늘린 경우에도 순차 부분 40은 남으므로 이론적 최대는 100 ÷ 40 = 2.5x다.
전체 작업 중 60%가 병렬화 가능한 경우의 계산은 다음과 같다.
- 1개 CPU: Speedup = 1.0x (기준)
- 2개 CPU: Speedup = 1 / [0.4 + (0.6/2)] = 1 / 0.7 = 1.43x
- 4개 CPU: Speedup = 1 / [0.4 + (0.6/4)] = 1 / 0.55 = 1.82x
- 8개 CPU: Speedup = 1 / [0.4 + (0.6/8)] = 1 / 0.475 = 2.11x
- 무한대 CPU: Speedup = 1 / 0.4 = 2.5x (이론적 최대)
4개의 CPU를 사용하면 평균적으로 약 2.5배의 성능 향상을 기대할 수 있습니다.
병렬화 비율이 50%이고 듀얼코어를 사용한다면 계산 결과는 1.33배다.
Speedup = 1 / ((1 - 0.5) + 0.5/2)
= 1 / (0.5 + 0.25)
= 1 / 0.75
= 1.33배
병렬화 비율이 90%, 코어 수가 10이면 5.26배가 된다.
Speedup = 1 / ((1 - 0.9) + 0.9/10)
= 1 / (0.1 + 0.09)
= 1 / 0.19
= 5.26배
같은 90% 병렬화에서 코어 수를 무한히 늘려도 최대 성능 향상은 10배다.
Speedup_max = 1 / (1 - 0.9)
= 1 / 0.1
= 10배 (최대)
순차 비율과 코어 효율의 관계
병렬화 비율이 90%일 때 최대 성능 향상은 10배지만, 95%로 높아지면 최대 20배가 된다. 5% 차이가 2배의 성능 차이로 이어진다. 95%와 99%를 비교하면 각각 최대 20배와 100배이며, 4% 차이가 5배 차이를 만든다.
| 병렬화 비율 (P) | 순차 비율 (1-P) | 최대 Speedup (N→∞) |
|---|---|---|
| 50% | 50% | 2배 |
| 75% | 25% | 4배 |
| 90% | 10% | 10배 |
| 95% | 5% | 20배 |
| 99% | 1% | 100배 |
| 99.9% | 0.1% | 1,000배 |
P = 0.9인 작업은 프로세서 수가 늘수록 성능은 계속 올라가지만, 코어당 효율은 낮아진다.
| 프로세서 수 (N) | Speedup | 효율 (Speedup/N) |
|---|---|---|
| 1 | 1.00 | 100% |
| 2 | 1.82 | 91% |
| 4 | 3.08 | 77% |
| 8 | 4.71 | 59% |
| 16 | 6.40 | 40% |
| 32 | 7.80 | 24% |
| ∞ | 10.00 | 0% |
특히 16코어 이상에서는 효율이 급격히 낮아진다. 무한 코어에서도 순차 부분은 남으므로 효율은 0%가 된다.
P = 0.75인 소프트웨어를 멀티코어에서 실행할 경우, 듀얼코어는 이상적인 2배 대신 1.6배와 80% 효율을 보인다. 쿼드코어에서는 이상적인 4배 대신 2.3배와 57.5%, 옥타코어에서는 이상적인 8배 대신 3.2배와 40% 효율이다. 코어 수 증가만으로는 비례한 성능 향상을 기대하기 어렵고, 소프트웨어의 병렬화 최적화가 함께 필요하다.
코어 증가만으로 해결되지 않는 이유
실제 시스템에서는 암달의 법칙이 보여주는 순차 구간 외에도 여러 오버헤드가 발생한다. 여러 코어가 동일 캐시 라인에 접근할 때는 캐시 충돌이 생길 수 있고, 공유 메모리에 동시에 접근하면 대기가 발생한다. 제한된 버스 대역폭을 여러 프로세서가 공유하는 문제도 있다. 스레드 사이의 데이터 일관성을 유지하기 위한 동기화 작업 역시 비용으로 남는다.
암달의 법칙은 문제 크기와 순차 부분 비율이 고정돼 있다고 가정한다. 또한 기본 공식은 병렬 처리의 오버헤드를 반영하지 않는다. 실제 시스템에는 쓰레드 생성·종료 비용, 컨텍스트 스위칭, Lock·Barrier 동기화, 분산 시스템의 통신 비용, 캐시 일관성 유지 비용이 들어간다. 이를 포함하면 식은 다음처럼 확장할 수 있다.
Speedup = 1 / ((1 - P) + P/N + O(N))
O(N): 오버헤드 함수
작업 부하가 불균형하면 일부 코어는 유휴 상태가 될 수 있다. 메모리 대역폭과 캐시 경합, 디스크 및 네트워크 I/O 대기도 별도의 병목으로 남는다. 이 때문에 병렬화 효율은 프로세서 수에 비례해 늘어나지 않는다. 어느 시점부터는 코어를 추가할수록 투자 효과가 작아지는 수익 체감 구간에 들어간다.
설계에서는 순차 구간과 비용을 함께 본다
시스템을 설계할 때는 병렬화 가능한 비율을 높이는 한편, 병렬화할 수 없는 부분의 실행 시간을 줄여야 한다. 프로파일링으로 실행 시간을 분석해 순차 구간과 Hotspot을 먼저 식별하고, 코어 수는 암달의 법칙으로 효율을 계산한 뒤 비용 대비 효과를 평가해 결정한다. 도구로는 Linux의 gprof, perf, Intel VTune, Visual Studio Profiler가 있다.
순차 알고리즘을 병렬 알고리즘으로 바꾸고, 공유 데이터를 줄이며, Lock-free 자료구조나 Lock Granularity 조정, Read-Write Lock을 검토하는 방식으로 병렬화 가능 영역을 넓힐 수 있다. 순차 코드 자체의 최적화도 우선순위가 높다. 알고리즘을 O(n²)에서 O(n log n)으로 개선하고, 캐시 친화적인 코드를 작성하거나 컴파일러 최적화 옵션 -O3를 적용할 수 있다.
초기 몇 개의 코어를 추가할 때는 효과가 크지만, 일정 수준을 넘으면 추가 투자 효과가 감소한다. 따라서 하드웨어를 확장하기 전에 소프트웨어 최적화를 검토할 필요가 있다. 총소유비용(TCO)은 장비 가격뿐 아니라 전력, 냉각, 관리 비용까지 포함해 평가한다.
프로세서 속도 증가에 의존하던 방식은 소프트웨어, 알고리즘, 아키텍처를 함께 다루는 방향으로 옮겨왔다. 멀티스레딩·비동기 처리·분산 컴퓨팅은 병렬 프로그래밍의 수단이며, GPU·TPU·FPGA 같은 특화 하드웨어는 특정 작업에 맞춘 선택지다. CPU와 GPU를 함께 쓰는 이종 컴퓨팅에서는 작업별로 적합한 장치를 선택한다.
알고리즘의 시간 복잡도를 낮추고, 캐시 친화적인 데이터 접근 패턴을 설계하며, 작업 단위를 적절히 나누는 일은 병렬화 자체만큼 중요하다. I/O 대기 시간에는 다른 작업을 수행하도록 비동기 처리를 적용할 수 있다.
데이터와 태스크를 나누는 방식
데이터 병렬성은 같은 연산을 서로 다른 데이터에 적용하는 방식이며, SIMD(Single Instruction Multiple Data), OpenMP, AVX·SSE, CUDA, OpenCL이 활용 대상이다.
#pragma omp parallel for
for (int i = 0; i < N; i++) {
result[i] = compute(data[i]);
}태스크 병렬성은 서로 다른 작업을 동시에 실행하는 방식으로, 파이프라인과 Producer-Consumer 구조에 적용할 수 있다. 쓰레드 풀, 비동기 I/O, 태스크 큐가 대표적인 기법이다.
// 쓰레드 1: 데이터 읽기
// 쓰레드 2: 데이터 처리
// 쓰레드 3: 결과 쓰기알고리즘별 병렬성도 다르다. 행렬 곱셈은 P ≈ 0.99로 높은 병렬성을 가질 수 있어 멀티코어 효과가 크다. 병합 정렬은 P ≈ 0.7~0.8이며, 퀵 정렬에는 순차 부분이 있다. 데이터베이스에서는 테이블 스캔을 병렬화할 수 있지만 집계 연산에는 순차 부분이 존재한다.
클라우드 환경에서도 같은 관점이 적용된다. MapReduce에서는 Map 단계의 병렬성이 높지만 Reduce 단계가 순차 병목이 될 수 있다. 분산 학습에서는 데이터 병렬화가 효과적이지만 모델 동기화가 순차 오버헤드가 된다.
고정된 문제와 확장되는 문제의 관점 차이
암달의 법칙은 고정된 크기의 문제를 얼마나 빠르게 풀 수 있는지에 초점을 둔다. 반면 구스타프슨의 법칙은 프로세서 증가에 맞춰 문제 크기도 커질 수 있다는 관점에서 출발한다. 실제 환경에서는 문제 크기가 증가하는 Weak Scaling이 가능하고, 이때 순차 부분의 비율이 감소할 수 있다.
존 구스타프슨(John Gustafson)은 1988년에 문제 크기를 늘리는 Scaled Speedup 관점을 제안했다. 프로세서가 늘어날수록 더 큰 문제를 해결하고 순차 부분의 비율을 낮출 수 있다는 생각이다.
Scaled_Speedup = N - P × (N - 1)
N: 프로세서 수
P: 병렬 가능 비율 (순차 부분 비율 아님)
P = 0.9, N = 10인 예시는 원문에 다음과 같이 제시되어 있다.
Scaled_Speedup = 10 - 0.9 × (10 - 1)
= 10 - 8.1
= 1.9... 아니, 실제로는
= 10 × 0.1 + 10 × 0.9 = 10 (정확히)
암달의 법칙은 문제 크기를 고정한 Strong Scaling에서 실행 시간 단축을 다루며, 순차 부분을 제약으로 본다. 구스타프슨의 법칙은 문제 크기를 증가시키는 Weak Scaling에서 처리량 증가를 목표로 하고 병렬 부분 비율의 유지를 본다.
| 구분 | 암달의 법칙 | 구스타프슨의 법칙 |
|---|---|---|
| 문제 크기 | 고정 | 증가 |
| 목표 | 실행 시간 단축 | 처리량 증가 |
| 성능 향상 | 제한적 (순차 부분) | 선형에 가까움 |
| 적용 사례 | 단일 태스크 가속 | 대규모 데이터 처리 |
제한된 크기의 문제를 빠르게 해결해야 하는 실시간 시스템이나 응답 시간이 중요한 애플리케이션에는 암달의 법칙의 관점이 맞닿아 있다. 과학 계산, 빅데이터 처리, 시뮬레이션처럼 더 큰 문제를 같은 시간에 처리하려는 경우에는 구스타프슨의 법칙이 다른 해석을 제공한다. 빅데이터 처리에서는 데이터셋 크기를 늘리고 더 많은 노드로 처리하는 방식에 구스타프슨 법칙을 적용할 수 있다. 과학 시뮬레이션에서도 해상도를 높이거나 더 정밀한 계산을 수행하면서 병렬 처리 효과를 지속할 수 있다.
멀티코어 환경에서 남는 과제
코어를 늘리면 발열과 전력 소비 문제가 뒤따른다. 프로세서 속도 개선에 비해 메모리 속도 개선이 지연되는 병목도 있고, 병렬 프로그래밍의 복잡도와 버그 가능성도 고려해야 한다. 본질적으로 순차적인 작업이 존재한다는 점은 여전히 바뀌지 않는다.
이기종 컴퓨팅은 CPU+GPU+FPGA 조합으로 서로 다른 작업 유형에 대응한다. AI나 암호화처럼 특정 작업에 최적화된 도메인 특화 가속기, 다층 캐시·HBM·3D 적층 메모리를 활용한 메모리 계층 최적화, 컴파일러와 런타임의 자동 병렬화 지원도 이런 제약에 대응하는 방식이다.