구스타프슨의 법칙

3. 유도

병렬 컴퓨터에서 프로그램 실행 시간은 다음과 같이 표현된다.

:$(a\; +\; b)$

여기서 $a$는 순차적인 처리 시간, $b$는 $P$개의 프로세서에서의 병렬 처리 시간이다. (오버헤드는 무시)

구스타프슨은 병렬 처리되는 총 작업 시간이 프로세서 수에 따라 선형적으로 변한다고 가정했다. 즉, 프로세서당 병렬 처리 시간 $b$는 $P$가 변해도 고정되어야 하며, 순차적 처리 시간은 다음과 같다.

:$a\; +\; P\backslash cdot\; b$

따라서 속도 향상은 다음과 같이 계산된다.

:$(a\; +\; P\backslash cdot\; b)/(a+b)$

병렬 처리에서 순차적인 처리 부분의 비율을 $\backslash alpha\; =\; a/(a+b)$로 정의하면, 다음 식을 얻을 수 있다.

:$S(P)=\; \backslash alpha\; +\; P\backslash cdot(1-\backslash alpha)\; =\; P\; -\; \backslash alpha\backslash cdot(P-1)$

이 식에 따르면, 순차적 처리 비중($\backslash alpha$)이 작다면 속도 향상은 대략 $P$에 근접한다. 또한 문제 크기가 증가함에 따라 $P$가 증가하면 $\backslash alpha$는 $P$가 된다.

병렬 시스템에서 실행되는 프로그램의 실행 시간은 프로세서 수 증가의 이점을 얻지 못하는 직렬 부분과 이점을 얻는 병렬 부분으로 나눌 수 있다.

예를 들어, 디스크에서 파일을 처리하는 컴퓨터 프로그램을 생각해 보자. 프로그램의 일부는 디스크의 디렉토리를 스캔하여 메모리에 파일 목록을 생성하고, 다른 부분은 각 파일을 별도의 스레드로 전달하여 처리한다. 디렉토리를 스캔하고 파일 목록을 생성하는 부분은 병렬 컴퓨터에서 속도를 높일 수 없지만, 파일을 처리하는 부분은 속도를 높일 수 있다.

병렬 시스템에서의 총 실행 시간을 $T\; =\; 1$로 설정하고, 직렬 시간을 $s$, 병렬 시간을 $p$로 표시하면, $s\; +\; p\; =\; 1$이다. 프로세서 수를 $N$으로 표시한다.

직렬 시스템(하나의 프로세서)에서 프로그램을 실행하면 직렬 부분은 $s$, 병렬 부분은 $Np$가 걸린다. 따라서 직렬 시스템에서의 실행 시간은 다음과 같다.

