Changeset 4757


Ignore:
Timestamp:
Sep 3, 2015, 11:17:33 AM (4 years ago)
Author:
nmedfort
Message:

Minor changes

File:
1 edited

Legend:

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

    r4756 r4757  
    329329    summarizeAST(block, terminals, G);
    330330    redistributeAST(block, G);
    331 
    332 //    for (;;) {
    333 //        summarizeAST(block, terminals, G);
    334 //        if (redistributeAST(block, G)) {
    335 //            G.clear();
    336 //        } else {
    337 //            break;
    338 //        }
    339 //    }
    340331
    341332    printGraph(block, G, "G");
     
    615606
    616607using VertexSet = std::vector<Vertex>;
    617 using VertexSets = std::set<VertexSet>;
     608using VertexSets = std::vector<VertexSet>;
    618609
    619610/** ------------------------------------------------------------------------------------------------------------- *
     
    625616 * (star) cliques, this does not record them.
    626617 ** ------------------------------------------------------------------------------------------------------------- */
    627 static std::vector<VertexSet> mica(const Graph & G) {
    628 
    629     VertexSets B1;
     618template <class Graph>
     619static VertexSets mica(const Graph & G) {
     620    using IntersectionSets = std::set<VertexSet>;
     621
     622    IntersectionSets B1;
    630623    for (auto u : make_iterator_range(vertices(G))) {
    631624        if (in_degree(u, G) == 0) {
     
    640633    }
    641634
    642     VertexSets Bi;
    643 
     635    IntersectionSets Bi;
    644636    VertexSet clique;
    645637    for (auto i = B1.begin(); i != B1.end(); ++i) {
     
    653645    }
    654646
    655     VertexSets C;
    656 
     647    IntersectionSets C;
    657648    for (;;) {
    658649        if (Bi.empty()) {
     
    661652        C.insert(Bi.begin(), Bi.end());
    662653
    663         VertexSets Bk;
     654        IntersectionSets Bk;
    664655        for (auto i = B1.begin(); i != B1.end(); ++i) {
    665656            for (auto j = Bi.begin(); j != Bi.end(); ++j) {
     
    676667    }
    677668
    678     return std::vector<VertexSet>(C.begin(), C.end());
     669    return VertexSets(C.begin(), C.end());
    679670}
    680671
     
    683674 ** ------------------------------------------------------------------------------------------------------------- */
    684675template <class Type>
    685 inline bool areNonDisjoint(const Type & A, const Type & B) {
     676inline bool intersects(const Type & A, const Type & B) {
    686677    auto first1 = A.begin(), last1 = A.end();
    687678    auto first2 = B.begin(), last2 = B.end();
     
    701692 * @brief maximalIndependentSet
    702693 ** ------------------------------------------------------------------------------------------------------------- */
    703 static void maximalIndependentSet(std::vector<VertexSet> & V) {
     694static void maximalIndependentSet(VertexSets & V) {
    704695    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    705696    const auto l = V.size();
     
    712703    for (unsigned i = 0; i != l; ++i) {
    713704        for (unsigned j = i + 1; j != l; ++j) {
    714             if (areNonDisjoint(V[i], V[j])) {
     705            if (intersects(V[i], V[j])) {
    715706                add_edge(i, j, I);
    716707            }
     
    718709    }
    719710    // Use the greedy algorithm to choose our independent set (TODO: try the similar randomized approach)
    720     std::vector<Vertex> selected;
    721 
     711    VertexSet selected;
    722712    std::vector<bool> ignored(l, false);
    723713    for (;;) {
     
    739729
    740730    // Sort the selected list and then remove the unselected sets from V
    741     std::sort(selected.begin(), selected.end(), std::greater<unsigned>());
     731    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
    742732    auto end = V.end();
    743733    for (const unsigned offset : selected) {
     
    745735    }
    746736    V.erase(V.begin(), end);
    747 
    748 }
    749 
    750 
    751 /** ------------------------------------------------------------------------------------------------------------- *
    752  * @brief maximalIndependentBicliqueSet
    753  ** ------------------------------------------------------------------------------------------------------------- */
    754 static void maximalIndependentBicliqueSet(Graph & G) {
     737}
     738
     739/** ------------------------------------------------------------------------------------------------------------- *
     740 * @brief computeSafeBicliqueSet
     741 ** ------------------------------------------------------------------------------------------------------------- */
     742template <class Graph>
     743static void computeSafeBicliqueSet(Graph & G) {
    755744    // First enumerate our bicliques in G.
    756745    auto R = mica(G);
    757746    // Then compute the maximal independent set of the vertices in the B bipartition.
    758     // NOTE: this means vertices in A can point to more than one vertex in B. These
    759     // have to be resolved specially later.
    760747    maximalIndependentSet(R);
    761     // Update G to reflect our maximal independent biclique set
    762     std::vector<VertexSet> L;
     748    // Finally update G to reflect our chosen bicliques
     749    VertexSets L;
     750    L.reserve(R.size());
    763751    for (const VertexSet & B : R) {
    764752        // Compute our A set
     
    783771        L.emplace_back(std::move(A));
    784772    }
     773    std::vector<Vertex> sources;
    785774    for (auto u : make_iterator_range(vertices(G))) {
    786775        if (in_degree(u, G) == 0) {
    787             clear_out_edges(u, G);
    788         }
     776            sources.push_back(u);
     777        }
     778    }
     779    for (auto u : sources) {
     780        clear_out_edges(u, G);
    789781    }
    790782    for (unsigned i = 0; i != R.size(); ++i) {
     
    805797    using TypeId = PabloAST::ClassTypeId;
    806798
    807     Graph B;
    808     Map M;
     799    adjacency_list<hash_setS, vecS, bidirectionalS, Vertex> H;
     800    flat_map<Vertex, Vertex> M;
    809801
    810802    for (const Vertex u : make_iterator_range(vertices(G))) {
     
    847839                        }
    848840                    }
    849                     if (anyOpportunities) {
     841                    if (anyOpportunities) {                       
    850842                        for (auto ob : observed) {
    851843                            if (std::get<1>(ob)) {
    852                                 const Vertex v = std::get<0>(ob);
    853                                 for (auto e : make_iterator_range(out_edges(v, G))) {
    854                                     const Vertex w = target(e, G);
    855                                     if (distributable.count(w)) {
    856                                         add_edge(getVertex(G[v], B, M), getVertex(G[w], B, M), B);
     844                                const Vertex w = std::get<0>(ob);
     845                                for (auto e : make_iterator_range(out_edges(w, G))) {
     846                                    const Vertex v = target(e, G);
     847                                    if (distributable.count(v)) {
     848                                        const Vertex x = getVertex(u, H, M);
     849                                        const Vertex y = getVertex(v, H, M);
     850                                        const Vertex z = getVertex(w, H, M);
     851                                        add_edge(y, x, H);
     852                                        add_edge(z, y, H);
    857853                                    }
    858854                                }
     
    866862
    867863    // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    868     if (num_vertices(B) == 0) {
     864    if (num_vertices(H) == 0) {
    869865        return false;
    870866    }
    871867
    872     printGraph(block, B, "B0");
    873 
    874     // By finding the maximal set of independent bicliques in S,
    875 
    876     maximalIndependentBicliqueSet(B);
    877 
    878 
    879     printGraph(block, B, "B1");
     868    printGraph(block, H, G, "H0");
     869
     870    // By finding the maximal set of bicliques in H=(A,B) ∪ T in which the verticies in bipartition B are
     871    // independent, we can identify a safe set of vertices to apply the distribution law to.
     872    computeSafeBicliqueSet(H);
     873
     874    // If no edges are remaining, no bicliques were found that would have a meaningful impact on the AST.
     875    if (LLVM_UNLIKELY(num_edges(H) == 0)) {
     876        return false;
     877    }
     878
     879    printGraph(block, H, G, "H1");
     880
     881//    for (const Vertex u : make_iterator_range(vertices(H))) {
     882//        if (LLVM_UNLIKELY(in_degree(u, H) == 0 && out_degree(u, H) != 0)) {
     883
     884//        }
     885//    }
     886
    880887
    881888
Note: See TracChangeset for help on using the changeset viewer.