프로그램 중 병렬로 실행할 수 있는 부분의 비율과 프로세서(코어) 수를 입력하면, 암달의 법칙에 따라 프로그램 전체가 얼마나 빨라지는지 확인할 수 있습니다. 양대수 그래프에서는 문제 크기를 고정했을 때의 이 한계를, 프로세서 수에 맞춰 문제를 키우는 구스타프슨의 관점과 비교합니다.
가는 점선은 이상적인 선형 속도 향상(N배), 파란 선은 암달의 법칙, 초록 선은 구스타프슨의 법칙입니다. 두 축 모두 로그 눈금입니다. 통신, 동기화, 부하 불균형에 따른 오버헤드는 포함하지 않으므로 실제 속도 향상률은 보통 이보다 낮습니다.
다른 입력은 현재 값 그대로 두고, 선택한 입력만 현재 값의 1/4~4배 범위에서 바꿨을 때의 결과입니다. 빨간 점이 현재 값입니다.
프로세서 1개에서의 실행 시간을 1로 두고, 병렬화할 수 있는 부분의 비율을 p라고 합니다. 프로세서가 N개이면 병렬 부분은 p/N으로 줄어들지만 직렬 부분 (1 − p)는 그대로이므로, 속도 향상률은 S = 1/((1 − p) + p/N)입니다. N을 아무리 키워도 직렬 부분은 사라지지 않으므로 속도 향상률의 상한은 1/(1 − p)입니다. 기본값인 p = 95%, N = 16에서는 S ≈ 9.14이고 한계는 20입니다. 불과 5%의 직렬 처리가 프로그램이 도달할 수 있는 최고 속도를 결정합니다.
병렬 효율 E = S/N은 각 프로세서가 얼마나 유효한 일을 하는지를 나타냅니다. 기본값에서는 9.14 ÷ 16 ≈ 57.1%로, 처리 능력의 40% 이상이 사실상 놀고 있는 셈입니다. 그래프에서 파란 선은 N이 작을 때 이상적인 점선을 따라가다가 점차 벗어나 한계를 향해 평평해집니다. p = 95%를 유지한 채 N을 64로 늘리면 S ≈ 15.4이고 효율은 약 24%에 불과합니다. 효율이 급격히 떨어지기 시작하는 지점은 비용에 걸맞은 프로세서 수를 판단하는 실용적인 기준이 됩니다.
암달의 법칙은 프로세서를 늘리는 동안 문제 크기가 고정되어 있다고 가정하며, 이를 강한 스케일링이라고 합니다. 구스타프슨의 법칙은 반대로 프로세서 수에 맞춰 문제를 키우고 같은 시간 안에 푸는 경우로, 이를 약한 스케일링이라고 하며 S = (1 − p) + p·N이 됩니다. 예를 들어 시뮬레이션 격자를 세밀하게 하면 병렬 작업만 늘어나므로 속도 향상률이 거의 N에 비례해 커집니다. 여기서 p는 N개 프로세서로 실행했을 때 측정한 시간의 비율이므로, 암달의 법칙의 p와는 정의가 다르다는 점에 주의하십시오.
실제 프로그램에는 스레드 시작, 데이터 통신, 락과 배리어에서의 대기, 부하 불균형이 더해지므로 실제 속도 향상률은 암달의 법칙의 예측보다 낮아집니다. 코어를 늘리는 것보다 직렬 부분을 줄이는 편이 효과적인 경우가 많으므로, 먼저 프로파일링을 한 뒤 핫스폿을 병렬화하는 것이 일반적입니다. GPU에서는 호스트와의 데이터 전송과 커널 실행도 직렬 부분으로 작용합니다. 칩 설계에서는 소수의 고성능 코어와 다수의 소형 코어를 조합해 워크로드의 직렬 부분과 병렬 부분을 모두 빠르게 하는 방법이 쓰입니다.
정답: B. 1.6배
개선 후 시간은 빠르게 하지 않는 나머지 50%(0.5)와 4배 빠르게 한 50%(0.5÷4=0.125)의 합인 0.625가 됩니다. 속도 향상률은 1÷0.625=1.6배입니다. 빠르게 한 부분을 아무리 빠르게 해도 나머지 50%는 그대로 남으므로 전체는 최대 2배밖에 되지 않습니다. 전체를 크게 빠르게 하려면 시간을 많이 차지하는 부분을 찾아 개선해야 합니다.
정답: A. 시간을 많이 쓰는 부분(자주 있는 경우)을 빠르게 하는 것을 우선한다
전체의 1%밖에 사용하지 않는 부분을 무한히 빠르게 해도 전체는 약 1%밖에 빨라지지 않습니다. 반면 80%를 사용하는 부분을 2배 빠르게 하면 전체는 약 1.7배가 됩니다. 따라서 먼저 프로파일러 등으로 시간을 많이 쓰는 부분을 찾아 거기서부터 개선하는 것이 기본입니다. '자주 있는 경우를 빠르게 하라'는 컴퓨터 설계에서도 반복해서 쓰이는 원칙입니다.
암달의 법칙에 따르면 한계는 1/(1 − 0.9) = 10배입니다. 프로세서가 16개라도 속도 향상률은 1/(0.1 + 0.9/16) = 6.4에 그치며 효율은 40%입니다. 남은 10%의 직렬 처리를 줄이지 않는 한 속도 향상률은 결코 10을 넘을 수 없습니다.
아닙니다. 암달의 법칙은 문제 크기가 고정된 강한 스케일링을, 구스타프슨의 법칙은 프로세서 수에 따라 문제가 커지는 약한 스케일링을 다룹니다. 어느 관점이 맞는지는 같은 문제를 더 빨리 풀고 싶은지, 더 큰 문제를 같은 시간에 풀고 싶은지에 따라 달라집니다.
있습니다. 프로세서를 추가해 각 프로세서가 맡는 데이터가 캐시에 들어갈 만큼 작아지면 메모리 접근이 빨라져 초선형 속도 향상이 나타날 수 있습니다. 암달의 법칙은 이러한 효과를 모델링하지 않습니다.
암달의 법칙(Amdahl's Law) 구스타프슨의 법칙(Gustafson's Law) 속도 향상률(Speedup) 병렬 효율(Parallel Efficiency) 강한 스케일링(strong scaling) 약한 스케일링(Weak Scaling)