'피보나치'에 해당되는 글 2건
- 2009/07/21 두가지 C++ 차세대 병렬 플랫폼 간단 비교 (1)
- 2009/06/09 n번째 피보나치 수 구하는 프로그램
- 두가지 C++ 차세대 병렬 플랫폼 간단 비교
Tweet
- Game Development
- 2009/07/21 00:20
- Cilk, Cilk++, Concurrency, fibonacci, Paralle Patterns Library, parallelism, PPL, visual studio 2010, visualstudio2010, 비주얼스튜디오2010, 비쥬얼스튜디오2010, 피보나치
-
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 베타 버전이 출시되었다는 소식을 들었습니다. 그래서 한 번 받아서 테스트 해보았습니다.
코드의 전반적인 구성에 대한 설명은 팀블로그 글을 참고해주세요. 기본적으로 거기의 예제 코드에서 메모리 관련 테스트를 빼고 병렬 버전의 함수를 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에 관련된 유용한 정보 및 소식] 에 링크 되어있습니다.
제가 일원으로 참여하고 있는 Visual Studio Team System 2010 공식 팀 블로그에 며칠 전 PPL을 이용한 피보나치 수 병렬 계산에 대한 글을 올렸습니다. 근데 그 후 Cilk++ 1.1.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에 관련된 유용한 정보 및 소식] 에 링크 되어있습니다.
'Game Development' 카테고리의 다른 글
| 잘 알려지지 않은 C++0x의 유용한 기능들 - 첫번째 (8) | 2009/07/23 |
|---|---|
| Parallelism이란 무엇인가?! (0) | 2009/07/22 |
| 두가지 C++ 차세대 병렬 플랫폼 간단 비교 (1) | 2009/07/21 |
| VSTS 2010 팀 3분기 맴버 모집 (0) | 2009/07/09 |
| Poor men's Code Coverage (2) | 2009/07/02 |
| [해외 개발자 인터뷰] Michelle Martin (0) | 2009/06/26 |
- n번째 피보나치 수 구하는 프로그램
Tweet
- Game Development
- 2009/06/09 22:10
- Exponentiation by squaring, fibonacci, recursion, Ruby, 루비, 재귀호출, 피보나치, 황금비
-
 romanesco by docman   |
다음과 같은 피보나치 수열을 아실겁니다.
0, 1에서 출발하여 다음과 같은 재귀 관계를 만족하는 수들입니다.
실제 자연 현상에서도 다양하게 확인되며, 황금비와의 관련 등 여러 흥미로운 특징을 가지는 수가 되겠습니다.
n번째 피보나치 수를 구하기 위해 가장 단순하게는 다음과 같은 함수를 만들 수 있겠죠.
하지만 따져 보시면 알겠지만 중복 계산이 많으며, 실제 지수 시간이 걸립니다.
이를 선형 시간 안에 계산하려면, 여러가지 방법이 있습니다만, 가장 금방 생각해낼 수 있는 것이 중복 계산 방지를 위해 메모이제이션을 사용하는 겁니다. 계산 결과를 캐슁해 놓았다가 재활용하는 것이지요.
F(n)이 n번째 피보나치 수라 할 때, 위와 같은 행렬식이 성립합니다. 이렇게 거듭 제곱 형태로 변경하고 나면 제곱으로 지수값 구하기를 이용하여 효율적으로 계산하는 것이 가능해집니다. (루비 코드입니다; 친절한 설명은 여길 참조)
이것이 가장 빠른 피보나치 알고리즘은 아니지만 순진한 맨위의 초기 구현보다는 큰 n에 대해서 훨씬 빠르겠죠.
 Fibonachess by fdecomite |
매우 간단한 수학 문제지만 실제 프로그래밍으로의 구현에서는 생각할 것이 많은... 그래서 인터뷰 질문으로 매우 유용한 소재라고 생각합니다.
참고: 피보나치 수 프로그램
'Game Development' 카테고리의 다른 글
| 게임 프로그래머를 위한 Yammer 그룹 가입신청 받습니다. (13) | 2009/06/19 |
|---|---|
| 크라이텍 깜짝 선물 (2) | 2009/06/16 |
| n번째 피보나치 수 구하는 프로그램 (0) | 2009/06/09 |
| D&D-style map of C++ (2) | 2009/06/06 |
| Double-checked locking 이디엄의 함정 (2) | 2009/06/03 |
| Iterators Must Go! (in favor of ranges) (2) | 2009/05/15 |
Recent comment