병렬화) Amdahl's law 와 Gustafson's law

프로그램 성능 높이기

Sequential 프로그램 실행 성능을 높이기 위해서 다음 같은 2 가지 접근법이 있다.

1. Sequential program optimization : 알고리즘 고도화, 불필요한 코드 제거, 컴파일러를 통한 최적화 등등
2. Parallelzation : multi-core CPU, GPU, FPGA, multi node system 등을 이용한 계산 병렬처리

일반적으로 프로그램의 성능 향상시키기 위해서는 Sequential 프로그램 최적화를 먼저 진행하고, 목표 성능이 달성되지 않았다면 병렬화를 진행한다.

이때 병렬화 시 미리 어느 정도 성능 향상을 달성할 수 있는 지 예측할 수 있는 2가지 법칙이 있다.

• 암달의 법칙 (Amdahl's law)
  • 일의 양이 정해졌을 때, 병렬화하면 이 일을 얼마나 빨리 처리할 수 있는가?
  • 즉 현재 프로그램이 최대한 얼마까지 빨라질 수 있는가?에 대한 답이다.
• 구스타프슨의 법칙(Gustafson's law)
  • 시간이 정해졌을 때, 병렬화하면 얼마나 많은 일을 처리할 수 있는가?
  • 즉 주어진 시간동안 프로그램이 얼마나 더 많은 계산을 할 수 있는가에 대한 답이다.

암달의 법칙 Amdahl's law

어떤 프로그램의 전체 실행 시간을 분석했을 때, 병렬로 처리되는 실행 시간의 비율을 P라고 하자. 그렇다면 병렬로 처리되지 않는 실행 시간의 비율을 (1-P)일 것이다.
이때 P 시간을 S개의 processor로 병렬처리(병렬처리 overhead가 없다고 가정)한다면 병렬로 처리되는 실행 시간은 P/S로 향상될 것이다. 즉 전체 프로그램의 실행 시간은 (1-P) + (P/S)로 줄어들 것이고, 이때의 병렬화 결과 프로그램의 speed-up은

 

암달의 법칙 공식

이 될 것이다.

예를 들어 병렬 처리 가능한 실행 시간 비율을 90퍼라고 하고, processor의 개수를 N라고 하자. 마찬가지로 병렬처리 overhead가 없다고 가정하고, 이 프로그램을 N개의 processor들로 병렬화할 경우 1 / (0.1 + 0.9/N)의 speed-up을 보인다.

N=2일때는 speed-up은 1/(0.1+0.9/2)=1.8
N=4일때는 speed-up은 1/(0.1+0.9/4)=3.1
N=8일때는 speed-up은 1/(0.1+0.9/8)=4.7
N=∞일때는 speed-up은 1/(0.1)=10

위 예제를 보면 알겠지만 사용되는 프로세서의 개수가 아무리 많아지더라도 성능 향상의 한계가 존재한다. 그래서 종종 암달의 저주라는 말을 쓰기도 한다. 밑의 그림은 이러한 암달의 저주를 잘 설명해준다.

 

병렬화 가능한 영역의 비율에 따른 성능 향상의 한계를 보여줌. 프로세서가 많아지더라도 결국은 성능 향상에 한계가 있음 [1]

구스타프슨의 법칙 Gustafson's law

암달의 저주에 따라 프로그램의 성능 향상에 한계가 존재한다면, GPU와 같은 수천개의 코어를 가진 하드웨어를 이용한 병렬화는 필요가 없는 것 아닌가? 라는 질문을 던질 수 있을 것이다.
하지만 암달의 저주는 일의 양이 정해질 경우에 성능의 한계가 있다는 것이다. 데이터 처리와 같이 빨리 계산하면 더 많은 일을 할 수 있는 애플리케이션의 경우에는 암달의 저주는 적용되지 않고, 더 많은 프로세서는 더 많은 성능 향상을 이끌어낼 수 있다. 대게 병렬화가 필요할 만큼의 애플리케이션은 단위 시간당 처리하는 일의 개수가 더 중요하기에 암달의 저주를 생각할 필요없이 더 많은 CPU, GPU, 더 큰 시스템을 빌드하여 사용하여도 된다.

이러한 개념을 법칙으로 나타낸 것이 구스타프슨의 법칙이다. 구스타프슨의 법칙은 다음과 같다.

 

구스타프슨의 법칙 공식 [2]

P는 프로세서의 개수, α는 병렬화 불가능한 코드의 실행 시간 비율, S는 speed-up을 의미한다. 이법칙에서 프로세서의 개수 P가 증가할수록 더 S(P)는 제한 없이 증가한다.

유도는 다음과 같다. a를 병렬화 불가능한 코드의 실행 시간, b를 P개의 processor로 병렬화한 영역의 실행시간이라 한다면, 병렬화 프로그램의 실행시간은 (a+b)이다. 만약 병렬화하지 않았다면 프로그램의 총 실행시간은 (a+P*b)일 것이다(b시간동안 P가 처리한 일을 1개가 처리하기에 b -> b*P 시간으로 늘어날 것이다.).
따라서 speed-up=(a+P*b)/(a+b)이며 α=a/(a+b)라 치환하여 정리하면 위 법칙을 유도할 수 있다.

Reference

[1] https://ko.wikipedia.org/wiki/%EC%95%94%EB%8B%AC%EC%9D%98_%EB%B2%95%EC%B9%99
[2] https://ko.wikipedia.org/wiki/구스타프슨의_법칙