Changeset 4570


Ignore:
Timestamp:
May 21, 2015, 3:58:27 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

    r4569 r4570  
    2121static void AutoMultiplexing::optimize(PabloBlock & block) {
    2222    AutoMultiplexing am;
    23 
    24     Engine eng = am.initialize(block, vars);
    25     am.characterize(eng, vars);
    26 
    27 
     23    Engine eng = am.initialize(vars, block);
     24    am.characterize(eng, block);
     25    RNG rng(std::random_device()());
     26    am.generateMultiplexSets(rng);
     27    am.approxMaxWeightIndependentSet();
     28    am.multiplexSelectedIndependentSets();
    2829}
    2930
     
    3839Engine AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
    3940
    40     std::vector<const Statement *> advances;
     41    unsigned m = 1;
     42    unsigned variables = 0;
     43
     44    flat_map<PabloAST *, unsigned> map;
     45    for (const Var * var : vars) {
     46        map.emplace(var, 0);
     47    }
     48
    4149    std::stack<const Statement *> scope;
    4250
    43     unsigned variables = 0;
    44 
    4551    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    46     unsigned n = 1;
     52    unsigned n = 0;
    4753    for (const Statement * stmt = entry.front(); ; ) {
    48         for (; stmt; stmt = stmt->getNextNode()) {
     54        while ( stmt ) {
    4955            ++n;
    5056            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     
    5965            switch (stmt->getClassTypeId()) {
    6066                case PabloAST::ClassTypeId::Advance:
    61                     advances.push_back(stmt);
     67                    mIndexMap.emplace(stmt, m);
     68                    map.emplace(stmt, ++m);
    6269                case PabloAST::ClassTypeId::Call:
    6370                case PabloAST::ClassTypeId::ScanThru:
     
    6875                    break;
    6976            }
     77            stmt = stmt->getNextNode();
    7078        }
    7179        if (scope.empty()) {
     
    7684    }
    7785
    78     // create the transitive closure matrix of our advances; we'll use
    79     const unsigned m = advances.size() + 1;
    80     flat_map<PabloAST *, unsigned> map;
    81     for (const Var * var : vars) {
    82         map.emplace(var, 0);
    83     }
    84     for (unsigned i = 1; i != m; ++i) {
    85         map.emplace(advances[i], i);
    86     }
     86    // Create the transitive closure matrix of graph. From this we'll construct
     87    // two graphs restricted to the relationships between advances. The first will
     88    // be a path graph, which is used to bypass testing for mutual exclusivity of
     89    // advances that cannot be multiplexed. The second is a transitive reduction
     90    // of that graph, which forms the basis of our constraint graph when deciding
     91    // which advances ought to be multiplexed.
     92
    8793    matrix<bool> G(n, m);
    8894    G.clear();
     
    9197    }
    9298
    93     for (const Statement * stmt = entry.front(), n = 1; ; ) {
    94         for (; stmt; stmt = stmt->getNextNode()) {
     99    for (const Statement * stmt = entry.front(), n = 0; ; ) {
     100        while ( stmt ) {
    95101            // Fill in the transitive closure G ...
    96             const unsigned u = n++;
     102            unsigned u;
     103            if (isa<Advance>(stmt)) {               
     104                u = ++n;
     105                assert (mIndexMap.count(stmt) != 0 && mIndexMap[stmt] == (u - 1));
     106            }
     107            else {
     108                u = ++m;
     109                map.emplace(stmt, u);
     110            }
    97111            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    98                 const unsigned v = map[stmt->getOperand(i)];
    99                 for (unsigned w = 0; w != m; ++w) {
     112                PabloAST * const op = stmt->getOperand(i);
     113                if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
     114                    continue;
     115                }
     116                const unsigned v = map[op];
     117                for (unsigned w = 0; w != n; ++w) {
    100118                    G(v, w) |= G(u, w);
    101119                }
     
    110128                continue;
    111129            }
     130            stmt = stmt->getNextNode();
    112131        }
    113132        if (scope.empty()) {
     
    119138
    120139    // Record our transitive closure in the path graph and remove any reflexive-loops
    121     mPathGraph = PathGraph(m);
    122     for (unsigned i = 0; i != m; ++i) {
    123         for (unsigned j = 0; j != m; ++j) {
     140    mPathGraph = PathGraph(n);
     141    for (unsigned i = 0; i != n; ++i) {
     142        for (unsigned j = 0; j != n; ++j) {
    124143            if (G(i, j)) {
    125144                add_edge(i, j, mPathGraph);
     
    129148    }
    130149
    131     // Now transcribe the transitive reduction of G into our constraint graph
    132     mConstraintGraph = ConstraintGraph(m);
    133     for (unsigned j = 0; j != m; ++j) {
    134         for (unsigned i = 0; i != m; ++i) {
     150    // Now take the transitive reduction of G
     151    for (unsigned j = 1; j != n; ++j) {
     152        for (unsigned i = 1; i != n; ++i) {
    135153            if (G(i, j)) {
    136                 add_edge(i, j, mConstraintGraph);
    137154                // Eliminate any unecessary arcs not covered by a longer path
    138155                for (unsigned k = 0; k != m; ++k) {
    139156                    G(i, k) = G(j, k) ? false : G(i, k);
    140157                }
     158            }
     159        }
     160    }
     161
     162    // And now transcribe it into our base constraint graph
     163    mConstraintGraph = ConstraintGraph(m - 1);
     164    for (unsigned j = 1; j != n; ++j) {
     165        for (unsigned i = 1; i != n; ++i) {
     166            if (G(i, j)) {
     167                add_edge(i - 1, j - 1, mConstraintGraph);
    141168            }
    142169        }
     
    147174    mCharacterizationMap.emplace(entry.createZeroes(), BDD::Contradiction());
    148175    mCharacterizationMap.emplace(entry.createOnes(), BDD::Tautology());
     176    // order the variables so that our inputs are pushed to the end; they ought to
     177    // be the most complex to resolve.
    149178    for (const Var * var : vars) {
    150179        mCharacterizationMap.emplace(var, engine.var(variables++));
     
    165194    std::stack<const Statement *> scope;
    166195
     196   
     197   
    167198    unsigned variables = 0;
    168     unsigned offset = 0;
    169199
    170200    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     
    204234                case PabloAST::ClassTypeId::And:
    205235                    bdd = engine.applyAnd(input[0], input[1]);
    206                     if (LLVM_UNLIKELY(mTestForConjunctionContradictions && engine.satOne(bdd).isFalse())) {
     236                    if (LLVM_UNLIKELY(engine.satOne(bdd).isFalse())) {
    207237                        bdd = BDD::Contradiction();
    208238                        // Look into making a "replaceAllUsesWithZero" method that can recursively apply
     
    219249                    bdd = engine.applyXor(input[0], input[1]);
    220250                    break;
    221 
    222251                case PabloAST::ClassTypeId::Not:
    223252                    bdd = engine.applyNot(input[0]);
     
    227256                    break;
    228257                case PabloAST::ClassTypeId::ScanThru:
    229                     // some optimization may be possible use not op2 for scan thrus if we rule out the possibility
    230                     // of a contradition being calculated later.
     258                    // It may be possible use "engine.applyNot(input[1])" for ScanThrus if we rule out the
     259                    // possibility of a contradition being calculated later. An example of this would be
     260                    // ¬(ScanThru(c,m) √ m) but are there others that would be harder to predict?
    231261                case PabloAST::ClassTypeId::Call:
    232262                case PabloAST::ClassTypeId::MatchStar:
    233263                    bdd = engine.var(variables++);
    234264                    break;
    235                 case PabloAST::ClassTypeId::Advance:
    236                     {
    237                         BDD var = engine.var(variables++);
     265                case PabloAST::ClassTypeId::Advance: {
     266                        const BDD var = engine.var(variables++);
    238267
    239268                        bdd = var;
     
    243272
    244273                        const unsigned k = advances.size();
    245                         const BDD A = input[0];
     274
     275                        assert (mIndexMap.count(stmt) != 0 && mIndexMap[stmt] == k);
    246276
    247277                        for (unsigned i = 0; i != k; ++i) {
    248278
    249279                            Advance * adv;
    250                             BDD B;
    251                             std::tie(adv, B) = advances[i];
    252 
    253                             // Are these two advances advancing their values by the same amount?
    254                             if (stmt->getOperand(1) == adv->getOperand(1)) {
    255                                 continue;
     280                            BDD eq;
     281                            std::tie(adv, eq) = advances[i];
     282
     283                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
     284                            if ((stmt->getOperand(1) != adv->getOperand(1)) && !edge(k, i, mPathGraph).second) {
     285
     286                                const BDD C = engine.applyAnd(input[0], eq); // do we need to simplify this to identify subsets?
     287                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
     288                                if (engine.satOne(C).isFalse()) {
     289                                    auto f = mCharacterizationMap.find(adv);
     290                                    // build up our BDD equation for the k-th Advance
     291                                    bdd = engine.applyAnd(bdd, engine.applyNot(f->second));
     292                                    // but only
     293                                    f->second = engine.applyAnd(f->second, engine.applyNot(var));
     294                                    continue;
     295                                }
     296                                else if (LLVM_UNLIKELY(input[0] == C)) {
     297                                    add_edge(k, i, mSubsetGraph);
     298                                    continue;
     299                                }
     300                                else if (LLVM_UNLIKELY(eq == C)) {
     301                                    add_edge(i, k, mSubsetGraph);
     302                                    continue;
     303                                }
    256304                            }
    257 
    258                             // Are these advances transitively dependant?
    259                             if (edge(offset + i, offset + k, mPathGraph).second) {
    260                                 continue;
    261                             }
    262 
    263                             const BDD C = engine.applyAnd(A, B); // do we need to simplify this to identify subsets?
    264                             // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    265                             if (engine.satOne(C).isFalse()) {
    266                                 auto f = mCharacterizationMap.find(adv);
    267                                 bdd = engine.applyAnd(bdd, engine.applyNot(f->second));
    268                                 f->second = engine.applyAnd(f->second, engine.applyNot(var));
    269                             }
    270                             else if (LLVM_UNLIKELY(A == C)) {
    271                                 add_edge(k, i, mSubsetGraph);
    272                             }
    273                             else if (LLVM_UNLIKELY(B == C)) {
    274                                 add_edge(i, k, mSubsetGraph);
    275                             }
    276                             else {
    277                                 // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
    278                                 // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
    279                                 add_edge(k > i ? i : k, k > i ? k : i, mConstraintGraph);
    280                             }
    281 
    282                             advances.emplace_back(cast<Advance>(stmt), A);
     305                            // We want the constraint graph to be acyclic; since the dependencies are already in topological order,
     306                            // adding an arc from a lesser to greater numbered vertex won't induce a cycle.
     307                            add_edge(i, k, mConstraintGraph);
     308                            // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
     309                            // eliminate the need for looking it up again.
     310                            advances.emplace_back(cast<Advance>(stmt), input[0]);
    283311                        }
    284312                    }
    285313                    break;
    286                 }
    287                 mCharacterizationMap.insert(std::make_pair(stmt, bdd));
    288             }
    289         }
     314            }
     315            mCharacterizationMap.insert(std::make_pair(stmt, bdd));
     316        }
     317
    290318        if (scope.empty()) {
    291319            break;
     
    297325
    298326/** ------------------------------------------------------------------------------------------------------------- *
    299  * @brief findIndependentSets
    300  * @param bb
    301  * @param tli
     327 * @brief generateMultiplexSets
     328 * @param RNG random number generator
    302329 ** ------------------------------------------------------------------------------------------------------------- */
    303 void AutoMultiplexing::findIndependentSets() {
    304 
    305     typedef DependencyGraph::vertex_descriptor                  Vertex;
    306     typedef graph_traits<DependencyGraph>::vertex_iterator      VertexIterator;
    307     typedef graph_traits<DependencyGraph>::out_edge_iterator    EdgeIterator;
     330void AutoMultiplexing::generateMultiplexSets(RNG & rng) {
     331
     332    using Vertex = ConstraintGraph::vertex_descriptor;
     333    using VertexIterator = graph_traits<ConstraintGraph>::vertex_iterator;
     334    using EdgeIterator = graph_traits<ConstraintGraph>::out_edge_iterator;
     335    using DegreeType = graph_traits<ConstraintGraph>::degree_size_type;
    308336
    309337    // push all source nodes into the active independent set S
    310     Vertices S;
     338    IndependentSet S;
     339    unsigned remainingVerticies = num_vertices(mConstraintGraph);
     340    std::vector<DegreeType> D(remainingVerticies);
     341
    311342    VertexIterator vi, vi_end;
    312     for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
    313         if (in_degree(*vi, G) == 0) {
    314             S.push_back(*vi);
    315         }
    316     }
    317 
    318     while (!S.empty()) {
    319         if (S.size() >= 3) {
    320             independentSets.push_back(std::move(Vertices(S)));
    321         }
    322         if (num_edges(G) == 0) {
    323             break;
    324         }
    325         // discard the node of maximum degree from S.
    326         auto max_vi = S.begin();
    327         auto max_timestamp = timestamp[*max_vi];
    328         auto max_degree = out_degree(*max_vi, G);
    329         for (auto vi = max_vi + 1; vi != S.end(); ++vi) {
    330             const auto d = out_degree(*vi, G);
    331             const auto t = timestamp[*vi];
    332              if (max_degree < d || (max_degree == d && max_timestamp < t)) {
    333              // if (max_timestamp < t || (max_timestamp == t && max_degree < d)) {
    334                 max_degree = d;
    335                 max_timestamp = t;
    336                 max_vi = vi;
    337             }
    338         }
    339 
    340 //        auto max_m = metric[*max_vi];
    341 //        for (auto vi = max_vi + 1; vi != S.end(); ++vi) {
    342 //            const auto m = metric[*max_vi];
    343 //            const auto t = timestamp[*vi];
    344 //            if (max_m < m || (max_m == m && max_timestamp < t)) {
    345 //                max_m = m;
    346 //                max_timestamp = t;
    347 //                max_vi = vi;
    348 //            }
    349 //        }
    350 
    351         const unsigned v = *max_vi;
    352         S.erase(max_vi);
     343    for (std::tie(vi, vi_end) = vertices(mConstraintGraph); vi != vi_end; ++vi) {
     344        auto d = in_degree(*vi, mConstraintGraph);
     345        D[*vi] = d;
     346        if (d == 0) {
     347            S.insert(*vi);
     348        }
     349    }
     350
     351    for ( ; remainingVerticies >= 3; --remainingVerticies) {
     352        if (S.size() > 2) {
     353            addMultiplexSet(S);
     354        }
     355        // Randomly choose a vertex in S and discard it.
     356        const auto i = S.begin() + RNGDistribution(0, S.size() - 1)(rng);
     357        const Vertex u = *i;
     358        S.erase(i);
    353359        EdgeIterator ei, ei_end;
    354         for (std::tie(ei, ei_end) = out_edges(v, G); ei != ei_end; ++ei) {
    355             const Vertex u = target(*ei, G);
    356             if (in_degree(u, G) == 1) {
    357                 S.push_back(u);
    358             }
    359         }
    360         clear_out_edges(v, G);
    361     }
    362 }
    363 
    364 
     360        for (std::tie(ei, ei_end) = out_edges(u, mConstraintGraph); ei != ei_end; ++ei) {
     361            const Vertex v = target(*ei, mConstraintGraph);
     362            if ((--D[v]) == 0) {
     363                S.insert(v);
     364            }
     365        }
     366    }
     367}
     368
     369/** ------------------------------------------------------------------------------------------------------------- *
     370 * @brief addMultiplexSet
     371 * @param set an independent set
     372 ** ------------------------------------------------------------------------------------------------------------- */
     373void AutoMultiplexing::addMultiplexSet(const IndependentSet & set) {
     374
     375
     376}
    365377
    366378
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4569 r4570  
    1111#include <boost/container/flat_map.hpp>
    1212#include <boost/numeric/ublas/matrix.hpp>
     13#include <random>
    1314#include <stdint.h>
    1415
     
    2324    using IndexMap = boost::container::flat_map<PabloAST *, unsigned>;
    2425
     26    using RNG = std::mt19937;
     27    using RNGDistribution = std::uniform_int_distribution<RNG::result_type>;
     28
     29    using Vertex = ConstraintGraph::vertex_descriptor;
     30
     31    using IndependentSet = boost::container::flat_set<Vector>;
     32
    2533public:
    2634    static void optimize(PabloBlock & block);
    2735protected:
    28     bdd::Engine AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
    29 
     36    bdd::Engine initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
     37    void characterize(bdd::Engine & engine, const PabloBlock & entry);
     38    void generateMultiplexSets(RNG & rng);
     39    void addMultiplexSet(const IndependentSet & set);
     40    void approxMaxWeightIndependentSet();
     41    void multiplexSelectedIndependentSets();
    3042
    3143private:
     
    3648    ConstraintGraph         mConstraintGraph;
    3749    SubsetGraph             mSubsetGraph;
     50    IndexMap                mIndexMap;
    3851
    39     bool                    mTestForConjunctionContradictions;
    4052};
    4153
Note: See TracChangeset for help on using the changeset viewer.