1 //===----------- ReductionRules.h - Reduction Rules -------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // Reduction Rules. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_CODEGEN_PBQP_REDUCTIONRULES_H 15 #define LLVM_CODEGEN_PBQP_REDUCTIONRULES_H 16 17 #include "Graph.h" 18 #include "Math.h" 19 #include "Solution.h" 20 21 namespace llvm { 22 namespace PBQP { 23 24 /// \brief Reduce a node of degree one. 25 /// 26 /// Propagate costs from the given node, which must be of degree one, to its 27 /// neighbor. Notify the problem domain. 28 template <typename GraphT> applyR1(GraphT & G,typename GraphT::NodeId NId)29 void applyR1(GraphT &G, typename GraphT::NodeId NId) { 30 typedef typename GraphT::NodeId NodeId; 31 typedef typename GraphT::EdgeId EdgeId; 32 typedef typename GraphT::Vector Vector; 33 typedef typename GraphT::Matrix Matrix; 34 typedef typename GraphT::RawVector RawVector; 35 36 assert(G.getNodeDegree(NId) == 1 && 37 "R1 applied to node with degree != 1."); 38 39 EdgeId EId = *G.adjEdgeIds(NId).begin(); 40 NodeId MId = G.getEdgeOtherNodeId(EId, NId); 41 42 const Matrix &ECosts = G.getEdgeCosts(EId); 43 const Vector &XCosts = G.getNodeCosts(NId); 44 RawVector YCosts = G.getNodeCosts(MId); 45 46 // Duplicate a little to avoid transposing matrices. 47 if (NId == G.getEdgeNode1Id(EId)) { 48 for (unsigned j = 0; j < YCosts.getLength(); ++j) { 49 PBQPNum Min = ECosts[0][j] + XCosts[0]; 50 for (unsigned i = 1; i < XCosts.getLength(); ++i) { 51 PBQPNum C = ECosts[i][j] + XCosts[i]; 52 if (C < Min) 53 Min = C; 54 } 55 YCosts[j] += Min; 56 } 57 } else { 58 for (unsigned i = 0; i < YCosts.getLength(); ++i) { 59 PBQPNum Min = ECosts[i][0] + XCosts[0]; 60 for (unsigned j = 1; j < XCosts.getLength(); ++j) { 61 PBQPNum C = ECosts[i][j] + XCosts[j]; 62 if (C < Min) 63 Min = C; 64 } 65 YCosts[i] += Min; 66 } 67 } 68 G.setNodeCosts(MId, YCosts); 69 G.disconnectEdge(EId, MId); 70 } 71 72 template <typename GraphT> applyR2(GraphT & G,typename GraphT::NodeId NId)73 void applyR2(GraphT &G, typename GraphT::NodeId NId) { 74 typedef typename GraphT::NodeId NodeId; 75 typedef typename GraphT::EdgeId EdgeId; 76 typedef typename GraphT::Vector Vector; 77 typedef typename GraphT::Matrix Matrix; 78 typedef typename GraphT::RawMatrix RawMatrix; 79 80 assert(G.getNodeDegree(NId) == 2 && 81 "R2 applied to node with degree != 2."); 82 83 const Vector &XCosts = G.getNodeCosts(NId); 84 85 typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin(); 86 EdgeId YXEId = *AEItr, 87 ZXEId = *(++AEItr); 88 89 NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId), 90 ZNId = G.getEdgeOtherNodeId(ZXEId, NId); 91 92 bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId), 93 FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId); 94 95 const Matrix *YXECosts = FlipEdge1 ? 96 new Matrix(G.getEdgeCosts(YXEId).transpose()) : 97 &G.getEdgeCosts(YXEId); 98 99 const Matrix *ZXECosts = FlipEdge2 ? 100 new Matrix(G.getEdgeCosts(ZXEId).transpose()) : 101 &G.getEdgeCosts(ZXEId); 102 103 unsigned XLen = XCosts.getLength(), 104 YLen = YXECosts->getRows(), 105 ZLen = ZXECosts->getRows(); 106 107 RawMatrix Delta(YLen, ZLen); 108 109 for (unsigned i = 0; i < YLen; ++i) { 110 for (unsigned j = 0; j < ZLen; ++j) { 111 PBQPNum Min = (*YXECosts)[i][0] + (*ZXECosts)[j][0] + XCosts[0]; 112 for (unsigned k = 1; k < XLen; ++k) { 113 PBQPNum C = (*YXECosts)[i][k] + (*ZXECosts)[j][k] + XCosts[k]; 114 if (C < Min) { 115 Min = C; 116 } 117 } 118 Delta[i][j] = Min; 119 } 120 } 121 122 if (FlipEdge1) 123 delete YXECosts; 124 125 if (FlipEdge2) 126 delete ZXECosts; 127 128 EdgeId YZEId = G.findEdge(YNId, ZNId); 129 130 if (YZEId == G.invalidEdgeId()) { 131 YZEId = G.addEdge(YNId, ZNId, Delta); 132 } else { 133 const Matrix &YZECosts = G.getEdgeCosts(YZEId); 134 if (YNId == G.getEdgeNode1Id(YZEId)) { 135 G.setEdgeCosts(YZEId, Delta + YZECosts); 136 } else { 137 G.setEdgeCosts(YZEId, Delta.transpose() + YZECosts); 138 } 139 } 140 141 G.disconnectEdge(YXEId, YNId); 142 G.disconnectEdge(ZXEId, ZNId); 143 144 // TODO: Try to normalize newly added/modified edge. 145 } 146 147 148 // \brief Find a solution to a fully reduced graph by backpropagation. 149 // 150 // Given a graph and a reduction order, pop each node from the reduction 151 // order and greedily compute a minimum solution based on the node costs, and 152 // the dependent costs due to previously solved nodes. 153 // 154 // Note - This does not return the graph to its original (pre-reduction) 155 // state: the existing solvers destructively alter the node and edge 156 // costs. Given that, the backpropagate function doesn't attempt to 157 // replace the edges either, but leaves the graph in its reduced 158 // state. 159 template <typename GraphT, typename StackT> backpropagate(GraphT & G,StackT stack)160 Solution backpropagate(GraphT& G, StackT stack) { 161 typedef GraphBase::NodeId NodeId; 162 typedef typename GraphT::Matrix Matrix; 163 typedef typename GraphT::RawVector RawVector; 164 165 Solution s; 166 167 while (!stack.empty()) { 168 NodeId NId = stack.back(); 169 stack.pop_back(); 170 171 RawVector v = G.getNodeCosts(NId); 172 173 for (auto EId : G.adjEdgeIds(NId)) { 174 const Matrix& edgeCosts = G.getEdgeCosts(EId); 175 if (NId == G.getEdgeNode1Id(EId)) { 176 NodeId mId = G.getEdgeNode2Id(EId); 177 v += edgeCosts.getColAsVector(s.getSelection(mId)); 178 } else { 179 NodeId mId = G.getEdgeNode1Id(EId); 180 v += edgeCosts.getRowAsVector(s.getSelection(mId)); 181 } 182 } 183 184 s.setSelection(NId, v.minIndex()); 185 } 186 187 return s; 188 } 189 190 } // namespace PBQP 191 } // namespace llvm 192 193 #endif 194