Changeset 4760 for icGREP


Ignore:
Timestamp:
Sep 4, 2015, 4:44:59 PM (4 years ago)
Author:
nmedfort
Message:

More work on reassociation + distribution pass

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
1 added
1 edited

Legend:

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

    r4759 r4760  
    1212#include <iostream>
    1313#include <pablo/printer_pablos.h>
    14 
     14#include "graph-facade.hpp"
    1515
    1616using namespace boost;
     
    187187        PabloAST * e2 = Q.front(); Q.pop_front();
    188188        PabloAST * expr = nullptr;
     189        // Note: this switch ought to compile to an array of function pointers to the appropriate method.
    189190        switch (typeId) {
    190191            case PabloAST::ClassTypeId::And:
     
    331332
    332333    summarizeAST(block, terminals, G);
    333     redistributeAST(block, G);
    334 
    335334    printGraph(block, G, "G");
    336 
     335    if (redistributeAST(block, G)) {
     336        printGraph(block, G, "H");
     337    }
    337338}
    338339
     
    614615static VertexSet incomingVertexSet(const Vertex u, const Graph & G) {
    615616    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));
     617    V.reserve(G.in_degree(u));
     618    for (auto e : make_iterator_range(G.in_edges(u))) {
     619        V.push_back(G.source(e));
    619620    }
    620621    std::sort(V.begin(), V.end());
     
    625626static VertexSet outgoingVertexSet(const Vertex u, const Graph & G) {
    626627    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));
     628    V.reserve(G.out_degree(u));
     629    for (auto e : make_iterator_range(G.out_edges(u))) {
     630        V.push_back(G.target(e));
    630631    }
    631632    std::sort(V.begin(), V.end());
     
    634635
    635636/** ------------------------------------------------------------------------------------------------------------- *
    636  * @brief mica
     637 * @brief enumerateBicliques
    637638 *
    638639 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal
    639640 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies with an in-degree of 0
    640  * (or out-degree of 0 if the graph is transposed) to be in bipartition A and their adjacencies to be in B.
     641 * to be in bipartition A and their adjacencies to be in B.
    641642  ** ------------------------------------------------------------------------------------------------------------- */
    642 template <bool transposed, class Graph>
    643 static VertexSets mica(const Graph & G) {
     643template <class Graph>
     644static VertexSets enumerateBicliques(const Graph & G) {
    644645    using IntersectionSets = std::set<VertexSet>;
    645646
    646     IntersectionSets C;
    647 
    648647    IntersectionSets B1;
    649     for (auto u : make_iterator_range(vertices(G))) {
    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());
     648    for (auto u : make_iterator_range(G.vertices())) {
     649        if (G.in_degree(u) == 0) {
     650            B1.insert(std::move(outgoingVertexSet(u, G)));
     651        }
     652    }
     653
     654    IntersectionSets C(B1.begin(), B1.end());
    656655
    657656    IntersectionSets Bi;
     
    674673        }
    675674        C.insert(Bi.begin(), Bi.end());
    676 
    677675        IntersectionSets Bk;
    678676        for (auto i = B1.begin(); i != B1.end(); ++i) {
     
    761759
    762760/** ------------------------------------------------------------------------------------------------------------- *
    763  * @brief filterBicliqueGraph
    764  ** ------------------------------------------------------------------------------------------------------------- */
    765 template <bool transposed, class Graph>
    766 static VertexSets filterBicliqueGraph(Graph & G) {
    767     VertexSets B(std::move(maximalIndependentSet(std::move(mica<transposed>(G)))));
     761 * @brief sinkIndependentBicliques
     762 ** ------------------------------------------------------------------------------------------------------------- */
     763template <class Graph>
     764static VertexSets sinkIndependentBicliques(Graph && G) {
     765    VertexSets B = maximalIndependentSet(std::move(enumerateBicliques(G)));
    768766    VertexSets A;
    769767    A.reserve(B.size());
     
    771769        // Compute our A set
    772770        auto bi = Bi.begin();
    773         VertexSet Ai(std::move(transposed ? outgoingVertexSet(*bi, G) : incomingVertexSet(*bi, G)));
     771        VertexSet Ai = incomingVertexSet(*bi, G);
    774772        while (++bi != Bi.end()) {
    775             VertexSet Ai(std::move(transposed ? outgoingVertexSet(*bi, G) : incomingVertexSet(*bi, G)));
     773            VertexSet Ai = incomingVertexSet(*bi, G);
    776774            VertexSet Ak;
    777775            std::set_intersection(Ai.begin(), Ai.end(), Ai.begin(), Ai.end(), std::back_inserter(Ak));
     
    780778        A.emplace_back(std::move(Ai));
    781779    }
    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             }
     780    std::vector<Vertex> sources;
     781    std::vector<Vertex> intermediary;
     782    for (auto u : make_iterator_range(G.vertices())) {
     783        if (G.in_degree(u) == 0) {
     784            sources.push_back(u);
     785        } else if (G.out_degree(u) != 0) {
     786            intermediary.push_back(u);
     787        }
     788    }
     789    for (auto u : sources) {
     790        G.clear_out_edges(u);
     791    }
     792    for (unsigned i = 0; i != B.size(); ++i) {
     793        for (auto u : A[i]) {
     794            for (auto v : B[i]) {
     795                G.add_edge(u, v);
     796            }
     797        }
     798    }
     799    for (auto u : intermediary) {
     800        if (G.in_degree(u) == 0) {
     801            G.clear_out_edges(u);
    831802        }
    832803    }
     
    835806
    836807/** ------------------------------------------------------------------------------------------------------------- *
    837  * @brief computeSafeBicliqueSet
     808 * @brief safeDistributionSets
    838809 ** ------------------------------------------------------------------------------------------------------------- */
    839810template <class Graph>
    840 static 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.
     811static VertexSets safeDistributionSets(Graph & G) {
     812    VertexSets sinks(std::move(sinkIndependentBicliques(makeTransposedGraphFacade(G))));
     813    // Scan through G and replicate any source that has more than one sink until G is broken
     814    // into weakly connected components in which each has exactly one sink.
    844815    if (sinks.size() > 1) {
    845816        std::vector<unsigned> component(num_vertices(G), 0);
     
    881852        }
    882853    }
    883     return std::move(filterBicliqueGraph<false>(G));
     854    return std::move(sinkIndependentBicliques(makeGraphFacade(G)));
     855}
     856
     857/** ------------------------------------------------------------------------------------------------------------- *
     858 * @brief segmentInto3LevelGraph
     859 *
     860 * Ensure that every source-to-sink path in G has a distance of exactly 2.
     861 ** ------------------------------------------------------------------------------------------------------------- */
     862template <class Graph>
     863Graph & segmentInto3LevelGraph(Graph & G) {
     864
     865    std::vector<Vertex> ordering;
     866    ordering.reserve(num_vertices(G));
     867
     868    topological_sort(G, std::back_inserter(ordering));
     869
     870    std::vector<unsigned> distance(num_vertices(G));
     871    // Compute the distance to furthest sink for each node
     872    for (Vertex u : ordering) {
     873        unsigned d = 0;
     874        for (auto e : make_iterator_range(out_edges(u, G))) {
     875            d = std::max<unsigned>(d, distance[target(e, G)] + 1);
     876        }
     877        distance[u] = d;
     878    }
     879
     880
     881
     882
     883    return G;
    884884}
    885885
     
    892892    using TypeId = PabloAST::ClassTypeId;
    893893
    894     adjacency_list<hash_setS, vecS, bidirectionalS, Vertex> H;
    895     flat_map<Vertex, Vertex> M;
    896 
    897     for (const Vertex u : make_iterator_range(vertices(G))) {
    898         const TypeId outerTypeId = G[u]->getClassTypeId();
    899         if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
    900             if (inCurrentBlock(cast<Statement>(G[u]), block)) {
    901                 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
    902                 flat_set<Vertex> distributable;
    903                 for (auto e : make_iterator_range(in_edges(u, G))) {
    904                     const Vertex v = source(e, G);
    905                     if (G[v]->getClassTypeId() == innerTypeId && inCurrentBlock(cast<Statement>(G[v]), block)) {
    906                         bool safe = true;
    907                         for (PabloAST * user : G[v]->users()) {
    908                             if (user->getClassTypeId() != outerTypeId || !inCurrentBlock(cast<Statement>(user), block)) {
    909                                 safe = false;
    910                                 break;
     894    bool anyChanges = false;
     895
     896    for (;;) {
     897
     898        adjacency_list<hash_setS, vecS, bidirectionalS, Vertex> H;
     899        flat_map<Vertex, Vertex> M;
     900
     901        for (const Vertex u : make_iterator_range(vertices(G))) {
     902            const TypeId outerTypeId = G[u]->getClassTypeId();
     903            if (outerTypeId == TypeId::And || outerTypeId == TypeId::Or) {
     904                if (inCurrentBlock(cast<Statement>(G[u]), block)) {
     905                    const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And;
     906                    flat_set<Vertex> distributable;
     907                    for (auto e : make_iterator_range(in_edges(u, G))) {
     908                        const Vertex v = source(e, G);
     909                        if (LLVM_UNLIKELY(G[v]->getClassTypeId() == innerTypeId) && LLVM_LIKELY(inCurrentBlock(cast<Statement>(G[v]), block))) {
     910                            bool safe = true;
     911                            for (const auto e : make_iterator_range(out_edges(v, G))) {
     912                                if (G[target(e, G)]->getClassTypeId() != outerTypeId) {
     913                                    safe = false;
     914                                    break;
     915                                }
    911916                            }
    912                         }
    913                         if (safe) {
    914                             distributable.insert(v);
    915                         }
    916                     }
    917                 }
    918                 if (LLVM_LIKELY(distributable.size() > 1)) {
    919                     // We're only interested in computing a subgraph of G in which every source has an out-degree
    920                     // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
    921                     // benefit. (Note: this does not consider register pressure / liveness.)
    922                     flat_map<Vertex, unsigned> observed;
    923                     bool anyOpportunities = false;
    924                     for (const Vertex v : distributable) {
    925                         for (auto e : make_iterator_range(in_edges(v, G))) {
    926                             const Vertex w = source(e, G);
    927                             const auto f = observed.find(w);
    928                             if (f == observed.end()) {
    929                                 observed.emplace(w, 0);
    930                             } else {
    931                                 f->second += 1;
    932                                 anyOpportunities = true;
     917                            if (safe) {
     918                                distributable.insert(v);
    933919                            }
    934920                        }
    935921                    }
    936                     if (anyOpportunities) {                       
    937                         for (auto ob : observed) {
    938                             if (std::get<1>(ob)) {
    939                                 const Vertex w = std::get<0>(ob);
    940                                 for (auto e : make_iterator_range(out_edges(w, G))) {
    941                                     const Vertex v = target(e, G);
    942                                     if (distributable.count(v)) {
    943                                         const Vertex x = getVertex(u, H, M);
    944                                         const Vertex y = getVertex(v, H, M);
    945                                         const Vertex z = getVertex(w, H, M);
    946                                         add_edge(y, x, H);
    947                                         add_edge(z, y, H);
     922                    if (LLVM_LIKELY(distributable.size() > 1)) {
     923                        // We're only interested in computing a subgraph of G in which every source has an out-degree
     924                        // greater than 1. Otherwise we'd only end up permuting the AND/OR sequence with no logical
     925                        // benefit. (Note: this does not consider register pressure / liveness.)
     926                        flat_map<Vertex, unsigned> observed;
     927                        bool anyOpportunities = false;
     928                        for (const Vertex v : distributable) {
     929                            for (auto e : make_iterator_range(in_edges(v, G))) {
     930                                const Vertex w = source(e, G);
     931                                const auto f = observed.find(w);
     932                                if (f == observed.end()) {
     933                                    observed.emplace(w, 0);
     934                                } else {
     935                                    f->second += 1;
     936                                    anyOpportunities = true;
     937                                }
     938                            }
     939                        }
     940                        if (anyOpportunities) {
     941                            for (auto ob : observed) {
     942                                if (std::get<1>(ob)) {
     943                                    const Vertex w = std::get<0>(ob);
     944                                    for (auto e : make_iterator_range(out_edges(w, G))) {
     945                                        const Vertex v = target(e, G);
     946                                        if (distributable.count(v)) {
     947                                            const Vertex y = getVertex(v, H, M);
     948                                            add_edge(y, getVertex(u, H, M), H);
     949                                            add_edge(getVertex(w, H, M), y, H);
     950                                        }
    948951                                    }
    949952                                }
     
    954957            }
    955958        }
    956     }
    957 
    958     // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
    959     if (num_vertices(H) == 0) {
    960         return false;
    961     }
    962 
    963     // printGraph(block, H, G, "H0");
    964 
    965     // By finding the maximal set of bicliques in H=(A,B) ∪ T in which the verticies in bipartition B are
    966     // independent, we can identify a safe set of vertices to apply the distribution law to.
    967     VertexSets sourceSets(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(sourceSets.size() == 0)) {
    971         return false;
    972     }
    973 
    974     // printGraph(block, H, G, "H1");
    975 
    976     for (VertexSet & sources : sourceSets) {
    977         VertexSet intermediary;
    978         intermediary.reserve(out_degree(sources.front(), H));
    979         for (auto e : make_iterator_range(out_edges(sources.front(), H))) {
    980             const Vertex v = H[target(e, H)];
    981 
    982 
    983             intermediary.push_back(v);
    984         }
    985         VertexSet terminals;
    986         terminals.reserve(out_degree(intermediary.front(), H));
    987         for (auto e : make_iterator_range(out_edges(intermediary.front(), H))) {
    988             terminals.push_back(H[target(e, H)]);
    989         }
    990         const TypeId typeId = G[H[terminals.front()]]->getClassTypeId();
    991         assert (typeId == TypeId::And || typeId == TypeId::Or);
    992         circular_buffer<Vertex> Q(std::max(sources.size(), intermediary.size() + 1));
    993         for (const Vertex u : intermediary) {
    994             Q.push_back(G[H[u]]);
    995         }
    996         PabloAST * merged = createTree(block, typeId, Q);
    997         for (const Vertex u : sources) {
    998             Q.push_back(G[H[u]]);
    999         }
    1000         Q.push_back(merged);
    1001         PabloAST * masked = createTree(block, typeId == TypeId::Or ? TypeId::And : TypeId::Or, Q);
    1002 
    1003 
    1004 
    1005 
    1006 
    1007         circular_buffer<Vertex> I(out_degree(S.front(), H));
    1008         for (auto e : make_iterator_range(out_edges(S.front(), H))) {
    1009             I.push_back(H[target(e, H)]);
    1010         }
    1011 
    1012 
    1013 
    1014 
    1015 
    1016     }
    1017 
    1018 
    1019     return true;
    1020 }
    1021 
    1022 }
     959
     960        // If we found no potential opportunities then we cannot apply the distribution law to any part of G.
     961        if (num_vertices(H) == 0) {
     962            break;
     963        }
     964
     965        const VertexSets distributionSets = safeDistributionSets(segmentInto3LevelGraph(H));
     966
     967        // If no sources remain, no bicliques were found that would have a meaningful impact on the AST.
     968        if (LLVM_UNLIKELY(distributionSets.size() == 0)) {
     969            break;
     970        }
     971
     972        for (const VertexSet & sources : distributionSets) {
     973            assert (sources.size() > 0);
     974            const VertexSet intermediary = outgoingVertexSet(sources.front(), makeGraphFacade(H));
     975            assert (intermediary.size() > 0);
     976            const VertexSet sinks = outgoingVertexSet(intermediary.front(), makeGraphFacade(H));
     977            assert (sinks.size() > 0);
     978
     979            // Now begin transforming the AST
     980            const TypeId typeId = G[H[sinks.front()]]->getClassTypeId();
     981            assert (typeId == TypeId::And || typeId == TypeId::Or);
     982
     983            circular_buffer<PabloAST *> Q(std::max(sources.size(), intermediary.size() + 1));
     984            for (const Vertex u : intermediary) {
     985                Q.push_back(G[H[u]]);
     986            }
     987            PabloAST * merged = createTree(block, typeId, Q);
     988            for (const Vertex s : sources) {
     989                Q.push_back(G[H[s]]);
     990            }
     991            Q.push_back(merged);
     992            PabloAST * masked = createTree(block, typeId == TypeId::Or ? TypeId::And : TypeId::Or, Q);
     993
     994            // Eliminate the edges from our original graph
     995            for (const Vertex u : intermediary) {
     996                for (const Vertex s : sources) {
     997                    remove_edge(H[s], H[u], G);
     998                }
     999                for (const Vertex t : sinks) {
     1000                    remove_edge(H[u], H[t], G);
     1001                }
     1002            }
     1003
     1004            // Finally update G to match the desired changes
     1005            const Vertex x = add_vertex(merged, G);
     1006            const Vertex y = add_vertex(masked, G);
     1007            for (const Vertex u : intermediary) {
     1008                add_edge(H[u], x, G);
     1009            }
     1010            add_edge(x, y, G);
     1011            for (const Vertex s : sources) {
     1012                add_edge(H[s], y, G);
     1013            }
     1014            for (const Vertex t : sinks) {
     1015                add_edge(y, H[t], G);
     1016            }
     1017        }
     1018        anyChanges = true;
     1019    }
     1020
     1021    return anyChanges;
     1022}
     1023
     1024}
Note: See TracChangeset for help on using the changeset viewer.