arch · 11

암달의 법칙

성능병렬처리속도향상

대부분의 프로그램에는 코어를 아무리 늘려도 나눠 처리할 수 없는 부분이 남습니다. 암달의 법칙(Amdahl's Law)은 프로그램의 일부만 빠르게 만들었을 때 전체 성능이 얼마나 좋아지는지를 계산하는 법칙이며, 병렬 처리로 얻을 수 있는 속도 향상에는 한계가 있음을 보여줍니다.

핵심 개념

속도 향상(Speedup)

개선 전 실행 시간 ÷ 개선 후 실행 시간입니다. 실행 시간이 절반으로 줄었다면 속도 향상은 2배입니다.

핵심 개념

병렬 비율 p

전체 실행 시간 중 여러 코어로 나눠 처리할 수 있는 부분의 비율입니다. 나머지 (1-p)는 반드시 직렬로 실행됩니다.

핵심 개념

암달의 법칙 공식

Speedup(N) = 1 / ((1-p) + p/N). N은 코어(프로세서) 수이며, 직렬 부분은 그대로 두고 병렬 부분만 N으로 나눕니다.

핵심 개념

이론적 한계

N을 무한대로 늘리면 p/N이 0에 가까워져 Speedup은 1/(1-p)에 수렴합니다. p=0.8이면 최대 5배입니다.

핵심 개념

수확 체감

코어를 늘릴수록 코어당 효율이 떨어지고, 어느 지점부터는 코어를 2배로 늘려도 추가로 얻는 폭이 줄어듭니다. p=0.8에서 4코어는 2.5배, 8코어는 약 3.33배, 16코어는 4배입니다.

핵심 개념

구스타프슨의 법칙

암달의 법칙은 문제 크기가 고정이라고 가정합니다. 구스타프슨의 법칙은 코어가 늘면 처리할 문제 크기도 함께 키운다는 관점으로 확장성을 설명합니다.

병목은 직렬 부분입니다 — 병렬 부분을 아무리 빠르게 만들어도 직렬 부분의 시간은 그대로여서, 전체 향상 폭의 천장은 직렬 비율이 결정합니다.

코어 수보다 병렬 비율이 중요합니다 — p가 0.5면 코어를 무한히 늘려도 최대 2배입니다. 코어를 더 사기 전에 직렬 구간을 줄이는 쪽이 더 효과적일 수 있습니다.

병렬화에만 해당하는 법칙이 아닙니다 — "전체 중 일부만 s배 빠르게 만들었을 때 전체가 얼마나 빨라지는가"라는 일반적인 성능 개선 상황에 모두 적용됩니다.

이 시각화에서 확인할 것 — "시간 분할" 탭에서 코어가 늘어도 직렬 구간이 남는 모습을, "속도 향상 곡선" 탭에서 병렬 비율별 한계선을, "병렬 비율 비교" 탭에서 같은 8코어라도 결과가 크게 달라지는 것을 STEP으로 확인하세요.

암달의 법칙이 나온 배경

진 암달(Gene Amdahl)은 1967년 학회 발표에서 단일 프로세서로 큰 계산을 빠르게 하려는 접근이 어디까지 유효한지 논했고, 이 논의가 오늘날 '암달의 법칙'으로 정리되었습니다. 컴퓨터 구조 교재에서는 이 법칙을 병렬 처리에만 쓰지 않고, 일부를 빠르게 만들었을 때 전체가 얼마나 빨라지는가를 계산하는 일반식으로 소개합니다. 전체 속도 향상 = 1 / ((1 − f) + f / s)에서 f는 개선된 부분이 전체 실행 시간에서 차지하는 비율, s는 그 부분이 빨라진 배수입니다.

숫자로 확인하기

일반식 예 — 실행 시간의 40%를 차지하는 부분을 10배 빠르게 만들면 1 / (0.6 + 0.04) ≈ 1.56배입니다. 60%인 나머지가 그대로이므로 10배가 되지 않습니다.

코어 수에 따른 변화 — 병렬 비율 p = 0.9이면 8코어에서 1 / (0.1 + 0.1125) ≈ 4.71배, 64코어에서 1 / (0.1 + 0.0140625) ≈ 8.77배입니다. 코어를 8배로 늘렸는데 속도는 1.9배도 안 늘었습니다.

병렬 비율별 상한 — 코어를 무한히 늘려도 p = 0.5는 2배, p = 0.9는 10배, p = 0.95는 20배, p = 0.99는 100배가 한계입니다.

자주 하는 오해

코어를 2배로 늘리면 속도도 2배가 된다 — 직렬 부분이 남아 있는 한 그렇게 되지 않습니다. p = 0.9에서 코어 2개는 1 / (0.1 + 0.45) ≈ 1.82배이고, 코어 8개는 약 4.71배입니다.

p는 코드 줄 수의 비율이다 — p는 개선 전 실행 시간에서 병렬로 처리할 수 있는 부분이 차지하는 비율입니다. 코드가 짧아도 오래 도는 반복문이면 p에 크게 기여합니다.

암달의 법칙 식에는 병렬화 비용이 들어 있다 — 기본식에는 스레드 동기화, 통신, 부하 불균형 같은 비용이 들어 있지 않습니다. 그래서 실제 속도 향상은 식이 주는 값보다 낮아지며, 식의 값은 이상적인 상한으로 읽어야 합니다.

직렬 비율은 고정된 값이다 — 문제 크기를 키우면 직렬 비율이 달라질 수 있습니다. 존 구스타프슨은 1988년 같은 시간에 더 큰 문제를 푸는 관점의 '확장 속도 향상(scaled speedup)'을 제시했고, 그 식은 N − (N − 1) × s입니다(s는 병렬 실행 시간에서 직렬 부분의 비율).

면접에서 이렇게 물어요

면접 질문

병렬 비율 90%인 프로그램을 8코어에서 돌리면 속도 향상은 얼마인가요?

1 / ((1 − 0.9) + 0.9 / 8) = 1 / 0.2125 ≈ 4.71배입니다. 코어를 무한히 늘려도 1 / 0.1 = 10배를 넘을 수 없다는 점까지 말하면 좋습니다.

면접 질문

암달의 법칙과 구스타프슨의 법칙은 무엇이 다른가요?

암달의 법칙은 문제 크기를 고정하고 같은 일을 얼마나 빨리 끝내는지(강한 확장성)를 봅니다. 구스타프슨의 법칙은 코어가 늘면 문제 크기도 키워 같은 시간에 더 많은 일을 하는 것(약한 확장성)을 봅니다. 같은 현상을 서로 다른 전제에서 본 것입니다.

면접 질문

성능을 개선할 부분을 어떻게 고르나요?

전체 실행 시간에서 차지하는 비율이 큰 부분부터 개선합니다. 비율이 작은 부분은 아무리 빠르게 만들어도 전체 이득이 작기 때문에, 먼저 프로파일링으로 시간이 어디에 쓰이는지 측정합니다.

면접 질문

직렬 부분이 생기는 대표적인 이유는 무엇인가요?

한 번에 하나의 스레드만 실행할 수 있는 임계 구역(락으로 보호한 구간), 작업을 나누고 결과를 합치는 단계, 다른 작업과 겹치지 못하는 입출력 대기 같은 것이 직렬 부분이 될 수 있습니다.

실제 시스템에서는

임계 구역 — 여러 스레드가 락 하나를 두고 경쟁하면 그 구간은 사실상 직렬로 실행됩니다. 락 범위를 줄이거나 락을 쓰지 않는 자료구조로 바꾸면 직렬 비율을 줄일 수 있는 경우가 있습니다.

고성능 컴퓨팅의 확장성 측정 — 문제 크기를 고정하고 코어 수를 늘려 가며 시간을 재는 방식을 강한 확장성(strong scaling), 코어 수에 비례해 문제 크기를 키우며 재는 방식을 약한 확장성(weak scaling)이라고 부릅니다. 앞쪽이 암달의 법칙, 뒤쪽이 구스타프슨의 법칙과 연결됩니다.

컴퓨터 구조 교재 — Hennessy와 Patterson은 암달의 법칙을 병렬화뿐 아니라 캐시나 명령어 최적화처럼 시스템 일부를 개선하는 모든 경우에 쓰는 기본 원리로 설명합니다.

함께 보면 좋은 토픽

파이프라이닝 — 명령어 처리를 겹쳐 처리량을 높이는 방법과 그 한계를 봅니다.

비순차 실행 — 명령어 수준 병렬성을 끌어내는 또 다른 방법을 봅니다.

스레드 — 한 프로세스 안에서 일을 나눠 실행하는 단위를 봅니다.

프로세스 동기화 — 락과 임계 구역이 왜 직렬 부분이 되는지 봅니다.

참고 자료

암달의 법칙 원 발표 — Amdahl, "Validity of the single processor approach to achieving large scale computing capabilities", AFIPS Conference Proceedings (Spring Joint Computer Conference), 1967

구스타프슨의 법칙 — Gustafson, "Reevaluating Amdahl's Law", Communications of the ACM 31(5), 532-533, 1988

교재 — Hennessy, Patterson, "Computer Architecture: A Quantitative Approach", 6판(2017), 1장 "Fundamentals of Quantitative Design and Analysis"의 Amdahl's Law 설명

암달의 법칙 공식을 그대로 코드로

// Speedup(N) = 1 / ((1 - p) + p / N)
static double speedup(double p, int cores) {
    return 1.0 / ((1.0 - p) + p / cores);
}

speedup(0.8, 1);    // 1.00
speedup(0.8, 8);    // 3.33
speedup(0.8, 1024); // 약 4.98 — 상한 5.0에 수렴

병렬 비율 p가 0.8이면 코어를 1024개로 늘려도 5배를 넘을 수 없습니다. 코어를 8개에서 1024개로 128배 늘렸는데 속도 향상은 3.33배에서 4.98배로 늘어나는 데 그칩니다.

병렬 구간과 직렬 구간이 섞인 실제 코드

// 병렬 구간: 각 요소를 서로 독립적으로 처리 — 코어를 늘리면 빨라짐
long sum = data.parallelStream()
                .mapToLong(x -> heavy(x))
                .sum();

// 직렬 구간: 파일 쓰기처럼 순서대로 한 번에 하나씩 — 코어를 늘려도 그대로
writeResultToFile(sum);

heavy(x) 계산은 코어 수만큼 나눠 처리되지만, 결과를 파일에 쓰는 구간은 코어를 늘려도 줄지 않습니다. 이 직렬 구간이 전체 시간에서 차지하는 비율이 곧 1-p이고, 속도 향상의 상한을 결정합니다.

일부만 s배 빨라졌을 때 — 일반화된 형태

// 전체 중 비율 f 만 s배 빨라졌을 때의 전체 속도 향상
static double overall(double f, double s) {
    return 1.0 / ((1.0 - f) + f / s);
}

overall(0.4, 10); // 약 1.56 — 전체의 40%를 10배 빠르게 해도 전체는 1.56배

병렬화가 아니라 "특정 연산을 하드웨어로 가속" 같은 경우에도 똑같이 적용됩니다. 전체의 40%만 10배 빨라져도 나머지 60%가 그대로여서 전체 향상은 1.56배에 그칩니다.

병렬 비율이 p인 프로그램을 코어 N개로 실행할 때, 암달의 법칙에 따른 속도 향상(Speedup) 식은?

코어를 늘려도 나눠지지 않는 부분은 어느 쪽일까요?

직렬로 실행해야 하는 부분 (1-p)는 코어를 늘려도 그대로이고, 병렬화 가능한 부분 p만 N으로 나뉩니다. 그래서 Speedup = 1 / ((1-p) + p/N) 입니다.

병렬 비율 p=0.8인 프로그램을 코어를 무한히 늘려 실행할 때, 이론상 최대 속도 향상은?

N이 무한대가 되면 p/N은 0에 가까워집니다.

N → ∞ 이면 p/N → 0 이므로 Speedup의 상한은 1 / (1-p) 입니다. p=0.8이면 1 / 0.2 = 5배가 한계입니다.

암달의 법칙이 주는 교훈으로 옳은 것은?

코어를 계속 늘려도 남는 부분이 있습니다.

병렬화할 수 없는 직렬 구간은 코어를 늘려도 시간이 줄지 않으므로, 이 구간의 비율이 전체 속도 향상의 천장이 됩니다. 코어를 더 늘리기 전에 직렬 구간을 줄이는 것이 더 효과적일 수 있습니다.

병렬 비율이 0.9인 프로그램을 코어 10개로 실행할 때 속도 향상은 약 얼마일까?

1 / ((1 - 0.9) + 0.9 / 10) 를 계산해 보세요.

1 / (0.1 + 0.09) = 1 / 0.19 ≈ 5.26배입니다. 코어가 10개여도 직렬 10%가 남아 있어 10배에는 한참 못 미칩니다.