Mercurial > hg > Members > kono > Cerium
annotate example/many_task/sort.cc @ 625:60aa3f241b10
64bit mode worked on Mac OS X.
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 16 Nov 2009 10:59:55 +0900 |
parents | 2f4b5ce2a515 |
children | c13bbb7d70b3 |
rev | line source |
---|---|
227 | 1 #include "TaskManager.h" |
573 | 2 #include "SchedTask.h" |
227 | 3 #include "sort.h" |
4 #include "Func.h" | |
5 | |
6 DataPtr data; // sort array | |
7 int data_length; | |
8 static int sort_count; // sort 完了に必要な回数 | |
9 static int split_num; // data の分割数 | |
10 static int half_num; | |
11 static int block_num; // 一つのタスクで sort する data 数 | |
12 static int last_block_num; | |
13 static int half_block_num; | |
14 static int last_half_block_num; | |
400 | 15 static TaskManager *manager; |
227 | 16 |
573 | 17 static void sort_restart(SchedTask *, void *, void *); |
400 | 18 static void sort_start(); |
227 | 19 |
20 /** | |
21 * 一つの block にある data の数が MAX_BLOCK_SIZE 超えないような | |
22 * len の分割数を返す | |
23 * | |
24 * @param len sort する data の総数 | |
25 * @param num 使用する SPE の数 | |
26 * | |
27 * @return data の分割数 | |
28 * | |
29 * TODO: | |
30 * len が num 以下とか考えてません | |
31 */ | |
32 static int | |
33 get_split_num(int len, int num) | |
34 { | |
35 if (len / num < MAX_BLOCK_SIZE) { | |
36 return num; | |
37 } else { | |
38 // 切り上げ | |
39 return (len + MAX_BLOCK_SIZE - 1) / MAX_BLOCK_SIZE; | |
40 } | |
41 } | |
42 | |
43 /** | |
44 * btask が全て終了したら、再び sort_start を実行する | |
45 * @param d 生成された btask の数 | |
46 */ | |
47 static void | |
573 | 48 sort_restart(SchedTask *s, void *d, void *e) |
227 | 49 { |
50 static int cnt = 0; | |
625
60aa3f241b10
64bit mode worked on Mac OS X.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
573
diff
changeset
|
51 long max = (long)d; |
227 | 52 |
53 if (++cnt == max) { | |
54 cnt = 0; | |
55 sort_start(); | |
56 } | |
57 } | |
58 | |
59 static void | |
400 | 60 sort_start() |
227 | 61 { |
62 if (--sort_count < 0) { | |
63 return; | |
64 } | |
65 | |
66 HTaskPtr fsort[split_num]; | |
67 | |
68 for (int i = 0; i < split_num-1; i++) { | |
69 fsort[i] = manager->create_task(QUICK_SORT); | |
70 fsort[i]->add_inData(&data[i*block_num], sizeof(Data)*block_num); | |
71 fsort[i]->add_outData(&data[i*block_num], sizeof(Data)*block_num); | |
625
60aa3f241b10
64bit mode worked on Mac OS X.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
573
diff
changeset
|
72 fsort[i]->set_param(0,(memaddr)block_num); |
227 | 73 fsort[i]->set_cpu(SPE_ANY); |
74 } | |
75 | |
76 // 最後の block は端数なので last_block_num を使う | |
77 { | |
78 int i = split_num-1; | |
79 | |
80 fsort[i] = manager->create_task(QUICK_SORT); | |
81 fsort[i]->add_inData(&data[i*block_num], sizeof(Data)*last_block_num); | |
82 fsort[i]->add_outData(&data[i*block_num], sizeof(Data)*last_block_num); | |
625
60aa3f241b10
64bit mode worked on Mac OS X.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
573
diff
changeset
|
83 fsort[i]->set_param(0,(memaddr)last_block_num); |
227 | 84 fsort[i]->set_cpu(SPE_ANY); |
85 } | |
86 | |
87 if (split_num > 1) { | |
88 HTaskPtr bsort[half_num]; | |
89 | |
90 for (int i = 0; i < half_num-1; i++) { | |
91 bsort[i] = manager->create_task(QUICK_SORT); | |
92 bsort[i]->add_inData(&data[i*block_num+half_block_num], | |
93 sizeof(Data)*block_num); | |
94 bsort[i]->add_outData(&data[i*block_num+half_block_num], | |
95 sizeof(Data)*block_num); | |
625
60aa3f241b10
64bit mode worked on Mac OS X.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
573
diff
changeset
|
96 bsort[i]->set_param(0,(memaddr)block_num); |
227 | 97 bsort[i]->set_cpu(SPE_ANY); |
98 } | |
99 | |
100 { | |
101 int i = half_num-1; | |
102 | |
103 bsort[i] = manager->create_task(QUICK_SORT); | |
104 bsort[i]->add_inData(&data[i*block_num+half_block_num], | |
105 sizeof(Data)*last_half_block_num); | |
106 bsort[i]->add_outData(&data[i*block_num+half_block_num], | |
107 sizeof(Data)*last_half_block_num); | |
625
60aa3f241b10
64bit mode worked on Mac OS X.
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
573
diff
changeset
|
108 bsort[i]->set_param(0,(memaddr)last_half_block_num); |
227 | 109 bsort[i]->set_cpu(SPE_ANY); |
110 } | |
111 | |
112 for (int i = 0; i < half_num; i++) { | |
113 bsort[i]->wait_for(fsort[i]); | |
114 bsort[i]->wait_for(fsort[i+1]); | |
573 | 115 bsort[i]->set_post(sort_restart, (void*)(half_num),0); |
227 | 116 bsort[i]->spawn(); |
117 } | |
118 } | |
119 | |
120 for (int i = 0; i < split_num; i++) { | |
121 fsort[i]->spawn(); | |
122 } | |
123 } | |
124 | |
125 void | |
400 | 126 sort_init(TaskManager *manager_, int cpuNum, int length) |
227 | 127 { |
400 | 128 manager = manager_; |
129 | |
227 | 130 data = (DataPtr)manager->allocate(sizeof(Data)*length); |
131 data_length = length; | |
132 | |
133 for (int i = 0; i < length; i++) { | |
230 | 134 data[i].index = manager->get_random()%10000; |
227 | 135 data[i].ptr = 0; |
136 } | |
137 | |
138 split_num = get_split_num(length, cpuNum); | |
139 half_num = split_num-1; | |
140 sort_count = split_num; | |
141 | |
142 block_num = (length + split_num -1)/split_num; | |
143 half_block_num = block_num/2; | |
144 | |
145 last_block_num = length - (split_num-1)*block_num; | |
146 last_half_block_num = half_block_num+(last_block_num/2); | |
147 | |
148 sort_start(); | |
149 } | |
400 | 150 |