암달의 법칙 (Amdahl's Law)

코어를 100개로 늘려도 프로그램이 100배 빨라지지 않는다 — 병렬화의 수학적 한계

친구 8명이 모여 청소를 한다고 하자. 방을 나눠 맡으면 8배 빨리 끝날 것 같지만, 쓰레기봉투 묶기처럼 한 사람만 해야 하는 일은 아무리 사람이 많아도 시간이 그대로다. 프로그램도 똑같다. 코드에는 병렬로 나눌 수 있는 부분과 반드시 순서대로 해야 하는 부분(직렬 구간)이 섞여 있다. 1967년 진 암달(Gene Amdahl)은 이 둘의 비율만 알면 최대 속도 향상(speedup)이 정해진다는 것을 보였다.

공식

Speedup(N) = 1 (1 − p) + p / N

p = 병렬화 가능한 코드 비율 (0~1) · N = 프로세서(코어) 수 · (1−p) = 직렬 구간

코어를 무한히 늘리면 p/N → 0 이 되어 분모는 (1−p) 만 남는다. 즉 최대 speedup = 1 / (1 − p) — 직렬 구간이 speedup의 천장을 결정한다. 직렬 구간이 5%(p=0.95)면 코어가 몇 개든 20배가 한계다.

직접 실험해 보기

병렬화 비율 p 0.90

코어 수 N 16

현재 Speedup

—

이론적 최대 (N→∞)

—

코어 효율

—

1코어 실행 시간 (기준 = 100)

직렬

병렬

16코어 실행 시간

직렬

병렬

빗금친 빨강 = 아무리 코어를 늘려도 줄지 않는 직렬 구간. 파랑 = 코어 수만큼 짧아지는 병렬 구간.

코어 수(로그 스케일)에 따른 speedup 곡선. 각 곡선은 점선으로 표시된 자기 천장에 붙어 평평해진다.

숫자로 보는 천장

병렬 비율 p	직렬 구간	N=16	N=1024	최대 (N→∞)
0.50	50%	1.88×	2.0×	2×
0.90	10%	6.4×	9.9×	10×
0.95	5%	9.1×	19.6×	20×
0.99	1%	13.9×	91.2×	100×
0.999	0.1%	15.8×	506×	1000×

p=0.99 인 프로그램에 코어를 16개 → 1024개로 64배 늘려도 speedup은 13.9× → 91× 로 6.5배밖에 안 는다. 나머지 코어는 직렬 구간이 끝나길 놀며 기다린다.

코드로 speedup 계산

# 암달의 법칙: 병렬 비율 p, 코어 N 일 때의 speedup
def speedup(p, N):
    return 1 / ((1 - p) + p / N)

def max_speedup(p):        # N -> 무한대
    return 1 / (1 - p)

print(speedup(0.95, 16))    # 9.14...
print(max_speedup(0.95))      # 20.0  <- 코어를 아무리 늘려도 이 값이 한계

실무에서의 의미

1. 직렬 구간을 줄이는 게 코어를 늘리는 것보다 중요하다. p를 0.90에서 0.95로 올리면 천장이 10×에서 20×로 두 배가 된다.

2. 락(lock)·동기화·I/O는 숨은 직렬 구간이다. 임계 구역을 뮤텍스로 감싸면 그 부분은 사실상 직렬로 실행된다.

3. 반론 — 구스타프슨의 법칙(Gustafson's Law). 암달은 "문제 크기 고정"을 가정한다. 코어가 많아지면 보통 더 큰 문제를 푸는데(더 높은 해상도, 더 많은 데이터), 이때는 병렬 구간이 함께 커져서 speedup이 코어 수에 비례해 늘어날 수 있다. 슈퍼컴퓨터가 수만 코어로도 쓸모 있는 이유다.