angel
mercurial changeset:
|
00001 // $Id: xaif_interface.cpp,v 1.15 2008/02/28 14:57:33 gottschling Exp $ 00002 /* 00003 ############################################################# 00004 # This file is part of angel released under the BSD license # 00005 # The full COPYRIGHT notice can be found in the top # 00006 # level directory of the angel distribution # 00007 ############################################################# 00008 */ 00009 00010 #ifdef USEXAIFBOOSTER 00011 00012 #include <set> 00013 #include <climits> 00014 00015 #include "angel/include/xaif_interface.hpp" 00016 #include "angel/include/eliminations.hpp" 00017 #include "angel/include/heuristics.hpp" 00018 #include "angel/include/reroutings.hpp" 00019 #include "angel/include/angel_tools.hpp" 00020 00021 #include "angel/include/angel_io.hpp" 00022 #include "angel/include/sa.hpp" 00023 00024 namespace angel { 00025 00026 using namespace std; 00027 using namespace boost; 00028 using namespace xaifBoosterCrossCountryInterface; 00029 00030 inline size_t which_index (const LinearizedComputationalGraphVertex * const add, 00031 const vector<const LinearizedComputationalGraphVertex*>& av) { 00032 for (size_t c= 0; c < av.size(); c++) if (add == av[c]) return c; 00033 return av.size(); } 00034 00035 struct edge_address_t { 00036 ad_edge_t e; 00037 const LinearizedComputationalGraphEdge* address; 00038 edge_address_t (int _i, int _j, const LinearizedComputationalGraphEdge* _address) : 00039 e (_i, _j), address (_address) {} 00040 }; 00041 00042 void read_graph_xaif_booster (const LinearizedComputationalGraph& xg, c_graph_t& cg, 00043 vector<const LinearizedComputationalGraphVertex*>& av, 00044 vector<edge_address_t>& ae) { 00045 typedef LinearizedComputationalGraph xgraph_t; 00046 typedef LinearizedComputationalGraphVertex xvertex_t; 00047 typedef LinearizedComputationalGraphEdge xedge_t; 00048 typedef c_graph_t::vertex_t vertex_t; 00049 00050 int nv= xg.numVertices (); 00051 c_graph_t gtmp (0, nv, 0); // all vertices as intermediate for now 00052 00053 xgraph_t::ConstVertexIteratorPair vip (xg.vertices()); 00054 00055 // independents are first 00056 const xgraph_t::VertexPointerList& indeps_list= xg.getIndependentList (); 00057 xgraph_t::VertexPointerList::const_iterator 00058 bi= indeps_list.begin(), be= indeps_list.end(); 00059 for (; bi != be; bi++) { 00060 av.push_back (*bi); 00061 // indeps.push_back (c); 00062 } 00063 00064 // remaining are sorted topologically 00065 while ((int) av.size() < nv) { 00066 xgraph_t::ConstVertexIterator vi (vip.first), v_end (vip.second); 00067 for (; vi != v_end; ++vi) { 00068 if (which_index (&*vi, av) != av.size()) continue; 00069 xgraph_t::ConstInEdgeIteratorPair inedges (xg.getInEdgesOf (*vi)); 00070 xgraph_t::ConstInEdgeIterator ie= inedges.first, iend= inedges.second; 00071 bool all_num= true; // all predecessors numbered 00072 for (; ie != iend; ++ie) 00073 if (which_index (&(xg.getSourceOf (*ie)), av) == av.size()) { 00074 all_num= false; break; } 00075 if (all_num) av.push_back (&*vi); 00076 } } 00077 00078 // re-activated 00079 vector<vertex_t> indeps; 00080 for (bi= indeps_list.begin(); bi != be; bi++) indeps.push_back (which_index (*bi, av)); 00081 00082 // test whether indeps in the beginning 00083 for (size_t c= 0; c < indeps.size(); c++) 00084 // assert (indeps[c] < indeps.size()); 00085 THROW_EXCEPT_MACRO (indeps[c] >= indeps.size(), consistency_exception, 00086 "Independent not at the beginning"); 00087 00088 vector<vertex_t> deps; 00089 const xgraph_t::VertexPointerList& deps_list= xg.getDependentList (); 00090 bi= deps_list.begin(), be= deps_list.end(); 00091 for (; bi != be; bi++) deps.push_back (which_index (*bi, av)); 00092 00093 int edge_number= 0; 00094 boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), cg); 00095 xgraph_t::ConstEdgeIteratorPair eip (xg.edges()); 00096 for (xgraph_t::ConstEdgeIterator ei (eip.first), e_end (eip.second); ei != e_end; ++ei) { 00097 vertex_t source= which_index (& (xg.getSourceOf (*ei)), av), 00098 target= which_index (& (xg.getTargetOf (*ei)), av); 00099 pair<c_graph_t::edge_t, bool> new_edge = add_edge (source, target, edge_number++, cg); 00100 ae.push_back (edge_address_t(source, target, &*ei)); 00101 if ((*ei).getEdgeLabelType() == LinearizedComputationalGraphEdge::UNIT_LABEL) 00102 eType[new_edge.first] = UNIT_EDGE; 00103 else if ((*ei).getEdgeLabelType() == LinearizedComputationalGraphEdge::CONSTANT_LABEL) 00104 eType[new_edge.first] = CONSTANT_EDGE; 00105 else 00106 eType[new_edge.first] = VARIABLE_EDGE; 00107 } // end for all LCG edges 00108 00109 cg.X= int (indeps.size()); cg.dependents= deps; 00110 00111 #ifndef NDEBUG 00112 write_graph ("read_graph_xaif_booster: resulting graph", cg); 00113 #endif 00114 00115 } 00116 00117 inline const LinearizedComputationalGraphEdge* 00118 xaif_edge_pr (line_graph_t::edge_t e, const accu_graph_t& ag, const vector<edge_address_t>& ae) { 00119 line_graph_t::const_evn_t evn= get (vertex_name, ag.lg); 00120 ad_edge_t edge_name= evn[e]; 00121 00122 int first_try= e - ag.lg.x(); 00123 if (edge_name == ae[first_try].e) return ae[first_try].address; 00124 for (size_t c= 0; c < ae.size(); c++) 00125 if (edge_name == ae[c].e) return ae[c].address; 00126 return 0; 00127 } 00128 00129 void write_graph_xaif_booster (const accu_graph_t& ag, 00130 const vector<const LinearizedComputationalGraphVertex*>& av, 00131 const vector<edge_address_t>& ae, 00132 JacobianAccumulationExpressionList& JAElist, 00133 LinearizedComputationalGraph& remainderLCG, 00134 VertexCorrelationList& v_cor_list, 00135 EdgeCorrelationList& e_cor_list) { 00136 remainderLCG.clear(); 00137 set<unsigned int> independent_indices, dependent_indices; 00138 // line_graph_t::const_evn_t evn= get (vertex_name, ag.lg); 00139 00140 // make a preliminary pass to make remainder graph vertices 00141 for (size_t c = 0; c < ag.accu_exp.size(); c++) { 00142 ad_edge_t my_jacobi = ag.jacobi_entries[c]; 00143 if (my_jacobi.second != 0) { 00144 // store indices of indep and dep vertices 00145 independent_indices.insert(my_jacobi.first); 00146 dependent_indices.insert(my_jacobi.second); 00147 } 00148 } // end preliminary pass 00149 00150 // create and correlate remainder graph vertices from indep and dep sets 00151 for (set<unsigned int>::const_iterator sit = independent_indices.begin(); sit != independent_indices.end(); sit++) { 00152 LinearizedComputationalGraphVertex& new_remainder_vertex = remainderLCG.addVertex(); 00153 VertexCorrelationEntry new_vertex_correlation; 00154 new_vertex_correlation.myOriginalVertex_p = av[*sit]; 00155 new_vertex_correlation.myRemainderVertex_p = &new_remainder_vertex; 00156 v_cor_list.push_back(new_vertex_correlation); 00157 } 00158 for (set<unsigned int>::const_iterator sit = dependent_indices.begin(); sit != dependent_indices.end(); sit++) { 00159 LinearizedComputationalGraphVertex& new_remainder_vertex = remainderLCG.addVertex(); 00160 VertexCorrelationEntry new_vertex_correlation; 00161 new_vertex_correlation.myOriginalVertex_p = av[*sit]; 00162 new_vertex_correlation.myRemainderVertex_p = &new_remainder_vertex; 00163 v_cor_list.push_back(new_vertex_correlation); 00164 } 00165 00166 // iterate over all angel JAEs 00167 vector<JacobianAccumulationExpressionVertex*> exp_output_pr; // pointer to output vertex of expression 00168 for (size_t c= 0; c < ag.accu_exp.size(); c++) { 00169 const accu_exp_graph_t& my_exp= ag.accu_exp[c]; 00170 property_map<pure_accu_exp_graph_t, vertex_name_t>::const_type vpr= get (vertex_name, my_exp); 00171 00172 JacobianAccumulationExpression& new_exp = JAElist.addExpression(); 00173 //exp_pr.push_back(&new_exp); 00174 vector<JacobianAccumulationExpressionVertex*> vp (my_exp.v()); 00175 for (size_t vc= 0; vc < (size_t) my_exp.v(); vc++) { 00176 const accu_exp_t& prop= vpr[vc]; 00177 JacobianAccumulationExpressionVertex& new_vertex = new_exp.addVertex(); 00178 vp[vc]= &new_vertex; 00179 00180 // the last vertex in the expression is the output vertex 00181 if (vc+1 == (size_t) my_exp.v()) exp_output_pr.push_back(&new_vertex); 00182 00183 switch (prop.ref_kind) { 00184 case accu_exp_t::nothing: THROW_EXCEPT_MACRO (true, consistency_exception, "Unset vertex"); break; 00185 case accu_exp_t::exp: 00186 THROW_DEBUG_EXCEPT_MACRO (prop.ref.exp_nr >= int (c), consistency_exception, "Expression number too large") 00187 new_vertex.setInternalReference (*exp_output_pr[prop.ref.exp_nr]); break; 00188 case accu_exp_t::lgn: { 00189 const LinearizedComputationalGraphEdge* ptr= xaif_edge_pr (prop.ref.node, ag, ae); 00190 THROW_DEBUG_EXCEPT_MACRO (ptr == NULL, consistency_exception, "Unset reference"); 00191 new_vertex.setExternalReference (*ptr); } break; 00192 case accu_exp_t::isop: 00193 new_vertex.setOperation (prop.ref.op == accu_exp_t::add ? JacobianAccumulationExpressionVertex::ADD_OP 00194 : JacobianAccumulationExpressionVertex::MULT_OP); 00195 } // end switch on prop.ref_kind 00196 } // end all expression vertices 00197 00198 // deal with JAE edges 00199 graph_traits<pure_accu_exp_graph_t>::edge_iterator ei, e_end; 00200 for (tie (ei, e_end)= edges (my_exp); ei != e_end; ei++) 00201 new_exp.addEdge (*vp[source (*ei, my_exp)], *vp[target (*ei, my_exp)]); 00202 00203 // deal with JAEs that are Jacobian entries 00204 ad_edge_t my_jacobi = ag.jacobi_entries[c]; 00205 if (my_jacobi.second != 0) { 00206 //new_exp.setJacobianEntry (*av[my_jacobi.second], *av[my_jacobi.first]); 00207 00208 // create edge in the remainder graph 00209 const LinearizedComputationalGraphVertex* original_src_p = av[my_jacobi.first]; 00210 const LinearizedComputationalGraphVertex* original_tgt_p = av[my_jacobi.second]; 00211 LinearizedComputationalGraphVertex* remainder_src_p = NULL; 00212 LinearizedComputationalGraphVertex* remainder_tgt_p = NULL; 00213 for (VertexCorrelationList::iterator vcori = v_cor_list.begin(); vcori != v_cor_list.end(); vcori++) { 00214 if (vcori->myOriginalVertex_p == original_src_p) remainder_src_p = vcori->myRemainderVertex_p; 00215 else if (vcori->myOriginalVertex_p == original_tgt_p) remainder_tgt_p = vcori->myRemainderVertex_p; 00216 } // end all vertex correlation entries 00217 THROW_EXCEPT_MACRO (remainder_src_p == NULL || remainder_tgt_p == NULL, consistency_exception, "Vertex in remainder graph could not be found"); 00218 LinearizedComputationalGraphEdge& new_remainder_edge = remainderLCG.addEdge(*remainder_src_p, *remainder_tgt_p); 00219 00220 // crate the correlation entry 00221 EdgeCorrelationEntry new_edge_correlation; 00222 new_edge_correlation.myRemainderGraphEdge_p = &new_remainder_edge; 00223 new_edge_correlation.myType = EdgeCorrelationEntry::JAE_VERT; 00224 new_edge_correlation.myEliminationReference.myJAEVertex_p = exp_output_pr.back(); 00225 //new_edge_correlation.myEliminationReference.myJAEVertex_p = getJAE_p (*ei, angelLCG, edge_ref_list); 00226 e_cor_list.push_back(new_edge_correlation); 00227 } // end if Jacobian entry 00228 00229 } // end all Jacobian accumulation expressions 00230 } // end write_graph_xaif_booster() 00231 00232 unsigned int num_nontrivial_edges (const c_graph_t& angelLCG, 00233 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) { 00234 boost::property_map<c_graph_t, EdgeType>::const_type eType = get (EdgeType(), angelLCG); 00235 unsigned int numNontrivialEdges = 0; 00236 c_graph_t::ei_t ei, e_end; 00237 for (tie (ei, e_end)= edges (angelLCG); ei != e_end; ++ei) 00238 if (ourAwarenessLevel == AwarenessLevel::NO_AWARENESS 00239 || (ourAwarenessLevel == AwarenessLevel::UNIT_AWARENESS && eType[*ei] != UNIT_EDGE) 00240 || (ourAwarenessLevel == AwarenessLevel::CONSTANT_AWARENESS && eType[*ei] == VARIABLE_EDGE)) 00241 numNontrivialEdges++; 00242 00243 return numNontrivialEdges; 00244 } // end of num_nontrivial_edges() 00245 00246 unsigned int numIntermediateVertices (const c_graph_t& angelLCG) { 00247 unsigned int numIntermediates = 0; 00248 c_graph_t::vi_t vi, v_end; 00249 for (tie (vi, v_end) = vertices (angelLCG); vi != v_end; ++vi) 00250 if (vertex_type (*vi, angelLCG) == intermediate) numIntermediates++; 00251 return numIntermediates; 00252 } // end numIntermediateVertices() 00253 00254 unsigned int numIntermediateVerticesWithoutUnitEdge (const c_graph_t& angelLCG) { 00255 boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG); 00256 unsigned int numIntermediatesWithoutUnitEdge = 0; 00257 c_graph_t::vi_t vi, v_end; 00258 c_graph_t::iei_t iei, ie_end; 00259 c_graph_t::oei_t oei, oe_end; 00260 00261 for (tie (vi, v_end) = vertices (angelLCG); vi != v_end; ++vi) { 00262 if (vertex_type (*vi, angelLCG) == intermediate) { 00263 for (tie(iei, ie_end) = in_edges (*vi, angelLCG); iei != ie_end; ++iei) 00264 if (eType[*iei] == UNIT_EDGE) break; 00265 for (tie(oei, oe_end) = out_edges (*vi, angelLCG); oei != oe_end; ++oei) 00266 if (eType[*oei] == UNIT_EDGE) break; 00267 if ( iei == ie_end && oei == oe_end) numIntermediatesWithoutUnitEdge++; 00268 } 00269 } 00270 return numIntermediatesWithoutUnitEdge; 00271 } // end numIntermediateVertices() 00272 00273 void ourLCG_to_angelLCG (const LinearizedComputationalGraph& ourLCG, 00274 vector<const LinearizedComputationalGraphVertex*>& ourLCG_verts, 00275 c_graph_t& angelLCG, 00276 list<EdgeRef_t>& edge_ref_list) { 00277 angelLCG.clear(); 00278 00279 // COPY VERTICES 00280 const LinearizedComputationalGraph::VertexPointerList& ourLCG_indeps = ourLCG.getIndependentList (); 00281 const LinearizedComputationalGraph::VertexPointerList& ourLCG_deps = ourLCG.getDependentList (); 00282 LinearizedComputationalGraph::VertexPointerList::const_iterator LCGvi; 00283 00284 // Add pointers to independent vertices to vector ourLCG_verts 00285 for (LCGvi = ourLCG_indeps.begin(); LCGvi != ourLCG_indeps.end(); LCGvi++) 00286 ourLCG_verts.push_back (*LCGvi); 00287 00288 // remaining are sorted topologically 00289 int nv = ourLCG.numVertices (); 00290 LinearizedComputationalGraph::ConstVertexIteratorPair vip (ourLCG.vertices()); 00291 while ((int) ourLCG_verts.size() < nv) { 00292 for (LinearizedComputationalGraph::ConstVertexIterator topi (vip.first), top_end (vip.second); topi != top_end; ++topi) { 00293 if (which_index (&*topi, ourLCG_verts) != ourLCG_verts.size()) continue; 00294 bool all_num = true; // all predecessors numbered 00295 LinearizedComputationalGraph::ConstInEdgeIteratorPair inedges (ourLCG.getInEdgesOf (*topi)); 00296 for (LinearizedComputationalGraph::ConstInEdgeIterator ie = inedges.first, iend = inedges.second; ie != iend; ++ie) 00297 if (which_index (&(ourLCG.getSourceOf (*ie)), ourLCG_verts) == ourLCG_verts.size()) { 00298 all_num = false; 00299 break; 00300 } 00301 if (all_num) ourLCG_verts.push_back (&*topi); 00302 } // end all vertices 00303 } 00304 00305 // populate vectors of independent and dependent vertices 00306 vector<c_graph_t::vertex_t> indeps, deps; 00307 for (LCGvi = ourLCG_indeps.begin(); LCGvi != ourLCG_indeps.end(); LCGvi++) 00308 indeps.push_back (which_index (*LCGvi, ourLCG_verts)); 00309 angelLCG.x(int (indeps.size())); 00310 for (LCGvi = ourLCG_deps.begin(); LCGvi != ourLCG_deps.end(); LCGvi++) 00311 deps.push_back (which_index (*LCGvi, ourLCG_verts)); 00312 angelLCG.dependents = deps; 00313 00314 // ensure that indeps occur in the beginning 00315 for (size_t c = 0; c < indeps.size(); c++) 00316 THROW_EXCEPT_MACRO (indeps[c] >= indeps.size(), consistency_exception, "Independent not at the beginning"); 00317 00318 // COPY EDGES ---------------------------------------------------------------- 00319 int edge_number = 0; 00320 boost::property_map<c_graph_t, EdgeType>::type eType = get(EdgeType(), angelLCG); 00321 LinearizedComputationalGraph::ConstEdgeIteratorPair eip (ourLCG.edges()); 00322 for (LinearizedComputationalGraph::ConstEdgeIterator ei (eip.first), e_end (eip.second); ei != e_end; ++ei) { 00323 // locate source and target of edge in angelLCG 00324 c_graph_t::vertex_t angelSource = which_index (& (ourLCG.getSourceOf (*ei)), ourLCG_verts); 00325 c_graph_t::vertex_t angelTarget = which_index (& (ourLCG.getTargetOf (*ei)), ourLCG_verts); 00326 pair<c_graph_t::edge_t, bool> new_edge = add_edge (angelSource, angelTarget, edge_number++, angelLCG); 00327 if ((*ei).getEdgeLabelType() == LinearizedComputationalGraphEdge::UNIT_LABEL) 00328 eType[new_edge.first] = UNIT_EDGE; 00329 else if ((*ei).getEdgeLabelType() == LinearizedComputationalGraphEdge::CONSTANT_LABEL) 00330 eType[new_edge.first] = CONSTANT_EDGE; 00331 else 00332 eType[new_edge.first] = VARIABLE_EDGE; 00333 00334 EdgeRef_t new_edge_ref (new_edge.first, &*ei); 00335 edge_ref_list.push_back(new_edge_ref); 00336 } // end for all LCG edges 00337 00338 #ifndef NDEBUG 00339 write_graph ("angelLCG (constructed from ourLCG): ", angelLCG); 00340 #endif 00341 00342 } // end ourLCG_to_angelLCG() 00343 00344 void populate_remainderGraph_and_correlationLists (const c_graph_t& angelLCG, 00345 const vector<const LinearizedComputationalGraphVertex*> ourLCG_verts, 00346 const list<EdgeRef_t>& edge_ref_list, 00347 LinearizedComputationalGraph& remainderLCG, 00348 VertexCorrelationList& v_cor_list, 00349 EdgeCorrelationList& e_cor_list) { 00350 remainderLCG.clear(); 00351 00352 // copy and correlate vertices 00353 v_cor_list.resize(0); 00354 c_graph_t::vi_t vi, v_end; 00355 for (tie (vi, v_end) = vertices (angelLCG); vi != v_end; ++vi) { 00356 // since vertices aren't removed from angelLCG, only copy non-isolated vertices 00357 if (in_degree (*vi, angelLCG) != 0 || out_degree (*vi, angelLCG) != 0) { 00358 LinearizedComputationalGraphVertex& new_rvert (remainderLCG.addVertex()); 00359 // add a new correlation entry to the list 00360 VertexCorrelationEntry new_rvert_cor; 00361 new_rvert_cor.myOriginalVertex_p = ourLCG_verts[*vi]; 00362 new_rvert_cor.myRemainderVertex_p = &new_rvert; 00363 v_cor_list.push_back(new_rvert_cor); 00364 } 00365 } // end all vertices 00366 00367 // copy and correlate edges 00368 boost::property_map<c_graph_t, EdgeType>::const_type eType = get(EdgeType(), angelLCG); 00369 e_cor_list.resize(0); 00370 c_graph_t::ei_t ei, e_end; 00371 for (tie(ei, e_end) = edges(angelLCG); ei != e_end; ++ei) { 00372 // Find source and target in remainder LCG 00373 const LinearizedComputationalGraphVertex* original_src_p = ourLCG_verts[source(*ei, angelLCG)]; 00374 const LinearizedComputationalGraphVertex* original_tgt_p = ourLCG_verts[target(*ei, angelLCG)]; 00375 LinearizedComputationalGraphVertex* remainder_src_p = NULL; 00376 LinearizedComputationalGraphVertex* remainder_tgt_p = NULL; 00377 for (VertexCorrelationList::iterator vcori = v_cor_list.begin(); vcori != v_cor_list.end(); vcori++) { 00378 if (vcori->myOriginalVertex_p == original_src_p) remainder_src_p = vcori->myRemainderVertex_p; 00379 else if (vcori->myOriginalVertex_p == original_tgt_p) remainder_tgt_p = vcori->myRemainderVertex_p; 00380 } // end all vertex correlation entries 00381 THROW_EXCEPT_MACRO (remainder_src_p == NULL || remainder_tgt_p == NULL, consistency_exception, 00382 "Vertex in remainder graph could not be correlated"); 00383 00384 // create the edge and its correlation entry 00385 LinearizedComputationalGraphEdge& new_redge = remainderLCG.addEdge(*remainder_src_p, *remainder_tgt_p); 00386 EdgeCorrelationEntry new_edge_correlation; 00387 new_edge_correlation.myRemainderGraphEdge_p = &new_redge; 00388 00389 // set the edge type (unit/const/variable) 00390 switch (eType[*ei]) { 00391 case UNIT_EDGE: 00392 new_redge.setEdgeLabelType(LinearizedComputationalGraphEdge::UNIT_LABEL); 00393 break; 00394 case CONSTANT_EDGE: 00395 new_redge.setEdgeLabelType(LinearizedComputationalGraphEdge::CONSTANT_LABEL); 00396 break; 00397 case VARIABLE_EDGE: 00398 new_redge.setEdgeLabelType(LinearizedComputationalGraphEdge::VARIABLE_LABEL); 00399 break; 00400 } 00401 00402 // derive contents of correlation entry from the internal edge reference list 00403 EdgeRefType_E new_remainder_edge_ref_t = getRefType (*ei, angelLCG, edge_ref_list); 00404 if (new_remainder_edge_ref_t == LCG_EDGE) { 00405 new_edge_correlation.myEliminationReference.myOriginalEdge_p = getLCG_p (*ei, angelLCG, edge_ref_list); 00406 new_edge_correlation.myType = EdgeCorrelationEntry::LCG_EDGE; 00407 } 00408 else if (new_remainder_edge_ref_t == JAE_VERT) { 00409 new_edge_correlation.myEliminationReference.myJAEVertex_p = getJAE_p (*ei, angelLCG, edge_ref_list); 00410 new_edge_correlation.myType = EdgeCorrelationEntry::JAE_VERT; 00411 } 00412 else THROW_EXCEPT_MACRO (true, consistency_exception, "Edge reference type neither LCG_EDGE nor JAE_VERT"); 00413 00414 e_cor_list.push_back(new_edge_correlation); 00415 } // end all edges in angelLCG 00416 00417 } // end populate_remainderGraph_and_correlationLists() 00418 00419 unsigned int replay_transformation_seq(c_graph_t& angelLCG, 00420 const vector<Transformation> transformationSeqV, 00421 unsigned int& previous_numNontrivialEdges, 00422 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 00423 transformationSeq_cost_t& dummy_transformationSeq_cost, 00424 refillDependenceMap_t& dummy_refillDependenceMap) { 00425 unsigned int computationalCost = 0; 00426 for (size_t i = 0; i < transformationSeqV.size(); i++) { 00427 if (i == transformationSeqV.size() - 1) // save previous_numNontrivialEdges 00428 previous_numNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel); 00429 #ifndef NDEBUG 00430 cout << "\t"; 00431 #endif 00432 // REROUTING 00433 if (transformationSeqV[i].isRerouting()) 00434 computationalCost += transformationSeqV[i].getRerouting().isPre() ? 00435 prerouteEdge_noJAE(transformationSeqV[i].getRerouting().getER(angelLCG), angelLCG) 00436 : postrouteEdge_noJAE(transformationSeqV[i].getRerouting().getER(angelLCG), angelLCG); 00437 // EDGE ELIMINATION 00438 else 00439 computationalCost += transformationSeqV[i].getEdgeElim().isFront() ? 00440 frontEdgeElimination_noJAE(transformationSeqV[i].getEdgeElim().getE(angelLCG), angelLCG, &dummy_transformationSeq_cost, dummy_refillDependenceMap) 00441 : backEdgeElimination_noJAE(transformationSeqV[i].getEdgeElim().getE(angelLCG), angelLCG, &dummy_transformationSeq_cost, dummy_refillDependenceMap); 00442 } // end iterate over transformations 00443 return computationalCost; 00444 } // end replay_transformation_seq() 00445 00446 bool isTrivialEdge(const c_graph_t::edge_t& e, 00447 c_graph_t& theAngelLCG, 00448 const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) { 00449 boost::property_map<c_graph_t,EdgeType>::type eType = get(EdgeType(),theAngelLCG); 00450 if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::NO_AWARENESS) 00451 return false; 00452 else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::UNIT_AWARENESS) 00453 return (eType[e] == UNIT_EDGE); 00454 else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::CONSTANT_AWARENESS) 00455 return (eType[e] != VARIABLE_EDGE); 00456 else 00457 THROW_EXCEPT_MACRO(true, consistency_exception, "isTrivialEdge: unknown AwarenessLevel"); 00458 } // end isTrivialEdge() 00459 00460 void assessPairElim(const c_graph_t::edge_t& e1, 00461 const c_graph_t::edge_t& e2, 00462 c_graph_t& theAngelLCG, 00463 const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 00464 unsigned int& cost, 00465 int& totalEdgecountChange, 00466 int& nontrivialEdgecountChange) { 00467 boost::property_map<c_graph_t,EdgeType>::type eType = get(EdgeType(),theAngelLCG); 00468 // determine cost 00469 cost = (eType[e1] == UNIT_EDGE || eType[e2] == UNIT_EDGE) ? 0 : 1; 00470 00471 // determine whether absorption edge is present 00472 c_graph_t::edge_t absorb_e; 00473 bool found_absorb_e; 00474 tie(absorb_e,found_absorb_e) = edge(source(e1,theAngelLCG), 00475 target(e2,theAngelLCG), 00476 theAngelLCG); 00477 // determine change in total edge count 00478 totalEdgecountChange = (found_absorb_e) ? 0 : 1; 00479 00480 // determine change in nontrivial edge count 00481 if (found_absorb_e) { // absorption: nontrivial edge count goes up iff absorb edge goes trivial => nontrivial 00482 if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::NO_AWARENESS) 00483 nontrivialEdgecountChange = 0; 00484 else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::CONSTANT_AWARENESS) { 00485 if (eType[absorb_e] == VARIABLE_EDGE) 00486 nontrivialEdgecountChange = 0; // absorb edge is already nontrivial (variable) 00487 else 00488 nontrivialEdgecountChange = (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) ? 1 : 0; 00489 } // end CONSTANT_AWARENESS 00490 else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::UNIT_AWARENESS) { 00491 if (eType[absorb_e] != UNIT_EDGE) 00492 nontrivialEdgecountChange = 0; // absorb edge is already nontrivial (nonunit) 00493 else 00494 nontrivialEdgecountChange = (eType[e1] != UNIT_EDGE || eType[e2] != UNIT_EDGE) ? 1 : 0; 00495 } // end UNIT_AWARENESS 00496 else 00497 THROW_EXCEPT_MACRO(true, consistency_exception, "isTrivialEdge: unknown AwarenessLevel"); 00498 } // end absorption 00499 00500 else { // fill-in: nontrivial edge count change iff the fill edge is nontrivial 00501 if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::NO_AWARENESS) 00502 nontrivialEdgecountChange = 1; 00503 else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::CONSTANT_AWARENESS) 00504 // nontrivial edge count goes up iff e1 or e2 is variable 00505 nontrivialEdgecountChange = (eType[e1] == VARIABLE_EDGE || eType[e2] == VARIABLE_EDGE) ? 1 : 0; 00506 else if (ourAwarenessLevel == xaifBoosterCrossCountryInterface::AwarenessLevel::UNIT_AWARENESS) 00507 // nontrivial edge count goes up iff e1 or e2 is nonunit 00508 nontrivialEdgecountChange = (eType[e1] != UNIT_EDGE || eType[e2] != UNIT_EDGE) ? 1 : 0; 00509 else 00510 THROW_EXCEPT_MACRO(true, consistency_exception, "assessPairElim: unknown AwarenessLevel"); 00511 } // end fill-in 00512 } // end assessPairElim() 00513 00514 void assessFrontEdgeElim(const c_graph_t::edge_t& e, 00515 c_graph_t& theAngelLCG, 00516 const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 00517 unsigned int& cost, 00518 int& totalEdgecountChange, 00519 int& nontrivialEdgecountChange) { 00520 boost::property_map<c_graph_t,EdgeType>::type eType = get(EdgeType(),theAngelLCG); 00521 bool isIsolated = (in_degree(target(e,theAngelLCG),theAngelLCG) == 1 00522 && vertex_type(target(e,theAngelLCG),theAngelLCG) != dependent); 00523 c_graph_t::oei_t oei, oe_end; 00524 for (tie(oei,oe_end) = out_edges(target(e,theAngelLCG),theAngelLCG); oei != oe_end; ++oei) { 00525 unsigned int pairCost; 00526 int pairTotalEdgecountChange, pairNontrivialEdgecountChange; 00527 assessPairElim(e, 00528 *oei, 00529 theAngelLCG, 00530 ourAwarenessLevel, 00531 pairCost, 00532 pairTotalEdgecountChange, 00533 pairNontrivialEdgecountChange); 00534 cost += pairCost; 00535 totalEdgecountChange += pairTotalEdgecountChange; 00536 nontrivialEdgecountChange += pairNontrivialEdgecountChange; 00537 // determine effect of isolation 00538 if (isIsolated) { 00539 totalEdgecountChange -= 1; 00540 if (!isTrivialEdge(*oei,theAngelLCG,ourAwarenessLevel)) 00541 nontrivialEdgecountChange -= 1; 00542 } // end if isIsolated 00543 } // end for all outedges of the target 00544 } // end assessFrontEdgeElim() 00545 00546 void assessBackEdgeElim(const c_graph_t::edge_t& e, 00547 c_graph_t& theAngelLCG, 00548 const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 00549 unsigned int& cost, 00550 int& totalEdgecountChange, 00551 int& nontrivialEdgecountChange) { 00552 boost::property_map<c_graph_t,EdgeType>::type eType = get(EdgeType(),theAngelLCG); 00553 bool isIsolated = (out_degree(source(e,theAngelLCG),theAngelLCG) == 1 00554 && vertex_type(source(e,theAngelLCG),theAngelLCG) != dependent); 00555 c_graph_t::iei_t iei, ie_end; 00556 for (tie(iei,ie_end) = in_edges(source(e,theAngelLCG),theAngelLCG); iei != ie_end; ++iei) { 00557 unsigned int pairCost; 00558 int pairTotalEdgecountChange, pairNontrivialEdgecountChange; 00559 assessPairElim(*iei, 00560 e, 00561 theAngelLCG, 00562 ourAwarenessLevel, 00563 pairCost, 00564 pairTotalEdgecountChange, 00565 pairNontrivialEdgecountChange); 00566 cost += pairCost; 00567 totalEdgecountChange += pairTotalEdgecountChange; 00568 nontrivialEdgecountChange += pairNontrivialEdgecountChange; 00569 // determine effect of isolation 00570 if (isIsolated) { 00571 totalEdgecountChange -= 1; 00572 if (!isTrivialEdge(*iei,theAngelLCG,ourAwarenessLevel)) 00573 nontrivialEdgecountChange -= 1; 00574 } // end if isIsolated 00575 } // end for all inedges of the source 00576 } // end assessBackEdgeElim() 00577 00578 void assessEdgeElim(const EdgeElim& anEdgeElim, 00579 c_graph_t& theAngelLCG, 00580 const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 00581 unsigned int& cost, 00582 int& totalEdgecountChange, 00583 int& nontrivialEdgecountChange) { 00584 cost = 0; 00585 // determine the effect of removing e 00586 totalEdgecountChange = -1; 00587 nontrivialEdgecountChange = isTrivialEdge(anEdgeElim.getE(theAngelLCG),theAngelLCG,ourAwarenessLevel) ? 0 : -1; 00588 if (anEdgeElim.isFront()) 00589 assessFrontEdgeElim(anEdgeElim.getE(theAngelLCG), 00590 theAngelLCG, 00591 ourAwarenessLevel, 00592 cost, 00593 totalEdgecountChange, 00594 nontrivialEdgecountChange); 00595 else 00596 assessBackEdgeElim(anEdgeElim.getE(theAngelLCG), 00597 theAngelLCG, 00598 ourAwarenessLevel, 00599 cost, 00600 totalEdgecountChange, 00601 nontrivialEdgecountChange); 00602 } // end assessEdgeElim() 00603 00604 void postProcessRemainderGraph(c_graph_t& theAngelLCG, 00605 xaifBoosterCrossCountryInterface::JacobianAccumulationExpressionList& theJAEList, 00606 std::list<EdgeRef_t>& edge_ref_list, 00607 const xaifBoosterCrossCountryInterface::AwarenessLevel::AwarenessLevel_E ourAwarenessLevel) { 00608 vector<EdgeElim> allEdgeElimsV; 00609 bool done = false; 00610 while (!done) { 00611 done = true; 00612 eliminatable_edges(theAngelLCG,allEdgeElimsV); 00613 if (allEdgeElimsV.empty()) break; // no more eliminatable edges 00614 for (size_t c = 0; c < allEdgeElimsV.size(); c++) { 00615 unsigned int cost; 00616 int totalEdgecountChange, nontrivialEdgecountChange; 00617 assessEdgeElim(allEdgeElimsV[c], 00618 theAngelLCG, 00619 ourAwarenessLevel, 00620 cost, 00621 totalEdgecountChange, 00622 nontrivialEdgecountChange); 00623 // THROW_EXCEPT_MACRO(nontrivialEdgecountChange < 0,consistency_exception,"postProcessRemainderGraph: found reduction in nontrivial edge count in remainder graph produced by scarcity heuristic"); 00624 // we require the following 00625 // (1) no computational cost 00626 // (2) some reduction in total edge count 00627 // (3) no change in nontrivial edge count (\todo in the future we will allow decreases, though they shouldn't occur at this point) 00628 if (cost == 0 00629 && totalEdgecountChange < 0 00630 && nontrivialEdgecountChange == 0) { 00631 #ifndef NDEBUG 00632 std::cout << "+++++++++++++++++ GREEDY REDUCTION FOUND: cost=" << cost 00633 << ", totalEdgecountChange=" << totalEdgecountChange 00634 << ", nontrivialEdgecountChange=" << nontrivialEdgecountChange << "+++++++++++++++++++++++" << std::endl; 00635 #endif 00636 unsigned int actualCost = allEdgeElimsV[c].isFront() 00637 ? front_eliminate_edge_directly(allEdgeElimsV[c].getE(theAngelLCG), 00638 theAngelLCG, 00639 edge_ref_list, 00640 theJAEList) 00641 : back_eliminate_edge_directly(allEdgeElimsV[c].getE(theAngelLCG), 00642 theAngelLCG, 00643 edge_ref_list, 00644 theJAEList); 00645 THROW_EXCEPT_MACRO(cost != actualCost,consistency_exception,"postProcessRemainderGraph: discrepancy in cost between assessEdgeElim and eliminate_edge_directly"); 00646 00647 allEdgeElimsV.clear(); 00648 done = false; 00649 break; 00650 } 00651 } // end for all edge elims 00652 } // end while 00653 } // end postProcessRemainderGraph() 00654 00655 } // end namespace angel 00656 00657 00658 00659 using namespace angel; 00660 00661 namespace xaifBoosterCrossCountryInterface { 00662 void compute_partial_elimination_sequence_random(const LinearizedComputationalGraph& ourLCG, 00663 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 00664 const bool allowMaintainingFlag, 00665 JacobianAccumulationExpressionList& jae_list, 00666 LinearizedComputationalGraph& remainderLCG, 00667 VertexCorrelationList& v_cor_list, 00668 EdgeCorrelationList& e_cor_list) { 00669 srand(time(NULL)); 00670 // Create internal (angel) LCG from xaifBooster LCG 00671 vector<const LinearizedComputationalGraphVertex*> ourLCG_verts; 00672 c_graph_t angelLCG; 00673 list<EdgeRef_t> edge_ref_list; 00674 ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG, edge_ref_list); 00675 00676 unsigned int max_steps = 50 * num_vertices(angelLCG); 00677 unsigned int num_passes = 5; 00678 00679 c_graph_t angelLCG_copy (angelLCG); 00680 elimSeq_cost_t dummy_elimSeq_cost (0, 0, 0, 0, 0, 0); 00681 transformationSeq_cost_t dummy_tSeqCost (0, 0, 0, 0, 0, 0); 00682 refillDependenceMap_t dummy_refillDependenceMap; 00683 vector<EdgeElim> allEdgeElimsV; 00684 vector<Transformation> edgeElimSeqV, best_edgeElimSeqV; 00685 unsigned int previous_numNontrivialEdges = num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel); 00686 unsigned int bestNumNontrivialEdges = num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel); 00687 unsigned int computationalCost_at_bestEdgeCount = 0; 00688 unsigned int computationalCost = 0; 00689 #ifndef NDEBUG 00690 cout << "datapoint:" << computationalCost << ":" << num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel) << endl; 00691 #endif 00692 for (unsigned int steps_counter = 0; steps_counter < max_steps; steps_counter++) { 00693 // Start over from the beginning 00694 if (steps_counter%(max_steps/num_passes) == 0) { 00695 #ifndef NDEBUG 00696 cout << "Starting a new SA pass (" << steps_counter << "/" << max_steps << " steps):\tbestNumNontrivialEdges = " << bestNumNontrivialEdges << ", computationalCost_at_bestEdgeCount = " << computationalCost_at_bestEdgeCount << endl; 00697 #endif 00698 edgeElimSeqV.clear(); 00699 computationalCost = 0; 00700 previous_numNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel); 00701 angelLCG_copy = angelLCG; 00702 continue; 00703 } 00704 00705 eliminatable_edges(angelLCG_copy, allEdgeElimsV); 00706 if (allEdgeElimsV.empty()) break; // no more eliminatable edges 00707 00708 // calculate relative probabilities for each possible edge elim 00709 vector<double> deltaE(allEdgeElimsV.size() + 1); 00710 for (size_t c = 0; c < allEdgeElimsV.size(); c++) 00711 deltaE[c] = edge_elim_effect (allEdgeElimsV[c], angelLCG_copy, ourAwarenessLevel); 00712 deltaE[allEdgeElimsV.size()] = (int)previous_numNontrivialEdges - (int)num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel); 00713 00714 unsigned int choice_index = chooseTarget_sa(deltaE); 00715 if (choice_index != allEdgeElimsV.size()) { // eliminate an edge 00716 previous_numNontrivialEdges = num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel); 00717 computationalCost += allEdgeElimsV[choice_index].isFront() ? 00718 front_elim(allEdgeElimsV[choice_index].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap) 00719 : back_elim(allEdgeElimsV[choice_index].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap); 00720 edgeElimSeqV.push_back(Transformation (allEdgeElimsV[choice_index])); 00721 // check whether we've beaten our CURRENT best 00722 if (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel) < bestNumNontrivialEdges 00723 || (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel) == bestNumNontrivialEdges && computationalCost < computationalCost_at_bestEdgeCount)) { 00724 bestNumNontrivialEdges = num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel); 00725 computationalCost_at_bestEdgeCount = computationalCost; 00726 best_edgeElimSeqV = edgeElimSeqV; 00727 #ifndef NDEBUG 00728 cout << "** New bestNumNontrivialEdges: " << bestNumNontrivialEdges << " with computational cost " << computationalCost << " after " << edgeElimSeqV.size() << " eliminations" << endl; 00729 #endif 00730 } 00731 } 00732 else { // this corresponds to a backtracking (going back cannot lead to a new "best-so-far" result) 00733 #ifndef NDEBUG 00734 cout << "Performing a BACKTRACKING step" << endl; 00735 #endif 00736 if (edgeElimSeqV.empty()) 00737 continue; 00738 angelLCG_copy = angelLCG; 00739 edgeElimSeqV.pop_back(); 00740 computationalCost = replay_transformation_seq(angelLCG_copy, edgeElimSeqV, previous_numNontrivialEdges, ourAwarenessLevel, dummy_tSeqCost, dummy_refillDependenceMap); 00741 } 00742 #ifndef NDEBUG 00743 cout << "datapoint:" << computationalCost << ":" << num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel) << endl; 00744 #endif 00745 } // end of elimination sequence 00746 00747 #ifndef NDEBUG 00748 // Really, we output the number of intermediates with no incident unit edge (can be normalized) 00749 cout << "Achieved a nontrivial edge count of " << bestNumNontrivialEdges << " with the following sequence of edge eliminations:"; 00750 for (size_t c = 0; c < best_edgeElimSeqV.size(); c++) 00751 cout << endl << best_edgeElimSeqV[c].debug().c_str(); 00752 cout << endl << endl << "****** Now re-performing best_edgeElimSeqV until we reach our edge goal of " << bestNumNontrivialEdges << " nontrivial edges" << endl; 00753 #endif 00754 00755 // Now replay the elimination sequence until we reach edge count goal. 00756 // Additionally, we perform a greedy reduction of the resulting remainder graph, 00757 // which may lead to more concise propagation code. 00758 unsigned int cost_of_elim_seq = 0; 00759 if (best_edgeElimSeqV.empty() || 00760 num_nontrivial_edges(angelLCG, ourAwarenessLevel) == bestNumNontrivialEdges) { 00761 #ifndef NDEBUG 00762 cout << "No eliminations necessary to reach the desired edge count of " << bestNumNontrivialEdges << endl; 00763 #endif 00764 } 00765 else { //replay the elimination sequence until we reach edge count goal 00766 for (size_t c = 0; c < best_edgeElimSeqV.size(); c++) { 00767 cost_of_elim_seq += best_edgeElimSeqV[c].getEdgeElim().isFront() ? 00768 front_eliminate_edge_directly(best_edgeElimSeqV[c].getEdgeElim().getE(angelLCG), angelLCG, edge_ref_list, jae_list) 00769 : back_eliminate_edge_directly(best_edgeElimSeqV[c].getEdgeElim().getE(angelLCG), angelLCG, edge_ref_list, jae_list); 00770 if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) == bestNumNontrivialEdges) { 00771 #ifndef NDEBUG 00772 cout << "Goal of " << bestNumNontrivialEdges << " reached at a computational cost of " << cost_of_elim_seq << " nontrivial scalar multiplications" << endl; 00773 #endif 00774 break; 00775 } 00776 } 00777 } 00778 // we may want to perform additional no-cost eliminations that don't lead to an increase in nontrivial edges 00779 #ifndef NDEBUG 00780 cout << "Now greedily reducing the remainder graph..." << endl; 00781 #endif 00782 postProcessRemainderGraph(angelLCG, 00783 jae_list, 00784 edge_ref_list, 00785 ourAwarenessLevel); 00786 00787 #ifndef NDEBUG 00788 write_graph ("angelLCG after partial edge elimination sequence (G prime): ", angelLCG); 00789 writeVertexAndEdgeTypes (cout, angelLCG); 00790 cout << "Cost of partial edge elimination sequence: " << cost_of_elim_seq << endl; 00791 #endif 00792 populate_remainderGraph_and_correlationLists (angelLCG, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list); 00793 } // end xaifBoosterCrossCountryInterface::compute_partial_elimination_sequence_random() 00794 00795 void compute_partial_elimination_sequence (const LinearizedComputationalGraph& ourLCG, 00796 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 00797 const bool allowMaintainingFlag, 00798 JacobianAccumulationExpressionList& jae_list, 00799 LinearizedComputationalGraph& remainderLCG, 00800 VertexCorrelationList& v_cor_list, 00801 EdgeCorrelationList& e_cor_list) { 00802 // Create internal (angel) LCG from xaifBooster LCG 00803 vector<const LinearizedComputationalGraphVertex*> ourLCG_verts; 00804 c_graph_t angelLCG; 00805 list<EdgeRef_t> edge_ref_list; 00806 ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG, edge_ref_list); 00807 00808 #ifndef NDEBUG 00809 cout << endl << "****** Performing total elim sequences and building up refill dependence information..." << endl; 00810 #endif 00811 00812 // To begin with, the best elimination sequence is NO elimination sequence 00813 elimSeq_cost_t *bestEliminationSequence = new elimSeq_cost_t (num_nontrivial_edges(angelLCG, ourAwarenessLevel), // bestNumNontrivialEdges 00814 0, // cost 00815 0, // costAtBestEdgecount 00816 numIntermediateVertices(angelLCG), // numIntermediatesAtBestEdgecount 00817 numIntermediateVerticesWithoutUnitEdge(angelLCG), // numIntermediatesWithoutUnitEdgeAtBestEdgecount 00818 0); // lastDesiredElim 00819 elimSeq_cost_t *currentEliminationSequence; 00820 00821 // while I eliminate, build up list of refill dependences. This is STATIC, because I store the vertex dependences 00822 refillDependenceMap_t refillDependences; 00823 vector<EdgeElim> eeV1, eeV2, eeV3, eeV4, eeV5; 00824 00825 unsigned int seqNum = 0; 00826 while (true) { 00827 c_graph_t angelLCG_copy (angelLCG); 00828 currentEliminationSequence = new elimSeq_cost_t (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel), // bestNumNontrivialEdges 00829 0, // cost 00830 0, // costAtBestEdgecount 00831 numIntermediateVertices(angelLCG_copy), // numIntermediatesAtBestEdgecount 00832 numIntermediateVerticesWithoutUnitEdge(angelLCG), // numIntermediatesWithoutUnitEdgeAtBestEdgecount 00833 0); // lastDesiredElim 00834 #ifndef NDEBUG 00835 cout << "++++++++++++++++++++++++" << "TRYING A NEW COMPLETE ELIMINATION SEQUENCE" << "++++++++++++++++++++++++" << endl; 00836 #endif 00837 00838 // perform a complete elimination sequence that preserves scarcity and tries to avoid refill 00839 unsigned int elimNum = 0; 00840 while(true) { 00841 #ifndef NDEBUG 00842 write_graph("angelLCG_copy: ", angelLCG_copy); 00843 cout << "datapoint:" << seqNum << ":" << elimNum << ":" << num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel) << endl; 00844 #endif 00845 00846 // run through the heuristics pipeline 00847 eliminatable_edges(angelLCG_copy, eeV1); 00848 if (eeV1.empty()) 00849 break; // no more eliminatable edges 00850 00851 if (reducing_edge_eliminations(eeV1, angelLCG_copy, ourAwarenessLevel, eeV2) == 0 && allowMaintainingFlag) 00852 maintaining_edge_eliminations(eeV1, angelLCG_copy, ourAwarenessLevel, eeV2); 00853 00854 if (!eeV2.empty()) 00855 refill_avoiding_edge_eliminations(eeV2, angelLCG_copy, refillDependences, eeV3); 00856 else 00857 refill_avoiding_edge_eliminations(eeV1, angelLCG_copy, refillDependences, eeV3); 00858 00859 if (!eeV3.empty()) // there are some refill avoiding elims 00860 lowestMarkowitzEdgeElim(eeV3, angelLCG_copy, eeV4); 00861 else if (!eeV2.empty()) // there are no refill avoiding elims, but there are scarcity-preserving elims 00862 lowestMarkowitzEdgeElim(eeV2, angelLCG_copy, eeV4); 00863 else // there are no refill avoiding elims, and no scarcity-preserving elims 00864 lowestMarkowitzEdgeElim(eeV1, angelLCG_copy, eeV4); 00865 00866 reverseModeEdgeElim(eeV4, angelLCG_copy, eeV5); 00867 00868 EdgeElim thisEdgeElim (eeV5[0]); 00869 currentEliminationSequence->edgeElimVector.push_back(thisEdgeElim); 00870 currentEliminationSequence->cost += thisEdgeElim.isFront() ? 00871 front_elim (thisEdgeElim.getE(angelLCG_copy), angelLCG_copy, *currentEliminationSequence, refillDependences) 00872 : back_elim (thisEdgeElim.getE(angelLCG_copy), angelLCG_copy, *currentEliminationSequence, refillDependences); 00873 00874 // check whether we've beaten our CURRENT best 00875 if (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel) < currentEliminationSequence->bestNumNontrivialEdges) { 00876 currentEliminationSequence->bestNumNontrivialEdges = num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel); 00877 currentEliminationSequence->costAtBestEdgecount = currentEliminationSequence->cost; 00878 currentEliminationSequence->numIntermediatesAtBestEdgecount = numIntermediateVertices(angelLCG_copy); 00879 currentEliminationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount = numIntermediateVerticesWithoutUnitEdge(angelLCG_copy); 00880 currentEliminationSequence->lastDesiredElim = currentEliminationSequence->edgeElimVector.size(); 00881 #ifndef NDEBUG 00882 cout << "** new best_num_edges for currentElimSeq: " << currentEliminationSequence->bestNumNontrivialEdges << endl; 00883 #endif 00884 } 00885 00886 #ifndef NDEBUG 00887 write_refillDependences (cout, refillDependences); 00888 #endif 00889 00890 elimNum++; 00891 } // end of elimination sequence 00892 bool finished = !currentEliminationSequence->revealedNewDependence; 00893 00894 #ifndef NDEBUG 00895 cout << "complete elim sequence complete. This sequence achieved " << currentEliminationSequence->bestNumNontrivialEdges << " edges and "; 00896 if (currentEliminationSequence->revealedNewDependence) cout << "DID"; else cout << "DID NOT"; 00897 cout << " add new dependence information to the dependence map" << endl; 00898 #endif 00899 00900 // check whether we've beaten our OVERALL best, or MATCHED it with lower cost 00901 if (currentEliminationSequence->bestNumNontrivialEdges < bestEliminationSequence->bestNumNontrivialEdges 00902 || (currentEliminationSequence->bestNumNontrivialEdges == bestEliminationSequence->bestNumNontrivialEdges 00903 && currentEliminationSequence->costAtBestEdgecount < bestEliminationSequence->costAtBestEdgecount)) { 00904 delete bestEliminationSequence; 00905 bestEliminationSequence = currentEliminationSequence; 00906 currentEliminationSequence = NULL; 00907 #ifndef NDEBUG 00908 cout << "This elimination sequence is best so far" << endl; 00909 #endif 00910 } 00911 else { // latest elimination sequence isn't an improvement 00912 #ifndef NDEBUG 00913 cout << "This elimination sequence isn't an improvement" << endl; 00914 #endif 00915 delete currentEliminationSequence; 00916 } 00917 00918 if (finished) break; 00919 seqNum++; 00920 } // end determine best elimination sequence 00921 00922 #ifndef NDEBUG 00923 // Really, we output the number of intermediates with no incident unit edge (can be normalized) 00924 cout << "The best partial edge elimination sequence achieves a nontrivial edge count of " << bestEliminationSequence->bestNumNontrivialEdges 00925 << ", at which point there are " << bestEliminationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount << " intermediate vertices with no incident unit edge" << endl; 00926 cout << "The best partial edge elimination sequence is: " << endl; 00927 for (size_t i = 0; i < bestEliminationSequence->edgeElimVector.size(); i++) 00928 cout << bestEliminationSequence->edgeElimVector[i].debug().c_str(); 00929 cout << endl << endl << "****** Now re-performing bestElimSeqFound until we reach our edge goal of " << bestEliminationSequence->bestNumNontrivialEdges << " nontrivial edges" << endl; 00930 #endif 00931 00932 if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) > bestEliminationSequence->bestNumNontrivialEdges) { 00933 for (size_t c = 0; c < bestEliminationSequence->edgeElimVector.size(); c++) { 00934 bestEliminationSequence->edgeElimVector[c].isFront() ? 00935 front_eliminate_edge_directly (bestEliminationSequence->edgeElimVector[c].getE(angelLCG), angelLCG, edge_ref_list, jae_list) 00936 : back_eliminate_edge_directly (bestEliminationSequence->edgeElimVector[c].getE(angelLCG), angelLCG, edge_ref_list, jae_list); 00937 if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) == bestEliminationSequence->bestNumNontrivialEdges) 00938 break; 00939 } // end iterate over bestEliminationSequence->edgeElimVector 00940 } 00941 #ifndef NDEBUG 00942 else 00943 cout << "No eliminations necessary to reach the desired edge count of " << bestEliminationSequence->bestNumNontrivialEdges << endl; 00944 00945 write_graph ("angelLCG after partial edge elimination sequence (G prime): ", angelLCG); 00946 writeVertexAndEdgeTypes (cout, angelLCG); 00947 #endif 00948 00949 delete bestEliminationSequence; 00950 00951 // we may want to perform additional no-cost eliminations that don't lead to an increase in nontrivial edges 00952 #ifndef NDEBUG 00953 cout << "Now greedily reducing the remainder graph..." << endl; 00954 #endif 00955 postProcessRemainderGraph(angelLCG, 00956 jae_list, 00957 edge_ref_list, 00958 ourAwarenessLevel); 00959 00960 populate_remainderGraph_and_correlationLists (angelLCG, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list); 00961 } // end xaifBoosterCrossCountryInterface::compute_partial_elimination_sequence() 00962 00963 void compute_partial_transformation_sequence_random(const LinearizedComputationalGraph& ourLCG, 00964 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 00965 const bool allowMaintainingFlag, 00966 JacobianAccumulationExpressionList& jae_list, 00967 LinearizedComputationalGraph& remainderLCG, 00968 VertexCorrelationList& v_cor_list, 00969 EdgeCorrelationList& e_cor_list, 00970 unsigned int& numReroutings) { 00971 srand(time(NULL)); 00972 00973 // Create internal (angel) LCG from xaifBooster LCG 00974 vector<const LinearizedComputationalGraphVertex*> ourLCG_verts; 00975 c_graph_t angelLCG_orig; 00976 list<EdgeRef_t> edge_ref_list; 00977 ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG_orig, edge_ref_list); 00978 00979 unsigned int max_steps = 20 * num_vertices(angelLCG_orig); 00980 unsigned int num_passes = 5; 00981 00982 transformationSeq_cost_t dummy_transformationSeq_cost (0, 0, 0, 0, 0, 0); 00983 refillDependenceMap_t dummy_refillDependenceMap; 00984 vector<Transformation> allViableTransformationsV, transformationSeqV, best_transformationSeqV; 00985 c_graph_t angelLCG (angelLCG_orig); 00986 unsigned int previous_numNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel); 00987 unsigned int bestNumNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel); 00988 unsigned int computationalCost_at_bestEdgeCount = 0; 00989 unsigned int computationalCost = 0; 00990 for (unsigned int steps_counter = 0; steps_counter < max_steps; steps_counter++) { 00991 #ifndef NDEBUG 00992 cout << "datapoint:" << computationalCost << ":" << num_nontrivial_edges(angelLCG, ourAwarenessLevel) << endl; 00993 #endif 00994 00995 // Start over from the beginning 00996 if (steps_counter%(max_steps/num_passes) == 0) { 00997 #ifndef NDEBUG 00998 cout << "Starting a new SA pass (" << steps_counter << "/" << max_steps << " steps):\tbestNumNontrivialEdges = " << bestNumNontrivialEdges << ", computationalCost_at_bestEdgeCount = " << computationalCost_at_bestEdgeCount << endl; 00999 #endif 01000 transformationSeqV.clear(); 01001 computationalCost = 0; 01002 previous_numNontrivialEdges = num_nontrivial_edges(angelLCG_orig, ourAwarenessLevel); 01003 angelLCG = angelLCG_orig; 01004 continue; 01005 } 01006 01007 // assess the effect of each viable transformation 01008 all_viable_transformations(angelLCG, transformationSeqV, allViableTransformationsV); 01009 if (allViableTransformationsV.empty()) 01010 break; 01011 vector<double> deltaE(allViableTransformationsV.size() + 1); 01012 for (size_t c = 0; c < allViableTransformationsV.size(); c++) 01013 deltaE[c] = transformation_effect(allViableTransformationsV[c], angelLCG, ourAwarenessLevel); 01014 // calculate probability for going backwards one step 01015 deltaE[allViableTransformationsV.size()] = (int)previous_numNontrivialEdges - (int)num_nontrivial_edges(angelLCG, ourAwarenessLevel); 01016 01017 unsigned int choice_index = chooseTarget_sa(deltaE); 01018 if (choice_index != allViableTransformationsV.size()) { // perform a transformation 01019 previous_numNontrivialEdges = num_nontrivial_edges(angelLCG, ourAwarenessLevel); 01020 transformationSeqV.push_back(allViableTransformationsV[choice_index]); 01021 // REROUTING 01022 if (allViableTransformationsV[choice_index].isRerouting()) { 01023 computationalCost += allViableTransformationsV[choice_index].getRerouting().isPre() ? 01024 prerouteEdge_noJAE(allViableTransformationsV[choice_index].getRerouting().getER(angelLCG), angelLCG) 01025 : postrouteEdge_noJAE(allViableTransformationsV[choice_index].getRerouting().getER(angelLCG), angelLCG); 01026 } 01027 // EDGE ELIM 01028 else { 01029 computationalCost += allViableTransformationsV[choice_index].getEdgeElim().isFront() ? 01030 frontEdgeElimination_noJAE(allViableTransformationsV[choice_index].getEdgeElim().getE(angelLCG), angelLCG, &dummy_transformationSeq_cost, dummy_refillDependenceMap) 01031 : backEdgeElimination_noJAE(allViableTransformationsV[choice_index].getEdgeElim().getE(angelLCG), angelLCG, &dummy_transformationSeq_cost, dummy_refillDependenceMap); 01032 } // end edge elim 01033 01034 // check whether we've beaten our CURRENT best 01035 if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) < bestNumNontrivialEdges 01036 || (num_nontrivial_edges (angelLCG, ourAwarenessLevel) == bestNumNontrivialEdges && computationalCost < computationalCost_at_bestEdgeCount)) { 01037 bestNumNontrivialEdges = num_nontrivial_edges (angelLCG, ourAwarenessLevel); 01038 computationalCost_at_bestEdgeCount = computationalCost; 01039 best_transformationSeqV = transformationSeqV; 01040 #ifndef NDEBUG 01041 cout << "** New best_num_edges found: " << bestNumNontrivialEdges 01042 << " with computational cost " << computationalCost 01043 << " after " << transformationSeqV.size() << " transformations" << endl; 01044 #endif 01045 } 01046 } // end perform a transformation 01047 else { // this corresponds to a backtracking (NOTE: going back cannot lead to a new "best-so-far" result) 01048 #ifndef NDEBUG 01049 cout << "Performing a BACKTRACKING step" << endl; 01050 #endif 01051 if (transformationSeqV.empty()) 01052 continue; 01053 angelLCG = angelLCG_orig; 01054 transformationSeqV.pop_back(); 01055 computationalCost = replay_transformation_seq(angelLCG, transformationSeqV, previous_numNontrivialEdges, ourAwarenessLevel, dummy_transformationSeq_cost, dummy_refillDependenceMap); 01056 } // end backtracking 01057 } 01058 01059 #ifndef NDEBUG 01060 cout << "Achieved a nontrivial edge count of " << bestNumNontrivialEdges << endl; 01061 cout << "Best sequence of transformations: " << endl; 01062 for (size_t c = 0; c < best_transformationSeqV.size(); c++) 01063 cout << best_transformationSeqV[c].debug().c_str() << endl; 01064 cout << endl << endl << "****** Now re-performing best_transformationSeqV until we reach our edge goal of " << bestNumNontrivialEdges << " nontrivial edges" << endl; 01065 #endif 01066 01067 //replay the elimination sequence until we reach edge count goal 01068 numReroutings = 0; 01069 if (num_nontrivial_edges (angelLCG_orig, ourAwarenessLevel) > bestNumNontrivialEdges) { 01070 for (size_t c = 0; c < best_transformationSeqV.size(); c++) { 01071 if (best_transformationSeqV[c].isRerouting()) { // REROUTING 01072 numReroutings++; 01073 best_transformationSeqV[c].getRerouting().isPre() ? 01074 preroute_edge_directly(best_transformationSeqV[c].getRerouting().getER(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list) 01075 : postroute_edge_directly(best_transformationSeqV[c].getRerouting().getER(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list); 01076 } 01077 else { // EDGE ELIMINATION 01078 best_transformationSeqV[c].getEdgeElim().isFront() ? 01079 front_eliminate_edge_directly(best_transformationSeqV[c].getEdgeElim().getE(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list) 01080 : back_eliminate_edge_directly(best_transformationSeqV[c].getEdgeElim().getE(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list); 01081 } 01082 if (num_nontrivial_edges (angelLCG_orig, ourAwarenessLevel) == bestNumNontrivialEdges) { 01083 #ifndef NDEBUG 01084 cout << "Goal of " << bestNumNontrivialEdges << " reached" << endl; 01085 #endif 01086 break; 01087 } 01088 } 01089 } 01090 #ifndef NDEBUG 01091 else 01092 cout << "No eliminations necessary to reach the desired edge count of " << bestNumNontrivialEdges << endl; 01093 #endif 01094 01095 #ifndef NDEBUG 01096 write_graph ("angelLCG after partial transformation sequence (G prime): ", angelLCG_orig); 01097 writeVertexAndEdgeTypes (cout, angelLCG_orig); 01098 #endif 01099 populate_remainderGraph_and_correlationLists (angelLCG_orig, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list); 01100 } // end xaifBoosterCrossCountryInterface::compute_partial_transformation_sequence_random() 01101 01102 void compute_partial_transformation_sequence (const LinearizedComputationalGraph& ourLCG, 01103 const AwarenessLevel::AwarenessLevel_E ourAwarenessLevel, 01104 const bool allowMaintainingFlag, 01105 JacobianAccumulationExpressionList& jae_list, 01106 LinearizedComputationalGraph& remainderLCG, 01107 VertexCorrelationList& v_cor_list, 01108 EdgeCorrelationList& e_cor_list, 01109 unsigned int& numReroutings) { 01110 // Create internal (angel) LCG from xaifBooster LCG 01111 vector<const LinearizedComputationalGraphVertex*> ourLCG_verts; 01112 c_graph_t angelLCG; 01113 list<EdgeRef_t> edge_ref_list; 01114 ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG, edge_ref_list); 01115 01116 #ifndef NDEBUG 01117 cout << "Determining a partial sequence of transformations..." << endl; 01118 #endif 01119 01120 // To begin with, the best transformation sequence is NO transformation sequence 01121 transformationSeq_cost_t *bestTransformationSequence = new transformationSeq_cost_t (num_nontrivial_edges(angelLCG, ourAwarenessLevel), 01122 0, 01123 0, 01124 numIntermediateVertices(angelLCG), 01125 numIntermediateVerticesWithoutUnitEdge(angelLCG), 01126 0); 01127 transformationSeq_cost_t *currentTransformationSequence; 01128 01129 refillDependenceMap_t refillDependences; 01130 vector<Transformation> allViableTransformationsV, 01131 maintainingTransformationsV, 01132 reducingTransformationsV, 01133 reroutingConsiderateTransformationsV, 01134 refillAvoidingTransformationsV, 01135 lowestMarkowitzTransformationsV, 01136 reverseModeTransformationsV; 01137 01138 // determine a best transformation sequence 01139 unsigned int seqNum = 0; 01140 while (true) { 01141 c_graph_t angelLCG_copy (angelLCG); 01142 currentTransformationSequence = new transformationSeq_cost_t (num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel), 01143 0, 01144 0, 01145 numIntermediateVertices(angelLCG_copy), 01146 numIntermediateVerticesWithoutUnitEdge(angelLCG), 01147 0); 01148 01149 #ifndef NDEBUG 01150 cout << "++++++++++++++++++++++++" << endl << "TRYING A NEW COMPLETE TRANSFORMATION SEQUENCE" << "++++++++++++++++++++++++" << endl; 01151 #endif 01152 01153 // run currentTransformationSequence 01154 unsigned int elimNum = 0; 01155 while (true) { 01156 #ifndef NDEBUG 01157 cout << "datapoint:" << seqNum << ":" << elimNum << ":" << num_nontrivial_edges(angelLCG_copy, ourAwarenessLevel) << endl; 01158 #endif 01159 01160 // run filters 01161 if (!all_viable_transformations (angelLCG_copy, currentTransformationSequence->transformationVector, allViableTransformationsV)) 01162 break; 01163 maintaining_transformations (allViableTransformationsV, angelLCG_copy, ourAwarenessLevel, maintainingTransformationsV); 01164 reducing_transformations (maintainingTransformationsV, angelLCG_copy, ourAwarenessLevel, reducingTransformationsV); 01165 rerouting_considerate_transformations (reducingTransformationsV, angelLCG_copy, currentTransformationSequence->transformationVector, reroutingConsiderateTransformationsV); 01166 refill_avoiding_transformations (reroutingConsiderateTransformationsV, angelLCG_copy, ourAwarenessLevel, refillDependences, refillAvoidingTransformationsV); 01167 lowest_markowitz_transformations (refillAvoidingTransformationsV, angelLCG_copy, lowestMarkowitzTransformationsV); 01168 reverse_mode_transformations (lowestMarkowitzTransformationsV, angelLCG_copy, reverseModeTransformationsV); 01169 01170 Transformation chosenTransformation (reverseModeTransformationsV[0]); 01171 currentTransformationSequence->transformationVector.push_back(chosenTransformation); 01172 01173 if (chosenTransformation.isRerouting()) 01174 currentTransformationSequence->cost += chosenTransformation.getRerouting().isPre() ? 01175 prerouteEdge_noJAE(chosenTransformation.getRerouting().getER(angelLCG_copy), angelLCG_copy) 01176 : postrouteEdge_noJAE(chosenTransformation.getRerouting().getER(angelLCG_copy), angelLCG_copy); 01177 else 01178 currentTransformationSequence->cost += chosenTransformation.getEdgeElim().isFront() ? 01179 frontEdgeElimination_noJAE(chosenTransformation.getEdgeElim().getE(angelLCG_copy), angelLCG_copy, currentTransformationSequence, refillDependences) 01180 : backEdgeElimination_noJAE(chosenTransformation.getEdgeElim().getE(angelLCG_copy), angelLCG_copy, currentTransformationSequence, refillDependences); 01181 01182 // check whether we've beaten our CURRENT best 01183 if (num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel) < currentTransformationSequence->bestNumNontrivialEdges) { 01184 currentTransformationSequence->bestNumNontrivialEdges = num_nontrivial_edges (angelLCG_copy, ourAwarenessLevel); 01185 currentTransformationSequence->costAtBestEdgecount = currentTransformationSequence->cost; 01186 currentTransformationSequence->numIntermediatesAtBestEdgecount = numIntermediateVertices(angelLCG_copy); 01187 currentTransformationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount = numIntermediateVerticesWithoutUnitEdge(angelLCG_copy); 01188 currentTransformationSequence->lastDesiredTransformation = currentTransformationSequence->transformationVector.size(); 01189 #ifndef NDEBUG 01190 cout << "** new currentTransformationSequence->bestNumNontrivialEdges: " << currentTransformationSequence->bestNumNontrivialEdges << endl; 01191 #endif 01192 } 01193 01194 elimNum++; 01195 } // end of transformation sequence 01196 01197 bool notFinishedYet = currentTransformationSequence->revealedNewDependence; 01198 01199 #ifndef NDEBUG 01200 cout << "complete elim sequence complete. This sequence achieved " << currentTransformationSequence->bestNumNontrivialEdges << " edges and "; 01201 if (currentTransformationSequence->revealedNewDependence) cout << "DID"; else cout << "DID NOT"; 01202 cout << " add new dependence information to the dependence map" << endl; 01203 write_refillDependences (cout, refillDependences); 01204 #endif 01205 01206 // check whether we've beaten our OVERALL best, or MATCHED it with lower cost 01207 if (currentTransformationSequence->bestNumNontrivialEdges < bestTransformationSequence->bestNumNontrivialEdges 01208 || (currentTransformationSequence->bestNumNontrivialEdges == bestTransformationSequence->bestNumNontrivialEdges 01209 && currentTransformationSequence->costAtBestEdgecount < bestTransformationSequence->costAtBestEdgecount)) { 01210 delete bestTransformationSequence; 01211 bestTransformationSequence = currentTransformationSequence; 01212 currentTransformationSequence = NULL; 01213 #ifndef NDEBUG 01214 cout << "This transformation sequence is best so far" << endl; 01215 #endif 01216 } 01217 else { // latest transformation sequence isn't an improvement 01218 #ifndef NDEBUG 01219 cout << "This transformation isn't an improvement" << endl; 01220 #endif 01221 delete currentTransformationSequence; 01222 } 01223 01224 // determine whether it's time to stop 01225 if (!notFinishedYet) break; 01226 01227 seqNum++; 01228 } // end determine a best transformation sequence 01229 01230 #ifndef NDEBUG 01231 // Really, we output the number of intermediates with no incident unit edge (can be normalized) 01232 cout << "The best transformation sequence achieves a nontrivial edge count of " << bestTransformationSequence->bestNumNontrivialEdges 01233 << ", at which point there are " << bestTransformationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount << " intermediate vertices" << endl; 01234 //<< ", at which point " << bestTransformationSequence->numIntermediatesWithoutUnitEdgeAtBestEdgecount << " of " 01235 //<< bestTransformationSequence->numIntermediatesAtBestEdgecount << " intermediate vertices have no incident unit edges" << endl; 01236 cout << "Now performing the best partial sequence of transformations..." << endl; 01237 #endif 01238 // Perform the best transformation sequence 01239 numReroutings = 0; 01240 for (size_t i = 0; i < bestTransformationSequence->transformationVector.size(); i++) { 01241 if (bestTransformationSequence->transformationVector[i].isRerouting()) { // rerouting 01242 numReroutings++; 01243 bestTransformationSequence->transformationVector[i].getRerouting().isPre() ? 01244 preroute_edge_directly(bestTransformationSequence->transformationVector[i].getRerouting().getER(angelLCG), angelLCG, edge_ref_list, jae_list) 01245 : postroute_edge_directly(bestTransformationSequence->transformationVector[i].getRerouting().getER(angelLCG), angelLCG, edge_ref_list, jae_list); 01246 } // end rerouting 01247 else { // edge elimination 01248 bestTransformationSequence->transformationVector[i].getEdgeElim().isFront() ? 01249 front_eliminate_edge_directly(bestTransformationSequence->transformationVector[i].getEdgeElim().getE(angelLCG), angelLCG, edge_ref_list, jae_list) 01250 : back_eliminate_edge_directly(bestTransformationSequence->transformationVector[i].getEdgeElim().getE(angelLCG), angelLCG, edge_ref_list, jae_list); 01251 } // end edge elimination 01252 // break when we've reached our goal 01253 if (num_nontrivial_edges (angelLCG, ourAwarenessLevel) == bestTransformationSequence->bestNumNontrivialEdges) 01254 break; 01255 } // end iterate over best transformation sequence 01256 01257 #ifndef NDEBUG 01258 cout << "Goal of " << bestTransformationSequence->bestNumNontrivialEdges << " reached" << endl; 01259 #endif 01260 delete bestTransformationSequence; 01261 01262 populate_remainderGraph_and_correlationLists (angelLCG, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list); 01263 } // end xaifBoosterCrossCountryInterface::compute_partial_transformation_sequence() 01264 01265 void computeEliminationSequenceRandom(const LinearizedComputationalGraph& ourLCG, 01266 JacobianAccumulationExpressionList& jae_list, 01267 LinearizedComputationalGraph& remainderLCG, 01268 VertexCorrelationList& v_cor_list, 01269 EdgeCorrelationList& e_cor_list) { 01270 srand(time(NULL)); 01271 01272 // Create internal (angel) LCG from xaifBooster LCG 01273 vector<const LinearizedComputationalGraphVertex*> ourLCG_verts; 01274 c_graph_t angelLCG_orig; 01275 list<EdgeRef_t> edge_ref_list; 01276 ourLCG_to_angelLCG (ourLCG, ourLCG_verts, angelLCG_orig, edge_ref_list); 01277 01278 unsigned int max_steps = 100 * num_edges(angelLCG_orig); 01279 01280 c_graph_t angelLCG_copy (angelLCG_orig); 01281 elimSeq_cost_t dummy_elimSeq_cost (0, 0, 0, 0, 0, 0); 01282 refillDependenceMap_t dummy_refillDependenceMap; 01283 vector<EdgeElim> allEdgeElimsV, edgeElimSeqV, best_edgeElimSeqV; 01284 unsigned int previous_computationalCost = 0; 01285 unsigned int computationalCost = 0; 01286 int best_computationalCost = -1; 01287 for (unsigned int steps_counter = 0; steps_counter < max_steps; steps_counter++) { 01288 /* 01289 // Start over from the beginning 01290 if (steps_counter%(max_steps/num_passes) == 0) { 01291 #ifndef NDEBUG 01292 cout << "Starting a new random pass (" << steps_counter << "/" << max_steps << " steps):\tbest_computationalCost = " << best_computationalCost << endl; 01293 #endif 01294 edgeElimSeqV.clear(); 01295 computationalCost = 0; 01296 previous_computationalCost = 0; 01297 angelLCG_copy = angelLCG_orig; 01298 continue; 01299 } 01300 */ 01301 eliminatable_edges(angelLCG_copy, allEdgeElimsV); 01302 if (allEdgeElimsV.empty()) { 01303 #ifndef NDEBUG 01304 cout << "Sequence complete. length = " << edgeElimSeqV.size() << ", cost = " << computationalCost; 01305 #endif 01306 if (best_computationalCost == -1 // this is our first sequence 01307 || (int)computationalCost < best_computationalCost) { 01308 #ifndef NDEBUG 01309 cout << " (this sequence is new best) " << endl; 01310 #endif 01311 best_computationalCost = computationalCost; 01312 best_edgeElimSeqV = edgeElimSeqV; 01313 } 01314 #ifndef NDEBUG 01315 else 01316 cout << endl; 01317 #endif 01318 edgeElimSeqV.clear(); 01319 computationalCost = 0; 01320 previous_computationalCost = 0; 01321 angelLCG_copy = angelLCG_orig; 01322 continue; 01323 } // end sequence is finished 01324 01325 // calculate relative probabilities for each possible edge elim 01326 vector<double> deltaE(allEdgeElimsV.size()); 01327 for (size_t c = 0; c < allEdgeElimsV.size(); c++) 01328 deltaE[c] = allEdgeElimsV[c].getCost(angelLCG_copy); 01329 int choice_index = chooseEdgeElimRandomly(deltaE); 01330 if (choice_index == -1) { // BACKTRACKING 01331 #ifndef NDEBUG 01332 cout << "Performing a BACKTRACKING step" << endl; 01333 #endif 01334 if (edgeElimSeqV.empty()) 01335 continue; 01336 angelLCG_copy = angelLCG_orig; 01337 edgeElimSeqV.pop_back(); 01338 computationalCost = 0; 01339 for (size_t i = 0; i < edgeElimSeqV.size(); i++) { 01340 if (i == edgeElimSeqV.size() - 1) // save previous_computationalCost 01341 previous_computationalCost = computationalCost; 01342 #ifndef NDEBUG 01343 cout << "\t"; 01344 #endif 01345 computationalCost += edgeElimSeqV[i].isFront() ? 01346 front_elim(edgeElimSeqV[i].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap) 01347 : back_elim(edgeElimSeqV[i].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap); 01348 } // end iterate over edge elims 01349 } // end backtracking 01350 else { // eliminate an edge 01351 previous_computationalCost = computationalCost; 01352 edgeElimSeqV.push_back(allEdgeElimsV[choice_index]); 01353 computationalCost += allEdgeElimsV[choice_index].isFront() ? 01354 front_elim(allEdgeElimsV[choice_index].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap) 01355 : back_elim(allEdgeElimsV[choice_index].getE(angelLCG_copy), angelLCG_copy, dummy_elimSeq_cost, dummy_refillDependenceMap); 01356 } // end edge elim. 01357 #ifndef NDEBUG 01358 cout << "datapoint:" << edgeElimSeqV.size() << ":" << computationalCost << endl; 01359 #endif 01360 } // end outer loop 01361 01362 #ifndef NDEBUG 01363 cout << "Achieved cost " << best_computationalCost << " with the following sequence of edge eliminations:"; 01364 for (size_t c = 0; c < best_edgeElimSeqV.size(); c++) 01365 cout << endl << best_edgeElimSeqV[c].debug().c_str(); 01366 cout << endl << endl << "****** Now re-performing best_edgeElimSeqV" << endl; 01367 #endif 01368 unsigned int cost_of_elim_seq = 0; 01369 for (size_t c = 0; c < best_edgeElimSeqV.size(); c++) 01370 cost_of_elim_seq += best_edgeElimSeqV[c].isFront() ? 01371 front_eliminate_edge_directly(best_edgeElimSeqV[c].getE(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list) 01372 : back_eliminate_edge_directly(best_edgeElimSeqV[c].getE(angelLCG_orig), angelLCG_orig, edge_ref_list, jae_list); 01373 #ifndef NDEBUG 01374 write_graph ("angelLCG_orig after complete edge elimination sequence (G prime): ", angelLCG_orig); 01375 writeVertexAndEdgeTypes (cout, angelLCG_orig); 01376 cout << "computeEliminationSequenceRandom: cost " << cost_of_elim_seq << endl; 01377 #endif 01378 populate_remainderGraph_and_correlationLists (angelLCG_orig, ourLCG_verts, edge_ref_list, remainderLCG, v_cor_list, e_cor_list); 01379 } // end xaifBoosterCrossCountryInterface::compute_elimination_sequence_random() 01380 01381 void compute_elimination_sequence (const LinearizedComputationalGraph& xgraph, 01382 JacobianAccumulationExpressionList& JAElist, 01383 LinearizedComputationalGraph& remainderLCG, 01384 VertexCorrelationList& v_cor_list, 01385 EdgeCorrelationList& e_cor_list) { 01386 c_graph_t cg; 01387 vector<const LinearizedComputationalGraphVertex*> av; 01388 vector<edge_address_t> ae; 01389 read_graph_xaif_booster (xgraph, cg, av, ae); 01390 01391 typedef heuristic_pair_t<lowest_markowitz_vertex_t, reverse_mode_vertex_t> lm_rm_t; 01392 typedef heuristic_pair_t<lmmd_vertex_t, reverse_mode_vertex_t> lmmd_rm_t; 01393 typedef heuristic_triplet_t<momr_vertex_t, lowest_markowitz_vertex_t, reverse_mode_vertex_t> momr_lm_rm_t; 01394 lm_rm_t lm_rm_v (lowest_markowitz_vertex, reverse_mode_vertex); 01395 lmmd_rm_t lmmd_rm_v (lmmd_vertex, reverse_mode_vertex); 01396 momr_lm_rm_t momr_lm_rm_v (momr_vertex, lowest_markowitz_vertex, reverse_mode_vertex); 01397 01398 edge_ij_elim_heuristic_t<forward_mode_edge_t> fm_ij (forward_mode_edge); 01399 edge_ij_elim_heuristic_t<reverse_mode_edge_t> rm_ij (reverse_mode_edge); 01400 emulated_vertex_heuristic_t<lm_rm_t> lm_rm_e (lm_rm_v); 01401 emulated_vertex_heuristic_t<lmmd_rm_t> lmmd_rm_e (lmmd_rm_v); 01402 emulated_vertex_heuristic_t<momr_lm_rm_t> momr_lm_rm_e (momr_lm_rm_v); 01403 01404 vector<c_graph_t::vertex_t> vseq; 01405 vector<edge_ij_elim_t> eseq,v_eseq; 01406 int vCost=INT_MAX, eCost; 01407 01408 if (vertex_eliminatable (cg)) { 01409 vCost = best_heuristic (cg, vseq, forward_mode_vertex, reverse_mode_vertex, 01410 lm_rm_v, lmmd_rm_v, momr_lm_rm_v); 01411 #ifndef NDEBUG 01412 write_vector("Vertex elimination: sequence",vseq); 01413 cout << "Costs are " << vCost << '\n'; 01414 #endif 01415 convert_elimination_sequence (vseq, cg, v_eseq); 01416 #ifndef NDEBUG 01417 write_vector("Same elimination sequence as edge eliminations", v_eseq); 01418 #endif 01419 } 01420 eCost = best_heuristic (cg, eseq, fm_ij, rm_ij, lm_rm_e, lmmd_rm_e, momr_lm_rm_e); 01421 #ifndef NDEBUG 01422 write_vector("Edge elimination: sequence",eseq); 01423 cout << "Costs are " << eCost << '\n'; 01424 #endif 01425 if (vCost<eCost) 01426 eseq=v_eseq; 01427 01428 line_graph_t lg (cg); 01429 vector<triplet_t> tv; 01430 convert_elimination_sequence (eseq, lg, tv); 01431 01432 #ifndef NDEBUG 01433 write_vector("Same elimination sequence as face eliminations", tv); 01434 #endif 01435 01436 accu_graph_t ac (cg, lg); 01437 for (size_t c= 0; c < tv.size(); c++) 01438 face_elimination (tv[c], lg, ac); 01439 01440 #ifndef NDEBUG 01441 write_graph ("Empty line graph", lg); 01442 line_graph_t::evn_t evn= get(vertex_name, lg); 01443 write_vertex_property (cout, "vertices of this edge graph", evn, lg); 01444 #endif 01445 01446 ac.set_jacobi_entries (); 01447 01448 #ifndef NDEBUG 01449 for (size_t c= 0; c < ac.accu_exp.size(); c++) { 01450 write_graph ("Accumulation graph", ac.accu_exp[c]); 01451 property_map<pure_accu_exp_graph_t, vertex_name_t>::type vprop= 01452 get (vertex_name, ac.accu_exp[c]); 01453 write_vertex_property (cout, "Vertex props", vprop, ac.accu_exp[c]); 01454 ad_edge_t my_jacobi= ac.jacobi_entries[c]; 01455 if (my_jacobi.second == 0) cout << "isn't Jacobian entry\n"; 01456 else cout << "is Jacoby entry: " << my_jacobi << std::endl; } 01457 #endif 01458 01459 write_graph_xaif_booster (ac, av, ae, JAElist, remainderLCG, v_cor_list, e_cor_list); 01460 } // end xaifBoosterCrossCountryInterface::compute_elimination_sequence() 01461 01462 void compute_elimination_sequence_lsa_face (const LinearizedComputationalGraph& xgraph, 01463 int iterations, 01464 double gamma, 01465 JacobianAccumulationExpressionList& JAElist, 01466 LinearizedComputationalGraph& remainderLCG, 01467 VertexCorrelationList& v_cor_list, 01468 EdgeCorrelationList& e_cor_list) { 01469 c_graph_t cg; 01470 vector<const LinearizedComputationalGraphVertex*> av; 01471 vector<edge_address_t> ae; 01472 read_graph_xaif_booster (xgraph, cg, av, ae); 01473 line_graph_t lg (cg); 01474 01475 face_elimination_history_t feh (lg); 01476 typedef triplet_heuristic_t<reverse_mode_face_t> rm_t; 01477 rm_t rm (reverse_mode_face); 01478 SA_elimination_cost_t<rm_t> cost (rm); 01479 neighbor_sequence_check_t neighbor; 01480 01481 // int elim_costs= 01482 LSA (feh, neighbor, cost, gamma, iterations); 01483 feh.complete_sequence (rm); 01484 01485 accu_graph_t ac (cg, lg); 01486 for (size_t c= 0; c < feh.seq.size(); c++) 01487 face_elimination (feh.seq[c], lg, ac); 01488 ac.set_jacobi_entries (); 01489 01490 write_graph_xaif_booster (ac, av, ae, JAElist, remainderLCG, v_cor_list, e_cor_list); 01491 01492 } // end xaifBoosterCrossCountryInterface::compute_elimination_sequence_lsa_face() 01493 01494 void compute_elimination_sequence_lsa_vertex (const LinearizedComputationalGraph& xgraph, 01495 int iterations, 01496 double gamma, 01497 JacobianAccumulationExpressionList& JAElist, 01498 LinearizedComputationalGraph& remainderLCG, 01499 VertexCorrelationList& v_cor_list, 01500 EdgeCorrelationList& e_cor_list) { 01501 c_graph_t cg; 01502 vector<const LinearizedComputationalGraphVertex*> av; 01503 vector<edge_address_t> ae; 01504 read_graph_xaif_booster (xgraph, cg, av, ae); 01505 01506 // Check if vertex elimination works 01507 for (size_t i= 0; i != cg.dependents.size(); i++) 01508 // version 1 01509 if (out_degree (cg.dependents[i], cg) > 0) { 01510 cerr << "Warning! Vertex elimination not possible with this graph, because at least one dependent vertex has at least one outedge.\n" 01511 << "Calling LSA for face elimination with same parameters (may take longer)...\n"; 01512 return compute_elimination_sequence_lsa_face (xgraph, iterations, gamma, JAElist, remainderLCG, v_cor_list, e_cor_list);} 01513 // version 2 01514 // THROW_EXCEPT_MACRO (out_degree (cg.dependents[i], cg) > 0, consistency_exception, "Vertex elimination not possible with these graph."); 01515 01516 vertex_elimination_history_t veh (cg); 01517 SA_elimination_cost_t<reverse_mode_vertex_t> cost (reverse_mode_vertex); 01518 neighbor_sequence_check_t neighbor; 01519 01520 // int elim_costs= 01521 LSA (veh, neighbor, cost, gamma, iterations); 01522 veh.complete_sequence (reverse_mode_vertex); 01523 01524 vector<edge_ij_elim_t> eseq; 01525 vector<triplet_t> tv; 01526 line_graph_t lg (cg); 01527 convert_elimination_sequence (veh.seq, cg, eseq); 01528 convert_elimination_sequence (eseq, lg, tv); 01529 01530 accu_graph_t ac (cg, lg); 01531 for (size_t c= 0; c < tv.size(); c++) 01532 face_elimination (tv[c], lg, ac); 01533 ac.set_jacobi_entries (); 01534 01535 write_graph_xaif_booster (ac, av, ae, JAElist, remainderLCG, v_cor_list, e_cor_list); 01536 } // end of angel::compute_elimination_sequence_lsa_vertex() 01537 01538 void Elimination::eliminate() { 01539 01540 try { 01541 switch (myType) { 01542 case OPS_ELIMTYPE: 01543 compute_elimination_sequence(*myLCG_p, 01544 myJAEList, 01545 myRemainderLCG, 01546 myVertexCorrelationList, 01547 myEdgeCorrelationList); 01548 break; 01549 case OPS_RANDOM_ELIMTYPE: 01550 computeEliminationSequenceRandom(*myLCG_p, 01551 myJAEList, 01552 myRemainderLCG, 01553 myVertexCorrelationList, 01554 myEdgeCorrelationList); 01555 break; 01556 case OPS_LSA_VERTEX_ELIMTYPE: 01557 compute_elimination_sequence_lsa_vertex(*myLCG_p, 01558 getNumIterations(), 01559 getGamma(), 01560 myJAEList, 01561 myRemainderLCG, 01562 myVertexCorrelationList, 01563 myEdgeCorrelationList); 01564 break; 01565 case OPS_LSA_FACE_ELIMTYPE: 01566 compute_elimination_sequence_lsa_face(*myLCG_p, 01567 getNumIterations(), 01568 getGamma(), 01569 myJAEList, 01570 myRemainderLCG, 01571 myVertexCorrelationList, 01572 myEdgeCorrelationList); 01573 break; 01574 case SCARCE_ELIMTYPE: 01575 compute_partial_elimination_sequence(*myLCG_p, 01576 ourAwarenessLevel, 01577 ourAllowMaintainingFlag, 01578 myJAEList, 01579 myRemainderLCG, 01580 myVertexCorrelationList, 01581 myEdgeCorrelationList); 01582 break; 01583 case SCARCE_RANDOM_ELIMTYPE: 01584 compute_partial_elimination_sequence_random(*myLCG_p, 01585 ourAwarenessLevel, 01586 ourAllowMaintainingFlag, 01587 myJAEList, 01588 myRemainderLCG, 01589 myVertexCorrelationList, 01590 myEdgeCorrelationList); 01591 break; 01592 case SCARCE_TRANSFORMATIONTYPE: 01593 compute_partial_transformation_sequence(*myLCG_p, 01594 ourAwarenessLevel, 01595 ourAllowMaintainingFlag, 01596 myJAEList, 01597 myRemainderLCG, 01598 myVertexCorrelationList, 01599 myEdgeCorrelationList, 01600 myNumReroutings); 01601 break; 01602 case SCARCE_RANDOM_TRANSFORMATIONTYPE: 01603 compute_partial_transformation_sequence_random(*myLCG_p, 01604 ourAwarenessLevel, 01605 ourAllowMaintainingFlag, 01606 myJAEList, 01607 myRemainderLCG, 01608 myVertexCorrelationList, 01609 myEdgeCorrelationList, 01610 myNumReroutings); 01611 break; 01612 default: 01613 THROW_EXCEPT_MACRO (true, consistency_exception, "Missing or invalid elimination type"); 01614 break; 01615 } // end switch (myType) 01616 } // end try 01617 catch (base_exception e) { 01618 throw EliminationException(std::string("angel exception caught within Elimination::eliminate() : ")+e.what_reason()); 01619 } 01620 01621 } // end of xaifBoosterCrossCountryInterface::Elimination::eliminate() 01622 01623 } // end namespace xaifBoosterCrossCountryInterface 01624 01625 #endif // USEXAIFBOOSTER 01626