5. 병렬 프로그램의 성능 평가 (Performance)

* Speedup 과 Efficiency란?

어떤 문제를 푸는 순차프로그램과 병렬프로그램이 있다고 하자. 병렬프로그램이 순차 프로그램보다 몇 배나 더 빨리 실행되었는가를 나타내는 척도가 speedup이다. effiency는 전체 시스템이 몇 %정도 효율을 올렸는가를 나타내는 척도이다. 

Speedup	S = Ts / Tp
Efficiency	S / p

• p = 코어 혹은 프로세서의 수
• Ts = 순차 프로그램 런타임
• Tp = 병렬 프로그램 런타임

만약 병렬 프로그램의 speedup이 실행에 사용한 프로세서 개수와 같을 때(p=S), 그 프로그램은 linear speedup을 낸다고 한다. 즉, 사용하 프로세서 개수에 선형적으로 비례하여 속도가 향상된다는 것이다. 하지만 일반적으로 프로세스의 개수가 증가할 수록 speedup과  efficiency는 상대적으로 감소한다. 프로세서 개수가 증가하면 프로세서 사이의 통신 오버헤드도 증가하기 때문이다.  단, problem의 크기가 커질수록 프로그램의 speedup은 상대적으로 증가한다. 통신 등에 드는 오버헤드에 비해 계산량이 증가하여 효율이 좋아지는 것이다. 

 

병렬 프로그램 실행시간 Tp =  Ts / p + T overhead

병렬 프로그램의 실행시간은 순차프로그램을 여러 프로세스가 나누어서 일을 하는데 드는 시간에 오버헤드를 더하여 계산한다.  만약 linear speedup인 경우에는 maximum speedup인 p가 될 것이다. 하지만 메모리가 추가되거나 nonderministic algorithm을 푸는 경우에는 p보다 더 높은 speedup을 가지는 superlinear speedup이 나타날 수도 있다. 

EX) 순차탐색의 경우 순차 프로그램은 x*Ts/p +Dt 의 시간이 걸리지만 병렬 프로그램은 Dt의 시간만 걸리므로 superlinear speedup이 나타난다. 

 

1. 암달의 법칙 (Amdahl's Law)

암달의 법칙

S(p)= ts / fts+ (1-f)ts/p

=  p/1+ (p-1)f

암달의 법칙은 negative하게 측정하는 방법으로, 순차 프로그램 전체가 병렬화되지 않는다면, 사용가능한 프로세서의 개수에 상관없이 가능한 성능 향상은 매우 제한적이다라는 입장에서 정리된 법칙이다. 

 

2. Gustafson의 법칙 ( Scaled Speedup)

암달의 법칙보다 speedup을 좀더 positive하게 측정하는 법칙이다. 여기서는 2가지 가정을 해야한다. 

1) 병렬 프로그램의 실행시간을 고정해보자. (constant = 1)

2) 순차프로그램에서 순차적으로 실행되어야하는 부분도 코어개수p와 상관없이 고정적이다. 

S(p) = fts+ (1-f)ts*p /1