구스타프슨의 법칙

구스타프슨의 법칙(Gustafson's Law)은 컴퓨터 과학에서 대용량 데이터 처리는 효과적으로 병렬화할 수 있다는 법칙이다. 구스타프슨-바시스의 법칙(Gustafson-Barsis' law)으로도 알려져 있다. 구스타프슨의 법칙은 병렬화로 얻을 수 있는 프로그램의 성능 향상은 프로그램의 순차적인 부분에 의해 제한된다는 암달의 법칙에 대한 반대 개념이다. 구스타프슨의 법칙은 처음에 존 구스타프슨과 동료인 에드윈 바시스에 의해서 처음 발표되었다.

여기서 P는 프로세서의 수이며 S는 성능향상, 는 어떤 병렬 프로세스에서 병렬화 되지 않는 순차적인 부분의 비를 말한다.

구스타프슨의 법칙은 암달의 법칙이 가지고 있는 단점 - 컴퓨터의 수가 증가함에 따라 가용한 계산 능력을 활용하지 않는다 - 에 대한 해법을 제시했다. 구스타프슨의 법칙은 실질적으로 대용량 문제를 풀기 위해 제한된 시간안에 가용한 장비가 풀 수 있는 문제의 크기를 프로그래머가 정해야 한다고 제안을 한다. 이후, 더욱 더 빠르거나 또는 더욱 더 병렬화 처리를 잘하는 컴퓨터가 나오면 더 큰 문제도 주어진 동일한 시간안에 풀 수 있다는 것이다.

그리하여, 구스타프슨은 그의 공식을 Scaled Speedup이라고 불렀다. 왜냐하면 위 식에서 S(P)는 단일 프로세스의 총 실행 시간 대비 프로세스당 병렬 처리 시간의 비율이기 때문이다. 단일 프로세스 실행 시간은 P에 비례하지만 프로세스당 병렬 처리 시간은 거의 고정되었다고 가정한다. 이것은 단일 프로세스 실행 시간은 데이터 처리 양에 고정되었다고 생각하며 단축된 단일 프로세스당 실행시간과 비교하는 암달의 법칙과는 반대이다. 따라서 암달의 법칙은 문제 크기가 고정되었다는 가정에 설립된 법칙으로 전반적인 프로그램의 작업부하는 컴퓨터 머신의 크기에 따라 변하지 않는다고 가정한다. 두 법칙은 병렬화되는 부분은 P 프로세서들에 고르게 분산된다고 가정한다.

구스타프의 법칙으로 문제들을 해결하는 방식이 처리가 어려운 대용량 문제를 처리 가능한 문제 크기로 정하거나 가공하여 주어진 동일한 시간안에 풀 수 있도록 바뀌게 되었다.

구스타프슨의 법칙 유도
병렬 컴퓨터에서의 프로그램 실행 시간은 아래와 같다.

여기서 는 순차적인 시간이며 는 어떤 P 프로세서들에서의 병렬 시간이다.(오버헤드는 무시되었음)

구스타프슨의 주요 가정은 병렬적으로 실행되는 총 작업 시간은 프로세서들의 수에 따라 선형적으로 변한다라는 것이다.
프로세스당 병렬 처리시간 b는 P가 변해도 고정되어야 하며 순차적 처리에 걸리는 시간은 아래와 같다.

따라서 속도 향상은 아래와 같다.

병렬 처리에서 순차적인 처리 부분의 비율을
 로 정의하면

이다.

따라서 만약 순차적 처리 비중인  이 작다면 속도 향상은 대략 P이고 더욱이 문제의 크기가 증가함과 함께 P가 증가하면 는 P가 된다.

같이 보기 
 암달의 법칙

참조 

병렬 알고리즘 분석