병렬 처리 관련 법칙들

 "모든 컴퓨터 아키텍트들은 암달의 법칙을 알고 있다. 그럼에도 불구하고, 우리는 때때로 불가능한 성능 최적화를 위해 막대한 노력을 기울인다. 그리고, 전체 속도향상이 실망스러운 수준임을 확인했을 때에서야 비로소 암달의 법칙을 떠올린다."-In  Computer Architecture: A Quantitative Edition, 4th ed.  John L. Hennessy and David A. Patterson 

"모두들 암달의 법칙을 알고 있지만, 금방 잊어버린다!" - Thomas Puzak

  병렬 처리에 있어 중요한 비교척도로는 속도향상과 효율성이 존재한다. 1개의 프로세서 또는 1개의 노드 추가로 이루어지는 어떠한 알고리즘의 속도향상(speedup)은 다음과 같이 계산된다.

  (식 1)

 여기에서,  n는 프로세서의 수 또는 노드의 수, T₁은 직렬 알고리즘의 실행 시간,   T_n 는 n 개의 프로세서 또는 노드를 이용한 병렬 알고리즘의 실행 시간을 의미한다.  속도 향상은 다시 크게 절대 속도향상(absolute speedup)과 상대 속도향상(relative speedup)으로 나뉘는데, 절대 속도 향상은 T₁ 이 가장 최적의 직렬 알고리즘(best sequential algorithm)의 실행 시간인 반면에, 상대 속도 향상에서는   T₁ 이 병렬 알고리즘을 한 프로세서에서 실행된 시간이다. 보통 속도향상을 얘기할 때는 상대 속도향상을 의미한다.

효율성(Efficiency)은 한 프로세서 또는 노드가 병렬 처리를 위해 얼마나 잘 활용되는지를 비교하는데 이용된다. 

 (식 2) 

 이상적으로는 병렬 처리에서 속도 향상은 추가되는 n 개의 프로세서 또는 노드의 수에 따라 선형(linear)으로 증가한다. 즉, Speedup(n) = n이 된다.  이 경우 효율성은 1이 된다. 하지만 실제로는 I/O, 네트워크 대역폭(bandwidth), 지연시간(latency) 등 여러 이유로 1이 되지 못한다. 가장 대표적인 이유는 알고리즘의 모든 부분을 병렬화(parallelize) 시킬 수가 없기 때문인데, 이 알고리즘에 남아있는 직렬 처리 부분은 모든 알고리즘의 병렬화의 한계를 결정한다. 이는 암달의 법칙(Amdahl's law)으로 설명된다.  

  



Amdahl's law^[각주:1]

 암달의 법칙은 1967년 한 컨퍼런스에서 IBM의 Gene Amdahl이 논한 것으로, 이 공식은 어떤 시스템의 f  비율만큼의 부분이 S만큼 속도향상이 있을 때, 최대로 얻을 수 있는 이상적인 속도향상은 다음과 같이 제약됨을 설명한다. 또한, 여기에서는,  프로그램 수행을 통해 풀고자 하는 문제의 크기가 특정 부분의 속도 향상의 전후에도 언제나 동일한 것으로 가정한다.

 식(3)

1) 만약 속도향상을 이룬 부분이 작다면 (f값이 작다면), 전체 시스템의 속도향상은 미미하다.

2) 만약 f 부분의 속도향상을 무한대(S →∞)로 할 수 있다면, 전체 시스템의 속도향상은 1/(1-f)로 수렴될 수 있다.

예를 들어 전체 시스템의 20%를 2배만큼 속도향상을 시킬 수 있다면, 이로 인해 얻을 수 있는 전체 시스템의 속도향상은:

 (식 4)

로 제한된다. 이 암달의 법칙은 어떠한 프로그램을 병렬화할 때 얻을 수 있는 최대한의 속도향상을 예측하는데 이용되기도 하는데, 이 때는 아래와 같은 형식으로 표현될 수 있다. 

 (식5)

여기에서 f는 프로그램에서 병렬화된 부분을 n은 프로세서 또는 노드의 수를 의미한다.

