Changeset 4578


Ignore:
Timestamp:
May 25, 2015, 10:30:21 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

    r4577 r4578  
    1111#include <boost/container/flat_set.hpp>
    1212#include <boost/numeric/ublas/matrix.hpp>
    13 
     13#include <include/simd-lib/builtins.hpp>
     14#include <expression_map.hpp>
    1415
    1516using namespace llvm;
     
    2728    am.createMappingGraph();
    2829    RNG rng(std::random_device()());
    29     am.generateMultiplexSets(rng);
    30     am.approxMaxWeightIndependentSet();
    31     am.applySubsetConstraints();
    32     am.multiplexSelectedIndependentSets();
     30    if (am.generateMultiplexSets(rng)) {
     31        am.approxMaxWeightIndependentSet();
     32        am.applySubsetConstraints();
     33        am.multiplexSelectedIndependentSets();
     34        am.topologicalSort();
     35    }
    3336}
    3437
     
    299302                                const BDD C = engine.applyAnd(A, B); // do we need to simplify this to identify subsets?
    300303                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    301                                 mutuallyExclusive = (engine.satOne(C) == false);
     304                                mutuallyExclusive = engine.satOne(C).isFalse();
    302305
    303306                                constrained = !mutuallyExclusive || (stmt->getParent() != adv->getParent()) ;
     
    318321                            }
    319322                            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).
     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).
    322325                                add_edge(k, i, mSubsetGraph);
    323326                                continue;
     
    365368 * @param RNG random number generator
    366369 ** ------------------------------------------------------------------------------------------------------------- */
    367 void AutoMultiplexing::generateMultiplexSets(RNG & rng) {
     370bool AutoMultiplexing::generateMultiplexSets(RNG & rng) {
    368371
    369372    using Vertex = ConstraintGraph::vertex_descriptor;
     
    376379    unsigned remainingVerticies = num_vertices(mConstraintGraph);
    377380    std::vector<DegreeType> D(remainingVerticies);
     381
     382    bool canMultiplex = false;
    378383
    379384    VertexIterator vi, vi_end;
     
    389394        if (S.size() >= 3) {
    390395            addMultiplexSet(S);
     396            canMultiplex = true;
    391397        }       
    392398        // Randomly choose a vertex in S and discard it.
     
    404410    }
    405411
     412    return canMultiplex;
    406413}
    407414
     
    617624}
    618625
     626//#define FAST_LOG2(x) ((sizeof(unsigned long) * 8 - 1) - ScanReverseIntrinsic((unsigned long)(x)))
     627
     628//#define FAST_CEIL_LOG2(x) (FAST_LOG_2(x) + ((x & (x - 1) != 0) ? 1 : 0))
    619629
    620630/** ------------------------------------------------------------------------------------------------------------- *
     
    623633void AutoMultiplexing::multiplexSelectedIndependentSets() {
    624634
    625 
    626 
    627 }
    628 
    629 }
     635    // When entering thus function, the mapping graph M is a bipartite DAG with edges denoting the set
     636    // relationships of our independent sets.
     637
     638    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));
     641    }
     642    unsigned M = static_cast<unsigned>(std::ceil(std::log2(N))); // use a faster builtin function for this.
     643
     644    std::vector<MappingGraph::vertex_descriptor> V(N);
     645    std::queue<PabloAST *> T(M);
     646    std::queue<PabloAST *> F(M);
     647    std::vector<SmallVector<User *, 4>> users(N);
     648
     649    for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMappingGraph); s != e; ++s) {
     650        const unsigned n = out_degree(s, mMappingGraph);
     651        if (n) {
     652
     653            const unsigned m = static_cast<unsigned>(std::ceil(std::log2(n))); // use a faster builtin function for this.
     654
     655            graph_traits<MappingGraph>::out_edge_iterator ei_begin, ei_end;
     656            std::tie(ei_begin, ei_end) = out_edges(s, mMappingGraph);
     657            for (auto ei = ei_begin; ei != ei_end; ++ei) {
     658                V[std::distance(ei_begin, ei)] = target(*ei, mMappingGraph);
     659            }
     660            std::sort(V.begin(), V.begin() + n);
     661
     662            PabloBlock * const pb = mAdvance[V[0]]->getParent();
     663            // Sanity test to make sure every advance is in the same scope.
     664            #ifndef NDEBUG
     665            for (auto i = 1; i != n; ++i) {
     666                assert (mAdvance[V[i]]->getParent() == pb);
     667            }
     668            #endif
     669
     670            /// Perform n-to-m Multiplexing
     671            for (unsigned j = 0; j != m; ++j) {
     672                for (unsigned i = 0; i != (1 << m); ++i) {
     673                    if (((i + 1) & (1 << j)) != 0) {
     674                        T.push(mAdvance[V[i]]->getOperand(0));
     675                    }
     676                }
     677                // TODO: figure out a way to determine whether we're creating a duplicate value below.
     678                // The expression map findOrCall ought to work conceptually but the functors method
     679                // doesn't really work anymore with the current API.
     680                while (T.size() > 1) {
     681                    PabloAST * a1 = T.front(); T.pop();
     682                    PabloAST * a2 = T.front(); T.pop();
     683                    pb->setInsertPoint(cast<Statement>(a2));
     684                    T.push(pb->createOr(a1, a2));
     685                }
     686                mAdvance[V[j]]->setOperand(0, T.front()); T.pop();
     687            }
     688
     689            /// Perform m-to-n Demultiplexing
     690            // Store the original users of our advances; we'll be modifying these extensively shortly.
     691            for (unsigned i = 0; i != n; ++i) {
     692                const Advance * const adv = mAdvance[V[i]];
     693                users[i].insert(users[i].begin(), adv->user_begin(), adv->user_end()) ;
     694            }
     695
     696            // Now construct the demuxed values and replaces all the users of the original advances with them.
     697            for (unsigned i = 0; i != n; ++i) {
     698                for (unsigned j = 0; j != m; ++j) {
     699                    if (((i + 1) & (1 << j)) != 0) {
     700                        T.push(mAdvance[V[j]]);
     701                    }
     702                    else {
     703                        F.push(mAdvance[V[j]]);
     704                    }
     705                }
     706                while (T.size() > 1) {
     707                    PabloAST * a1 = T.front(); T.pop();
     708                    PabloAST * a2 = T.front(); T.pop();
     709                    pb->setInsertPoint(cast<Statement>(a2));
     710                    T.push(pb->createAnd(a1, a2));
     711                }
     712                assert (T.size() == 1);
     713
     714                while (F.size() > 1) {
     715                    PabloAST * a1 = T.front(); T.pop();
     716                    PabloAST * a2 = T.front(); T.pop();
     717                    pb->setInsertPoint(cast<Statement>(a2));
     718                    F.push(pb->createOr(a1, a2));
     719                }
     720                assert (F.size() == 1);
     721
     722                PabloAST * const demux = pb->createAnd(T.front(), pb->createNot(F.front()), "demux"); T.pop(); F.pop();
     723                for (PabloAST * use : users[i]) {
     724                    cast<Statement>(use)->replaceUsesOfWith(mAdvance[V[j]], demux);
     725                }
     726            }
     727
     728            /// Clean up the unneeded advances ...
     729            for (unsigned i = m; i != n; ++i) {
     730                mAdvance[V[i]]->eraseFromParent(true);
     731            }
     732            for (unsigned i = 0; i != n; ++i) {
     733                users[i].clear();
     734            }
     735
     736        }
     737    }
     738}
     739
     740/** ------------------------------------------------------------------------------------------------------------- *
     741 * @brief topologicalSort
     742 *
     743 * After transforming the IR, we need to run this in order to always have a valid program. Each multiplex set
     744 * contains vertices corresponding to an Advance in the IR. While we know each Advance within a set is independent
     745 * 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.
     748 ** ------------------------------------------------------------------------------------------------------------- */
     749void AutoMultiplexing::topologicalSort() {
     750
     751
     752}
     753
     754
     755}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4577 r4578  
    3838    bdd::Engine initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
    3939    void characterize(bdd::Engine & engine, const PabloBlock & entry);
    40     void generateMultiplexSets(RNG & rng);
     40    bool generateMultiplexSets(RNG & rng);
    4141    void addMultiplexSet(const IndependentSet & set);
    4242    void approxMaxWeightIndependentSet(RNG & rng);
    4343    void applySubsetConstraints();
    4444    void multiplexSelectedIndependentSets();
     45    void topologicalSort();
    4546
    4647private:
Note: See TracChangeset for help on using the changeset viewer.