오래만에 돌아왔습니다.
동영상 자막 번역은 영 아니다라는 판단하에(?), 일반적인 형식으로
C++0x와
Visual Studio 2010에서의 병렬 프로그래밍에 대해 글을 써볼 생각입니다.
일단
http://code.msdn.microsoft.com/concrtextras 에서 샘플 코드를 받으십시오. 그를 기준으로 당분간은 진행 예정입니다. 당연히 돌려보려면
Visual Studio 2010 베타1이 필요합니다.
오늘은
Parallel Patterns Library를 이용한
피보나치 수 계산 예부터 살펴보죠. 순차 수행 버전과
PPL의 태스크 기능을 이용한 병렬 수행 버전의 성능 비교가 첫번째 핵심 사항입니다. 그리고 malloc 대
Concurrency::Alloc의 성능 비교가 두번째 핵심 사항 되겠습니다.
소스를 찬찬히 살펴보죠.
8 #include "windows.h"
9 #include <ppl.h>
10
11 using namespace Concurrency;
12
13 int SPINCOUNT = 25;
14
15 //Spins for a fixed number of loops
16 #pragma optimize("", off)
17 void delay()
18 {
19 for(int i=0;i < SPINCOUNT;++i);
20 };
21 #pragma optimize("", on)
먼저 헤더 파일 포함이 나오고, 각 작업의 계산 부하 조절을 위한 idle loop 함수가 나옵니다. pragma 디렉티브로 최적화를 해당 함수에 대해서만 끄고 있습니다. 그래야 실제 부하 조절 용도로 의미가 있겠죠.
23 //Times execution of a functor in ms
24 template <class Functor>
25 __int64 time_call(Functor& fn)
26 {
27 __int64 begin, end;
28 begin = GetTickCount();
29 fn();
30 end = GetTickCount();
31 return end - begin;
32 };
이 함수는 단순히 프로파일링(성능 측정)을 위한 유틸리티 함수 되겠습니다.
34 //Computes the fibonacci number of 'n' serially
35 int fib(int n)
36 {
37 delay();
38 if (n< 2)
39 return n;
40 int n1, n2;
41 n1 = fib(n-1);
42 n2 = fib(n-2);
43 return n1 + n2;
44 }
실제 가장 이해하기 쉬운 재귀 방식의 피보나치 수 구하기 함수입니다. 당연히
이 방식은 중복 계산이 많아 성능이 한참 떨어지게 되는데요, 이 글의 쟁점은 아니므로 넘어갑니다.
45 //Computes the fibonacci number of 'n' in parallel
46 int struct_fib(int n)
47 {
48 delay();
49 if (n< 2)
50 return n;
51 int n1, n2;
52
53 //declare a structured task group
54 structured_task_group tasks;
55
56 //invoke the first half as a task
57 auto task1 = make_task([&n1,n]{n1 = struct_fib(n-1);});
58 tasks.run(task1);
59
60 //run the second recursive call inline
61 n2 = struct_fib(n-2);
62
63 //wait for completion
64 tasks.wait();
65
66 return n1 + n2;
67 }
다음은 해당 알고리즘의 병렬 구현입니다.
structured_task_group 변수를 하나 선언하고, make_task를 이용해 재귀 호출의 한쪽을 담당할 태스크를 만든 뒤, 태스크 그룹을 통해 돌립니다. tasks.wait() 호출을 통해 스폰한 태스크 작업이 마무리될 때까지 대기한 후, 최종 결과를 리턴하고 있습니다.
C++0x의 람다가 쓰이고 있는 것을 확인하실 수 있습니다.
재귀적으로 호출이 되면서 꽤나 많은 태스크들이 만들어질텐데, 그냥
스레드 수준에서 직접 이런 작업을 했다면, 실제 하드웨어가 지원하는 병렬 수행의 수보다
과도하게 많은 스레드 생성이 이루어지면서, 상당히 비효율적으로 돌텐데요. PPL의 태스크 개념을 사용해 이렇게 보다
고수준에서 작업하면 그러한 오버헤드를 상당 부분 알아서 최적화 해줍니다.
69 //Computes the fibonacci number of 'n' allocating storage for integers on heap
70 int struct_fib_heap(int n)
71 {
72 delay();
73 if (n< 2)
74 return n;
75 //n1 and n2 are now allocated on the heap
76 int* n1;
77 int* n2;
78
79 //declare a task_group
80 structured_task_group tg;
81
82 auto t1 = make_task([&]{
83 n1 = (int*) malloc(sizeof(int));
84 *n1 = struct_fib_heap(n-1);
85 });
86 tg.run(t1);
87 n2 = (int*) malloc(sizeof(int));
88 *n2 = struct_fib_heap(n-2);
89 tg.wait();
90 int result = *n1 + *n2;
91 free(n1);
92 free(n2);
93 return result;
94 }
malloc으로 힙에 버퍼를 잡아 결과를 리턴하는 버전입니다.
Concurrency::Alloc과의 성능 비교를 위한 함수 되겠습니다.
95 //Computes the fibonacci number of 'n' using the ConcRT suballocator
96 int struct_fib_concrt_heap(int n)
97 {
98 delay();
99 if (n< 2)
100 return n;
101 int* n1;
102 int* n2;
103 structured_task_group tg;
104 auto t1 = make_task([&]{
105 n1 = (int*) Concurrency::Alloc(sizeof(int));
106 *n1 = struct_fib_concrt_heap(n-1);
107 });
108 tg.run(t1);
109 n2 = (int*) Concurrency::Alloc(sizeof(int));
110 *n2 = struct_fib_concrt_heap(n-2);
111 tg.wait();
112 int result = *n1 + *n2;
113 Concurrency::Free(n1);
114 Concurrency::Free(n2);
115 return result;
116 }
이번에는
병렬 런타임의 suballocator를 이용하고 있습니다.
117 int main()
118 {
119 int num = 30;
120 SPINCOUNT = 500;
121 double serial, parallel;
122
123 //compare the timing of serial vs parallel fibonacci
124 printf("computing fibonacci of %d serial vs parallel\n",num);
125 printf("\tserial: ");
126 serial= (double)time_call([=](){fib(num);});
127 printf("%4.0f ms\n",serial);
128
129 printf("\tparallel: ");
130 parallel = (double)time_call([=](){struct_fib(num);});
131 printf("%4.0f ms\n",parallel);
132
133 printf("\tspeedup: %4.2fX\n",serial/parallel);
134
135 //compare the timing of malloc vs Concurrency::Alloc,
136 //where we expect to get speedups because there are a large
137 //number of small malloc and frees.
138
139 //increase the number of tasks
140 num = 34;
141
142 //reduce the amount of 'work' in each task
143 SPINCOUNT = 0;
144
145 //execute fib using new & delete
146 printf("computing fibonacci of %d using heap\n",num);
147 printf("\tusing malloc: ");
148 serial= (double)time_call([=](){struct_fib_heap(num);});
149 printf("%4.0f ms\n",serial);
150
151 //execute fib using the concurrent suballocator
152 printf("\tusing Concurrency::Alloc: ");
153 parallel = (double)time_call([=](){struct_fib_concrt_heap(num);});
154 printf("%4.0f ms\n",parallel);
155
156 printf("\tspeedup: %4.2fX\n",serial/parallel);
157
158 return 0;
159 }
마지막으로 main 함수입니다. 단순히 각 함수를 호출하고 시간을 측정한 뒤 적절한 메시지를 출력하고 있습니다. 역시 람다가 쓰여 구문이 간결해졌습니다.
2 코어 머신에서 디버그 버전으로 돌려본 결과는 다음과 같습니다.
순차 대 병렬 버전의 경우
1.29배 속도 향상,
malloc 대 Concurrency::Alloc의 경우
2.60배 속도 향상을 확인할 수 있습니다. 병렬 버전에서의 속도 향상이 생각보다 미미한데요. 제 컴퓨터가 좀 문제(?)가 있어서 그럴지도 모르겠습니다;
한편, 병렬 환경에서 메모리 할당 및 해제가 빈번한 경우, 반드시 병렬 런타임의 할당자를 써야겠군요.
※
추가:
제 블로그에 관련 주제로
글(두가지 C++ 차세대 병렬 플랫폼 간단 비교)을 하나 올렸습니다. 참고하세요. ^^
Umc.Core.Tools.PresentationMouseTracker.v1.0.vsix
TL25[1].srt
TDD and BDD via Mock of POWERUMC.zip
