홍라이프 계산기암달·구스타프슨 법칙 속도 향상 계산기 쉽게 이해하기 — 개념과 원리
프로그램을 여러 프로세서에 나누어 돌리면 얼마나 빨라질까요? 암달의 법칙은 문제 크기가 고정되어 있을 때, 구스타프슨의 법칙은 기계가 커지는 만큼 문제도 커질 때의 답을 줍니다. 이 계산기는 두 가지 속도 향상, 코어가 무한할 때의 이론적 한계, 병렬 효율을 함께 보여 주어 코어를 늘릴 가치가 있는지 판단하게 돕습니다.
계산 방법
병렬화 가능한 비율을 P(소수), 프로세서 수를 N이라 합니다.
- 암달 속도 향상: S = 1 ÷ ((1 − P) + P ÷ N)
- 최대 속도 향상(N → ∞): 1 ÷ (1 − P)
- 구스타프슨 확장 속도 향상: S = N − (1 − P) × (N − 1)
- 효율: 암달 속도 향상 ÷ N × 100%
P는 단일 프로세서로 실행했을 때 전체 시간 중 병렬로 돌릴 수 있는 부분의 비율입니다.
원리
암달의 법칙(1967)은 원래 실행 시간을 프로세서를 늘려도 줄지 않는 직렬 부분 (1 − P)과 N으로 나뉘는 병렬 부분 P로 나눕니다. N이 커지면 병렬 부분은 0에 가까워지지만 직렬 부분은 그대로 남으므로 속도 향상은 1 ÷ (1 − P)에 다가갑니다. 직렬 코드가 5%만 있어도 최대 20배를 넘을 수 없습니다. 구스타프슨(1988)은 사람들이 보통 큰 기계로 같은 시간에 더 큰 문제를 푼다는 점에 주목했습니다. 직렬 부분은 그대로이고 병렬 작업이 N에 비례해 늘면 확장 속도 향상은 거의 선형으로 커집니다. 두 법칙은 모두 맞으며, 강한 확장성과 약한 확장성이라는 서로 다른 질문에 답합니다.
예제 풀이
- 입력값은 P = 90% = 0.9, N = 16입니다.
- 암달: 0.9 ÷ 16 = 0.05625, 0.1 + 0.05625 = 0.15625이므로 1 ÷ 0.15625 = 6.4배입니다.
- 한계: 1 ÷ 0.1 = 10배입니다.
- 구스타프슨: 16 − 0.1 × 15 = 14.5배입니다.
- 효율: 6.4 ÷ 16 = 40%입니다.
| 병렬화 가능한 비율 (%) | 암달 속도 향상 |
|---|---|
| 22.5 | 1.267326733 |
| 45 | 1.72972973 |
| 67.5 | 2.723404255 |
| 90 | 6.4 |
| 112 | -18.28571429 |
| 135 | -3.764705882 |
| 180 | -1.454545455 |
결과 해석
효율은 하드웨어를 실제로 얼마나 활용하는지 보여 줍니다. 40%라면 코어 16개 능력의 절반 이상을 직렬 부분 때문에 잃고 있으므로, 코어를 늘리기보다 직렬 작업을 줄이는 편이 효과적입니다. 암달 속도 향상이 이미 한계에 가깝다면 코어를 더 늘려도 얻는 것이 적습니다.
흔한 실수
- P를 고정값으로 보는 경우입니다. 동기화와 통신 비용은 N과 함께 늘어나는 일이 많습니다.
- P를 원래의 직렬 실행이 아니라 병렬 실행에서 재는 경우입니다.
- 구스타프슨 결과를 고정된 작업이 14.5배 빨리 끝난다는 뜻으로 읽는 경우입니다.
자주 묻는 질문
강한 확장성과 약한 확장성은 무엇이 다른가요?
강한 확장성은 문제 크기를 고정하고(암달), 약한 확장성은 프로세서 수에 맞춰 문제를 키웁니다(구스타프슨).
내 프로그램의 병렬 비율은 어떻게 추정하나요?
몇 가지 코어 수에서 속도 향상을 재고 암달 공식을 P에 대해 풀면 됩니다. 카프-플랫(Karp–Flatt) 지표가 이 아이디어입니다.
출처: G. M. Amdahl, "Validity of the single processor approach to achieving large scale computing capabilities", AFIPS Conference Proceedings 30, 1967 · J. L. Gustafson, "Reevaluating Amdahl's Law", Communications of the ACM 31(5), 1988