LLVM API Documentation
00001 //===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ --*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // Heuristic PBQP solver. This solver is able to perform optimal reductions for 00011 // nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is 00012 // used to to select a node for reduction. 00013 // 00014 //===----------------------------------------------------------------------===// 00015 00016 #ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H 00017 #define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H 00018 00019 #include "Solver.h" 00020 #include "AnnotatedGraph.h" 00021 #include "llvm/Support/raw_ostream.h" 00022 #include <limits> 00023 00024 namespace PBQP { 00025 00026 /// \brief Important types for the HeuristicSolverImpl. 00027 /// 00028 /// Declared seperately to allow access to heuristic classes before the solver 00029 /// is fully constructed. 00030 template <typename HeuristicNodeData, typename HeuristicEdgeData> 00031 class HSITypes { 00032 public: 00033 00034 class NodeData; 00035 class EdgeData; 00036 00037 typedef AnnotatedGraph<NodeData, EdgeData> SolverGraph; 00038 typedef typename SolverGraph::NodeIterator GraphNodeIterator; 00039 typedef typename SolverGraph::EdgeIterator GraphEdgeIterator; 00040 typedef typename SolverGraph::AdjEdgeIterator GraphAdjEdgeIterator; 00041 00042 typedef std::list<GraphNodeIterator> NodeList; 00043 typedef typename NodeList::iterator NodeListIterator; 00044 00045 typedef std::vector<GraphNodeIterator> NodeStack; 00046 typedef typename NodeStack::iterator NodeStackIterator; 00047 00048 class NodeData { 00049 friend class EdgeData; 00050 00051 private: 00052 00053 typedef std::list<GraphEdgeIterator> LinksList; 00054 00055 unsigned numLinks; 00056 LinksList links, solvedLinks; 00057 NodeListIterator bucketItr; 00058 HeuristicNodeData heuristicData; 00059 00060 public: 00061 00062 typedef typename LinksList::iterator AdjLinkIterator; 00063 00064 private: 00065 00066 AdjLinkIterator addLink(const GraphEdgeIterator &edgeItr) { 00067 ++numLinks; 00068 return links.insert(links.end(), edgeItr); 00069 } 00070 00071 void delLink(const AdjLinkIterator &adjLinkItr) { 00072 --numLinks; 00073 links.erase(adjLinkItr); 00074 } 00075 00076 public: 00077 00078 NodeData() : numLinks(0) {} 00079 00080 unsigned getLinkDegree() const { return numLinks; } 00081 00082 HeuristicNodeData& getHeuristicData() { return heuristicData; } 00083 const HeuristicNodeData& getHeuristicData() const { 00084 return heuristicData; 00085 } 00086 00087 void setBucketItr(const NodeListIterator &bucketItr) { 00088 this->bucketItr = bucketItr; 00089 } 00090 00091 const NodeListIterator& getBucketItr() const { 00092 return bucketItr; 00093 } 00094 00095 AdjLinkIterator adjLinksBegin() { 00096 return links.begin(); 00097 } 00098 00099 AdjLinkIterator adjLinksEnd() { 00100 return links.end(); 00101 } 00102 00103 void addSolvedLink(const GraphEdgeIterator &solvedLinkItr) { 00104 solvedLinks.push_back(solvedLinkItr); 00105 } 00106 00107 AdjLinkIterator solvedLinksBegin() { 00108 return solvedLinks.begin(); 00109 } 00110 00111 AdjLinkIterator solvedLinksEnd() { 00112 return solvedLinks.end(); 00113 } 00114 00115 }; 00116 00117 class EdgeData { 00118 private: 00119 00120 SolverGraph &g; 00121 GraphNodeIterator node1Itr, node2Itr; 00122 HeuristicEdgeData heuristicData; 00123 typename NodeData::AdjLinkIterator node1ThisEdgeItr, node2ThisEdgeItr; 00124 00125 public: 00126 00127 EdgeData(SolverGraph &g) : g(g) {} 00128 00129 HeuristicEdgeData& getHeuristicData() { return heuristicData; } 00130 const HeuristicEdgeData& getHeuristicData() const { 00131 return heuristicData; 00132 } 00133 00134 void setup(const GraphEdgeIterator &thisEdgeItr) { 00135 node1Itr = g.getEdgeNode1Itr(thisEdgeItr); 00136 node2Itr = g.getEdgeNode2Itr(thisEdgeItr); 00137 00138 node1ThisEdgeItr = g.getNodeData(node1Itr).addLink(thisEdgeItr); 00139 node2ThisEdgeItr = g.getNodeData(node2Itr).addLink(thisEdgeItr); 00140 } 00141 00142 void unlink() { 00143 g.getNodeData(node1Itr).delLink(node1ThisEdgeItr); 00144 g.getNodeData(node2Itr).delLink(node2ThisEdgeItr); 00145 } 00146 00147 }; 00148 00149 }; 00150 00151 template <typename Heuristic> 00152 class HeuristicSolverImpl { 00153 public: 00154 // Typedefs to make life easier: 00155 typedef HSITypes<typename Heuristic::NodeData, 00156 typename Heuristic::EdgeData> HSIT; 00157 typedef typename HSIT::SolverGraph SolverGraph; 00158 typedef typename HSIT::NodeData NodeData; 00159 typedef typename HSIT::EdgeData EdgeData; 00160 typedef typename HSIT::GraphNodeIterator GraphNodeIterator; 00161 typedef typename HSIT::GraphEdgeIterator GraphEdgeIterator; 00162 typedef typename HSIT::GraphAdjEdgeIterator GraphAdjEdgeIterator; 00163 00164 typedef typename HSIT::NodeList NodeList; 00165 typedef typename HSIT::NodeListIterator NodeListIterator; 00166 00167 typedef std::vector<GraphNodeIterator> NodeStack; 00168 typedef typename NodeStack::iterator NodeStackIterator; 00169 00170 /// \brief Constructor, which performs all the actual solver work. 00171 HeuristicSolverImpl(const SimpleGraph &orig) : 00172 solution(orig.getNumNodes(), true) 00173 { 00174 copyGraph(orig); 00175 simplify(); 00176 setup(); 00177 computeSolution(); 00178 computeSolutionCost(orig); 00179 } 00180 00181 /// \brief Returns the graph for this solver. 00182 SolverGraph& getGraph() { return g; } 00183 00184 /// \brief Return the solution found by this solver. 00185 const Solution& getSolution() const { return solution; } 00186 00187 private: 00188 00189 /// \brief Add the given node to the appropriate bucket for its link 00190 /// degree. 00191 void addToBucket(const GraphNodeIterator &nodeItr) { 00192 NodeData &nodeData = g.getNodeData(nodeItr); 00193 00194 switch (nodeData.getLinkDegree()) { 00195 case 0: nodeData.setBucketItr( 00196 r0Bucket.insert(r0Bucket.end(), nodeItr)); 00197 break; 00198 case 1: nodeData.setBucketItr( 00199 r1Bucket.insert(r1Bucket.end(), nodeItr)); 00200 break; 00201 case 2: nodeData.setBucketItr( 00202 r2Bucket.insert(r2Bucket.end(), nodeItr)); 00203 break; 00204 default: heuristic.addToRNBucket(nodeItr); 00205 break; 00206 } 00207 } 00208 00209 /// \brief Remove the given node from the appropriate bucket for its link 00210 /// degree. 00211 void removeFromBucket(const GraphNodeIterator &nodeItr) { 00212 NodeData &nodeData = g.getNodeData(nodeItr); 00213 00214 switch (nodeData.getLinkDegree()) { 00215 case 0: r0Bucket.erase(nodeData.getBucketItr()); break; 00216 case 1: r1Bucket.erase(nodeData.getBucketItr()); break; 00217 case 2: r2Bucket.erase(nodeData.getBucketItr()); break; 00218 default: heuristic.removeFromRNBucket(nodeItr); break; 00219 } 00220 } 00221 00222 public: 00223 00224 /// \brief Add a link. 00225 void addLink(const GraphEdgeIterator &edgeItr) { 00226 g.getEdgeData(edgeItr).setup(edgeItr); 00227 00228 if ((g.getNodeData(g.getEdgeNode1Itr(edgeItr)).getLinkDegree() > 2) || 00229 (g.getNodeData(g.getEdgeNode2Itr(edgeItr)).getLinkDegree() > 2)) { 00230 heuristic.handleAddLink(edgeItr); 00231 } 00232 } 00233 00234 /// \brief Remove link, update info for node. 00235 /// 00236 /// Only updates information for the given node, since usually the other 00237 /// is about to be removed. 00238 void removeLink(const GraphEdgeIterator &edgeItr, 00239 const GraphNodeIterator &nodeItr) { 00240 00241 if (g.getNodeData(nodeItr).getLinkDegree() > 2) { 00242 heuristic.handleRemoveLink(edgeItr, nodeItr); 00243 } 00244 g.getEdgeData(edgeItr).unlink(); 00245 } 00246 00247 /// \brief Remove link, update info for both nodes. Useful for R2 only. 00248 void removeLinkR2(const GraphEdgeIterator &edgeItr) { 00249 GraphNodeIterator node1Itr = g.getEdgeNode1Itr(edgeItr); 00250 00251 if (g.getNodeData(node1Itr).getLinkDegree() > 2) { 00252 heuristic.handleRemoveLink(edgeItr, node1Itr); 00253 } 00254 removeLink(edgeItr, g.getEdgeNode2Itr(edgeItr)); 00255 } 00256 00257 /// \brief Removes all links connected to the given node. 00258 void unlinkNode(const GraphNodeIterator &nodeItr) { 00259 NodeData &nodeData = g.getNodeData(nodeItr); 00260 00261 typedef std::vector<GraphEdgeIterator> TempEdgeList; 00262 00263 TempEdgeList edgesToUnlink; 00264 edgesToUnlink.reserve(nodeData.getLinkDegree()); 00265 00266 // Copy adj edges into a temp vector. We want to destroy them during 00267 // the unlink, and we can't do that while we're iterating over them. 00268 std::copy(nodeData.adjLinksBegin(), nodeData.adjLinksEnd(), 00269 std::back_inserter(edgesToUnlink)); 00270 00271 for (typename TempEdgeList::iterator 00272 edgeItr = edgesToUnlink.begin(), edgeEnd = edgesToUnlink.end(); 00273 edgeItr != edgeEnd; ++edgeItr) { 00274 00275 GraphNodeIterator otherNode = g.getEdgeOtherNode(*edgeItr, nodeItr); 00276 00277 removeFromBucket(otherNode); 00278 removeLink(*edgeItr, otherNode); 00279 addToBucket(otherNode); 00280 } 00281 } 00282 00283 /// \brief Push the given node onto the stack to be solved with 00284 /// backpropagation. 00285 void pushStack(const GraphNodeIterator &nodeItr) { 00286 stack.push_back(nodeItr); 00287 } 00288 00289 /// \brief Set the solution of the given node. 00290 void setSolution(const GraphNodeIterator &nodeItr, unsigned solIndex) { 00291 solution.setSelection(g.getNodeID(nodeItr), solIndex); 00292 00293 for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr), 00294 adjEdgeEnd = g.adjEdgesEnd(nodeItr); 00295 adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) { 00296 GraphEdgeIterator edgeItr(*adjEdgeItr); 00297 GraphNodeIterator adjNodeItr(g.getEdgeOtherNode(edgeItr, nodeItr)); 00298 g.getNodeData(adjNodeItr).addSolvedLink(edgeItr); 00299 } 00300 } 00301 00302 private: 00303 00304 SolverGraph g; 00305 Heuristic heuristic; 00306 Solution solution; 00307 00308 NodeList r0Bucket, 00309 r1Bucket, 00310 r2Bucket; 00311 00312 NodeStack stack; 00313 00314 // Copy the SimpleGraph into an annotated graph which we can use for reduction. 00315 void copyGraph(const SimpleGraph &orig) { 00316 00317 assert((g.getNumEdges() == 0) && (g.getNumNodes() == 0) && 00318 "Graph should be empty prior to solver setup."); 00319 00320 assert(orig.areNodeIDsValid() && 00321 "Cannot copy from a graph with invalid node IDs."); 00322 00323 std::vector<GraphNodeIterator> newNodeItrs; 00324 00325 for (unsigned nodeID = 0; nodeID < orig.getNumNodes(); ++nodeID) { 00326 newNodeItrs.push_back( 00327 g.addNode(orig.getNodeCosts(orig.getNodeItr(nodeID)), NodeData())); 00328 } 00329 00330 for (SimpleGraph::ConstEdgeIterator 00331 origEdgeItr = orig.edgesBegin(), origEdgeEnd = orig.edgesEnd(); 00332 origEdgeItr != origEdgeEnd; ++origEdgeItr) { 00333 00334 unsigned id1 = orig.getNodeID(orig.getEdgeNode1Itr(origEdgeItr)), 00335 id2 = orig.getNodeID(orig.getEdgeNode2Itr(origEdgeItr)); 00336 00337 g.addEdge(newNodeItrs[id1], newNodeItrs[id2], 00338 orig.getEdgeCosts(origEdgeItr), EdgeData(g)); 00339 } 00340 00341 // Assign IDs to the new nodes using the ordering from the old graph, 00342 // this will lead to nodes in the new graph getting the same ID as the 00343 // corresponding node in the old graph. 00344 g.assignNodeIDs(newNodeItrs); 00345 } 00346 00347 // Simplify the annotated graph by eliminating independent edges and trivial 00348 // nodes. 00349 void simplify() { 00350 disconnectTrivialNodes(); 00351 eliminateIndependentEdges(); 00352 } 00353 00354 // Eliminate trivial nodes. 00355 void disconnectTrivialNodes() { 00356 for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd(); 00357 nodeItr != nodeEnd; ++nodeItr) { 00358 00359 if (g.getNodeCosts(nodeItr).getLength() == 1) { 00360 00361 std::vector<GraphEdgeIterator> edgesToRemove; 00362 00363 for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr), 00364 adjEdgeEnd = g.adjEdgesEnd(nodeItr); 00365 adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) { 00366 00367 GraphEdgeIterator edgeItr = *adjEdgeItr; 00368 00369 if (g.getEdgeNode1Itr(edgeItr) == nodeItr) { 00370 GraphNodeIterator otherNodeItr = g.getEdgeNode2Itr(edgeItr); 00371 g.getNodeCosts(otherNodeItr) += 00372 g.getEdgeCosts(edgeItr).getRowAsVector(0); 00373 } 00374 else { 00375 GraphNodeIterator otherNodeItr = g.getEdgeNode1Itr(edgeItr); 00376 g.getNodeCosts(otherNodeItr) += 00377 g.getEdgeCosts(edgeItr).getColAsVector(0); 00378 } 00379 00380 edgesToRemove.push_back(edgeItr); 00381 } 00382 00383 while (!edgesToRemove.empty()) { 00384 g.removeEdge(edgesToRemove.back()); 00385 edgesToRemove.pop_back(); 00386 } 00387 } 00388 } 00389 } 00390 00391 void eliminateIndependentEdges() { 00392 std::vector<GraphEdgeIterator> edgesToProcess; 00393 00394 for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd(); 00395 edgeItr != edgeEnd; ++edgeItr) { 00396 edgesToProcess.push_back(edgeItr); 00397 } 00398 00399 while (!edgesToProcess.empty()) { 00400 tryToEliminateEdge(edgesToProcess.back()); 00401 edgesToProcess.pop_back(); 00402 } 00403 } 00404 00405 void tryToEliminateEdge(const GraphEdgeIterator &edgeItr) { 00406 if (tryNormaliseEdgeMatrix(edgeItr)) { 00407 g.removeEdge(edgeItr); 00408 } 00409 } 00410 00411 bool tryNormaliseEdgeMatrix(const GraphEdgeIterator &edgeItr) { 00412 00413 Matrix &edgeCosts = g.getEdgeCosts(edgeItr); 00414 Vector &uCosts = g.getNodeCosts(g.getEdgeNode1Itr(edgeItr)), 00415 &vCosts = g.getNodeCosts(g.getEdgeNode2Itr(edgeItr)); 00416 00417 for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { 00418 PBQPNum rowMin = edgeCosts.getRowMin(r); 00419 uCosts[r] += rowMin; 00420 if (rowMin != std::numeric_limits<PBQPNum>::infinity()) { 00421 edgeCosts.subFromRow(r, rowMin); 00422 } 00423 else { 00424 edgeCosts.setRow(r, 0); 00425 } 00426 } 00427 00428 for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { 00429 PBQPNum colMin = edgeCosts.getColMin(c); 00430 vCosts[c] += colMin; 00431 if (colMin != std::numeric_limits<PBQPNum>::infinity()) { 00432 edgeCosts.subFromCol(c, colMin); 00433 } 00434 else { 00435 edgeCosts.setCol(c, 0); 00436 } 00437 } 00438 00439 return edgeCosts.isZero(); 00440 } 00441 00442 void setup() { 00443 setupLinks(); 00444 heuristic.initialise(*this); 00445 setupBuckets(); 00446 } 00447 00448 void setupLinks() { 00449 for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd(); 00450 edgeItr != edgeEnd; ++edgeItr) { 00451 g.getEdgeData(edgeItr).setup(edgeItr); 00452 } 00453 } 00454 00455 void setupBuckets() { 00456 for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd(); 00457 nodeItr != nodeEnd; ++nodeItr) { 00458 addToBucket(nodeItr); 00459 } 00460 } 00461 00462 void computeSolution() { 00463 assert(g.areNodeIDsValid() && 00464 "Nodes cannot be added/removed during reduction."); 00465 00466 reduce(); 00467 computeTrivialSolutions(); 00468 backpropagate(); 00469 } 00470 00471 void printNode(const GraphNodeIterator &nodeItr) { 00472 llvm::errs() << "Node " << g.getNodeID(nodeItr) << " (" << &*nodeItr << "):\n" 00473 << " costs = " << g.getNodeCosts(nodeItr) << "\n" 00474 << " link degree = " << g.getNodeData(nodeItr).getLinkDegree() << "\n" 00475 << " links = [ "; 00476 00477 for (typename HSIT::NodeData::AdjLinkIterator 00478 aeItr = g.getNodeData(nodeItr).adjLinksBegin(), 00479 aeEnd = g.getNodeData(nodeItr).adjLinksEnd(); 00480 aeItr != aeEnd; ++aeItr) { 00481 llvm::errs() << "(" << g.getNodeID(g.getEdgeNode1Itr(*aeItr)) 00482 << ", " << g.getNodeID(g.getEdgeNode2Itr(*aeItr)) 00483 << ") "; 00484 } 00485 llvm::errs() << "]\n"; 00486 } 00487 00488 void dumpState() { 00489 llvm::errs() << "\n"; 00490 00491 for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd(); 00492 nodeItr != nodeEnd; ++nodeItr) { 00493 printNode(nodeItr); 00494 } 00495 00496 NodeList* buckets[] = { &r0Bucket, &r1Bucket, &r2Bucket }; 00497 00498 for (unsigned b = 0; b < 3; ++b) { 00499 NodeList &bucket = *buckets[b]; 00500 00501 llvm::errs() << "Bucket " << b << ": [ "; 00502 00503 for (NodeListIterator nItr = bucket.begin(), nEnd = bucket.end(); 00504 nItr != nEnd; ++nItr) { 00505 llvm::errs() << g.getNodeID(*nItr) << " "; 00506 } 00507 00508 llvm::errs() << "]\n"; 00509 } 00510 00511 llvm::errs() << "Stack: [ "; 00512 for (NodeStackIterator nsItr = stack.begin(), nsEnd = stack.end(); 00513 nsItr != nsEnd; ++nsItr) { 00514 llvm::errs() << g.getNodeID(*nsItr) << " "; 00515 } 00516 llvm::errs() << "]\n"; 00517 } 00518 00519 void reduce() { 00520 bool reductionFinished = r1Bucket.empty() && r2Bucket.empty() && 00521 heuristic.rNBucketEmpty(); 00522 00523 while (!reductionFinished) { 00524 00525 if (!r1Bucket.empty()) { 00526 processR1(); 00527 } 00528 else if (!r2Bucket.empty()) { 00529 processR2(); 00530 } 00531 else if (!heuristic.rNBucketEmpty()) { 00532 solution.setProvedOptimal(false); 00533 solution.incRNReductions(); 00534 heuristic.processRN(); 00535 } 00536 else reductionFinished = true; 00537 } 00538 00539 }; 00540 00541 void processR1() { 00542 00543 // Remove the first node in the R0 bucket: 00544 GraphNodeIterator xNodeItr = r1Bucket.front(); 00545 r1Bucket.pop_front(); 00546 00547 solution.incR1Reductions(); 00548 00549 //llvm::errs() << "Applying R1 to " << g.getNodeID(xNodeItr) << "\n"; 00550 00551 assert((g.getNodeData(xNodeItr).getLinkDegree() == 1) && 00552 "Node in R1 bucket has degree != 1"); 00553 00554 GraphEdgeIterator edgeItr = *g.getNodeData(xNodeItr).adjLinksBegin(); 00555 00556 const Matrix &edgeCosts = g.getEdgeCosts(edgeItr); 00557 00558 const Vector &xCosts = g.getNodeCosts(xNodeItr); 00559 unsigned xLen = xCosts.getLength(); 00560 00561 // Duplicate a little code to avoid transposing matrices: 00562 if (xNodeItr == g.getEdgeNode1Itr(edgeItr)) { 00563 GraphNodeIterator yNodeItr = g.getEdgeNode2Itr(edgeItr); 00564 Vector &yCosts = g.getNodeCosts(yNodeItr); 00565 unsigned yLen = yCosts.getLength(); 00566 00567 for (unsigned j = 0; j < yLen; ++j) { 00568 PBQPNum min = edgeCosts[0][j] + xCosts[0]; 00569 for (unsigned i = 1; i < xLen; ++i) { 00570 PBQPNum c = edgeCosts[i][j] + xCosts[i]; 00571 if (c < min) 00572 min = c; 00573 } 00574 yCosts[j] += min; 00575 } 00576 } 00577 else { 00578 GraphNodeIterator yNodeItr = g.getEdgeNode1Itr(edgeItr); 00579 Vector &yCosts = g.getNodeCosts(yNodeItr); 00580 unsigned yLen = yCosts.getLength(); 00581 00582 for (unsigned i = 0; i < yLen; ++i) { 00583 PBQPNum min = edgeCosts[i][0] + xCosts[0]; 00584 00585 for (unsigned j = 1; j < xLen; ++j) { 00586 PBQPNum c = edgeCosts[i][j] + xCosts[j]; 00587 if (c < min) 00588 min = c; 00589 } 00590 yCosts[i] += min; 00591 } 00592 } 00593 00594 unlinkNode(xNodeItr); 00595 pushStack(xNodeItr); 00596 } 00597 00598 void processR2() { 00599 00600 GraphNodeIterator xNodeItr = r2Bucket.front(); 00601 r2Bucket.pop_front(); 00602 00603 solution.incR2Reductions(); 00604 00605 // Unlink is unsafe here. At some point it may optimistically more a node 00606 // to a lower-degree list when its degree will later rise, or vice versa, 00607 // violating the assumption that node degrees monotonically decrease 00608 // during the reduction phase. Instead we'll bucket shuffle manually. 00609 pushStack(xNodeItr); 00610 00611 assert((g.getNodeData(xNodeItr).getLinkDegree() == 2) && 00612 "Node in R2 bucket has degree != 2"); 00613 00614 const Vector &xCosts = g.getNodeCosts(xNodeItr); 00615 00616 typename NodeData::AdjLinkIterator tempItr = 00617 g.getNodeData(xNodeItr).adjLinksBegin(); 00618 00619 GraphEdgeIterator yxEdgeItr = *tempItr, 00620 zxEdgeItr = *(++tempItr); 00621 00622 GraphNodeIterator yNodeItr = g.getEdgeOtherNode(yxEdgeItr, xNodeItr), 00623 zNodeItr = g.getEdgeOtherNode(zxEdgeItr, xNodeItr); 00624 00625 removeFromBucket(yNodeItr); 00626 removeFromBucket(zNodeItr); 00627 00628 removeLink(yxEdgeItr, yNodeItr); 00629 removeLink(zxEdgeItr, zNodeItr); 00630 00631 // Graph some of the costs: 00632 bool flipEdge1 = (g.getEdgeNode1Itr(yxEdgeItr) == xNodeItr), 00633 flipEdge2 = (g.getEdgeNode1Itr(zxEdgeItr) == xNodeItr); 00634 00635 const Matrix *yxCosts = flipEdge1 ? 00636 new Matrix(g.getEdgeCosts(yxEdgeItr).transpose()) : 00637 &g.getEdgeCosts(yxEdgeItr), 00638 *zxCosts = flipEdge2 ? 00639 new Matrix(g.getEdgeCosts(zxEdgeItr).transpose()) : 00640 &g.getEdgeCosts(zxEdgeItr); 00641 00642 unsigned xLen = xCosts.getLength(), 00643 yLen = yxCosts->getRows(), 00644 zLen = zxCosts->getRows(); 00645 00646 // Compute delta: 00647 Matrix delta(yLen, zLen); 00648 00649 for (unsigned i = 0; i < yLen; ++i) { 00650 for (unsigned j = 0; j < zLen; ++j) { 00651 PBQPNum min = (*yxCosts)[i][0] + (*zxCosts)[j][0] + xCosts[0]; 00652 for (unsigned k = 1; k < xLen; ++k) { 00653 PBQPNum c = (*yxCosts)[i][k] + (*zxCosts)[j][k] + xCosts[k]; 00654 if (c < min) { 00655 min = c; 00656 } 00657 } 00658 delta[i][j] = min; 00659 } 00660 } 00661 00662 if (flipEdge1) 00663 delete yxCosts; 00664 00665 if (flipEdge2) 00666 delete zxCosts; 00667 00668 // Deal with the potentially induced yz edge. 00669 GraphEdgeIterator yzEdgeItr = g.findEdge(yNodeItr, zNodeItr); 00670 if (yzEdgeItr == g.edgesEnd()) { 00671 yzEdgeItr = g.addEdge(yNodeItr, zNodeItr, delta, EdgeData(g)); 00672 } 00673 else { 00674 // There was an edge, but we're going to screw with it. Delete the old 00675 // link, update the costs. We'll re-link it later. 00676 removeLinkR2(yzEdgeItr); 00677 g.getEdgeCosts(yzEdgeItr) += 00678 (yNodeItr == g.getEdgeNode1Itr(yzEdgeItr)) ? 00679 delta : delta.transpose(); 00680 } 00681 00682 bool nullCostEdge = tryNormaliseEdgeMatrix(yzEdgeItr); 00683 00684 // Nulled the edge, remove it entirely. 00685 if (nullCostEdge) { 00686 g.removeEdge(yzEdgeItr); 00687 } 00688 else { 00689 // Edge remains - re-link it. 00690 addLink(yzEdgeItr); 00691 } 00692 00693 addToBucket(yNodeItr); 00694 addToBucket(zNodeItr); 00695 } 00696 00697 void computeTrivialSolutions() { 00698 00699 for (NodeListIterator r0Itr = r0Bucket.begin(), r0End = r0Bucket.end(); 00700 r0Itr != r0End; ++r0Itr) { 00701 GraphNodeIterator nodeItr = *r0Itr; 00702 00703 solution.incR0Reductions(); 00704 setSolution(nodeItr, g.getNodeCosts(nodeItr).minIndex()); 00705 } 00706 00707 } 00708 00709 void backpropagate() { 00710 while (!stack.empty()) { 00711 computeSolution(stack.back()); 00712 stack.pop_back(); 00713 } 00714 } 00715 00716 void computeSolution(const GraphNodeIterator &nodeItr) { 00717 00718 NodeData &nodeData = g.getNodeData(nodeItr); 00719 00720 Vector v(g.getNodeCosts(nodeItr)); 00721 00722 // Solve based on existing links. 00723 for (typename NodeData::AdjLinkIterator 00724 solvedLinkItr = nodeData.solvedLinksBegin(), 00725 solvedLinkEnd = nodeData.solvedLinksEnd(); 00726 solvedLinkItr != solvedLinkEnd; ++solvedLinkItr) { 00727 00728 GraphEdgeIterator solvedEdgeItr(*solvedLinkItr); 00729 Matrix &edgeCosts = g.getEdgeCosts(solvedEdgeItr); 00730 00731 if (nodeItr == g.getEdgeNode1Itr(solvedEdgeItr)) { 00732 GraphNodeIterator adjNode(g.getEdgeNode2Itr(solvedEdgeItr)); 00733 unsigned adjSolution = 00734 solution.getSelection(g.getNodeID(adjNode)); 00735 v += edgeCosts.getColAsVector(adjSolution); 00736 } 00737 else { 00738 GraphNodeIterator adjNode(g.getEdgeNode1Itr(solvedEdgeItr)); 00739 unsigned adjSolution = 00740 solution.getSelection(g.getNodeID(adjNode)); 00741 v += edgeCosts.getRowAsVector(adjSolution); 00742 } 00743 00744 } 00745 00746 setSolution(nodeItr, v.minIndex()); 00747 } 00748 00749 void computeSolutionCost(const SimpleGraph &orig) { 00750 PBQPNum cost = 0.0; 00751 00752 for (SimpleGraph::ConstNodeIterator 00753 nodeItr = orig.nodesBegin(), nodeEnd = orig.nodesEnd(); 00754 nodeItr != nodeEnd; ++nodeItr) { 00755 00756 unsigned nodeId = orig.getNodeID(nodeItr); 00757 00758 cost += orig.getNodeCosts(nodeItr)[solution.getSelection(nodeId)]; 00759 } 00760 00761 for (SimpleGraph::ConstEdgeIterator 00762 edgeItr = orig.edgesBegin(), edgeEnd = orig.edgesEnd(); 00763 edgeItr != edgeEnd; ++edgeItr) { 00764 00765 SimpleGraph::ConstNodeIterator n1 = orig.getEdgeNode1Itr(edgeItr), 00766 n2 = orig.getEdgeNode2Itr(edgeItr); 00767 unsigned sol1 = solution.getSelection(orig.getNodeID(n1)), 00768 sol2 = solution.getSelection(orig.getNodeID(n2)); 00769 00770 cost += orig.getEdgeCosts(edgeItr)[sol1][sol2]; 00771 } 00772 00773 solution.setSolutionCost(cost); 00774 } 00775 00776 }; 00777 00778 template <typename Heuristic> 00779 class HeuristicSolver : public Solver { 00780 public: 00781 Solution solve(const SimpleGraph &g) const { 00782 HeuristicSolverImpl<Heuristic> solverImpl(g); 00783 return solverImpl.getSolution(); 00784 } 00785 }; 00786 00787 } 00788 00789 #endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H