Ignore:
Timestamp:
Jun 5, 2015, 8:55:59 AM (4 years ago)
Author:
nmedfort
Message:

More multiplexing work.

File:
1 edited

Legend:

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

    r4594 r4596  
    2121using namespace boost::numeric::ublas;
    2222
     23#define USE_WEIGHTED_SELECTION
     24
    2325namespace pablo {
    2426
     27typedef uint64_t timestamp_t;
     28
     29static inline timestamp_t read_cycle_counter() {
     30#ifdef __GNUC__
     31timestamp_t ts;
     32#ifdef __x86_64__
     33  unsigned int eax, edx;
     34  asm volatile("rdtsc" : "=a" (eax), "=d" (edx));
     35  ts = ((timestamp_t) eax) | (((timestamp_t) edx) << 32);
     36#else
     37  asm volatile("rdtsc\n" : "=A" (ts));
     38#endif
     39  return(ts);
     40#endif
     41#ifdef _MSC_VER
     42  return __rdtsc();
     43#endif
     44}
     45
     46
    2547bool AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
     48    bool modified = false;
    2649    AutoMultiplexing am;
     50    const timestamp_t start = read_cycle_counter();
    2751    am.initialize(input, entry);
     52    const timestamp_t end_initialize = read_cycle_counter();
    2853    am.characterize(entry);
     54    const timestamp_t end_characterize = read_cycle_counter();
    2955    am.shutdown();
     56    const timestamp_t end_shutdown = read_cycle_counter();
    3057    am.createMultiplexSetGraph();
    3158    std::random_device rd;
    3259    RNG rng(rd());
    33     if (am.generateMultiplexSets(rng)) {
     60    const bool multiplex = am.generateMultiplexSets(rng);
     61    const timestamp_t end_create_multiplex_graph = read_cycle_counter();
     62    timestamp_t end_mwis = end_create_multiplex_graph,
     63            end_subset_constraints = end_create_multiplex_graph,
     64            end_select_independent_sets = end_create_multiplex_graph,
     65            end_topological_sort = end_create_multiplex_graph;
     66
     67    if (multiplex) {
    3468        am.approxMaxWeightIndependentSet(rng);
     69        end_mwis = read_cycle_counter();
    3570        am.applySubsetConstraints();
     71        end_subset_constraints = read_cycle_counter();
    3672        am.multiplexSelectedIndependentSets();
     73        end_select_independent_sets = read_cycle_counter();
    3774        am.topologicalSort(entry);
    38         return true;
    39     }
    40     return false;
     75        end_topological_sort = read_cycle_counter();
     76        modified = true;
     77    }
     78
     79    std::cerr << "Initialize:              " << (end_initialize - start) << std::endl;
     80    std::cerr << "Characterize:            " << (end_characterize - end_initialize) << std::endl;
     81    std::cerr << "Shutdown:                " << (end_shutdown - end_characterize) << std::endl;
     82    std::cerr << "GenerateMultiplexSets:   " << (end_create_multiplex_graph - end_shutdown) << std::endl;
     83    std::cerr << "MaxWeightIndependentSet: " << (end_mwis - end_create_multiplex_graph) << std::endl;
     84    std::cerr << "ApplySubsetConstraints:  " << (end_subset_constraints - end_mwis) << std::endl;
     85    std::cerr << "MultiplexSelectedSets:   " << (end_select_independent_sets - end_subset_constraints) << std::endl;
     86    std::cerr << "TopologicalSort:         " << (end_topological_sort - end_select_independent_sets) << std::endl;
     87
     88
     89    return modified;
    4190}
    4291
     
    52101
    53102    flat_map<const PabloAST *, unsigned> map;
    54     std::vector<const Statement *> complex;
     103    std::vector<const Statement *> complexStatements;
    55104    std::stack<const Statement *> scope;
    56105
     
    79128                case PabloAST::ClassTypeId::ScanThru:
    80129                case PabloAST::ClassTypeId::MatchStar:
    81                     complex.push_back(stmt);
     130                    complexStatements.push_back(stmt);
    82131                    break;
    83132                default:
     
    187236
    188237    // Initialize the BDD engine ...
    189     mManager = Cudd_Init((complex.size() + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     238    mManager = Cudd_Init((complexStatements.size() + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    190239    Cudd_AutodynDisable(mManager);
    191240
     
    197246    // be the most complex to resolve.
    198247    unsigned i = 0;
    199     for (const Statement * stmt : complex) {
     248    for (const Statement * stmt : complexStatements) {
    200249        mCharacterizationMap.emplace(stmt, Cudd_bddIthVar(mManager, i++));
    201250    }
     
    219268
    220269    // TODO: What if we did some minterm analysis in here? We'd need to be careful to keep the Advances properly indexed.
     270
     271    unsigned comparisons = 0;
     272    unsigned avoided = 0;
    221273
    222274    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     
    320372                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    321373                            if (constrained && (stmt->getOperand(1) == adv->getOperand(1)) && (notTransitivelyDependant(k, i))) {
     374                                ++comparisons;
    322375                                DdNode * Ii = std::get<0>(advances[i]);
    323376                                DdNode * Ni = std::get<1>(advances[i]);
     
    338391                                        const auto j = source(*ei, mSubsetGraph);
    339392                                        if (j > i && notTransitivelyDependant(k, j)) {
    340                                             assert (mCharacterizationMap.count(mAdvance[j]));
    341                                             DdNode *& Cj = mCharacterizationMap[mAdvance[j]];
     393                                            Advance * adv = mAdvance[j];
     394                                            assert (mCharacterizationMap.count(adv));
     395                                            DdNode *& Cj = mCharacterizationMap[adv];
    342396                                            DdNode * Nj = std::get<1>(advances[j]);
    343397                                            // Mark the i-th and j-th Advances as being mutually exclusive
     
    345399                                            Cj = And(Cj, Nk);
    346400                                            unconstrained[j] = true;
     401                                            ++avoided;
    347402                                        }
    348403                                    }
     
    361416                                            add_edge(k, j, mSubsetGraph);
    362417                                            unconstrained[j] = true;
     418                                            ++avoided;
    363419                                        }
    364420                                    }
     
    375431                                            add_edge(j, k, mSubsetGraph);
    376432                                            unconstrained[j] = true;
     433                                            ++avoided;
    377434                                        }
    378435                                    }
     
    420477        scope.pop();
    421478    }
     479
     480    std::cerr << "comparisons: " << comparisons << ", avoided: " << avoided << std::endl;
    422481}
    423482
     
    574633    for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) {
    575634        M.emplace(i, *vi);
    576         G[*vi] = std::make_pair(out_degree(i, mMultiplexSetGraph), i);
     635        G[*vi] = std::make_tuple(out_degree(i, mMultiplexSetGraph), 0, i);
    577636    }
    578637
     
    603662
    604663        // Select a vertex vi whose weight as greater than the average weight of its neighbours ...
    605 
    606         auto i = RNGDistribution(0, num_vertices(G) - 1)(rng);
    607         for (std::tie(vi, vi_end) = vertices(G); i && vi != vi_end; ++vi, --i);
    608 
    609         const unsigned Vw = G[*vi].first * (degree(*vi, G) + 1);
    610 
    611         unsigned Nw = 0;
     664        #ifdef USE_WEIGHTED_SELECTION
     665        int Tw = 0;
     666        for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
     667            int Vw = std::get<0>(G[*vi]) * (degree(*vi, G) + 1);
     668            int Nw = 0;
     669            graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
     670            std::tie(ai, ai_end) = adjacent_vertices(*vi, G);
     671            for (; ai != ai_end; ++ai) {
     672                Nw += std::get<0>(G[*ai]);
     673            }
     674            Vw = std::max<int>(Vw - Nw, 0);
     675            // Vw *= Vw;
     676            std::get<1>(G[*vi]) = Vw;
     677            Tw += Vw;
     678        }
     679
     680        int w = RNGDistribution(0, Tw - 1)(rng);
     681        for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) {
     682            w -= std::get<1>(G[*vi]);
     683            if (w < 0) {
     684                break;
     685            }
     686        }
     687        #else
     688        auto i = RNGDistribution(1, num_vertices(G))(rng);
     689        for (std::tie(vi, vi_end) = vertices(G); --i != 0; ++vi);
     690        #endif
     691        assert (vi != vi_end);
     692
     693        // Then add it to our set and remove it and its neighbourhood from G
     694        A.reserve(degree(*vi, G) + 1);
     695        // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively
     696        // choose the set refered to by vi as one of our chosen independent sets.
    612697        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
    613         std::tie(ai, ai_end) = adjacent_vertices(*vi, G);
    614         for (; ai != ai_end; ++ai) {
    615             Nw += G[*ai].first;
    616         }
    617 
    618         // Then add it to our set and remove it and its neighbourhood from G
    619 
    620         if (Nw <= Vw) {
    621             A.reserve(degree(*vi, G) + 1);
    622             // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively
    623             // choose the set refered to by vi as one of our chosen independent sets.
    624             graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
    625             A.push_back(*vi);
    626             for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) {
    627                 clear_out_edges(G[*ai].second, mMultiplexSetGraph);
    628                 A.push_back(*ai);
    629             }
    630             for (auto u : A) {
    631                 clear_vertex(u, G);
    632                 remove_vertex(u, G);
    633             }
    634             A.clear();
    635         }
    636 
    637 
     698        A.push_back(*vi);
     699        for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) {
     700            clear_out_edges(std::get<2>(G[*ai]), mMultiplexSetGraph);
     701            A.push_back(*ai);
     702        }
     703        for (auto u : A) {
     704            clear_vertex(u, G);
     705            remove_vertex(u, G);
     706        }
     707        A.clear();
     708    }
     709
     710    for (unsigned i = m; i != (m + n); ++i) {
     711        if (out_degree(i, mMultiplexSetGraph) > 0) {
     712            std::cerr << out_degree(i, mMultiplexSetGraph) << std::endl;
     713        }
    638714    }
    639715
Note: See TracChangeset for help on using the changeset viewer.