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

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

Added ability to limit the size of candidate multiplexing sets and choose a sample of the possible combinations.

File size: 4.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/container/flat_map.hpp>
10#include <boost/numeric/ublas/matrix.hpp>
11#include <random>
12#include <stdint.h>
13#include <llvm/ADT/DenseMap.h>
14
15struct DdManager; // forward declare of the CUDD manager
16struct DdNode;
17
18namespace pablo {
19
20class PabloBuilder;
21class PabloFunction;
22
23class AutoMultiplexing {
24
25    using CharacterizationMap = llvm::DenseMap<const PabloAST *, DdNode *>;
26    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
27    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
28    using RNG = std::mt19937;
29    using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
30    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
31    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
32    // the Advance pointer, input BDD and the BDD variable of the i-th Advance
33    using AdvanceMap = boost::container::flat_map<const Statement *, unsigned>;
34    using AdvanceVector = std::vector<std::tuple<Advance *, DdNode *, DdNode *>>;
35    using VertexVector = std::vector<ConstraintVertex>;
36    using RecentCharacterizations = std::vector<std::pair<const PabloAST *, DdNode *>>;
37    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
38    using TopologicalGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
39    using TopologicalVertex = TopologicalGraph::vertex_descriptor;
40    using TopologicalMap = boost::container::flat_map<const Statement *, TopologicalVertex>;
41public:
42    static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100);
43protected:
44    bool initialize(PabloFunction & function);
45    void characterize(PabloBlock & block);
46    DdNode * characterize(Statement * const stmt);
47    DdNode * characterize(Advance * adv, DdNode * input);
48    bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
49    bool generateCandidateSets(RNG & rng);
50    void addCandidateSet(const VertexVector & S, RNG & rng);
51    void selectMultiplexSets(RNG &);
52    void applySubsetConstraints();
53    void multiplexSelectedIndependentSets(PabloFunction & function);
54    void topologicalSort(PabloFunction & function, PabloBlock & block) const;
55    void resolveUsages(const TopologicalVertex u, Statement * expr, PabloBlock & block, TopologicalGraph & G, TopologicalMap & M, Statement * ignoreIfThis) const;
56    static TopologicalVertex getVertex(Statement * expr, TopologicalGraph & G, TopologicalMap & M);
57
58    inline AutoMultiplexing(const unsigned limit, const unsigned maxSelections)
59    : mLimit(limit)
60    , mMaxSelections(maxSelections)
61    , mVariables(0)
62    , mConstraintGraph(0)
63    {
64    }
65
66private:
67
68    DdNode * Zero() const;
69    DdNode * One() const;
70    bool isZero(DdNode * const x) const;
71    DdNode * And(DdNode * const x, DdNode * const y);
72    DdNode * Or(DdNode * const x, DdNode * const y);
73    DdNode * Xor(DdNode * const x, DdNode * const y);
74    DdNode * Not(DdNode * x) const;
75    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
76    DdNode * NewVar();
77    void Ref(DdNode * const x);
78    void Deref(DdNode * const x);
79    bool NoSatisfyingAssignment(DdNode * const x);
80    void Shutdown();
81
82private:
83    DdManager *                 mManager;
84    const unsigned              mLimit;
85    const unsigned              mMaxSelections;
86    unsigned                    mVariables;
87    CharacterizationMap         mCharacterizationMap;
88    ConstraintGraph             mConstraintGraph;
89    SubsetGraph                 mSubsetGraph;
90    AdvanceMap                  mAdvanceMap;
91    AdvanceVector               mAdvance;
92    MultiplexSetGraph           mMultiplexSetGraph;
93    RecentCharacterizations     mRecentCharacterizations;
94    ScopeMap                    mResolvedScopes;
95};
96
97}
98
99#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.