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

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

Added the ability to compute all unique combinations of potential multiplexing sets.

File size: 3.2 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::listS, boost::undirectedS, std::tuple<int, int, MultiplexSetGraph::vertex_descriptor>>;
27    using ChosenSet = std::vector<MultiplexSetGraph::vertex_descriptor>;
28    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
29    using Advances = std::vector<Advance *>;
30
31    using RNG = std::mt19937;
32    using RNGDistribution = std::uniform_int_distribution<RNG::result_type>;
33
34    using Vertex = ConstraintGraph::vertex_descriptor;
35
36    using IndependentSet = std::vector<Vertex>;
37
38public:
39    static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
40protected:
41    void initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
42    void characterize(PabloBlock & entry);
43    bool notTransitivelyDependant(const PathGraph::vertex_descriptor i, const PathGraph::vertex_descriptor j) const;
44    void createMultiplexSetGraph();
45    bool generateMultiplexSets(RNG & rng);   
46    void addMultiplexSet(const IndependentSet & N, const IndependentSet & S);
47    void addMultiplexSet(const IndependentSet & N, const int i, const IndependentSet & S, const int j);
48    void approxMaxWeightIndependentSet(RNG & rng);
49    void applySubsetConstraints();
50    void multiplexSelectedIndependentSets() const;
51    void topologicalSort(PabloBlock & entry) const;
52    inline AutoMultiplexing()
53    : mPathGraph(0) {
54    }
55private:
56    DdNode * Zero() const;
57    DdNode * One() const;
58    bool isZero(DdNode * const x) const;
59    DdNode * And(DdNode * const x, DdNode * const y);
60    DdNode * Intersect(DdNode * const x, DdNode * const y);
61    DdNode * Or(DdNode * const x, DdNode * const y);
62    DdNode * Xor(DdNode * const x, DdNode * const y);
63    DdNode * Not(DdNode * x) const;
64    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
65    bool noSatisfyingAssignment(DdNode * const x);
66    void shutdown();
67private:
68    DdManager *             mManager;
69    CharacterizationMap     mCharacterizationMap;
70    PathGraph               mPathGraph;
71    ConstraintGraph         mConstraintGraph;
72    SubsetGraph             mSubsetGraph;
73    Advances                mAdvance;   
74    MultiplexSetGraph       mMultiplexSetGraph;
75    ChosenSet               mCurrentCombination;
76};
77
78}
79
80#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.