Mercurial > hg > Members > kono > Cerium

comparison example/many_task/sort.cc @ 935:e54842e4d97b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
-a option for sort
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Sat, 31 Jul 2010 03:13:24 +0900
parents da657af64afd
children 14fb1c888931
comparison
equal deleted inserted replaced
934:da657af64afd 935:e54842e4d97b
8 extern void check_data(); 8 extern void check_data();
9 9
10 static DataPtr data; 10 static DataPtr data;
11 static int data_length; 11 static int data_length;
12 static int cpuNum; 12 static int cpuNum;
13
14 extern int all;
13 15
14 /** 16 /**
15 * 一つの block にある data の数が MAX_BLOCK_SIZE 超えないような 17 * 一つの block にある data の数が MAX_BLOCK_SIZE 超えないような
16 * len の分割数を返す 18 * len の分割数を返す
17 * 19 *
35 } 37 }
36 38
37 39
38 HTaskPtr *fsort; 40 HTaskPtr *fsort;
39 HTaskPtr *bsort; 41 HTaskPtr *bsort;
40 42 int split_num;
41 #define ALL_TASK 43
42
43 #ifdef ALL_TASK
44
45 static void
46 sort_start(SchedTask *manager)
47 {
48 int split_num = get_split_num(data_length, cpuNum); // data の分割数
49 int half_num = split_num-1;
50 static int sort_count = split_num; // sort 完了に必要な回数
51
52 // 一つのタスクで sort する data 数
53 int block_num = (data_length + split_num -1)/split_num;
54 int half_block_num = block_num/2;
55
56 int last_block_num = data_length - (split_num-1)*block_num;
57 int last_half_block_num = half_block_num+(last_block_num/2);
58
59 while (--sort_count > 0) {
60
61 for (int i = 0; i < split_num-1; i++) {
62 fsort[i] = manager->create_task(QUICK_SORT,
63 (memaddr)&data[i*block_num], sizeof(Data)*block_num,
64 (memaddr)&data[i*block_num], sizeof(Data)*block_num);
65 if (i>0 && bsort[i-1]) {
66 fsort[i]->wait_for(bsort[i-1]);
67 }
68 if (i<split_num-2 && bsort[i]) {
69 fsort[i]->wait_for(bsort[i]);
70 }
71 fsort[i]->set_cpu(SPE_ANY);
72 }
73
74 // 最後の block は端数なので last_block_num を使う
75 {
76 int i = split_num-1;
77
78 fsort[i] = manager->create_task(QUICK_SORT,
79 (memaddr)&data[i*block_num], sizeof(Data)*last_block_num,
80 (memaddr)&data[i*block_num], sizeof(Data)*last_block_num);
81 if (i>0 && bsort[i-1]) {
82 fsort[i]->wait_for(bsort[i-1]);
83 }
84 fsort[i]->set_cpu(SPE_ANY);
85 }
86
87 if (split_num > 1) {
88
89 for (int i = 0; i < half_num-1; i++) {
90 bsort[i] = manager->create_task(QUICK_SORT,
91 (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num,
92 (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*block_num);
93 bsort[i]->set_cpu(SPE_ANY);
94 }
95
96 {
97 int i = half_num-1;
98
99 bsort[i] = manager->create_task(QUICK_SORT,
100 (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num,
101 (memaddr)&data[i*block_num+half_block_num], sizeof(Data)*last_half_block_num);
102 bsort[i]->set_cpu(SPE_ANY);
103 }
104
105 for (int i = 0; i < half_num; i++) {
106 bsort[i]->wait_for(fsort[i]);
107 bsort[i]->wait_for(fsort[i+1]);
108 bsort[i]->spawn();
109 }
110 }
111
112 for (int i = 0; i < split_num; i++) {
113 fsort[i]->spawn();
114 }
115 }
116 }
117
118 #else
119 44
120 /** 45 /**
121 * btask が全て終了したら、再び sort_start を実行する 46 * btask が全て終了したら、再び sort_start を実行する
122 * @param d 生成された btask の数 47 * @param d 生成された btask の数
123 */ 48 */
124 static void 49
50 SchedDefineTask1(RESTART, sort_restart );
51
52 static int
125 sort_restart(SchedTask *s, void *d, void *e) 53 sort_restart(SchedTask *s, void *d, void *e)
126 { 54 {
127 static int cnt = 0;
128 static int ccc = 0; 55 static int ccc = 0;
129 long max = (long)d; 56
130 57 printf("restarted %d %% %d\n",ccc++,split_num);
131 if (++cnt == max) { 58 sort_start(s);
132 printf("restarted %d %% %ld\n",ccc++,max); 59 return 0;
133 cnt = 0;
134 sort_start(s);
135 }
136 } 60 }
137 #ifdef USE_SIMPLE_TASK 61 #ifdef USE_SIMPLE_TASK
138 62
139 static void 63 static void
140 sort_start(SchedTask *manager) 64 sort_start(SchedTask *manager)
141 { 65 {
142 int split_num = get_split_num(data_length, cpuNum); // data の分割数
143 int half_num = split_num-1; 66 int half_num = split_num-1;
144 static int sort_count = split_num; // sort 完了に必要な回数 67 static int sort_count = split_num; // sort 完了に必要な回数
145 68
146 // 一つのタスクで sort する data 数 69 // 一つのタスクで sort する data 数
147 int block_num = (data_length + split_num -1)/split_num; 70 int block_num = (data_length + split_num -1)/split_num;
205 bsort[i]->wait_for(fsort[i+1]); 128 bsort[i]->wait_for(fsort[i+1]);
206 bsort[i]->spawn(); 129 bsort[i]->spawn();
207 } 130 }
208 } 131 }
209 132
133 HTaskPtr restart = manager->create_task(RESTART,0,0,0,0);
210 for (int i = 0; i < split_num; i++) { 134 for (int i = 0; i < split_num; i++) {
211 fsort[i]->set_post(sort_restart, (void*)(half_num),(void*)manager); 135 if (!all) restart->wait_for(fsort[i]);
212 fsort[i]->spawn(); 136 fsort[i]->spawn();
213 } 137 }
138 restart->spawn();
214 } 139 }
215 140
216 #else 141 #else
217 142
218 static void 143 static void
219 sort_start(SchedTask *manager) 144 sort_start(SchedTask *manager)
220 { 145 {
221 int split_num = get_split_num(data_length, cpuNum); // data の分割数
222 int half_num = split_num-1; 146 int half_num = split_num-1;
223 static int sort_count = split_num; // sort 完了に必要な回数 147 static int sort_count = split_num; // sort 完了に必要な回数
224 148
225 // 一つのタスクで sort する data 数 149 // 一つのタスクで sort する data 数
226 int block_num = (data_length + split_num -1)/split_num; 150 int block_num = (data_length + split_num -1)/split_num;
294 bsort[i]->wait_for(fsort[i+1]); 218 bsort[i]->wait_for(fsort[i+1]);
295 bsort[i]->spawn(); 219 bsort[i]->spawn();
296 } 220 }
297 } 221 }
298 222
223 HTask restart = create_task(RESTART,0,0,0,0);
299 for (int i = 0; i < split_num; i++) { 224 for (int i = 0; i < split_num; i++) {
300 fsort[i]->set_post(sort_restart, (void*)(half_num),(void*)manager); 225 if (!all) restart->wait_for(fsort[i]);
301 fsort[i]->spawn(); 226 fsort[i]->spawn();
302 } 227 }
303 } 228 restart->spawn();
304 #endif 229
230 }
305 #endif 231 #endif
306 232
307 void check_data() 233 void check_data()
308 { 234 {
309 int flag = 1; 235 int flag = 1;
315 } 241 }
316 } 242 }
317 if (flag) printf("Data are sorted\n"); 243 if (flag) printf("Data are sorted\n");
318 } 244 }
319 245
246
320 void 247 void
321 sort_init(SchedTask *manager, void *a, void *b) 248 sort_init(SchedTask *manager, void *a, void *b)
322 { 249 {
323 cpuNum = (int)a; 250 cpuNum = (int)a;
324 int length = (int)b; 251 int length = (int)b;
325 252
326 data = (DataPtr)manager->allocate(sizeof(Data)*length); 253 data = (DataPtr)manager->allocate(sizeof(Data)*length);
327 data_length = length; 254 data_length = length;
328 255
329 int split_num = get_split_num(data_length, cpuNum); // data の分割数 256 split_num = get_split_num(data_length, cpuNum); // data の分割数
330 int half_num = split_num-1; 257 int half_num = split_num-1;
331 fsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*split_num); 258 fsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*split_num);
332 bsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*half_num); 259 bsort = (HTaskPtr*)manager->allocate(sizeof(HTaskPtr)*half_num);
333 memset((void*)bsort,0, sizeof(HTaskPtr)*half_num); 260 memset((void*)bsort,0, sizeof(HTaskPtr)*half_num);
334 261