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

Last change on this file since 4959 was 4959, checked in by nmedfort, 3 years ago

Initial modifications to Pablo Compiler and Kernel Builder to support circular buffers for Lookahead.

File size: 4.5 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 <boost/graph/adjacency_list.hpp>
7#include <boost/graph/adjacency_matrix.hpp>
8#include <boost/container/flat_set.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#include <llvm/ADT/DenseSet.h>
15
16typedef int BDD;
17
18namespace pablo {
19
20class PabloBuilder;
21class PabloFunction;
22
23class MultiplexingPass {
24
25    using CharacterizationMap = llvm::DenseMap<const PabloAST *, BDD>;
26
27    using ConstraintGraph = boost::adjacency_matrix<boost::directedS, boost::no_property, bool>;
28    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
29    using Constraints = std::vector<ConstraintVertex>;
30
31    using RNG = std::mt19937;
32    using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
33
34    using CandidateGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS>;
35    using Candidates = std::vector<CandidateGraph::vertex_descriptor>;
36
37    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
38
39    using CliqueGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS>;
40    using CliqueSet = boost::container::flat_set<CliqueGraph::vertex_descriptor>;
41    using CliqueSets = boost::container::flat_set<std::vector<CliqueGraph::vertex_descriptor>>;
42
43    using AdvanceVector = std::vector<Advance *>;
44    using AdvanceRank = std::vector<int>;
45    using AdvanceVariable = std::vector<BDD>;
46
47public:
48
49    static bool optimize(PabloFunction & function, const bool independent = false);
50    #ifdef PRINT_TIMING_INFORMATION
51    using seed_t = RNG::result_type;
52    static seed_t SEED;
53    static unsigned NODES_ALLOCATED;
54    static unsigned NODES_USED;
55    #endif
56protected:
57
58    unsigned initialize(PabloFunction & function, const bool independent);
59    void initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances);
60    void initializeAdvanceDepth(PabloBlock * const block, const unsigned advances) ;
61
62    void characterize(PabloBlock * const block);
63    BDD characterize(Statement * const stmt);
64    BDD characterize(Advance * const adv, const BDD Ik);
65    bool independent(const ConstraintVertex i, const ConstraintVertex j) const;
66    bool exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const;
67
68    void generateUsageWeightingGraph();
69    CliqueSets findMaximalCliques(const CliqueGraph & G);
70    void findMaximalCliques(const CliqueGraph & G, CliqueSet & R, CliqueSet && P, CliqueSet && X, CliqueSets & S);
71
72    bool generateCandidateSets();
73    void addCandidateSet(const Constraints & S);
74    void updateCandidateSet(ConstraintVertex * const begin, ConstraintVertex * const end);
75    void selectCandidateSet(const unsigned n, const unsigned k, const unsigned m, const Constraints & S, ConstraintVertex * const element);
76
77    void selectMultiplexSetsGreedy();
78    void selectMultiplexSetsWorkingSet();
79
80    void removePotentialCycles(const CandidateGraph::vertex_descriptor u);
81    bool dependent(const ConstraintVertex i, const ConstraintVertex j) const;
82
83    void eliminateSubsetConstraints();
84    void doTransitiveReductionOfSubsetGraph();
85
86    Candidates orderMultiplexSet(const CandidateGraph::vertex_descriptor u);
87    void multiplexSelectedSets(PabloFunction & function);
88
89    static void rewriteAST(PabloBlock * const block);
90
91    BDD & get(const PabloAST * const expr);
92
93    inline MultiplexingPass(const RNG::result_type seed)
94    : mTestConstrainedAdvances(true)
95    , mSubsetImplicationsAdhereToWindowingSizeConstraint(false)
96    , mVariables(0)
97    , mRNG(seed)
98    , mConstraintGraph(0)
99    , mAdvance(0, nullptr)
100    , mAdvanceRank(0, 0)
101    , mAdvanceNegatedVariable(0, 0)
102    {
103
104    }
105
106private:
107    const bool                  mTestConstrainedAdvances;
108    const bool                  mSubsetImplicationsAdhereToWindowingSizeConstraint;
109    unsigned                    mVariables;
110    RNG                         mRNG;
111    CharacterizationMap         mCharacterization;
112    ConstraintGraph             mConstraintGraph;   
113    AdvanceVector               mAdvance;
114    AdvanceRank                 mAdvanceRank;
115    AdvanceVariable             mAdvanceNegatedVariable;
116    SubsetGraph                 mSubsetGraph;
117    CliqueGraph                 mUsageGraph;
118    CandidateGraph              mCandidateGraph;
119};
120
121}
122
123#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.