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