all2one awakening

Parallelism by wauter de tuinkabouter

※ 이 글은 http://www.cilk.com/multicore-blog/bid/5365/What-the-is-Parallelism-Anyhow 의 글을 바탕으로 정리한 것입니다.

이 글에서는 병렬성이라는 것을 이론적으로 정의해보겠습니다. 이론적인게 보통 그렇듯 실제 무슨 쓸모가 있냐 할 수도 있지만, 병렬 알고리즘의 이해에 많은 도움이 되더군요.

암달의 법칙(Amdahl's law)
먼저 잘 알려진 암달의 법칙을 소개하겠습니다.

연산의 50%만 병렬화가 가능하고 나머지는 순차 수행만이 가능하다면, 아무리 많은 자원으로 병렬화를 하더라도 2배 이상의 성능 향상은 불가능하다

이상입니다. 좀 더 일반적으로 표현하면, 연산의 p 비율만큼만 병렬화가 가능한 경우, 병렬화로 인한 속도 향상은 최대 1/(1-p)로 제한된다가 되지요.

프로그램의 병렬 수행을 dag로 표현하기
병렬성을 정의하기 위해 병렬 수행을 dag(directed acyclic graph) 형태로 표현해봅시다. 다음이 그 예입니다.



그래프 상의 노드는 단위 연산을 나타내고, 화살표 연결은 실행 흐름을 나타냅니다. 자식이 여러 개인 노드는 거기서 여러 스레드로 병렬 수행이 시작된다는 의미가 되지요.
이 경우 병렬성(parallelism)이 얼마가 될까요? 3 혹은 5?

Work law
먼저 work의 개념을 정의하겠습니다. Work는 실제 모든 연산들을 수행하는데 드는 시간을 나타내는 것으로, Dag 상의 노드들의 개수가 됩니다. 위 그래프의 경우는 18이 되지요.
T_P를 간단히 p개의 프로세서를 사용해 낼 수 있는 최단 수행 시간이라 정의해보죠. work는 프로세서 한 개 사용 시 수행 시간에 해당하므로 T₁으로 나타낼 수 있습니다. 이 때 다음이 성립합니다.



이를 Work law라 합니다. 쉽게 말하면 p 프로세서를 사용하면 p배를 넘어서는 속도 향상은 불가능하다는 자명한 이야기입니다.

Span law
다음으로 span이라는 개념이 중요합니다. Span은 dag에서 가장 긴 의존 경로의 길이를 말합니다. 위 경우는 1→ 2 → 3→ 6 → 7 → 8 → 11→ 12 → 18 로 9가 되겠습니다. Dag에서 소위 임계경로의 길이가 되겠습니다. 이는 무한 개의 프로세서를 쓸 수 있다고 할 때, 가장 빠른 수행 시간에 해당하므로 T_∞로 나타낼 수 있습니다. 이 때 다음이 성립합니다.



 이를 Span law라 합니다. 역시 무한의 프로세서를 활용한 경우보다, p개의 프로세서를 활용한 경우가 더 빠를 수 없으니 자명해보입니다.

Parallelism
이 둘을 가지고 병렬성이 정의됩니다. 병렬성은 바로 T₁/T_∞입니다. 왜 이 놈으로 병렬성을 정의하는 것이 의미가 있는지 한번 고민해보세요. ^^ 위의 경우는 18/9가 되어 2의 병렬성이 나옵니다. 다시 말하면 프로세서 몇개를 사용해도 2배를 넘어서는 속도 향상은 위 프로그램 흐름에서는 불가능하다가 되겠습니다. 어떠세요? 예상했던 것과 비슷한가요?
실제 암달의 법칙도 간단히 유도가 됩니다. 암달의 법칙에서 p 비율만큼만 병렬화가 가능하고 나머지 1-p에 해당하는 부분은 순차 수행이 불가피하므로 T_∞ > (1–p) T₁ 라 할 수 있습니다. 이 때 가능한 최대 속도 향상은 T₁/T_∞ < 1/(1–p) 식으로 제한이 되겠죠.

이제 병렬성을 이론적으로 확실히 정의하였습니다! 실제 이러한 병렬성의 개념을 어떻게 유용하게 쓸 수 있는지는 다음에 기회가 될 때 보여드리도록 하겠습니다.

참고링크
http://www.cilk.com/multicore-blog/

* 이 포스트는 blogkorea [블코채널 : 웹, 컴퓨터, it에 관련된 유용한 정보 및 소식] 에 링크 되어있습니다.

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.