Ignore:
Timestamp:
May 28, 2015, 11:04:43 AM (4 years ago)
Author:
nmedfort
Message:

More work on multiplexing.

Location:
icGREP/icgrep-devel/icgrep/pablo
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/analysis/bdd/bdd.hpp

    r4581 r4582  
    134134    }
    135135
    136     inline BDD Contradiction() const {
     136    static inline BDD Contradiction() {
    137137        return BDD(0);
    138138    }
    139139
    140     inline BDD Tautology() const {
     140    static inline BDD Tautology() {
    141141        return BDD(1);
    142142    }
    143143
     144    inline BDD() : mRoot(0) {}
     145    inline BDD(const BDD & r) : mRoot(r.mRoot) {  }
     146
     147    inline ~BDD() { }
     148
    144149protected:
    145150
    146     inline BDD() : mRoot(0) {}
    147151    inline BDD(const index_type index) : mRoot(index) { }
    148     inline BDD(const BDD & r) : mRoot(r.mRoot) {  }
    149     inline ~BDD() { }
    150152
    151153private:
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4581 r4582  
    2222namespace pablo {
    2323
    24 static void AutoMultiplexing::optimize(PabloBlock & block) {
     24void AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
    2525    AutoMultiplexing am;
    26     Engine eng = am.initialize(vars, block);
    27     am.characterize(eng, block);
     26    Engine eng = am.initialize(input, entry);
     27    am.characterize(eng, entry);
    2828    am.createMultiplexSetGraph();
    29     RNG rng(std::random_device()());
     29    std::random_device rd;
     30    RNG rng(rd());
    3031    if (am.generateMultiplexSets(rng)) {
    31         am.approxMaxWeightIndependentSet();
     32        am.approxMaxWeightIndependentSet(rng);
    3233        am.applySubsetConstraints();
    3334        am.multiplexSelectedIndependentSets();
    34         am.topologicalSort();
     35        am.topologicalSort(entry);
    3536    }
    3637}
     
    4647Engine AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
    4748
    48     flat_map<PabloAST *, unsigned> map;
     49    flat_map<const PabloAST *, unsigned> map;
    4950    for (const Var * var : vars) {
    5051        map.emplace(var, 0);
     
    6970            switch (stmt->getClassTypeId()) {
    7071                case PabloAST::ClassTypeId::Advance:
    71                     mAdvance.push_back(stmt);
     72                    mAdvance.push_back(const_cast<Advance*>(cast<Advance>(stmt)));
    7273                    map.emplace(stmt, m++);
    7374                case PabloAST::ClassTypeId::Call:
     
    101102    }
    102103
    103     for (const Statement * stmt = entry.front(), m = 0, n = m; ; ) {
     104    m = 0;
     105    n = m;
     106    const Statement * stmt = entry.front();
     107    for (;;) {
    104108        while ( stmt ) {
    105109            unsigned u;
     
    113117            }
    114118            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    115                 PabloAST * const op = stmt->getOperand(i);
     119                const PabloAST * const op = stmt->getOperand(i);
    116120                if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
    117121                    continue;
     
    192196 * Scan through the program and iteratively compute the BDDs for each statement.
    193197 ** ------------------------------------------------------------------------------------------------------------- */
    194 void AutoMultiplexing::characterize(Engine & engine, const PabloBlock & entry) {
     198void AutoMultiplexing::characterize(Engine & engine, PabloBlock & entry) {
    195199
    196200    std::vector<std::pair<BDD, BDD>> advances; // the input BDD and the BDD variable of the i-th Advance
    197     std::stack<const Statement *> scope;
     201    std::stack<Statement *> scope;
    198202
    199203    advances.reserve(mAdvance.size());
     
    202206
    203207    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    204     for (const Statement * stmt = entry.front(); ; ) {
     208    for (Statement * stmt = entry.front(); ; ) {
    205209        while ( stmt ) {
    206210
     
    215219            }
    216220
    217             BDD bdd = false;
     221            BDD bdd; // defaults to false
    218222
    219223            // Map our operands to the computed BDDs
     
    258262                    // would be ¬(ScanThru(c,m) √ m) but are there others that would be harder to predict?
    259263                case PabloAST::ClassTypeId::MatchStar:
    260                     if (LLVM_UNLIKELY(input[0] == false || input[1] == false)) {
     264                    if (LLVM_UNLIKELY(input[0].isFalse() || input[1].isFalse())) {
    261265                        break;
    262266                    }
     
    266270                    break;
    267271                case PabloAST::ClassTypeId::Advance:
    268                     if (LLVM_LIKELY(input[0] != false)) {
     272                    if (LLVM_LIKELY(!input[0].isFalse())) {
    269273
    270274                        // When we built the path graph, we constructed it in the same order; hense the row/column of
     
    299303                                    f->second = engine.applyAnd(f->second, engine.applyNot(Vk));
    300304
    301                                     // If these advances are not from the same scope, we cannot safely multiplex them even if they're
    302                                     // mutually exclusive.
     305                                    // If these advances are not from the same scope, we cannot safely multiplex them even if
     306                                    // they're mutually exclusive.
    303307                                    constrained = (stmt->getParent() != adv->getParent());
    304308                                }
     
    310314                                        // i-th advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the
    311315                                        // multiplex set graph if Advance_i and Advance_k happen to be mutually exclusive set.
    312                                         add_edge(k, i, mSubsetGraph);
     316                                        mSubsetGraph.emplace_back(k, i);
    313317                                        continue;
    314318                                    }
    315319                                    else if (LLVM_UNLIKELY(Ii == C)) {
    316                                         add_edge(i, k, mSubsetGraph);
     320                                        mSubsetGraph.emplace_back(i, k);
    317321                                        continue;
    318322                                    }
    319 
    320323                                }
    321324                            }
     
    332335                    // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
    333336                    // eliminate the need for looking it up again.
    334                     advances.emplace_back(cast<Advance>(stmt), Ik);
     337                    advances.emplace_back(input[0], bdd);
    335338
    336339                    testContradiction = false;
     
    338341                    break;
    339342            }
    340             if (LLVM_UNLIKELY(testContradiction && engine.satOne(bdd) == false)) {
     343            if (LLVM_UNLIKELY(testContradiction && engine.satOne(bdd).isFalse())) {
    341344                stmt = stmt->replaceWith(entry.createZeroes());
    342345            }
    343346            else {
    344                 mCharacterizationMap.insert(std::make_pair(stmt, bdd));
     347                mCharacterizationMap.emplace(stmt, bdd);
    345348                stmt = stmt->getNextNode();
    346349            }
     
    436439
    437440    const unsigned m = num_vertices(mConstraintGraph);
    438     const unsigned n = num_vertices(mMultiplexSetGraph) - m;
     441    const unsigned n = num_vertices(mMultiplexSetGraph);
    439442
    440443    IndependentSetGraph G(n);
    441444
    442445    // Record the "weight" of this independent set vertex
    443     for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) {
    444         G[i] = out_degree(m + i, mMultiplexSetGraph);
    445     }
    446     // Add in any edges based on the adjacencies in the multiplex set graph
    447     for (MultiplexSetGraph::vertex_descriptor i = 0; i != m; ++i) {
     446    for (IndependentSetGraph::vertex_descriptor i = m; i != n; ++i) {
     447        G[i] = out_degree(i, mMultiplexSetGraph);
     448    }
     449
     450    // Make all vertices in G adjacent if they are mutually adjacent to a set vertex in S.
     451    for (MultiplexSetGraph::vertex_descriptor i = m; i != n; ++i) {
    448452        graph_traits<MultiplexSetGraph>::in_edge_iterator ei, ei_end;
    449453        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
    450454        for (; ei != ei_end; ++ei) {
    451455            for (auto ej = ei; ej != ei; ++ej) {
    452                 add_edge(*ei - m, *ej - m, G);
     456                add_edge(source(*ei, mMultiplexSetGraph), source(*ej, mMultiplexSetGraph), G);
    453457            }
    454458        }
     
    506510    // Add in any edges from our subset constraints to M that are within the same set.
    507511    bool hasSubsetConstraint = false;
    508     graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
    509     for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
    510         const auto u = source(*ei, mSubsetGraph);
    511         const auto v = target(*ei, mSubsetGraph);
     512    for (const auto & ei : mSubsetGraph) {
     513        const auto u = ei.first;
     514        const auto v = ei.second;
    512515        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
    513516        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
     
    516519            auto w = target(*ej, mMultiplexSetGraph);
    517520            // Only check (v, w) if w is a "set vertex".
    518             if (w >= (n - m) && edge(v, w).second) {
     521            if (w >= (n - m) && edge(v, w, mMultiplexSetGraph).second) {
    519522                add_edge(u, v, mMultiplexSetGraph);
    520523                hasSubsetConstraint = true;
     
    552555                            D.set(v);
    553556                            if (out_degree(v, mMultiplexSetGraph) == 0) {
    554                                 V.push(v);
     557                                V.push_back(v);
    555558                            }
    556559                            else {
     
    571574                    PabloBlock * pb = adv->getParent();
    572575
     576                    #define CHOOSE(A,B,C) (isa<Statement>(A) ? cast<Statement>(A) : (isa<Statement>(B) ? cast<Statement>(B) : C))
     577
    573578                    for (auto i : V) {
    574579                        Q.push(mAdvance[i]->getOperand(0));
     
    577582                        PabloAST * a1 = Q.front(); Q.pop();
    578583                        PabloAST * a2 = Q.front(); Q.pop();
    579                         pb->setInsertPoint(a2);
     584                        pb->setInsertPoint(CHOOSE(a2, a1, adv));
    580585                        Q.push(pb->createOr(a1, a2));
    581586                    }
     
    600605                        PabloAST * a1 = Q.front(); Q.pop();
    601606                        PabloAST * a2 = Q.front(); Q.pop();
    602                         pb->setInsertPoint(cast<Statement>(a2));
     607                        pb->setInsertPoint(CHOOSE(a2, a1, adv));
    603608                        Q.push(pb->createOr(a1, a2));
    604609                    }
     
    672677                    }
    673678                }
     679                Advance * const adv = mAdvance[V[j]];
    674680                // TODO: figure out a way to determine whether we're creating a duplicate value below.
    675681                // The expression map findOrCall ought to work conceptually but the functors method
     
    678684                    PabloAST * a1 = T.front(); T.pop();
    679685                    PabloAST * a2 = T.front(); T.pop();
    680                     pb->setInsertPoint(cast<Statement>(a2));
     686                    pb->setInsertPoint(CHOOSE(a2, a1, adv));
    681687                    T.push(pb->createOr(a1, a2));
    682688                }
    683                 mAdvance[V[j]]->setOperand(0, T.front()); T.pop();
     689                adv->setOperand(0, T.front()); T.pop();
    684690            }
    685691
     
    693699            // Now construct the demuxed values and replaces all the users of the original advances with them.
    694700            for (unsigned i = 0; i != n; ++i) {
     701                Advance * adv = mAdvance[V[i]];
    695702                for (unsigned j = 0; j != m; ++j) {
    696703                    if (((i + 1) & (1 << j)) != 0) {
     
    704711                    PabloAST * a1 = T.front(); T.pop();
    705712                    PabloAST * a2 = T.front(); T.pop();
    706                     pb->setInsertPoint(cast<Statement>(a2));
     713                    pb->setInsertPoint(CHOOSE(a2, a1, adv));
    707714                    T.push(pb->createAnd(a1, a2));
    708715                }
     
    712719                    PabloAST * a1 = T.front(); T.pop();
    713720                    PabloAST * a2 = T.front(); T.pop();
    714                     pb->setInsertPoint(cast<Statement>(a2));
     721                    pb->setInsertPoint(CHOOSE(a2, a1, adv));
    715722                    F.push(pb->createOr(a1, a2));
    716723                }
     
    719726                PabloAST * const demux = pb->createAnd(T.front(), pb->createNot(F.front()), "demux"); T.pop(); F.pop();
    720727                for (PabloAST * use : users[i]) {
    721                     cast<Statement>(use)->replaceUsesOfWith(mAdvance[V[j]], demux);
     728                    cast<Statement>(use)->replaceUsesOfWith(adv, demux);
    722729                }
    723730            }
     
    752759    std::stack<Statement *> scope;
    753760
    754     Statement * ip = nullptr, first, stmt;
     761    Statement * ip = nullptr;
     762    Statement * first;
     763    Statement * stmt;
    755764
    756765    for (first = stmt = entry.front(); ; ) {
     
    776785                    continue;
    777786                }
    778                 add_edge(f->second, u);
     787                add_edge(f->second, u, G);
    779788            }
    780789            if (in_degree(u, G) == 0) {
     
    821830    M.clear();
    822831}
     832
     833} // end of namespace pablo
     834
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4581 r4582  
    1818class AutoMultiplexing {
    1919
    20     using CharacterizationMap = boost::container::flat_map<PabloAST *, bdd::BDD>;
    21     using ConstraintGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::directedS>;
     20    using CharacterizationMap = boost::container::flat_map<const PabloAST *, bdd::BDD>;
     21    using ConstraintGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    2222    using PathGraph = boost::adjacency_matrix<boost::undirectedS>;
    23     using SubsetGraph = boost::edge_list<std::pair<unsigned, unsigned>>;
    2423    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    2524    using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS, unsigned>;
     25    using SubsetGraph = std::vector<std::pair<MultiplexSetGraph::vertex_descriptor, MultiplexSetGraph::vertex_descriptor>>;
    2626    using Advances = std::vector<Advance *>;
    27     using TopologicalSortGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::directedS, PabloAST *>;
     27    using TopologicalSortGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
    2828    using TopologicalSortQueue = std::queue<TopologicalSortGraph::vertex_descriptor>;
    29     using TopologicalSortMap = boost::container::flat_map<Statement *, TopologicalSortGraph::vertex_descriptor>;
     29    using TopologicalSortMap = boost::container::flat_map<PabloAST *, TopologicalSortGraph::vertex_descriptor>;
    3030
    3131    using RNG = std::mt19937;
     
    3737
    3838public:
    39     static void optimize(PabloBlock & block);
     39    static void optimize(const std::vector<Var *> & input, PabloBlock & entry);
    4040protected:
    4141    bdd::Engine initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
    42     void characterize(bdd::Engine & engine, const PabloBlock & entry);
     42    void characterize(bdd::Engine & engine, PabloBlock &entry);
    4343    void createMultiplexSetGraph();
    4444    bool generateMultiplexSets(RNG & rng);   
Note: See TracChangeset for help on using the changeset viewer.