all2one awakening

프로그래밍programming

• RT programmingjoy: LtU: Scratch: Programming for All #programming http://bit.ly/1FZc4P #
• 아이들을 위한 프로그래밍 언어
  
• RT programmingjoy: Inside "MinWin": The Windows 7 Kernel Slims Down #programming http://bit.ly/1Wj6d6 #
• 서버 및 임베디드 플랫폼을 위한 윈도 최소 버전에 관한 아르스 테크니카 글
  
• RT rickasaurus: RT IdeaKitchn: RT TommyLee The #PDC09 session videos are now becoming available at http://bit.ly/45XnrF. #programming #
• 얼마 전 있었던 PDC09 세션 비디오들. 저도 아직 보지는 못했다는...;
  
• RT programmingjoy: Buy Bad Code Offsets Today! #programming http://bit.ly/1Rb8vI #
• 지저분한 코드를 위한 면죄부!? 저도 좀 사둬야 할 듯 ㅋㅋ
  
• Next permutation — When C++ gets it right: http://su.pr/2OlYCd #C++ #programming #
• 흥미로운 코딩 퀴즈
  
• RT programmingjoy: 40% off Thanksgiving PragSale now through 11/25 #programming http://bit.ly/3dvA6y #
• 유용한 책들이 많이 선보이는 "The Pragmatic Bookshelf"에서 추수감사절맞이 40% 세일을 진행 중입니다. 25일까지이니 서두르시길
  
• RT programmingjoy: Sun announces First-class methods for Java 7 at Devoxx 2009 conference #programming http://bit.ly/1ULrFh #
• 함수형 접근이 대세...
  
• RT meshula: Ambient Occlusion benchmark http://bit.ly/1idsyh by aobench ported to #golang http://bit.ly/2oYfKL , also Hask... #programming #
• Ambient Occlusion 연산 수행을 통한 벤치마크 프로그램. 정말 다양한 언어와 플랫폼으로 포팅되어 있습니다. 흥미롭군요... 제가 요즘 공부 중인 Haskell도 성능이 나쁘지 않네요. C나 ㅎㄷㄷ한 일본 친구가 만든 GPU 버전에 비하면 많이 느리지만요;
  
• RT programmingjoy: MacRuby 0.5 beta 2 is out #programming http://bit.ly/1N2IQS #
• 이런 프로젝트도 있었군요.
  
• RT a_williams: New blog entry: November 2009 C++ Standards Committee Mailing http://bit.ly/2KFhyr #C++ #programming #
• 2009년 11월 C++ 표준 위원회 모임에 관한 블로그 글
  
• RT programmingjoy: 25 Tips for Intermediate Git Users #programming http://bit.ly/31n7W2 #
• RT programmingjoy: Types in Haskell: Types are Propositions, Programs are Proofs #programming http://bit.ly/3vrMOG #
• 해스켈... 심오합니다.
  
• RT KageKirin: pystring - C++ functions matching ... of python string methods with std::string http://tinyurl.com/y9ofn5v #C++ #programming #
• C++ STL string과도 호환되면서 파이썬 문자열 연산 기능들을 지원하는 라이브러리
  
• RT programmingjoy: headache relief for programmers - regular expression generator #programming http://bit.ly/FeWmS #
• 온라인 정규표현식 생성기
  
• RT programmingjoy: Build,Compile, and test your first Android Application[video lecture] #programming http://bit.ly/Sr1UD #
• 안드로이드 개발 튜토리얼 동영상
  
• RT programmingjoy: Mercurial DVCS v1.4 released! #programming http://bit.ly/CGD4L #
• RT programmingjoy: Why Go Matters, or why Go won't take over the world, just one country. #programming http://bit.ly/4cJn3I #
• 요즘 뜨거운 감자인 Go 프로그래밍 언어에 대한 글. 그나저나 이름 문제는 해결이 되었는지 모르겠군요;
  
• RT programmingjoy: Tweet your builds with Maven Twitter Plugin #programming http://bit.ly/4o6Msw #
• 빌드 결과를 트윗해주는 Maven 플러그인
  
• RT programmingjoy: Comparing Go and Stackless Python #programming http://bit.ly/180HzP #
• Go의 비동기 루틴 및 채널 개념을 유사하게 지원하는 스택리스 파이썬
  
• RT programmingjoy: Installing Google's Go Language on Mac OS X Leopard - a walkthrough #programming http://bit.ly/3MfE6y #
• 맥오에스에 Go 언어 설치하기
  
• cdecl: C gibberish ↔ English http://su.pr/2ysi0g #C++ #programming #
• 복잡한 C 언어 선언을 영어로 번역해주는 서비스; 소스도 제공하는군요.
  
• RT programmingjoy: Stackless Python outperforms Google's Go #programming http://bit.ly/1AZnd8 #
• 스택리스 파이썬과 Go의 간단한 성능 비교
  
• RT programmingjoy: Asynchronous Go API idioms #programming http://bit.ly/3odziz #
• Go 언어에 관한 또 다른 글
  
