Ignore:
Timestamp:
Dec 9, 2015, 4:59:02 PM (3 years ago)
Author:
nmedfort
Message:

Continued work on multiplexing pass.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4888 r4890  
    44#include <pablo/codegenstate.h>
    55#include <slab_allocator.h>
    6 #include <queue>
    76#include <boost/graph/adjacency_list.hpp>
    87#include <boost/graph/adjacency_matrix.hpp>
     8#include <boost/container/flat_set.hpp>
    99#include <boost/container/flat_map.hpp>
    1010#include <boost/numeric/ublas/matrix.hpp>
     
    1919class PabloBuilder;
    2020class PabloFunction;
     21struct OrderingVerifier;
    2122
    2223class MultiplexingPass {
     
    2930    using MultiplexSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    3031    using SubsetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
     32    using SubsetEdgeIterator = boost::graph_traits<SubsetGraph>::edge_iterator;
     33    using CliqueGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS>;
     34    using CliqueSet = boost::container::flat_set<CliqueGraph::vertex_descriptor>;
     35    using CliqueSets = boost::container::flat_set<std::vector<CliqueGraph::vertex_descriptor>>;
     36
     37    using AdvanceVector = std::vector<Advance *>;
    3138    using AdvanceDepth = std::vector<int>;
    32     using AdvanceAttributes = std::vector<std::pair<Advance *, BDD>>; // the Advance pointer and its respective base BDD variable
     39    using AdvanceVariable = std::vector<BDD>;
    3340    using VertexVector = std::vector<ConstraintVertex>;
    34     using ScopeMap = boost::container::flat_map<const PabloBlock *, Statement *>;
    3541
    3642public:
    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);
     43
     44    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);
     45
    3846protected:
     47
    3948    unsigned initialize(PabloFunction & function, const bool independent);
    4049    void initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances);
     
    4655    bool independent(const ConstraintVertex i, const ConstraintVertex j) const;
    4756    bool exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const;
    48     bool generateCandidateSets(RNG & rng);
    4957
    50     void addCandidateSet(const VertexVector & S, RNG & rng);
    51     void selectMultiplexSets(RNG & rng);
     58    void generateUsageWeightingGraph();
     59    CliqueSets findMaximalCliques(const CliqueGraph & G);
     60    void findMaximalCliques(const CliqueGraph & G, CliqueSet & R, CliqueSet && P, CliqueSet && X, CliqueSets & S);
     61
     62    bool generateCandidateSets();
     63    void addCandidateSet(const VertexVector & S);
     64    void selectMultiplexSets();
     65
     66    void eliminateSubsetConstraints();
    5267    void doTransitiveReductionOfSubsetGraph();
    53     void eliminateSubsetConstraints();
     68
    5469    void multiplexSelectedIndependentSets(PabloFunction & function);
     70
    5571    static void topologicalSort(PabloFunction & function);
     72    static void topologicalSort(PabloBlock * block, OrderingVerifier & parent);
     73
    5674    BDD & get(const PabloAST * const expr);
    5775
    58     inline MultiplexingPass(const unsigned limit, const unsigned maxSelections, const unsigned windowSize)
     76    inline MultiplexingPass(const RNG::result_type seed, const unsigned limit, const unsigned maxSelections, const unsigned windowSize)
    5977    : mMultiplexingSetSizeLimit(limit)
    6078    , mMaxMultiplexingSetSelections(maxSelections)
     
    6280    , mTestConstrainedAdvances(true)
    6381    , mVariables(0)
     82    , mRNG(seed)
    6483    , mConstraintGraph(0)
     84    , mAdvance(0, nullptr)
    6585    , mAdvanceDepth(0, 0)
     86    , mAdvanceNegatedVariable(0, 0)
    6687    {
    6788
     
    7495    const bool                  mTestConstrainedAdvances;
    7596    unsigned                    mVariables;
     97    RNG                         mRNG;
    7698    CharacterizationMap         mCharacterization;
    77     ConstraintGraph             mConstraintGraph;
     99    ConstraintGraph             mConstraintGraph;   
     100    AdvanceVector               mAdvance;
    78101    AdvanceDepth                mAdvanceDepth;
     102    AdvanceVariable             mAdvanceNegatedVariable;
    79103    SubsetGraph                 mSubsetGraph;
    80     AdvanceAttributes           mAdvanceAttributes;
     104    CliqueGraph                 mUsageWeightingGraph;
    81105    MultiplexSetGraph           mMultiplexSetGraph;
    82     ScopeMap                    mResolvedScopes;
    83106};
    84107
Note: See TracChangeset for help on using the changeset viewer.