암달의 법칙 깨기 by 허브 서터

DDJ에 실린 허브 서터의 아티클을 요약. 전번에 썼던 직렬 실행 최적화의 시대가 끝나가고 멀티코어를 홭용하는 방향으로는 가야겠는데, 그렇다면 어떻게 해야 좋은 성능을 낼 수 있겠는가에 관한 글이다.

어제 작성했던 글이나, 멀티 코어 용 라이브러리 관련된 포스팅을 했던 것 처럼, 이런 “멀티코어를 활용할 수 있는 환경"은 점점 더 잘 구축되어가고 있고…인데. 허브 서터는 이런 점을 이용해서 병렬처리에서 말해온 “암달의 법칙; Amdahl’s Law"를 깨뜨릴 수 있다고 말하고 있다.

암달의 법칙을 병렬 처리 관점에서 말하면 – 사실 이게 원본(?)이겠지만 나는 이걸 컴퓨터 구조에서 처음 배운듯하다 – 전체 작업 중에 P부분 만큼 병렬화 가능한 부분 (허브 서터의 표현을 빌자면 O(N) 병렬화가능한; parallelizable¹ 부분)에 대해 N개의 코어를 사용하면 다음과 같은 비율로 “실행 속도"가 증가한다.

Speed up = 1 / ((1 – P) + P/N)

문제는 이 공식을 그래프로 그려보면 알 수 있는데, P 부분이 작으면 (크다곤 해도 N이 좀 증가하면) 전체적인 속도 증가가 미미해진다는 것. 이게 암달의 법칙이 설명하는 “병렬처리의 한계선"이 된다².

그렇다면 이런 한계선을 극복하기 위해서는 어찌해야하는 가에 대해 허브 서터는 다음 세 가지를 제시하고 그에 대해 설명하고 있다.

• O(N) 병렬화가 가능한 부분에서 처리하는 일 자체를 증가 시켜라
• 새로운 O(N) 작업을 추가하라
• 직렬 실행(O(1) 병렬화)만 하던 부분을 O(K)로 만들어라

이렇게 한다면 P 자체도 커지고, (1-P) 에 해당하는 것도 (1-P)/K로 가게된다. 그리고 그러면서도 하는 일 전체의 양은 “훨씬 증가하게” 된다.

첫번째 항목은 병렬처리에서 나온 또다른 법칙인 Gustafson’s Law에 해당하는 이야기다. 즉

해야할 일이 충분히 많다면, 사실상 모두 병렬화 할 수 있다.

라는 것인데, 컴퓨터가 빨라지면 “처리할 일도 늘어난다"라는 업계 농담[…]처럼 일 자체가 늘어나기 때문에 첫항목이 달성된다는 것. 속도 증가가 아니라 속도는 유지되고 같은 시간에 처리하는 작업이 늘어난다라는 관점에서 접근하는 것이다. 똑같은 속도로 실행되는 게임이라도 해상도가 2배로 증가하고, 나오는 물체들도 3배쯤 늘어나는 게임이라거나를 보면 즐겁지 않을까.

두번째로는 다른 누군가가 생각하지 못한 새로운 O(N)작업 – 본질적으로 병렬적인 무언가 – 를 추가해서 UX를 강화 한다는 것. 이런 작업의 예로는 “현재의 3D 가속기능이 포함된 그래픽 카드"가 아닐까. (비슷한 예제를 허브 서터도 얘기하고 있음) 동영상 재생할 때 모니터 해상도에 맞춰서 확대된 동영상을 per-pixel 레벨에서 근접한 다른 pixel들을 비교해서 적정한 pixel 값을 출력해줘서 자연스럽게 하는 것을 요즘은 그래픽 카드의 pixel-shader를 사용해서 처리한다. 그리고 이런 연산은 말그대로 병렬연산 이기에 카드가 지원해주기 전까지는 너무 느려서 할 수도 없던 무언가였다 :) . 이런 부분이 게임 서버에도 적용되기 쉬운? 부분이 아닐까 하지만…

마지막 내용은 직렬로 보이는 작업이더라도 내재된 병렬화 할 수 있는 부분이 있긴 할 것이니 이를 찾아서 K개로 라도 나눠보겠다는 것. …근데 생각해보면 이건 매일매일하고 있는 일인데.

뭐 결론적으론 이런 것들을 잘 해서 암달의 법칙(이 정한 한계선)을 돌파하겠다는 것인데, 병렬 처리, 멀티코어 시스템을 바라보는 조금 색다른 관점으로라도 읽어보면 좋은 글이었던 듯 하다.

References

• H. Sutter. Break Amdahl’s Law! Doctor Dobb’s Journal, Jan. 2008_._ http://www.ddj.com/architect/205900309
• H. Sutter. The Pillars of Concurrency. Doctor Dobb’s Journal, Jul. 2007. http://www.ddj.com/hpc-high-performance-computing/200001985
• H. Sutter. How Much Scalability Do You Have or Need? Doctor Dobb’s Journal, Sept. 2007. http://www.ddj.com/hpc-high-performance-computing/201202924