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

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

Bug fixes

File size: 5.0 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    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 MultiplexVector = std::vector<MultiplexSetGraph::vertex_descriptor>;
32    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
33    using SubsetEdgeIterator = boost::graph_traits<SubsetGraph>::edge_iterator;
34    using CliqueGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS>;
35    using CliqueSet = boost::container::flat_set<CliqueGraph::vertex_descriptor>;
36    using CliqueSets = boost::container::flat_set<std::vector<CliqueGraph::vertex_descriptor>>;
37    using OrderingGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS, Statement *>;
38    using OrderingMap = boost::container::flat_map<const Statement *, OrderingGraph::vertex_descriptor>;
39
40    using AdvanceVector = std::vector<Advance *>;
41    using AdvanceDepth = std::vector<int>;
42    using AdvanceVariable = std::vector<BDD>;
43    using VertexVector = std::vector<ConstraintVertex>;
44
45public:
46
47    static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100, const unsigned windowSize = 1, const bool independent = false);
48    #ifdef PRINT_TIMING_INFORMATION
49    using seed_t = RNG::result_type;
50    static seed_t SEED;
51    static unsigned NODES_ALLOCATED;
52    static unsigned NODES_USED;
53    #endif
54protected:
55
56    unsigned initialize(PabloFunction & function, const bool independent);
57    void initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances);
58    void initializeAdvanceDepth(PabloBlock * const block, const unsigned advances) ;
59
60    void characterize(PabloBlock * const block);
61    BDD characterize(Statement * const stmt);
62    BDD characterize(Advance * const adv, const BDD Ik);
63    bool independent(const ConstraintVertex i, const ConstraintVertex j) const;
64    bool exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const;
65
66    void generateUsageWeightingGraph();
67    CliqueSets findMaximalCliques(const CliqueGraph & G);
68    void findMaximalCliques(const CliqueGraph & G, CliqueSet & R, CliqueSet && P, CliqueSet && X, CliqueSets & S);
69
70    bool generateCandidateSets();
71    void addCandidateSet(const VertexVector & S);
72    void selectMultiplexSets();
73
74    void eliminateSubsetConstraints();
75    void doTransitiveReductionOfSubsetGraph();
76
77    MultiplexVector orderMultiplexSet(const MultiplexSetGraph::vertex_descriptor u);
78    void multiplexSelectedSets(PabloFunction & function);
79
80    static void topologicalSort(PabloBlock * const block);
81    static void topologicalSort(const OrderingGraph::vertex_descriptor u, const PabloBlock * const block, const Statement * const stmt, OrderingGraph & G, OrderingMap & M);
82
83    BDD & get(const PabloAST * const expr);
84
85    inline MultiplexingPass(const RNG::result_type seed, const unsigned limit, const unsigned maxSelections, const unsigned windowSize)
86    : mMultiplexingSetSizeLimit(limit)
87    , mMaxMultiplexingSetSelections(maxSelections)
88    , mWindowSize(windowSize)
89    , mTestConstrainedAdvances(true)
90    , mSubsetImplicationsAdhereToWindowingSizeConstraint(false)
91    , mVariables(0)
92    , mRNG(seed)
93    , mConstraintGraph(0)
94    , mAdvance(0, nullptr)
95    , mAdvanceDepth(0, 0)
96    , mAdvanceNegatedVariable(0, 0)
97    {
98
99    }
100
101private:
102    const unsigned              mMultiplexingSetSizeLimit;
103    const unsigned              mMaxMultiplexingSetSelections;
104    const unsigned              mWindowSize;
105    const bool                  mTestConstrainedAdvances;
106    const bool                  mSubsetImplicationsAdhereToWindowingSizeConstraint;
107    unsigned                    mVariables;
108    RNG                         mRNG;
109    CharacterizationMap         mCharacterization;
110    ConstraintGraph             mConstraintGraph;   
111    AdvanceVector               mAdvance;
112    AdvanceDepth                mAdvanceDepth;
113    AdvanceVariable             mAdvanceNegatedVariable;
114    SubsetGraph                 mSubsetGraph;
115    CliqueGraph                 mUsageGraph;
116    MultiplexSetGraph           mMultiplexSetGraph;
117};
118
119}
120
121#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.