Changeset 4601


Ignore:
Timestamp:
Jun 12, 2015, 12:21:15 PM (4 years ago)
Author:
nmedfort
Message:

Minor changes to multiplexing code.

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

Legend:

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

    r4600 r4601  
    1111#include <include/simd-lib/builtins.hpp>
    1212#include <pablo/expression_map.hpp>
    13 #include <pablo/printer_pablos.h>
    14 #include <iostream>
     13//#include <boost/function.hpp>
     14//#include <boost/graph/connected_components.hpp>
     15//#include <boost/graph/filtered_graph.hpp>
     16#include <boost/range/iterator_range.hpp>
    1517#include <cudd.h>
    1618#include <util.h>
     
    2123using namespace boost::numeric::ublas;
    2224
    23 
    24 namespace pablo {
    25 
     25// #define PRINT_DEBUG_OUTPUT
     26
     27#if !defined(NDEBUG) || defined(PRINT_DEBUG_OUTPUT)
     28#include <iostream>
     29
     30using namespace pablo;
    2631typedef uint64_t timestamp_t;
    2732
     
    4348}
    4449
    45 #ifndef NDEBUG
    4650#define LOG(x) std::cerr << x << std::endl;
     51#define RECORD_TIMESTAMP(Name) const timestamp_t Name = read_cycle_counter()
     52#define LOG_GRAPH(Name, G) \
     53    LOG(Name << " |V|=" << num_vertices(G) << ", |E|="  << num_edges(G) << \
     54                " (" << (((double)num_edges(G)) / ((double)(num_vertices(G) * (num_vertices(G) - 1) / 2))) << ')')
     55
     56unsigned __count_advances(const PabloBlock & entry) {
     57
     58    std::stack<const Statement *> scope;
     59    unsigned advances = 0;
     60
     61    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     62    for (const Statement * stmt = entry.front(); ; ) {
     63        while ( stmt ) {
     64            if (isa<Advance>(stmt)) {
     65                ++advances;
     66            }
     67            else if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     68                // Set the next statement to be the first statement of the inner scope and push the
     69                // next statement of the current statement into the scope stack.
     70                const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     71                scope.push(stmt->getNextNode());
     72                stmt = nested.front();
     73                assert (stmt);
     74                continue;
     75            }
     76            stmt = stmt->getNextNode();
     77        }
     78        if (scope.empty()) {
     79            break;
     80        }
     81        stmt = scope.top();
     82        scope.pop();
     83    }
     84    return advances;
     85}
     86
     87#define LOG_NUMBER_OF_ADVANCES(entry) LOG("|Advances|=" << __count_advances(entry))
     88
    4789#else
    4890#define LOG(x)
     91#define RECORD_TIMESTAMP(Name)
     92#define LOG_GRAPH(Name, G)
     93#define LOG_NUMBER_OF_ADVANCES(entry)
    4994#endif
    5095
     96
     97namespace pablo {
    5198
    5299bool AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
     
    58105    LOG("Seed:                    " << seed);
    59106
    60     bool modified = false;
    61107    AutoMultiplexing am;
    62     const timestamp_t start_initialize = read_cycle_counter();
     108    RECORD_TIMESTAMP(start_initialize);
    63109    am.initialize(input, entry);
    64     const timestamp_t end_initialize = read_cycle_counter();
     110    RECORD_TIMESTAMP(end_initialize);
    65111
    66112    LOG("Initialize:              " << (end_initialize - start_initialize));
    67113
    68     const timestamp_t start_characterize = read_cycle_counter();
     114    LOG_NUMBER_OF_ADVANCES(entry);
     115
     116    RECORD_TIMESTAMP(start_characterize);
    69117    am.characterize(entry);
    70     const timestamp_t end_characterize = read_cycle_counter();
     118    RECORD_TIMESTAMP(end_characterize);
    71119
    72120    LOG("Characterize:            " << (end_characterize - start_characterize));
    73121
    74     const timestamp_t start_shutdown = read_cycle_counter();
     122    RECORD_TIMESTAMP(start_shutdown);
    75123    am.shutdown();
    76     const timestamp_t end_shutdown = read_cycle_counter();
     124    RECORD_TIMESTAMP(end_shutdown);
    77125    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
    78126
    79     const timestamp_t start_create_multiplex_graph = read_cycle_counter();
     127    RECORD_TIMESTAMP(start_create_multiplex_graph);
    80128    am.createMultiplexSetGraph();
    81129    const bool multiplex = am.generateMultiplexSets(rng);
    82     const timestamp_t end_create_multiplex_graph = read_cycle_counter();
     130    RECORD_TIMESTAMP(end_create_multiplex_graph);
    83131    LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
    84132
    85133    if (multiplex) {
    86134
    87         const timestamp_t start_mwis = read_cycle_counter();
     135        RECORD_TIMESTAMP(start_mwis);
    88136        am.approxMaxWeightIndependentSet(rng);
    89         const timestamp_t end_mwis = read_cycle_counter();
     137        RECORD_TIMESTAMP(end_mwis);
    90138        LOG("MaxWeightIndependentSet: " << (end_mwis - start_mwis));
    91139
    92         const timestamp_t start_subset_constraints = read_cycle_counter();
     140        RECORD_TIMESTAMP(start_subset_constraints);
    93141        am.applySubsetConstraints();
    94         const timestamp_t end_subset_constraints = read_cycle_counter();
     142        RECORD_TIMESTAMP(end_subset_constraints);
    95143        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
    96144
    97         const timestamp_t start_select_independent_sets = read_cycle_counter();
     145        RECORD_TIMESTAMP(start_select_independent_sets);
    98146        am.multiplexSelectedIndependentSets();
    99         const timestamp_t end_select_independent_sets = read_cycle_counter();
     147        RECORD_TIMESTAMP(end_select_independent_sets);
    100148        LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
    101149
    102         const timestamp_t start_topological_sort = read_cycle_counter();
     150        RECORD_TIMESTAMP(start_topological_sort);
    103151        am.topologicalSort(entry);
    104         const timestamp_t end_topological_sort = read_cycle_counter();
     152        RECORD_TIMESTAMP(end_topological_sort);
    105153        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
    106 
    107         modified = true;
    108     }
    109 
    110     return modified;
     154    }
     155
     156    LOG_NUMBER_OF_ADVANCES(entry);
     157
     158    return multiplex;
    111159}
    112160
     
    220268    }
    221269
    222     // Record our transitive closure in the path graph and remove any reflexive-loops
    223     mPathGraph = PathGraph(m);
     270    // Record the path / base constraint graph after removing any reflexive-loops.
     271    // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
     272    // reverse the edges as we're writing them to obtain the transposed graph.
     273    mConstraintGraph = ConstraintGraph(m);
     274    mSubsetGraph = SubsetGraph(m);
     275
    224276    for (unsigned i = 0; i != m; ++i) {
    225277        G(i, i) = false;
    226278        for (unsigned j = 0; j != m; ++j) {
    227279            if (G(i, j)) {
    228                 add_edge(i, j, mPathGraph);
     280                add_edge(j, i, mConstraintGraph);
    229281            }
    230282        }       
    231     }
    232 
    233     // Now take the transitive reduction of G
    234     for (unsigned j = 0; j != m; ++j) {
    235         for (unsigned i = 0; i != m; ++i) {
    236             if (G(i, j)) {
    237                 // Eliminate any unecessary arcs not covered by a longer path
    238                 for (unsigned k = 0; k != m; ++k) {
    239                     G(i, k) = G(j, k) ? false : G(i, k);
    240                 }
    241             }
    242         }
    243     }
    244 
    245     // And now transcribe it into our base constraint graph. Since G is a use-def
    246     // graph and we want our constraint graph to be a def-use graph, reverse the
    247     // edges as we're writing them to obtain the transposed graph.
    248     mConstraintGraph = ConstraintGraph(m);
    249     mSubsetGraph = SubsetGraph(m);
    250     for (unsigned j = 0; j != m; ++j) {
    251         for (unsigned i = 0; i != m; ++i) {
    252             if (G(i, j)) {
    253                 add_edge(j, i, mConstraintGraph);
    254             }
    255         }
    256283    }
    257284
     
    286313
    287314    // TODO: What if we did some minterm analysis in here? We'd need to be careful to keep the Advances properly indexed.
    288 
    289     unsigned comparisons = 0;
    290     unsigned avoided = 0;
    291315
    292316    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     
    363387                        // the path graph is equivalent to the index.
    364388
     389                        // Only test pairs if they are in the same scope or one has a user in the a scope that is reachable by
     390                        // the other?
     391
     392                        // Can we use a transposed copy of the subset graph to determine an ordering of variables?
     393
    365394                        DdNode * const Ik = input[0];
    366395                        DdNode * Ck = Cudd_bddIthVar(mManager, mVariables++);
     
    369398                        const unsigned k = advances.size();
    370399
    371                         std::fill(unconstrained.begin(), unconstrained.end(), false);
    372 
    373                         // Instead of processing these sequentially, look at the existing subset relationships incase we can infer
    374                         // more things sooner?
     400                        std::fill(unconstrained.begin(), unconstrained.begin() + k, false);
     401
    375402                        for (unsigned i = 0; i != k; ++i) {
    376 
     403                            // Have we already proven that these are unconstrained by the subset relationships?
     404                            if (unconstrained[i]) continue;
    377405                            Advance * adv = mAdvance[i];
    378 
    379                             // Only test pairs if they are in the same scope or one has a user in the a scope that is reachable by
    380                             // the other?
    381 
    382                             bool constrained = !unconstrained[i];
    383 
    384406                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    385                             if (constrained && (stmt->getOperand(1) == adv->getOperand(1)) && (notTransitivelyDependant(k, i))) {
    386                                 ++comparisons;
     407                            if ((stmt->getOperand(1) == adv->getOperand(1)) && (notTransitivelyDependant(i, k))) {
    387408                                DdNode * Ii = std::get<0>(advances[i]);
    388409                                DdNode * Ni = std::get<1>(advances[i]);
     
    402423                                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    403424                                        const auto j = source(*ei, mSubsetGraph);
    404                                         if (j > i && notTransitivelyDependant(k, j)) {
     425                                        if (notTransitivelyDependant(k, j)) {
    405426                                            Advance * adv = mAdvance[j];
    406427                                            assert (mCharacterizationMap.count(adv));
     
    411432                                            Cj = And(Cj, Nk);
    412433                                            unconstrained[j] = true;
    413                                             ++avoided;
    414434                                        }
    415435                                    }
    416                                     constrained = false;
     436                                    unconstrained[i] = true;
    417437                                }
    418438                                else if (Ik == IiIk) {
     
    425445                                    for (std::tie(ei, ei_end) = out_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    426446                                        const auto j = target(*ei, mSubsetGraph);
    427                                         if (j > i) {
    428                                             add_edge(k, j, mSubsetGraph);
    429                                             unconstrained[j] = true;
    430                                             ++avoided;
    431                                         }
     447                                        add_edge(k, j, mSubsetGraph);
     448                                        unconstrained[j] = true;
    432449                                    }
    433                                     constrained = false;
     450                                    unconstrained[i] = true;
    434451                                }
    435452                                else if (Ii == IiIk) {
     
    440457                                    for (std::tie(ei, ei_end) = in_edges(i, mSubsetGraph); ei != ei_end; ++ei) {
    441458                                        const auto j = source(*ei, mSubsetGraph);
    442                                         if (j > i) {
    443                                             add_edge(j, k, mSubsetGraph);
    444                                             unconstrained[j] = true;
    445                                             ++avoided;
    446                                         }
     459                                        add_edge(j, k, mSubsetGraph);
     460                                        unconstrained[j] = true;
    447461                                    }
    448                                     constrained = false;
     462                                    unconstrained[i] = true;
    449463                                }
    450464                                Cudd_RecursiveDeref(mManager, IiIk);
    451465                            }
    452 
     466                        }
     467
     468                        for (unsigned i = 0; i != k; ++i) {
     469                            const Advance * const adv = mAdvance[i];
    453470                            // Even if these Advances are mutually exclusive, they must be in the same scope or they cannot be safely multiplexed.
    454                             if (constrained || (stmt->getParent() != adv->getParent())) {
     471                            if (!unconstrained[i] || (stmt->getParent() != adv->getParent())) {
    455472                                // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
    456473                                // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
    457474                                add_edge(i, k, mConstraintGraph);
    458475                            }
    459 
    460476                        }
     477
    461478                        // Append this advance to the list of known advances. Both its input BDD and the Advance variable are stored in
    462479                        // the list to eliminate the need for searching for it.
     
    468485                    throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
    469486            }
    470             assert ("Failed to generate a" && (bdd));
     487            assert ("Failed to generate a BDD." && (bdd));
    471488            mCharacterizationMap[stmt] = bdd;
    472489            if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
    473490                if (!isa<Assign>(stmt)) {
    474491                    Cudd_RecursiveDeref(mManager, bdd);
     492                    mCharacterizationMap[stmt] = Zero();
    475493                    stmt = stmt->replaceWith(entry.createZeroes());
    476494                    continue;
     
    486504        scope.pop();
    487505    }
    488 
    489 //    LOG("comparisons: " << comparisons << ", avoided: " << avoided);
    490506}
    491507
     
    494510 ** ------------------------------------------------------------------------------------------------------------- */
    495511inline bool AutoMultiplexing::notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const {
    496     return (mPathGraph.get_edge(i, j) == 0);
     512    return (mConstraintGraph.get_edge(i, j) == 0);
    497513}
    498514
     
    568584
    569585    using Vertex = ConstraintGraph::vertex_descriptor;
    570     using VertexIterator = graph_traits<ConstraintGraph>::vertex_iterator;
    571     using EdgeIterator = graph_traits<ConstraintGraph>::out_edge_iterator;
    572586    using DegreeType = graph_traits<ConstraintGraph>::degree_size_type;
    573587
    574     IndependentSet S, N;
     588    // What if we generated a "constraint free" graph instead? By taking each connected component of it
     589    // and computing the complement of it (with the same lesser to greater index ordering), we should
     590    // have the same problem here but decomposed into subgraphs.
     591
     592    IndependentSet M, N;
    575593    auto remainingVerticies = num_vertices(mConstraintGraph);
    576594    std::vector<DegreeType> D(remainingVerticies);
    577     S.reserve(15);
     595    M.reserve(15);
    578596    N.reserve(15);
    579597
    580598    // Push all source nodes into the new independent set N
    581     VertexIterator vi, vi_end;
    582     for (std::tie(vi, vi_end) = vertices(mConstraintGraph); vi != vi_end; ++vi) {
    583         const auto d = in_degree(*vi, mConstraintGraph);
    584         D[*vi] = d;
     599    for (auto v : make_iterator_range(vertices(mConstraintGraph))) {
     600        const auto d = in_degree(v, mConstraintGraph);
     601        D[v] = d;
    585602        if (d == 0) {
    586             N.push_back(*vi);
    587         }
    588     }
    589 
    590     while ( remainingVerticies >= 3 ) {
    591 
    592 
    593         // If we have at least 3 vertices in our two sets, try adding them to our
    594         // multiplexing set.
    595         if ((N.size() + S.size()) >= 3) {
    596             addMultiplexSet(N, S);
    597         }       
    598 
    599         // Move all of our "newly" uncovered vertices into the "known" set. By always
    600         // choosing at least one element from N, this will prevent us from adding the
    601         // same multiplexing set again.
    602         S.insert(S.end(), N.begin(), N.end()); N.clear();
     603            N.push_back(v);
     604        }
     605    }
     606
     607    for (;;) {
     608
     609        // If we have at least 3 vertices in our two sets, try adding them to our multiplexing set.
     610        if ((N.size() + M.size()) >= 3) {
     611            addMultiplexSet(N, M);
     612        }
     613
     614        if (remainingVerticies == 0) {
     615            break;
     616        }
     617
     618        // Move all of our "newly" uncovered vertices in S into the "known" set M. By always choosing
     619        // at least one element from N, this will prevent us from adding the same multiplexing set again.
     620        M.insert(M.end(), N.begin(), N.end()); N.clear();
    603621
    604622        do {
    605623            // Randomly choose a vertex in S and discard it.
    606             assert (!S.empty());
    607             const auto i = S.begin() + RNGDistribution(0, S.size() - 1)(rng);
     624            assert (!M.empty());
     625            const auto i = M.begin() + RNGDistribution(0, M.size() - 1)(rng);
    608626            const Vertex u = *i;
    609             S.erase(i);
     627            M.erase(i);
    610628            --remainingVerticies;
    611             EdgeIterator ei, ei_end;
    612             for (std::tie(ei, ei_end) = out_edges(u, mConstraintGraph); ei != ei_end; ++ei) {
    613                 const Vertex v = target(*ei, mConstraintGraph);
     629            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
     630                const Vertex v = target(e, mConstraintGraph);
    614631                if ((--D[v]) == 0) {
    615632                    N.push_back(v);
     
    617634            }
    618635        }
    619         while (N.empty() && remainingVerticies >= 3);
     636        while (N.empty() && remainingVerticies != 0);
    620637    }
    621638
     
    754771        // Select a vertex vi whose weight as greater than the average weight of its neighbours ...
    755772        ssize_t totalWeight = 0;
    756         for (auto vi = indices.begin(); vi != indices.end(); ++vi) {
     773        for (auto vi = indices.begin(); vi != indices.end(); ++vi) {           
    757774            const ssize_t prevWeight = totalWeight;
    758775            totalWeight += cardinalityWeight(std::get<1>(G[*vi]));
     
    774791        // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively
    775792        // choose the set refered to by vi as one of our chosen independent sets.
    776         graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end, aj, aj_end;
    777         for (std::tie(ai, ai_end) = adjacent_vertices(v, G); ai != ai_end; ) {
    778             const auto u = *ai++;
     793
     794        for (auto u : make_iterator_range(adjacent_vertices(v, G))) {
    779795            assert (indices.count(u));
    780796            indices.erase(indices.find(u));
    781797            clear_out_edges(u + m, mMultiplexSetGraph);
    782798            const auto Wj = std::get<0>(G[u]);
    783             for (std::tie(aj, aj_end) = adjacent_vertices(u, G); aj != aj_end; ) {
     799            for (auto w : make_iterator_range(adjacent_vertices(u, G))) {
    784800
    785801                // Let Vi be vertex i, Wi = weight of Vi, Di = degree of Vi, Ni = sum of the weights of vertices
     
    792808                //    Ai' = (Wi * (Di + 1 - 1)) - (Ni - Wj) = (Ai - Wi + Wj)
    793809
    794                 const auto w = *aj++;
    795810                const auto Wi = std::get<0>(G[w]);
    796811                auto & Ai = std::get<1>(G[w]);
     
    804819
    805820    #ifndef NDEBUG
    806     for (unsigned i = m; i != (m + n); ++i) {
    807         if (out_degree(i, mMultiplexSetGraph) > 0) {
    808             LOG(out_degree(i, mMultiplexSetGraph));
    809         }
    810     }
    811821    for (unsigned i = 0; i != m; ++i) {
    812822        assert (in_degree(i, mMultiplexSetGraph) <= 1);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4600 r4601  
    2222
    2323    using CharacterizationMap = boost::container::flat_map<const PabloAST *, DdNode *>;
    24     using ConstraintGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
     24    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
    2525    using PathGraph = boost::adjacency_matrix<boost::undirectedS>;
    2626    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
     
    4949    inline AutoMultiplexing()
    5050    : mVariables(0)
    51     , mPathGraph(0)
     51    , mConstraintGraph(0)
    5252    {
    5353    }
     
    6868    unsigned                mVariables;
    6969    CharacterizationMap     mCharacterizationMap;
    70     PathGraph               mPathGraph;
    7170    ConstraintGraph         mConstraintGraph;
    7271    SubsetGraph             mSubsetGraph;
Note: See TracChangeset for help on using the changeset viewer.