Ignore:
Timestamp:
Nov 16, 2015, 4:20:15 PM (4 years ago)
Author:
nmedfort
Message:

Minor improvements to the optimizers and AST manipulation.

File:
1 edited

Legend:

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

    r4870 r4871  
    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) {
     103bool AutoMultiplexing::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const bool independent) {
    104104
    105105//    std::random_device rd;
     
    108108    RNG rng(seed);
    109109
    110 
    111     raw_os_ostream out(std::cerr);
    112 
    113 //    out << seed << ',';
    114 
    115110    LOG("Seed:                    " << seed);
    116111
    117112    AutoMultiplexing am(limit, maxSelections);
    118113    RECORD_TIMESTAMP(start_initialize);
    119     const unsigned advances = am.initialize(function, out);
     114    const unsigned advances = am.initialize(function, independent);
    120115    RECORD_TIMESTAMP(end_initialize);
    121116
     
    131126    am.characterize(function.getEntryBlock());
    132127    RECORD_TIMESTAMP(end_characterize);
    133 
    134     out << bdd_getnodenum() << ',' << bdd_getallocnum() << '\n';
    135128
    136129    LOG("Characterize:            " << (end_characterize - start_characterize));
     
    155148        LOG("SelectMultiplexSets:     " << (end_select_multiplex_sets - start_select_multiplex_sets));
    156149
    157 //        raw_os_ostream out(std::cerr);
    158 //        PabloPrinter::print(function.getEntryBlock().statements(), out);
    159 //        out.flush();
    160 
    161150        RECORD_TIMESTAMP(start_subset_constraints);
    162151        am.applySubsetConstraints();
     
    170159
    171160        AutoMultiplexing::topologicalSort(function);
     161
     162        #ifndef NDEBUG
     163        PabloVerifier::verify(function, "post-multiplexing");
     164        #endif
    172165    }
    173166
     
    184177 * the proper variable ordering.
    185178 ** ------------------------------------------------------------------------------------------------------------- */
    186 unsigned AutoMultiplexing::initialize(PabloFunction & function, raw_ostream & out) {
    187 
    188     flat_map<const PabloAST *, unsigned> map;   
     179unsigned AutoMultiplexing::initialize(PabloFunction & function, const bool independent) {
     180
     181    flat_map<const PabloAST *, unsigned> map;
    189182    std::stack<Statement *> scope;
    190183    unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable
     
    229222    }
    230223
    231     out << statements << ',' << variableCount << ',' << advances << ',';
    232 
    233224    // If there are fewer than three Advances in this program, just abort. We cannot reduce it.
    234225    if (advances < 3) {
     
    243234    // which advances ought to be multiplexed.
    244235
    245     matrix<bool> G(statements, advances);
    246     G.clear();
     236    matrix<bool> G(statements, advances, false);
    247237    for (unsigned i = 0; i != advances; ++i) {
    248238        G(i, i) = true;
     
    290280    }
    291281
     282    // Can I use the data in the matrix to indicate whether an Advance is dependent on a particular instruction and only
     283    // for which there is still a use left of it?
     284
    292285    // Record the path / base constraint graph after removing any reflexive-loops.
    293286    // Since G is a use-def graph and we want our constraint graph to be a def-use graph,
    294287    // reverse the edges as we're writing them to obtain the transposed graph.
     288
    295289    mConstraintGraph = ConstraintGraph(advances);
    296290    mSubsetGraph = SubsetGraph(advances);
     
    302296                add_edge(j, i, mConstraintGraph);
    303297            }
    304         }       
     298        }
    305299    }
    306300
     
    310304    bdd_setcacheratio(64);
    311305    bdd_setmaxincrease(10000000);
    312     // bdd_setminfreenodes(10000);
    313     bdd_autoreorder(BDD_REORDER_NONE);
    314 
    315     // Map the predefined 0/1 entries
    316     mCharacterizationMap[PabloBlock::createZeroes()] = bdd_zero();
    317     mCharacterizationMap[PabloBlock::createOnes()] = bdd_one();
    318 
    319     // Order the variables so the input Vars are pushed to the end; they ought to
    320     // be the most complex to resolve.
    321     for (mVariables = 0; mVariables != function.getNumOfParameters(); ++mVariables) {
    322         mCharacterizationMap[function.getParameter(mVariables)] = bdd_ithvar(mVariables);
     306    bdd_autoreorder(BDD_REORDER_SIFT);
     307
     308    // Map the constants and input variables
     309    mCharacterization[PabloBlock::createZeroes()] = bdd_zero();
     310    mCharacterization[PabloBlock::createOnes()] = bdd_one();
     311    mVariables = function.getNumOfParameters();
     312
     313    // TODO: record information in the function to indicate which pairs of input variables are independent
     314    if (independent) {
     315        for (unsigned i = 0; i != mVariables; ++i) {
     316            BDD Vi = bdd_ithvar(i);
     317            BDD Ni = bdd_zero();
     318            for (unsigned j = 0; j != i; ++j) {
     319                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
     320            }
     321            for (unsigned j = i + 1; j != mVariables; ++j) {
     322                Ni = bdd_addref(bdd_or(Ni, bdd_ithvar(j)));
     323            }
     324            Ni = bdd_addref(bdd_not(Ni));
     325            mCharacterization[function.getParameter(i)] = bdd_addref(bdd_imp(Vi, Ni));
     326        }
     327    } else {
     328        for (unsigned i = 0; i != mVariables; ++i) {
     329            mCharacterization[function.getParameter(i)] = bdd_ithvar(i);
     330        }
    323331    }
    324332
     
    348356            }
    349357        } else {
    350             mCharacterizationMap.insert(std::make_pair(stmt, characterize(stmt)));
     358            mCharacterization.insert(std::make_pair(stmt, characterize(stmt)));
    351359        }
    352360    }
     
    408416inline BDD AutoMultiplexing::characterize(Advance * const adv, const BDD Ik) {
    409417
    410     bdd_addref(Ik);
    411 
    412418    const auto k = mAdvanceAttributes.size();
    413419
     
    420426        // If these advances are "shifting" their values by the same amount ...
    421427        const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);
    422         if (adv->getOperand(1) == ithAdv->getOperand(1)) {
     428        if (independent(i, k) && adv->getOperand(1) == ithAdv->getOperand(1)) {
    423429            const BDD Ii = get(ithAdv->getOperand(0));
    424430            const BDD IiIk = bdd_addref(bdd_and(Ii, Ik));
     
    472478            // If these Advances are mutually exclusive, in the same scope, and transitively independent,
    473479            // we safely multiplex them.
    474             if ((adv->getParent() == ithAdv->getParent()) && independent(i, k)) {
     480            if (adv->getParent() == ithAdv->getParent()) {
    475481                continue;
    476482            }
     
    478484        add_edge(i, k, mConstraintGraph);
    479485    }
    480 
    481     bdd_delref(Ik);
    482486
    483487    mAdvanceAttributes.emplace_back(adv, Vk);
     
    535539            const auto i = S.begin() + IntDistribution(0, S.size() - 1)(rng);
    536540            assert (i != S.end());
    537             const ConstraintVertex u = *i;           
    538             S.erase(i);           
     541            const ConstraintVertex u = *i;
     542            S.erase(i);
    539543
    540544            for (auto e : make_iterator_range(out_edges(u, mConstraintGraph))) {
     
    814818        const size_t n = out_degree(idx, mMultiplexSetGraph);
    815819        if (n) {
    816             const size_t m = log2_plus_one(n);           
     820            const size_t m = log2_plus_one(n);
    817821            Advance * input[n];
    818             Advance * muxed[m];           
     822            Advance * muxed[m];
    819823
    820824            unsigned i = 0;
     
    843847                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
    844848                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
    845                     assert (!Q.full());                                       
     849                    assert (!Q.full());
    846850                    Q.push_back(builder.createOr(a2, a1, "muxing"));
    847851                }
     
    849853                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
    850854                // The only way this did not return an Advance statement would be if either the mux or shift amount
    851                 // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.               
     855                // is zero. Since these cases would have been eliminated earlier, we are safe to cast here.
    852856                muxed[j] = cast<Advance>(builder.createAdvance(mux, adv->getOperand(1), prefix.str()));
    853857            }
    854858
    855             /// Perform m-to-n Demultiplexing                       
     859            /// Perform m-to-n Demultiplexing
    856860            for (size_t i = 0; i != n; ++i) {
    857861
     
    981985 ** ------------------------------------------------------------------------------------------------------------- */
    982986inline BDD & AutoMultiplexing::get(const PabloAST * const expr) {
    983     auto f = mCharacterizationMap.find(expr);
    984     assert (f != mCharacterizationMap.end());
     987    auto f = mCharacterization.find(expr);
     988    assert (f != mCharacterization.end());
    985989    return f->second;
    986990}
Note: See TracChangeset for help on using the changeset viewer.