4 * Created on: 06.05.2010
10 #include "adt/array.h"
15 #include "heuristical_co_ld.h"
18 #include "html_dumper.h"
22 #include "pbqp_edge.h"
23 #include "pbqp_edge_t.h"
24 #include "pbqp_node.h"
25 #include "pbqp_node_t.h"
31 static void back_propagate_RI(pbqp *pbqp, pbqp_node *node)
42 edge = node->edges[0];
44 is_src = edge->src == node;
51 node->solution = pbqp_matrix_get_col_min_index(mat, other->solution, vec);
56 node->solution = pbqp_matrix_get_row_min_index(mat, other->solution, vec);
60 if (pbqp->dump_file) {
61 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
66 static void back_propagate_RII(pbqp *pbqp, pbqp_node *node)
68 pbqp_edge *src_edge = node->edges[0];
69 pbqp_edge *tgt_edge = node->edges[1];
70 int src_is_src = src_edge->src == node;
71 int tgt_is_src = tgt_edge->src == node;
84 src_node = src_edge->tgt;
86 src_node = src_edge->src;
90 tgt_node = tgt_edge->tgt;
92 tgt_node = tgt_edge->src;
95 /* Swap nodes if necessary. */
96 if (tgt_node->index < src_node->index) {
108 src_is_src = src_edge->src == node;
109 tgt_is_src = tgt_edge->src == node;
112 src_mat = src_edge->costs;
113 tgt_mat = tgt_edge->costs;
115 node_vec = node->costs;
117 row_index = src_node->solution;
118 col_index = tgt_node->solution;
120 vec = vector_copy(pbqp, node_vec);
123 vector_add_matrix_col(vec, src_mat, row_index);
125 vector_add_matrix_row(vec, src_mat, row_index);
129 vector_add_matrix_col(vec, tgt_mat, col_index);
131 vector_add_matrix_row(vec, tgt_mat, col_index);
134 node->solution = vector_get_min_index(vec);
137 if (pbqp->dump_file) {
138 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
142 obstack_free(&pbqp->obstack, vec);
145 static void back_propagate_RN(pbqp *pbqp, pbqp_node *node)
148 pbqp_node *neighbor = NULL;
149 pbqp_edge *edge = NULL;
154 vec = vector_copy(pbqp, node->costs);
156 for(idx = 0; idx < pbqp_node_get_degree(node); idx++) {
157 /* get neighbor node */
158 edge = node->edges[idx];
159 neighbor = edge->src == node ? edge->tgt : edge->src;
161 if(edge->src == node) /* node is edge src node */
162 vector_add_matrix_col(vec, edge->costs, neighbor->solution);
163 else /* node is edge tgt node */
164 vector_add_matrix_row(vec, edge->costs, neighbor->solution);
167 assert(vector_get_min(vec) != INF_COSTS);
168 node->solution = vector_get_min_index(vec);
171 if (pbqp->dump_file) {
172 fprintf(pbqp->dump_file, "node n%d is set to %d<br>\n", node->index, node->solution);
176 obstack_free(&pbqp->obstack, vec);
179 static void back_propagate_ld(pbqp *pbqp)
182 unsigned node_len = node_bucket_get_length(reduced_bucket);
187 if (pbqp->dump_file) {
188 dump_section(pbqp->dump_file, 2, "Back Propagation");
192 for (node_index = node_len; node_index > 0; --node_index) {
193 pbqp_node *node = reduced_bucket[node_index - 1];
195 switch (pbqp_node_get_degree(node)) {
197 back_propagate_RI(pbqp, node);
200 back_propagate_RII(pbqp, node);
203 back_propagate_RN(pbqp, node);
209 static void apply_RN_co_without_selection(pbqp *pbqp, plist_t *rpeo)
211 pbqp_node *node = NULL;
212 pbqp_node *neighbor = NULL;
213 pbqp_edge *edge = NULL;
219 /* get last element from reverse perfect elimination order */
220 node = plist_last(rpeo)->data;
221 /* remove element from reverse perfect elimination order */
222 plist_erase(rpeo, plist_last(rpeo));
223 /* insert node at the beginning of rpeo so the rpeo already exits after pbqp solving */
224 plist_insert_front(rpeo, node);
225 } while(node_is_reduced(node));
228 assert(pbqp_node_get_degree(node) > 2);
231 if (pbqp->dump_file) {
233 sprintf(txt, "RN-Reduction of Node n%d", node->index);
234 dump_section(pbqp->dump_file, 2, txt);
235 pbqp_dump_graph(pbqp);
239 /* Disconnect neighbor nodes */
240 for(idx = 0; idx < pbqp_node_get_degree(node); idx++) {
241 /* get neighbor node */
242 edge = node->edges[idx];
243 neighbor = edge->src == node ? edge->tgt : edge->src;
245 assert(neighbor != node);
247 if(!is_connected(neighbor, edge))
250 disconnect_edge(neighbor, edge);
251 reorder_node(neighbor);
254 /* Remove node from old bucket */
255 node_bucket_remove(&node_buckets[3], node);
257 /* Add node to back propagation list. */
258 node_bucket_insert(&reduced_bucket, node);
263 static void apply_heuristic_reductions_co(pbqp *pbqp, plist_t *rpeo)
267 ir_timer_t *t_edge = ir_timer_register("be_pbqp_edges", "pbqp reduce independent edges");
268 ir_timer_t *t_r0 = ir_timer_register("be_pbqp_r0", "pbqp R0 reductions");
269 ir_timer_t *t_r1 = ir_timer_register("be_pbqp_r1", "pbqp R1 reductions");
270 ir_timer_t *t_r2 = ir_timer_register("be_pbqp_r2", "pbqp R2 reductions");
271 ir_timer_t *t_rn = ir_timer_register("be_pbqp_rN", "pbqp RN reductions");
274 ir_timer_reset(t_edge);
275 ir_timer_reset(t_r0);
276 ir_timer_reset(t_r1);
277 ir_timer_reset(t_r2);
278 ir_timer_reset(t_rn);
282 if (edge_bucket_get_length(edge_bucket) > 0) {
284 ir_timer_start(t_r0);
292 } else if (node_bucket_get_length(node_buckets[1]) > 0) {
294 ir_timer_start(t_r1);
302 } else if (node_bucket_get_length(node_buckets[2]) > 0) {
304 ir_timer_start(t_r2);
312 } else if (node_bucket_get_length(node_buckets[3]) > 0) {
314 ir_timer_start(t_rn);
317 apply_RN_co_without_selection(pbqp, rpeo);
324 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_edge), (double)ir_timer_elapsed_usec(t_edge) / 1000.0);
325 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r0), (double)ir_timer_elapsed_usec(t_r0) / 1000.0);
326 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r1), (double)ir_timer_elapsed_usec(t_r1) / 1000.0);
327 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_r2), (double)ir_timer_elapsed_usec(t_r2) / 1000.0);
328 printf("%-20s: %8.3lf msec\n", ir_timer_get_description(t_rn), (double)ir_timer_elapsed_usec(t_rn) / 1000.0);
336 void solve_pbqp_heuristical_co_ld(pbqp *pbqp, plist_t *rpeo)
338 /* Reduce nodes degree ... */
339 initial_simplify_edges(pbqp);
341 /* ... and put node into bucket representing their degree. */
342 fill_node_buckets(pbqp);
345 FILE *fh = fopen("solutions.pb", "a");
346 fprintf(fh, "Solution");
350 apply_heuristic_reductions_co(pbqp, rpeo);
352 pbqp->solution = determine_solution(pbqp);
355 fh = fopen("solutions.pb", "a");
356 fprintf(fh, ": %lld RE:%u R0:%u R1:%u R2:%u RN/BF:%u\n", pbqp->solution,
357 pbqp->num_edges, pbqp->num_r0, pbqp->num_r1, pbqp->num_r2,
362 /* Solve reduced nodes. */
363 back_propagate_ld(pbqp);