1 //===---------------- PBQP.cpp --------- PBQP Solver ------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Developed by: Bernhard Scholz
11 // The University of Sydney
12 // http://www.it.usyd.edu.au/~scholz
13 //===----------------------------------------------------------------------===//
16 #include "llvm/Config/alloca.h"
23 /**************************************************************************
25 **************************************************************************/
27 /* edge of PBQP graph */
28 typedef struct adjnode {
29 struct adjnode *prev, /* doubly chained list */
31 *reverse; /* reverse edge */
32 int adj; /* adj. node */
33 PBQPMatrix *costs; /* cost matrix of edge */
35 bool tc_valid; /* flag whether following fields are valid */
36 int *tc_safe_regs; /* safe registers */
37 int tc_impact; /* impact */
41 typedef struct bucketnode {
42 struct bucketnode *prev; /* doubly chained list */
43 struct bucketnode *succ;
47 /* data structure of partitioned boolean quadratic problem */
49 int num_nodes; /* number of nodes */
50 int max_deg; /* maximal degree of a node */
51 bool solved; /* flag that indicates whether PBQP has been solved yet */
52 bool optimal; /* flag that indicates whether PBQP is optimal */
54 bool changed; /* flag whether graph has changed in simplification */
57 PBQPVector **node_costs; /* cost vectors of nodes */
58 int *node_deg; /* node degree of nodes */
59 int *solution; /* solution for node */
60 adjnode **adj_list; /* adj. list */
61 bucketnode **bucket_ptr; /* bucket pointer of a node */
64 int *stack; /* stack of nodes */
65 int stack_ptr; /* stack pointer */
68 bucketnode **bucket_list; /* bucket list */
70 int num_r0; /* counters for number statistics */
77 bool isInf(PBQPNum n) { return n == std::numeric_limits<PBQPNum>::infinity(); }
79 /*****************************************************************************
80 * allocation/de-allocation of pbqp problem
81 ****************************************************************************/
83 /* allocate new partitioned boolean quadratic program problem */
84 pbqp *alloc_pbqp(int num_nodes)
89 assert(num_nodes > 0);
91 /* allocate memory for pbqp data structure */
92 this_ = (pbqp *)malloc(sizeof(pbqp));
94 /* Initialize pbqp fields */
95 this_->num_nodes = num_nodes;
96 this_->solved = false;
97 this_->optimal = true;
100 this_->changed = false;
105 this_->num_rn_special = 0;
107 /* initialize/allocate stack fields of pbqp */
108 this_->stack = (int *) malloc(sizeof(int)*num_nodes);
109 this_->stack_ptr = 0;
111 /* initialize/allocate node fields of pbqp */
112 this_->adj_list = (adjnode **) malloc(sizeof(adjnode *)*num_nodes);
113 this_->node_deg = (int *) malloc(sizeof(int)*num_nodes);
114 this_->solution = (int *) malloc(sizeof(int)*num_nodes);
115 this_->bucket_ptr = (bucketnode **) malloc(sizeof(bucketnode **)*num_nodes);
116 this_->node_costs = (PBQPVector**) malloc(sizeof(PBQPVector*) * num_nodes);
117 for(u=0;u<num_nodes;u++) {
118 this_->solution[u]=-1;
119 this_->adj_list[u]=NULL;
120 this_->node_deg[u]=0;
121 this_->bucket_ptr[u]=NULL;
122 this_->node_costs[u]=NULL;
125 /* initialize bucket list */
126 this_->bucket_list = NULL;
131 /* free pbqp problem */
132 void free_pbqp(pbqp *this_)
136 adjnode *adj_ptr,*adj_next;
137 bucketnode *bucket,*bucket_next;
139 assert(this_ != NULL);
141 /* free node cost fields */
142 for(u=0;u < this_->num_nodes;u++) {
143 delete this_->node_costs[u];
145 free(this_->node_costs);
147 /* free bucket list */
148 for(deg=0;deg<=this_->max_deg;deg++) {
149 for(bucket=this_->bucket_list[deg];bucket!=NULL;bucket=bucket_next) {
150 this_->bucket_ptr[bucket->u] = NULL;
151 bucket_next = bucket-> succ;
155 free(this_->bucket_list);
158 assert(this_->adj_list != NULL);
159 for(u=0;u < this_->num_nodes; u++) {
160 for(adj_ptr = this_->adj_list[u]; adj_ptr != NULL; adj_ptr = adj_next) {
161 adj_next = adj_ptr -> succ;
162 if (u < adj_ptr->adj) {
163 assert(adj_ptr != NULL);
164 delete adj_ptr->costs;
166 if (adj_ptr -> tc_safe_regs != NULL) {
167 free(adj_ptr -> tc_safe_regs);
172 free(this_->adj_list);
174 /* free other node fields */
175 free(this_->node_deg);
176 free(this_->solution);
177 free(this_->bucket_ptr);
182 /* free pbqp data structure itself */
187 /****************************************************************************
189 ****************************************************************************/
191 /* find data structure of adj. node of a given node */
193 adjnode *find_adjnode(pbqp *this_,int u,int v)
197 assert (this_ != NULL);
198 assert (u >= 0 && u < this_->num_nodes);
199 assert (v >= 0 && v < this_->num_nodes);
200 assert(this_->adj_list != NULL);
202 for(adj_ptr = this_ -> adj_list[u];adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
203 if (adj_ptr->adj == v) {
210 /* allocate a new data structure for adj. node */
212 adjnode *alloc_adjnode(pbqp *this_,int u, PBQPMatrix *costs)
216 assert(this_ != NULL);
217 assert(costs != NULL);
218 assert(u >= 0 && u < this_->num_nodes);
220 p = (adjnode *)malloc(sizeof(adjnode));
227 p->tc_safe_regs = NULL;
233 /* insert adjacence node to adj. list */
235 void insert_adjnode(pbqp *this_, int u, adjnode *adj_ptr)
238 assert(this_ != NULL);
239 assert(adj_ptr != NULL);
240 assert(u >= 0 && u < this_->num_nodes);
242 /* if adjacency list of node is not empty -> update
243 first node of the list */
244 if (this_ -> adj_list[u] != NULL) {
245 assert(this_->adj_list[u]->prev == NULL);
246 this_->adj_list[u] -> prev = adj_ptr;
249 /* update doubly chained list pointers of pointers */
250 adj_ptr -> succ = this_->adj_list[u];
251 adj_ptr -> prev = NULL;
253 /* update adjacency list pointer of node u */
254 this_->adj_list[u] = adj_ptr;
257 /* remove entry in an adj. list */
259 void remove_adjnode(pbqp *this_, int u, adjnode *adj_ptr)
261 assert(this_!= NULL);
262 assert(u >= 0 && u <= this_->num_nodes);
263 assert(this_->adj_list != NULL);
264 assert(adj_ptr != NULL);
266 if (adj_ptr -> prev == NULL) {
267 this_->adj_list[u] = adj_ptr -> succ;
269 adj_ptr -> prev -> succ = adj_ptr -> succ;
272 if (adj_ptr -> succ != NULL) {
273 adj_ptr -> succ -> prev = adj_ptr -> prev;
276 if(adj_ptr->reverse != NULL) {
277 adjnode *rev = adj_ptr->reverse;
281 if (adj_ptr -> tc_safe_regs != NULL) {
282 free(adj_ptr -> tc_safe_regs);
288 /*****************************************************************************
290 ****************************************************************************/
292 /* get degree of a node */
294 int get_deg(pbqp *this_,int u)
299 assert(this_ != NULL);
300 assert(u >= 0 && u < this_->num_nodes);
301 assert(this_->adj_list != NULL);
303 for(adj_ptr = this_ -> adj_list[u];adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
311 void reinsert_node(pbqp *this_,int u)
316 assert(this_!= NULL);
317 assert(u >= 0 && u <= this_->num_nodes);
318 assert(this_->adj_list != NULL);
320 for(adj_u = this_ -> adj_list[u]; adj_u != NULL; adj_u = adj_u -> succ) {
321 int v = adj_u -> adj;
322 adj_v = alloc_adjnode(this_,u,adj_u->costs);
323 insert_adjnode(this_,v,adj_v);
329 void remove_node(pbqp *this_,int u)
333 assert(this_!= NULL);
334 assert(u >= 0 && u <= this_->num_nodes);
335 assert(this_->adj_list != NULL);
337 for(adj_ptr = this_ -> adj_list[u]; adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
338 remove_adjnode(this_,adj_ptr->adj,adj_ptr -> reverse);
342 /*****************************************************************************
344 ****************************************************************************/
346 /* insert edge to graph */
347 /* (does not check whether edge exists in graph */
349 void insert_edge(pbqp *this_, int u, int v, PBQPMatrix *costs)
354 /* create adjanceny entry for u */
355 adj_u = alloc_adjnode(this_,v,costs);
356 insert_adjnode(this_,u,adj_u);
359 /* create adjanceny entry for v */
360 adj_v = alloc_adjnode(this_,u,costs);
361 insert_adjnode(this_,v,adj_v);
363 /* create link for reverse edge */
364 adj_u -> reverse = adj_v;
365 adj_v -> reverse = adj_u;
370 void delete_edge(pbqp *this_,int u,int v)
375 assert(this_ != NULL);
376 assert( u >= 0 && u < this_->num_nodes);
377 assert( v >= 0 && v < this_->num_nodes);
379 adj_ptr=find_adjnode(this_,u,v);
380 assert(adj_ptr != NULL);
381 assert(adj_ptr->reverse != NULL);
383 delete adj_ptr -> costs;
385 rev = adj_ptr->reverse;
386 remove_adjnode(this_,u,adj_ptr);
387 remove_adjnode(this_,v,rev);
390 /*****************************************************************************
392 ****************************************************************************/
394 /* Note: Since cost(u,v) = transpose(cost(v,u)), it would be necessary to store
395 two matrices for both edges (u,v) and (v,u). However, we only store the
396 matrix for the case u < v. For the other case we transpose the stored matrix
400 /* add costs to cost vector of a node */
401 void add_pbqp_nodecosts(pbqp *this_,int u, PBQPVector *costs)
403 assert(this_ != NULL);
404 assert(costs != NULL);
405 assert(u >= 0 && u <= this_->num_nodes);
407 if (!this_->node_costs[u]) {
408 this_->node_costs[u] = new PBQPVector(*costs);
410 *this_->node_costs[u] += *costs;
414 /* get cost matrix ptr */
416 PBQPMatrix *get_costmatrix_ptr(pbqp *this_, int u, int v)
419 PBQPMatrix *m = NULL;
421 assert (this_ != NULL);
422 assert (u >= 0 && u < this_->num_nodes);
423 assert (v >= 0 && v < this_->num_nodes);
425 adj_ptr = find_adjnode(this_,u,v);
427 if (adj_ptr != NULL) {
428 m = adj_ptr -> costs;
434 /* get cost matrix ptr */
435 /* Note: only the pointer is returned for
439 PBQPMatrix *pbqp_get_costmatrix(pbqp *this_, int u, int v)
441 adjnode *adj_ptr = find_adjnode(this_,u,v);
443 if (adj_ptr != NULL) {
445 return new PBQPMatrix(*adj_ptr->costs);
447 return new PBQPMatrix(adj_ptr->costs->transpose());
454 /* add costs to cost matrix of an edge */
455 void add_pbqp_edgecosts(pbqp *this_,int u,int v, PBQPMatrix *costs)
457 PBQPMatrix *adj_costs;
459 assert(this_!= NULL);
460 assert(costs != NULL);
461 assert(u >= 0 && u <= this_->num_nodes);
462 assert(v >= 0 && v <= this_->num_nodes);
464 /* does the edge u-v exists ? */
466 PBQPVector *diag = new PBQPVector(costs->diagonalize());
467 add_pbqp_nodecosts(this_,v,diag);
469 } else if ((adj_costs = get_costmatrix_ptr(this_,u,v))!=NULL) {
471 *adj_costs += *costs;
473 *adj_costs += costs->transpose();
476 adj_costs = new PBQPMatrix((u < v) ? *costs : costs->transpose());
477 insert_edge(this_,u,v,adj_costs);
481 /* remove bucket from bucket list */
483 void pbqp_remove_bucket(pbqp *this_, bucketnode *bucket)
487 assert(this_ != NULL);
488 assert(u >= 0 && u < this_->num_nodes);
489 assert(this_->bucket_list != NULL);
490 assert(this_->bucket_ptr[u] != NULL);
492 /* update predecessor node in bucket list
493 (if no preceeding bucket exists, then
494 the bucket_list pointer needs to be
497 if (bucket->prev != NULL) {
498 bucket->prev-> succ = bucket->succ;
500 this_->bucket_list[this_->node_deg[u]] = bucket -> succ;
503 /* update successor node in bucket list */
504 if (bucket->succ != NULL) {
505 bucket->succ-> prev = bucket->prev;
509 /**********************************************************************************
511 **********************************************************************************/
513 /* pop node of given degree */
515 int pop_node(pbqp *this_,int deg)
520 assert(this_ != NULL);
521 assert(deg >= 0 && deg <= this_->max_deg);
522 assert(this_->bucket_list != NULL);
524 /* get first bucket of bucket list */
525 bucket = this_->bucket_list[deg];
526 assert(bucket != NULL);
529 pbqp_remove_bucket(this_,bucket);
535 /**********************************************************************************
537 **********************************************************************************/
539 /* add bucket to bucketlist */
541 void add_to_bucketlist(pbqp *this_,bucketnode *bucket, int deg)
543 bucketnode *old_head;
545 assert(bucket != NULL);
546 assert(this_ != NULL);
547 assert(deg >= 0 && deg <= this_->max_deg);
548 assert(this_->bucket_list != NULL);
550 /* store node degree (for re-ordering purposes)*/
551 this_->node_deg[bucket->u] = deg;
553 /* put bucket to front of doubly chained list */
554 old_head = this_->bucket_list[deg];
555 bucket -> prev = NULL;
556 bucket -> succ = old_head;
557 this_ -> bucket_list[deg] = bucket;
558 if (bucket -> succ != NULL ) {
559 assert ( old_head -> prev == NULL);
560 old_head -> prev = bucket;
565 /* reorder node in bucket list according to
566 current node degree */
568 void reorder_node(pbqp *this_, int u)
572 assert(this_ != NULL);
573 assert(u>= 0 && u < this_->num_nodes);
574 assert(this_->bucket_list != NULL);
575 assert(this_->bucket_ptr[u] != NULL);
577 /* get current node degree */
578 deg = get_deg(this_,u);
580 /* remove bucket from old bucket list only
581 if degree of node has changed. */
582 if (deg != this_->node_deg[u]) {
583 pbqp_remove_bucket(this_,this_->bucket_ptr[u]);
584 add_to_bucketlist(this_,this_->bucket_ptr[u],deg);
588 /* reorder adj. nodes of a node */
590 void reorder_adjnodes(pbqp *this_,int u)
594 assert(this_!= NULL);
595 assert(u >= 0 && u <= this_->num_nodes);
596 assert(this_->adj_list != NULL);
598 for(adj_ptr = this_ -> adj_list[u]; adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
599 reorder_node(this_,adj_ptr->adj);
603 /**********************************************************************************
605 **********************************************************************************/
607 /* create new bucket entry */
608 /* consistency of the bucket list is not checked! */
610 void create_bucket(pbqp *this_,int u,int deg)
614 assert(this_ != NULL);
615 assert(u >= 0 && u < this_->num_nodes);
616 assert(this_->bucket_list != NULL);
618 bucket = (bucketnode *)malloc(sizeof(bucketnode));
619 assert(bucket != NULL);
622 this_->bucket_ptr[u] = bucket;
624 add_to_bucketlist(this_,bucket,deg);
627 /* create bucket list */
629 void create_bucketlist(pbqp *this_)
635 assert(this_ != NULL);
636 assert(this_->bucket_list == NULL);
638 /* determine max. degree of the nodes */
639 max_deg = 2; /* at least of degree two! */
640 for(u=0;u<this_->num_nodes;u++) {
641 deg = this_->node_deg[u] = get_deg(this_,u);
646 this_->max_deg = max_deg;
648 /* allocate bucket list */
649 this_ -> bucket_list = (bucketnode **)malloc(sizeof(bucketnode *)*(max_deg + 1));
650 memset(this_->bucket_list,0,sizeof(bucketnode *)*(max_deg + 1));
651 assert(this_->bucket_list != NULL);
653 /* insert nodes to the list */
654 for(u=0;u<this_->num_nodes;u++) {
655 create_bucket(this_,u,this_->node_deg[u]);
659 /*****************************************************************************
660 * PBQP simplification for trivial nodes
661 ****************************************************************************/
663 /* remove trivial node with cost vector length of one */
665 void disconnect_trivialnode(pbqp *this_,int u)
673 assert(this_ != NULL);
674 assert(this_->node_costs != NULL);
675 assert(u >= 0 && u < this_ -> num_nodes);
676 assert(this_->node_costs[u]->getLength() == 1);
678 /* add edge costs to node costs of adj. nodes */
679 for(adj_ptr = this_->adj_list[u]; adj_ptr != NULL; adj_ptr = next){
680 next = adj_ptr -> succ;
682 assert(v >= 0 && v < this_ -> num_nodes);
684 /* convert matrix to cost vector offset for adj. node */
685 c_uv = pbqp_get_costmatrix(this_,u,v);
686 c_v = new PBQPVector(c_uv->getRowAsVector(0));
687 *this_->node_costs[v] += *c_v;
689 /* delete edge & free vec/mat */
692 delete_edge(this_,u,v);
696 /* find all trivial nodes and disconnect them */
698 void eliminate_trivial_nodes(pbqp *this_)
702 assert(this_ != NULL);
703 assert(this_ -> node_costs != NULL);
705 for(u=0;u < this_ -> num_nodes; u++) {
706 if (this_->node_costs[u]->getLength() == 1) {
707 disconnect_trivialnode(this_,u);
712 /*****************************************************************************
713 * Normal form for PBQP
714 ****************************************************************************/
716 /* simplify a cost matrix. If the matrix
717 is independent, then simplify_matrix
718 returns true - otherwise false. In
719 vectors u and v the offset values of
720 the decomposition are stored.
724 bool normalize_matrix(PBQPMatrix *m, PBQPVector *u, PBQPVector *v)
729 assert( u->getLength() > 0);
730 assert( v->getLength() > 0);
732 assert(m->getRows() == u->getLength());
733 assert(m->getCols() == v->getLength());
735 /* determine u vector */
736 for(unsigned r = 0; r < m->getRows(); ++r) {
737 PBQPNum min = m->getRowMin(r);
740 m->subFromRow(r, min);
746 /* determine v vector */
747 for(unsigned c = 0; c < m->getCols(); ++c) {
748 PBQPNum min = m->getColMin(c);
751 m->subFromCol(c, min);
757 /* determine whether matrix is
763 /* simplify single edge */
765 void simplify_edge(pbqp *this_,int u,int v)
770 assert (this_ != NULL);
771 assert (u >= 0 && u <this_->num_nodes);
772 assert (v >= 0 && v <this_->num_nodes);
775 /* swap u and v if u > v in order to avoid un-necessary
776 tranpositions of the cost matrix */
784 /* get cost matrix and simplify it */
785 costs = get_costmatrix_ptr(this_,u,v);
786 is_zero=normalize_matrix(costs,this_->node_costs[u],this_->node_costs[v]);
790 delete_edge(this_,u,v);
791 this_->changed = true;
795 /* normalize cost matrices and remove
796 edges in PBQP if they ary independent,
797 i.e. can be decomposed into two
801 void eliminate_independent_edges(pbqp *this_)
804 adjnode *adj_ptr,*next;
806 assert(this_ != NULL);
807 assert(this_ -> adj_list != NULL);
809 this_->changed = false;
810 for(u=0;u < this_->num_nodes;u++) {
811 for (adj_ptr = this_ -> adj_list[u]; adj_ptr != NULL; adj_ptr = next) {
812 next = adj_ptr -> succ;
814 assert(v >= 0 && v < this_->num_nodes);
816 simplify_edge(this_,u,v);
823 /*****************************************************************************
824 * PBQP reduction rules
825 ****************************************************************************/
828 This reduction rule is applied for nodes
832 void apply_RI(pbqp *this_,int x)
838 PBQPVector *c_x, *delta;
840 assert(this_ != NULL);
841 assert(x >= 0 && x < this_->num_nodes);
842 assert(this_ -> adj_list[x] != NULL);
843 assert(this_ -> adj_list[x] -> succ == NULL);
845 /* get adjacence matrix */
846 y = this_ -> adj_list[x] -> adj;
847 assert(y >= 0 && y < this_->num_nodes);
849 /* determine length of cost vectors for node x and y */
850 xlen = this_ -> node_costs[x]->getLength();
851 ylen = this_ -> node_costs[y]->getLength();
853 /* get cost vector c_x and matrix c_yx */
854 c_x = this_ -> node_costs[x];
855 c_yx = pbqp_get_costmatrix(this_,y,x);
856 assert (c_yx != NULL);
859 /* allocate delta vector */
860 delta = new PBQPVector(ylen);
862 /* compute delta vector */
863 for(unsigned i = 0; i < ylen; ++i) {
864 PBQPNum min = (*c_yx)[i][0] + (*c_x)[0];
865 for(unsigned j = 1; j < xlen; ++j) {
866 PBQPNum c = (*c_yx)[i][j] + (*c_x)[j];
873 /* add delta vector */
874 *this_ -> node_costs[y] += *delta;
877 remove_node(this_,x);
879 /* reorder adj. nodes of node x */
880 reorder_adjnodes(this_,x);
882 /* push node x on stack */
883 assert(this_ -> stack_ptr < this_ -> num_nodes);
884 this_->stack[this_ -> stack_ptr++] = x;
890 /* increment counter for number statistic */
895 This reduction rule is applied for nodes
899 void apply_RII(pbqp *this_,int x)
902 unsigned xlen,ylen,zlen;
905 PBQPMatrix *c_yx, *c_zx;
909 assert(this_ != NULL);
910 assert(x >= 0 && x < this_->num_nodes);
911 assert(this_ -> adj_list[x] != NULL);
912 assert(this_ -> adj_list[x] -> succ != NULL);
913 assert(this_ -> adj_list[x] -> succ -> succ == NULL);
915 /* get adjacence matrix */
916 y = this_ -> adj_list[x] -> adj;
917 z = this_ -> adj_list[x] -> succ -> adj;
918 assert(y >= 0 && y < this_->num_nodes);
919 assert(z >= 0 && z < this_->num_nodes);
921 /* determine length of cost vectors for node x and y */
922 xlen = this_ -> node_costs[x]->getLength();
923 ylen = this_ -> node_costs[y]->getLength();
924 zlen = this_ -> node_costs[z]->getLength();
926 /* get cost vector c_x and matrix c_yx */
927 cx = this_ -> node_costs[x];
928 c_yx = pbqp_get_costmatrix(this_,y,x);
929 c_zx = pbqp_get_costmatrix(this_,z,x);
930 assert(c_yx != NULL);
931 assert(c_zx != NULL);
933 /* Colour Heuristic */
934 if ( (adj_yz = find_adjnode(this_,y,z)) != NULL) {
935 adj_yz->tc_valid = false;
936 adj_yz->reverse->tc_valid = false;
939 /* allocate delta matrix */
940 delta = new PBQPMatrix(ylen, zlen);
942 /* compute delta matrix */
943 for(unsigned i=0;i<ylen;i++) {
944 for(unsigned j=0;j<zlen;j++) {
945 PBQPNum min = (*c_yx)[i][0] + (*c_zx)[j][0] + (*cx)[0];
946 for(unsigned k=1;k<xlen;k++) {
947 PBQPNum c = (*c_yx)[i][k] + (*c_zx)[j][k] + (*cx)[k];
952 (*delta)[i][j] = min;
956 /* add delta matrix */
957 add_pbqp_edgecosts(this_,y,z,delta);
960 remove_node(this_,x);
962 /* simplify cost matrix c_yz */
963 simplify_edge(this_,y,z);
965 /* reorder adj. nodes */
966 reorder_adjnodes(this_,x);
968 /* push node x on stack */
969 assert(this_ -> stack_ptr < this_ -> num_nodes);
970 this_->stack[this_ -> stack_ptr++] = x;
977 /* increment counter for number statistic */
984 void apply_RN(pbqp *this_,int x)
988 assert(this_ != NULL);
989 assert(x >= 0 && x < this_->num_nodes);
990 assert(this_ -> node_costs[x] != NULL);
992 xlen = this_ -> node_costs[x] -> getLength();
994 /* after application of RN rule no optimality
995 can be guaranteed! */
996 this_ -> optimal = false;
998 /* push node x on stack */
999 assert(this_ -> stack_ptr < this_ -> num_nodes);
1000 this_->stack[this_ -> stack_ptr++] = x;
1003 remove_node(this_,x);
1005 /* reorder adj. nodes of node x */
1006 reorder_adjnodes(this_,x);
1008 /* increment counter for number statistic */
1014 void compute_tc_info(pbqp *this_, adjnode *p)
1019 PBQPVector *c_x, *c_y;
1020 int *row_inf_counts;
1022 assert(p->reverse != NULL);
1033 /* get cost vectors */
1034 c_x = this_ -> node_costs[x];
1035 c_y = this_ -> node_costs[y];
1037 /* get cost matrix */
1038 m = pbqp_get_costmatrix(this_, x, y);
1041 /* allocate allowed set for edge (x,y) and (y,x) */
1042 if (p->tc_safe_regs == NULL) {
1043 p->tc_safe_regs = (int *) malloc(sizeof(int) * c_x->getLength());
1046 if (r->tc_safe_regs == NULL ) {
1047 r->tc_safe_regs = (int *) malloc(sizeof(int) * c_y->getLength());
1050 p->tc_impact = r->tc_impact = 0;
1052 row_inf_counts = (int *) alloca(sizeof(int) * c_x->getLength());
1055 p->tc_safe_regs[0] = 0;
1056 row_inf_counts[0] = 0;
1057 for(unsigned i = 1; i < c_x->getLength(); ++i){
1058 p->tc_safe_regs[i] = 1;
1059 row_inf_counts[i] = 0;
1062 r->tc_safe_regs[0] = 0;
1063 for(unsigned j = 1; j < c_y->getLength(); ++j){
1064 r->tc_safe_regs[j] = 1;
1067 for(unsigned j = 0; j < c_y->getLength(); ++j) {
1068 int col_inf_counts = 0;
1069 for (unsigned i = 0; i < c_x->getLength(); ++i) {
1070 if (isInf((*m)[i][j])) {
1072 ++row_inf_counts[i];
1074 p->tc_safe_regs[i] = 0;
1075 r->tc_safe_regs[j] = 0;
1078 if (col_inf_counts > p->tc_impact) {
1079 p->tc_impact = col_inf_counts;
1083 for(unsigned i = 0; i < c_x->getLength(); ++i){
1084 if (row_inf_counts[i] > r->tc_impact)
1086 r->tc_impact = row_inf_counts[i];
1094 * Checks whether node x can be locally coloured.
1097 int is_colorable(pbqp *this_,int x)
1103 int num_allowed = 0;
1104 unsigned total_impact = 0;
1106 assert(this_ != NULL);
1107 assert(x >= 0 && x < this_->num_nodes);
1108 assert(this_ -> node_costs[x] != NULL);
1110 c_x = this_ -> node_costs[x];
1112 /* allocate allowed set */
1113 allowed = (int *)malloc(sizeof(int) * c_x->getLength());
1114 for(unsigned i = 0; i < c_x->getLength(); ++i){
1115 if (!isInf((*c_x)[i]) && i > 0) {
1123 /* determine local minimum */
1124 for(adj_ptr=this_->adj_list[x] ;adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
1125 if (!adj_ptr -> tc_valid) {
1126 compute_tc_info(this_, adj_ptr);
1129 total_impact += adj_ptr->tc_impact;
1131 if (num_allowed > 0) {
1132 for (unsigned i = 1; i < c_x->getLength(); ++i){
1134 if (!adj_ptr->tc_safe_regs[i]){
1137 if (num_allowed == 0)
1144 if ( total_impact >= c_x->getLength() - 1 && num_allowed == 0 ) {
1154 /* use briggs heuristic
1155 note: this_ is not a general heuristic. it only is useful for
1156 interference graphs.
1158 int pop_colorablenode(pbqp *this_)
1161 bucketnode *min_bucket=NULL;
1162 PBQPNum min = std::numeric_limits<PBQPNum>::infinity();
1164 /* select node where the number of colors is less than the node degree */
1165 for(deg=this_->max_deg;deg > 2;deg--) {
1167 for(bucket=this_->bucket_list[deg];bucket!= NULL;bucket = bucket -> succ) {
1169 if (is_colorable(this_,u)) {
1170 pbqp_remove_bucket(this_,bucket);
1171 this_->num_rn_special++;
1178 /* select node with minimal ratio between average node costs and degree of node */
1179 for(deg=this_->max_deg;deg >2; deg--) {
1181 for(bucket=this_->bucket_list[deg];bucket!= NULL;bucket = bucket -> succ) {
1186 assert(u>=0 && u < this_->num_nodes);
1187 h = (*this_->node_costs[u])[0] / (PBQPNum) deg;
1189 min_bucket = bucket;
1195 /* return node and free bucket */
1196 if (min_bucket != NULL) {
1199 pbqp_remove_bucket(this_,min_bucket);
1209 /*****************************************************************************
1210 * PBQP graph parsing
1211 ****************************************************************************/
1213 /* reduce pbqp problem (first phase) */
1215 void reduce_pbqp(pbqp *this_)
1219 assert(this_ != NULL);
1220 assert(this_->bucket_list != NULL);
1224 if (this_->bucket_list[1] != NULL) {
1225 u = pop_node(this_,1);
1227 } else if (this_->bucket_list[2] != NULL) {
1228 u = pop_node(this_,2);
1230 } else if ((u = pop_colorablenode(this_)) != -1) {
1238 /*****************************************************************************
1239 * PBQP back propagation
1240 ****************************************************************************/
1242 /* determine solution of a reduced node. Either
1243 RI or RII was applied for this_ node. */
1245 void determine_solution(pbqp *this_,int x)
1247 PBQPVector *v = new PBQPVector(*this_ -> node_costs[x]);
1250 assert(this_ != NULL);
1251 assert(x >= 0 && x < this_->num_nodes);
1252 assert(this_ -> adj_list != NULL);
1253 assert(this_ -> solution != NULL);
1255 for(adj_ptr=this_->adj_list[x] ;adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
1256 int y = adj_ptr -> adj;
1257 int y_sol = this_ -> solution[y];
1259 PBQPMatrix *c_yx = pbqp_get_costmatrix(this_,y,x);
1260 assert(y_sol >= 0 && y_sol < (int)this_->node_costs[y]->getLength());
1261 (*v) += c_yx->getRowAsVector(y_sol);
1264 this_ -> solution[x] = v->minIndex();
1269 /* back popagation phase of PBQP */
1271 void back_propagate(pbqp *this_)
1275 assert(this_ != NULL);
1276 assert(this_->stack != NULL);
1277 assert(this_->stack_ptr < this_->num_nodes);
1279 for(i=this_ -> stack_ptr-1;i>=0;i--) {
1280 int x = this_ -> stack[i];
1281 assert( x >= 0 && x < this_ -> num_nodes);
1282 reinsert_node(this_,x);
1283 determine_solution(this_,x);
1287 /* solve trivial nodes of degree zero */
1289 void determine_trivialsolution(pbqp *this_)
1294 assert( this_ != NULL);
1295 assert( this_ -> bucket_list != NULL);
1297 /* determine trivial solution */
1298 while (this_->bucket_list[0] != NULL) {
1299 u = pop_node(this_,0);
1301 assert( u >= 0 && u < this_ -> num_nodes);
1303 this_->solution[u] = this_->node_costs[u]->minIndex();
1304 delta = (*this_->node_costs[u])[this_->solution[u]];
1305 this_->min = this_->min + delta;
1307 /* increment counter for number statistic */
1312 /*****************************************************************************
1314 ****************************************************************************/
1316 void check_pbqp(pbqp *this_)
1322 assert( this_ != NULL);
1324 for(u=0;u< this_->num_nodes; u++) {
1325 assert (this_ -> node_costs[u] != NULL);
1326 for(adj_ptr = this_ -> adj_list[u];adj_ptr != NULL; adj_ptr = adj_ptr -> succ) {
1328 assert( v>= 0 && v < this_->num_nodes);
1330 costs = adj_ptr -> costs;
1331 assert( costs->getRows() == this_->node_costs[u]->getLength() &&
1332 costs->getCols() == this_->node_costs[v]->getLength());
1338 /*****************************************************************************
1339 * PBQP solve routines
1340 ****************************************************************************/
1342 /* solve PBQP problem */
1343 void solve_pbqp(pbqp *this_)
1345 assert(this_ != NULL);
1346 assert(!this_->solved);
1348 /* check vector & matrix dimensions */
1351 /* simplify PBQP problem */
1353 /* eliminate trivial nodes, i.e.
1354 nodes with cost vectors of length one. */
1355 eliminate_trivial_nodes(this_);
1357 /* eliminate edges with independent
1358 cost matrices and normalize matrices */
1359 eliminate_independent_edges(this_);
1361 /* create bucket list for graph parsing */
1362 create_bucketlist(this_);
1367 /* solve trivial nodes */
1368 determine_trivialsolution(this_);
1370 /* back propagation phase */
1371 back_propagate(this_);
1373 this_->solved = true;
1376 /* get solution of a node */
1377 int get_pbqp_solution(pbqp *this_,int x)
1379 assert(this_ != NULL);
1380 assert(this_->solution != NULL);
1381 assert(this_ -> solved);
1383 return this_->solution[x];
1386 /* is solution optimal? */
1387 bool is_pbqp_optimal(pbqp *this_)
1389 assert(this_ -> solved);
1390 return this_->optimal;