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

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

Minor changes to multiplexing code.

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