Changeset 4758


Ignore:
Timestamp:
Sep 3, 2015, 4:06:46 PM (3 years ago)
Author:
nmedfort
Message:

Temporary check-in

File:
1 edited

Legend:

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

    r4757 r4758  
    269269    out << "digraph " << name << " {\n";
    270270    for (auto u : make_iterator_range(vertices(S))) {
     271        if (in_degree(u, S) == 0 && out_degree(u, S) == 0) {
     272            continue;
     273        }
    271274        out << "v" << u << " [label=\"";
    272275        PabloAST * expr = G[S[u]];
     
    608611using VertexSets = std::vector<VertexSet>;
    609612
     613template <class Graph>
     614static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
     615    VertexSet V;
     616    V.reserve(in_degree(u, G));
     617    for (auto e : make_iterator_range(in_edges(u, G))) {
     618        V.push_back(source(e, G));
     619    }
     620    std::sort(V.begin(), V.end());
     621    return std::move(V);
     622}
     623
     624template <class Graph>
     625static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) {
     626    VertexSet V;
     627    V.reserve(out_degree(u, G));
     628    for (auto e : make_iterator_range(out_edges(u, G))) {
     629        V.push_back(target(e, G));
     630    }
     631    std::sort(V.begin(), V.end());
     632    return std::move(V);
     633}
     634
    610635/** ------------------------------------------------------------------------------------------------------------- *
    611636 * @brief mica
     
    613638 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
    614639 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
    615  * to be in bipartition A and their adjacencies to be in bipartition B. Because we do not care about the rank 1
    616  * (star) cliques, this does not record them.
    617  ** ------------------------------------------------------------------------------------------------------------- */
    618 template <class Graph>
     640 * (or out-degree of 0 if the graph is transposed) to be in bipartition A and their adjacencies to be in B.
     641  ** ------------------------------------------------------------------------------------------------------------- */
     642template <bool transposed, class Graph>
    619643static VertexSets mica(const Graph & G) {
    620644    using IntersectionSets = std::set<VertexSet>;
    621645
     646    IntersectionSets C;
     647
    622648    IntersectionSets B1;
    623649    for (auto u : make_iterator_range(vertices(G))) {
    624         if (in_degree(u, G) == 0) {
    625             VertexSet B;
    626             B.reserve(out_degree(u, G));
    627             for (auto e : make_iterator_range(out_edges(u, G))) {
    628                 B.push_back(target(e, G));
    629             }
    630             std::sort(B.begin(), B.end()); // note: these already ought to be in order
    631             B1.insert(std::move(B));
    632         }
    633     }
     650        if ((transposed ? out_degree(u, G) : in_degree(u, G)) == 0) {
     651            B1.insert(std::move(transposed ? incomingVertexSet(u, G) : outgoingVertexSet(u, G)));
     652        }
     653    }
     654
     655    C.insert(B1.begin(), B1.end());
    634656
    635657    IntersectionSets Bi;
     
    639661            std::set_intersection(i->begin(), i->end(), j->begin(), j->end(), std::back_inserter(clique));
    640662            if (clique.size() > 0) {
    641                 Bi.insert(clique);
     663                if (C.count(clique) == 0) {
     664                    Bi.insert(clique);
     665                }
    642666                clique.clear();
    643667            }
     
    645669    }
    646670
    647     IntersectionSets C;
    648671    for (;;) {
    649672        if (Bi.empty()) {
     
    671694
    672695/** ------------------------------------------------------------------------------------------------------------- *
    673  * @brief areNonDisjoint
     696 * @brief intersects
    674697 ** ------------------------------------------------------------------------------------------------------------- */
    675698template <class Type>
     
    692715 * @brief maximalIndependentSet
    693716 ** ------------------------------------------------------------------------------------------------------------- */
    694 static void maximalIndependentSet(VertexSets & V) {
     717static VertexSets && maximalIndependentSet(VertexSets && V) {
    695718    using IndependentSetGraph = adjacency_list<hash_setS, vecS, undirectedS, unsigned>;
    696719    const auto l = V.size();
     
    698721    // Initialize our weights
    699722    for (unsigned i = 0; i != l; ++i) {
    700         I[i] = std::pow(V[i].size(), 2);
     723        I[i] = V[i].size();
    701724    }
    702725    // Determine our constraints
     
    720743            }
    721744        }
    722         if (w < 2) break;
     745        if (w == 0) break;
    723746        selected.push_back(u);
    724747        ignored[u] = true;
     
    727750        }
    728751    }
    729 
    730752    // Sort the selected list and then remove the unselected sets from V
    731753    std::sort(selected.begin(), selected.end(), std::greater<Vertex>());
     
    735757    }
    736758    V.erase(V.begin(), end);
     759    return std::move(V);
     760}
     761
     762/** ------------------------------------------------------------------------------------------------------------- *
     763 * @brief filterBicliqueGraph
     764 ** ------------------------------------------------------------------------------------------------------------- */
     765template <bool transposed, class Graph>
     766static VertexSets filterBicliqueGraph(Graph & G) {
     767    VertexSets B(std::move(maximalIndependentSet(std::move(mica<transposed>(G)))));
     768    VertexSets A;
     769    A.reserve(B.size());
     770    for (const VertexSet & Bi : B) {
     771        // Compute our A set
     772        auto bi = Bi.begin();
     773        VertexSet Ai(std::move(transposed ? outgoingVertexSet(*bi, G) : incomingVertexSet(*bi, G)));
     774        while (++bi != Bi.end()) {
     775            VertexSet Ai(std::move(transposed ? outgoingVertexSet(*bi, G) : incomingVertexSet(*bi, G)));
     776            VertexSet Ak;
     777            std::set_intersection(Ai.begin(), Ai.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak));
     778            Ai.swap(Ak);
     779        }
     780        A.emplace_back(std::move(Ai));
     781    }
     782    if (transposed) {
     783        std::vector<Vertex> sinks;
     784        std::vector<Vertex> intermediary;
     785        for (auto u : make_iterator_range(vertices(G))) {
     786            if (out_degree(u, G) == 0) {
     787                sinks.push_back(u);
     788            } else if (in_degree(u, G) != 0) {
     789                intermediary.push_back(u);
     790            }
     791        }
     792        for (auto u : sinks) {
     793            clear_in_edges(u, G);
     794        }
     795        for (unsigned i = 0; i != B.size(); ++i) {
     796            for (auto u : A[i]) {
     797                for (auto v : B[i]) {
     798                    add_edge(v, u, G);
     799                }
     800            }
     801        }
     802        for (auto u : intermediary) {
     803            if (out_degree(u, G) == 0) {
     804                clear_in_edges(u, G);
     805            }
     806        }
     807    } else {
     808        std::vector<Vertex> sources;
     809        std::vector<Vertex> intermediary;
     810        for (auto u : make_iterator_range(vertices(G))) {
     811            if (in_degree(u, G) == 0) {
     812                sources.push_back(u);
     813            } else if (out_degree(u, G) != 0) {
     814                intermediary.push_back(u);
     815            }
     816        }
     817        for (auto u : sources) {
     818            clear_out_edges(u, G);
     819        }
     820        for (unsigned i = 0; i != B.size(); ++i) {
     821            for (auto u : A[i]) {
     822                for (auto v : B[i]) {
     823                    add_edge(u, v, G);
     824                }
     825            }
     826        }
     827        for (auto u : intermediary) {
     828            if (in_degree(u, G) == 0) {
     829                clear_out_edges(u, G);
     830            }
     831        }
     832    }
     833    return std::move(A);
    737834}
    738835
     
    741838 ** ------------------------------------------------------------------------------------------------------------- */
    742839template <class Graph>
    743 static void computeSafeBicliqueSet(Graph & G) {
    744     // First enumerate our bicliques in G.
    745     auto R = mica(G);
    746     // Then compute the maximal independent set of the vertices in the B bipartition.
    747     maximalIndependentSet(R);
    748     // Finally update G to reflect our chosen bicliques
    749     VertexSets L;
    750     L.reserve(R.size());
    751     for (const VertexSet & B : R) {
    752         // Compute our A set
    753         VertexSet A;
    754         auto bi = B.begin();
    755         A.reserve(in_degree(*bi, G));
    756         for (auto e : make_iterator_range(in_edges(*bi, G))) {
    757             A.push_back(source(e, G));
    758         }
    759         std::sort(A.begin(), A.end());
    760         while (++bi != B.end()) {
    761             VertexSet Ai;
    762             Ai.reserve(in_degree(*bi, G));
    763             for (auto e : make_iterator_range(in_edges(*bi, G))) {
    764                 Ai.push_back(source(e, G));
    765             }
    766             std::sort(Ai.begin(), Ai.end());
    767             VertexSet Ak;
    768             std::set_intersection(A.begin(), A.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak));
    769             A.swap(Ak);
    770         }
    771         L.emplace_back(std::move(A));
    772     }
    773     std::vector<Vertex> sources;
    774     for (auto u : make_iterator_range(vertices(G))) {
    775         if (in_degree(u, G) == 0) {
    776             sources.push_back(u);
    777         }
    778     }
    779     for (auto u : sources) {
    780         clear_out_edges(u, G);
    781     }
    782     for (unsigned i = 0; i != R.size(); ++i) {
    783         for (auto u : L[i]) {
    784             for (auto v : R[i]) {
    785                 add_edge(u, v, G);
    786             }
    787         }
    788     }
     840static VertexSets computeSafeBicliqueSet(Graph & G) {
     841    VertexSets sinks(std::move(filterBicliqueGraph<true>(G)));
     842    // scan through G and replicate any source that has more than one sink until G is broken
     843    // into weakly connected components with exactly one sink.
     844    if (sinks.size() > 1) {
     845        std::vector<unsigned> component(num_vertices(G), 0);
     846        unsigned components = 0;
     847        for (const VertexSet & S : sinks) {
     848            ++components;
     849            for (auto e : make_iterator_range(in_edges(S.front(), G))) {
     850                component[source(e, G)] = components;
     851            }
     852        }
     853        for (const Vertex u : make_iterator_range(vertices(G))) {
     854            if (LLVM_UNLIKELY(in_degree(u, G) == 0)) {
     855                flat_set<unsigned> membership;
     856                for (auto e : make_iterator_range(out_edges(u, G))) {
     857                    membership.insert(component[target(e, G)]);
     858                }
     859                if (LLVM_UNLIKELY(membership.size() > 1)) {
     860                    VertexSet adjacent;
     861                    adjacent.reserve(out_degree(u, G));
     862                    for (auto e : make_iterator_range(out_edges(u, G))) {
     863                        adjacent.push_back(target(e, G));
     864                    }
     865                    clear_out_edges(u, G);
     866                    auto mi = membership.begin();
     867                    for (Vertex uu = u; ;) {
     868                        const unsigned m = *mi;
     869                        for (auto v : adjacent) {
     870                            if (component[v] == m) {
     871                                add_edge(uu, v, G);
     872                            }
     873                        }
     874                        if (++mi == membership.end()) {
     875                            break;
     876                        }
     877                        uu = add_vertex(G[u], G);
     878                    }
     879                }
     880            }
     881        }
     882    }
     883    return std::move(filterBicliqueGraph<false>(G));
    789884}
    790885
     
    870965    // By finding the maximal set of bicliques in H=(A,B) ∪ T in which the verticies in bipartition B are
    871966    // 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)) {
     967    VertexSets sources(std::move(computeSafeBicliqueSet(H)));
     968
     969    // If no sources remain, no bicliques were found that would have a meaningful impact on the AST.
     970    if (LLVM_UNLIKELY(sources.size() == 0)) {
    876971        return false;
    877972    }
     
    879974    printGraph(block, H, G, "H1");
    880975
    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 
    887976
    888977
Note: See TracChangeset for help on using the changeset viewer.