Changeset 4598 for icGREP/icgrepdevel/icgrep/pablo/optimizers
 Timestamp:
 Jun 5, 2015, 4:34:27 PM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4596 r4598 376 376 DdNode * Ni = std::get<1>(advances[i]); 377 377 // TODO: test both Cudd_And and Cudd_bddIntersect to see which is faster 378 DdNode * const IiIk = Cudd_bddIntersect(mManager, Ik, Ii); Cudd_Ref(IiIk);378 DdNode * const IiIk = Intersect(Ik, Ii); 379 379 // Is there any satisfying truth assignment? If not, these streams are mutually exclusive. 380 380 if (noSatisfyingAssignment(IiIk)) { 381 381 assert (mCharacterizationMap.count(adv)); 382 382 DdNode *& Ci = mCharacterizationMap[adv]; 383 // mark the ith and kth Advances as being mutually exclusive383 // Mark the ith and kth Advances as being mutually exclusive 384 384 Ck = And(Ck, Ni); 385 385 Ci = And(Ci, Nk); … … 510 510 } 511 511 512 inline DdNode * AutoMultiplexing::Intersect(DdNode * const x, DdNode * const y) { 513 DdNode * r = Cudd_bddIntersect(mManager, x, y); Cudd_Ref(r); 514 return r; 515 } 516 512 517 inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) { 513 518 DdNode * r = Cudd_bddOr(mManager, x, y); … … 558 563 using DegreeType = graph_traits<ConstraintGraph>::degree_size_type; 559 564 560 // push all source nodes into the active independent set S 561 IndependentSet S; 562 unsigned remainingVerticies = num_vertices(mConstraintGraph); 565 IndependentSet S, N; 566 auto remainingVerticies = num_vertices(mConstraintGraph); 563 567 std::vector<DegreeType> D(remainingVerticies); 564 568 S.reserve(15); 569 N.reserve(15); 570 571 // Push all source nodes into the new independent set N 565 572 VertexIterator vi, vi_end; 566 573 for (std::tie(vi, vi_end) = vertices(mConstraintGraph); vi != vi_end; ++vi) { 567 auto d = in_degree(*vi, mConstraintGraph);574 const auto d = in_degree(*vi, mConstraintGraph); 568 575 D[*vi] = d; 569 576 if (d == 0) { 570 S.push_back(*vi); 571 } 572 } 573 574 assert (!S.empty()); 575 576 for ( ; remainingVerticies >= 3; remainingVerticies) { 577 if (S.size() >= 3) { 578 addMultiplexSet(S); 577 N.push_back(*vi); 578 } 579 } 580 581 while ( remainingVerticies >= 3 ) { 582 583 584 // If we have at least 3 vertices in our two sets, try adding them to our 585 // multiplexing set. 586 if ((N.size() + S.size()) >= 3) { 587 addMultiplexSet(N, S); 579 588 } 580 // Randomly choose a vertex in S and discard it. 581 assert (!S.empty()); 582 const auto i = S.begin() + RNGDistribution(0, S.size()  1)(rng); 583 const Vertex u = *i; 584 S.erase(i); 585 EdgeIterator ei, ei_end; 586 for (std::tie(ei, ei_end) = out_edges(u, mConstraintGraph); ei != ei_end; ++ei) { 587 const Vertex v = target(*ei, mConstraintGraph); 588 if ((D[v]) == 0) { 589 S.push_back(v); 590 } 591 } 589 590 // Move all of our "newly" uncovered vertices into the "known" set. By always 591 // choosing at least one element from N, this will prevent us from adding the 592 // same multiplexing set again. 593 S.insert(S.end(), N.begin(), N.end()); N.clear(); 594 595 do { 596 // Randomly choose a vertex in S and discard it. 597 assert (!S.empty()); 598 const auto i = S.begin() + RNGDistribution(0, S.size()  1)(rng); 599 const Vertex u = *i; 600 S.erase(i); 601 remainingVerticies; 602 EdgeIterator ei, ei_end; 603 for (std::tie(ei, ei_end) = out_edges(u, mConstraintGraph); ei != ei_end; ++ei) { 604 const Vertex v = target(*ei, mConstraintGraph); 605 if ((D[v]) == 0) { 606 N.push_back(v); 607 } 608 } 609 } 610 while (N.empty() && remainingVerticies >= 3); 592 611 } 593 612 … … 596 615 597 616 /**  * 617 * @brief is_power_of_2 618 * @param n an integer 619 **  */ 620 static inline bool is_power_of_2(const size_t n) { 621 return ((n & (n  1)) == 0) ; 622 } 623 624 /**  * 598 625 * @brief addMultiplexSet 626 * @param N an independent set 599 627 * @param S an independent set 600 628 **  */ 601 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & S) {629 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & S) { 602 630 603 631 // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships 604 632 // between the "set vertex" and its members. We obtain these from "generateMultiplexSets". 605 633 606 // TODO: Instead of building a graph, construct a trie of all members in the powersetof S that are of size634 // TODO: Instead of building a graph, construct a trie of all members of all combinations of S that are of size 607 635 // >= 3 and not 2^n for any n. 608 636 609 const auto v = add_vertex(mMultiplexSetGraph); 610 for (auto u : S) { 611 add_edge(v, u, mMultiplexSetGraph); 637 // This will give us <= (âi=1 to N C(N,i)) * [1 + (âi=1 to M C(M,i))] combinations. It seems to improve 638 // the potential result but make the MaxWeightIndependentSet far more costly. Look into a method without explicit 639 // vertex deletion. 640 641 for (int i = 0; i < N.size(); ++i) { 642 mCurrentCombination.push_back(N[i]); 643 addMultiplexSet(N, i + 1, S, 0); 644 assert (mCurrentCombination.back() == N[i]); 645 mCurrentCombination.pop_back(); 646 } 647 } 648 649 /**  * 650 * @brief addMultiplexSet 651 * @param N an independent set 652 * @param S an independent set 653 **  */ 654 void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const int i, 655 const IndependentSet & S, const int j) { 656 657 // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships 658 // between the "set vertex" and its members. We obtain these from "generateMultiplexSets". 659 660 // TODO: Instead of building a graph, construct a trie of all members of all combinations of S that are of size 661 // >= 3 and not 2^n for any n. 662 663 if (mCurrentCombination.size() >= 3 && !is_power_of_2(mCurrentCombination.size())) { 664 const auto v = add_vertex(mMultiplexSetGraph); 665 for (auto u : mCurrentCombination) { 666 add_edge(v, u, mMultiplexSetGraph); 667 } 668 } 669 670 for (int ii = i; ii < N.size(); ++ii) { 671 mCurrentCombination.push_back(N[ii]); 672 addMultiplexSet(N, ii + 1, S, j); 673 assert (mCurrentCombination.back() == N[ii]); 674 mCurrentCombination.pop_back(); 675 } 676 677 for (int jj = j; jj < S.size(); ++jj) { 678 mCurrentCombination.push_back(S[jj]); 679 addMultiplexSet(N, i + 1, S, jj + 1); 680 assert (mCurrentCombination.back() == S[jj]); 681 mCurrentCombination.pop_back(); 612 682 } 613 683 … … 673 743 } 674 744 Vw = std::max<int>(Vw  Nw, 0); 675 //Vw *= Vw;745 Vw *= Vw; 676 746 std::get<1>(G[*vi]) = Vw; 677 747 Tw += Vw; … … 862 932 863 933 /**  * 864 * @brief compute_m865 **  */ 866 static inline size_t compute_m(const size_t n) {934 * @brief log2_plus_one 935 **  */ 936 static inline size_t log2_plus_one(const size_t n) { 867 937 return std::log2<size_t>(n) + 1; // use a faster builtin function for this? 868 938 } … … 881 951 max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph)); 882 952 } 883 const size_t max_m = compute_m(max_n);953 const size_t max_m = log2_plus_one(max_n); 884 954 885 955 std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n); … … 895 965 if (n) { 896 966 897 const size_t m = compute_m(n);967 const size_t m = log2_plus_one(n); 898 968 899 969 graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end; … … 928 998 std::ostringstream prefix; 929 999 930 prefix << "mux" ;1000 prefix << "mux" << n << "to" << m; 931 1001 for (size_t i = 1; i <= n; ++i) { 932 1002 if ((i & (static_cast<size_t>(1) << j)) != 0) { 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp
