all2one awakening

• RT ujeani: RT urpurple: 엄청난 각종 전문서적 원서 e-book이 가득한 곳 http://knowfree.net 내 취향을 분석해주는 사이트 http://www.idsolution.co.kr/ 저보고 아방가르드취향이라는 군요. #
• 또다른 공짜 이북 소개 사이트
  
• RT nvidiadeveloper: Slides for "Efficient Substitutes for Subdivision Surfaces" is now available! http://is.gd/23HLQ #siggraph #
• 엔비디아의 시그래프 2009 세션 정보 및 자료를 구할 수 있는 페이지
  
• RT sioum: 수학노트라는 훌륭한 사이트 발견! pythagoras0님 대단하십니다 RT pythagoras0:puzzlist http://pythagoras0.springnote.com/ 에 가입하시면 써포트 해드리겠습니다 ㅋㅋㅋ #
• 수학을 좋아하셨거나 좋아하시고 싶은 분들에게 유용할 위키 사이트
  
• VSBuildStatusAddin display the status of a build/clean/deploy operation: http://su.pr/5RxOgw #
• 비주얼스튜디오에서 빌드 진행 상태를 깔끔하게 보여주는 add-in
  
• RT mike_acton: Roundup: Recent sketches on concurrency, data design and performance. http://post.ly/1u4J #
• Insomniac Games에서 일하는 마이크의 영감을 주는 concurrency 관련 슬라이드들
  
• RT KageKirin: "OpenGL 3.2 and GLSL 1.5 released at Siggraph!" - http://ping.fm/q4S7c #gl #programming #
• 이번 시그래프에서 OpenGL 3.2와 GLSL 1.5가 발표되었답니다!
  
• RT nvidiadeveloper: We've announced the launch of the NVIDIA Application Acceleration Engines, including Optix http://is.gd/22hNa #
• 엔비디아도 이번 시그래프에서 실시간 광선추적 엔진을 비롯한 응용프로그램 가속 엔진들을 발표했습니다.
  
• RT bjoernknafla: RT JamesReinders:Intel Threading Building Blocks, new version 2.2, appeals to C++ and C programmers http://tr.im/vrAi #
• 인텔 TBB도 2.2 버전이 나오면서 C++0x의 람다도 지원하고 Cilk와 유사한 런타임 엔진을 제공한다는군요. 인텔이 Cilk++를 사들인 것과 무관하지 않은듯. 앞으로 더욱 기대가 되는군요!
  
• RT unclebobmartin: http://bit.ly/127rtT Interview with Barbara Liskov. #
• Liskov Substitution Principle 아시죠? 그 Liskov가 여성분이셨군요!
  
• RT SoftTalkBlog: Some parallel programming locking strategies that can speed up programs while avoiding data races: http://bit.ly/WTPyc #
• 병렬 프로그래밍에서의 locking 전략에 관한 팁들
  
• RT programmingjoy: Lua bitstring parsing and creation library based on Erlang bit syntax #programming http://bit.ly/rMzwl #
• 루아 비트열 파싱 및 생성 라이브러리
  
• RT programmingjoy: C++ vs Java vs Python vs Ruby : a first impression #programming http://bit.ly/ke1e9 #
• C++/Java/Python/Ruby 언어의 간단 비교
  
• RT programmingjoy: The Scheme Programming Language, 4th Edition, now available #programming http://bit.ly/A8Atw #
• 스킴 언어 서적
  
• RT programmingjoy: List of freely available programming books #programming http://bit.ly/vLVD6 #
• 역시 프로그래밍 관련 공짜 이북들
  
• Ask.C++: Looking for references on coding for optimization on x86 architectures http://su.pr/7ApBEq #
• 최적화 관련 도움을 주는 링크들
  
• RT programmingjoy: Engineers are artists too. Reply to Merlin Mann on "engineering block" #programming http://bit.ly/zhLa7 #
• 엔지니어도 아티스트다!
  
• RT KageKirin: "rsizr" - seamless image resizing - http://rsizr.com/ #
• 이미지를 깔끔하게 리사이징해주는 웹 도구
  
• RT insic: 50 Eye-Popping Examples of Concept Art | Webdesigner Depot http://bit.ly/38FMvS #
• 50가지 멋진 원화들
  
• RT mike_acton: Cool! Handy regex cheat sheet. RT FrankSansC http://bit.ly/zg9LV #
• 아주 유용한 정규표현식 컨닝페이퍼
  
• RT programmingjoy: Probably the hardest (answerable) logic question ever. #programming http://bit.ly/I95qJ #
• 골때리는(?) 퀴즈 문제
  
• RT programmingjoy: Don?t use standard library/CRT functions in static initializers/DllMain! #programming http://bit.ly/z9Wmt #
• 정적 초기자 및 DllMain에서 표준 라이브러리/CRT 함수를 쓸 경우의 문제점
  
• RT KageKirin: "Unigine" - http://unigine.com/ #programming #opengl #
• 또다른 실시간 3D 엔진
  
• RT programmingjoy: Sony Pictures Imageworks - Open Source #programming http://bit.ly/17z5As #
• 소니 픽쳐스 이미지웍스의 오픈 소스 페이지
  
