Changeset 4600


Ignore:
Timestamp:
Jun 10, 2015, 11:55:50 AM (4 years ago)
Author:
nmedfort
Message:

Multiplexing work: minor bug fix and inconsequential changes.

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

Legend:

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

    r4599 r4600  
    2121using namespace boost::numeric::ublas;
    2222
    23 #define USE_WEIGHTED_SELECTION
    2423
    2524namespace pablo {
     
    4443}
    4544
     45#ifndef NDEBUG
     46#define LOG(x) std::cerr << x << std::endl;
     47#else
     48#define LOG(x)
     49#endif
     50
    4651
    4752bool AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
     53
     54    std::random_device rd;
     55    const auto seed = rd();
     56    RNG rng(seed);
     57
     58    LOG("Seed:                    " << seed);
     59
    4860    bool modified = false;
    4961    AutoMultiplexing am;
    50     const timestamp_t start = read_cycle_counter();
     62    const timestamp_t start_initialize = read_cycle_counter();
    5163    am.initialize(input, entry);
    5264    const timestamp_t end_initialize = read_cycle_counter();
     65
     66    LOG("Initialize:              " << (end_initialize - start_initialize));
     67
     68    const timestamp_t start_characterize = read_cycle_counter();
    5369    am.characterize(entry);
    5470    const timestamp_t end_characterize = read_cycle_counter();
     71
     72    LOG("Characterize:            " << (end_characterize - start_characterize));
     73
     74    const timestamp_t start_shutdown = read_cycle_counter();
    5575    am.shutdown();
    5676    const timestamp_t end_shutdown = read_cycle_counter();
     77    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
     78
     79    const timestamp_t start_create_multiplex_graph = read_cycle_counter();
    5780    am.createMultiplexSetGraph();
    58     std::random_device rd;
    59     const auto seed = rd(); // 573650087;
    60     RNG rng(seed);
    6181    const bool multiplex = am.generateMultiplexSets(rng);
    6282    const timestamp_t end_create_multiplex_graph = read_cycle_counter();
    63     timestamp_t end_mwis = end_create_multiplex_graph,
    64             end_subset_constraints = end_create_multiplex_graph,
    65             end_select_independent_sets = end_create_multiplex_graph,
    66             end_topological_sort = end_create_multiplex_graph;
     83    LOG("GenerateMultiplexSets:   " << (end_create_multiplex_graph - start_create_multiplex_graph));
    6784
    6885    if (multiplex) {
     86
     87        const timestamp_t start_mwis = read_cycle_counter();
    6988        am.approxMaxWeightIndependentSet(rng);
    70         end_mwis = read_cycle_counter();
     89        const timestamp_t end_mwis = read_cycle_counter();
     90        LOG("MaxWeightIndependentSet: " << (end_mwis - start_mwis));
     91
     92        const timestamp_t start_subset_constraints = read_cycle_counter();
    7193        am.applySubsetConstraints();
    72         end_subset_constraints = read_cycle_counter();
     94        const timestamp_t end_subset_constraints = read_cycle_counter();
     95        LOG("ApplySubsetConstraints:  " << (end_subset_constraints - start_subset_constraints));
     96
     97        const timestamp_t start_select_independent_sets = read_cycle_counter();
    7398        am.multiplexSelectedIndependentSets();
    74         end_select_independent_sets = read_cycle_counter();
     99        const timestamp_t end_select_independent_sets = read_cycle_counter();
     100        LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
     101
     102        const timestamp_t start_topological_sort = read_cycle_counter();
    75103        am.topologicalSort(entry);
    76         end_topological_sort = read_cycle_counter();
     104        const timestamp_t end_topological_sort = read_cycle_counter();
     105        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
     106
    77107        modified = true;
    78108    }
    79 
    80 //    std::cerr << "Initialize:              " << (end_initialize - start) << "   (seed=" << seed << ')' << std::endl;
    81 //    std::cerr << "Characterize:            " << (end_characterize - end_initialize) << std::endl;
    82 //    std::cerr << "Shutdown:                " << (end_shutdown - end_characterize) << std::endl;
    83 //    std::cerr << "GenerateMultiplexSets:   " << (end_create_multiplex_graph - end_shutdown) << std::endl;
    84 //    std::cerr << "MaxWeightIndependentSet: " << (end_mwis - end_create_multiplex_graph) << std::endl;
    85 //    std::cerr << "ApplySubsetConstraints:  " << (end_subset_constraints - end_mwis) << std::endl;
    86 //    std::cerr << "MultiplexSelectedSets:   " << (end_select_independent_sets - end_subset_constraints) << std::endl;
    87 //    std::cerr << "TopologicalSort:         " << (end_topological_sort - end_select_independent_sets) << std::endl;
    88109
    89110    return modified;
     
    100121void AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
    101122
    102     flat_map<const PabloAST *, unsigned> map;
    103     std::vector<const Statement *> complexStatements;
     123    flat_map<const PabloAST *, unsigned> map;   
    104124    std::stack<const Statement *> scope;
     125    unsigned complexStatements = 0; // number of statements that cannot always be categorized without generating a new variable
    105126
    106127    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     
    128149                case PabloAST::ClassTypeId::ScanThru:
    129150                case PabloAST::ClassTypeId::MatchStar:
    130                     complexStatements.push_back(stmt);
     151                    complexStatements++;
    131152                    break;
    132153                default:
     
    236257
    237258    // Initialize the BDD engine ...
    238     mManager = Cudd_Init((complexStatements.size() + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     259    mManager = Cudd_Init((complexStatements + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    239260    Cudd_AutodynDisable(mManager);
    240261
     
    245266    // Order the variables so the input Vars are pushed to the end; they ought to
    246267    // be the most complex to resolve.
    247     unsigned i = 0;
    248     for (const Statement * stmt : complexStatements) {
    249         mCharacterizationMap.emplace(stmt, Cudd_bddIthVar(mManager, i++));
    250     }
     268    unsigned i = complexStatements;
    251269    for (const Var * var : vars) {
    252270        mCharacterizationMap.emplace(var, Cudd_bddIthVar(mManager, i++));
     
    299317                input[i] = f->second;
    300318            }
    301 
    302             bool testContradiction = true;
    303             bool updateVariable = true;
    304319
    305320            switch (stmt->getClassTypeId()) {
     
    313328                    // The next instruction is almost identical to an OR; however, a Next cannot be
    314329                    // an operand of a Statement. Instead it updates the Initial operand's value.
    315                     testContradiction = false;
    316330                case PabloAST::ClassTypeId::Or:           
    317331                    bdd = Or(input[0], input[1]);
     
    336350                    }
    337351                case PabloAST::ClassTypeId::Call:
    338                     testContradiction = false;
    339                     updateVariable = false;
     352                    bdd = Cudd_bddIthVar(mManager, mVariables++);
    340353                    break;
    341354                case PabloAST::ClassTypeId::Advance:
    342355                    assert (stmt == mAdvance[advances.size()]);
    343356                    if (LLVM_UNLIKELY(isZero(input[0]))) {
    344                         bdd = input[0];
     357                        bdd = Zero();
    345358                        advances.emplace_back(bdd, bdd);
    346359                    }
     
    350363                        // the path graph is equivalent to the index.
    351364
    352                         assert (mCharacterizationMap.count(stmt));
    353365                        DdNode * const Ik = input[0];
    354                         DdNode * Ck = mCharacterizationMap[stmt];
     366                        DdNode * Ck = Cudd_bddIthVar(mManager, mVariables++);
    355367                        DdNode * const Nk = Not(Ck);
    356368
     
    450462                        // the list to eliminate the need for searching for it.
    451463                        advances.emplace_back(Ik, Nk);
    452                         testContradiction = false;
    453464                        bdd = Ck;
    454465                    }
     
    457468                    throw std::runtime_error("Unexpected statement type " + stmt->getName()->to_string());
    458469            }
    459             assert ("Failed to generate a BDD." && (bdd || !(testContradiction || updateVariable)));
    460             if (LLVM_LIKELY(updateVariable)) {
    461                 mCharacterizationMap[stmt] = bdd;
    462             }
    463             if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) {               
     470            assert ("Failed to generate a" && (bdd));
     471            mCharacterizationMap[stmt] = bdd;
     472            if (LLVM_UNLIKELY(noSatisfyingAssignment(bdd))) {
    464473                if (!isa<Assign>(stmt)) {
    465474                    Cudd_RecursiveDeref(mManager, bdd);
     
    478487    }
    479488
    480 //    std::cerr << "comparisons: " << comparisons << ", avoided: " << avoided << std::endl;
     489//    LOG("comparisons: " << comparisons << ", avoided: " << avoided);
    481490}
    482491
     
    675684}
    676685
    677 static inline ssize_t sqr(const ssize_t n) {
    678     return n * n;
     686/** ------------------------------------------------------------------------------------------------------------- *
     687 * @brief cardinalityWeight
     688 * @param x the input number
     689 *
     690 * Returns 0 if x < 0; otherwise x^2.
     691 ** ------------------------------------------------------------------------------------------------------------- */
     692static inline ssize_t cardinalityWeight(const ssize_t x) {
     693    const ssize_t xx = std::max<ssize_t>(x, 0);
     694    return xx * xx;
    679695}
    680696
     
    690706    const unsigned m = num_vertices(mConstraintGraph);
    691707    const unsigned n = num_vertices(mMultiplexSetGraph) - m;
    692 
    693     const auto start = read_cycle_counter();
    694708
    695709    IndependentSetGraph G(n);
     
    721735    boost::container::flat_set<IndependentSetGraph::vertex_descriptor> indices;
    722736    indices.reserve(n);
    723     #ifdef USE_WEIGHTED_SELECTION
     737
    724738    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
    725739        int neighbourhoodWeight = 0;
     
    733747        indices.insert(*vi);
    734748    }
    735     #endif
    736 
    737     const auto built_graph = read_cycle_counter();
    738 
    739     // std::cerr << "G=(" << num_vertices(G) << ',' << num_edges(G) << ") built in " << (built_graph - start) << std::endl;
    740 
    741749    // Using WMIN from "A note on greedy algorithms for the maximum weighted independent set problem"
    742750    // (Note: look into minimum independent dominating set algorithms. It fits better with the ceil log2 + subset cost model.)
     
    745753
    746754        // Select a vertex vi whose weight as greater than the average weight of its neighbours ...
    747         #ifdef USE_WEIGHTED_SELECTION
    748         int totalWeight = 0;
     755        ssize_t totalWeight = 0;
    749756        for (auto vi = indices.begin(); vi != indices.end(); ++vi) {
    750             totalWeight += sqr(std::get<1>(G[*vi]));
     757            const ssize_t prevWeight = totalWeight;
     758            totalWeight += cardinalityWeight(std::get<1>(G[*vi]));
     759            assert (totalWeight >= prevWeight);
    751760        }
    752761
    753762        IndependentSetGraph::vertex_descriptor v = 0;
    754763        ssize_t remainingWeight = RNGDistribution(0, totalWeight - 1)(rng);
    755         for (auto vi = indices.begin(); vi != indices.end(); ++vi) {
    756             remainingWeight -= sqr(std::max<int>(std::get<1>(G[*vi]), 0));
     764        assert (remainingWeight >= 0 && remainingWeight < totalWeight);
     765        for (auto vi = indices.begin(); vi != indices.end(); ++vi) {           
     766            remainingWeight -= cardinalityWeight(std::get<1>(G[*vi]));
    757767            if (remainingWeight < 0) {
    758768                v = *vi;
     
    761771        }
    762772        assert (remainingWeight < 0);
    763 
    764         #else
    765         auto i = RNGDistribution(1, indices.size())(rng);
    766         for (std::tie(vi, vi_end) = vertices(G); --i != 0; ++vi);
    767         assert (vi != vi_end);
    768         #endif       
    769773
    770774        // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively
     
    776780            indices.erase(indices.find(u));
    777781            clear_out_edges(u + m, mMultiplexSetGraph);
    778             #ifdef USE_WEIGHTED_SELECTION
    779782            const auto Wj = std::get<0>(G[u]);
    780783            for (std::tie(aj, aj_end) = adjacent_vertices(u, G); aj != aj_end; ) {
     
    795798                remove_edge(u, w, G);
    796799            }
    797             #else
    798             clear_vertex(u, G);
    799             #endif
    800800            remove_edge(v, u, G);
    801801        }
     
    803803    }
    804804
    805 //    for (unsigned i = m; i != (m + n); ++i) {
    806 //        if (out_degree(i, mMultiplexSetGraph) > 0) {
    807 //            std::cerr << out_degree(i, mMultiplexSetGraph) << std::endl;
    808 //        }
    809 //    }
    810 
    811805    #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    }
    812811    for (unsigned i = 0; i != m; ++i) {
    813812        assert (in_degree(i, mMultiplexSetGraph) <= 1);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4599 r4600  
    2929    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    3030    using Advances = std::vector<Advance *>;
    31 
    3231    using RNG = std::mt19937;
    3332    using RNGDistribution = std::uniform_int_distribution<RNG::result_type>;
    34 
    35     using Vertex = ConstraintGraph::vertex_descriptor;
    36 
    37     using IndependentSet = std::vector<Vertex>;
     33    using IndependentSet = std::vector<ConstraintGraph::vertex_descriptor>;
    3834
    3935public:
     
    5248    void topologicalSort(PabloBlock & entry) const;
    5349    inline AutoMultiplexing()
    54     : mPathGraph(0)
     50    : mVariables(0)
     51    , mPathGraph(0)
    5552    {
    5653    }
     
    6966private:
    7067    DdManager *             mManager;
     68    unsigned                mVariables;
    7169    CharacterizationMap     mCharacterizationMap;
    7270    PathGraph               mPathGraph;
Note: See TracChangeset for help on using the changeset viewer.