r4596 r4598 25 25 using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>; 26 26 using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::listS, boost::undirectedS, std::tuple<int, int, MultiplexSetGraph::vertex_descriptor>>; 27 using ChosenSet s= std::vector<MultiplexSetGraph::vertex_descriptor>;27 using ChosenSet = std::vector<MultiplexSetGraph::vertex_descriptor>; 28 28 using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>; 29 29 using Advances = std::vector<Advance *>; … … 44 44 void createMultiplexSetGraph(); 45 45 bool generateMultiplexSets(RNG & rng); 46 void addMultiplexSet(const IndependentSet & set); 46 void addMultiplexSet(const IndependentSet & N, const IndependentSet & S); 47 void addMultiplexSet(const IndependentSet & N, const int i, const IndependentSet & S, const int j); 47 48 void approxMaxWeightIndependentSet(RNG & rng); 48 49 void applySubsetConstraints(); … … 57 58 bool isZero(DdNode * const x) const; 58 59 DdNode * And(DdNode * const x, DdNode * const y); 60 DdNode * Intersect(DdNode * const x, DdNode * const y); 59 61 DdNode * Or(DdNode * const x, DdNode * const y); 60 62 DdNode * Xor(DdNode * const x, DdNode * const y); … … 69 71 ConstraintGraph mConstraintGraph; 70 72 SubsetGraph mSubsetGraph; 71 Advances mAdvance; 73 Advances mAdvance; 72 74 MultiplexSetGraph mMultiplexSetGraph; 75 ChosenSet mCurrentCombination; 73 76 }; 74 77
Note: See TracChangeset
for help on using the changeset viewer.