• RT programmingjoy: The Go I Forgot: Concurrency and Go-Routines - MarkCC #programming http://bit.ly/zREJP #
• Go Go Rush!
  
• RT programmingjoy: Multicore programming in Go #programming http://bit.ly/1PbF2G #
• 또 고!
  
• RT programmingjoy: How Programmers Need To Relate To Humans And Vice-Versa [interesting read] #programming http://bit.ly/JsUMG #
• 프로그래머가 어떻게 일반인(?)들과 소통해야 하는가에 관한 흥미로운 글
  
• RT programmingjoy: A Brief Introduction to Lisp (short video series) #programming http://bit.ly/AuWaP #
• 리스프 소개 동영상
  
• RT rickasaurus: The Most Intriguing Concept In Google's Go Language http://is.gd/4UgvC #programming #
• RT programmingjoy: Portraits rendered with delaunay triangulation #programming http://bit.ly/uoyXE #
• Delaunay triangulation을 이용한 초상화. ㅎㅎ 재밌군요...
  
• The parallelism shift and C++'s memory model (pdf): http://su.pr/5YoGzE #C++ #programming #
• 병렬성과 C++0x의 메모리 모델에 관한 주옥같은 문서
  
• Overriding Virtual Functions? Use C++0x Attributes to Avoid Bugs: http://su.pr/2dzyCt #C++ #programming #
• C++0x의 attribute를 이용해 버그 피하기
  
• RT programmingjoy: C, Erlang, Java , (Google) Go Web Server performance test #programming http://bit.ly/13KtGD #
• 여러 언어를 이용한 웹서버 성능 비교
  
• RT itshooter: 6460A Visual Studio 2008- Windows Presentation Foundation : 99eBooks | Online Books Library http://bit.ly/29iwSE #programming #
• WPF에 관한 공짜 이북
  
• RT programmingjoy: Summary of all the MIT Introduction to Algorithms lectures #programming http://bit.ly/3iiPaP #
• MIT 알고리즘 강좌 요약
  
• RT programmingjoy: Gerrit: Google-style code review meets git #programming http://bit.ly/3XBdRi #
• Git과 연동되는 웹 기반 코드 리뷰 시스템
  
• RT programmingjoy: Is Python Slow? #programming http://bit.ly/4jyzWm #
• Solving ordinary differential equations in C++: http://su.pr/5DR286 #C++ #programming #
• 미분방정식을 풀기 위한 C++ 라이브러리
  
• A new #programming language from Google RT GoogleCode: Hey! Ho! Let's Go! Introducing a new experimental language - Go http://bit.ly/28z8CM #
• RT programmingjoy: Philosophizing about Programming; or "Why I'm learning to love functional programming" #programming http://bit.ly/2Se1sm #
• 내가 함수형 언어를 배우는 이유
  

개발방법론methodology

• RT LeanKitKanban: RT henrikkniberg: Kanban kick-start example, illustrating a bunch of ... http://tinyurl.com/kanbanexample #methodology #
• 바로 시작하는 칸반
  

그래픽스graphics

• RT tatsuma_mu: RT repi RT tuan_kuranes: Real Time Global Illumination Using Temporal Coherence http://bit.ly/RRwXu #graphics #
• 실시간 전역 조명에 관한 논문
  
• RT meshula: Wow! RT @_osa_ _osa_ Origami Simulator http://bit.ly/23BvU4 (via morphocode) generates crease pattern and folding... #graphics #
• 종이접기 시뮬레이터...
  
• RT repi: Been waiting for these! RT IanMcNaughton: RT ATIGraphics: RT pcper AMD Radeon HD 5970 2GB Review http://bit.ly/2RWjGi #graphics #
• 현재로선 궁극의 그래픽 카드 라데온 HD 5970 2GB에 대한 리뷰
  
• RT meshula: bjoernknafla Despite Erlang's stated goals, wings3d http://wings3d.com is the most impressive application of Erlang! #graphics #
• 얼랭으로 만들어진 3차원 모델러
  
• RT repi: AMD's interview with me about Frostbite2 & DX11 is up: http://bit.ly/3cfWgB Full longer pdf ver... http://bit.ly/4usBmA #graphics #
• DX11을 지원하는 프로스트바이트2 엔진에 관한 인터뷰
  
• RT meshula: RT tuan_kuranes: deferred rendering in frameranger. http://bit.ly/2KuyUq #gamedev #graphics #
• 지연 렌더링 기법에 관한 글
  
• RT meshula: Megatexture demo under MIT license. http://bit.ly/3fbFDs #graphics #
• id Tech 5 엔진으로 유명해진 메가텍스처 기법을 C#으로 구현한 예. 관련 기법을 연구 중인 분들께 매우 유용할 듯.
  

병렬성parallelism

• RT SoftTalkBlog: Universal cloud for programmers - full details on Intel's new Parallel Universe - http://bit.ly/2JGynD #intel #parallelism #
• 인텔이 제시하는 병렬 테스팅 플랫폼
  
• RT programmingjoy: QuickThread: A New C++ Multicore Library #programming http://bit.ly/gKAQJ #parallelism #
• 새로운 C++ 멀티코어 라이브러리
  
