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

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

More multiplexing work. Reduced MWIS approximation cost.

File size: 3.1 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/container/flat_set.hpp>
12#include <boost/numeric/ublas/matrix.hpp>
13#include <random>
14#include <stdint.h>
15
16struct DdManager; // forward declare of the CUDD manager
17struct DdNode;
18
19namespace pablo {
20
21class AutoMultiplexing {
22
23    using CharacterizationMap = boost::container::flat_map<const PabloAST *, DdNode *>;
24    using ConstraintGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
25    using PathGraph = boost::adjacency_matrix<boost::undirectedS>;
26    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
27    using IndependentSetGraph = boost::adjacency_matrix<boost::undirectedS, std::pair<int, int>>;
28    using ChosenSet = boost::container::flat_set<MultiplexSetGraph::vertex_descriptor>;
29    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
30    using Advances = std::vector<Advance *>;
31
32    using RNG = std::mt19937;
33    using RNGDistribution = std::uniform_int_distribution<RNG::result_type>;
34
35    using Vertex = ConstraintGraph::vertex_descriptor;
36
37    using IndependentSet = std::vector<Vertex>;
38
39public:
40    static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
41protected:
42    void initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
43    void characterize(PabloBlock & entry);
44    bool notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const;
45    void createMultiplexSetGraph();
46    bool generateMultiplexSets(RNG & rng);   
47    void addMultiplexSet(const IndependentSet & N, const IndependentSet & M);
48    void addMultiplexSet(const IndependentSet & N, int i, const IndependentSet & M, int j, ChosenSet & S);
49    void approxMaxWeightIndependentSet(RNG & rng);
50    void applySubsetConstraints();
51    void multiplexSelectedIndependentSets() const;
52    void topologicalSort(PabloBlock & entry) const;
53    inline AutoMultiplexing()
54    : mPathGraph(0)
55    {
56    }
57private:
58    DdNode * Zero() const;
59    DdNode * One() const;
60    bool isZero(DdNode * const x) const;
61    DdNode * And(DdNode * const x, DdNode * const y);
62    DdNode * Intersect(DdNode * const x, DdNode * const y);
63    DdNode * Or(DdNode * const x, DdNode * const y);
64    DdNode * Xor(DdNode * const x, DdNode * const y);
65    DdNode * Not(DdNode * x) const;
66    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
67    bool noSatisfyingAssignment(DdNode * const x);
68    void shutdown();
69private:
70    DdManager *             mManager;
71    CharacterizationMap     mCharacterizationMap;
72    PathGraph               mPathGraph;
73    ConstraintGraph         mConstraintGraph;
74    SubsetGraph             mSubsetGraph;
75    Advances                mAdvance;   
76    MultiplexSetGraph       mMultiplexSetGraph;
77};
78
79}
80
81#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.