Mercurial > hg > Game > Cerium

comparison example/many_task/sort.cc @ 945:9ed1c4a877ca draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
sort example fix ( simple task accepts one param and more compatible with old task)
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sun, 01 Aug 2010 19:29:27 +0900
parents fc6cfaae6de7
children 774eba654643
comparison
equal deleted inserted replaced
944:0ab84d4c689a 945:9ed1c4a877ca
2 #include "SchedTask.h" 2 #include "SchedTask.h"
3 #include "sort.h" 3 #include "sort.h"
4 #include "Func.h" 4 #include "Func.h"
5 #include <string.h> 5 #include <string.h>
6 6
7 extern void check_data(); 7 extern int get_split_num(int len, int num);
8 extern int all; // allocate task at once 8 extern int all; // allocate task at once
9
10 static void sort_start(SchedTask *);
11 static int data_length;
12 static int cpuNum;
13 static int split_num;
14 9
15 /** 10 /**
16 * 一つの block にある data の数が MAX_BLOCK_SIZE 超えないような 11 * 一つの block にある data の数が MAX_BLOCK_SIZE 超えないような
17 * len の分割数を返す 12 * len の分割数を返す
18 * 13 *
22 * @return data の分割数 17 * @return data の分割数
23 * 18 *
24 * TODO: 19 * TODO:
25 * len が num 以下とか考えてません 20 * len が num 以下とか考えてません
26 */ 21 */
27 static int 22 int
28 get_split_num(int len, int num) 23 get_split_num(int len, int num)
29 { 24 {
30 if (len / num < MAX_BLOCK_SIZE) { 25 if (len / num < MAX_BLOCK_SIZE) {
31 return num; 26 return num;
32 } else { 27 } else {
34 return (len + MAX_BLOCK_SIZE - 1) / MAX_BLOCK_SIZE; 29 return (len + MAX_BLOCK_SIZE - 1) / MAX_BLOCK_SIZE;
35 } 30 }
36 } 31 }
37 32
38 33
39 static HTaskPtr *fsort;
40 static HTaskPtr *bsort;
41
42 static DataPtr data;
43
44 /** 34 /**
45 * btask が全て終了したら、再び sort_start を実行する 35 * btask が全て終了したら、再び sort_start を実行する
46 * @param d 生成された btask の数 36 * @param d 生成された btask の数
47 */ 37 */
48 38
49 SchedDefineTask1(RESTART, sort_restart ); 39 SchedDefineTask1(SortSimple, sort_start );
50 40
51 static int 41 static int
52 sort_restart(SchedTask *s, void *d, void *e) 42 sort_start(SchedTask *manager, void *d, void *e)
53 { 43 {
54 // static int ccc = 0; 44 Sort *s = (Sort*)manager->get_param(0);
55 45 int half_num = s->split_num-1;
56 // printf("restarted %d %% %d\n",ccc++,split_num); 46 static int sort_count = s->split_num; // sort 完了に必要な回数
57 sort_start(s);
58 return 0;
59 }
60 #ifdef USE_SIMPLE_TASK
61
62 static void
63 sort_start(SchedTask *manager)
64 {
65 int half_num = split_num-1;
66 static int sort_count = split_num; // sort 完了に必要な回数
67 47
68 // 一つのタスクで sort する data 数 48 // 一つのタスクで sort する data 数
69 int block_num = (data_length + split_num -1)/split_num; 49 int block_num = (s->data_length + s->split_num -1)/s->split_num;
70 int half_block_num = block_num/2; 50 int half_block_num = block_num/2;
71 51
72 int last_block_num = data_length - (split_num-1)*block_num; 52 int last_block_num = s->data_length - (s->split_num-1)*block_num;
73 int last_half_block_num = half_block_num+(last_block_num/2); 53 int last_half_block_num = half_block_num+(last_block_num/2);
74 54
75 if (--sort_count < 0) { 55 if (--sort_count < 0) {
76 return; 56 return 0;
77 } 57 }
78 58
79 59
80 for (int i = 0; i < split_num-1; i++) { 60 for (int i = 0; i < s->split_num-1; i++) {
81 fsort[i] = manager->create_task(QUICK_SORT, 61 s->fsort[i] = manager->create_task(QUICK_SORT,
82 (memaddr)&data[i*block_num], sizeof(Data)*block_num, 62 (memaddr)&s->data[i*block_num], sizeof(Data)*block_num,
83 (memaddr)&data[i*block_num], sizeof(Data)*block_num); 63 (memaddr)&s->data[i*block_num], sizeof(Data)*block_num);
84 if (i>0 && bsort[i-1]) { 64 if (i>0 && s->bsort[i-1]) {
85 fsort[i]->wait_for(bsort[i-1]); 65 s->fsort[i]->wait_for(s->bsort[i-1]);
86 } 66 }
87 if (i<split_num-2 && bsort[i]) { 67 if (i<s->split_num-2 && s->bsort[i]) {
88 fsort[i]->wait_for(bsort[i]); 68 s->fsort[i]->wait_for(s->bsort[i]);
89 } 69 }
90 fsort[i]->set_cpu(SPE_ANY); 70 s->fsort[i]->set_cpu(SPE_ANY);
91 } 71 }
92 72
93 // 最後の block は端数なので last_block_num を使う 73 // 最後の block は端数なので last_block_num を使う
94 { 74 {
95 int i = split_num-1; 75 int i = s->split_num-1;
96 76
97 fsort[i] = manager->create_task(QUICK_SORT, 77 s->fsort[i] = manager->create_task(QUICK_SORT,
98 (memaddr)&data[i*block_num], sizeof(Data)*last_block_num, 78 (memaddr)&s->data[i*block_num], sizeof(Data)*last_block_num,
99 (memaddr)&data[i*block_num], sizeof(Data)*last_block_num); 79 (memaddr)&s->data[i*block_num], sizeof(Data)*last_block_num);
100 if (i>0 && bsort[i-1]) { 80 if (i>0 && s->bsort[i-1]) {
101 fsort[i]->wait_for(bsort[i-1]); 81 s->fsort[i]->wait_for(s->bsort[i-1]);
102 } 82 }
103 fsort[i]->set_cpu(SPE_ANY); 83 s->fsort[i]->set_cpu(SPE_ANY);
104 } 84 }
105 85
106 if (split_num > 1) { 86 if (s->split_num > 1) {
107 87
108 for (int i = 0; i < half_num-1; i++) { 88 for (int i = 0; i < half_num-1; i++) {
109 if (bsort[i]) manager->free_htask(bsort[i]); 89 if (s->bsort[i]) manager->free_htask(s->bsort[i]);
110 bsort[i] = manager->create_task(QUICK_SORT, 90 s->bsort[i] = manager->create_task(QUICK_SORT,
111 (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num, 91 (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*block_num,
112 (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num); 92 (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*block_num);
113 bsort[i]->set_cpu(SPE_ANY); 93 s->bsort[i]->set_cpu(SPE_ANY);
114 } 94 }
115 95
116 { 96 {
117 int i = half_num-1; 97 int i = half_num-1;
118 98
119 if (bsort[i]) manager->free_htask(bsort[i]); 99 if (s->bsort[i]) manager->free_htask(s->bsort[i]);
120 bsort[i] = manager->create_task(QUICK_SORT, 100 s->bsort[i] = manager->create_task(QUICK_SORT,
121 (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num, 101 (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num,
122 (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num); 102 (memaddr)&s->data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num);
123 bsort[i]->set_cpu(SPE_ANY); 103 s->bsort[i]->set_cpu(SPE_ANY);
124 } 104 }
125 105
126 for (int i = 0; i < half_num; i++) { 106 for (int i = 0; i < half_num; i++) {
127 bsort[i]->wait_for(fsort[i]); 107 s->bsort[i]->wait_for(s->fsort[i]);
128 bsort[i]->wait_for(fsort[i+1]); 108 s->bsort[i]->wait_for(s->fsort[i+1]);
129 bsort[i]->no_auto_free(); 109 s->bsort[i]->no_auto_free();
130 bsort[i]->spawn(); 110 s->bsort[i]->spawn();
131 } 111 }
132 } 112 }
133 113
134 HTaskPtr restart = manager->create_task(RESTART,0,0,0,0); 114 HTaskPtr restart = manager->create_task(SortSimple,0,0,0,0);
135 for (int i = 0; i < split_num; i++) { 115 restart->set_param(0,(memaddr)s);
136 if (!all) restart->wait_for(fsort[i]); 116 if (!all) restart->wait_for(s->fsort[0]);
137 fsort[i]->spawn(); 117 for (int i = 0; i < s->split_num; i++) {
118 s->fsort[i]->spawn();
138 } 119 }
139 restart->spawn(); 120 restart->spawn();
140 } 121 return 0;
141
142 #else
143
144 static void
145 sort_start(SchedTask *manager)
146 {
147 int half_num = split_num-1;
148 static int sort_count = split_num; // sort 完了に必要な回数
149
150 // 一つのタスクで sort する data 数
151 int block_num = (data_length + split_num -1)/split_num;
152 int half_block_num = block_num/2;
153
154 int last_block_num = data_length - (split_num-1)*block_num;
155 int last_half_block_num = half_block_num+(last_block_num/2);
156
157
158 if (--sort_count < 0) {
159 return;
160 }
161
162
163 for (int i = 0; i < split_num-1; i++) {
164 fsort[i] = manager->create_task(QUICK_SORT);
165 fsort[i]->add_inData(&data[i*block_num], sizeof(Data)*block_num);
166 fsort[i]->add_outData(&data[i*block_num], sizeof(Data)*block_num);
167 fsort[i]->set_param(0,(memaddr)block_num);
168 if (i>0 && bsort[i-1]) {
169 fsort[i]->wait_for(bsort[i-1]);
170 }
171 if (i<split_num-2 && bsort[i]) {
172 fsort[i]->wait_for(bsort[i]);
173 }
174 fsort[i]->set_cpu(SPE_ANY);
175 }
176
177 // 最後の block は端数なので last_block_num を使う
178 {
179 int i = split_num-1;
180
181 fsort[i] = manager->create_task(QUICK_SORT);
182 fsort[i]->add_inData(&data[i*block_num], sizeof(Data)*last_block_num);
183 fsort[i]->add_outData(&data[i*block_num], sizeof(Data)*last_block_num);
184 fsort[i]->set_param(0,(memaddr)last_block_num);
185 if (i>0 && bsort[i-1]) {
186 fsort[i]->wait_for(bsort[i-1]);
187 }
188 fsort[i]->set_cpu(SPE_ANY);
189 }
190
191 if (split_num > 1) {
192
193 for (int i = 0; i < half_num-1; i++) {
194 if (bsort[i]) manager->free_htask(bsort[i]);
195 bsort[i] = manager->create_task(QUICK_SORT);
196 bsort[i]->add_inData(&data[i*block_num+half_block_num],
197 sizeof(Data)*block_num);
198 bsort[i]->add_outData(&data[i*block_num+half_block_num],
199 sizeof(Data)*block_num);
200 bsort[i]->set_param(0,(memaddr)block_num);
201 bsort[i]->set_cpu(SPE_ANY);
202 }
203
204 {
205 int i = half_num-1;
206
207 if (bsort[i]) manager->free_htask(bsort[i]);
208 bsort[i] = manager->create_task(QUICK_SORT);
209 bsort[i]->add_inData(&data[i*block_num+half_block_num],
210 sizeof(Data)*last_half_block_num);
211 bsort[i]->add_outData(&data[i*block_num+half_block_num],
212 sizeof(Data)*last_half_block_num);
213 bsort[i]->set_param(0,(memaddr)last_half_block_num);
214 bsort[i]->set_cpu(SPE_ANY);
215 }
216
217 for (int i = 0; i < half_num; i++) {
218 bsort[i]->wait_for(fsort[i]);
219 bsort[i]->wait_for(fsort[i+1]);
220 bsort[i]->no_auto_free();
221 bsort[i]->spawn();
222 }
223 }
224
225 HTaskPtr restart = manager->create_task(RESTART,0,0,0,0);
226 for (int i = 0; i < split_num; i++) {
227 if (!all) restart->wait_for(fsort[i]);
228 fsort[i]->spawn();
229 }
230 restart->spawn();
231 }
232
233 #endif
234
235 void check_data()
236 {
237 for(int i=0; i< data_length-1;i++) {
238 if (data[i].index>data[i+1].index) {
239 printf("Data are not sorted at %d. %d > %d \n",i, data[i].index,data[i+1].index);
240 return;
241 }
242 }
243 printf("Data are sorted\n");
244 } 122 }
245 123
246 124
247 void
248 sort_init(SchedTask *manager, void *a, void *b)
249 {
250 cpuNum = (int)a;
251 int length = (int)b;
252
253 data = (DataPtr)manager->allocate(sizeof(Data)*length);
254 data_length = length;
255
256 split_num = get_split_num(data_length, cpuNum); // data の分割数
257 int half_num = split_num-1;
258 fsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*split_num);
259 bsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*half_num);
260 memset((void*)bsort,0, sizeof(HTaskPtr)*half_num);
261
262 for (int i = 0; i < length; i++) {
263 data[i].index = manager->get_random()%10000;
264 data[i].ptr = i;
265 }
266
267 sort_start(manager);
268 }
269
270 /* end */ 125 /* end */