• RT bjoernknafla: Via ACM: #SC09 papers online (public): http://bit.ly/3alCA4 (choose "Papers" for "Selected Activities") #parallelism #
• 역시 얼마 전 있었던 SuperComputing09 발표 논문들
  
• RT SoftTalkBlog: Parallel programming tips from tibor19 at TechEd - http://bit.ly/4vACYF #tee09 #parallelism #
• 병렬 프로그래밍 팁
  
• RT bjoernknafla: RT rickmolloy: new blog post describing the Concurrency Runtime samples for Beta2 http://bit.ly/27wW0k #parallelism #
• VS2010 베타2와 함께 나온 새로운 Concurrency Runtime 예제들
  
• RT SoftTalkBlog: TechEd: How the Concurrency Coordination Runtime helps with a new parallel programmin... http://bit.ly/2OCLny #parallelism #
• RT repi: Slides for my "Parallel Futures of a Game Engine" keynote is now up! Get it while it's hot: http://repi.se #parallelism #gamedev #
• 게임 엔진 병렬화의 미래에 대한 매우 심도 있는 전망
  

게임개발gamedev

• RT inCrysis: CryEngine 3 now available for FREE for educational institutions http://bit.ly/uqZeh #gamedev #
• RT bjoernknafla: RT mlesniak: Video of the tools for the Love MMORPG: Totally impressive. Just Wow. http://bit.ly/14YkqU #gamedev #
• Love라는 이름의 MMORPG의 매우 인상적인 툴 시연
  
• RT tatsuma_mu: External Lightmapping Tool for Unity released. http://bit.ly/1mGDy9 #gamedev #
• RT meshula: Wide ranging tome! RT tatsuma_mu: Core Techniques and Algorithms in Game Programming http://bit.ly/ivTye #gamedev #programming #
• 게임 프로그래밍에서의 핵심 기법과 알고리즘에 대한 광범위한 자료
  
• RT repi: RT msinilo: *Great* GDC 2k9 presentation on state-based scripting in Uncharted2 - http://bit.ly/1au88G #programming #gamedev #
• Uncharted2에 쓰인 상태 기반 스크립팅에 대한 슬라이드 자료
  

기타etc

• RT rigmania: PMD Copy/Paste Detector(CPD) 좋네요. http://parkpd.egloos.com/1969980 #
• Copy/Paste 코딩을 검출해내기 위한 도구
  
• RT xiles: 아주 기본적인 작업만 하시고, 적은 디스크 공간에 윈도우7을 설치해보고 싶다면 Tiny Windows 7을 사용해보세요. http://bit.ly/3NIg3K #
• 크라이텍 10주년 파티 http://yfrog.com/3ng72tj #
• 어느덧 이번 주군요...
  
• 한글 트위터 사용자 디렉토리 http://KoreanTwitters.com 에 지금 등록했습니다: #프랑크푸르트 #게임개발 #프로그래밍 #크라이텍 #IT #
• RT jasonfried: So clever. A scroll-bar clock: http://bit.ly/3LYExJ #
• 스크롤바를 이용한 시계
  
• RT eHub: Tweetwally http://bit.ly/1hV9US #
• RT DeliciousHot: 25 Ways to Use Google (That You've Never Heard Of) http://bit.ly/3lGPQ4 #
• 유용한 구글 활용법들
  
• RT gamearchitect: 10 Useful Tools for Finding the Perfect Domain Name: http://bit.ly/3gtAZK #
• RT tatsuma_mu: Jobs at Apple "Job title Game/Media Software Engineer" http://bit.ly/34hG9Z #
• RT Silverchime: 스케치업용 여성형 액션 피규레이션. http://bit.ly/47m7WE 제작자분의 센스가 대단하군요. #
• RT repi: ArsTechnica article with some more public details of the AMD Fusion single die CPU/GPU http://bit.ly/1ZxuIs Makes sense as a firs #
• RT ㅋㅋ spolsky: StackOverflow discovers the rare --> operator in C++. http://bit.ly/BFlq7 #
• RT pomad: http://tr.im/ERil screener 라는 트윗 연동 서비스네요.. ㅋㅋ 재밌군요... #
• RT DeliciousHot: 100 Useful Links for eBook Lovers http://is.gd/4U2hs #
• RT gamearchitect: Google Wave Cheat Sheet: http://bit.ly/4twxeh #
• RT gamearchitect: 100 Open Courses to Learn Any New Language: http://bit.ly/3KlLB5 #
• RT gamearchitect: How to Develop Your Photography Skills - 11 steps (with pictures): http://bit.ly/gba1U #
• RT SingleFunction: News - 10 Free Tools & Resources to Find Icons For Your Website http://bit.ly/z7WHC #

ashlin, february 2008 by ∆ matt caplin ∆

p.s. 최근 블로깅에 약간 슬럼프 상태입니다... ㅠㅠ 그래서 업데이트가 많이 뜸했죠. 얼마 전 100,000 카운트도 돌파하고 했는데... 좀 더 분발해 보겠습니다. :)

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