source: icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp @ 4583

Last change on this file since 4583 was 4583, checked in by nmedfort, 4 years ago

More multiplexing work. Can only be enabled by adding -DENABLE_MULTIPLEXING=yes to the cmake command. Not quite functional yet but close.

File size: 3.0 KB
Line 
1#ifndef PABLO_AUTOMULTIPLEXING_HPP
2#define PABLO_AUTOMULTIPLEXING_HPP
3
4#include <pablo/codegenstate.h>
5#include <slab_allocator.h>
6#include <queue>
7#include <boost/graph/adjacency_list.hpp>
8#include <boost/graph/adjacency_matrix.hpp>
9#include <boost/graph/edge_list.hpp>
10#include <boost/container/flat_map.hpp>
11#include <boost/numeric/ublas/matrix.hpp>
12#include <random>
13#include <stdint.h>
14
15struct DdManager; // forward declare of the CUDD manager
16struct DdNode;
17
18namespace pablo {
19
20class AutoMultiplexing {
21
22    using CharacterizationMap = boost::container::flat_map<const PabloAST *, DdNode *>;
23    using ConstraintGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
24    using PathGraph = boost::adjacency_matrix<boost::undirectedS>;
25    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
26    using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS, unsigned>;
27    using SubsetGraph = std::vector<std::pair<MultiplexSetGraph::vertex_descriptor, MultiplexSetGraph::vertex_descriptor>>;
28    using Advances = std::vector<Advance *>;
29    using TopologicalSortGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
30    using TopologicalSortQueue = std::queue<TopologicalSortGraph::vertex_descriptor>;
31    using TopologicalSortMap = boost::container::flat_map<PabloAST *, TopologicalSortGraph::vertex_descriptor>;
32
33    using RNG = std::mt19937;
34    using RNGDistribution = std::uniform_int_distribution<RNG::result_type>;
35
36    using Vertex = ConstraintGraph::vertex_descriptor;
37
38    using IndependentSet = std::vector<Vertex>;
39
40public:
41    static void optimize(const std::vector<Var *> & input, PabloBlock & entry);
42protected:
43    void initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
44    void characterize(PabloBlock & entry);   
45    void createMultiplexSetGraph();
46    bool generateMultiplexSets(RNG & rng);   
47    void addMultiplexSet(const IndependentSet & set);
48    void approxMaxWeightIndependentSet(RNG & rng);
49    void applySubsetConstraints();
50    void multiplexSelectedIndependentSets();
51    void topologicalSort(PabloBlock & entry) const;
52    void topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q, TopologicalSortMap & M, Statement * ip, Statement * first) const;
53    inline AutoMultiplexing()
54    : mPathGraph(0) {
55    }
56private:
57    bool isZero(DdNode * x) const;
58    DdNode * And(DdNode * x, DdNode * y);
59    DdNode * Or(DdNode * x, DdNode * y);
60    DdNode * Xor(DdNode * x, DdNode * y);
61    DdNode * Not(DdNode * x);
62    DdNode * Ite(DdNode * x, DdNode * y, DdNode * z);
63    bool noSatisfyingAssignment(DdNode * x);
64    void shutdown();
65private:
66    DdManager *             mManager;
67    CharacterizationMap     mCharacterizationMap;
68    PathGraph               mPathGraph;
69    ConstraintGraph         mConstraintGraph;
70    SubsetGraph             mSubsetGraph;
71    Advances                mAdvance;
72    MultiplexSetGraph       mMultiplexSetGraph;
73};
74
75}
76
77#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.