Amdahl's Law

이상적인 병렬 처리에서는, n-way 만큼 처리 능력을 향상시켰다고 할 때 n 배의 성능 향상 효과가 있어야 한다. 하지만, 이런 선형적인 성능 향상은 현실 세계에서는 절대로 불가능하다. 왜냐하면, 병렬 처리가 필요한 계산 문제에서, 여기에 참여하는 각 구성 요소들의 통신과 협조 비용이 존재하기 때문이다. 즉, 각 작업량이 모두 동일하지 않을 수도 있으며, 작업들 사이에서 의존성 관계가 생길 수 있기 때문에 이를 중재하지 않고서는 병렬화가 불가능하다.

이런 종류의 분석 결과를 단적으로 말해주는 것이 암달의 법칙(Amdahl's Law)이다. 암달의 법칙은 어떤 작업의 속도를 향상시킬 수 있는 정도는, 성능 향상이 적용되지 않는 부분에 의해 제한된다는 보여준다. 작업의 속도 향상 정도 S는, 하나의 프로세서로 해당 작업을 끝내는데 걸리는 시간과, n 개의 병행 프로세서가 같은 작업을 끝내는데 걸린 시간의 비율로 정의한다. 하나의 프로세서로 해당 작업을 끝내는데 걸리는 시간을 1이라고 했을 때(정규화), N개의 프로세서를 사용하면 병렬 처리가 가능한 부분을 p / n, 순차 처리 부분은 1 - p이라고 할 수 있다. 따라서, (1 - p) + p / n은 이 과정에서의 전체 처리 속도를 나타낸다. 암달의 법칙을 수식으로 표현하면,

S = 1 / ((1 - p) + p / n)

으로 정의할 수 있다.

예를 들어, 전체 작업량 10에서 8이 병렬 처리가 가능하다고 했을 때 p = 8 / 10이 된다. 그렇다면, 2의 작업량은 순차적으로 처리될 수 밖에 없고, 이 부분을 처리하기 위한 비용은 1 - 0.8 = 0.2가 된다. 여기에 만약 10의 작업자를 투입한다고 했을 때, 병렬화할 수 있는 정도는 0.8 / 10이 된다. 즉, 100 / 28 ≒ 3.6, 10의 작업자를 투입하더라도 고작 3.6배의 속도 향상이 있을 뿐이라는 것을 볼 수 있다. 즉, 병렬화되지 않거나 병렬 처리를 적용하기 어려운 이 부분이 병렬화로 얻는 이득을 크게 줄이며, 이것을 최대한 최적화할 필요가 있다. 이 작업은 쉽지 않지만, 충분히 시도할만한 가치가 있다.


Reference
Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier, 2008
김진욱, 하재승, 멀티프로세서 프로그래밍, 한빛미디어, 2009 (번역)