Ignore:
Timestamp:
Dec 17, 2015, 4:45:18 PM (3 years ago)
Author:
nmedfort
Message:

Work on coalescing algorithm + minor changes.

File:
1 edited

Legend:

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

    r4890 r4896  
    160160
    161161        RECORD_TIMESTAMP(start_select_independent_sets);
    162         mp.multiplexSelectedIndependentSets(function);
     162        mp.multiplexSelectedSets(function);
    163163        RECORD_TIMESTAMP(end_select_independent_sets);
    164164        LOG("SelectedIndependentSets:  " << (end_select_independent_sets - start_select_independent_sets));
     
    575575 *
    576576 * Note: it'd be preferable to contract vertices in the constraint graph prior to scanning through it but that
    577  * leaves us with a more difficult problem. Namely, an Advance node may belong to more than one clique and we
    578  * want to avoid generating a multiplexing set whose size is 2^n for any n ∈ â„€* but don't want to needlessly
    579  * limit the size of any clique. Look into this further later.
     577 * leaves us with a more difficult problem. Namely, Advance nodes may belong to more than one clique but it'd be
     578 * useless to compute a value twice; furthermore, we want to avoid generating a multiplexing set whose size is 2^n
     579 * for any n ∈ â„€* but don't want to needlessly limit the size of any clique. Look into this further later.
    580580 ** ------------------------------------------------------------------------------------------------------------- */
    581581void MultiplexingPass::generateUsageWeightingGraph() {
     
    588588        for (unsigned j = i + 1; j != n; ++j) {
    589589            const Advance * const advJ = mAdvance[j];
    590             if (LLVM_UNLIKELY(advI->getNumUsers() == advJ->getNumUsers()) && independent(i, j)) {
     590            if (LLVM_UNLIKELY(advI->getNumUses() == advJ->getNumUses()) && independent(i, j)) {
    591591                if (LLVM_UNLIKELY(std::equal(advI->user_begin(), advI->user_end(), advJ->user_begin()))) {
    592592                    // INVESTIGATE: we should be able to ignore subset relations if these are going to become a
     
    614614        }
    615615    }
    616     mUsageWeightingGraph = G;
     616    mUsageGraph = G;
    617617}
    618618
     
    763763 * enough but can be shown to produce a suboptimal solution if there are three candidate sets labelled A, B and C,
    764764 * in which A ∩ B = âˆ
    765 , |A| ≀ |B| < |C| < (|A| + |B|), and C ∩ (A ∪ B) = C.
     765, |A| ≀ |B| < |C|, and C ⊂ (A ∪ B).
    766766 ** ------------------------------------------------------------------------------------------------------------- */
    767767void MultiplexingPass::selectMultiplexSets() {
     
    798798                for (auto ei = begin; ei != end; ++ei) {
    799799                    for (auto ej = ei; ++ej != end; ) {
    800                         if (edge(target(*ei, mMultiplexSetGraph), target(*ej, mMultiplexSetGraph), mUsageWeightingGraph).second) {
     800                        if (edge(target(*ei, mMultiplexSetGraph), target(*ej, mMultiplexSetGraph), mUsageGraph).second) {
    801801                            ++r;
    802802                        }
     
    901901
    902902        // At least one subset constraint exists; perform a transitive reduction on the graph to ensure that
    903         // we perform the minimum number of AST modifications for the given multiplexing sets.
     903        // we perform the minimum number of AST modifications for the selected multiplexing sets.
    904904
    905905        doTransitiveReductionOfSubsetGraph();
     
    921921
    922922/** ------------------------------------------------------------------------------------------------------------- *
    923  * @brief multiplexSelectedIndependentSets
    924  ** ------------------------------------------------------------------------------------------------------------- */
    925 void MultiplexingPass::multiplexSelectedIndependentSets(PabloFunction &) {
     923 * @brief multiplexSelectedSets
     924 ** ------------------------------------------------------------------------------------------------------------- */
     925void MultiplexingPass::multiplexSelectedSets(PabloFunction &) {
    926926    const auto first_set = num_vertices(mConstraintGraph);
    927927    const auto last_set = num_vertices(mMultiplexSetGraph);
     
    934934            // The multiplex set graph is a DAG with edges denoting the set relationships of our independent sets.
    935935            unsigned i = 0;
    936             for (const auto e : make_iterator_range(out_edges(idx, mMultiplexSetGraph))) {
    937                 input[i++] = mAdvance[target(e, mMultiplexSetGraph)];
     936            for (const auto u : orderMultiplexSet(idx)) {
     937                input[i++] = mAdvance[u];
    938938            }
    939939            Advance * const adv = input[0];
     
    960960                    demuxing[j] = muxed[j];
    961961                    if (((i + 1) & (1UL << j)) == 0) {
    962                         demuxing[j] = block->createNot(demuxing[j]);
     962                        demuxing[j] = block->createNot(muxed[j]);
    963963                    }
    964964                }
     
    971971        }
    972972    }
     973}
     974
     975/** ------------------------------------------------------------------------------------------------------------- *
     976 * @brief orderMultiplexSet
     977 ** ------------------------------------------------------------------------------------------------------------- */
     978inline MultiplexingPass::MultiplexVector MultiplexingPass::orderMultiplexSet(const MultiplexSetGraph::vertex_descriptor u) {
     979    MultiplexVector set;
     980    set.reserve(out_degree(u, mMultiplexSetGraph));
     981    for (const auto e : make_iterator_range(out_edges(u, mMultiplexSetGraph))) {
     982        set.push_back(target(e, mMultiplexSetGraph));
     983    }
     984    std::sort(set.begin(), set.end());
     985    MultiplexVector clique;
     986    MultiplexVector result;
     987    result.reserve(out_degree(u, mMultiplexSetGraph));
     988    while (set.size() > 0) {
     989        const auto v = *set.begin();
     990        clique.push_back(v);
     991        set.erase(set.begin());
     992        for (const auto w : make_iterator_range(adjacent_vertices(v, mUsageGraph))) {
     993            auto f = std::lower_bound(set.begin(), set.end(), w);
     994            // Is w in our multiplexing set?
     995            if (f == set.end() || *f != w) {
     996                continue;
     997            }
     998            // Is our subgraph still a clique after adding w to it?
     999            bool valid = true;
     1000            for (const auto y : clique) {
     1001                if (!edge(w, y, mUsageGraph).second) {
     1002                    valid = false;
     1003                    break;
     1004                }
     1005            }
     1006            if (valid) {
     1007                clique.push_back(w);
     1008                set.erase(f);
     1009            }
     1010        }
     1011        result.insert(result.end(), clique.begin(), clique.end());
     1012        clique.clear();
     1013    }
     1014    return result;
    9731015}
    9741016
Note: See TracChangeset for help on using the changeset viewer.