Ignore:
Timestamp:
Jun 18, 2015, 11:33:10 AM (4 years ago)
Author:
nmedfort
Message:

Some clean up work and additional comments for last multiplexing check in.

File:
1 edited

Legend:

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

    r4608 r4610  
    122122
    123123    RECORD_TIMESTAMP(start_create_multiplex_graph);
    124     am.createMultiplexSetGraph();
    125124    const bool multiplex = am.generateMultiplexSets(rng, 1);
    126125    RECORD_TIMESTAMP(end_create_multiplex_graph);
     
    129128    if (multiplex) {
    130129
    131         RECORD_TIMESTAMP(start_mwis);
     130        RECORD_TIMESTAMP(start_select_multiplex_sets);
    132131        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));
    135134
    136135        RECORD_TIMESTAMP(start_subset_constraints);
     
    370369                    }
    371370                case PabloAST::ClassTypeId::Call:
    372                     bdd = Cudd_bddIthVar(mManager, mVariables++);
     371                    bdd = NewVar();
    373372                    break;
    374373                case PabloAST::ClassTypeId::Advance:
     
    389388
    390389                        DdNode * const Ik = input[0];
    391                         DdNode * Ck = Cudd_bddIthVar(mManager, mVariables++);
     390                        DdNode * Ck = NewVar();
    392391                        DdNode * const Nk = Not(Ck);
    393392
     
    505504 * @brief notTransitivelyDependant
    506505 ** ------------------------------------------------------------------------------------------------------------- */
    507 inline bool AutoMultiplexing::notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const {
     506inline bool AutoMultiplexing::notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const {
    508507    return (mConstraintGraph.get_edge(i, j) == 0);
    509508}
     
    519518inline DdNode * AutoMultiplexing::One() const {
    520519    return Cudd_ReadOne(mManager);
     520}
     521
     522inline DdNode * AutoMultiplexing::NewVar() {
     523    return Cudd_bddIthVar(mManager, mVariables++);
    521524}
    522525
     
    567570
    568571/** ------------------------------------------------------------------------------------------------------------- *
    569  * @brief createMultiplexSetGraph
    570  ** ------------------------------------------------------------------------------------------------------------- */
    571 void AutoMultiplexing::createMultiplexSetGraph() {
    572     mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
    573 }
    574 
    575 /** ------------------------------------------------------------------------------------------------------------- *
    576572 * @brief generateMultiplexSets
    577573 * @param RNG random number generator
     
    579575bool AutoMultiplexing::generateMultiplexSets(RNG & rng, unsigned k) {
    580576
    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;
    583579
    584580    // What if we generated a "constraint free" graph instead? By taking each connected component of it
     
    588584    IndependentSet M, N;
    589585    auto remainingVerticies = num_vertices(mConstraintGraph);
    590     std::vector<DegreeType> D(remainingVerticies);
     586    std::vector<degree_t> D(remainingVerticies);
    591587    M.reserve(15);
    592588    N.reserve(15);
     589
     590    mMultiplexSetGraph = MultiplexSetGraph(remainingVerticies);
    593591
    594592    while (k) {
     
    621619                assert (!M.empty());
    622620                const auto i = M.begin() + IntDistribution(0, M.size() - 1)(rng);
    623                 const Vertex u = *i;
     621                const vertex_t u = *i;
    624622                M.erase(i);
    625623                --remainingVerticies;
    626624                for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
    627                     const Vertex v = target(e, mConstraintGraph);
     625                    const vertex_t v = target(e, mConstraintGraph);
    628626                    if ((--D[v]) == 0) {
    629627                        N.push_back(v);
     
    648646 * @brief addMultiplexSet
    649647 * @param N an independent set
    650  * @param S an independent set
     648 * @param M an independent set
    651649 ** ------------------------------------------------------------------------------------------------------------- */
    652650inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) {
     
    682680
    683681/** ------------------------------------------------------------------------------------------------------------- *
    684  * @brief approxMinWeightExactSubsetCover
     682 * @brief selectMultiplexSets
    685683 * @param RNG random number generator
     684 *
     685 * This algorithm is simply computes a greedy set cover. We want an exact max-weight 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.
    686688 ** ------------------------------------------------------------------------------------------------------------- */
    687689void AutoMultiplexing::selectMultiplexSets(RNG &) {
     690
    688691
    689692    using OutEdgeIterator = graph_traits<MultiplexSetGraph>::out_edge_iterator;
     
    704707    for (;;) {
    705708
     709        // Choose the set with the greatest number of vertices not already included in some other set.
    706710        vertex_t k = 0;
    707711        degree_t w = 0;
     
    714718        }
    715719
     720        // Multiplexing requires at least 3 elements; if the best set contains fewer than 3, abort.
    716721        if (w < 3) {
    717722            break;
    718723        }
    719724
    720         degree_t count = 0;
    721725        OutEdgeIterator ei, ei_end;
    722726        for (std::tie(ei, ei_end) = out_edges(k + m, mMultiplexSetGraph); ei != ei_end; ++ei) {
     
    727731                for (std::tie(ej, ej_end) = in_edges(j, mMultiplexSetGraph); ej != ej_end; ++ej) {
    728732                    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)) {
    736742            vertex_t j = 0;
    737743            degree_t w = 0;
     
    741747                    degree_t r = 1;
    742748                    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);
    744751                    }
    745752                    if (w < r) {
Note: See TracChangeset for help on using the changeset viewer.