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 대한민국 라이선스에 따라 이용하실 수 있습니다.

C++0x의 기본적인 병렬 지원 강화와 함께 여러 병렬 플랫폼이 대두되고 있습니다. OpenMP(얼마 전 3.0 스펙이 나왔죠), 인텔의 TBB(Threading Building Blocks), VS 2010과 함께 등장할 PPL(Parallel Patterns Library) 및 AAL(Asynchronous Agents Library), MIT 스핀오프인 Cilk++(상용) 등이 그것입니다.


제가 일원으로 참여하고 있는 Visual Studio Team System 2010 공식 팀 블로그에 며칠 전 PPL을 이용한 피보나치 수 병렬 계산에 대한 글을 올렸습니다. 근데 그 후 Cilk++ 1.1.0 베타 버전이 출시되었다는 소식을 들었습니다. 그래서 한 번 받아서 테스트 해보았습니다.

#include "windows.h" #include <functional> int SPINCOUNT = 25; //Spins for a fixed number of loops #pragma optimize("", off) void delay() { for(int i=0;i < SPINCOUNT;++i); }; #pragma optimize("", on) //Computes the fibonacci number of 'n' serially int fib(int n) { delay(); if (n< 2) return n; int n1, n2; n1 = fib(n-1); n2 = fib(n-2); return n1 + n2; } //Computes the fibonacci number of 'n' in parallel int cilk_fib(int n) { delay(); if (n< 2) return n; int n1, n2; n1 = cilk_spawn cilk_fib(n-1); n2 = cilk_fib(n-2); cilk_sync; return n1 + n2; } int cilk_main(int argc, char* argv[]) { int num = 30; SPINCOUNT = 500; double serial, parallel; __int64 begin, end; //compare the timing of serial vs parallel fibonacci printf("computing fibonacci of %d serial vs parallel\n",num); printf("\tserial: "); begin = GetTickCount(); fib(num); end = GetTickCount(); serial = (double)(end - begin); printf("%4.0f ms\n",serial); printf("\tparallel: "); begin = GetTickCount(); cilk_fib(num); end = GetTickCount(); parallel = (double)(end - begin); printf("%4.0f ms\n",parallel); printf("\tspeedup: %4.2fX\n",serial/parallel); return 0; }

코드의 전반적인 구성에 대한 설명은 팀블로그 글을 참고해주세요. 기본적으로 거기의 예제 코드에서 메모리 관련 테스트를 빼고 병렬 버전의 함수를 PPL이 아닌 Cilk++을 사용토록 수정한 것입니다. cilk_spawn이 PPL 코드의 tasks.run() 함수에 해당하고, cilk_sync가 tasks.wait() 함수에 해당한다고 보면 됩니다.

일단 순차 버전과의 실제 코드 차이가 PPL 버전 보다 더욱 좁혀졌습니다. 몇가지 키워드가 추가된 것 말고는 완전히 동일하죠. 라이브러리 형태로 태스크 개념을 지원하는 PPL과 달리, Cilk++는 언어 확장 키워드(31과 33줄의 cilk_spawn, cilk_sync가 그 예)로 병렬 개념을 지원합니다. 또한 OpenMP처럼 수많은 디렉티브를 공부해야할 필요도 없습니다. 서너 개의 키워드만이 제공되기 때문이죠.

그리고 Cilk++ 키워드의 장점은 그것이 강제 사항이 아니라 권고 사항이라는 겁니다. 따라서 위에서 cilk_spawn 했다고 해서 반드시 별도 스레드로 병렬 수행되는 것이 아니라 실제 하드웨어 병렬성을 조사하여 그냥 순차 실행하는 것이 낫다고 판단할 경우 순차실행할 수도 있다는거죠.

어쨌든 2 코어의 제 컴에서 릴리즈 빌드를 돌린 결과를 보면 다음과 같습니다.

PPL 버전:


Cilk++ 버전:


Cilk++ 버전이 병렬화를 더 잘하고 있음(1.82X > 1.51X)을 확인할 수 있습니다. 약간의 차이지만 여러번 돌려보아도 계속 비슷한 결과가 나왔습니다. PPL 버전은 VS 2010 기반이고 Cilk++ 버전은 VS 2080 기반이며, 그 밖에도 여러가지 면에서 엄정한 테스트와는 거리가 멉니다만... 그래도 어느 정도 Cilk++의 성능상 장점을 보여준다고 생각합니다(물론, PPL은 아직 정식 버전이 나온게 아니죠).

단, PPL은 VS 2010을 사면 공짜가 되겠지만, Cilk++은 상업적 용도로는 분명 유료라는 점!을 간과해서는 안되겠죠. ^^

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

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

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