Ignore:
Timestamp:
Jun 7, 2015, 4:05:46 PM (4 years ago)
Author:
nmedfort
Message:

More multiplexing work. Reduced MWIS approximation cost.

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

Legend:

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

    r4598 r4599  
    5757    am.createMultiplexSetGraph();
    5858    std::random_device rd;
    59     RNG rng(rd());
     59    const auto seed = rd(); // 573650087;
     60    RNG rng(seed);
    6061    const bool multiplex = am.generateMultiplexSets(rng);
    6162    const timestamp_t end_create_multiplex_graph = read_cycle_counter();
     
    7778    }
    7879
    79     std::cerr << "Initialize:              " << (end_initialize - start) << std::endl;
    80     std::cerr << "Characterize:            " << (end_characterize - end_initialize) << std::endl;
    81     std::cerr << "Shutdown:                " << (end_shutdown - end_characterize) << std::endl;
    82     std::cerr << "GenerateMultiplexSets:   " << (end_create_multiplex_graph - end_shutdown) << std::endl;
    83     std::cerr << "MaxWeightIndependentSet: " << (end_mwis - end_create_multiplex_graph) << std::endl;
    84     std::cerr << "ApplySubsetConstraints:  " << (end_subset_constraints - end_mwis) << std::endl;
    85     std::cerr << "MultiplexSelectedSets:   " << (end_select_independent_sets - end_subset_constraints) << std::endl;
    86     std::cerr << "TopologicalSort:         " << (end_topological_sort - end_select_independent_sets) << std::endl;
    87 
     80//    std::cerr << "Initialize:              " << (end_initialize - start) << "   (seed=" << seed << ')' << std::endl;
     81//    std::cerr << "Characterize:            " << (end_characterize - end_initialize) << std::endl;
     82//    std::cerr << "Shutdown:                " << (end_shutdown - end_characterize) << std::endl;
     83//    std::cerr << "GenerateMultiplexSets:   " << (end_create_multiplex_graph - end_shutdown) << std::endl;
     84//    std::cerr << "MaxWeightIndependentSet: " << (end_mwis - end_create_multiplex_graph) << std::endl;
     85//    std::cerr << "ApplySubsetConstraints:  " << (end_subset_constraints - end_mwis) << std::endl;
     86//    std::cerr << "MultiplexSelectedSets:   " << (end_select_independent_sets - end_subset_constraints) << std::endl;
     87//    std::cerr << "TopologicalSort:         " << (end_topological_sort - end_select_independent_sets) << std::endl;
    8888
    8989    return modified;
     
    478478    }
    479479
    480     std::cerr << "comparisons: " << comparisons << ", avoided: " << avoided << std::endl;
     480//    std::cerr << "comparisons: " << comparisons << ", avoided: " << avoided << std::endl;
    481481}
    482482
     
    627627 * @param S an independent set
    628628 ** ------------------------------------------------------------------------------------------------------------- */
    629 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & S) {
     629inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) {
    630630
    631631    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
    632632    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
    633633
    634     // TODO: Instead of building a graph, construct a trie of all members of all combinations of S that are of size
    635     // >= 3 and not 2^n for any n.
    636 
    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 
     634    // Note: this computes (∑i=1 to |N| C(|N|,i)) * [1 + (∑i=1 to |M| C(|M|,i))] = (2^|N| - 1) * (2^|M|) combinations.
     635
     636    ChosenSet S;
    641637    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();
     638        S.insert(N[i]);
     639        addMultiplexSet(N, i + 1, M, 0, S);
     640        S.erase(S.find(N[i]));
    646641    }
    647642}
     
    653648 ** ------------------------------------------------------------------------------------------------------------- */
    654649void 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())) {
     650                                       const IndependentSet & M, const int j,
     651                                       ChosenSet & S) {
     652
     653    // TODO: Instead of building a graph, construct a trie of all members.
     654
     655    // Add S to the multiplex set if |S| >= 3 and not equal to 2^n for any n.
     656    if (S.size() >= 3 && !is_power_of_2(S.size())) {
    664657        const auto v = add_vertex(mMultiplexSetGraph);
    665         for (auto u : mCurrentCombination) {
     658        for (auto u : S) {
    666659            add_edge(v, u, mMultiplexSetGraph);
    667660        }
     
    669662
    670663    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();
    682     }
    683 
     664        S.insert(N[ii]);
     665        addMultiplexSet(N, ii + 1, M, j, S);
     666        S.erase(S.find(N[ii]));
     667    }
     668
     669    for (int jj = j; jj < M.size(); ++jj) {
     670        S.insert(M[jj]);
     671        addMultiplexSet(N, i + 1, M, jj + 1, S);
     672        S.erase(S.find(M[jj]));
     673    }
     674
     675}
     676
     677static inline ssize_t sqr(const ssize_t n) {
     678    return n * n;
    684679}
    685680
     
    696691    const unsigned n = num_vertices(mMultiplexSetGraph) - m;
    697692
     693    const auto start = read_cycle_counter();
     694
    698695    IndependentSetGraph G(n);
    699696
    700     std::unordered_map<MultiplexSetGraph::vertex_descriptor, IndependentSetGraph::vertex_descriptor> M;
    701697    MultiplexSetGraph::vertex_descriptor i = m;
    702698    graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end;
    703699    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
    704         M.emplace(i, *vi);
    705         G[*vi] = std::make_tuple(out_degree(i, mMultiplexSetGraph), 0, i);
     700        G[*vi] = std::make_pair(out_degree(i, mMultiplexSetGraph), 0);
    706701    }
    707702
     
    718713                for (auto ej = ei_begin; ej != ei; ++ej) {
    719714                    // Note: ei and ej are incoming edges. The source is the set vertex,
    720                     add_edge(M[source(*ei, mMultiplexSetGraph)], M[source(*ej, mMultiplexSetGraph)], G);
    721                 }
    722             }
    723         }
    724     }
     715                    add_edge(source(*ei, mMultiplexSetGraph) - m, source(*ej, mMultiplexSetGraph) - m, G);
     716                }
     717            }
     718        }
     719    }
     720
     721    boost::container::flat_set<IndependentSetGraph::vertex_descriptor> indices;
     722    indices.reserve(n);
     723    #ifdef USE_WEIGHTED_SELECTION
     724    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
     725        int neighbourhoodWeight = 0;
     726        int neighbours = 1;
     727        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
     728        for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) {
     729            ++neighbours;
     730            neighbourhoodWeight += std::get<0>(G[*ai]);
     731        }
     732        std::get<1>(G[*vi]) = (std::get<0>(G[*vi]) * neighbours) - neighbourhoodWeight;
     733        indices.insert(*vi);
     734    }
     735    #endif
     736
     737    const auto built_graph = read_cycle_counter();
     738
     739    // std::cerr << "G=(" << num_vertices(G) << ',' << num_edges(G) << ") built in " << (built_graph - start) << std::endl;
    725740
    726741    // Using WMIN from "A note on greedy algorithms for the maximum weighted independent set problem"
    727742    // (Note: look into minimum independent dominating set algorithms. It fits better with the ceil log2 + subset cost model.)
    728743
    729     std::vector<IndependentSetGraph::vertex_descriptor> A;
    730 
    731     while (num_vertices(G) > 0) {
     744    while (!indices.empty()) {
    732745
    733746        // Select a vertex vi whose weight as greater than the average weight of its neighbours ...
    734747        #ifdef USE_WEIGHTED_SELECTION
    735         int Tw = 0;
    736         for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
    737             int Vw = std::get<0>(G[*vi]) * (degree(*vi, G) + 1);
    738             int Nw = 0;
    739             graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
    740             std::tie(ai, ai_end) = adjacent_vertices(*vi, G);
    741             for (; ai != ai_end; ++ai) {
    742                 Nw += std::get<0>(G[*ai]);
    743             }
    744             Vw = std::max<int>(Vw - Nw, 0);
    745             Vw *= Vw;
    746             std::get<1>(G[*vi]) = Vw;
    747             Tw += Vw;
    748         }
    749 
    750         int w = RNGDistribution(0, Tw - 1)(rng);
    751         for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
    752             w -= std::get<1>(G[*vi]);
    753             if (w < 0) {
     748        int totalWeight = 0;
     749        for (auto vi = indices.begin(); vi != indices.end(); ++vi) {
     750            totalWeight += sqr(std::get<1>(G[*vi]));
     751        }
     752
     753        IndependentSetGraph::vertex_descriptor v = 0;
     754        ssize_t remainingWeight = RNGDistribution(0, totalWeight - 1)(rng);
     755        for (auto vi = indices.begin(); vi != indices.end(); ++vi) {
     756            remainingWeight -= sqr(std::max<int>(std::get<1>(G[*vi]), 0));
     757            if (remainingWeight < 0) {
     758                v = *vi;
    754759                break;
    755760            }
    756761        }
     762        assert (remainingWeight < 0);
     763
    757764        #else
    758         auto i = RNGDistribution(1, num_vertices(G))(rng);
     765        auto i = RNGDistribution(1, indices.size())(rng);
    759766        for (std::tie(vi, vi_end) = vertices(G); --i != 0; ++vi);
    760         #endif
    761767        assert (vi != vi_end);
    762 
    763         // Then add it to our set and remove it and its neighbourhood from G
    764         A.reserve(degree(*vi, G) + 1);
     768        #endif       
     769
    765770        // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively
    766771        // choose the set refered to by vi as one of our chosen independent sets.
    767         graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
    768         A.push_back(*vi);
    769         for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) {
    770             clear_out_edges(std::get<2>(G[*ai]), mMultiplexSetGraph);
    771             A.push_back(*ai);
    772         }
    773         for (auto u : A) {
     772        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end, aj, aj_end;
     773        for (std::tie(ai, ai_end) = adjacent_vertices(v, G); ai != ai_end; ) {
     774            const auto u = *ai++;
     775            assert (indices.count(u));
     776            indices.erase(indices.find(u));
     777            clear_out_edges(u + m, mMultiplexSetGraph);
     778            #ifdef USE_WEIGHTED_SELECTION
     779            const auto Wj = std::get<0>(G[u]);
     780            for (std::tie(aj, aj_end) = adjacent_vertices(u, G); aj != aj_end; ) {
     781
     782                // Let Vi be vertex i, Wi = weight of Vi, Di = degree of Vi, Ni = sum of the weights of vertices
     783                // adjacent to Vi, and Ai be the weight difference of Vi w.r.t. its neighbours. Initially,
     784
     785                //     Ai = (Wi * (Di + 1)) - Ni
     786
     787                // Suppose Vj is removed from G and is adjacent to Vi. Then,
     788
     789                //    Ai' = (Wi * (Di + 1 - 1)) - (Ni - Wj) = (Ai - Wi + Wj)
     790
     791                const auto w = *aj++;
     792                const auto Wi = std::get<0>(G[w]);
     793                auto & Ai = std::get<1>(G[w]);
     794                Ai = Ai - Wi + Wj;
     795                remove_edge(u, w, G);
     796            }
     797            #else
    774798            clear_vertex(u, G);
    775             remove_vertex(u, G);
    776         }
    777         A.clear();
    778     }
    779 
    780     for (unsigned i = m; i != (m + n); ++i) {
    781         if (out_degree(i, mMultiplexSetGraph) > 0) {
    782             std::cerr << out_degree(i, mMultiplexSetGraph) << std::endl;
    783         }
    784     }
     799            #endif
     800            remove_edge(v, u, G);
     801        }
     802        indices.erase(indices.find(v));
     803    }
     804
     805//    for (unsigned i = m; i != (m + n); ++i) {
     806//        if (out_degree(i, mMultiplexSetGraph) > 0) {
     807//            std::cerr << out_degree(i, mMultiplexSetGraph) << std::endl;
     808//        }
     809//    }
    785810
    786811    #ifndef NDEBUG
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4598 r4599  
    99#include <boost/graph/edge_list.hpp>
    1010#include <boost/container/flat_map.hpp>
     11#include <boost/container/flat_set.hpp>
    1112#include <boost/numeric/ublas/matrix.hpp>
    1213#include <random>
     
    2425    using PathGraph = boost::adjacency_matrix<boost::undirectedS>;
    2526    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    26     using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::listS, boost::undirectedS, std::tuple<int, int, MultiplexSetGraph::vertex_descriptor>>;
    27     using ChosenSet = std::vector<MultiplexSetGraph::vertex_descriptor>;
     27    using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>;
     28    using ChosenSet = boost::container::flat_set<MultiplexSetGraph::vertex_descriptor>;
    2829    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    2930    using Advances = std::vector<Advance *>;
     
    4445    void createMultiplexSetGraph();
    4546    bool generateMultiplexSets(RNG & rng);   
    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    void addMultiplexSet(const IndependentSet & N, const IndependentSet & M);
     48    void addMultiplexSet(const IndependentSet & N, int i, const IndependentSet & M, int j, ChosenSet & S);
    4849    void approxMaxWeightIndependentSet(RNG & rng);
    4950    void applySubsetConstraints();
     
    5152    void topologicalSort(PabloBlock & entry) const;
    5253    inline AutoMultiplexing()
    53     : mPathGraph(0) {
     54    : mPathGraph(0)
     55    {
    5456    }
    5557private:
     
    7375    Advances                mAdvance;   
    7476    MultiplexSetGraph       mMultiplexSetGraph;
    75     ChosenSet               mCurrentCombination;
    7677};
    7778
Note: See TracChangeset for help on using the changeset viewer.