병렬 컴퓨터의 시간 계산, 암달의 법칙(Amdahl's Law)

암달의 법칙(Amdahl's law)은 미국의 컴퓨터 공학자이자 기업가였던 진 암달(Gene Amdahl)이 만든 법칙으로 암달의 저주(Amdahl's curse), 암달의 인수(Amdahl's argument)라고도 불린다.

진 암달(Gene Amdahl, 1922년 11월 16일 ~ 2015년 11월 10일)은 위스콘신 대학교 매디슨에서 이론물리학 석박사를 취득했고, 52년에 IBM으로 입사해 704 메인프레임, 시스템 360 메인프레임 등의 개발을 총괄하기도 했다. 암달의 법칙은 1965년 옮긴 어드밴스드컴퓨팅시스템랩에서 만든 것으로 컴퓨터 성능 최적화의 한계점을 측정하기 위해 만든 법칙이다.

Gene Amdahl

암달의 법칙의 병렬 프로세스 성능 관점

암달의 법칙은 현재도 많이 쓰이며, 일반적으로 서버를 추가할 때 얼마만큼의 속도 향상이 있을 것인지 등을 체크하기 위해서 많이 활용한다. 

우리가 대규모의 연산이 필요하여, 병렬프로그램을 만들어야 한다고 가정을 해보자. 그러나 필연적으로 들어가는 것이 있는데 바로 절대적인 직렬(Serial) 시간이라는 것이다.

예를 들어, 병렬 프로그램을 가동하기 전에 데이터를 읽는다던지, 초기화 작업을 한다던지 등등 이러한 직렬 프로그램은 서버를 확충해도 절대적인 시간을 잡아먹게 된다.

<그림 1> CPU가 1개이며 병렬 처리가 없을 때

하나의 예로 <그림 1>을 보면 데이터 수집에 10이라는 시간이 분석에 20, DB 저장에 10이라는 시간이 들어갔다고 가정 하였다. 여기서 병렬을 수행할 수 있는 부분이 분석이라고 할 때, 우선 CPU를 한개 더 늘릴 경우 다음과 같을 것이다.

<그림 2> CPU가 2개이며 병렬 처리를 했을 때

<그림 1>의 프로그램 속도는 40이고, CPU가 1개 더 늘어 2개일 때 속도의 향상은 30이 되었다. 그러나 많은 사람들은 컴퓨터의 성능이 2배 늘어날 경우 속도 역시 2배가 줄어들거라 착각하는 사람들이 많다. 즉 일반적인 사람들은 속도는 40 -> 20으로 줄어든다 생각하는 것이다.

이렇게 암달이라는 법칙은 직렬 프로그램이 어쩔 수 없이 존재하는 한, 아무리 병렬로 컴퓨터 성능을 향상시켜도 성능이 향상되는 한계가 존재한다는 의미이다. 

<그림 3> CPU를 무한대로 늘렸을 경우

<그림 3>을 보면 쉽게 이해할 수 있겠지만, CPU를 아무리 많이 늘려도 DB 저장과 데이터 수집이라는 직렬 프로세스 때문에 20이라는 시간은 먹고 들어가게 된다. 한마디로 이와 같은 상황에서는 20 + α(병렬 분석 시간) 이라는 공식이 만들어지게 되는 것이다.

암달의 법칙 계산

시스템을 개선하여 전체 작업 중 P의 부분에서 S배의 성능이 향상되었을 때 공식은 다음과 같다.

전체 작업 시간 중에 40%를 차지하는 병렬 프로세스의 속도를 2배 증가시켰다면, 전체 작업 속도는 1.25배로 증가한다.

P = 해당 성능이 전체적으로 차지하는 비율 (ex: 50%면 0.5)

S = 해당 성능을 개선시킨 속도

 

암달의 법칙에 따라 프로그램을 실행하는 프로세서수의 함수로 프로그램 실행 대기 시간의 이론적 속도 향상. 속도는 프로그램의 시리얼 부분에 의해 제한된다. 예를 들어 프로그램의 95%를 병렬화 할 수 있으면 병렬 컴퓨팅을 사용한 이론상 최대 속도는 20배가 된다.

참고로, 암달의 법칙의 개념을 무너뜨린 병렬 법칙이 있는데 구스타프슨의 법칙이다. 해당 법칙은 다음 포스팅에 설명을 해보도록 하겠다.

참고자료

진 암달 - 위키피디아

암달의 법칙 - 위키피디아

연관자료

무어의 법칙(Moore's Law)과 황의법칙(Hwang's Law)