Changeset 4571 for icGREP


Ignore:
Timestamp:
May 22, 2015, 5:09:26 PM (4 years ago)
Author:
nmedfort
Message:

More work on multiplexing

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/analysis/bdd/bdd.hpp

    r4569 r4571  
    111111    }
    112112
    113     inline int operator==(const bool term) const {
    114         return term ? isFalse() : isTrue();
     113    inline BDD & operator=(const bool term) const {
     114        mRoot = term ? 0 : 1;
     115        return *this;
    115116    }
    116117
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4570 r4571  
    2323    Engine eng = am.initialize(vars, block);
    2424    am.characterize(eng, block);
     25    am.createMappingGraph();
    2526    RNG rng(std::random_device()());
    2627    am.generateMultiplexSets(rng);
    2728    am.approxMaxWeightIndependentSet();
     29    am.applySubsetConstraints();
    2830    am.multiplexSelectedIndependentSets();
    2931}
     
    194196    std::stack<const Statement *> scope;
    195197
    196    
    197    
    198198    unsigned variables = 0;
    199199
    200200    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    201201    for (const Statement * stmt = entry.front(); ; ) {
    202         for (; stmt; stmt = stmt->getNextNode()) {
     202        while ( stmt ) {
    203203
    204204            if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) {
     
    234234                case PabloAST::ClassTypeId::And:
    235235                    bdd = engine.applyAnd(input[0], input[1]);
    236                     if (LLVM_UNLIKELY(engine.satOne(bdd).isFalse())) {
    237                         bdd = BDD::Contradiction();
    238                         // Look into making a "replaceAllUsesWithZero" method that can recursively apply
    239                         // the implication of having a Zero output.
    240                         stmt->replaceAllUsesWith(entry.createZeroes());
    241                         stmt->eraseFromParent(true);
    242                     }
    243236                    break;
    244237                case PabloAST::ClassTypeId::Or:
     
    257250                case PabloAST::ClassTypeId::ScanThru:
    258251                    // It may be possible use "engine.applyNot(input[1])" for ScanThrus if we rule out the
    259                     // possibility of a contradition being calculated later. An example of this would be
    260                     // ¬(ScanThru(c,m) √ m) but are there others that would be harder to predict?
     252                    // possibility of a contradition being erroneously calculated later. An example of this
     253                    // would be ¬(ScanThru(c,m) √ m) but are there others that would be harder to predict?
     254                case PabloAST::ClassTypeId::MatchStar:
     255                    if (LLVM_UNLIKELY(input[0] == false || input[1] == false)) {
     256                        bdd = false;
     257                        break;
     258                    }
    261259                case PabloAST::ClassTypeId::Call:
    262                 case PabloAST::ClassTypeId::MatchStar:
    263260                    bdd = engine.var(variables++);
    264261                    break;
    265                 case PabloAST::ClassTypeId::Advance: {
     262                case PabloAST::ClassTypeId::Advance:
     263                    if (LLVM_UNLIKELY(input[0] == false)) {
     264                        bdd = false;
     265                    }
     266                    else {
     267
    266268                        const BDD var = engine.var(variables++);
    267269
    268270                        bdd = var;
    269271
    270                         // when we built the path graph, we constructed it in the same order; hense the row/column of
     272                        // When we built the path graph, we constructed it in the same order; hense the row/column of
    271273                        // the path graph is equivalent to the index.
    272274
     
    313315                    break;
    314316            }
    315             mCharacterizationMap.insert(std::make_pair(stmt, bdd));
     317            if (LLVM_UNLIKELY(engine.satOne(bdd) == false)) {
     318                stmt = stmt->replaceWith(entry.createZeroes());
     319            }
     320            else {
     321                mCharacterizationMap.insert(std::make_pair(stmt, bdd));
     322                stmt = stmt->getNextNode();
     323            }
    316324        }
    317325
     
    322330        scope.pop();
    323331    }
     332}
     333
     334/** ------------------------------------------------------------------------------------------------------------- *
     335 * @brief createMappingGraph
     336 ** ------------------------------------------------------------------------------------------------------------- */
     337void AutoMultiplexing::createMappingGraph() {
     338    mMappingGraph = MappingGraph(num_vertices(mConstraintGraph));
    324339}
    325340
     
    345360        D[*vi] = d;
    346361        if (d == 0) {
    347             S.insert(*vi);
     362            S.push_back(*vi);
    348363        }
    349364    }
    350365
    351366    for ( ; remainingVerticies >= 3; --remainingVerticies) {
    352         if (S.size() > 2) {
     367        if (S.size() >= 3) {
    353368            addMultiplexSet(S);
    354         }
     369        }       
    355370        // Randomly choose a vertex in S and discard it.
     371        assert (!S.empty());
    356372        const auto i = S.begin() + RNGDistribution(0, S.size() - 1)(rng);
    357373        const Vertex u = *i;
     
    361377            const Vertex v = target(*ei, mConstraintGraph);
    362378            if ((--D[v]) == 0) {
    363                 S.insert(v);
    364             }
    365         }
    366     }
     379                S.push_back(v);
     380            }
     381        }
     382    }
     383
    367384}
    368385
     
    371388 * @param set an independent set
    372389 ** ------------------------------------------------------------------------------------------------------------- */
    373 void AutoMultiplexing::addMultiplexSet(const IndependentSet & set) {
    374 
    375 
    376 }
    377 
    378 
    379 AutoMultiplexing::AutoMultiplexing()
    380 {
    381 
    382 }
    383 
    384 
    385 }
     390inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & set) {
     391
     392    // At this stage, the mapping graph is a directed bipartite graph that is used to show relationships between
     393    // the advance vertices and a "set vertex" for each independent set we find from "generateMultiplexSets".
     394
     395    const auto v = add_vertex(mMappingGraph);
     396    for (auto u : set) {
     397        add_edge(u, v, mMappingGraph);
     398    }
     399}
     400
     401/** ------------------------------------------------------------------------------------------------------------- *
     402 * @brief approxMaxWeightIndependentSet
     403 ** ------------------------------------------------------------------------------------------------------------- */
     404void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) {
     405
     406    // Compute our independent set graph from our mapping graph; effectively it's the graph resulting
     407    // from contracting one advance node edge with an adjacent vertex
     408
     409    const unsigned m = num_vertices(mConstraintGraph);
     410    const unsigned n = num_vertices(mMappingGraph) - m;
     411
     412    IndependentSetGraph G(n);
     413
     414    // Record the "weight" of this independent set vertex
     415    for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) {
     416        G[i] = in_degree(m + i, mMappingGraph);
     417    }
     418    // Add in any edges based on the adjacencies in the mapping graph
     419    for (MappingGraph::vertex_descriptor i = 0; i != m; ++i) {
     420        graph_traits<MappingGraph>::out_edge_iterator ei, ei_end;
     421        std::tie(ei, ei_end) = out_edges(i, mMappingGraph);
     422        for (; ei != ei_end; ++ei) {
     423            for (auto ej = ei; ej != ei; ++ej) {
     424                add_edge(*ei - m, *ej - m, G);
     425            }
     426        }
     427    }
     428    // Process the graph using the greedy method of "Approximation Algorithms for the Weighted Independent Set Problem" (2005)
     429    std::vector<IndependentSetGraph::vertex_descriptor> S;
     430    std::vector<bool> removed(n, false);
     431    for (;;) {
     432        // Select the miminum weight vertex
     433        graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end;
     434        std::tie(vi, vi_end) = vertices(G);
     435        unsigned W = std::numeric_limits<unsigned>::max();
     436        for (; vi != vi_end; ++vi) {
     437            if (removed[*vi]) {
     438                continue;
     439            }
     440            const unsigned w = G[*vi];
     441            if (w <= W) {
     442                if (w < W) {
     443                    W = w;
     444                    S.clear();
     445                }
     446                S.push_back(*vi);
     447            }
     448        }
     449        if (S.empty()) {
     450            break;
     451        }
     452
     453        const auto u = S[S.size() == 1 ? 0 : RNGDistribution(0, S.size() - 1)(rng)];
     454        // Remove it and its adjacencies from G; clear the adjacent set vertices from the mapping graph
     455        graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end;
     456        std::tie(ai, ai_end) = adjacent_vertices(u, G);
     457        for (; ai != ai_end; ++ai) {
     458            removed[*ai] = true;
     459            clear_in_edges(m + *ai, mMappingGraph);
     460        }
     461        removed[u] = true;
     462    }
     463}
     464
     465/** ------------------------------------------------------------------------------------------------------------- *
     466 * @brief applySubsetConstraints
     467 ** ------------------------------------------------------------------------------------------------------------- */
     468void AutoMultiplexing::applySubsetConstraints() {
     469
     470    // The mapping graph now contains edges denoting the set relationships of our independent sets.
     471    // Add in any edges from our subset constraints to the Mapping Graph that are within the same set.
     472
     473    graph_traits<SubsetGraph>::edge_iterator ei, ei_end;
     474    for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) {
     475        const auto u = source(*ei, mSubsetGraph);
     476        const auto v = target(*ei, mSubsetGraph);
     477        graph_traits<MappingGraph>::out_edge_iterator ej, ej_end;
     478        for (std::tie(ej, ej_end) = out_edges(u, mMappingGraph); ej != ej_end; ++ej) {
     479            // If both the source and target of ei are adjacent to the same vertex, that vertex must be the
     480            // "set vertex". Add the edge between the vertices.
     481            if (edge(v, target(*ej, mMappingGraph)).second) {
     482                add_edge(u, v, mMappingGraph);
     483            }
     484        }
     485    }
     486
     487}
     488
     489
     490/** ------------------------------------------------------------------------------------------------------------- *
     491 * @brief multiplexSelectedIndependentSets
     492 ** ------------------------------------------------------------------------------------------------------------- */
     493void AutoMultiplexing::multiplexSelectedIndependentSets() {
     494
     495
     496
     497}
     498
     499}
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4570 r4571  
    2222    using PathGraph = boost::adjacency_matrix<boost::undirectedS>;
    2323    using SubsetGraph = boost::edge_list<std::pair<unsigned, unsigned>>;
     24    using MappingGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
     25    using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS, unsigned>;
    2426    using IndexMap = boost::container::flat_map<PabloAST *, unsigned>;
    2527
     
    2931    using Vertex = ConstraintGraph::vertex_descriptor;
    3032
    31     using IndependentSet = boost::container::flat_set<Vector>;
     33    using IndependentSet = std::vector<Vertex>;
    3234
    3335public:
     
    3840    void generateMultiplexSets(RNG & rng);
    3941    void addMultiplexSet(const IndependentSet & set);
    40     void approxMaxWeightIndependentSet();
     42    void approxMaxWeightIndependentSet(RNG & rng);
     43    void applySubsetConstraints();
    4144    void multiplexSelectedIndependentSets();
    4245
     
    4952    SubsetGraph             mSubsetGraph;
    5053    IndexMap                mIndexMap;
    51 
     54    MappingGraph            mMappingGraph;
    5255};
    5356
Note: See TracChangeset for help on using the changeset viewer.