Ignore:
Timestamp:
Jul 27, 2015, 4:54:56 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check in

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

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

    r4699 r4702  
    77#include <boost/numeric/ublas/matrix.hpp>
    88#include <boost/circular_buffer.hpp>
     9#include <boost/graph/topological_sort.hpp>
    910#include <boost/range/iterator_range.hpp>
    1011#include <llvm/ADT/BitVector.h>
     
    147148
    148149        RECORD_TIMESTAMP(start_select_independent_sets);
    149         am.multiplexSelectedIndependentSets();
     150        auto multiplexedSets = am.multiplexSelectedIndependentSets();
    150151        RECORD_TIMESTAMP(end_select_independent_sets);
    151152        LOG("MultiplexSelectedSets:   " << (end_select_independent_sets - start_select_independent_sets));
     
    155156        RECORD_TIMESTAMP(end_topological_sort);
    156157        LOG("TopologicalSort:         " << (end_topological_sort - start_topological_sort));
     158
     159        llvm::raw_os_ostream out(std::cerr);
     160        PabloPrinter::print(function.getEntryBlock(), out);
     161        out.flush();
     162
     163        RECORD_TIMESTAMP(start_reduce);
     164        am.reduce(multiplexedSets);
     165        RECORD_TIMESTAMP(end_reduce);
     166        LOG("Reduce:                  " << (end_reduce - start_reduce));
    157167    }
    158168
     
    164174    LOG_NUMBER_OF_ADVANCES(function.getEntryBlock());
    165175
    166     BDDMinimizationPass::optimize(function);
     176    // BDDMinimizationPass::optimize(function);
    167177
    168178    return multiplex;
     
    963973 * @brief multiplexSelectedIndependentSets
    964974 ** ------------------------------------------------------------------------------------------------------------- */
    965 void AutoMultiplexing::multiplexSelectedIndependentSets() const {
     975std::vector<std::vector<PabloAST *>> AutoMultiplexing::multiplexSelectedIndependentSets() const {
    966976
    967977    const unsigned f = num_vertices(mConstraintGraph);
     
    973983        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
    974984    }
    975     const size_t max_m = log2_plus_one(max_n);
    976985
    977986    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
    978987    std::vector<Advance *> input(max_n);
    979     std::vector<PabloAST *> muxed(max_m);
     988    std::vector<std::vector<PabloAST *>> outputs;
    980989    circular_buffer<PabloAST *> Q(max_n);
    981990
     
    988997
    989998            const size_t m = log2_plus_one(n);
     999
     1000            std::vector<PabloAST *> muxed(m);
    9901001
    9911002            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
     
    10271038            }
    10281039
    1029             /// Perform m-to-n Demultiplexing
    1030             // Now construct the demuxed values and replaces all the users of the original advances with them.
     1040            /// Perform m-to-n Demultiplexing           
    10311041            for (size_t i = 1; i <= n; ++i) {
    10321042
     1043                // Construct the demuxed values and replaces all the users of the original advances with them.
    10331044                for (size_t j = 0; j != m; ++j) {
    10341045                    if ((i & (static_cast<size_t>(1) << j)) == 0) {
     
    10661077                input[i - 1]->replaceWith(demuxed, true, true);
    10671078            }
    1068         }
    1069     }
     1079            outputs.push_back(std::move(muxed));
     1080        }
     1081    }
     1082    return outputs;
     1083}
     1084
     1085/** ------------------------------------------------------------------------------------------------------------- *
     1086 * @brief reduce
     1087 ** ------------------------------------------------------------------------------------------------------------- */
     1088inline bool isBinaryOp(const PabloAST * const expr) {
     1089    switch (expr->getClassTypeId()) {
     1090        case PabloAST::ClassTypeId::And:
     1091        case PabloAST::ClassTypeId::Or:
     1092        case PabloAST::ClassTypeId::Not:
     1093        case PabloAST::ClassTypeId::Xor:
     1094        case PabloAST::ClassTypeId::Sel:
     1095            return true;
     1096        default:
     1097            return false;
     1098    }
     1099}
     1100
     1101
     1102void AutoMultiplexing::reduce(const std::vector<std::vector<PabloAST *>> & sets) const {
     1103
     1104    for (const auto & set : sets) {
     1105
     1106        // first do a BFS to build a topological ordering of statements we're going to end up visiting
     1107        // and determine which of those will be terminals in the BDD
     1108        using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;
     1109        using Vertex = Graph::vertex_descriptor;
     1110
     1111        Graph G;
     1112        std::unordered_map<PabloAST *, unsigned> M;
     1113
     1114        std::queue<Statement *> Q;
     1115
     1116        llvm::raw_os_ostream out(std::cerr);
     1117
     1118        for (PabloAST * inst : set) {
     1119            if (LLVM_LIKELY(isa<Advance>(inst))) {
     1120                const auto u = add_vertex(inst, G);
     1121                M.insert(std::make_pair(inst, u));
     1122
     1123                for (PabloAST * user : inst->users()) {
     1124                    auto f = M.find(user);
     1125                    Vertex v = 0;
     1126                    if (f == M.end()) {
     1127                        v = add_vertex(user, G);
     1128                        M.insert(std::make_pair(user, v));
     1129                        if (isBinaryOp(user)) {
     1130                            Q.push(cast<Statement>(user));
     1131                        }
     1132                    } else { // if (f != M.end()) {
     1133                        v = f->second;
     1134                    }
     1135                    add_edge(u, v, G);
     1136                }
     1137
     1138            }
     1139        }
     1140
     1141        while (!Q.empty()) {
     1142            Statement * const var = Q.front(); Q.pop();
     1143            const Vertex u = M[var];
     1144
     1145            for (unsigned i = 0; i != var->getNumOperands(); ++i) {
     1146                PabloAST * operand = var->getOperand(i);
     1147                auto f = M.find(operand);
     1148                Vertex v;
     1149                if (LLVM_UNLIKELY(f == M.end())) {
     1150                    v = add_vertex(operand, G);
     1151                    M.insert(std::make_pair(operand, v));
     1152                } else { // if (f != M.end()) {
     1153                    v = f->second;
     1154                }
     1155                add_edge(v, u, G);
     1156            }
     1157
     1158            for (PabloAST * user : var->users()) {
     1159                auto f = M.find(user);
     1160                Vertex v = 0;
     1161                if (LLVM_LIKELY(f == M.end())) {
     1162                    v = add_vertex(user, G);
     1163                    M.insert(std::make_pair(user, v));
     1164                    if (isBinaryOp(user)) {
     1165                        Q.push(cast<Statement>(user));
     1166                    }
     1167                } else { // if (f != M.end()) {
     1168                    v = f->second;
     1169                }
     1170                add_edge(u, v, G);
     1171            }
     1172        }
     1173
     1174        out << "\ndigraph G {\n";
     1175        for (auto u : make_iterator_range(vertices(G))) {
     1176            out << "  v" << u;
     1177            PabloPrinter::print(cast<Statement>(G[u]), " [label=\"", out);
     1178            out << "\"];\n";
     1179        }
     1180        for (auto e : make_iterator_range(edges(G))) {
     1181            out << "  v" << source(e, G) << " -> v" << target(e, G) << ";\n";
     1182        }
     1183        out << "}\n\n";
     1184        out.flush();
     1185
     1186        // count the number of sinks (sources) so we know how many variables (terminals) will exist in the BDD
     1187        std::vector<Vertex> variable;
     1188        flat_set<Vertex> terminal;
     1189        for (auto u : make_iterator_range(vertices(G))) {
     1190            if (in_degree(u, G) == 0) {
     1191                variable.push_back(u);
     1192            }
     1193            if (out_degree(u, G) == 0) {
     1194                // the inputs to the sinks become the terminals in the BDD
     1195                for (auto e : make_iterator_range(in_edges(u, G))) {
     1196                    terminal.insert(target(e, G));
     1197                }
     1198            }
     1199        }
     1200
     1201        DdManager * manager = Cudd_Init(variable.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     1202        Cudd_AutodynEnable(manager, CUDD_REORDER_LAZY_SIFT);
     1203
     1204        std::vector<DdNode *> characterization(num_vertices(G), nullptr);
     1205        unsigned i = 0;
     1206        for (auto u : variable) {
     1207            characterization[u] = Cudd_bddIthVar(manager, i++);
     1208        }
     1209
     1210        std::vector<Vertex> ordering;
     1211        ordering.reserve(num_vertices(G));
     1212        topological_sort(G, std::back_inserter(ordering));
     1213
     1214        for (auto ui = ordering.rbegin(); ui != ordering.rend(); ++ui) {
     1215
     1216            const Vertex u = *ui;
     1217
     1218            Statement * stmt = cast<Statement>(G[u]);
     1219
     1220            out << u; PabloPrinter::print(stmt, " : ", out); out << " = " << (long)characterization[u] << '\n';
     1221            out.flush();
     1222
     1223            if (characterization[u]) {
     1224                continue;
     1225            }
     1226
     1227            std::array<DdNode *, 3> input;
     1228
     1229            unsigned i = 0;
     1230            for (const auto e : make_iterator_range(in_edges(u, G))) {
     1231                input[i++] = characterization[source(e, G)];
     1232
     1233            }
     1234
     1235            assert (is<Statement>(G[u]) ? i == cast<Statement>(G[u])->getNumOperands() : i == 0);
     1236
     1237            DdNode * bdd = nullptr;
     1238
     1239            switch (G[u]->getClassTypeId()) {
     1240                case PabloAST::ClassTypeId::And:
     1241                    bdd = Cudd_bddAnd(manager, input[0], input[1]);
     1242                    break;
     1243                case PabloAST::ClassTypeId::Or:
     1244                    bdd = Cudd_bddOr(manager, input[0], input[1]);
     1245                    break;
     1246                case PabloAST::ClassTypeId::Not:
     1247                    bdd = Cudd_Not(input[0]);
     1248                    break;
     1249                case PabloAST::ClassTypeId::Xor:
     1250                    bdd = Cudd_bddXor(manager, input[0], input[1]);
     1251                    break;
     1252                case PabloAST::ClassTypeId::Sel:
     1253                    bdd = Cudd_bddIte(manager, input[0], input[1], input[2]);
     1254                    break;
     1255                default: break;
     1256            }
     1257
     1258            characterization[u] = bdd;
     1259        }
     1260
     1261        Cudd_ReduceHeap(manager, CUDD_REORDER_SIFT, 0);
     1262
     1263        for (auto t : terminal) {
     1264
     1265            llvm::raw_os_ostream out(std::cerr);
     1266            out << " REDUNCTION : "; PabloPrinter::print(G[t], out); out << '\n';
     1267            out.flush();
     1268
     1269            DdNode * bdd = characterization[t];
     1270            Cudd_bddPrintCover(manager, bdd, bdd);
     1271
     1272            out << '\n'; out.flush();
     1273        }
     1274
     1275        Cudd_Quit(manager);
     1276    }
     1277
    10701278}
    10711279
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4665 r4702  
    3535    using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
    3636    using VertexVector = std::vector<ConstraintVertex>;
    37     using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
    38 
     37    using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;   
    3938public:
    4039    static bool optimize(PabloFunction & function);
     
    4948    void selectMultiplexSets(RNG &);
    5049    void applySubsetConstraints();
    51     void multiplexSelectedIndependentSets() const;
     50    std::vector<std::vector<PabloAST *>> multiplexSelectedIndependentSets() const;
     51    void reduce(const std::vector<std::vector<PabloAST *>> & sets) const;
    5252    void topologicalSort(PabloBlock & entry) const;
    5353    inline AutoMultiplexing()
Note: See TracChangeset for help on using the changeset viewer.