Ignore:
Timestamp:
May 24, 2015, 4:18:10 PM (4 years ago)
Author:
nmedfort
Message:

More multiplexing work.

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

Legend:

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

    r4571 r4577  
    44#include <llvm/ADT/DenseMap.h>
    55#include <llvm/ADT/DenseSet.h>
     6#include <llvm/ADT/BitVector.h>
    67#include <stack>
    78#include <queue>
     
    1011#include <boost/container/flat_set.hpp>
    1112#include <boost/numeric/ublas/matrix.hpp>
     13
    1214
    1315using namespace llvm;
     
    6769            switch (stmt->getClassTypeId()) {
    6870                case PabloAST::ClassTypeId::Advance:
    69                     mIndexMap.emplace(stmt, m);
     71                    mAdvance.emplace(stmt, m);
    7072                    map.emplace(stmt, ++m);
    7173                case PabloAST::ClassTypeId::Call:
     
    105107            if (isa<Advance>(stmt)) {               
    106108                u = ++n;
    107                 assert (mIndexMap.count(stmt) != 0 && mIndexMap[stmt] == (u - 1));
     109                mAdvance.push_back(cast<Advance>(stmt));
     110                assert (mAdvance.size() == n);
    108111            }
    109112            else {
     
    195198    std::vector<std::pair<Advance *, BDD>> advances;
    196199    std::stack<const Statement *> scope;
     200
     201    advances.reserve(mAdvance.size());
    197202
    198203    unsigned variables = 0;
     
    228233            }
    229234
     235            bool testContradiction = true;
     236
    230237            switch (stmt->getClassTypeId()) {
    231238                case PabloAST::ClassTypeId::Assign:
     
    258265                    }
    259266                case PabloAST::ClassTypeId::Call:
     267                    testContradiction = false;
    260268                    bdd = engine.var(variables++);
    261269                    break;
     
    273281                        // the path graph is equivalent to the index.
    274282
     283                        const BDD A = input[0];
    275284                        const unsigned k = advances.size();
    276285
    277                         assert (mIndexMap.count(stmt) != 0 && mIndexMap[stmt] == k);
     286                        assert (stmt == mAdvance[k - 1]);
    278287
    279288                        for (unsigned i = 0; i != k; ++i) {
    280289
    281290                            Advance * adv;
    282                             BDD eq;
    283                             std::tie(adv, eq) = advances[i];
     291                            BDD B;
     292                            std::tie(adv, B) = advances[i];
     293
     294                            bool mutuallyExclusive = false;
     295                            bool constrained = false;
    284296
    285297                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    286298                            if ((stmt->getOperand(1) != adv->getOperand(1)) && !edge(k, i, mPathGraph).second) {
    287 
    288                                 const BDD C = engine.applyAnd(input[0], eq); // do we need to simplify this to identify subsets?
     299                                const BDD C = engine.applyAnd(A, B); // do we need to simplify this to identify subsets?
    289300                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    290                                 if (engine.satOne(C).isFalse()) {
    291                                     auto f = mCharacterizationMap.find(adv);
    292                                     // build up our BDD equation for the k-th Advance
    293                                     bdd = engine.applyAnd(bdd, engine.applyNot(f->second));
    294                                     // but only
    295                                     f->second = engine.applyAnd(f->second, engine.applyNot(var));
    296                                     continue;
    297                                 }
    298                                 else if (LLVM_UNLIKELY(input[0] == C)) {
    299                                     add_edge(k, i, mSubsetGraph);
    300                                     continue;
    301                                 }
    302                                 else if (LLVM_UNLIKELY(eq == C)) {
    303                                     add_edge(i, k, mSubsetGraph);
    304                                     continue;
    305                                 }
    306                             }
    307                             // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
    308                             // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
    309                             add_edge(i, k, mConstraintGraph);
    310                             // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
    311                             // eliminate the need for looking it up again.
    312                             advances.emplace_back(cast<Advance>(stmt), input[0]);
     301                                mutuallyExclusive = (engine.satOne(C) == false);
     302
     303                                constrained = !mutuallyExclusive || (stmt->getParent() != adv->getParent()) ;
     304                            }
     305
     306                            if (mutuallyExclusive) {
     307                                auto f = mCharacterizationMap.find(adv);
     308                                // build up our BDD equation for the k-th advance
     309                                bdd = engine.applyAnd(bdd, engine.applyNot(f->second));
     310                                // but only mark the other advance as being mutually exclusive with the k-th *variable*
     311                                f->second = engine.applyAnd(f->second, engine.applyNot(var));
     312                            }
     313
     314                            if (constrained) {
     315                                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
     316                                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
     317                                add_edge(i, k, mConstraintGraph);
     318                            }
     319                            else if (LLVM_UNLIKELY(A == C)) {
     320                                // If A = C and C = A ∩ B then A (the input to the k-th advance) is a *subset* of B (the input
     321                                // of the i-th advance). Record this in the subset graph with the arc (k,i).
     322                                add_edge(k, i, mSubsetGraph);
     323                                continue;
     324                            }
     325                            else if (LLVM_UNLIKELY(B == C)) {
     326                                add_edge(i, k, mSubsetGraph);
     327                                continue;
     328                            }
    313329                        }
    314                     }
    315                     break;
    316             }
    317             if (LLVM_UNLIKELY(engine.satOne(bdd) == false)) {
     330
     331                        // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
     332                        // eliminate the need for looking it up again.
     333                        advances.emplace_back(cast<Advance>(stmt), A);
     334
     335                        testContradiction = false;
     336                    }
     337                    break;
     338            }
     339            if (LLVM_UNLIKELY(testContradiction && engine.satOne(bdd) == false)) {
    318340                stmt = stmt->replaceWith(entry.createZeroes());
    319341            }
     
    388410 * @param set an independent set
    389411 ** ------------------------------------------------------------------------------------------------------------- */
    390 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & set) {
     412inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & S) {
    391413
    392414    // At this stage, the mapping graph is a directed bipartite graph that is used to show relationships between
    393     // the advance vertices and a "set vertex" for each independent set we find from "generateMultiplexSets".
    394 
     415    // the "set vertex" for each independent set and its members. We obtain these from "generateMultiplexSets".
     416
     417    // Question: should we enumerate the power set of S?
    395418    const auto v = add_vertex(mMappingGraph);
    396     for (auto u : set) {
    397         add_edge(u, v, mMappingGraph);
     419    for (auto u : S) {
     420        add_edge(v, u, mMappingGraph);
    398421    }
    399422}
     
    414437    // Record the "weight" of this independent set vertex
    415438    for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) {
    416         G[i] = in_degree(m + i, mMappingGraph);
     439        G[i] = out_degree(m + i, mMappingGraph);
    417440    }
    418441    // Add in any edges based on the adjacencies in the mapping graph
    419442    for (MappingGraph::vertex_descriptor i = 0; i != m; ++i) {
    420         graph_traits<MappingGraph>::out_edge_iterator ei, ei_end;
    421         std::tie(ei, ei_end) = out_edges(i, mMappingGraph);
     443        graph_traits<MappingGraph>::in_edge_iterator ei, ei_end;
     444        std::tie(ei, ei_end) = in_edges(i, mMappingGraph);
    422445        for (; ei != ei_end; ++ei) {
    423446            for (auto ej = ei; ej != ei; ++ej) {
     
    427450    }
    428451    // Process the graph using the greedy method of "Approximation Algorithms for the Weighted Independent Set Problem" (2005)
     452    // (Note: look into minimum independent dominating set algorithms. It fits better with the log2 + subset relationship cost model.)
    429453    std::vector<IndependentSetGraph::vertex_descriptor> S;
    430454    std::vector<bool> removed(n, false);
    431455    for (;;) {
    432         // Select the miminum weight vertex
     456        // Let S be the set of verticies of miminal weight
    433457        graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end;
    434458        std::tie(vi, vi_end) = vertices(G);
     
    450474            break;
    451475        }
    452 
     476        // Select u from S
    453477        const auto u = S[S.size() == 1 ? 0 : RNGDistribution(0, S.size() - 1)(rng)];
    454         // Remove it and its adjacencies from G; clear the adjacent set vertices from the mapping graph
     478        // Remove u and its adjacencies from G; clear the adjacent set vertices from the mapping graph. This will effectively
     479        // choose the set refered to by u as one of our chosen independent sets and discard any other sets that contain one
     480        // of the vertices in the chosen set.
    455481        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
    456482        std::tie(ai, ai_end) = adjacent_vertices(u, G);
    457483        for (; ai != ai_end; ++ai) {
    458484            removed[*ai] = true;
    459             clear_in_edges(m + *ai, mMappingGraph);
     485            clear_out_edges(m + *ai, mMappingGraph);
    460486        }
    461487        removed[u] = true;
     
    468494void AutoMultiplexing::applySubsetConstraints() {
    469495
    470     // The mapping graph now contains edges denoting the set relationships of our independent sets.
    471     // Add in any edges from our subset constraints to the Mapping Graph that are within the same set.
    472 
     496    // When entering thus function, the mapping graph M is a bipartite DAG with edges denoting the set
     497    // relationships of our independent sets.
     498    const unsigned m = num_vertices(mConstraintGraph);
     499    const unsigned n = num_vertices(mMappingGraph);
     500
     501    // Add in any edges from our subset constraints to M that are within the same set.
     502    bool hasSubsetConstraint = false;
    473503    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
    474504    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
    475505        const auto u = source(*ei, mSubsetGraph);
    476506        const auto v = target(*ei, mSubsetGraph);
    477         graph_traits<MappingGraph>::out_edge_iterator ej, ej_end;
    478         for (std::tie(ej, ej_end) = out_edges(u, mMappingGraph); ej != ej_end; ++ej) {
    479             // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
    480             // "set vertex". Add the edge between the vertices.
    481             if (edge(v, target(*ej, mMappingGraph)).second) {
     507        graph_traits<MappingGraph>::in_edge_iterator ej, ej_end;
     508        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
     509        // "set vertex". Add the edge between the vertices.
     510        for (std::tie(ej, ej_end) = in_edges(u, mMappingGraph); ej != ej_end; ++ej) {
     511            auto w = target(*ej, mMappingGraph);
     512            // Only check (v, w) if w is a "set vertex".
     513            if (w >= (n - m) && edge(v, w).second) {
    482514                add_edge(u, v, mMappingGraph);
    483             }
    484         }
    485     }
    486 
     515                hasSubsetConstraint = true;
     516            }
     517        }
     518    }
     519
     520    if (LLVM_UNLIKELY(hasSubsetConstraint)) {
     521        // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices
     522        // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST.
     523        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
     524
     525        std::vector<MappingGraph::vertex_descriptor> V;
     526        std::stack<MappingGraph::vertex_descriptor> S;
     527        std::queue<PabloAST *> Q;
     528        BitVector D(n - m, 0);
     529
     530        for (auto i = m; i != n; ++i) {
     531            graph_traits<MappingGraph>::out_edge_iterator ei, ei_end;
     532            // For each member of a "set vertex" ...
     533            std::tie(ei, ei_end) = out_edges(i, mMappingGraph);
     534            for (; ei != ei_end; ++ei) {
     535                const auto s = source(*ei, mMappingGraph);
     536                if (out_degree(s, mMappingGraph) != 0) {
     537                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
     538                    // consisting of all sinks w.r.t. vertex s.
     539                    auto u = s;
     540                    for (;;) {
     541                        graph_traits<MappingGraph>::out_edge_iterator ej, ej_end;
     542                        for (std::tie(ej, ej_end) = out_edges(u, mMappingGraph); ej != ej_end; ++ej) {
     543                            auto v = target(*ej, mMappingGraph);
     544                            if (D.test(v)) {
     545                                continue;
     546                            }
     547                            D.set(v);
     548                            if (out_degree(v, mMappingGraph) == 0) {
     549                                V.push(v);
     550                            }
     551                            else {
     552                                S.push(v);
     553                            }
     554                        }
     555                        if (S.empty()) {
     556                            break;
     557                        }
     558                        u = S.top();
     559                        S.pop();
     560                    }
     561                    D.clear();
     562                    // Now in order for these advances to be mutually exclusive, the input to A_s must be masked
     563                    // with the complement of each advance indicated by V.
     564
     565                    Advance * adv = mAdvance[s];
     566                    PabloBlock * pb = adv->getParent();
     567
     568                    for (auto i : V) {
     569                        Q.push(mAdvance[i]->getOperand(0));
     570                    }
     571                    pb->setInsertPoint(adv->getPrevNode());
     572                    while (Q.size() > 1) {
     573                        PabloAST * a1 = Q.front(); Q.pop();
     574                        PabloAST * a2 = Q.front(); Q.pop();
     575                        Q.push(pb->createOr(a1, a2));
     576                    }
     577                    assert (Q.size() == 1);
     578
     579                    PabloAST * const mask = pb->createNot(Q.front()); Q.pop();
     580                    adv->setOperand(0, pb->createAnd(adv->getOperand(0), mask, "subset_in"));
     581
     582                    // Similar to the above, we're going to OR together the result of each advance,
     583                    // including s. This will restore the advanced variable back to its original state.
     584
     585                    // Gather the original users to this advance. We'll be manipulating it shortly.
     586                    Statement::Users U(adv->users());
     587
     588                    // Add s to V and sort the list; it'll be closer to being in topological order.
     589                    V.push_back(s);
     590                    std::sort(V.begin(), V.end());
     591                    for (auto i : V) {
     592                        Q.push(mAdvance[i]);
     593                    }
     594                    while (Q.size() > 1) {
     595                        PabloAST * a1 = Q.front(); Q.pop();
     596                        PabloAST * a2 = Q.front(); Q.pop();
     597                        pb->setInsertPoint(cast<Statement>(a2));
     598                        Q.push(pb->createOr(a1, a2));
     599                    }
     600                    assert (Q.size() == 1);
     601                    PabloAST * const input = Q.front(); Q.pop();
     602
     603                    for (PabloAST * use : U) {
     604                        if (LLVM_LIKELY(isa<Statement>(use))) {
     605                            cast<Statement>(use)->replaceUsesOfWith(adv, input);
     606                        }
     607                    }
     608
     609                    pb->setInsertPoint(pb->back());
     610
     611                    V.clear();
     612
     613                }
     614            }
     615        }
     616    }
    487617}
    488618
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4571 r4577  
    2424    using MappingGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    2525    using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS, unsigned>;
    26     using IndexMap = boost::container::flat_map<PabloAST *, unsigned>;
     26    using Advances = std::vector<Advance *>;
    2727
    2828    using RNG = std::mt19937;
     
    5151    ConstraintGraph         mConstraintGraph;
    5252    SubsetGraph             mSubsetGraph;
    53     IndexMap                mIndexMap;
     53    Advances                mAdvance;
    5454    MappingGraph            mMappingGraph;
    5555};
Note: See TracChangeset for help on using the changeset viewer.