• RT programmingjoy: Programming Praxis: Josephus' Circle #programming http://bit.ly/D0vt3 #
• 풀어볼만한 프로그래밍 퀴즈
  
• RT programmingjoy: How Bad Design Patterns Ruin Good Programmers #programming http://bit.ly/3oAoK #
• 디자인패턴이 좋은 것만은 아니다!?
  
• RT SoftTalkBlog: Two parallel programming debugging tools compared: Intel Thread Checker and Intel Parallel Inspector. http://bit.ly/iwrp1 #
• 인텔에서 만든 두가지 병렬 프로그래밍 디버깅 도구의 간단 비교
  
• RT programmingjoy: RethinkDB - The database for solid state drives. #programming http://bit.ly/ENVTG #
• 이런 것도 나오네요. SSD를 위한 데이터베이스입니다.
  
• The Passionate Programmer: Creating a Remarkable Career in Software Development (a book): http://su.pr/6w2YAH #
• 구입예정인 책
  
• RT programmingjoy: The Haskell Cheatsheet #programming http://bit.ly/8ICjH #
• Haskell 컨닝페이퍼
  
• RT programmingjoy: Can Agile development work for a team of experts? Doesn't look like it... #programming http://bit.ly/BBVs8 #
• 애자일 개발이 전문가로 구성된 팀에 적절한가?
  
• Pro Git - professional version control (A book about git now online): http://su.pr/2exnde #
• 분산버전관리시스템 Git 온라인 서적
  
• Intel Advanced Graphics Lab papers: http://su.pr/9aXwmJ #
• 인텔 고급 그래픽스 연구실 논문들
  
• Morphological Antialiasing: http://su.pr/2UTEKS #
• 최근 발표된 새로운 안티알리아싱 기법 논문
  
• RT programmingjoy: Statistics of two years of blogging about programming #programming http://bit.ly/5uByY #
• 구글 엔지니어인듯한 한 친구의 블로그
  

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

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

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

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

• 분산 버전 제어 시스템 소개: http://su.pr/71wcpc #
• Agile Fails Better: http://su.pr/1hO99i #
• User-friendly compile errors for templates in C++0x: http://su.pr/1rv3Ws #
• Chrome Engine 4: http://su.pr/77X37R #
• Curved Ray-Casting for Displacement Mapping in the GPU: http://su.pr/4fPJCM #
• Ending the Era of Patronizing Language Design: http://su.pr/1TAqcy #
• RT SingleFunction: 105 Examples of Clean and Minimal Twitter Apps http://tr.im/sfCB #
• 실버라이트3 기반 트위터 클라이언트 ‘소비즈’: http://su.pr/2iWdoJ #
• Voxel Tracing: http://su.pr/1AKmwh #
• Work-In-Play Limits in Agile Software Development: http://su.pr/9NvOvc #
• RT bjoernknafla: Fantastic overview article abt parallelization & related pragmatic tips&tricks from Cantrill & Bonwick: http://is.gd/1w4tm #
• SIGGRAPH 2009 Talks: http://su.pr/1pUG4T #
• Elements of Modern C++: 2 ECTS advanced C++ course http://su.pr/1oyr5F #
• Twitter Search Operators: http://su.pr/2GJJ6z #
• Cheat-Sheets.org: http://su.pr/3S4OUU #
• RT DexterShin: 회사 지인이 Scrum 가이드 좀 해달라 해서 찾아본 멋진 스라이드. The Zen of Scrum http://tr.im/roTc (잘 모르는걸 말할땐 소심 해여야 하는건데, 이번기회에 공부 해야지 히히. ) #
• [STL] std::splice() - 컨테이너의 elements 이동시 loop을 사용하지 말자: http://su.pr/2LqK0Y #
• How much boost does a C++ newbie need? http://su.pr/21wcqC #
• RT unclebobmartin: RT CodebetterNew: Blog Post Embrace Pain: Agile is abt surfacng pain. It's not abt roses, p.. http://tinyurl.com/ml2nja #
• RT eHub: Screenjelly http://tinyurl.com/lrunry #
• RT mike_acton: New & improved slides. Doubly-linked list isnt a concurrent data structure. Welcome all feedback! http://tinyurl.com/lj4g5x #
• GameNewsHQ.com - Latest Video Game News Updated Live: http://su.pr/2qezwn #
• RenderAnts: Interactive REYES Rendering on GPUs http://su.pr/79hRNx #

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

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

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

std::shared_ptr<T> pop() { std::lock_guard<std::mutex> lock(m); if(data.empty()) throw empty_stack(); std::shared_ptr<T> const res(new T(data.top()); data.pop(); return res; } void pop(T& value) { std::lock_guard<std::mutex> lock(m); if(data.empty()) throw empty_stack(); value=data.top(); data.pop(); }

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

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

• Lock-Free Code: A False Sense of Security
• The Many Faces of Deadlock

Both DDJ articles are by Herb Sutter.

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

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

Pattern-Oriented Software Architecture Volume 2: Patterns for Concurrent and Networked Objects

I finally read this all. Definitely it's a must-read for all game programmers.

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

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

다음과 같은  두  개의  C 라이브러리를  발견하였습니다.

libcmt
LibLTX

아직 다소 생소한 concurrency  솔루션입니다만... 언젠가는  주류가 될지도 모르겠군요.

In English...(show)

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

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