Changeset 4579 for icGREP/icgrep-devel


Ignore:
Timestamp:
May 26, 2015, 4:56:01 PM (4 years ago)
Author:
nmedfort
Message:

More work on multiplexing

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

Legend:

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

    r4578 r4579  
    1212#include <boost/numeric/ublas/matrix.hpp>
    1313#include <include/simd-lib/builtins.hpp>
    14 #include <expression_map.hpp>
     14// #include <pablo/expression_map.hpp>
    1515
    1616using namespace llvm;
     
    2626    Engine eng = am.initialize(vars, block);
    2727    am.characterize(eng, block);
    28     am.createMappingGraph();
     28    am.createMultiplexSetGraph();
    2929    RNG rng(std::random_device()());
    3030    if (am.generateMultiplexSets(rng)) {
     
    4646Engine AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
    4747
    48     unsigned m = 1;
    49     unsigned variables = 0;
    50 
    5148    flat_map<PabloAST *, unsigned> map;
    5249    for (const Var * var : vars) {
     
    5754
    5855    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    59     unsigned n = 0;
     56    unsigned n = 0, m = 1, variables = 0;
    6057    for (const Statement * stmt = entry.front(); ; ) {
    6158        while ( stmt ) {
     
    7269            switch (stmt->getClassTypeId()) {
    7370                case PabloAST::ClassTypeId::Advance:
    74                     mAdvance.emplace(stmt, m);
    75                     map.emplace(stmt, ++m);
     71                    mAdvance.push_back(stmt);
     72                    map.emplace(stmt, m++);
    7673                case PabloAST::ClassTypeId::Call:
    7774                case PabloAST::ClassTypeId::ScanThru:
     
    9895    // which advances ought to be multiplexed.
    9996
    100     matrix<bool> G(n, m);
     97    matrix<bool> G(n, m); // Let G be a matrix with n rows of m (Advance) elements
    10198    G.clear();
    10299    for (unsigned i = 0; i != m; ++i) {
     
    104101    }
    105102
    106     for (const Statement * stmt = entry.front(), n = 0; ; ) {
     103    for (const Statement * stmt = entry.front(), m = 0, n = m; ; ) {
    107104        while ( stmt ) {
    108             // Fill in the transitive closure G ...
    109105            unsigned u;
    110             if (isa<Advance>(stmt)) {               
     106            if (isa<Advance>(stmt)) {
     107                assert (mAdvance[m] == stmt);
     108                u = ++m;
     109            }
     110            else {
    111111                u = ++n;
    112                 mAdvance.push_back(cast<Advance>(stmt));
    113                 assert (mAdvance.size() == n);
    114             }
    115             else {
    116                 u = ++m;
    117112                map.emplace(stmt, u);
    118113            }
     
    123118                }
    124119                const unsigned v = map[op];
    125                 for (unsigned w = 0; w != n; ++w) {
     120                for (unsigned w = 0; w != m; ++w) {
    126121                    G(v, w) |= G(u, w);
    127122                }
    128123            }
     124            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     125                // Set the next statement to be the first statement of the inner scope
     126                // and push the next statement of the current statement into the stack.
     127                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     128                scope.push(stmt->getNextNode());
     129                stmt = nested.front();
     130                assert (stmt);
     131                continue;
     132            }
     133            stmt = stmt->getNextNode();
     134        }
     135        if (scope.empty()) {
     136            break;
     137        }
     138        stmt = scope.top();
     139        scope.pop();
     140    }
     141
     142    // Record our transitive closure in the path graph and remove any reflexive-loops
     143    mPathGraph = PathGraph(m - 1);
     144    for (unsigned i = 1; i != m; ++i) {
     145        for (unsigned j = 1; j != m; ++j) {
     146            if (G(i, j)) {
     147                add_edge(i - 1, j - 1, mPathGraph);
     148            }
     149        }
     150        G(i, i) = false;
     151    }
     152
     153    // Now take the transitive reduction of G
     154    for (unsigned j = 1; j != m; ++j) {
     155        for (unsigned i = 1; i != m; ++i) {
     156            if (G(i, j)) {
     157                // Eliminate any unecessary arcs not covered by a longer path
     158                for (unsigned k = 0; k != m; ++k) {
     159                    G(i, k) = G(j, k) ? false : G(i, k);
     160                }
     161            }
     162        }
     163    }
     164
     165    // And now transcribe it into our base constraint graph
     166    mConstraintGraph = ConstraintGraph(m - 1);
     167    for (unsigned j = 1; j != m; ++j) {
     168        for (unsigned i = 1; i != m; ++i) {
     169            if (G(i, j)) {
     170                add_edge(i - 1, j - 1, mConstraintGraph);
     171            }
     172        }
     173    }
     174
     175    // Initialize the BDD engine ...
     176    Engine engine(variables + vars.size());
     177    mCharacterizationMap.emplace(entry.createZeroes(), BDD::Contradiction());
     178    mCharacterizationMap.emplace(entry.createOnes(), BDD::Tautology());
     179    // Order the variables so the input Vars are pushed to the end; they ought to
     180    // be the most complex to resolve.
     181    for (const Var * var : vars) {
     182        mCharacterizationMap.emplace(var, engine.var(variables++));
     183    }
     184    return engine;
     185}
     186
     187/** ------------------------------------------------------------------------------------------------------------- *
     188 * @brief characterize
     189 * @param engine the BDD engine
     190 * @param vars the input vars for this program
     191 *
     192 * Scan through the program and iteratively compute the BDDs for each statement.
     193 ** ------------------------------------------------------------------------------------------------------------- */
     194void AutoMultiplexing::characterize(Engine & engine, const PabloBlock & entry) {
     195
     196    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;
     198
     199    advances.reserve(mAdvance.size());
     200
     201    unsigned variables = 0;
     202
     203    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     204    for (const Statement * stmt = entry.front(); ; ) {
     205        while ( stmt ) {
     206
    129207            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    130208                // Set the next statement to be the first statement of the inner scope and push the
     
    136214                continue;
    137215            }
    138             stmt = stmt->getNextNode();
    139         }
    140         if (scope.empty()) {
    141             break;
    142         }
    143         stmt = scope.top();
    144         scope.pop();
    145     }
    146 
    147     // Record our transitive closure in the path graph and remove any reflexive-loops
    148     mPathGraph = PathGraph(n);
    149     for (unsigned i = 0; i != n; ++i) {
    150         for (unsigned j = 0; j != n; ++j) {
    151             if (G(i, j)) {
    152                 add_edge(i, j, mPathGraph);
    153             }
    154         }
    155         G(i, i) = false;
    156     }
    157 
    158     // Now take the transitive reduction of G
    159     for (unsigned j = 1; j != n; ++j) {
    160         for (unsigned i = 1; i != n; ++i) {
    161             if (G(i, j)) {
    162                 // Eliminate any unecessary arcs not covered by a longer path
    163                 for (unsigned k = 0; k != m; ++k) {
    164                     G(i, k) = G(j, k) ? false : G(i, k);
    165                 }
    166             }
    167         }
    168     }
    169 
    170     // And now transcribe it into our base constraint graph
    171     mConstraintGraph = ConstraintGraph(m - 1);
    172     for (unsigned j = 1; j != n; ++j) {
    173         for (unsigned i = 1; i != n; ++i) {
    174             if (G(i, j)) {
    175                 add_edge(i - 1, j - 1, mConstraintGraph);
    176             }
    177         }
    178     }
    179 
    180     // initialize the BDD engine ...
    181     Engine engine(variables + vars.size());
    182     mCharacterizationMap.emplace(entry.createZeroes(), BDD::Contradiction());
    183     mCharacterizationMap.emplace(entry.createOnes(), BDD::Tautology());
    184     // order the variables so that our inputs are pushed to the end; they ought to
    185     // be the most complex to resolve.
    186     for (const Var * var : vars) {
    187         mCharacterizationMap.emplace(var, engine.var(variables++));
    188     }
    189     return engine;
    190 }
    191 
    192 /** ------------------------------------------------------------------------------------------------------------- *
    193  * @brief characterize
    194  * @param engine the BDD engine
    195  * @param vars the input vars for this program
    196  *
    197  * Scan through the program and iteratively compute the BDDs for each statement.
    198  ** ------------------------------------------------------------------------------------------------------------- */
    199 void AutoMultiplexing::characterize(Engine & engine, const PabloBlock & entry) {
    200 
    201     std::vector<std::pair<Advance *, BDD>> advances;
    202     std::stack<const Statement *> scope;
    203 
    204     advances.reserve(mAdvance.size());
    205 
    206     unsigned variables = 0;
    207 
    208     // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    209     for (const Statement * stmt = entry.front(); ; ) {
    210         while ( stmt ) {
    211 
    212             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    213                 // Set the next statement to be the first statement of the inner scope and push the
    214                 // next statement of the current statement into the scope stack.
    215                 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    216                 scope.push(stmt->getNextNode());
    217                 stmt = nested.front();
    218                 assert (stmt);
    219                 continue;
    220             }
    221 
    222             BDD bdd;
     216
     217            BDD bdd = false;
    223218
    224219            // Map our operands to the computed BDDs
     
    264259                case PabloAST::ClassTypeId::MatchStar:
    265260                    if (LLVM_UNLIKELY(input[0] == false || input[1] == false)) {
    266                         bdd = false;
    267261                        break;
    268262                    }
     
    272266                    break;
    273267                case PabloAST::ClassTypeId::Advance:
    274                     if (LLVM_UNLIKELY(input[0] == false)) {
    275                         bdd = false;
    276                     }
    277                     else {
    278 
    279                         const BDD var = engine.var(variables++);
    280 
    281                         bdd = var;
     268                    if (LLVM_LIKELY(input[0] != false)) {
    282269
    283270                        // When we built the path graph, we constructed it in the same order; hense the row/column of
    284271                        // the path graph is equivalent to the index.
    285272
    286                         const BDD A = input[0];
     273                        const BDD Vk = bdd = engine.var(variables++);
     274                        const BDD Ik = input[0];
    287275                        const unsigned k = advances.size();
    288276
    289                         assert (stmt == mAdvance[k - 1]);
     277                        assert (stmt == mAdvance[k]);
    290278
    291279                        for (unsigned i = 0; i != k; ++i) {
    292280
    293                             Advance * adv;
    294                             BDD B;
    295                             std::tie(adv, B) = advances[i];
    296 
    297                             bool mutuallyExclusive = false;
    298                             bool constrained = false;
     281                            Advance * adv = mAdvance[i];
     282                            const BDD Ii = std::get<0>(advances[i]);
     283                            const BDD Vi = std::get<1>(advances[i]);
     284
     285                            bool constrained = true;
    299286
    300287                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    301288                            if ((stmt->getOperand(1) != adv->getOperand(1)) && !edge(k, i, mPathGraph).second) {
    302                                 const BDD C = engine.applyAnd(A, B); // do we need to simplify this to identify subsets?
     289
     290                                const BDD C = engine.applyAnd(Ik, Ii); // do we need to simplify this to identify subsets?
    303291                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    304                                 mutuallyExclusive = engine.satOne(C).isFalse();
    305 
    306                                 constrained = !mutuallyExclusive || (stmt->getParent() != adv->getParent()) ;
    307                             }
    308 
    309                             if (mutuallyExclusive) {
    310                                 auto f = mCharacterizationMap.find(adv);
    311                                 // build up our BDD equation for the k-th advance
    312                                 bdd = engine.applyAnd(bdd, engine.applyNot(f->second));
    313                                 // but only mark the other advance as being mutually exclusive with the k-th *variable*
    314                                 f->second = engine.applyAnd(f->second, engine.applyNot(var));
     292                                bool mutuallyExclusive = engine.satOne(C).isFalse();
     293
     294                                if (mutuallyExclusive) {
     295                                    auto f = mCharacterizationMap.find(adv);
     296                                    assert (f != mCharacterizationMap.end());
     297                                    // mark the i-th and k-th Advances as being mutually exclusive
     298                                    bdd = engine.applyAnd(bdd, engine.applyNot(Vi));
     299                                    f->second = engine.applyAnd(f->second, engine.applyNot(Vk));
     300
     301                                    // If these advances are not from the same scope, we cannot safely multiplex them even if they're
     302                                    // mutually exclusive.
     303                                    constrained = (stmt->getParent() != adv->getParent());
     304                                }
     305
     306                                if (constrained) {
     307                                    // Test whether one of the inputs to these advances are a subset of the other
     308                                    if (LLVM_UNLIKELY(Ik == C)) {
     309                                        // If Ik = C and C = Ii ∩ Ik then Ik (the input to the k-th advance) is a *subset* of Ii (the input of the
     310                                        // i-th advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the
     311                                        // multiplex set graph if Advance_i and Advance_k happen to be mutually exclusive set.
     312                                        add_edge(k, i, mSubsetGraph);
     313                                        continue;
     314                                    }
     315                                    else if (LLVM_UNLIKELY(Ii == C)) {
     316                                        add_edge(i, k, mSubsetGraph);
     317                                        continue;
     318                                    }
     319
     320                                }
    315321                            }
    316322
     
    320326                                add_edge(i, k, mConstraintGraph);
    321327                            }
    322                             else if (LLVM_UNLIKELY(A == C)) {
    323                                 // If A = C and C = A ∩ B then A (the input to the k-th advance) is a *subset* of B (the input of the
    324                                 // i-th advance). Record this in the subset graph with the arc (k,i).
    325                                 add_edge(k, i, mSubsetGraph);
    326                                 continue;
    327                             }
    328                             else if (LLVM_UNLIKELY(B == C)) {
    329                                 add_edge(i, k, mSubsetGraph);
    330                                 continue;
    331                             }
     328
    332329                        }
    333 
    334                         // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
    335                         // eliminate the need for looking it up again.
    336                         advances.emplace_back(cast<Advance>(stmt), A);
    337 
    338                         testContradiction = false;
    339                     }
     330                    }
     331
     332                    // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
     333                    // eliminate the need for looking it up again.
     334                    advances.emplace_back(cast<Advance>(stmt), Ik);
     335
     336                    testContradiction = false;
     337
    340338                    break;
    341339            }
     
    360358 * @brief createMappingGraph
    361359 ** ------------------------------------------------------------------------------------------------------------- */
    362 void AutoMultiplexing::createMappingGraph() {
    363     mMappingGraph = MappingGraph(num_vertices(mConstraintGraph));
     360void AutoMultiplexing::createMultiplexSetGraph() {
     361    mMultiplexSetGraph = MultiplexSetGraph(num_vertices(mConstraintGraph));
    364362}
    365363
     
    419417inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & S) {
    420418
    421     // At this stage, the mapping graph is a directed bipartite graph that is used to show relationships between
    422     // the "set vertex" for each independent set and its members. We obtain these from "generateMultiplexSets".
     419    // At this stage, the multiplex set graph is a directed bipartite graph that is used to show relationships
     420    // between the "set vertex" and its members. We obtain these from "generateMultiplexSets".
    423421
    424422    // Question: should we enumerate the power set of S?
    425     const auto v = add_vertex(mMappingGraph);
     423    const auto v = add_vertex(mMultiplexSetGraph);
    426424    for (auto u : S) {
    427         add_edge(v, u, mMappingGraph);
     425        add_edge(v, u, mMultiplexSetGraph);
    428426    }
    429427}
     
    434432void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) {
    435433
    436     // Compute our independent set graph from our mapping graph; effectively it's the graph resulting
     434    // Compute our independent set graph from our multiplex set graph; effectively it's the graph resulting
    437435    // from contracting one advance node edge with an adjacent vertex
    438436
    439437    const unsigned m = num_vertices(mConstraintGraph);
    440     const unsigned n = num_vertices(mMappingGraph) - m;
     438    const unsigned n = num_vertices(mMultiplexSetGraph) - m;
    441439
    442440    IndependentSetGraph G(n);
     
    444442    // Record the "weight" of this independent set vertex
    445443    for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) {
    446         G[i] = out_degree(m + i, mMappingGraph);
    447     }
    448     // Add in any edges based on the adjacencies in the mapping graph
    449     for (MappingGraph::vertex_descriptor i = 0; i != m; ++i) {
    450         graph_traits<MappingGraph>::in_edge_iterator ei, ei_end;
    451         std::tie(ei, ei_end) = in_edges(i, mMappingGraph);
     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) {
     448        graph_traits<MultiplexSetGraph>::in_edge_iterator ei, ei_end;
     449        std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
    452450        for (; ei != ei_end; ++ei) {
    453451            for (auto ej = ei; ej != ei; ++ej) {
     
    483481        // Select u from S
    484482        const auto u = S[S.size() == 1 ? 0 : RNGDistribution(0, S.size() - 1)(rng)];
    485         // Remove u and its adjacencies from G; clear the adjacent set vertices from the mapping graph. This will effectively
     483        // Remove u and its adjacencies from G; clear the adjacent set vertices from the multiplex set graph. This will effectively
    486484        // choose the set refered to by u as one of our chosen independent sets and discard any other sets that contain one
    487485        // of the vertices in the chosen set.
     
    490488        for (; ai != ai_end; ++ai) {
    491489            removed[*ai] = true;
    492             clear_out_edges(m + *ai, mMappingGraph);
     490            clear_out_edges(m + *ai, mMultiplexSetGraph);
    493491        }
    494492        removed[u] = true;
     
    501499void AutoMultiplexing::applySubsetConstraints() {
    502500
    503     // When entering thus function, the mapping graph M is a bipartite DAG with edges denoting the set
     501    // When entering thus function, the multiplex set graph M is a bipartite DAG with edges denoting the set
    504502    // relationships of our independent sets.
    505503    const unsigned m = num_vertices(mConstraintGraph);
    506     const unsigned n = num_vertices(mMappingGraph);
     504    const unsigned n = num_vertices(mMultiplexSetGraph);
    507505
    508506    // Add in any edges from our subset constraints to M that are within the same set.
     
    512510        const auto u = source(*ei, mSubsetGraph);
    513511        const auto v = target(*ei, mSubsetGraph);
    514         graph_traits<MappingGraph>::in_edge_iterator ej, ej_end;
     512        graph_traits<MultiplexSetGraph>::in_edge_iterator ej, ej_end;
    515513        // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
    516514        // "set vertex". Add the edge between the vertices.
    517         for (std::tie(ej, ej_end) = in_edges(u, mMappingGraph); ej != ej_end; ++ej) {
    518             auto w = target(*ej, mMappingGraph);
     515        for (std::tie(ej, ej_end) = in_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
     516            auto w = target(*ej, mMultiplexSetGraph);
    519517            // Only check (v, w) if w is a "set vertex".
    520518            if (w >= (n - m) && edge(v, w).second) {
    521                 add_edge(u, v, mMappingGraph);
     519                add_edge(u, v, mMultiplexSetGraph);
    522520                hasSubsetConstraint = true;
    523521            }
     
    530528        // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams.
    531529
    532         std::vector<MappingGraph::vertex_descriptor> V;
    533         std::stack<MappingGraph::vertex_descriptor> S;
     530        std::vector<MultiplexSetGraph::vertex_descriptor> V;
     531        std::stack<MultiplexSetGraph::vertex_descriptor> S;
    534532        std::queue<PabloAST *> Q;
    535533        BitVector D(n - m, 0);
    536534
    537535        for (auto i = m; i != n; ++i) {
    538             graph_traits<MappingGraph>::out_edge_iterator ei, ei_end;
     536            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    539537            // For each member of a "set vertex" ...
    540             std::tie(ei, ei_end) = out_edges(i, mMappingGraph);
     538            std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph);
    541539            for (; ei != ei_end; ++ei) {
    542                 const auto s = source(*ei, mMappingGraph);
    543                 if (out_degree(s, mMappingGraph) != 0) {
     540                const auto s = source(*ei, mMultiplexSetGraph);
     541                if (out_degree(s, mMultiplexSetGraph) != 0) {
    544542                    // First scan through the subgraph of vertices in M dominated by s and build up the set T,
    545543                    // consisting of all sinks w.r.t. vertex s.
    546544                    auto u = s;
    547545                    for (;;) {
    548                         graph_traits<MappingGraph>::out_edge_iterator ej, ej_end;
    549                         for (std::tie(ej, ej_end) = out_edges(u, mMappingGraph); ej != ej_end; ++ej) {
    550                             auto v = target(*ej, mMappingGraph);
     546                        graph_traits<MultiplexSetGraph>::out_edge_iterator ej, ej_end;
     547                        for (std::tie(ej, ej_end) = out_edges(u, mMultiplexSetGraph); ej != ej_end; ++ej) {
     548                            auto v = target(*ej, mMultiplexSetGraph);
    551549                            if (D.test(v)) {
    552550                                continue;
    553551                            }
    554552                            D.set(v);
    555                             if (out_degree(v, mMappingGraph) == 0) {
     553                            if (out_degree(v, mMultiplexSetGraph) == 0) {
    556554                                V.push(v);
    557555                            }
     
    575573                    for (auto i : V) {
    576574                        Q.push(mAdvance[i]->getOperand(0));
    577                     }
    578                     pb->setInsertPoint(adv->getPrevNode());
     575                    }                   
    579576                    while (Q.size() > 1) {
    580577                        PabloAST * a1 = Q.front(); Q.pop();
    581578                        PabloAST * a2 = Q.front(); Q.pop();
     579                        pb->setInsertPoint(a2);
    582580                        Q.push(pb->createOr(a1, a2));
    583581                    }
     
    606604                    }
    607605                    assert (Q.size() == 1);
     606
    608607                    PabloAST * const input = Q.front(); Q.pop();
    609 
    610608                    for (PabloAST * use : U) {
    611609                        if (LLVM_LIKELY(isa<Statement>(use))) {
     
    633631void AutoMultiplexing::multiplexSelectedIndependentSets() {
    634632
    635     // When entering thus function, the mapping graph M is a bipartite DAG with edges denoting the set
     633    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
    636634    // relationships of our independent sets.
    637635
    638636    unsigned N = 3;
    639     for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMappingGraph); s != e; ++s) {
    640         N = std::max<unsigned>(N, out_degree(s, mMappingGraph));
     637    for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMultiplexSetGraph); s != e; ++s) {
     638        N = std::max<unsigned>(N, out_degree(s, mMultiplexSetGraph));
    641639    }
    642640    unsigned M = static_cast<unsigned>(std::ceil(std::log2(N))); // use a faster builtin function for this.
    643641
    644     std::vector<MappingGraph::vertex_descriptor> V(N);
     642    std::vector<MultiplexSetGraph::vertex_descriptor> V(N);
    645643    std::queue<PabloAST *> T(M);
    646644    std::queue<PabloAST *> F(M);
    647645    std::vector<SmallVector<User *, 4>> users(N);
    648646
    649     for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMappingGraph); s != e; ++s) {
    650         const unsigned n = out_degree(s, mMappingGraph);
     647    for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMultiplexSetGraph); s != e; ++s) {
     648        const unsigned n = out_degree(s, mMultiplexSetGraph);
    651649        if (n) {
    652650
    653651            const unsigned m = static_cast<unsigned>(std::ceil(std::log2(n))); // use a faster builtin function for this.
    654652
    655             graph_traits<MappingGraph>::out_edge_iterator ei_begin, ei_end;
    656             std::tie(ei_begin, ei_end) = out_edges(s, mMappingGraph);
     653            graph_traits<MultiplexSetGraph>::out_edge_iterator ei_begin, ei_end;
     654            std::tie(ei_begin, ei_end) = out_edges(s, mMultiplexSetGraph);
    657655            for (auto ei = ei_begin; ei != ei_end; ++ei) {
    658                 V[std::distance(ei_begin, ei)] = target(*ei, mMappingGraph);
     656                V[std::distance(ei_begin, ei)] = target(*ei, mMultiplexSetGraph);
    659657            }
    660658            std::sort(V.begin(), V.begin() + n);
     
    744742 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
    745743 * w.r.t. the transitive closure of their dependencies in the IR, the position of each Advance's dependencies and
    746  * users within the IR isn't taken into consideration. This while there must be a valid ordering for the program
    747  * it is not necessarily the original ordering.
     744 * users within the IR isn't taken into consideration. Thus while there must be a valid ordering for the program,
     745 * it's not necessarily the original ordering.
    748746 ** ------------------------------------------------------------------------------------------------------------- */
    749 void AutoMultiplexing::topologicalSort() {
    750 
    751 
    752 }
    753 
    754 
    755 }
     747void AutoMultiplexing::topologicalSort(PabloBlock & entry) {
     748
     749    TopologicalSortGraph G;
     750    TopologicalSortQueue Q;
     751    flat_map<Statement *, TopologicalSortGraph::vertex_descriptor> map;
     752
     753    std::stack<std::pair<Statement *, PabloBlock *>> scope;
     754
     755
     756    Statement * insertionPtr = nullptr;
     757    PabloBlock * insertionBlock = &entry;
     758
     759    for (Statement * stmt = entry.front(); ; ) {
     760        while ( stmt ) {
     761            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     762                // Set the next statement to be the first statement of the inner scope and push the
     763                // next statement of the current statement into the scope stack.
     764                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     765                scope.push(std::make_pair(stmt, insertionBlock));
     766                insertionBlock = &nested;
     767                insertionPtr = nullptr;
     768                stmt = nested.front();
     769                assert (stmt);
     770                continue;
     771            }
     772
     773            const auto u = add_vertex(stmt, G);
     774            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     775                auto f = map.find(stmt->getOperand(i));
     776                if (f == map.end()) {
     777                    continue;
     778                }
     779                add_edge(f->second, u);
     780            }
     781            if (in_degree(u, G)) {
     782                Q.push(u);
     783            }
     784            map.emplace(stmt, u);
     785
     786
     787
     788
     789            stmt = stmt->getNextNode();
     790        }
     791        if (scope.empty()) {
     792            break;
     793        }
     794        std::tie(insertionPtr, insertionBlock) = scope.top();
     795        scope.pop();
     796        stmt = insertionPtr->getNextNode();
     797    }
     798
     799}
     800
     801void AutoMultiplexing::topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q) {
     802
     803
     804    std::vector<Statement *> L;
     805    L.reserve(num_vertices(G));
     806    while (!Q.empty()) {
     807        const auto u = Q.front(); Q.pop();
     808        graph_traits<TopologicalSortGraph>::out_edge_iterator ei, ei_end;
     809        for (std::tie(ei, ei_end) = out_edges(u, G); ei != ei_end; ++ei) {
     810            const auto v = target(*ei, G);
     811            if (in_degree(v, G) == 1) {
     812                Q.push(v);
     813            }
     814        }
     815        clear_out_edges(u, G);
     816        L.push_back(G[u]);
     817    }
     818
     819
     820}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4578 r4579  
    44#include <pablo/codegenstate.h>
    55#include <slab_allocator.h>
    6 #include <unordered_map>
     6#include <queue>
    77#include <pablo/analysis/bdd/bdd.hpp>
    88#include <boost/graph/adjacency_list.hpp>
     
    2222    using PathGraph = boost::adjacency_matrix<boost::undirectedS>;
    2323    using SubsetGraph = boost::edge_list<std::pair<unsigned, unsigned>>;
    24     using MappingGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
     24    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    2525    using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS, unsigned>;
    2626    using Advances = std::vector<Advance *>;
     27    using TopologicalSortGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::directedS, PabloAST *>;
     28    using TopologicalSortQueue = std::queue<TopologicalSortGraph::vertex_descriptor>;
    2729
    2830    using RNG = std::mt19937;
     
    3840    bdd::Engine initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
    3941    void characterize(bdd::Engine & engine, const PabloBlock & entry);
    40     bool generateMultiplexSets(RNG & rng);
     42    void createMultiplexSetGraph();
     43    bool generateMultiplexSets(RNG & rng);   
    4144    void addMultiplexSet(const IndependentSet & set);
    4245    void approxMaxWeightIndependentSet(RNG & rng);
    4346    void applySubsetConstraints();
    4447    void multiplexSelectedIndependentSets();
    45     void topologicalSort();
     48    void topologicalSort(PabloBlock & entry) const;
     49    void topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q) const;
    4650
    4751private:
     
    5357    SubsetGraph             mSubsetGraph;
    5458    Advances                mAdvance;
    55     MappingGraph            mMappingGraph;
     59    MultiplexSetGraph       mMultiplexSetGraph;
    5660};
    5761
Note: See TracChangeset for help on using the changeset viewer.