Ignore:
Timestamp:
Jul 8, 2015, 8:54:04 AM (4 years ago)
Author:
nmedfort
Message:

Temporary check-in. Using simple trie to collect candidate multiplexing sets.

Location:
icGREP/icgrep-devel/icgrep
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4646 r4648  
    6161                                      cl::cat(cPabloOptimizationsOptions));
    6262#ifdef ENABLE_MULTIPLEXING
    63 static cl::opt<bool> EnableMultiplexing("enable-multiplexing", cl::init(true),
     63static cl::opt<bool> EnableMultiplexing("enable-multiplexing", cl::init(false),
    6464                                      cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
    6565                                      cl::cat(cPabloOptimizationsOptions));
  • icGREP/icgrep-devel/icgrep/icgrep-devel.files

    r4629 r4648  
    327327pablo/optimizers/pablo_bddminimization.h
    328328pablo/optimizers/pablo_bddminimization.cpp
     329pablo/carry_data.h
     330pablo/carry_manager.cpp
     331pablo/carry_manager.h
     332pablo/carry_data.cpp
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4646 r4648  
    2020using namespace boost::numeric::ublas;
    2121
    22 // #define PRINT_DEBUG_OUTPUT
     22#define PRINT_DEBUG_OUTPUT
    2323
    2424#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
     
    145145
    146146        RECORD_TIMESTAMP(start_topological_sort);
    147         am.topologicalSort(entry);
     147        // am.topologicalSort(entry);
    148148        RECORD_TIMESTAMP(end_topological_sort);
    149149        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
     
    429429    }
    430430
    431 
    432431    Ref(bdd);
    433432
     
    443442            stmt->replaceWith(stmt->getParent()->createZeroes());
    444443        }
    445         return Zero();
     444        bdd = Zero();
    446445    }
    447446
     
    550549
    551550    mAdvance.emplace_back(adv, Ik, Nk);
    552     Ref(Ck);
    553551    return Ck;
    554552}
     
    584582
    585583inline DdNode * AutoMultiplexing::And(DdNode * const x, DdNode * const y) {
    586     DdNode * var = Cudd_bddAnd(mManager, x, y);
    587     return var;
     584    return Cudd_bddAnd(mManager, x, y);
    588585}
    589586
    590587inline DdNode * AutoMultiplexing::Or(DdNode * const x, DdNode * const y) {
    591     DdNode * var = Cudd_bddOr(mManager, x, y);
    592     return var;
     588    return Cudd_bddOr(mManager, x, y);
    593589}
    594590
    595591inline DdNode * AutoMultiplexing::Xor(DdNode * const x, DdNode * const y) {
    596     DdNode * var = Cudd_bddXor(mManager, x, y);
    597     return var;
     592    return Cudd_bddXor(mManager, x, y);
    598593}
    599594
    600595inline DdNode * AutoMultiplexing::Not(DdNode * const x) const {
    601     DdNode * var = Cudd_Not(x);
    602     return var;
     596    return Cudd_Not(x);
    603597}
    604598
    605599inline DdNode * AutoMultiplexing::Ite(DdNode * const x, DdNode * const y, DdNode * const z) {
    606     DdNode * var = Cudd_bddIte(mManager, x, y, z);
    607     return var;
     600    return Cudd_bddIte(mManager, x, y, z);
    608601}
    609602
     
    635628bool AutoMultiplexing::generateMultiplexSets(RNG & rng, unsigned k) {
    636629
    637     using vertex_t = ConstraintGraph::vertex_descriptor;
    638630    using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
    639631
     
    642634    // have the same problem here but decomposed into subgraphs.
    643635
    644     IndependentSet M, N;
    645     auto remainingVerticies = num_vertices(mConstraintGraph);
    646     std::vector<degree_t> D(remainingVerticies);
     636    VertexVector M;
     637    std::vector<degree_t> D(num_vertices(mConstraintGraph));
    647638    M.reserve(15);
    648     N.reserve(15);
    649 
    650     mMultiplexSetGraph = MultiplexSetGraph(remainingVerticies);
     639
     640    Trie T;
     641    std::vector<ConstraintVertex> roots;
    651642
    652643    while (k) {
     
    657648            D[v] = d;
    658649            if (d == 0) {
    659                 N.push_back(v);
    660             }
    661         }
     650                M.push_back(v);
     651            }
     652        }
     653
     654        std::sort(M.begin(), M.end());
     655
     656        auto remainingVerticies = num_vertices(mConstraintGraph) - M.size();
    662657
    663658        for (;;) {
    664659
    665             addMultiplexSet(N, M);
     660            addCandidateSet(M, T, roots);
    666661
    667662            if (remainingVerticies == 0) {
     
    669664            }
    670665
    671             assert (N.size() > 0);
    672 
    673             // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing
    674             // at least one element from N, this will prevent us from adding the same multiplexing set again.
    675             M.insert(M.end(), N.begin(), N.end()); N.clear();
     666            auto entries = M.size();
    676667
    677668            do {
    678669                // Randomly choose a vertex in S and discard it.
    679670                assert (!M.empty());
    680                 const auto i = M.begin() + IntDistribution(0, M.size() - 1)(rng);
    681                 const vertex_t u = *i;
     671                const auto i = M.begin() + IntDistribution(0, entries - 1)(rng);
     672                const ConstraintVertex u = *i;
    682673                M.erase(i);
    683674                --remainingVerticies;
     675                --entries;
    684676                for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
    685                     const vertex_t v = target(e, mConstraintGraph);
     677                    const ConstraintVertex v = target(e, mConstraintGraph);
    686678                    if ((--D[v]) == 0) {
    687                         N.push_back(v);
    688                     }
    689                 }
    690             }
    691             while (N.empty() && remainingVerticies != 0);
    692         }
     679                        M.push_back(v);
     680                    }
     681                }
     682            }
     683            while ((M.size() == entries) && remainingVerticies != 0);
     684            // sort our new entries then merge the sorted lists
     685            std::sort(M.begin() + entries, M.end());
     686            std::inplace_merge(M.begin(), M.begin() + entries, M.end());
     687            assert (std::is_sorted(M.begin(), M.end()));
     688        }
     689        M.clear();
     690
     691        std::cerr << "T" << k << "=" << num_vertices(T) << std::endl;
    693692
    694693        if (--k == 0) {
    695694            break;
    696         }
    697 
    698         N.clear();
    699         M.clear();
    700     }
    701 
    702     return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph);
    703 }
    704 
    705 /** ------------------------------------------------------------------------------------------------------------- *
    706  * @brief addMultiplexSet
    707  * @param N an independent set
     695        }       
     696    }
     697
     698    // At this point T is a forest in which the set of any vertices from a source to a sink represents a
     699    // unique candidate set. Add all of them to the multiplex set graph.
     700
     701    if (num_vertices(T) == 0) {
     702        return false;
     703    }
     704
     705    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
     706    for (auto t : roots) {
     707        writeCandidateSet(t, T, M);
     708    }
     709    return true;
     710}
     711
     712/** ------------------------------------------------------------------------------------------------------------- *
     713 * @brief addCandidateSet
    708714 * @param M an independent set
    709  ** ------------------------------------------------------------------------------------------------------------- */
    710 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & N, const IndependentSet & M) {
    711 
    712     // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
    713     // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
    714 
    715     if ((N.size() + M.size()) >= 3) {
     715 * @param T the trie in which to encode this new set into
     716 * @param roots the roots (source nodes) for each tree in T
     717 ** ------------------------------------------------------------------------------------------------------------- */
     718inline void AutoMultiplexing::addCandidateSet(const VertexVector & M, Trie & T, VertexVector & roots) const {
     719    if (M.size() >= 3) {
     720        auto mi = M.cbegin();
     721        ConstraintVertex u = 0;
     722        for (ConstraintVertex s : roots) {
     723            if (T[s] == *mi) {
     724                u = s;
     725                while (++mi != M.cend()) {
     726                    bool not_found = true;
     727                    for (const auto e : make_iterator_range(out_edges(u, T))) {
     728                        const auto v = target(e, T);
     729                        if (T[v] == *mi) {
     730                            u = v;
     731                            not_found = false;
     732                            break;
     733                        }
     734                    }
     735                    if (not_found) {
     736                        break;
     737                    }
     738                }
     739                break;
     740            }
     741        }
     742        if (mi == M.cbegin()) {
     743            u = add_vertex(*mi++, T);
     744            roots.push_back(u);
     745        }
     746        for (; mi != M.cend(); ++mi) {
     747            const auto v = add_vertex(*mi, T);
     748            add_edge(u, v, T);
     749            u = v;
     750        }
     751    }
     752}
     753
     754/** ------------------------------------------------------------------------------------------------------------- *
     755 * @brief writeCandidateSet
     756 * @param M an independent set
     757 * @param T the trie in which to encode this new set into
     758 * @param roots the roots (source nodes) for each tree in T
     759 ** ------------------------------------------------------------------------------------------------------------- */
     760void AutoMultiplexing::writeCandidateSet(const Trie::vertex_descriptor t, const Trie & T, VertexVector & S) {
     761    S.push_back(T[t]);
     762    if (out_degree(t, T) == 0) {
    716763        const auto u = add_vertex(mMultiplexSetGraph);
    717         for (const auto x : N) {
    718             add_edge(u, x, mMultiplexSetGraph);
    719         }
    720         for (const auto y : M) {
    721             add_edge(u, y, mMultiplexSetGraph);
    722         }
    723     }
    724 }
     764        for (const auto v : S) {
     765            add_edge(u, v, mMultiplexSetGraph);
     766        }
     767    }
     768    else {
     769        for (const auto e : make_iterator_range(out_edges(t, T))) {
     770            writeCandidateSet(target(e, T), T, S);
     771        }
     772    }
     773    assert (S.back() == T[t]);
     774    S.pop_back();
     775}
     776
    725777
    726778/** ------------------------------------------------------------------------------------------------------------- *
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4646 r4648  
    2828    using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
    2929    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    30     using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>;
     30    using Trie = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::directedS, ConstraintVertex, boost::no_property>;
    3131    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    3232    // the Advance pointer, input BDD and the BDD variable of the i-th Advance
    3333    using AdvanceMap = boost::container::flat_map<const Statement *, unsigned>;
    3434    using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
    35     using IndependentSet = std::vector<ConstraintVertex>;
     35    using VertexVector = std::vector<ConstraintVertex>;
    3636    using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
    3737
     
    4545    bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
    4646    bool generateMultiplexSets(RNG & rng, unsigned k = 1);
    47     void addMultiplexSet(const IndependentSet & N, const IndependentSet & M);
     47    void addCandidateSet(const VertexVector & M, Trie & T, VertexVector & roots) const;
     48    void writeCandidateSet(const Trie::vertex_descriptor t, const Trie & T, VertexVector & S);
    4849    void selectMultiplexSets(RNG &);
    4950    void applySubsetConstraints();
Note: See TracChangeset for help on using the changeset viewer.