Ignore:
Timestamp:
Jun 5, 2015, 4:34:27 PM (4 years ago)
Author:
nmedfort
Message:

Added the ability to compute all unique combinations of potential multiplexing sets.

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4596 r4598  
    376376                                DdNode * Ni = std::get<1>(advances[i]);
    377377                                // 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);
    379379                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    380380                                if (noSatisfyingAssignment(IiIk)) {
    381381                                    assert (mCharacterizationMap.count(adv));
    382382                                    DdNode *& Ci = mCharacterizationMap[adv];
    383                                     // mark the i-th and k-th Advances as being mutually exclusive
     383                                    // Mark the i-th and k-th Advances as being mutually exclusive
    384384                                    Ck = And(Ck, Ni);
    385385                                    Ci = And(Ci, Nk);
     
    510510}
    511511
     512inline 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
    512517inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
    513518    DdNode * r = Cudd_bddOr(mManager, x, y);
     
    558563    using DegreeType = graph_traits<ConstraintGraph>::degree_size_type;
    559564
    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);
    563567    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
    565572    VertexIterator vi, vi_end;
    566573    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);
    568575        D[*vi] = d;
    569576        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);
    579588        }       
    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);
    592611    }
    593612
     
    596615
    597616/** ------------------------------------------------------------------------------------------------------------- *
     617 * @brief is_power_of_2
     618 * @param n an integer
     619 ** ------------------------------------------------------------------------------------------------------------- */
     620static inline bool is_power_of_2(const size_t n) {
     621    return ((n & (n - 1)) == 0) ;
     622}
     623
     624/** ------------------------------------------------------------------------------------------------------------- *
    598625 * @brief addMultiplexSet
     626 * @param N an independent set
    599627 * @param S an independent set
    600628 ** ------------------------------------------------------------------------------------------------------------- */
    601 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & S) {
     629inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & S) {
    602630
    603631    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
    604632    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
    605633
    606     // TODO: Instead of building a graph, construct a trie of all members in the powerset of S that are of size
     634    // TODO: Instead of building a graph, construct a trie of all members of all combinations of S that are of size
    607635    // >= 3 and not 2^n for any n.
    608636
    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 ** ------------------------------------------------------------------------------------------------------------- */
     654void 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();
    612682    }
    613683
     
    673743            }
    674744            Vw = std::max<int>(Vw - Nw, 0);
    675             // Vw *= Vw;
     745            Vw *= Vw;
    676746            std::get<1>(G[*vi]) = Vw;
    677747            Tw += Vw;
     
    862932
    863933/** ------------------------------------------------------------------------------------------------------------- *
    864  * @brief compute_m
    865  ** ------------------------------------------------------------------------------------------------------------- */
    866 static inline size_t compute_m(const size_t n) {
     934 * @brief log2_plus_one
     935 ** ------------------------------------------------------------------------------------------------------------- */
     936static inline size_t log2_plus_one(const size_t n) {
    867937    return std::log2<size_t>(n) + 1; // use a faster builtin function for this?
    868938}
     
    881951        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
    882952    }
    883     const size_t max_m = compute_m(max_n);
     953    const size_t max_m = log2_plus_one(max_n);
    884954
    885955    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
     
    895965        if (n) {
    896966
    897             const size_t m = compute_m(n);
     967            const size_t m = log2_plus_one(n);
    898968
    899969            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
     
    928998                std::ostringstream prefix;
    929999
    930                 prefix << "mux";
     1000                prefix << "mux" << n << "to" << m;
    9311001                for (size_t i = 1; i <= n; ++i) {
    9321002                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4596 r4598  
    2525    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    2626    using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::listS, boost::undirectedS, std::tuple<int, int, MultiplexSetGraph::vertex_descriptor>>;
    27     using ChosenSets = std::vector<MultiplexSetGraph::vertex_descriptor>;
     27    using ChosenSet = std::vector<MultiplexSetGraph::vertex_descriptor>;
    2828    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    2929    using Advances = std::vector<Advance *>;
     
    4444    void createMultiplexSetGraph();
    4545    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);
    4748    void approxMaxWeightIndependentSet(RNG & rng);
    4849    void applySubsetConstraints();
     
    5758    bool isZero(DdNode * const x) const;
    5859    DdNode * And(DdNode * const x, DdNode * const y);
     60    DdNode * Intersect(DdNode * const x, DdNode * const y);
    5961    DdNode * Or(DdNode * const x, DdNode * const y);
    6062    DdNode * Xor(DdNode * const x, DdNode * const y);
     
    6971    ConstraintGraph         mConstraintGraph;
    7072    SubsetGraph             mSubsetGraph;
    71     Advances                mAdvance;
     73    Advances                mAdvance;   
    7274    MultiplexSetGraph       mMultiplexSetGraph;
     75    ChosenSet               mCurrentCombination;
    7376};
    7477
Note: See TracChangeset for help on using the changeset viewer.