:$T\text{'}\; =\; s\; +\; Np$

$T\text{'}$를 기준으로 병렬 시스템의 속도 향상은 다음과 같다.

:$S\; =\; \backslash frac\{T\text{'}\}\{T\}\; =\; \backslash frac\{s\; +\; Np\}\{s\; +\; p\}\; =\; \backslash frac\{s\; +\; Np\}\{1\}\; =\; s\; +\; Np$

$p\; =\; 1\; -\; s$ 또는 $s\; =\; 1\; -\; p$를 대입하여 이전 섹션의 여러 형태를 도출할 수 있다.

문제의 크기를 나타내는 양을 $n$이라고 하면, 병렬 컴퓨터 상에서의 프로그램 실행은 다음과 같이 분해할 수 있다.

:$a(n)\; +\; b(n)\; =\; 1$

여기서 $a$는 직렬적인 부분의 비율, $b$는 병렬적인 부분의 비율이다. (오버헤드는 무시)

직렬적인 컴퓨터에서는 $p$를 병렬화했을 때의 프로세서 수라고 하면, 상대적인 처리 시간은 $a(n)\; +\; p\; \backslash cdot\; b(n)$이다.

즉, 속도 향상은 직렬적인 경우의 $a(n)\; +\; b(n)\; =\; 1$에 대해 병렬화했을 경우에는 $(a(n)\; +\; p\; \backslash cdot\; b(n))$이므로 다음과 같다.

:$S\; =\; a(n)\; +\; p\; (\; 1\; -\; a(n)\; )$

여기서 $a(n)$은 직렬적인 부분의 비율을 나타내는 함수이다.

직렬적인 함수 $a(n)$이 문제의 크기 $n$에 따라 감소한다고 가정하면, 속도 향상은 $n$이 무한히 커지면 원하는 대로 $p$에 도달한다.

구스타프슨의 법칙은 암달의 법칙의 한계로부터 병렬 컴퓨팅을 구해낼 수 있는 것처럼 보인다.

이러한 차이는 구스타프슨의 법칙은 방대한 수의 병렬 계산기를 사용해도 직렬적인 부분에 주는 영향이 없고, 따라서 그 부분의 크기는 일정하다고 생각하는 반면, 암달의 법칙은 프로세서의 수가 증가함에 따라 직렬적인 부분의 영향이 증가한다는 생각에서 비롯된다.

4. 비유

5. 응용

연구 분야에서는 더 많은 컴퓨팅 성능을 통해 데이터를 더 정밀하고 완전하게 분석할 수 있다. 예를 들어, 더 많은 변수를 고려한 핵폭발 시뮬레이션이 가능하다. 이전에는 핵 폭발이 모든 건물, 자동차 및 그 내용물(가구, 구조 강도 등 포함)에 미치는 영향을 시뮬레이션하는 것이 불가능하거나 실용적이지 않았지만, 컴퓨팅 성능이 증가함에 따라 연구자들은 더 많은 데이터를 추가하여 더 완벽하게 시뮬레이션하고 더 정확한 결과를 얻을 수 있게 되었다.^[1]

일반 컴퓨터 시스템에서는 컴퓨팅 성능 향상에 따라 시스템의 기능과 성능을 향상시킬 수 있다. 예를 들어, 대부분의 사용자에게 1분 부팅 시간이 허용 가능하다면, 운영 체제 부팅에 걸리는 시간은 동일하게 유지하면서 더 많은 그래픽 또는 사용자 친화적인 기능을 포함할 수 있다.^[1]

한국의 경우, 대규모 데이터를 활용하는 인공지능, 빅데이터 분석, 과학기술 연구 등 다양한 분야에서 구스타프슨의 법칙을 적용하여 더 높은 수준의 연구 성과를 얻을 수 있다.

해결하려는 문제에 따라 본질적으로 대규모 데이터 세트를 갖지 못하는 경우가 있다. 예를 들어, 전 세계의 모든 사람에 대해 하나씩 존재하는 데이터를 처리하는 문제는 연간 몇 퍼센트밖에 커지지 않는다.^[1]

비선형 알고리즘은 구스타프슨의 법칙에 의해 "분명하게" 드러나는 병렬성을 잘 활용하지 못하는 경우가 있다. 스나이더(Snyder)는 O(N³) 알고리즘에서는 병렬성을 두 배로 늘려도 문제 크기를 9% 증가시키는 것밖에 안 된다고 지적했다. 따라서 매우 높은 병렬성을 실현하더라도 원래의 병렬화 정도가 적은 방법에 대해서는 별다른 이점이 없을 수 있다. 하지만 실제로는 특히 클러스터나 콘도르와 같은 분산 컴퓨터를 사용함으로써 큰 진보가 이루어지고 있다.^[1]

6. 한계

일부 문제는 근본적으로 더 큰 데이터 세트를 가질 수 없다. 예를 들어, 세계 시민 1인당 하나의 데이터 포인트를 처리하는 것은 연간 몇 %씩만 증가한다. 구스타프슨의 법칙의 요점은 이러한 문제가 병렬 처리의 가장 유망한 응용 분야가 아닐 가능성이 높다는 것이다.

비선형 알고리즘은 구스타프슨의 법칙에 의해 "노출된" 병렬 처리를 활용하기 어려울 수 있다. 스나이더^[3]는 $O(N^3)$ 알고리즘은 동시성을 두 배로 늘려도 문제 크기가 약 26%밖에 증가하지 않는다는 점을 지적한다. 따라서 광대한 동시성을 차지하는 것이 가능할 수 있지만, 그렇게 하는 것은 원래의 덜 동시적인 솔루션에 비해 이점이 거의 없을 수 있다. 그러나 실제로는 상당한 개선이 이루어졌다.

힐과 마티^[4]는 멀티코어 머신에서도 순차적 실행 속도를 높이는 방법이 여전히 필요하다고 강조한다. 그들은 지역적으로 비효율적인 방법이 순차적 단계를 줄일 때 전체적으로 효율적일 수 있다고 지적한다. 또한, 우와 리^[5]는 암달의 법칙을 기반으로 미래의 많은 코어 프로세서에 대한 에너지 및 전력의 영향을 연구하여, 실행 전에 병렬 처리 양이 알려진 경우 비대칭 많은 코어 프로세서가 최적의 코어 수를 활성화하여 최상의 에너지 효율을 달성할 수 있음을 보여주었다.

알-하야니, 라피예프 등^[6][7]은 코어 이질성의 일반적인 표현을 기반으로 한 새로운 속도 향상 및 에너지 소비 모델을 개발했으며, 이를 정규 형태 이질성이라고 하며, 광범위한 이질적 많은 코어 아키텍처를 지원한다. 이러한 모델링 방법은 시스템 전력 효율성 및 성능 범위를 예측하는 것을 목표로 하며, 하드웨어 및 시스템 소프트웨어 수준에서 연구 개발을 촉진한다.

참조

_[1] 서적 Structured Parallel Programming: Patterns for Efficient Computation Elsevier
_[2] 논문 Reevaluating Amdahl's Law http://www.johngusta[...] 1988-05
_[3] 논문 Type Architectures, Shared Memory, and The Corollary of Modest Potential http://www.cs.washin[...] 1986-06
_[4] 논문 Amdahl's Law in the Multicore Era http://www.cs.wisc.e[...] 2008-07
_[5] 논문 Extending Amdahl's Law for Energy-Efficient Computing in the Many-Core Era 2008-12
_[6] 논문 Speedup and Power Scaling Models for Heterogeneous Many-Core Systems https://eprint.ncl.a[...] 2018-07-01
_[7] 논문 Amdahl's law in the context of heterogeneous many-core systems – a survey 2020-07
_[8] 간행물 Reevaluating Amdahl's Law http://citeseerx.ist[...] 1988