Ignore:
Timestamp:
Jul 4, 2015, 5:22:38 PM (4 years ago)
Author:
nmedfort
Message:

Temporary check in for demuxing simplification.

Location:
icGREP/icgrep-devel/icgrep/pablo/optimizers
Files:
2 edited

Legend:

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

    r4638 r4639  
    2020using namespace boost::numeric::ublas;
    2121
    22 #define PRINT_DEBUG_OUTPUT
     22// #define PRINT_DEBUG_OUTPUT
    2323
    2424#if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT)
     
    107107    LOG("Seed:                    " << seed);
    108108
    109     AutoMultiplexing am;
     109    AutoMultiplexing am(input);
    110110    RECORD_TIMESTAMP(start_initialize);
    111     am.initialize(input, entry);
     111    am.initialize(entry);
    112112    RECORD_TIMESTAMP(end_initialize);
    113113
     
    151151
    152152    RECORD_TIMESTAMP(start_shutdown);
    153     am.shutdown();
     153    am.Shutdown();
    154154    RECORD_TIMESTAMP(end_shutdown);
    155155    LOG("Shutdown:                " << (end_shutdown - start_shutdown));
     
    168168 * the proper variable ordering.
    169169 ** ------------------------------------------------------------------------------------------------------------- */
    170 void AutoMultiplexing::initialize(const std::vector<Var *> & vars, PabloBlock & entry) {
     170void AutoMultiplexing::initialize(PabloBlock & entry) {
    171171
    172172    flat_map<const PabloAST *, unsigned> map;   
     
    285285
    286286    // Initialize the BDD engine ...
    287     mManager = Cudd_Init((complexStatements + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     287    mManager = Cudd_Init((complexStatements + mBaseVariables.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
    288288    Cudd_AutodynDisable(mManager);
    289289
     
    295295    // be the most complex to resolve.
    296296    unsigned i = complexStatements;
    297     for (const Var * var : vars) {
     297    for (const Var * var : mBaseVariables) {
    298298        mCharacterizationMap[var] = Cudd_bddIthVar(mManager, i++);
    299299    }
     
    408408                DdNode * const IiIk = And(Ik, Ii);
    409409                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    410                 if (noSatisfyingAssignment(IiIk)) {
     410                if (NoSatisfyingAssignment(IiIk)) {
    411411                    assert (mCharacterizationMap.count(tmp));
    412412                    DdNode *& Ci = mCharacterizationMap[tmp];
     
    535535}
    536536
    537 inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * const x) {
     537inline bool AutoMultiplexing::NoSatisfyingAssignment(DdNode * const x) {
    538538    return Cudd_bddLeq(mManager, x, Zero());
    539539}
    540540
    541 inline void AutoMultiplexing::shutdown() {
     541inline void AutoMultiplexing::Shutdown() {
    542542    #ifdef PRINT_DEBUG_OUTPUT
    543543    Cudd_PrintInfo(mManager, stderr);
     
    10001000            }
    10011001
    1002             simplify(muxed, m, builder);
    1003         }
    1004     }
    1005 }
     1002            // simplify(muxed, m, builder);
     1003        }
     1004    }
     1005}
     1006
     1007
    10061008
    10071009/** ------------------------------------------------------------------------------------------------------------- *
     
    10101012void AutoMultiplexing::simplify(const std::vector<PabloAST *> & variables, const unsigned n, PabloBuilder & builder) const {
    10111013
    1012 
    1013 
    1014 
     1014    std::queue<PabloAST *> Q;
     1015    llvm::DenseMap<PabloAST *, DdNode *> characterization;
     1016    boost::container::flat_set<PabloAST *> uncharacterized;
     1017
     1018    DdManager * manager = Cudd_Init(n + mBaseVariables.size(), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     1019    Cudd_AutodynDisable(manager);
     1020
     1021    unsigned i = 0;
     1022    for (; i != n; ++i) {
     1023        PabloAST * const var = variables[i];
     1024        Q.push(var);
     1025        characterization[var] = Cudd_bddIthVar(manager, i);
     1026    }
     1027
     1028    for (Var * var : mBaseVariables) {
     1029        characterization[var] = Cudd_bddIthVar(manager, i++);
     1030    }
     1031
     1032    std::array<DdNode *, 3> input;
     1033
     1034    while (!Q.empty()) {
     1035        PabloAST * const var = Q.front(); Q.pop();
     1036        for (PabloAST * user : var->users()) {
     1037            Statement * stmt = nullptr;
     1038            // If this user is a boolean operation ...
     1039            switch (user->getClassTypeId()) {
     1040                case PabloAST::ClassTypeId::And:
     1041                case PabloAST::ClassTypeId::Or:
     1042                case PabloAST::ClassTypeId::Not:
     1043                case PabloAST::ClassTypeId::Xor:
     1044                case PabloAST::ClassTypeId::Sel:
     1045                    // And it is within the same scope ...
     1046                    if ((stmt = cast<Statement>(user))->getParent() == &builder.getPabloBlock()) {
     1047                        bool characterized = true;
     1048                        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     1049                            auto f = characterization.find(stmt->getOperand(i));
     1050                            if (f == characterization.end()) {
     1051                                characterized = false;
     1052                                break;
     1053                            }
     1054                            input[i] = f->second;
     1055                        }
     1056                        // And every input operand is characterizied ...
     1057                        if (characterized) {
     1058                            DdNode * bdd = nullptr;
     1059                            switch (user->getClassTypeId()) {
     1060                                case PabloAST::ClassTypeId::And:
     1061                                    bdd = Cudd_bddAnd(manager, input[0], input[1]);
     1062                                    break;
     1063                                case PabloAST::ClassTypeId::Or:
     1064                                    bdd = Cudd_bddOr(manager, input[0], input[1]);
     1065                                    break;
     1066                                case PabloAST::ClassTypeId::Not:
     1067                                    bdd = Cudd_Not(input[0]);
     1068                                    break;
     1069                                case PabloAST::ClassTypeId::Xor:
     1070                                    bdd = Cudd_bddXor(manager, input[0], input[1]);
     1071                                    break;
     1072                                case PabloAST::ClassTypeId::Sel:
     1073                                    bdd = Cudd_bddIte(manager, input[0], input[1], input[2]);
     1074                                    break;
     1075                                default: __builtin_unreachable();
     1076                            }
     1077                            characterization[stmt] = bdd;
     1078                            uncharacterized.erase(stmt);
     1079                            for (PabloAST * next : stmt->users()) {
     1080                                if (characterization.count(next) == 0) {
     1081                                    Q.push(next);
     1082                                }
     1083                            }
     1084                            break;
     1085                        }
     1086                    }
     1087                default:
     1088                    // Otherwise we probably apply Quine McCluskey to one of this statements operands
     1089                    // presuming they aren't characterized properly later.
     1090                    uncharacterized.insert(user);
     1091                    break;
     1092            }
     1093        }
     1094    }
     1095    // Gether up the output statements from the characterized inputs of the uncharacterized statements
     1096    llvm::DenseMap<PabloAST *, DdNode *> outputs;
     1097    for (PabloAST * var : uncharacterized) {
     1098        Statement * stmt = cast<Statement>(var);
     1099        for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
     1100            auto f = characterization.find(stmt->getOperand(i));
     1101            if (f != characterization.end()) {
     1102                outputs.insert(std::make_pair(f->first, f->second));
     1103            }
     1104        }
     1105    }
     1106
     1107    circular_buffer<PabloAST *> S(n);
     1108
     1109    CUDD_VALUE_TYPE value;
     1110    int * cube = nullptr;
     1111    for (auto itr : outputs) {
     1112        // Look into doing some more analysis here to see if a Xor or Sel operation is possible.
     1113        DdGen * gen = Cudd_FirstCube(manager, itr.second, &cube, &value);
     1114        while (!Cudd_IsGenEmpty(gen)) {
     1115            // cube[0 ... n - 1] = { 0 : false, 1: true, 2: don't care }
     1116            for (unsigned i = n - 1; i; --i) {
     1117                if (cube[i] == 0) {
     1118                    S.push_back(variables[i]);
     1119                }
     1120            }
     1121
     1122            if (S.size() > 0) {
     1123                while(S.size() > 1) {
     1124                    PabloAST * A = S.front(); S.pop_front();
     1125                    PabloAST * B = S.front(); S.pop_front();
     1126                    S.push_back(builder.createOr(A, B));
     1127                }
     1128                PabloAST * C = S.front(); S.pop_front();
     1129                S.push_back(builder.createNot(C));
     1130            }
     1131
     1132            for (unsigned i = n - 1; i; --i) {
     1133                if (cube[i] == 1) {
     1134                    S.push_back(variables[i]);
     1135                }
     1136            }
     1137
     1138            while(S.size() > 1) {
     1139                PabloAST * A = S.front(); S.pop_front();
     1140                PabloAST * B = S.front(); S.pop_front();
     1141                S.push_back(builder.createAnd(A, B));
     1142            }
     1143
     1144            Q.push(S.front()); S.pop_front();
     1145
     1146            Cudd_NextCube(gen, &cube, &value);
     1147        }
     1148        Cudd_GenFree(gen);
     1149
     1150        while (Q.size() > 1) {
     1151            PabloAST * A = Q.front(); Q.pop();
     1152            PabloAST * B = Q.front(); Q.pop();
     1153            Q.push(builder.createOr(A, B));
     1154        }
     1155
     1156        Statement * stmt = cast<Statement>(itr.first);
     1157        stmt->replaceWith(Q.front(), true, true);
     1158        Q.pop();
     1159    }
     1160    Cudd_Quit(manager);
    10151161
    10161162
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4638 r4639  
    3838    static bool optimize(const std::vector<Var *> & input, PabloBlock & entry);
    3939protected:
    40     void initialize(const std::vector<Var *> & vars, PabloBlock & entry);
     40    void initialize(PabloBlock & entry);
    4141    void characterize(PabloBlock & block);
    4242    DdNode * characterize(Statement * const stmt);
     
    4848    void applySubsetConstraints();
    4949    void multiplexSelectedIndependentSets() const;
    50     void simplify(const std::vector<PabloAST *> & variables, const unsigned m, PabloBuilder & block) const;
     50    void simplify(const std::vector<PabloAST *> & variables, const unsigned n, PabloBuilder & block) const;
    5151    void topologicalSort(PabloBlock & entry) const;
    52     inline AutoMultiplexing()
     52    inline AutoMultiplexing(const std::vector<Var *> & vars)
    5353    : mVariables(0)
    5454    , mConstraintGraph(0)
     55    , mBaseVariables(vars)
    5556    {
    5657    }
    5758private:
     59
    5860    DdNode * Zero() const;
    5961    DdNode * One() const;
     
    6567    DdNode * Ite(DdNode * const x, DdNode * const y, DdNode * const z);
    6668    DdNode * NewVar();
    67     bool noSatisfyingAssignment(DdNode * const x);
    68     void shutdown();
     69    bool NoSatisfyingAssignment(DdNode * const x);
     70    void Shutdown();
     71
    6972private:
    70     DdManager *             mManager;
    71     unsigned                mVariables;
    72     CharacterizationMap     mCharacterizationMap;
    73     ConstraintGraph         mConstraintGraph;
    74     SubsetGraph             mSubsetGraph;
    75     AdvanceMap              mAdvanceMap;
    76     AdvanceVector           mAdvance;
    77     MultiplexSetGraph       mMultiplexSetGraph;
     73    DdManager *                 mManager;
     74    unsigned                    mVariables;
     75    CharacterizationMap         mCharacterizationMap;
     76    ConstraintGraph             mConstraintGraph;
     77    SubsetGraph                 mSubsetGraph;
     78    AdvanceMap                  mAdvanceMap;
     79    AdvanceVector               mAdvance;
     80    MultiplexSetGraph           mMultiplexSetGraph;
     81    const std::vector<Var *> &  mBaseVariables;
    7882};
    7983
Note: See TracChangeset for help on using the changeset viewer.