먼저, 한 프로그램을 하나의 프로세서 또는 노드로 수행시켰을 때의 실행 시간을 1로 한다. 

다음으로 프로그램의 일정 부분 f를 n개의 프로세서나 노드로 병렬화하여 처리한다면, 이 f의 실행 시간은  f/n만큼의 시간이 들게 될 것이다. 반대로, 남은 부분 1-f는 한개의 프로세서 또는 노드로 수행하기 때문에 그대로 원래 만큼의 시간이 소요된다. 즉, 프로그램의 일정 부분 f를 n개의 프로세서나 노드를 이용하여 병렬화하는 경우 전체 수행 시간은 1-f+f/n만큼 소요되고, 이를 원래 시간 1과 비교하면 위의 식 5만큼의 성능 개선이 있다고 설명할 수 있다.

예를 들어, 만약 f=1, n=16, 즉 프로그램의 모든 부분이 병렬화되어 있고,  16개의 프로세서를 이용해 병렬 처리한다면, 속도향상은 16배가 될 것이다. 그리고, 이 경우 효율성은 1(=16/16)이 된다.  하지만, 프로그램의 모든 부분을 병렬화 할 수는 없다. 이런 이유로 실제 프로세서나 노드 수를 늘린다고 해도, 어느 수준 이상에서는 속도향상을 기대할 수 없다.  아래 그림은 암달의 법칙에서 프로세서의 증가에 따른 속도 향상의 한계를 보인다. 

Figure 1a.

그래프를 보면 프로그램의 95%(f=0.95)가 병렬화 되어 있다고 해도, 16개의 프로세서를 가지고 10배 이상의 속도향상을 내지 못한다.  이후로는 아무리 많은 수의 프로세서를 가진다 해도 20배 이상의 속도향상을 낼 수가 없다.  즉, 병렬화 되지 않은 부분이 많을수록 속도향상은 더 적다. 50%의 병렬화를 통해 16 프로세서를 가지고 얻을 수 있는 속도향상은 2배 밖에 되지 못한다. 실제로 프로그램 상에 남아있는 직렬 실행 부분의 비율은 아래 그래프와 같이 병렬화를 통해 얻을 수 있는 속도향상을 제약한다.

Figure 1b.

이러한 이유로 병렬 처리에서 있어서는 프로그램의 직렬화 부분(1-f)를 얼마만큼 줄이느냐, 다른 말로 병렬화 부분(f)을 얼마나 늘이느냐 것이 관건이 되어 왔다. 또한, 실제로는 모든 부분을 병렬화할 수 없기 때문에, 프로세서 수를 계속 늘려도 병렬화의 이점을 추가로 가질 수가 없다. 이에 따라서 병렬 처리는 보통 소수의 프로세서를 가지고서 병렬 처리를 해 왔다.  프로그램의 병렬 부분과 속도향상과의 관계는 위 식에 의해 아래와 유도가 가능하다.

 (식 6)

Gustafson's law^[각주:2]

 구스타프슨의 법칙은 1988년 Sandia national Lab에 있던 John Gustafson이  고안한 것으로  규모가 충분히 큰 문제들은 효과적으로 병렬화가 가능함을 기술하고 있다. 이는 암달의 법칙이 병렬화를 통해 일정 수준 이상의 속도향상을 기대할 수 없다고 얘기하는 것에 배치되는데, 그렇다고 암달의 법칙이 틀렸다는것은 아니다. 암달의 법칙은 계속 유효하다. 이 법칙은 아래와 같이 표기된다.  

 (식 7)

 여기에서 n은 프로세서 또는 노드의 수, α는 프로그램에서 병렬화되지 않은 부분을 의미한다(, α= 1-f).

