Changeset 4888


Ignore:
Timestamp:
Dec 2, 2015, 4:22:23 PM (3 years ago)
Author:
nmedfort
Message:

Work on adding Multiplexing Window Size.

Location:
icGREP/icgrep-devel/icgrep
Files:
3 edited

Legend:

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

    r4885 r4888  
    2020using namespace boost::numeric::ublas;
    2121
    22 // #define PRINT_DEBUG_OUTPUT
     22#define PRINT_DEBUG_OUTPUT
    2323
    2424#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
     
    101101using TypeId = PabloAST::ClassTypeId;
    102102
    103 bool AutoMultiplexing::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const bool independent) {
     103bool MultiplexingPass::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const unsigned windowSize, const bool independent) {
    104104
    105105//    std::random_device rd;
     
    110110    LOG("Seed:                    " << seed);
    111111
    112     AutoMultiplexing am(limit, maxSelections);
     112    MultiplexingPass mp(limit, maxSelections, windowSize);
    113113    RECORD_TIMESTAMP(start_initialize);
    114     const unsigned advances = am.initialize(function, independent);
     114    const unsigned advances = mp.initialize(function, independent);
    115115    RECORD_TIMESTAMP(end_initialize);
    116116
     
    124124
    125125    RECORD_TIMESTAMP(start_characterize);
    126     am.characterize(function.getEntryBlock());
     126    mp.characterize(function.getEntryBlock());
    127127    RECORD_TIMESTAMP(end_characterize);
    128128
     
    137137
    138138    RECORD_TIMESTAMP(start_create_multiplex_graph);
    139     const bool multiplex = am.generateCandidateSets(rng);
     139    const bool multiplex = mp.generateCandidateSets(rng);
    140140    RECORD_TIMESTAMP(end_create_multiplex_graph);
    141141    LOG("GenerateCandidateSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
     
    144144
    145145        RECORD_TIMESTAMP(start_select_multiplex_sets);
    146         am.selectMultiplexSets(rng);
     146        mp.selectMultiplexSets(rng);
    147147        RECORD_TIMESTAMP(end_select_multiplex_sets);
    148148        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
    149149
    150150        RECORD_TIMESTAMP(start_subset_constraints);
    151         am.applySubsetConstraints();
     151        mp.eliminateSubsetConstraints();
    152152        RECORD_TIMESTAMP(end_subset_constraints);
    153153        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
    154154
    155155        RECORD_TIMESTAMP(start_select_independent_sets);
    156         am.multiplexSelectedIndependentSets(function);
     156        mp.multiplexSelectedIndependentSets(function);
    157157        RECORD_TIMESTAMP(end_select_independent_sets);
    158158        LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets));
    159159
    160         AutoMultiplexing::topologicalSort(function);
     160        MultiplexingPass::topologicalSort(function);
    161161        #ifndef NDEBUG
    162162        PabloVerifier::verify(function, "post-multiplexing");
     
    176176 * the proper variable ordering.
    177177 ** ------------------------------------------------------------------------------------------------------------- */
    178 unsigned AutoMultiplexing::initialize(PabloFunction & function, const bool independent) {
    179 
    180     flat_map<const PabloAST *, unsigned> map;
     178unsigned MultiplexingPass::initialize(PabloFunction & function, const bool independent) {
     179
    181180    std::stack<Statement *> scope;
    182181    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
     
    184183    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    185184    unsigned statements = 0, advances = 0;
    186     mResolvedScopes.emplace(function.getEntryBlock(), nullptr);
    187185    for (Statement * stmt = function.getEntryBlock()->front(); ; ) {
    188186        while ( stmt ) {
    189187            ++statements;
    190188            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    191                 // Set the next statement to be the first statement of the inner scope and push the
    192                 // next statement of the current statement into the scope stack.
    193                 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    194                 mResolvedScopes.emplace(nested, stmt);
    195189                scope.push(stmt->getNextNode());
     190                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();               
    196191                stmt = nested->front();
    197192                assert (stmt);
    198193                continue;
    199194            }
    200 
    201             assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() > 0));
    202 
    203195            switch (stmt->getClassTypeId()) {
    204196                case TypeId::Advance:
     
    226218    }
    227219
    228     // Create the transitive closure matrix of graph. From this we'll construct
    229     // two graphs restricted to the relationships between advances. The first will
    230     // be a path graph, which is used to bypass testing for mutual exclusivity of
    231     // advances that cannot be multiplexed. The second is a transitive reduction
    232     // of that graph, which forms the basis of our constraint graph when deciding
    233     // which advances ought to be multiplexed.
    234 
    235     matrix<bool> G(statements, advances, false);
    236     for (unsigned i = 0; i != advances; ++i) {
    237         G(i, i) = true;
    238     }
    239 
    240     unsigned n = advances;
    241     unsigned m = 0;
    242 
    243     for (const Statement * stmt = function.getEntryBlock()->front();;) {
    244         while ( stmt ) {
    245 
    246             unsigned u = 0;
    247             if (isa<Advance>(stmt)) {
    248                 u = m++;
    249             } else {
    250                 u = n++;
    251             }
    252             map.emplace(stmt, u);
    253 
    254             for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    255                 const PabloAST * const op = stmt->getOperand(i);
    256                 if (LLVM_LIKELY(isa<Statement>(op))) {
    257                     const unsigned v = map[op];
    258                     for (unsigned w = 0; w != m; ++w) {
    259                         G(u, w) |= G(v, w);
    260                     }
    261                 }
    262             }
    263             if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
    264                 // Set the next statement to be the first statement of the inner scope
    265                 // and push the next statement of the current statement into the stack.
    266                 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
    267                 scope.push(stmt->getNextNode());
    268                 stmt = nested->front();
    269                 assert (stmt);
    270                 continue;
    271             }
    272             stmt = stmt->getNextNode();
    273         }
    274         if (scope.empty()) {
    275             break;
    276         }
    277         stmt = scope.top();
    278         scope.pop();
    279     }
    280 
    281     // Can I use the data in the matrix to indicate whether an Advance is dependent on a particular instruction and only
    282     // for which there is still a use left of it?
    283 
    284     // Record the path / base constraint graph after removing any reflexive-loops.
    285     // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
    286     // reverse the edges as we're writing them to obtain the transposed graph.
    287 
    288     mConstraintGraph = ConstraintGraph(advances);
     220    initializeBaseConstraintGraph(function.getEntryBlock(), statements, advances);
     221
    289222    mSubsetGraph = SubsetGraph(advances);
    290223
    291     for (unsigned i = 0; i != advances; ++i) {
    292         G(i, i) = false;
    293         for (unsigned j = 0; j != advances; ++j) {
    294             if (G(i, j)) {
    295                 add_edge(j, i, mConstraintGraph);
    296             }
    297         }
    298     }
     224    initializeAdvanceDepth(function.getEntryBlock(), advances);
    299225
    300226    // Initialize the BDD engine ...
     
    334260
    335261/** ------------------------------------------------------------------------------------------------------------- *
     262 * @brief initializeBaseConstraintGraph
     263 ** ------------------------------------------------------------------------------------------------------------- */
     264inline void MultiplexingPass::initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances) {
     265
     266    std::stack<Statement *> scope;
     267    flat_map<const PabloAST *, unsigned> M;
     268    M.reserve(statements);
     269    matrix<bool> G(statements, advances, false);
     270    for (unsigned i = 0; i != advances; ++i) {
     271        G(i, i) = true;
     272    }
     273
     274    unsigned n = advances;
     275    unsigned k = 0;
     276    for (const Statement * stmt = block->front();;) {
     277        while ( stmt ) {
     278            unsigned u = 0;
     279            if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
     280                u = k++;
     281            } else {
     282                u = n++;
     283            }
     284            M.emplace(stmt, u);
     285            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     286                const PabloAST * const op = stmt->getOperand(i);
     287                if (LLVM_LIKELY(isa<Statement>(op))) {
     288                    const unsigned v = M[op];
     289                    for (unsigned w = 0; w != k; ++w) {
     290                        G(u, w) |= G(v, w);
     291                    }
     292                }
     293            }
     294            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     295                scope.push(stmt->getNextNode());
     296                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     297                stmt = nested->front();
     298                assert (stmt);
     299                continue;
     300            }
     301            stmt = stmt->getNextNode();
     302        }
     303        if (scope.empty()) {
     304            break;
     305        }
     306        stmt = scope.top();
     307        scope.pop();
     308    }
     309
     310    assert (k == advances);
     311
     312    // Compute the base constraint graph as the union of TRANSPOSE(G) without any reflective loops and the set of edges
     313    // marking which advances are in differing scope blocks.
     314
     315    mConstraintGraph = ConstraintGraph(advances);
     316    for (unsigned i = 0; i != advances; ++i) {
     317        for (unsigned j = 0; j < i; ++j) {
     318            if (G(i, j)) {
     319                add_edge(j, i, mConstraintGraph);
     320            }
     321        }
     322        for (unsigned j = i + 1; j < advances; ++j) {
     323            if (G(i, j)) {
     324                add_edge(j, i, mConstraintGraph);
     325            }
     326        }
     327    }
     328
     329}
     330
     331/** ------------------------------------------------------------------------------------------------------------- *
     332 * @brief initializeAdvanceDepth
     333 ** ------------------------------------------------------------------------------------------------------------- */
     334inline void MultiplexingPass::initializeAdvanceDepth(PabloBlock * const block, const unsigned advances) {
     335
     336    std::stack<Statement *> scope;
     337    unsigned k = 0;
     338    int maxDepth = 0;
     339    const Advance * advance[advances];
     340    mAdvanceDepth.resize(advances, 0);
     341    for (Statement * stmt = block->front(); ; ) {
     342        while ( stmt ) {
     343            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     344                scope.push(stmt->getNextNode());
     345                const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();
     346                stmt = nested->front();
     347                assert (stmt);
     348                continue;
     349            } else if (LLVM_UNLIKELY(isa<Advance>(stmt))) {
     350                int depth = 0;
     351                advance[k] = cast<Advance>(stmt);
     352                for (unsigned i = 0; i != k; ++i) {
     353                    if (edge(i, k, mConstraintGraph).second || (advance[i]->getParent() != advance[k]->getParent())) {
     354                        depth = std::max<int>(depth, mAdvanceDepth[i]);
     355                    }
     356                }
     357                mAdvanceDepth[k++] = ++depth;
     358                maxDepth = std::max(maxDepth, depth);
     359            }
     360            stmt = stmt->getNextNode();
     361        }
     362        if (scope.empty()) {
     363            break;
     364        }
     365        stmt = scope.top();
     366        scope.pop();
     367    }
     368    assert (k == advances);
     369
     370    LOG("Window Size / Max Depth: " << mWindowSize << " of " << maxDepth);
     371}
     372
     373/** ------------------------------------------------------------------------------------------------------------- *
    336374 * @brief characterize
    337375 * @param vars the input vars for this program
     
    339377 * Scan through the program and iteratively compute the BDDs for each statement.
    340378 ** ------------------------------------------------------------------------------------------------------------- */
    341 void AutoMultiplexing::characterize(PabloBlock * const block) {
     379void MultiplexingPass::characterize(PabloBlock * const block) {
    342380    for (Statement * stmt : *block) {
    343381        if (LLVM_UNLIKELY(isa<If>(stmt))) {
     
    374412 * @brief characterize
    375413 ** ------------------------------------------------------------------------------------------------------------- */
    376 inline BDD AutoMultiplexing::characterize(Statement * const stmt) {
     414inline BDD MultiplexingPass::characterize(Statement * const stmt) {
    377415    BDD bdd = get(stmt->getOperand(0));
    378416    switch (stmt->getClassTypeId()) {
     
    402440            break;
    403441        case TypeId::ScanThru:
    404             // ScanThru(c, m) := (c + m) ∧ ¬m. We can conservatively represent this statement using the BDD for ¬m --- provided
    405             // no derivative of this statement is negated in any fashion.
     442            // ScanThru(c, m) := (c + m) ∧ ¬m. Thus we can conservatively represent this statement using the BDD
     443            // for ¬m --- provided no derivative of this statement is negated in any fashion.
    406444        case TypeId::MatchStar:
    407445        case TypeId::Call:
     
    418456 * @brief characterize
    419457 ** ------------------------------------------------------------------------------------------------------------- */
    420 inline BDD AutoMultiplexing::characterize(Advance * const adv, const BDD Ik) {
    421 
     458inline BDD MultiplexingPass::characterize(Advance * const adv, const BDD Ik) {
    422459    const auto k = mAdvanceAttributes.size();
    423460    std::vector<bool> unconstrained(k , false);
    424 
    425461    for (unsigned i = 0; i != k; ++i) {
    426         // Have we already proven that these are unconstrained by the subset relationships?
     462        // Are we interested in testing these streams to see whether they are mutually exclusive?
     463        if (exceedsWindowSize(i, k)) continue;
     464        // Have we already proven that they are unconstrained by their subset relationship?
    427465        if (unconstrained[i]) continue;
    428 
    429         // If these advances are "shifting" their values by the same amount ...
     466        // If these Advances are mutually exclusive, in the same scope, transitively independent, and shift their
     467        // values by the same amount, we can safely multiplex them. Otherwise mark the constraint in the graph.
    430468        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
    431         if (independent(i, k) && adv->getOperand(1) == ithAdv->getOperand(1)) {
     469        if ((mTestConstrainedAdvances || independent(i, k)) && (ithAdv->getOperand(1) == adv->getOperand(1))) {
    432470            const BDD Ii = get(ithAdv->getOperand(0));
    433471            const BDD IiIk = bdd_addref(bdd_and(Ii, Ik));
     
    468506    }
    469507
    470     const BDD Vk = bdd_addref(bdd_not(bdd_ithvar(mVariables++)));
    471     BDD Ck = bdd_one();
     508    BDD Ck = bdd_ithvar(mVariables++);
     509    const BDD Nk = bdd_addref(bdd_not(Ck));
    472510    for (unsigned i = 0; i != k; ++i) {
    473         const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
    474         BDD & Ci = get(ithAdv);
    475         const BDD Vi = std::get<1>(mAdvanceAttributes[i]);
    476511        if (unconstrained[i]) {
    477             const BDD exclusionConstraint = bdd_addref(bdd_or(Vi, Vk));
    478             Ci = bdd_addref(bdd_and(Ci, exclusionConstraint));
    479             Ck = bdd_addref(bdd_and(Ck, exclusionConstraint));
    480             // If these Advances are mutually exclusive, in the same scope and transitively independent,
    481             // we can safely multiplex them. Otherwise mark the constraint edge in the graph.
    482             if (adv->getParent() == ithAdv->getParent()) {
     512            const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
     513            const BDD Ni = std::get<1>(mAdvanceAttributes[i]);
     514
     515            BDD & Ci = get(ithAdv);
     516            Ci = bdd_addref(bdd_and(Ci, Nk));
     517            Ck = bdd_addref(bdd_and(Ck, Ni));
     518            if ((!mTestConstrainedAdvances || independent(i, k)) && (adv->getParent() == ithAdv->getParent())) {
    483519                continue;
    484520            }
     
    486522        add_edge(i, k, mConstraintGraph);
    487523    }
    488 
    489     mAdvanceAttributes.emplace_back(adv, Vk);
    490 
     524    mAdvanceAttributes.emplace_back(adv, Nk);
    491525    return Ck;
    492526}
     
    495529 * @brief independent
    496530 ** ------------------------------------------------------------------------------------------------------------- */
    497 inline bool AutoMultiplexing::independent(const ConstraintVertex i, const ConstraintVertex j) const {
     531inline bool MultiplexingPass::independent(const ConstraintVertex i, const ConstraintVertex j) const {
    498532    assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph));
    499533    return (mConstraintGraph.get_edge(i, j) == 0);
     
    501535
    502536/** ------------------------------------------------------------------------------------------------------------- *
     537 * @brief exceedsWindowSize
     538 ** ------------------------------------------------------------------------------------------------------------- */
     539inline bool MultiplexingPass::exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const {
     540    assert (i < mAdvanceDepth.size() && j < mAdvanceDepth.size());
     541    return (std::abs<int>(mAdvanceDepth[i] - mAdvanceDepth[j]) > mWindowSize);
     542}
     543
     544/** ------------------------------------------------------------------------------------------------------------- *
    503545 * @brief generateMultiplexSets
    504546 * @param RNG random number generator
    505547 ** ------------------------------------------------------------------------------------------------------------- */
    506 bool AutoMultiplexing::generateCandidateSets(RNG & rng) {
     548bool MultiplexingPass::generateCandidateSets(RNG & rng) {
    507549
    508550    using degree_t = graph_traits<ConstraintGraph>::degree_size_type;
     
    601643 * @param S an independent set
    602644 ** ------------------------------------------------------------------------------------------------------------- */
    603 inline void AutoMultiplexing::addCandidateSet(const VertexVector & S, RNG & rng) {
     645inline void MultiplexingPass::addCandidateSet(const VertexVector & S, RNG & rng) {
    604646    if (S.size() >= 3) {
    605         if (S.size() <= mLimit) {
     647        if (S.size() <= mMultiplexingSetSizeLimit) {
    606648            const auto u = add_vertex(mMultiplexSetGraph);
    607649            for (const auto v : S) {
     
    609651            }
    610652        } else {
    611             const auto max = choose(S.size(), mLimit);
    612             unsigned element[mLimit];
    613             if (LLVM_UNLIKELY(max <= mMaxSelections)) {
     653            const auto max = choose(S.size(), mMultiplexingSetSizeLimit);
     654            unsigned element[mMultiplexingSetSizeLimit];
     655            if (LLVM_UNLIKELY(max <= mMaxMultiplexingSetSelections)) {
    614656                for (unsigned i = 0; i != max; ++i) {
    615                     select(S.size(), mLimit, i, element);
     657                    select(S.size(), mMultiplexingSetSizeLimit, i, element);
    616658                    const auto u = add_vertex(mMultiplexSetGraph);
    617                     for (unsigned j = 0; j != mLimit; ++j) {
     659                    for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) {
    618660                        add_edge(u, S[element[j]], mMultiplexSetGraph);
    619661                    }
    620662                }
    621663            } else { // take m random samples
    622                 for (unsigned i = 0; i != mMaxSelections; ++i) {
    623                     select(S.size(), mLimit, rng() % max, element);
     664                for (unsigned i = 0; i != mMaxMultiplexingSetSelections; ++i) {
     665                    select(S.size(), mMultiplexingSetSizeLimit, rng() % max, element);
    624666                    const auto u = add_vertex(mMultiplexSetGraph);
    625                     for (unsigned j = 0; j != mLimit; ++j) {
     667                    for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) {
    626668                        add_edge(u, S[element[j]], mMultiplexSetGraph);
    627669                    }
     
    656698 * two, labelled A and B, are disjoint and the third larger set, C, that consists of elements of A and B.
    657699 ** ------------------------------------------------------------------------------------------------------------- */
    658 void AutoMultiplexing::selectMultiplexSets(RNG &) {
     700void MultiplexingPass::selectMultiplexSets(RNG &) {
    659701
    660702    using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator;
     
    750792
    751793/** ------------------------------------------------------------------------------------------------------------- *
    752  * @brief applySubsetConstraints
    753  ** ------------------------------------------------------------------------------------------------------------- */
    754 void AutoMultiplexing::applySubsetConstraints() {
     794 * @brief eliminateSubsetConstraints
     795 ** ------------------------------------------------------------------------------------------------------------- */
     796void MultiplexingPass::eliminateSubsetConstraints() {
    755797
    756798    using SubsetEdgeIterator = graph_traits<SubsetGraph>::edge_iterator;
     
    801843 * @brief multiplexSelectedIndependentSets
    802844 ** ------------------------------------------------------------------------------------------------------------- */
    803 void AutoMultiplexing::multiplexSelectedIndependentSets(PabloFunction &) {
     845void MultiplexingPass::multiplexSelectedIndependentSets(PabloFunction &) {
    804846
    805847    const unsigned first_set = num_vertices(mConstraintGraph);
     
    911953 * it's not necessarily the original ordering.
    912954 ** ------------------------------------------------------------------------------------------------------------- */
    913 void AutoMultiplexing::topologicalSort(PabloFunction & function) {
     955void MultiplexingPass::topologicalSort(PabloFunction & function) {
    914956    // Note: not a real topological sort. I expect the original order to be very close to the resulting one.
    915957    std::unordered_set<const PabloAST *> encountered;
     
    955997 * @brief doTransitiveReductionOfSubsetGraph
    956998 ** ------------------------------------------------------------------------------------------------------------- */
    957 void AutoMultiplexing::doTransitiveReductionOfSubsetGraph() {
     999void MultiplexingPass::doTransitiveReductionOfSubsetGraph() {
    9581000    std::vector<SubsetGraph::vertex_descriptor> Q;
    9591001    for (auto u : make_iterator_range(vertices(mSubsetGraph))) {
     
    9861028 * @brief get
    9871029 ** ------------------------------------------------------------------------------------------------------------- */
    988 inline BDD & AutoMultiplexing::get(const PabloAST * const expr) {
     1030inline BDD & MultiplexingPass::get(const PabloAST * const expr) {
     1031    assert (expr);
    9891032    auto f = mCharacterization.find(expr);
    9901033    assert (f != mCharacterization.end());
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4871 r4888  
    2020class PabloFunction;
    2121
    22 class AutoMultiplexing {
     22class MultiplexingPass {
    2323
    2424    using CharacterizationMap = llvm::DenseMap<const PabloAST *, BDD>;
     
    2929    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    3030    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
     31    using AdvanceDepth = std::vector<int>;
    3132    using AdvanceAttributes = std::vector<std::pair<Advance *, BDD>>; // the Advance pointer and its respective base BDD variable
    3233    using VertexVector = std::vector<ConstraintVertex>;
     
    3435
    3536public:
    36     static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100, const bool independent = false);
     37    static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100, const unsigned windowSize = 10, const bool independent = false);
    3738protected:
    3839    unsigned initialize(PabloFunction & function, const bool independent);
     40    void initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances);
     41    void initializeAdvanceDepth(PabloBlock * const block, const unsigned advances) ;
     42
    3943    void characterize(PabloBlock * const block);
    4044    BDD characterize(Statement * const stmt);
    4145    BDD characterize(Advance * const adv, const BDD Ik);
    4246    bool independent(const ConstraintVertex i, const ConstraintVertex j) const;
     47    bool exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const;
    4348    bool generateCandidateSets(RNG & rng);
     49
    4450    void addCandidateSet(const VertexVector & S, RNG & rng);
    45     void selectMultiplexSets(RNG &);
    46     void doTransitiveReductionOfSubsetGraph() ;
    47     void applySubsetConstraints();
     51    void selectMultiplexSets(RNG & rng);
     52    void doTransitiveReductionOfSubsetGraph();
     53    void eliminateSubsetConstraints();
    4854    void multiplexSelectedIndependentSets(PabloFunction & function);
    4955    static void topologicalSort(PabloFunction & function);
    5056    BDD & get(const PabloAST * const expr);
    5157
    52     inline AutoMultiplexing(const unsigned limit, const unsigned maxSelections)
    53     : mLimit(limit)
    54     , mMaxSelections(maxSelections)
     58    inline MultiplexingPass(const unsigned limit, const unsigned maxSelections, const unsigned windowSize)
     59    : mMultiplexingSetSizeLimit(limit)
     60    , mMaxMultiplexingSetSelections(maxSelections)
     61    , mWindowSize(windowSize)
     62    , mTestConstrainedAdvances(true)
    5563    , mVariables(0)
    5664    , mConstraintGraph(0)
     65    , mAdvanceDepth(0, 0)
    5766    {
     67
    5868    }
    5969
    6070private:
    61     const unsigned              mLimit;
    62     const unsigned              mMaxSelections;
     71    const unsigned              mMultiplexingSetSizeLimit;
     72    const unsigned              mMaxMultiplexingSetSelections;
     73    const unsigned              mWindowSize;
     74    const bool                  mTestConstrainedAdvances;
    6375    unsigned                    mVariables;
    6476    CharacterizationMap         mCharacterization;
    6577    ConstraintGraph             mConstraintGraph;
     78    AdvanceDepth                mAdvanceDepth;
    6679    SubsetGraph                 mSubsetGraph;
    6780    AdvanceAttributes           mAdvanceAttributes;
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4887 r4888  
    7878
    7979#ifdef ENABLE_MULTIPLEXING
    80 static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(false),
     80static cl::opt<bool> EnableMultiplexing("multiplexing", cl::init(true),
    8181                                        cl::desc("combine Advances whose inputs are mutual exclusive into the fewest number of advances possible (expensive)."),
    8282                                        cl::cat(cPabloOptimizationsOptions));
     
    8585                                        cl::desc("maximum size of any candidate multiplexing set."),
    8686                                        cl::cat(cPabloOptimizationsOptions));
    87 
    8887static cl::opt<unsigned> MultiplexingSelectionLimit("multiplexing-selection-limit", cl::init(100),
    8988                                        cl::desc("maximum number of selections from any partial candidate multiplexing set."),
    9089                                        cl::cat(cPabloOptimizationsOptions));
     90static cl::opt<unsigned> MultiplexingWindowSize("multiplexing-window-size", cl::init(100),
     91                                        cl::desc("maximum depth difference for computing mutual exclusion of Advance nodes."),
     92                                        cl::cat(cPabloOptimizationsOptions));
     93
    9194static cl::opt<bool> EnableLowering("lowering", cl::init(false),
    9295                                         cl::desc("coalesce associative functions prior to optimization passes."),
     
    157160#ifdef ENABLE_MULTIPLEXING   
    158161    if (EnableMultiplexing) {
    159         AutoMultiplexing::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit);
    160         FlattenAssociativeDFG::transform(*function);
     162        MultiplexingPass::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit, MultiplexingWindowSize);
    161163    }
    162164    if (EnableDistribution) {
Note: See TracChangeset for help on using the changeset viewer.