[컴퓨터구조] 암달의 법칙과 리틀의 법칙

현재 글은 컴퓨터 구조와 아키텍처 서적 및 대학에서 들은 강의를 기반으로 한다.

---

컴퓨터 구조에서 암달의 법칙 및 리틀의 법칙은 멀티코어 및 병렬 시스템에 대해 설명하는데 도움을 줄 수 있다.

암달의 법칙(Amdahl's law)

암달의 법칙에 따른 속도 증가 추이를 나타낸 그래프

암달의 법칙 공식  (https://en.wikipedia.org/wiki/Amdahl%27s_law)

 암달의 법칙은 병렬 컴퓨팅 상황에서 병렬 작업에 의한 성능 향상 정도를 나타내는 공식으로, 아무리 병렬성을 높인다고 해도 ( 코어 수를 늘린다고 해도 ) 최대 성능은 전체 작업 중 병렬 작업이 차지하는 비율에 종속된다는 의미를 가진다.

 위 공식에서 p 는 병렬적으로 처리할 수 있는 작업의 비율을 의미한다. 코어 s의 수가 충분히 많으면 p / s 는 0에 수렴하기 때문에, 전체 성능은 serial하게 처리되는 작업의 비율인 (1-P) 에 따라 달라진다. 이때 성능을 최대한 양보해서 병렬적으로 처리하는 작업이 전체 작업의 95% 라고 가정하자. 이 경우 병렬적으로 처리될 수 없는 작업이 5% 이므로 성능 증가 비율은 1 / 0.05 = 20 배가 된다.

 즉, 암달의 법칙에 따르면 컴퓨터의 전체 작업 중 병렬 처리가 가능한 작업의 비율이 95%나 되는 극적인 상황에서도 처리 속도는 20배가 한계이다. 즉, 속도 면에서는 아무리 병렬 처리를 해도 20배 이상 빨라질 수는 없다.

 병렬 처리의 효율을 방해하는 요인에는 다음과 같은 것들이 존재한다.

• load imbalance : 특정 업무를 병렬적으로 분해하여 각 프로세서에게 배분할 때 비균등하게 분배되어 가장 오래 걸리는 작업을 기준으로 다른 프로세서들이 대기해야 하는 문제로, 작업을 더 균등하게 분리해야 한다.
• resource contention : 운영체제는 I/O 와 같은 공유 자원을 다수의 프로세스가 사용하려다 발생하는 문제를 해결하기 위해 뮤텍스 락, 세마포어 등 다양한 기법을 제공한다. 병렬 단위로 일을 쪼개더라도 해당 일은 다수의 스레드에서 동시에 처리할 수 없어 순서대로 처리해야 한다.
• synchronization : 특정 업무를 수행하기 위해 데이터를 분리하거나, 코드를 분리해서 실행한 후에는 이들의 순서를 동기화 하는 과정에서 serial 한 작업 혹은 다른 스레드를 위한 대기 시간이 필요할 수 있다.

구스타프슨의 법칙( Gustafson's Law ) 

구스타프슨 법칙에 따른 성능 증가 추이를 나타낸 그래프

 암달의 법칙을 계산할 때 P : 병렬처리하는 작업의 비율은 변하지 않는다. 계산 시점에 수행해야 하는 일은 정해져 있으며, 이들을 좀 더 빠르게 실행할 수 없는지를 나타내는, 시간과 관련된 공식이기 때문이다. 작업(load)이 정해져 있다는 점에서 암달의 법칙은 fixed load model이라고 불리기도 한다.

 그런데 현실의 많은 일들은 빠른 시간 내에 처리하는 것 보다는 동일 시간 동안 더 많은 일을 수행할 수 있는지 여부가 더 중요한 요소인 경우가 많다.

 예를 들어 일기 예보를 생각해보자. 일기 예보에서 중요한 것은 얼마나 빨리 예측하는지가 아니라, 얼마나 정확하게 예측하는지이다. 대부분의 직장인은 일기예보에서 내일 날씨를 정확하게 예측하기를 바란다.  예보에서 내일 해가 쨍쨍하다고 해서 우산을 챙기지 않았는데 비를 맞게 된다면 이건 엄청난 불상사이기 때문이다. 반대로 예보가 나오는 시간은 그렇게까지 중요하지 않다. 최소한 출근 전까지만 정확한 예보가 나온다면 우산을 챙길 수 있기 때문이다. 기상청이 한달 뒤의 날씨를 벌써부터 예측해봤자 정확도가 50% 밖에 안된다면 결국 우산을 챙겨야 하는 것을 생각해보면, 예보는 정해진 시간 내에 최대한 많은 데이터를 기반으로 연산하여 최상의 정확도를 가질 필요가 있는 작업이다.

 구스타프슨의 법칙은 대용량으로 들어오는 일은 동일 시간 내에서 효율적으로 처리할 수 있음을 나타내는 법칙이다. 앞서 언급한 일기 예보의 경우 최소 하루 전에만 예측하면 되는 작업으로, 시간보다는 대량의 데이터 및 연산을 통해 높은 정확도를 가지는 것이 우선된다. 따라서 일기 예보의 경우 구스타프슨 법칙에 따라 병렬 처리 시 성능 향상을 기대할 수 있다. 동일 시간에 얼마나 많은 작업을 수행하는지 다루는 특성상 fixed time model 이라고 한다.

 암달의 법칙과 구스타프슨 법칙은 다루는 내용이 다르다. 암달의 법칙의 경우 작업이 일정할 때 시간 감소에 대한 내용을 담고 있는 반면, 구스타프슨 법칙은 시간이 일정할 때 수행하는 작업량의 증가에 대한 내용을 담고 있다. 암달의 법칙만 따지면 병렬 처리의 장점이 퇴색되어 보일지 몰라도 대규모 데이터를 다루는 현실의 많은 작업들은 구스타프슨 법칙에 따라 병렬 효율이 좋기 때문에 이에 대해 비관적으로 볼 필요는 없을 것이다.

리틀의 법칙(Little's Law)

 컴퓨터에서 큐는 필수적인 자료구조로, 대기열 등을 구현할 때 꼭 사용된다. 리틀의 법칙은 이러한 큐의 길이를 어느 정도로 맞춰야 가장 효율적인지 결정하는 공식으로, 원래는 경제학 분야에서 재고를 산출하기 위해 등장했지만 큐나 서비스 업종 등에도 적용할 수 있는 직관성을 가진다.

 리틀의 법칙에는 steady state 라는 조건이 있다. steady state는 대상이 "정상적" 으로 입출된다는 가정하의 조건으로, 쉽게 말해 평범하게 물건이나 사람이 들어왔다 나가면 된다. 시간 당 평균 30명의 사람이 오던 장소에 갑자기 1000명의 사람이 들이닥치는 상황은 steady 하다고 볼 수 없다. 이 조건 하에서 공식은 다음과 같다.

L = λ * W

• L : 큐의 길이
• λ : 시간 당 평균 도착률
• W : 평균 대기 시간

 컴퓨터에서 리틀의 법칙은 공유 메모리나 캐시 메모리 크기 지정 등 다양한 용도로 사용될 수 있다. 보다 직관적으로, 데이터의 입출이 있는 상황에서 대기하는 일이 있는 경우에는 모두 적용할 수 있어 보이며, 소프트웨어 테스팅 쪽에서도 사용되는 개념이라고 한다.

---

 암달의 법칙에 대해 찾는 과정에서 완전 병렬 처리하는 프로세서를 만들었다고 하는 기업에 대해 알게 되었다. 2020년의 기사를 마지막으로 관련된 내용이 나오지 않아 현재 상황은 잘 모르겠지만, 만약 완전 병렬 처리가 가능한 아키텍처를 이용했을 때 특정 분야에서 시장의 CPU들보다 성능이 좋을 수 있다면 대단할 것 같기는 하다.

http://morumi.kr/