병렬처리 성능 법칙(암달의 법칙·구스타프슨 법칙)
1. 개요
가. 정의
암달의 법칙(Amdahl's Law) 은 작업의 전체 크기를 고정한 채 프로세서 수를 늘릴 때 얻을 수 있는 성능 향상(speedup)이 직렬로만 수행되는 부분의 비율에 의해 상한이 결정된다는 법칙이고, 구스타프슨 법칙(Gustafson's Law, Gustafson–Barsis) 은 프로세서가 늘면 처리하는 문제의 크기도 함께 키운다고 가정할 때 성능 향상이 프로세서 수에 거의 비례해 확장될 수 있음을 보이는 법칙이다. 두 법칙은 같은 병렬 시스템을 각각 '고정된 일을 얼마나 빨리 끝내는가(strong scaling)'와 '같은 시간에 얼마나 많은 일을 하는가(weak scaling)'의 관점에서 설명한다.
병렬처리의 핵심 질문은 단순하다. "프로세서(코어)를 N배로 늘리면 성능도 N배가 되는가?" 직관적으로는 그래야 할 것 같지만 현실은 그렇지 않다. 어떤 프로그램이든 순서를 지켜 한 번에 하나씩 처리할 수밖에 없는 직렬 구간(serial section) — 초기화, 입출력, 임계영역, 결과 병합 등 — 이 존재하며, 이 구간은 프로세서를 아무리 늘려도 빨라지지 않는다. 암달의 법칙은 바로 이 직렬 구간이 전체 성능 향상의 '천장'을 만든다는 사실을, 구스타프슨 법칙은 문제 규모를 키우면 그 천장을 사실상 밀어 올릴 수 있다는 사실을 정량적으로 보여준다.
이 두 법칙은 서로 모순되는 것이 아니라 가정이 다른 상호 보완적 모델이다. 암달은 '일의 양을 고정'하고, 구스타프슨은 '시간을 고정(일의 양을 확장)'한다. 어느 쪽이 맞느냐가 아니라, 내 워크로드가 어느 시나리오에 해당하는지를 판단하는 것이 병렬 설계의 출발점이다. 기술사 관점에서 이 법칙들은 멀티코어 CPU, GPU 가속, 대규모 분산 학습, 빅데이터 처리의 투자 대비 효과(ROI)와 확장 한계를 예측하는 용량 산정·아키텍처 의사결정의 기본 도구로 쓰인다.
나. 등장 배경과 필요성
암달의 법칙은 1967년 Gene Amdahl이 단일 고속 프로세서와 다수 저속 프로세서의 경제성을 비교하는 맥락에서 제시했다. 당시는 병렬 컴퓨터의 효용에 대한 낙관론이 팽배했으나, Amdahl은 "프로그램의 상당 부분이 본질적으로 직렬이라면 병렬화의 이득은 제한적"이라는 냉정한 상한을 제시해 병렬화 투자에 대한 현실적 기준을 세웠다. 이후 무어의 법칙이 한계에 부딪히고 클럭 속도 향상 대신 코어 수 증가(멀티코어) 로 성능을 끌어올리는 시대가 열리면서, 암달의 법칙은 "코어를 늘려도 왜 기대만큼 빨라지지 않는가"를 설명하는 핵심 도구로 재조명되었다.
반면 1988년 John Gustafson은 샌디아 국립연구소의 1024-프로세서 하이퍼큐브에서 실제 과학 계산을 병렬화하며 암달의 비관적 예측과 다른 현상을 관찰했다. 프로세서를 늘릴 때 사람들은 같은 문제를 더 빨리 풀기보다 더 큰 문제(더 미세한 격자, 더 긴 시뮬레이션) 를 같은 시간 안에 푸는 방식으로 자원을 활용한다는 것이었다. 즉 직렬 비율은 문제 규모가 커질수록 상대적으로 작아지므로, 실제 HPC에서는 프로세서 수에 거의 비례하는 확장이 관측되었다. 이 통찰이 대규모 병렬 슈퍼컴퓨팅의 타당성을 뒷받침했다. 오늘날 수천 장의 GPU로 거대 언어모델(LLM)을 학습하거나 수만 코어로 기상·유체 시뮬레이션을 돌리는 것은 구스타프슨적 확장이 성립하기 때문이며, 반대로 응답시간이 중요한 온라인 서비스의 단일 요청 처리에는 암달적 한계가 그대로 적용된다.
2. 암달의 법칙 — 고정 작업량(Strong Scaling)
암달의 법칙은 '전체 일의 양을 고정'한다. 프로그램 실행시간을 병렬화 가능 비율 p(0≤p≤1)와 직렬 비율 1-p로 나누면, 프로세서 N개를 투입했을 때의 성능 향상은 다음과 같다.
Speedup(N) = 1 / ( (1 − p) + p/N ), 그리고 N → ∞ 이면 최대 성능 향상 = 1 / (1 − p)
아래 구조도는 전체 작업이 직렬 구간과 병렬 구간으로 분해되고, 병렬 구간만 N개의 처리기로 분산되는 암달 모델의 전체 구조를 보여준다. 직렬 구간은 분산되지 않고 그대로 남아 전체 시간의 하한을 만든다.
flowchart TB
JOB["고정된 전체 작업<br/>(실행시간 1)"]
JOB --> SER["직렬 구간 (1−p)<br/>프로세서 늘려도 불변"]
JOB --> PAR["병렬 구간 p<br/>N개로 분할 가능"]
PAR --> P0["처리기 0<br/>(p/N)"]
PAR --> P1["처리기 1<br/>(p/N)"]
PAR --> Pn["처리기 N−1<br/>(p/N)"]
SER --> OUT["총 실행시간<br/>(1−p) + p/N"]
P0 --> OUT
P1 --> OUT
Pn --> OUT
style SER fill:#fce8e6,stroke:#d93025,stroke-width:2px
style PAR fill:#e6f4ea,stroke:#188038,stroke-width:2px
style OUT fill:#e8f0fe,stroke:#2f6fed,stroke-width:2px
가. 직렬 구간이 만드는 천장
암달의 법칙이 전하는 가장 강력한 메시지는 '병렬화 불가능한 부분이 조금만 있어도 전체 확장성이 급격히 제한된다'는 점이다. 예를 들어 전체의 95%를 완벽히 병렬화해도(p=0.95), 직렬 5%가 남으면 프로세서를 무한히 늘려도 최대 성능 향상은 1/(1−0.95)=20배에 묶인다. 프로세서가 20개를 넘어서면 추가 투입은 거의 효과가 없으며, 1,000개를 넣어도 약 19.6배에 그친다. 이는 '직렬 5%'라는 작은 값이 전체 확장의 운명을 결정함을 뜻한다.
나. 수치로 본 수확 체감
구체적으로 p=0.90인 작업을 보자. N=2이면 1/(0.1+0.45)=약 1.82배, N=4이면 1/(0.1+0.225)=약 3.08배, N=8이면 약 4.71배, N=16이면 약 6.40배, N=∞이면 10배가 상한이다. 프로세서를 2배씩 늘려도 성능 향상 폭은 점점 줄어드는 수확 체감(diminishing returns) 이 뚜렷하다. 아래 표는 직렬 비율에 따른 이론적 상한을 정리한 것이다.
| 병렬화 비율 p | 직렬 비율 1−p | 최대 성능 향상(N→∞) | N=16일 때 |
|---|---|---|---|
| 0.50 | 0.50 | 2배 | 약 1.88배 |
| 0.90 | 0.10 | 10배 | 약 6.40배 |
| 0.95 | 0.05 | 20배 | 약 9.14배 |
| 0.99 | 0.01 | 100배 | 약 13.9배 |
다. 실무적 함의
암달의 법칙은 '병렬화에 앞서 직렬 구간을 줄이는 것이 더 중요할 수 있다'는 최적화 우선순위를 알려준다. 데이터베이스 트랜잭션의 커밋 직렬화, 락 경합, 전역 카운터, 단일 로그 파일에 대한 순차 기록 등은 전형적인 직렬 병목이며, 이들을 샤딩·락프리 자료구조·배치 처리로 줄이지 않으면 코어 증설은 돈 낭비가 된다. 실제로 한 OLTP 시스템에서 CPU를 8코어에서 32코어로 4배 늘렸으나 처리량이 1.6배에 그친 사례가 있는데, 이는 커넥션 풀과 커밋 경로의 직렬 구간이 p≈0.8 수준이어서 N=32의 이론 상한(약 4.7배)에도 못 미친 전형적 암달 현상이었다.
같은 관점은 소프트웨어 프로파일링에도 직접 적용된다. 암달의 법칙은 '전체에서 큰 비중을 차지하는 부분을 먼저 최적화하라'는 원칙의 수학적 근거이기도 하다. 전체 실행시간의 5%를 차지하는 함수를 10배 빠르게 만들어도 전체는 약 4.5%밖에 줄지 않지만, 60%를 차지하는 함수를 2배로만 개선해도 전체가 30% 줄어든다. 병렬화든 알고리즘 개선이든, 투자 효과는 언제나 '개선 대상이 전체에서 차지하는 비중'에 의해 제한된다는 것이 암달이 주는 보편적 교훈이다.
3. 구스타프슨 법칙 — 고정 시간(Weak Scaling)
구스타프슨 법칙은 관점을 뒤집는다. '시간을 고정'하고, 프로세서가 N배면 처리하는 문제 크기도 키운다고 본다. 병렬 실행 시간을 기준으로 직렬 비율을 s, 병렬 비율을 1−s라 할 때 scaled speedup은 다음과 같다.
Speedup(N) = N − (1 − 1/N) 해석상 = s + (1 − s)·N = N − s·(N − 1)
여기서 s는 '병렬 실행 기준'의 직렬 비율이라는 점이 암달과 다르다. 아래 다이어그램은 프로세서를 늘릴 때 암달(작업량 고정→시간 단축)과 구스타프슨(시간 고정→작업량 확장)이 자원을 쓰는 방식이 어떻게 갈리는지를 프로세스 관점에서 비교한다.
flowchart LR
START["프로세서 N배 증설"] --> Q{"무엇을 고정하는가?"}
Q -->|"작업량 고정"| A1["Amdahl: 같은 일을<br/>더 빨리"]
A1 --> A2["직렬 구간 비중 증가<br/>→ 성능 향상 포화"]
A2 --> A3["상한 1/(1−p)"]
Q -->|"시간 고정"| G1["Gustafson: 같은 시간에<br/>더 큰 일"]
G1 --> G2["문제 확대로 병렬 구간<br/>상대 비중 증가"]
G2 --> G3["성능 향상 ≈ N에<br/>거의 선형 확장"]
style A3 fill:#fce8e6,stroke:#d93025,stroke-width:2px
style G3 fill:#e6f4ea,stroke:#188038,stroke-width:2px
가. 직렬 비율이 상대적으로 작아지는 원리
과학 계산에서 직렬 작업(초기화·입출력)의 절대 시간은 문제 크기가 커져도 거의 일정한 반면, 병렬 작업(격자 계산·행렬 연산)의 양은 문제 크기에 비례해 폭증한다. 따라서 문제를 키울수록 전체에서 직렬이 차지하는 비율은 작아지고, 암달이 가정한 '고정된 직렬 비율'이 더 이상 유지되지 않는다. 예컨대 격자 해상도를 2배로 높이면 계산량은 수 배로 늘지만 파일을 여는 시간은 그대로이므로, 직렬 비율이 10%에서 2%로 떨어지는 식이다. 이것이 1,024 프로세서에서도 선형에 가까운 확장이 관측된 이유다.
나. 수치로 본 선형 확장
s=0.05(병렬 기준 직렬 5%)일 때 구스타프슨 성능 향상은 N=16이면 0.05+0.95×16=약 15.25배, N=1,024이면 약 972.9배에 이른다. 같은 직렬 5%라도 암달이 최대 20배에 묶이는 것과 극명히 대비된다. 핵심은 '무엇을 측정하느냐'다. 암달은 동일 문제의 응답시간 단축을, 구스타프슨은 동일 시간 내 처리 규모(throughput·문제 크기) 를 측정한다.
다. 적용 영역
구스타프슨적 확장이 성립하는 대표 사례는 HPC 시뮬레이션(기상·유체·구조해석), 대규모 딥러닝 학습(배치·데이터 병렬), 몬테카를로 시뮬레이션처럼 '자원이 늘면 더 정밀·대규모로 풀고 싶은' 문제들이다. 반대로 단일 사용자 요청의 응답시간, 고정 크기 배치의 마감시간처럼 '일의 양이 고정'된 문제에는 암달적 한계가 그대로 적용된다. 따라서 설계자는 "우리 워크로드는 더 빨리(strong)를 원하는가, 더 많이(weak)를 원하는가"를 먼저 정의해야 한다.
4. 두 법칙의 비교
두 법칙의 차이는 '틀림과 맞음'이 아니라 문제 설정의 차이에서 비롯된다. 암달은 고정 작업량(strong scaling), 구스타프슨은 확장 작업량(weak scaling)을 전제하며, 각각이 겨냥하는 현실 문제와 그로부터 나오는 실무 결론이 다르다.
| 구분 | 암달의 법칙 | 구스타프슨 법칙 |
|---|---|---|
| 고정 대상 | 작업량(문제 크기) | 실행 시간 |
| 스케일링 유형 | Strong scaling | Weak scaling |
| 성능 향상 식 | 1/((1−p)+p/N) | s+(1−s)·N |
| N→∞ 거동 | 상한 1/(1−p)로 포화 | N에 비례해 선형 증가 |
| 측정 지표 | 응답시간 단축 | 처리 규모·처리량 |
| 적합 사례 | 온라인 트랜잭션, 고정 배치 | HPC 시뮬레이션, 대규모 학습 |
표의 차이가 생기는 근본 이유는 직렬 비율을 고정으로 보느냐, 문제 규모의 함수로 보느냐에 있다. 암달은 직렬 비율을 상수로 두므로 N이 커지면 p/N이 0에 수렴해 직렬 항만 남고, 그래서 포화한다. 구스타프슨은 문제를 키우면 병렬 작업의 절대량이 늘어 직렬 비율이 감소한다고 보므로 포화가 일어나지 않는다. 실무적 함의는 분명하다. 응답 지연을 줄이는 투자(단일 쿼리 가속)라면 암달의 천장을 먼저 계산해 과잉 증설을 피해야 하고, 처리 용량을 키우는 투자(더 큰 모델·더 많은 사용자)라면 구스타프슨적 확장을 전제로 수평 확장을 설계하되 통신·동기화 비용이 새로운 병목이 되지 않는지 함께 봐야 한다.
구체적 사례로, 추천 시스템의 야간 배치 학습을 보자. 데이터가 고정된 어제치 로그라면(strong) GPU를 2장→8장으로 늘려도 전처리·체크포인트 저장의 직렬 구간 때문에 암달 상한에 걸려 4배가 아닌 2.5배 단축에 그친다. 그러나 운영팀이 "같은 4시간 안에 더 많은 피처와 더 큰 임베딩을 학습"하도록 목표를 바꾸면(weak) 동일한 8장으로 거의 선형적으로 모델 규모를 키울 수 있다. 같은 하드웨어라도 목표 설정에 따라 두 법칙 중 어느 쪽 곡선을 타는지가 달라진다.
5. 심화: 보편 확장성 법칙(USL)과 최신 동향
암달·구스타프슨은 통신·동기화 비용을 무시한 이상화 모델이라는 한계가 있다. 현실에서는 프로세서가 늘수록 공유 자원 경합(contention)과 데이터 일관성 유지를 위한 상호 통신(coherency)이 증가해, 어느 지점을 넘으면 성능이 오히려 감소(retrograde) 하기도 한다. Neil Gunther의 보편 확장성 법칙(USL, Universal Scalability Law) 은 이를 두 개의 벌점 항으로 모델링한다.
C(N) = N / ( 1 + α·(N − 1) + β·N·(N − 1) ) — α: 경합(직렬화), β: 일관성(상호 통신) 계수
여기서 β=0이면 USL은 암달의 법칙으로 환원되며, β가 0이 아니면 성능 곡선이 특정 정점(peak concurrency) 이후 하락하는 현실적 거동을 설명한다. USL은 소수의 부하 측정점(여러 스레드 수에서의 처리량)으로 α·β를 회귀 추정해, "우리 시스템은 몇 개의 노드/코어까지 늘려야 이득인가"라는 용량 산정 질문에 정량적 답을 준다. 즉 암달이 상한을, 구스타프슨이 확장 가능성을 말한다면, USL은 경합·통신 비용까지 포함한 현실적 최적 동시성을 짚어 준다.
구체적 수치로 보면, 어떤 분산 집계 작업을 스파크 클러스터에서 10노드→40노드로 4배 늘렸을 때 처리량이 3.9배까지 선형에 가깝게 오르다가(구스타프슨 구간), 80노드에서는 셔플 네트워크 경합 탓에 오히려 7.2배 수준으로 정점을 찍고 100노드에서 7.0배로 꺾이는 현상이 나타난다. 이 역전 구간은 암달·구스타프슨만으로는 설명되지 않으며, USL의 β 항으로만 포착된다. 따라서 "노드를 더 넣으면 무조건 빨라진다"는 가정은 위험하고, 측정으로 정점 동시성을 찾아 그 이상은 알고리즘·통신 구조를 바꿔야 한다는 결론이 나온다.
최신 동향에서 이 법칙들은 AI·데이터센터 규모 확장의 설계 언어가 되었다. 수천 장의 GPU로 LLM을 학습할 때 데이터·텐서·파이프라인 병렬화는 구스타프슨적 확장을 노리지만, 올-리듀스(all-reduce) 집합 통신이 USL의 β 항처럼 작용해 일정 규모를 넘으면 통신이 병목이 된다. 그래서 NVLink·InfiniBand·RoCE 같은 고속 인터커넥트와 통신·연산 중첩(overlap), 그래디언트 압축이 핵심 과제가 된다. 아파치 스파크의 셔플, 분산 데이터베이스의 합의(consensus)도 같은 구조로 경합·통신 비용이 선형 확장을 꺾는 지점을 만든다. 결국 현대 분산 시스템 설계는 '병렬 구간을 늘리고(구스타프슨), 직렬·경합·통신을 줄이는(암달·USL)' 두 축의 동시 최적화로 수렴한다.
6. 고려사항 및 시사점
기술사 관점에서 이 법칙들은 단순한 공식이 아니라 병렬·분산 투자의 타당성과 한계를 판단하는 의사결정 프레임으로 활용해야 하며, 다음과 같은 전략적 시사점을 갖는다.
적용 전략 — 워크로드 유형 선판별: 증설 투자에 앞서 대상 워크로드가 응답시간 단축형(strong, 암달)인지 처리규모 확장형(weak, 구스타프슨)인지 먼저 분류해야 한다. 전자는 직렬 비율
p를 측정해 이론 상한을 계산하고 그 안에서 적정 코어 수를 정하며, 후자는 문제 확대와 수평 확장을 전제로 통신 아키텍처를 먼저 설계한다.트레이드오프 — 직렬 축소 대 병렬 확대: 암달의 법칙은 '병렬화를 늘리기보다 직렬 병목을 없애는 것이 더 큰 이득'일 수 있음을 시사한다. 락 경합·전역 자원·순차 I/O를 샤딩·락프리·배치로 제거하는 리팩터링과, 코어·노드 증설 중 어디에 투자할지를 비용 대비 효과로 비교해야 한다. 과잉 증설은 수확 체감 구간에서 TCO만 키운다.
현실 비용의 반영(USL): 이상화된 암달·구스타프슨만 믿으면 통신·동기화 비용을 과소평가해 '넣을수록 느려지는' 함정에 빠진다. 소규모 부하 시험으로 α·β를 추정해 최적 동시성(peak)을 산정하고, 그 지점을 넘는 확장은 인터커넥트 개선이나 알고리즘 변경 없이는 효과가 없음을 의사결정에 반영해야 한다.
전망과 연계 기술 — 이기종·대규모 가속: GPU·NPU·TPU 등 가속기와 CXL 기반 메모리 확장, 초고속 인터커넥트가 보편화되면서 병렬 성능의 병목은 '연산'에서 '데이터 이동과 동기화'로 이동하고 있다. 통신·연산 중첩, 집합통신 최적화, 데이터 지역성(NUMA·토폴로지 인지 배치)이 세 법칙의 실무적 연장선이며, 거대 모델 학습·실시간 추론의 비용·전력 효율을 좌우하는 핵심 역량으로 자리 잡을 전망이다.
거버넌스·운영 관점: 확장성은 일회성 벤치마크가 아니라 지속 관측 대상이다. 처리량-동시성 곡선을 상시 측정해 성능 회귀를 조기에 포착하고, 하드웨어 세대 교체·토폴로지 변화 시 α·β를 재추정하는 용량 관리 프로세스를 운영에 내재화해야 투자 대비 효과를 지속 보장할 수 있다.
참고자료
- G. M. Amdahl, "Validity of the single processor approach to achieving large scale computing capabilities" (1967) — https://doi.org/10.1145/1465482.1465560
- J. L. Gustafson, "Reevaluating Amdahl's Law", CACM (1988) — https://doi.org/10.1145/42411.42415
- Neil J. Gunther, "Universal Scalability Law" — https://en.wikipedia.org/wiki/Neil_J._Gunther
- USL R package (vignette/manual) — https://cran.r-project.org/web/packages/usl/vignettes/usl.pdf
한 줄 요약: 암달의 법칙은 작업량을 고정했을 때 직렬 비율이 성능 향상의 상한(1/(1−p))을 정하는 strong scaling을, 구스타프슨 법칙은 문제 크기를 함께 키우면 성능이 프로세서 수에 거의 선형 확장되는 weak scaling을 설명하며, USL은 경합·통신 비용까지 반영해 현실적 최적 동시성을 짚어 주는 상호 보완적 병렬처리 성능 법칙이다.