1 /*
2 * heuristical_co_ld.c
3 *
4 * Created on: 06.05.2010
5 * Author: berschth
6 */
7
8 #include "config.h"
9
10 #include "adt/array.h"
11 #include "assert.h"
12 #include "error.h"
13
14 #include "bucket.h"
15 #include "heuristical_co_ld.h"
16 #include "optimal.h"
17 #if KAPS_DUMP
18 #include "html_dumper.h"
19 #endif
20 #include "kaps.h"
21 #include "matrix.h"
22 #include "pbqp_edge.h"
23 #include "pbqp_edge_t.h"
24 #include "pbqp_node.h"
25 #include "pbqp_node_t.h"
26 #include "vector.h"
27
28 #include "plist.h"
29 #include "timing.h"
30
back_propagate_RI(pbqp_t * pbqp,pbqp_node_t * node)31 static void back_propagate_RI(pbqp_t *pbqp, pbqp_node_t *node)
32 {
33 pbqp_edge_t *edge;
34 pbqp_node_t *other;
35 pbqp_matrix_t *mat;
36 vector_t *vec;
37 int is_src;
38
39 (void) pbqp;
40
41 edge = node->edges[0];
42 mat = edge->costs;
43 is_src = edge->src == node;
44 vec = node->costs;
45
46 if (is_src) {
47 other = edge->tgt;
48 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
49 } else {
50 other = edge->src;
51 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
52 }
53
54 #if KAPS_DUMP
55 if (pbqp->dump_file) {
56 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
57 }
58 #endif
59 }
60
back_propagate_RII(pbqp_t * pbqp,pbqp_node_t * node)61 static void back_propagate_RII(pbqp_t *pbqp, pbqp_node_t *node)
62 {
63 pbqp_edge_t *src_edge = node->edges[0];
64 pbqp_edge_t *tgt_edge = node->edges[1];
65 int src_is_src = src_edge->src == node;
66 int tgt_is_src = tgt_edge->src == node;
67 pbqp_matrix_t *src_mat;
68 pbqp_matrix_t *tgt_mat;
69 pbqp_node_t *src_node;
70 pbqp_node_t *tgt_node;
71 vector_t *vec;
72 vector_t *node_vec;
73 unsigned col_index;
74 unsigned row_index;
75
76 assert(pbqp);
77
78 if (src_is_src) {
79 src_node = src_edge->tgt;
80 } else {
81 src_node = src_edge->src;
82 }
83
84 if (tgt_is_src) {
85 tgt_node = tgt_edge->tgt;
86 } else {
87 tgt_node = tgt_edge->src;
88 }
89
90 /* Swap nodes if necessary. */
91 if (tgt_node->index < src_node->index) {
92 pbqp_node_t *tmp_node;
93 pbqp_edge_t *tmp_edge;
94
95 tmp_node = src_node;
96 src_node = tgt_node;
97 tgt_node = tmp_node;
98
99 tmp_edge = src_edge;
100 src_edge = tgt_edge;
101 tgt_edge = tmp_edge;
102
103 src_is_src = src_edge->src == node;
104 tgt_is_src = tgt_edge->src == node;
105 }
106
107 src_mat = src_edge->costs;
108 tgt_mat = tgt_edge->costs;
109
110 node_vec = node->costs;
111
112 row_index = src_node->solution;
113 col_index = tgt_node->solution;
114
115 vec = vector_copy(pbqp, node_vec);
116
117 if (src_is_src) {
118 vector_add_matrix_col(vec, src_mat, row_index);
119 } else {
120 vector_add_matrix_row(vec, src_mat, row_index);
121 }
122
123 if (tgt_is_src) {
124 vector_add_matrix_col(vec, tgt_mat, col_index);
125 } else {
126 vector_add_matrix_row(vec, tgt_mat, col_index);
127 }
128
129 node->solution = vector_get_min_index(vec);
130
131 #if KAPS_DUMP
132 if (pbqp->dump_file) {
133 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
134 }
135 #endif
136
137 obstack_free(&pbqp->obstack, vec);
138 }
139
back_propagate_RN(pbqp_t * pbqp,pbqp_node_t * node)140 static void back_propagate_RN(pbqp_t *pbqp, pbqp_node_t *node)
141 {
142 vector_t *vec = NULL;
143 pbqp_node_t *neighbor = NULL;
144 pbqp_edge_t *edge = NULL;
145 unsigned edge_index = 0;
146
147 assert(pbqp);
148
149 vec = vector_copy(pbqp, node->costs);
150
151 for(edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
152 /* get neighbor node */
153 edge = node->edges[edge_index];
154 neighbor = edge->src == node ? edge->tgt : edge->src;
155
156 /* node is edge src node */
157 if(edge->src == node)
158 vector_add_matrix_col(vec, edge->costs, neighbor->solution);
159 /* node is edge tgt node */
160 else
161 vector_add_matrix_row(vec, edge->costs, neighbor->solution);
162 }
163
164 assert(vector_get_min(vec) != INF_COSTS);
165 node->solution = vector_get_min_index(vec);
166
167 #if KAPS_DUMP
168 if (pbqp->dump_file) {
169 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
170 }
171 #endif
172
173 obstack_free(&pbqp->obstack, vec);
174 }
175
back_propagate_ld(pbqp_t * pbqp)176 static void back_propagate_ld(pbqp_t *pbqp)
177 {
178 unsigned node_index;
179 unsigned node_len = node_bucket_get_length(reduced_bucket);
180
181 assert(pbqp);
182
183 #if KAPS_DUMP
184 if (pbqp->dump_file) {
185 pbqp_dump_section(pbqp->dump_file, 2, "Back Propagation");
186 }
187 #endif
188
189 for (node_index = node_len; node_index > 0; --node_index) {
190 pbqp_node_t *node = reduced_bucket[node_index - 1];
191
192 switch (pbqp_node_get_degree(node)) {
193 case 1:
194 back_propagate_RI(pbqp, node);
195 break;
196 case 2:
197 back_propagate_RII(pbqp, node);
198 break;
199 default:
200 back_propagate_RN(pbqp, node);
201 break;
202 }
203 }
204 }
205
merge_into_RN_node(pbqp_t * pbqp,plist_t * rpeo)206 static void merge_into_RN_node(pbqp_t *pbqp, plist_t *rpeo)
207 {
208 pbqp_node_t *node = NULL;
209
210 assert(pbqp);
211
212 do {
213 /* get last element from reverse perfect elimination order */
214 node = (pbqp_node_t*)plist_last(rpeo)->data;
215 /* remove element from reverse perfect elimination order */
216 plist_erase(rpeo, plist_last(rpeo));
217 /* insert node at the beginning of rpeo so the rpeo already exits after pbqp solving */
218 plist_insert_front(rpeo, node);
219 } while(node_is_reduced(node));
220
221 assert(pbqp_node_get_degree(node) > 2);
222
223 /* Check whether we can merge a neighbor into the current node. */
224 apply_RM(pbqp, node);
225 }
226
apply_RN_co_without_selection(pbqp_t * pbqp)227 static void apply_RN_co_without_selection(pbqp_t *pbqp)
228 {
229 pbqp_node_t *node;
230 unsigned edge_index;
231
232 assert(pbqp);
233
234 node = merged_node;
235 merged_node = NULL;
236
237 if (node_is_reduced(node))
238 return;
239
240 #if KAPS_DUMP
241 if (pbqp->dump_file) {
242 char txt[100];
243 sprintf(txt, "RN-Reduction of Node n%d", node->index);
244 pbqp_dump_section(pbqp->dump_file, 2, txt);
245 pbqp_dump_graph(pbqp);
246 }
247 #endif
248
249 /* Disconnect neighbor nodes */
250 for(edge_index = 0; edge_index < pbqp_node_get_degree(node); edge_index++) {
251 pbqp_edge_t *edge;
252 pbqp_node_t *neighbor;
253
254 /* get neighbor node */
255 edge = node->edges[edge_index];
256
257 neighbor = edge->src == node ? edge->tgt : edge->src;
258
259 assert(neighbor != node);
260
261 if(!is_connected(neighbor, edge))
262 continue;
263
264 disconnect_edge(neighbor, edge);
265 reorder_node_after_edge_deletion(neighbor);
266 }
267
268 /* Remove node from old bucket */
269 node_bucket_remove(&node_buckets[3], node);
270
271 /* Add node to back propagation list. */
272 node_bucket_insert(&reduced_bucket, node);
273 }
274
apply_heuristic_reductions_co(pbqp_t * pbqp,plist_t * rpeo)275 static void apply_heuristic_reductions_co(pbqp_t *pbqp, plist_t *rpeo)
276 {
277 #if KAPS_TIMING
278 /* create timers */
279 ir_timer_t *t_edge = ir_timer_new();
280 ir_timer_t *t_r1 = ir_timer_new();
281 ir_timer_t *t_r2 = ir_timer_new();
282 ir_timer_t *t_rn = ir_timer_new();
283 #endif
284
285 for (;;) {
286 if (edge_bucket_get_length(edge_bucket) > 0) {
287 #if KAPS_TIMING
288 ir_timer_start(t_edge);
289 #endif
290
291 apply_edge(pbqp);
292
293 #if KAPS_TIMING
294 ir_timer_stop(t_edge);
295 #endif
296 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
297 #if KAPS_TIMING
298 ir_timer_start(t_r1);
299 #endif
300
301 apply_RI(pbqp);
302
303 #if KAPS_TIMING
304 ir_timer_stop(t_r1);
305 #endif
306 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
307 #if KAPS_TIMING
308 ir_timer_start(t_r2);
309 #endif
310
311 apply_RII(pbqp);
312
313 #if KAPS_TIMING
314 ir_timer_stop(t_r2);
315 #endif
316 } else if (merged_node != NULL) {
317 #if KAPS_TIMING
318 ir_timer_start(t_rn);
319 #endif
320
321 apply_RN_co_without_selection(pbqp);
322
323 #if KAPS_TIMING
324 ir_timer_stop(t_rn);
325 #endif
326 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
327 #if KAPS_TIMING
328 ir_timer_start(t_rn);
329 #endif
330
331 merge_into_RN_node(pbqp, rpeo);
332
333 #if KAPS_TIMING
334 ir_timer_stop(t_rn);
335 #endif
336 } else {
337 #if KAPS_TIMING
338 printf("PBQP RE reductions: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_edge) / 1000.0);
339 printf("PBQP R1 reductions: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_r1) / 1000.0);
340 printf("PBQP R2 reductions: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_r2) / 1000.0);
341 printf("PBQP RN reductions: %10.3lf msec\n", (double)ir_timer_elapsed_usec(t_rn) / 1000.0);
342 #endif
343
344 return;
345 }
346 }
347 }
348
solve_pbqp_heuristical_co_ld(pbqp_t * pbqp,plist_t * rpeo)349 void solve_pbqp_heuristical_co_ld(pbqp_t *pbqp, plist_t *rpeo)
350 {
351 /* Reduce nodes degree ... */
352 initial_simplify_edges(pbqp);
353
354 /* ... and put node into bucket representing their degree. */
355 fill_node_buckets(pbqp);
356
357 #if KAPS_STATISTIC
358 FILE *fh = fopen("solutions.pb", "a");
359 fprintf(fh, "Solution");
360 fclose(fh);
361 #endif
362
363 apply_heuristic_reductions_co(pbqp, rpeo);
364
365 pbqp->solution = determine_solution(pbqp);
366
367 #if KAPS_STATISTIC
368 fh = fopen("solutions.pb", "a");
369 #if KAPS_USE_UNSIGNED
370 fprintf(fh, ": %u RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
371 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
372 pbqp->num_rm, pbqp->num_rn);
373 #else
374 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RM:%u RN/BF:%u\n", pbqp->solution,
375 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
376 pbqp->num_rm, pbqp->num_rn);
377 #endif
378 fclose(fh);
379 #endif
380
381 /* Solve reduced nodes. */
382 back_propagate_ld(pbqp);
383
384 free_buckets();
385 }
386