암달의 법칙, 구스타프손의 법칙

출제 빈도: ★★★★★ | 기본 필수

답안.

Ⅰ. 개요

암달의 법칙(Amdahl's Law)은 병렬화로 얻을 수 있는 성능 향상의 이론적 상한을 제시하는 법칙이며, 구스타프손의 법칙(Gustafson's Law)은 이를 보완하여 문제 크기 확장 관점에서 병렬 처리의 실용적 효과를 설명한다.

Ⅱ. 암달의 법칙

병렬화 불가능 비율 S가 존재할 때, 프로세서 N개 투입 시 최대 속도향상은 다음과 같다.

Speedup = 1 / (S + (1-S)/N)

┌─────────────────────────────────────────────┐
│ S=10%일 때 Speedup 변화                      │
│                                             │
│ N=1    →  1.00배                            │
│ N=10   →  5.26배  ▓▓▓▓▓▓                   │
│ N=100  →  9.17배  ▓▓▓▓▓▓▓▓▓▓               │
│ N=∞    → 10.00배  ▓▓▓▓▓▓▓▓▓▓ (이론 한계)    │
│                                             │
│ 결론: 직렬 10%만 존재해도 최대 10배 한계      │
└─────────────────────────────────────────────┘

핵심 시사점은 병렬화 비율이 아무리 높아도 직렬 구간이 전체 성능의 병목이 된다는 점이다.

Ⅲ. 구스타프손의 법칙

암달의 법칙이 고정 크기 문제를 가정한 것에 대한 반론이다. 프로세서가 늘면 문제 크기도 키울 수 있으므로, 실용적 스피드업은 선형에 가까워진다.

Speedup = N - S(N-1)

예) S=0.1, N=100
    Speedup = 100 - 0.1×99 = 90.1배

빅데이터·AI 학습처럼 데이터셋 크기에 제한이 없는 워크로드에서는 구스타프손 관점이 더 현실적이다.

Ⅳ. 두 법칙 비교

Ⅴ. 성능 측정 지표

관련: 폴락의 법칙(08번) · GPU(34번) · HW 규모산정(31번)