암달의 법칙 깨기 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]

*

† 그의 이전 아티클 How Much Scalability Do You Have or Need (2007년 8월, DDJ, http://www.ddj.com/hpc-high-performance-computing/201202924)에서 직렬 실행(싱글프로세스/스레드)를 O(1), K 개의 코어를 이용해서 혹은 가정하고 명시적인;explicit 스레딩을 하는 것을 O(K) 병렬화, intel TBB나 OpenMP 혹은 .net framework의 Task Parallel Library 같은 것처럼 코어 수에 따라 scalable하게 확장되는 라이브러리들이 가능한 최대 병렬화(=O(N) 병렬화) 라고 명명하고 설명했다. 용어 정리라거나, 관련 토픽을 찾아보는 기점으로 쓰기에도 유용한 글이니 한 번쯤 읽어봐도 :)

‡ N→∞ 일 때, Speed up은 기껏해야 1/(1-P)다. P = 0.9래봐야(프로그램 전체 중에 90%가 병렬화 가능한 경우. 그리고 이런 경우는 흔치 않다 -_-;; ) 10배 증가.

Published by

rein

나는 ...

5 thoughts on “암달의 법칙 깨기 by 허브 서터”

  1. 근데 워드프레스는 각주 기호에 하이퍼링크 안 달리나? 좀 불편하네. 고어핀드 블로그는 클릭으로 왔다갔다해서 좋던데.

  2. 플러그인이 있긴한데, 제가 지금 쓰는 애가 개발버젼이라 동작을 안하더라고요 -_-;;
    + 저 각주기호는 제가 수동으로 다는 겁니다[…]

  3. 그러고 보니 다니엘 힐리스가 the pattern on the stone에서 프로세서 수만 개를 쓰는 컴퓨터를 만들면서 암달의 법칙이 항상 적용되는 건 아니라고 했던 듯한데, 이것도 헛소리가 아니라 저런 뜻이었나 보군.

  4. 두 번째 항목을 보다가 생각난 건데, 앞으로는 그래픽 카드의 GPU를 계산에도 사용할 수 있게 된다고 하는 걸 들은 기억이 나네요. 캐쉬가 필요없는 데이터(stream?)를 연산하는 데는 꽤 쓸만하다고.

  5. 일념 / 네 아마 “일의 내용”자체를 바꾸는 수준의 변화도 가능하고해서 그런것 같아요

    고어핀드 / 실제로 상대적으로 단순한 계산들을 고병렬로 처리하는데는 그래픽 카드만한게 없지. 픽셀 쉐이더 같은건 동시에 100개 이상도 처리해내니까; 캐쉬랑은 좀 다른 얘기지만 고병렬/단순연산은 실제로 그래픽 카드의 GPU를 많이 쓰기 시작했다.(전산 물리 쪽에서 요즘 그쪽을 두드려보기 시작했다는 글을 읽은 것 같은데 출처를 못찾겠음)

Leave a Reply