Changeset 4822


Ignore:
Timestamp:
Oct 5, 2015, 11:49:45 AM (2 years ago)
Author:
nmedfort
Message:

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

Location:
icGREP/icgrep-devel/icgrep
Files:
3 edited

Legend:

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

    r4809 r4822  
    106106using TypeId = PabloAST::ClassTypeId;
    107107
    108 bool AutoMultiplexing::optimize(PabloFunction & function) {
     108bool AutoMultiplexing::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections) {
    109109
    110110//    std::random_device rd;
     
    115115    LOG("Seed:                    " << seed);
    116116
    117     AutoMultiplexing am;
     117    AutoMultiplexing am(limit, maxSelections);
    118118    RECORD_TIMESTAMP(start_initialize);
    119119    const bool abort = am.initialize(function);
     
    650650    do {
    651651
    652         addCandidateSet(S);
     652        addCandidateSet(S, rng);
    653653
    654654        bool noNewElements = true;
     
    678678
    679679/** ------------------------------------------------------------------------------------------------------------- *
     680 * @brief choose
     681 ** ------------------------------------------------------------------------------------------------------------- */
     682inline unsigned long choose(const unsigned n, const unsigned k) {
     683    if (n < k)
     684        return 0;
     685    if (n == k || k == 0)
     686        return 1;
     687    unsigned long delta = k;
     688    unsigned long max = n - k;
     689    if (delta < max) {
     690        std::swap(delta, max);
     691    }
     692    unsigned long result = delta + 1;
     693    for (unsigned i = 2; i <= max; ++i) {
     694        result = (result * (delta + i)) / i;
     695    }
     696    return result;
     697}
     698
     699/** ------------------------------------------------------------------------------------------------------------- *
     700 * @brief select
     701 *
     702 * James McCaffrey's algorithm for "Generating the mth Lexicographical Element of a Mathematical Combination"
     703 ** ------------------------------------------------------------------------------------------------------------- */
     704void select(const unsigned n, const unsigned k, const unsigned m, unsigned * element) {
     705    unsigned long a = n;
     706    unsigned long b = k;
     707    unsigned long x = (choose(n, k) - 1) - m;
     708    for (unsigned i = 0; i != k; ++i) {
     709        while (choose(--a, b) > x);
     710        x = x - choose(a, b);
     711        b = b - 1;
     712        element[i] = (n - 1) - a;
     713    }
     714}
     715
     716/** ------------------------------------------------------------------------------------------------------------- *
    680717 * @brief addCandidateSet
    681718 * @param S an independent set
    682  * @param T the trie in which to encode this new set into
    683  * @param roots the roots (source nodes) for each tree in T
    684  ** ------------------------------------------------------------------------------------------------------------- */
    685 inline void AutoMultiplexing::addCandidateSet(const VertexVector & S) {
     719 ** ------------------------------------------------------------------------------------------------------------- */
     720inline void AutoMultiplexing::addCandidateSet(const VertexVector & S, RNG & rng) {
    686721    if (S.size() >= 3) {
    687         const auto u = add_vertex(mMultiplexSetGraph);
    688         for (const auto v : S) {
    689             add_edge(u, v, mMultiplexSetGraph);
     722        if (S.size() <= mLimit) {
     723            const auto u = add_vertex(mMultiplexSetGraph);
     724            for (const auto v : S) {
     725                add_edge(u, v, mMultiplexSetGraph);
     726            }
     727        } else {
     728            const auto max = choose(S.size(), mLimit);
     729            unsigned element[mLimit];
     730            if (LLVM_UNLIKELY(max <= mMaxSelections)) {
     731                for (unsigned i = 0; i != max; ++i) {
     732                    select(S.size(), mLimit, i, element);
     733                    const auto u = add_vertex(mMultiplexSetGraph);
     734                    for (unsigned j = 0; j != mLimit; ++j) {
     735                        add_edge(u, S[element[j]], mMultiplexSetGraph);
     736                    }
     737                }
     738            } else { // take m random samples
     739                for (unsigned i = 0; i != mMaxSelections; ++i) {
     740                    select(S.size(), mLimit, rng() % max, element);
     741                    const auto u = add_vertex(mMultiplexSetGraph);
     742                    for (unsigned j = 0; j != mLimit; ++j) {
     743                        add_edge(u, S[element[j]], mMultiplexSetGraph);
     744                    }
     745                }
     746            }
    690747        }
    691748    }
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4775 r4822  
    4040    using TopologicalMap = boost::container::flat_map<const Statement *, TopologicalVertex>;
    4141public:
    42     static bool optimize(PabloFunction & function);
     42    static bool optimize(PabloFunction & function, const unsigned limit = std::numeric_limits<unsigned>::max(), const unsigned maxSelections = 100);
    4343protected:
    4444    bool initialize(PabloFunction & function);
     
    4848    bool notTransitivelyDependant(const ConstraintVertex i, const ConstraintVertex j) const;
    4949    bool generateCandidateSets(RNG & rng);
    50     void addCandidateSet(const VertexVector & S);
     50    void addCandidateSet(const VertexVector & S, RNG & rng);
    5151    void selectMultiplexSets(RNG &);
    5252    void applySubsetConstraints();
     
    5656    static TopologicalVertex getVertex(Statement * expr, TopologicalGraph & G, TopologicalMap & M);
    5757
    58     inline AutoMultiplexing()
    59     : mVariables(0)
     58    inline AutoMultiplexing(const unsigned limit, const unsigned maxSelections)
     59    : mLimit(limit)
     60    , mMaxSelections(maxSelections)
     61    , mVariables(0)
    6062    , mConstraintGraph(0)
    6163    {
    6264    }
     65
    6366private:
    6467
     
    7982private:
    8083    DdManager *                 mManager;
     84    const unsigned              mLimit;
     85    const unsigned              mMaxSelections;
    8186    unsigned                    mVariables;
    8287    CharacterizationMap         mCharacterizationMap;
  • icGREP/icgrep-devel/icgrep/toolchain.cpp

    r4820 r4822  
    7878                                        cl::cat(cPabloOptimizationsOptions));
    7979
     80static cl::opt<unsigned> MultiplexingSetLimit("multiplexing-set-limit", cl::init(std::numeric_limits<unsigned>::max()),
     81                                        cl::desc("maximum size of any candidate multiplexing set."),
     82                                        cl::cat(cPabloOptimizationsOptions));
     83
     84static cl::opt<unsigned> MultiplexingSelectionLimit("multiplexing-selection-limit", cl::init(100),
     85                                        cl::desc("maximum number of selections from any partial candidate multiplexing set."),
     86                                        cl::cat(cPabloOptimizationsOptions));
     87
    8088static cl::opt<bool> EnableReassociation("reassoc", cl::init(false),
    8189                                         cl::desc("perform reassocation and distribution law optimization."),
     
    139147    if (EnableMultiplexing) {
    140148        pablo::BDDMinimizationPass::optimize(*function);
    141         pablo::AutoMultiplexing::optimize(*function);       
     149        pablo::AutoMultiplexing::optimize(*function, MultiplexingSetLimit, MultiplexingSelectionLimit);
    142150    }   
    143151    if (EnableReassociation) {
Note: See TracChangeset for help on using the changeset viewer.