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

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

Work on adding Multiplexing Window Size.

File size: 3.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 <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
15typedef int BDD;
16
17namespace pablo {
18
19class PabloBuilder;
20class PabloFunction;
21
22class MultiplexingPass {
23
24    using CharacterizationMap = llvm::DenseMap<const PabloAST *, BDD>;
25    using ConstraintGraph = boost::adjacency_matrix<boost::directedS>;
26    using ConstraintVertex = ConstraintGraph::vertex_descriptor;
27    using RNG = std::mt19937;
28    using IntDistribution = std::uniform_int_distribution<RNG::result_type>;
29    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
30    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
31    using AdvanceDepth = std::vector<int>;
32    using AdvanceAttributes = std::vector<std::pair<Advance *, BDD>>; // the Advance pointer and its respective base BDD variable
33    using VertexVector = std::vector<ConstraintVertex>;
34    using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
35
36public:
37    static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100, const unsigned windowSize = 10, const bool independent = false);
38protected:
39    unsigned initialize(PabloFunction & function, const bool independent);
40    void initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances);
41    void initializeAdvanceDepth(PabloBlock * const block, const unsigned advances) ;
42
43    void characterize(PabloBlock * const block);
44    BDD characterize(Statement * const stmt);
45    BDD characterize(Advance * const adv, const BDD Ik);
46    bool independent(const ConstraintVertex i, const ConstraintVertex j) const;
47    bool exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const;
48    bool generateCandidateSets(RNG & rng);
49
50    void addCandidateSet(const VertexVector & S, RNG & rng);
51    void selectMultiplexSets(RNG & rng);
52    void doTransitiveReductionOfSubsetGraph();
53    void eliminateSubsetConstraints();
54    void multiplexSelectedIndependentSets(PabloFunction & function);
55    static void topologicalSort(PabloFunction & function);
56    BDD & get(const PabloAST * const expr);
57
58    inline MultiplexingPass(const unsigned limit, const unsigned maxSelections, const unsigned windowSize)
59    : mMultiplexingSetSizeLimit(limit)
60    , mMaxMultiplexingSetSelections(maxSelections)
61    , mWindowSize(windowSize)
62    , mTestConstrainedAdvances(true)
63    , mVariables(0)
64    , mConstraintGraph(0)
65    , mAdvanceDepth(0, 0)
66    {
67
68    }
69
70private:
71    const unsigned              mMultiplexingSetSizeLimit;
72    const unsigned              mMaxMultiplexingSetSelections;
73    const unsigned              mWindowSize;
74    const bool                  mTestConstrainedAdvances;
75    unsigned                    mVariables;
76    CharacterizationMap         mCharacterization;
77    ConstraintGraph             mConstraintGraph;
78    AdvanceDepth                mAdvanceDepth;
79    SubsetGraph                 mSubsetGraph;
80    AdvanceAttributes           mAdvanceAttributes;
81    MultiplexSetGraph           mMultiplexSetGraph;
82    ScopeMap                    mResolvedScopes;
83};
84
85}
86
87#endif // PABLO_AUTOMULTIPLEXING_HPP
Note: See TracBrowser for help on using the repository browser.