이 법칙에 따르면, 만약 n=16이고 α=0.05이라면(95%가 병렬화 되어 있다면), 얻을 수 있는 속도향상은 15.25배(16-0.05*15) 이다. 이는  동일한 조건에서 속도향상은 10배를 넘지 못한다는 암달의 법칙과 상반된다. 이 이유는 무엇인가?

 암달의 법칙이 병렬 처리에 있어 병렬화 전후의 문제 크기는 변하지 않는 것을 가정하는데 반해, 구스타프슨의 법칙은 고정된 처리 시간 개념을 도입하여 보다 큰 문제에 대한 속도향상을 설명한다. 

 즉, 암달의 법칙에서는 고정된 문제 크기를 갖는다고 가정하였는데, 이는 프로세서 수의 증가에 상관없이 문제 크기는 증가하지 않는 것을 기초로 출발하였다.  아래의 그림을 보자.

 그림과 같이 직렬 시스템에서 프로그램을 실행하는데 걸린 시간은 프로그램의 직렬 부분 s와 병렬화 가능한  부분 p의 실행 시간으로 구성된다. 즉, s+p=1 이 병렬화 이전에 소요된 시간이다. 그리고 병렬화를 통해 얻어진 실행시간은 s+p/N이다. 여기에서 N은 프로세서의 수이다. 따라서 전체 속도향상은 식 1에 따라

1/(s+p/N)이 된다. s를 1-f라 하고 p를 f로 치환하면 위의 암달의 법칙(식 5)와 동일한 수식을 얻게 된다.

 반대로, 구스타프슨의 법칙은 주어진 시간 내에 보다 많은 크기의 문제를 해결하는 경우 병렬화가 효과적인 방법이 됨을 설명한다. 아래 그림을 보자 .  

 여기에서는 프로그램을 병렬화하였을 때의 실행 시간을 s+p=1로 하고, 이를 기준으로 프로그램의 직렬 시간과 비교한다. 즉 여기에서 속도향상은 식 1에 따라 s+Np가 된다. 여기에서 s를 α로, N을 n으로 치환하면, 식 7의 구스타프슨 법칙과 같게 된다. 즉 구스타프슨의 법칙은 주어진 시간에 병렬화로 임의 크기의 문제를 해결할 수 있을 때, 직렬 프로그램 실행 시간과의 비교를 통해 속도향상을 측정하는 반면에, 암달의 법칙은 직렬 실행 시간을 기준으로 병렬화를 수행하였을 때 얼마만큼의 속도향상이 있는지를 보인다는 점이 다르다. 병렬화 가능한 부분의 문제 크기가 클수록 구스타프슨 법칙에 따르면, 속도향상이 높게 나올 수 있다. 왜냐하면 문제 크기에 따라 더 많은 프로세서 할당을 통해 병렬 실행 시간 값(p)을 고정시킬 수 있기 때문이다. 예를 들어, 병렬가능한 문제 크기가 100이면, 100개의 프로세서로 할당하면 p=1이 된다. 1000이면, 1000개의 프로세서를 할당해서 p=1로 떨어지게 한다. 반대로 암달의 법칙은 문제 크기와 상관없이 고정된 제한 속도향상 값을 갖는다. 

 자동차를 가지고 두 법칙을 비유하자면, 

1) 자동차로 120Km 떨어진 도시로 이동한다고 하자. 그리고, 60Km/h의 속도로 한시간을 이미 이동하였다. 이제 나머지 절반의 거리를 아무리 빠르게 운전한다 하더라도, 출발지에서 목적지까지의 자동차의  평균 시속은   120Km/h를 넘을 수 없다. 이미 이동하는데 한시간을 써버렸고 아직 60Km의 이동 거리가 남아 있기 때문에 자동차가 남은 거리를 무한대의 시속으로 이동한다 하더라도, 이미 지나간 시간은 돌아오지 못하기 때문이다. (암달의 법칙)

2)  자동차로 120Km/h보다 낮은 속도로 이동하고 있었다고 하자. 남은 시간과 남은 이동거리가 충분하다면, 이전까지 얼마나 많이, 또 얼마나 천천히 운전했냐에 상관없이 자동차의 평균 시속은 120Km/h를 넘을 수 있다. 만약 60Km/h의 속도로 자동차를 한 시간 동안 운전했다면,  이 후 한 시간을 180Km/h 로 운전하거나 또는  150Km/h로 두 시간을 운전한다면, 총 이동 거리에 대한 평균 시속은 120Km/h에 도달하게 된다. (구스타프슨의 법칙)

