Amdahl의 법칙 병렬 가속과 효율 계산

Amdahl의 법칙은 컴퓨터 아키텍트 Gene Amdahl이 1967년에 제시한 것으로, 계산을 여러 프로세서에 분산했을 때 얻을 수 있는 이론적 가속을 설명합니다. 이는 병렬 컴퓨팅에서 가장 중요하고 널리 인용되는 원리 중 하나로, 프로세서를 아무리 늘려도 얻을 수 있는 성능 향상에는 분명한 상한이 있음을 보여줍니다. 이 법칙은 현실의 모든 프로그램이 두 부분으로 이루어진다는 단순한 관찰에서 출발합니다. 하나는 본질적으로 순차적이어서 각 단계가 이전 단계의 결과에 의존하므로 순서대로 실행해야 합니다. 다른 하나는 병렬화 가능해서 독립적인 작업으로 나누어 여러 프로세서에서 동시에 실행할 수 있습니다. Amdahl의 법칙은 이 둘의 관계를 수식으로 나타냅니다. 공식은 S(n) = 1 / (p + (1 − p) / n)입니다. 여기서 S는 가속도, p는 순차적으로 실행해야 하는 프로그램 비율(0~1), n은 프로세서 수, (1 − p)는 병렬화 가능한 비율입니다. n이 무한대로 커질수록 (1 − p) / n은 0에 가까워지고, 가속도는 1/p에 수렴합니다. 이것이 이론적 최대 가속도입니다. 이 최대값은 오직 순차 비율에 의해 결정되며, 프로세서를 얼마나 추가하든 넘을 수 없습니다. 영향은 큽니다. 프로그램의 10%가 순차적이라면(p = 0.1) 프로세서를 몇 개를 쓰든 최대 가속도는 1/0.1 = 10×입니다. 20%가 순차적이면 최대는 5×, 50%가 순차적이면 최대는 2×에 불과합니다. 일정 지점을 넘어서 프로세서를 더 추가해도 수익이 급격히 줄어듭니다. 순차 부분이 병목이 되기 때문이며, 이를 흔히 “Amdahl의 천장”이라고 부르기도 합니다. 구체적인 예를 보겠습니다. 어떤 프로그램이 단일 코어에서 3,600초 걸리고, 작업의 80%가 병렬화 가능하다고 합시다(p = 0.2). 프로세서 8개를 사용하면 S(8) = 1 / (0.2 + 0.8/8) = 1 / (0.2 + 0.1) = 1 / 0.3 = 3.33×입니다. 병렬 실행 시간은 3600 / 3.33 = 1080초입니다. 16개를 사용하면 S(16) = 1 / (0.2 + 0.8/16) = 1 / (0.2 + 0.05) = 4×가 되고 시간은 900초로 줄어듭니다. 8개에서 16개로 두 배 늘려도 성능은 20%만 개선되는데, 순차 20%가 전체를 지배하기 때문입니다. 병렬 효율은 가속도를 프로세서 수로 나눈 뒤 백분율로 나타낸 값입니다. E = S(n)/n × 100%입니다. 각 추가 프로세서가 얼마나 잘 활용되는지를 보여줍니다. 100%의 완벽한 효율은 모든 프로세서가 완전히 활용된다는 뜻으로, 이론적 이상입니다. 실제로는 순차 비율 때문에 프로세서 시간이 낭비되므로, 프로세서가 늘수록 효율은 떨어집니다. 효율이 50% 아래로 내려가면, 추가 프로세서를 사는 비용이 시간 절감보다 더 커질 수 있습니다. Amdahl의 법칙은 순차 비율 p가 문제 크기와 상관없이 일정하다고 가정합니다. Gustafson의 법칙(1988)은 보완적인 관점을 제공합니다. 더 큰 문제 크기에서는 더 많은 작업이 병렬화 가능해지고, 프로세서 수가 늘어도 효율이 더 높게 유지될 수 있습니다. 이 두 법칙을 함께 보면 병렬 확장의 전체 그림이 보입니다. Amdahl의 법칙은 비관적이지만 고정 문제 크기 시나리오를 정확히 설명하고, Gustafson의 법칙은 더 낙관적이며 문제 크기가 프로세서 수와 함께 커질 때 적용됩니다. Amdahl의 법칙은 CPU 및 GPU 아키텍처 설계, 클라우드 컴퓨팅 자원 배분, 고성능 컴퓨팅 알고리즘 분석, 기존 시스템에 프로세서를 추가할 때의 투자 대비 효과 추정 등에 활용됩니다. 더 나은 알고리즘, 동기화 오버헤드 감소, 데이터 구조 재설계를 통해 계산의 순차 비율을 찾아 줄이는 것이 Amdahl의 천장을 높이는 가장 효과적인 방법입니다.