암달의 법칙이란?
암달의 법칙은 컴퓨터 아키텍트 진 암달(Gene Amdahl)이 1967년에 제시한 법칙으로, 작업의 일부만 병렬화할 수 있을 때 얻을 수 있는 최대 이론적 속도 향상을 예측합니다. 병렬 컴퓨팅의 기본 원리 중 하나로, 프로세서·코어·스레드를 늘리기 전에 엔지니어가 현실적인 기대치를 설정하는 데 도움을 줍니다.
계산기 사용 방법
두 가지 값을 입력하세요. 먼저 병렬화 비율(p)은 프로그램에서 병렬로 실행할 수 있는 부분의 비율(0과 1 사이)입니다. 다음으로 속도 향상 계수(s)는 보통 그 병렬 부분에 투입하는 프로세서 또는 코어의 수를 뜻합니다. 계산기는 전체 속도 향상, 이론적 최대 속도 향상, 그리고 병렬 효율을 함께 보여 줍니다.
공식 풀이
공식은 다음과 같습니다.
$$\text{속도 향상} = \dfrac{1}{(1 - p) + \dfrac{p}{s}}$$여기서 \((1 - p)\)는 아무리 해도 빨라지지 않는 직렬(순차) 부분을 의미합니다. \(s\)가 매우 커지면 \(p/s\)는 0에 가까워지므로 속도 향상은 \(1/(1 - p)\)에서 한계에 부딪힙니다. 그래서 90%가 병렬화 가능한 프로그램은 프로세서를 아무리 많이 추가해도 결코 10배보다 빨라질 수 없습니다.
예제로 살펴보기
프로그램의 90%를 병렬화할 수 있고(\(p = 0.9\)) 프로세서 4개를 사용한다고(\(s = 4\)) 가정해 봅시다. 그러면 분모는 \((1 - 0.9) + 0.9/4 = 0.1 + 0.225 = 0.325\) 입니다. 속도 향상은 다음과 같습니다.
$$\text{속도 향상} = \dfrac{1}{0.325} \approx 3.08\text{배}$$가능한 최대 속도 향상은 \(1 / 0.1 = 10\)배이고, 효율은 \(3.08 / 4 \approx 76.9\%\) 입니다.
결과 해석
전체 속도 향상은 입력한 프로세서 수 \(s\)로 실제로 얻는 성능입니다 — 예를 들어, 4.71×의 결과는 병렬화된 프로그램이 단일 프로세서 버전보다 약 4.71배 더 빠르게 실행된다는 의미입니다. 최대 속도 향상, \(1/(1-p)\)은 무한히 많은 프로세서를 사용할 때 접근할 수 있는 절대적인 상한입니다. 두 값 사이의 간격은 남은 여유를 보여줍니다: 전체 속도 향상이 이미 최대값에 가깝다면, 하드웨어를 추가해도 거의 도움이 되지 않을 것입니다.
효율성은 "내가 구입한 프로세서를 얼마나 잘 사용하고 있는가?"를 답합니다. 100%에 가까운 효율성은 각 프로세서가 거의 1단위의 속도 향상에 기여한다는 의미이며, 이는 자원의 우수한 활용입니다. 낮은 효율성(예: 30% 이하)은 대부분의 프로세서가 유휴 상태이거나 직렬 부분에서 대기 중이라는 의미이므로, 유용한 작업을 거의 수행하지 않는 하드웨어에 대해 비용을 지불하고 있는 것입니다.
직렬 부분 \(1-p\)이 결정적인 한계입니다. 작은 직렬 부분도 성능을 크게 제한합니다: \(p=0.95\)에서 상한은 단 20×이므로, 대략 16~32개 프로세서를 넘으면 각각의 새 프로세서는 거의 아무것도 추가하지 않습니다. 실용적인 경험 법칙은 효율성이 허용 가능한 임계값(비용에 민감한 작업의 경우 종종 50~70%) 이하로 떨어지면 프로세서 추가를 중단하는 것입니다. 왜냐하면 그 시점을 지나면 점점 줄어드는 이득을 위해 돈을 쓰고 있기 때문입니다. 상한을 높이려면 직렬 부분 자체를 줄여야 합니다 — \(p\)를 증가시키는 알고리즘 변경은 보통 단순히 코어를 추가하는 것보다 훨씬 더 큰 성과를 냅니다.
핵심 용어 및 변수
- 병렬 부분(\(p\)) — 프로그램의 작업 중 병렬로 실행할 수 있는 비율로, 0과 1 사이의 소수로 표현합니다. 0.9의 값은 작업량의 90%를 프로세서들 간에 분할할 수 있다는 의미입니다.
- 직렬 부분(\(1-p\)) — 단일 프로세서에서 순차적으로 실행해야 하며 병렬화로 속도를 높일 수 없는 부분입니다. 이 부분이 전체 속도 향상의 확실한 상한을 결정합니다.
- 병렬 부분의 속도 향상(\(s\)) — 병렬화 가능한 부분이 가속되는 배수로, 보통 이에 적용된 프로세서 또는 코어의 개수와 같습니다.
- 전체 속도 향상 — 단일 프로세서 실행 시간과 병렬 실행 시간의 비율, \(1/\big((1-p)+p/s\big)\)입니다. 이것이 실제 성능 향상입니다.
- 최대 속도 향상 — \(s\)이 무한히 커질 때 도달하는 이론적 한계 \(1/(1-p)\)로, 직렬 부분에만 의해 결정됩니다.
- 병렬 효율성 — 전체 속도 향상을 프로세서 개수로 나눈 값, \(\text{속도 향상}/s\)으로, 백분율로 표현됩니다. 각 프로세서가 얼마나 효과적으로 활용되는지를 측정합니다.
자주 묻는 질문
프로세서를 늘려도 왜 효과가 점점 줄어드나요? 직렬 부분이 병목이 되기 때문입니다. 이 부분이 전체를 좌우하기 시작하면 프로세서를 더 추가해도 거의 도움이 되지 않습니다.
병렬 효율이란 무엇인가요? 속도 향상을 프로세서 수로 나눈 값을 백분율로 나타낸 것으로, 각 프로세서가 얼마나 효과적으로 활용되고 있는지를 보여 줍니다.
구스타프슨의 법칙과는 어떻게 다른가요? 암달의 법칙은 문제 크기가 고정되어 있다고 가정합니다. 반면 구스타프슨의 법칙은 프로세서 수에 따라 문제 규모가 함께 커진다고 가정하므로 더 낙관적인 결과를 내놓습니다.