Karp-Flatt metric^[각주:3]

 카프-플랫 척도는 1990년에 Alan H. Karp와 Horace P. Flatt에 의해 병렬 프로세서 시스템에서 코드의 병렬화를 측정하기 위해 고안되었다. 이 식은 측정된 속도향상 값을 가지고, 프로그램의 직렬화 부분의 비율을 찾아내는데 효과적이다. 암달이나 구스타프슨의 법칙은 실제 병렬 처리에 있어 스케쥴링, 프로세서간 통신 비용이나 프로세스간 동기화에 소비되는 비용, 프로세서간 불균형한 작업량 등을 고려하지 않는 이상적인 법칙이다. 반면에 이 척도는 실제 실험 결과를 대상으로 직렬화 부분의 비율을 계산할 수 있게 해준다.

 (식 7)

예를 들어, 1개의 프로세서를 가지고 프로그램을 실행하였을 떄 측정된 실행 시간이 5분(T1-5min)이 걸렸고, 10개의 프로세서(n=10)을 가지고 프로그램을 병렬화하였을 때 실행 시간이 1분이 걸렸다면(Tn=1min), 

 (식 8)

으로 해당 코드의 직렬 실행 부분은 1/9(약 11.1%) 임을 식을 통해 유도할 수 있다.  

Superlinear Speedup

  암달의 법칙에 따르면, 병렬화를 통해 얻을 수 있는 속도향상은 선형 이상이 될 수가 없다. 하지만, 특정한 경우에 프로그램의 병렬화는 초선형(superlinear)의 속도향상을 보이기도 한다. 즉, n개의 프로세서로 병렬화를 하였을 때 n배를 초과한 속도 향상이 나오기도 한다. 이렇다고 암달의 법칙이 틀렸다고 할 수는 없다. 다만 암달의 법칙이 초선형의 속도 향상을 보이기도 하는 이유를 설명하지 않는다 정도로 해석하는 것이 맞다. 초선형의 속도향상이 가끔씩 발생하는 이유 중 가장 큰 이유는 메모리 계층 상의 캐시 히트 때문이다.  즉 데이터 처리에 있어 이전에 이용되었던 데이터가 캐시에 남아 있어 메모리나 디스크 IO 없이 빠르게 처리된 경우에는 가끔씩 이런 경우가 목격된다.

  또 다른 이유로는 데이터의 공간 복잡도에서 발생하기도 한다. 예를 들어 x개의 입력을 가지고 2^x의 처리 데이터를 작성하는 시스템이 있다고 하자. 이 데이터를 n개의 프로세서에 분할 할당한다고 하면, 각 프로세서는  2^x/n  크기의 데이터를 처리할 것이다. 하지만 입력 자체를 n개로 나누어 처리 데이터를 작성한다면, 각 프로세서에 할당되는 데이터의 크기는   2^x/n으로  2^x/n 보다 훨씬 작게 된다. 병렬 처리 알고리즘의 복잡도가 선형이라면, 그만큼 병렬 실행 시간도 초선형으로 줄어들 수 있다.

 

Acknowledgement

그림 1a.는 Wikipedia의 암달의 법칙에서, 1b.~2b.는 참고문헌 [2]의 논문에서 발췌하였음. 식들은 모두 Online LaTeX Equation Editor를 이용해 작성되었음.

Written by bart7449

1. Amdahl, G.M. Validity of the single processor approach to achieving large scale computing capabilities, In AFIPS Conference Proceedings, Vol. 30 (Atlantic City, NJ Apr. 18-20). AFIPS Press, Reston, Va., 1967, pp. 483--385 [본문으로]
2. Gustafson, J.L, Reevaluating Amdahl's law, Communications of ACM , May 1988 Vol. 31, No. 5 pp.532--533 [본문으로]
3. Karp Alan H. and Flatt Horace P. Measuring Parallel Processor Performance, Communications of ACM, Vol 33, No. 5, May 1990 [본문으로]