Changeset 4610 for icGREP/icgrepdevel
 Timestamp:
 Jun 18, 2015, 11:33:10 AM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4608 r4610 122 122 123 123 RECORD_TIMESTAMP(start_create_multiplex_graph); 124 am.createMultiplexSetGraph();125 124 const bool multiplex = am.generateMultiplexSets(rng, 1); 126 125 RECORD_TIMESTAMP(end_create_multiplex_graph); … … 129 128 if (multiplex) { 130 129 131 RECORD_TIMESTAMP(start_ mwis);130 RECORD_TIMESTAMP(start_select_multiplex_sets); 132 131 am.selectMultiplexSets(rng); 133 RECORD_TIMESTAMP(end_ mwis);134 LOG("SelectMultiplexSets: " << (end_ mwis  start_mwis));132 RECORD_TIMESTAMP(end_select_multiplex_sets); 133 LOG("SelectMultiplexSets: " << (end_select_multiplex_sets  start_select_multiplex_sets)); 135 134 136 135 RECORD_TIMESTAMP(start_subset_constraints); … … 370 369 } 371 370 case PabloAST::ClassTypeId::Call: 372 bdd = Cudd_bddIthVar(mManager, mVariables++);371 bdd = NewVar(); 373 372 break; 374 373 case PabloAST::ClassTypeId::Advance: … … 389 388 390 389 DdNode * const Ik = input[0]; 391 DdNode * Ck = Cudd_bddIthVar(mManager, mVariables++);390 DdNode * Ck = NewVar(); 392 391 DdNode * const Nk = Not(Ck); 393 392 … … 505 504 * @brief notTransitivelyDependant 506 505 **  */ 507 inline bool AutoMultiplexing::notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptorj) const {506 inline bool AutoMultiplexing::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const { 508 507 return (mConstraintGraph.get_edge(i, j) == 0); 509 508 } … … 519 518 inline DdNode * AutoMultiplexing::One() const { 520 519 return Cudd_ReadOne(mManager); 520 } 521 522 inline DdNode * AutoMultiplexing::NewVar() { 523 return Cudd_bddIthVar(mManager, mVariables++); 521 524 } 522 525 … … 567 570 568 571 /**  * 569 * @brief createMultiplexSetGraph570 **  */571 void AutoMultiplexing::createMultiplexSetGraph() {572 mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));573 }574 575 /**  *576 572 * @brief generateMultiplexSets 577 573 * @param RNG random number generator … … 579 575 bool AutoMultiplexing::generateMultiplexSets(RNG & rng, unsigned k) { 580 576 581 using Vertex= ConstraintGraph::vertex_descriptor;582 using DegreeType= graph_traits<ConstraintGraph>::degree_size_type;577 using vertex_t = ConstraintGraph::vertex_descriptor; 578 using degree_t = graph_traits<ConstraintGraph>::degree_size_type; 583 579 584 580 // What if we generated a "constraint free" graph instead? By taking each connected component of it … … 588 584 IndependentSet M, N; 589 585 auto remainingVerticies = num_vertices(mConstraintGraph); 590 std::vector< DegreeType> D(remainingVerticies);586 std::vector<degree_t> D(remainingVerticies); 591 587 M.reserve(15); 592 588 N.reserve(15); 589 590 mMultiplexSetGraph = MultiplexSetGraph(remainingVerticies); 593 591 594 592 while (k) { … … 621 619 assert (!M.empty()); 622 620 const auto i = M.begin() + IntDistribution(0, M.size()  1)(rng); 623 const Vertexu = *i;621 const vertex_t u = *i; 624 622 M.erase(i); 625 623 remainingVerticies; 626 624 for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) { 627 const Vertexv = target(e, mConstraintGraph);625 const vertex_t v = target(e, mConstraintGraph); 628 626 if ((D[v]) == 0) { 629 627 N.push_back(v); … … 648 646 * @brief addMultiplexSet 649 647 * @param N an independent set 650 * @param San independent set648 * @param M an independent set 651 649 **  */ 652 650 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) { … … 682 680 683 681 /**  * 684 * @brief approxMinWeightExactSubsetCover682 * @brief selectMultiplexSets 685 683 * @param RNG random number generator 684 * 685 * This algorithm is simply computes a greedy set cover. We want an exact maxweight set cover but can generate new 686 * sets by taking a subset of any existing set. With a few modifications, the greedy approach seems to work well 687 * enough but more analysis is needed. 686 688 **  */ 687 689 void AutoMultiplexing::selectMultiplexSets(RNG &) { 690 688 691 689 692 using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator; … … 704 707 for (;;) { 705 708 709 // Choose the set with the greatest number of vertices not already included in some other set. 706 710 vertex_t k = 0; 707 711 degree_t w = 0; … … 714 718 } 715 719 720 // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort. 716 721 if (w < 3) { 717 722 break; 718 723 } 719 724 720 degree_t count = 0;721 725 OutEdgeIterator ei, ei_end; 722 726 for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) { … … 727 731 for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) { 728 732 remaining[source(*ej, mMultiplexSetGraph)  m]; 729 ++count; 730 } 731 } 732 } 733 734 // If this contains 2^n elements for any n, return the one with the greatest number of unvisited sets. 735 if (is_power_of_2(count)) { 733 } 734 } 735 } 736 737 assert (remaining[k] == 0); 738 739 // If this contains 2^n elements for any n, discard the member that is most likely to be added 740 // to some future set. 741 if (is_power_of_2(w)) { 736 742 vertex_t j = 0; 737 743 degree_t w = 0; … … 741 747 degree_t r = 1; 742 748 for (std::tie(ej, ej_end) = in_edges(i, mMultiplexSetGraph); ej != ej_end; ++ej) { 743 r += remaining[source(*ej, mMultiplexSetGraph)  m]; 749 // strongly prefer adding weight to unvisited sets that have more remaining vertices 750 r += std::pow(remaining[source(*ej, mMultiplexSetGraph)  m], 2); 744 751 } 745 752 if (w < r) { 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp
r4608 r4610 23 23 using CharacterizationMap = boost::container::flat_map<const PabloAST *, DdNode *>; 24 24 using ConstraintGraph = boost::adjacency_matrix<boost::directedS>; 25 using PathGraph = boost::adjacency_matrix<boost::undirectedS>;25 using ConstraintVertex = ConstraintGraph::vertex_descriptor; 26 26 using RNG = std::mt19937; 27 27 using IntDistribution = std::uniform_int_distribution<RNG::result_type>; 28 using RealDistribution = std::uniform_real_distribution<double>; 29 using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, boost::no_property, double>; 28 using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>; 30 29 using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>; 31 using ChosenSet = boost::container::flat_set<MultiplexSetGraph::vertex_descriptor>;32 30 using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>; 33 31 using Advances = std::vector<Advance *>; 34 using IndependentSet = std::vector<Constraint Graph::vertex_descriptor>;32 using IndependentSet = std::vector<ConstraintVertex>; 35 33 36 34 public: … … 39 37 void initialize(const std::vector<Var *> & vars, const PabloBlock & entry); 40 38 void characterize(PabloBlock & entry); 41 bool notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const; 42 void createMultiplexSetGraph(); 39 bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const; 43 40 bool generateMultiplexSets(RNG & rng, unsigned k = 1); 44 41 void addMultiplexSet(const IndependentSet & N, const IndependentSet & M); … … 62 59 DdNode * Not(DdNode * x) const; 63 60 DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z); 61 DdNode * NewVar(); 64 62 bool noSatisfyingAssignment(DdNode * const x); 65 63 void shutdown();
Note: See TracChangeset
for help on using the changeset viewer.