Changeset 4583 for icGREP


Ignore:
Timestamp:
May 30, 2015, 4:22:10 PM (4 years ago)
Author:
nmedfort
Message:

More multiplexing work. Can only be enabled by adding -DENABLE_MULTIPLEXING=yes to the cmake command. Not quite functional yet but close.

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

Legend:

Unmodified
Added
Removed
  • icGREP/icgrep-devel/icgrep/CMakeLists.txt

    r4566 r4583  
    1414  message("-- Build with BLOCK_SIZE=128")
    1515endif()
     16option(ENABLE_MULTIPLEXING "Compiling the Multiplexing Module")
     17
    1618
    1719# configure a header file to pass some of the CMake settings
     
    5052set(Boost_USE_STATIC_LIBS ON)
    5153set(Boost_USE_MULTITHREADED OFF)
    52 set(Boost_USE_STATIC_RUNTIME OFF)
     54set(Boost_USE_STATIC_RUNTIME ON)
     55
     56if(ENABLE_MULTIPLEXING)
     57find_package(Boost COMPONENTS system)
     58else()
    5359find_package(Boost)
    54 
    55 add_library(PabloADT pablo/pabloAST.cpp pablo/ps_assign.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/codegenstate.cpp pablo/symbol_generator.cpp pablo/printer_pablos.cpp pablo/pablo_compiler.cpp pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp pablo/carry_data.cpp)
     60endif()
     61
     62SET(PABLO_SRC pablo/pabloAST.cpp pablo/ps_assign.cpp pablo/ps_if.cpp pablo/ps_while.cpp pablo/codegenstate.cpp pablo/symbol_generator.cpp pablo/printer_pablos.cpp pablo/pablo_compiler.cpp pablo/optimizers/pablo_simplifier.cpp pablo/optimizers/pablo_codesinking.cpp pablo/carry_data.cpp)
     63IF (ENABLE_MULTIPLEXING)
     64SET(PABLO_SRC ${PABLO_SRC} pablo/optimizers/pablo_automultiplexing.cpp)
     65ENDIF()
     66
     67add_library(PabloADT ${PABLO_SRC})
    5668add_library(RegExpADT re/re_re.cpp re/re_cc.cpp re/re_parser.cpp re/re_rep.cpp re/parsefailure.cpp re/re_nullable.cpp re/re_simplifier.cpp re/re_compiler.cpp re/printer_re.cpp re/re_diff.cpp re/re_intersect.cpp re/re_analysis.cpp)
    5769add_library(CCADT cc/cc_namemap.cpp cc/cc_compiler.cpp utf8_encoder.cpp UCD/CaseFolding_txt.cpp)
    5870add_library(UCDlib UCD/unicode_set.cpp UCD/precompiled_gc.cpp UCD/precompiled_sc.cpp UCD/precompiled_scx.cpp UCD/precompiled_blk.cpp UCD/precompiled_derivedcoreproperties.cpp UCD/precompiled_proplist.cpp)
     71
     72
     73IF(Boost_FOUND)
     74    include_directories("${Boost_INCLUDE_DIRS}")
     75    link_directories(${Boost_LIBRARY_DIR})
     76    SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DUSE_BOOST")
     77ENDIF()
     78
     79IF (ENABLE_MULTIPLEXING)
     80message(STATUS "Enabling Multiplexing")
     81SET(CUDD_ROOT "${CMAKE_SOURCE_DIR}/../cudd-2.5.1")
     82message(STATUS ${CUDD_ROOT})
     83file(GLOB UTIL_SOURCES "${CUDD_ROOT}/util/*.c")
     84file(GLOB MTR_SOURCES "${CUDD_ROOT}/mtr/*.c")
     85file(GLOB CUDD_SOURCES "${CUDD_ROOT}/cudd/*.c")
     86file(GLOB ST_SOURCES "${CUDD_ROOT}/st/*.c")
     87file(GLOB EPD_SOURCES "${CUDD_ROOT}/epd/*.c")
     88add_library(CUDD ${UTIL_SOURCES} ${MTR_SOURCES} ${CUDD_SOURCES} ${ST_SOURCES} ${EPD_SOURCES})
     89
     90
     91
     92include_directories(${CUDD_ROOT}/include)
     93target_link_libraries (PabloADT CUDD)
     94SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DENABLE_MULTIPLEXING")
     95ENDIF()
    5996
    6097include_directories("${PROJECT_SOURCE_DIR}")
     
    73110target_link_libraries (PabloADT ${REQ_LLVM_LIBRARIES})
    74111target_link_libraries (icgrep UCDlib PabloADT RegExpADT CCADT ${REQ_LLVM_LIBRARIES})
    75 # If Boost is on the system, include the headers and libraries
    76 IF(Boost_FOUND)
    77     include_directories("${Boost_INCLUDE_DIRS}")
    78     link_directories(${Boost_LIBRARY_DIR})
    79     SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -DUSE_BOOST")
    80     # target_link_libraries (CCADT ${Boost_LIBRARIES})
    81     # target_link_libraries (PabloADT ${Boost_LIBRARIES})
    82     # target_link_libraries (RegExpADT ${Boost_LIBRARIES})
    83 ENDIF()
    84112
    85113#Check compiler support for 0x / 11
     
    105133endif()
    106134
    107 
    108135#Disable RunTime Type Information
    109136IF (MSVC) # using Visual Studio C++
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4567 r4583  
    1919#include <pablo/optimizers/pablo_simplifier.hpp>
    2020#include <pablo/optimizers/pablo_codesinking.hpp>
     21#ifdef ENABLE_MULTIPLEXING
     22#include <pablo/optimizers/pablo_automultiplexing.hpp>
     23#endif
    2124#include "UCD/precompiled_gc.h"
    2225#include "UCD/precompiled_sc.h"
     
    159162        CodeSinking::optimize(main);
    160163    }
     164    #ifdef ENABLE_MULTIPLEXING
     165        AutoMultiplexing::optimize(basisBits, main);
     166    #endif
    161167    if (PrintOptimizedREcode) {
    162168      //Print to the terminal the AST that was generated by the pararallel bit-stream compiler.
  • icGREP/icgrep-devel/icgrep/pablo/analysis/bdd/bdd.cpp

    r4581 r4583  
    11#include "bdd.hpp"
     2#include <iostream>
    23
    34namespace bdd {
     
    2324
    2425Engine::index_type Engine::apply(const index_type l, const index_type r, const OpCode op) {
     26
     27    std::cerr << "Engine::apply(" << l << ',' << r << ',' << (int)(op) << ")\n";
    2528
    2629    switch (op) {
     
    4851    }
    4952
     53    if (l >= mNode.size() || r >= mNode.size()) {
     54        throw std::runtime_error("Accessing invalid BDD node!");
     55    }
     56
    5057    const Node & nl = mNode[l];
    51     const Node & nr = mNode[l];
     58    const Node & nr = mNode[r];
    5259
    5360    unsigned lowl = l;
    5461    unsigned highl = l;
     62    unsigned lowr = r;
     63    unsigned highr = r;
    5564    unsigned level = nl.level;
     65
    5666    if (nl.level <= nr.level) {
    5767        lowl = nl.low;
     
    5969    }
    6070
    61     unsigned lowr = r;
    62     unsigned highr = r;
    6371    if (nr.level <= nl.level) {
    6472        lowr = nr.low;
     
    95103}
    96104
    97 BDD Engine::var(const unsigned index) {
    98     return BDD(mVar[index * 2]);
    99 }
    100 
    101 BDD Engine::nvar(const unsigned index) {
    102     return BDD(mVar[index * 2 + 1]);
    103 }
    104 
    105105BDD Engine::addVar() {
    106106    unsigned level = mVar.size() >> 1;
     
    111111}
    112112
    113 Engine::Engine(const size_t initialSize) {
    114     mNode.reserve(initialSize + 2);
    115     mMap.bucket_size(initialSize);
     113void Engine::init(const size_t variables) {
     114    mNode.reserve(variables + 2);
     115    mMap.bucket_size(variables);
    116116
    117117    // add the 0 terminal
     
    126126
    127127    // and the variables
    128     mVar.resize(initialSize * 2);
    129     for (auto i = 0; i != initialSize; ++i) {
     128    mVar.resize(variables * 2);
     129    for (auto i = 0; i != variables; ++i) {
    130130        mVar[i * 2] = makeNode(i, 0, 1);
    131131        mVar[i * 2 + 1] = makeNode(i, 1, 0);
  • icGREP/icgrep-devel/icgrep/pablo/analysis/bdd/bdd.hpp

    r4582 r4583  
    99#endif
    1010#include <slab_allocator.h>
    11 
    1211
    1312namespace bdd {
     
    6564public:
    6665
    67     Engine(const size_t initialSize);
     66    inline Engine() {}
    6867
    69     BDD applyAnd(const BDD & r, const BDD & l);
     68    void init(const size_t initialSize);
    7069
    71     BDD applyOr(const BDD & r, const BDD & l);
     70    inline BDD applyAnd(const BDD & r, const BDD & l);
    7271
    73     BDD applyNot(const BDD & bdd);
     72    inline BDD applyOr(const BDD & r, const BDD & l);
    7473
    75     BDD applyXor(const BDD & r, const BDD & l);
     74    inline BDD applyNot(const BDD & bdd);
    7675
    77     BDD applySel(const BDD & cond, const BDD & trueBDD, const BDD & falseBDD);
     76    inline BDD applyXor(const BDD & r, const BDD & l);
     77
     78    inline BDD applySel(const BDD & cond, const BDD & trueBDD, const BDD & falseBDD);
    7879
    7980    BDD addVar();
    8081
    81     BDD var(const unsigned index);
     82    inline BDD var(const unsigned index);
    8283
    83     BDD nvar(const unsigned index);
     84    inline BDD nvar(const unsigned index);
    8485
    85     BDD satOne(const BDD & bdd);
     86    inline BDD satOne(const BDD & bdd);
    8687
    8788protected:
     
    184185}
    185186
     187BDD Engine::var(const unsigned index) {
     188    return BDD(mVar[index * 2]);
     189}
     190
     191BDD Engine::nvar(const unsigned index) {
     192    return BDD(mVar[index * 2 + 1]);
     193}
     194
    186195}
    187196
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4582 r4583  
    88#include <queue>
    99#include <unordered_set>
    10 #include <pablo/analysis/bdd/bdd.hpp>
    1110#include <boost/container/flat_set.hpp>
    1211#include <boost/numeric/ublas/matrix.hpp>
    1312#include <include/simd-lib/builtins.hpp>
    1413// #include <pablo/expression_map.hpp>
     14#include <pablo/printer_pablos.h>
     15#include <iostream>
     16#include <cudd.h>
     17#include <util.h>
     18#include <fstream>
    1519
    1620using namespace llvm;
    17 using namespace bdd;
    1821using namespace boost;
    1922using namespace boost::container;
     
    2427void AutoMultiplexing::optimize(const std::vector<Var *> & input, PabloBlock & entry) {
    2528    AutoMultiplexing am;
    26     Engine eng = am.initialize(input, entry);
    27     am.characterize(eng, entry);
     29    am.initialize(input, entry);
     30    am.characterize(entry);
     31    am.shutdown();
    2832    am.createMultiplexSetGraph();
    2933    std::random_device rd;
     
    3539        am.topologicalSort(entry);
    3640    }
     41
    3742}
    3843
     
    4550 * the proper variable ordering.
    4651 ** ------------------------------------------------------------------------------------------------------------- */
    47 Engine AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
     52void AutoMultiplexing::initialize(const std::vector<Var *> & vars, const PabloBlock & entry) {
    4853
    4954    flat_map<const PabloAST *, unsigned> map;
    50     for (const Var * var : vars) {
    51         map.emplace(var, 0);
    52     }
    53 
     55    std::vector<const Statement *> complex;
    5456    std::stack<const Statement *> scope;
    5557
    5658    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
    57     unsigned n = 0, m = 1, variables = 0;
     59    unsigned n = 0, m = 0;
    5860    for (const Statement * stmt = entry.front(); ; ) {
    5961        while ( stmt ) {
     
    6870                continue;
    6971            }
     72
    7073            switch (stmt->getClassTypeId()) {
    7174                case PabloAST::ClassTypeId::Advance:
     
    7578                case PabloAST::ClassTypeId::ScanThru:
    7679                case PabloAST::ClassTypeId::MatchStar:
    77                     ++variables;
     80                    complex.push_back(stmt);
    7881                    break;
    7982                default:
     
    102105    }
    103106
     107    n = m;
    104108    m = 0;
    105     n = m;
     109
    106110    const Statement * stmt = entry.front();
    107111    for (;;) {
    108112        while ( stmt ) {
     113
    109114            unsigned u;
    110115            if (isa<Advance>(stmt)) {
    111116                assert (mAdvance[m] == stmt);
    112                 u = ++m;
     117                u = m++;
    113118            }
    114119            else {
    115                 u = ++n;
     120                u = n++;
    116121                map.emplace(stmt, u);
    117122            }
     123
    118124            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    119125                const PabloAST * const op = stmt->getOperand(i);
    120                 if (LLVM_UNLIKELY(isa<Integer>(op) || isa<String>(op))) {
    121                     continue;
    122                 }
    123                 const unsigned v = map[op];
    124                 for (unsigned w = 0; w != m; ++w) {
    125                     G(v, w) |= G(u, w);
     126                if (LLVM_LIKELY(isa<Statement>(op))) {
     127                    const unsigned v = map[op];
     128                    for (unsigned w = 0; w != m; ++w) {
     129                        G(u, w) |= G(v, w);
     130                    }
    126131                }
    127132            }
     
    145150
    146151    // Record our transitive closure in the path graph and remove any reflexive-loops
    147     mPathGraph = PathGraph(m - 1);
    148     for (unsigned i = 1; i != m; ++i) {
    149         for (unsigned j = 1; j != m; ++j) {
     152    mPathGraph = PathGraph(m);
     153    for (unsigned i = 0; i != m; ++i) {
     154        G(i, i) = false;
     155        for (unsigned j = 0; j != m; ++j) {
    150156            if (G(i, j)) {
    151                 add_edge(i - 1, j - 1, mPathGraph);
    152             }
    153         }
    154         G(i, i) = false;
     157                add_edge(i, j, mPathGraph);
     158            }
     159        }       
    155160    }
    156161
    157162    // Now take the transitive reduction of G
    158     for (unsigned j = 1; j != m; ++j) {
    159         for (unsigned i = 1; i != m; ++i) {
     163    for (unsigned j = 0; j != m; ++j) {
     164        for (unsigned i = 0; i != m; ++i) {
    160165            if (G(i, j)) {
    161166                // Eliminate any unecessary arcs not covered by a longer path
     
    167172    }
    168173
    169     // And now transcribe it into our base constraint graph
    170     mConstraintGraph = ConstraintGraph(m - 1);
    171     for (unsigned j = 1; j != m; ++j) {
    172         for (unsigned i = 1; i != m; ++i) {
     174    // And now transcribe it into our base constraint graph. Since G is a use-def
     175    // graph and we want our constraint graph to be a def-use graph, reverse the
     176    // edges as we're writing them to obtain the transposed graph.
     177    mConstraintGraph = ConstraintGraph(m);
     178    for (unsigned j = 0; j != m; ++j) {
     179        for (unsigned i = 0; i != m; ++i) {
    173180            if (G(i, j)) {
    174                 add_edge(i - 1, j - 1, mConstraintGraph);
     181                add_edge(j, i, mConstraintGraph);
    175182            }
    176183        }
     
    178185
    179186    // Initialize the BDD engine ...
    180     Engine engine(variables + vars.size());
    181     mCharacterizationMap.emplace(entry.createZeroes(), BDD::Contradiction());
    182     mCharacterizationMap.emplace(entry.createOnes(), BDD::Tautology());
     187    mManager = Cudd_Init((complex.size() + vars.size()), 0, CUDD_UNIQUE_SLOTS, CUDD_CACHE_SLOTS, 0);
     188
     189    // Map the predefined 0/1 entries
     190    mCharacterizationMap.emplace(entry.createZeroes(), Cudd_ReadZero(mManager));
     191    mCharacterizationMap.emplace(entry.createOnes(), Cudd_ReadOne(mManager));
     192
    183193    // Order the variables so the input Vars are pushed to the end; they ought to
    184194    // be the most complex to resolve.
     195    unsigned i = 0;
     196    for (const Statement * stmt : complex) {
     197        mCharacterizationMap.emplace(stmt, Cudd_bddIthVar(mManager, i++));
     198    }
    185199    for (const Var * var : vars) {
    186         mCharacterizationMap.emplace(var, engine.var(variables++));
    187     }
    188     return engine;
     200        mCharacterizationMap.emplace(var, Cudd_bddIthVar(mManager, i++));
     201    }
    189202}
    190203
    191204/** ------------------------------------------------------------------------------------------------------------- *
    192205 * @brief characterize
    193  * @param engine the BDD engine
    194206 * @param vars the input vars for this program
    195207 *
    196208 * Scan through the program and iteratively compute the BDDs for each statement.
    197209 ** ------------------------------------------------------------------------------------------------------------- */
    198 void AutoMultiplexing::characterize(Engine & engine, PabloBlock & entry) {
    199 
    200     std::vector<std::pair<BDD, BDD>> advances; // the input BDD and the BDD variable of the i-th Advance
     210void AutoMultiplexing::characterize(PabloBlock & entry) {
     211
     212    std::vector<std::pair<DdNode *, DdNode *>> advances; // the input BDD and the BDD variable of the i-th Advance
    201213    std::stack<Statement *> scope;
    202 
    203     advances.reserve(mAdvance.size());
    204 
    205     unsigned variables = 0;
    206214
    207215    // Scan through and collect all the advances, calls, scanthrus and matchstars ...
     
    219227            }
    220228
    221             BDD bdd; // defaults to false
     229            DdNode * bdd = nullptr;
    222230
    223231            // Map our operands to the computed BDDs
    224             std::array<BDD, 3> input;
     232            std::array<DdNode *, 3> input;
    225233            for (unsigned i = 0; i != stmt->getNumOperands(); ++i) {
    226234                PabloAST * const op = stmt->getOperand(i);
     
    235243            }
    236244
     245            PabloAST * expr = stmt;
    237246            bool testContradiction = true;
    238247
     
    242251                    break;
    243252                case PabloAST::ClassTypeId::And:
    244                     bdd = engine.applyAnd(input[0], input[1]);
     253                    bdd = And(input[0], input[1]);
    245254                    break;
     255                case PabloAST::ClassTypeId::Next:
     256                    // The next instruction is almost identical to an OR; however, a Next cannot be
     257                    // an operand of a Statement. Instead it updates the Initial operand's value.
     258                    testContradiction = false;
     259                    expr = stmt->getOperand(0);
    246260                case PabloAST::ClassTypeId::Or:
    247                 case PabloAST::ClassTypeId::Next:
    248                     bdd = engine.applyOr(input[0], input[1]);
     261                    bdd = Or(input[0], input[1]);
    249262                    break;
    250263                case PabloAST::ClassTypeId::Xor:
    251                     bdd = engine.applyXor(input[0], input[1]);
     264                    bdd = Xor(input[0], input[1]);
    252265                    break;
    253266                case PabloAST::ClassTypeId::Not:
    254                     bdd = engine.applyNot(input[0]);
     267                    bdd = Not(input[0]);
    255268                    break;
    256269                case PabloAST::ClassTypeId::Sel:
    257                     bdd = engine.applySel(input[0], input[1], input[2]);
     270                    bdd = Ite(input[0], input[1], input[2]);
    258271                    break;
    259272                case PabloAST::ClassTypeId::ScanThru:
    260                     // It may be possible use "engine.applyNot(input[1])" for ScanThrus if we rule out the
     273                    // It may be possible use "mEngine.applyNot(input[1])" for ScanThrus if we rule out the
    261274                    // possibility of a contradition being erroneously calculated later. An example of this
    262275                    // would be ¬(ScanThru(c,m) √ m) but are there others that would be harder to predict?
    263276                case PabloAST::ClassTypeId::MatchStar:
    264                     if (LLVM_UNLIKELY(input[0].isFalse() || input[1].isFalse())) {
     277                    if (LLVM_UNLIKELY(isZero(input[0]) || isZero(input[1]))) {
     278                        bdd = Cudd_ReadZero(mManager);
    265279                        break;
    266280                    }
    267281                case PabloAST::ClassTypeId::Call:
    268282                    testContradiction = false;
    269                     bdd = engine.var(variables++);
     283                    assert (mCharacterizationMap.count(stmt));
     284                    bdd = mCharacterizationMap[stmt];
    270285                    break;
    271286                case PabloAST::ClassTypeId::Advance:
    272                     if (LLVM_LIKELY(!input[0].isFalse())) {
     287
     288                    assert (stmt == mAdvance[advances.size()]);
     289
     290                    if (LLVM_UNLIKELY(isZero(input[0]))) {
     291                        bdd = Cudd_ReadZero(mManager);
     292                        // mark this advance as having an input and output of 0
     293                        advances.emplace_back(bdd, bdd);
     294                    }
     295                    else {
    273296
    274297                        // When we built the path graph, we constructed it in the same order; hense the row/column of
    275298                        // the path graph is equivalent to the index.
    276299
    277                         const BDD Vk = bdd = engine.var(variables++);
    278                         const BDD Ik = input[0];
     300                        assert (mCharacterizationMap.count(stmt));
     301                        DdNode * Ik = input[0];
     302                        DdNode * Vk = bdd = mCharacterizationMap[stmt];
    279303                        const unsigned k = advances.size();
    280304
    281                         assert (stmt == mAdvance[k]);
    282 
    283305                        for (unsigned i = 0; i != k; ++i) {
    284306
    285307                            Advance * adv = mAdvance[i];
    286                             const BDD Ii = std::get<0>(advances[i]);
    287                             const BDD Vi = std::get<1>(advances[i]);
     308                            DdNode * Ii = std::get<0>(advances[i]);
     309                            DdNode * Vi = std::get<1>(advances[i]);
    288310
    289311                            bool constrained = true;
    290312
    291313                            // If these advances are "shifting" their values by the same amount and aren't transitively dependant ...
    292                             if ((stmt->getOperand(1) != adv->getOperand(1)) && !edge(k, i, mPathGraph).second) {
    293 
    294                                 const BDD C = engine.applyAnd(Ik, Ii); // do we need to simplify this to identify subsets?
     314                            if ((stmt->getOperand(1) == adv->getOperand(1)) && (!edge(k, i, mPathGraph).second)) {
     315
     316                                DdNode * tmp = And(Ik, Ii); // do we need to simplify this to identify subsets?
     317
    295318                                // Is there any satisfying truth assignment? If not, these streams are mutually exclusive.
    296                                 bool mutuallyExclusive = engine.satOne(C).isFalse();
    297 
    298                                 if (mutuallyExclusive) {
    299                                     auto f = mCharacterizationMap.find(adv);
    300                                     assert (f != mCharacterizationMap.end());
     319                                if (noSatisfyingAssignment(tmp)) {
     320
     321                                    assert (mCharacterizationMap.count(adv));
     322
     323                                    DdNode *& other = mCharacterizationMap[adv];
    301324                                    // mark the i-th and k-th Advances as being mutually exclusive
    302                                     bdd = engine.applyAnd(bdd, engine.applyNot(Vi));
    303                                     f->second = engine.applyAnd(f->second, engine.applyNot(Vk));
    304 
     325                                    bdd = And(bdd, Not(Vi));
     326                                    other = And(other, Not(Vk));
    305327                                    // If these advances are not from the same scope, we cannot safely multiplex them even if
    306328                                    // they're mutually exclusive.
    307329                                    constrained = (stmt->getParent() != adv->getParent());
    308330                                }
    309 
    310                                 if (constrained) {
    311                                     // Test whether one of the inputs to these advances are a subset of the other
    312                                     if (LLVM_UNLIKELY(Ik == C)) {
     331                                else { // Test whether one of the inputs to these advances are a subset of the other
     332                                    if (LLVM_UNLIKELY(Ik == tmp)) {
    313333                                        // If Ik = C and C = Ii ∩ Ik then Ik (the input to the k-th advance) is a *subset* of Ii (the input of the
    314334                                        // i-th advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the
    315                                         // multiplex set graph if Advance_i and Advance_k happen to be mutually exclusive set.
     335                                        // multiplex set graph if Advance_i and Advance_k happen to be in the same mutually exclusive set.
    316336                                        mSubsetGraph.emplace_back(k, i);
    317                                         continue;
     337                                        constrained = false;
    318338                                    }
    319                                     else if (LLVM_UNLIKELY(Ii == C)) {
     339                                    else if (LLVM_UNLIKELY(Ii == tmp)) {
    320340                                        mSubsetGraph.emplace_back(i, k);
    321                                         continue;
     341                                        constrained = false;
    322342                                    }
    323343                                }
     344
     345                                Cudd_RecursiveDeref(mManager, tmp);
    324346                            }
    325347
     
    331353
    332354                        }
    333                     }
    334 
    335                     // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
    336                     // eliminate the need for looking it up again.
    337                     advances.emplace_back(input[0], bdd);
    338 
    339                     testContradiction = false;
     355
     356                        // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to
     357                        // eliminate the need for looking it up again.
     358                        advances.emplace_back(input[0], Vk);
     359                        testContradiction = false;
     360                    }
     361
    340362
    341363                    break;
    342             }
    343             if (LLVM_UNLIKELY(testContradiction && engine.satOne(bdd).isFalse())) {
     364                default:
     365                    throw std::runtime_error("Unexpected statement " + stmt->getName()->to_string());
     366            }
     367            if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) {
     368                Cudd_RecursiveDeref(mManager, bdd);
    344369                stmt = stmt->replaceWith(entry.createZeroes());
    345370            }
    346371            else {
    347                 mCharacterizationMap.emplace(stmt, bdd);
     372                mCharacterizationMap[expr] = bdd;
    348373                stmt = stmt->getNextNode();
    349374            }
     
    357382    }
    358383}
     384
     385/** ------------------------------------------------------------------------------------------------------------- *
     386 * @brief CUDD wrappers
     387 ** ------------------------------------------------------------------------------------------------------------- */
     388
     389inline bool AutoMultiplexing::isZero(DdNode * x) const {
     390    return x == Cudd_ReadZero(mManager);
     391}
     392
     393inline DdNode * AutoMultiplexing::And(DdNode * x, DdNode * y) {
     394    DdNode * r = Cudd_bddAnd(mManager, x, y);
     395    Cudd_Ref(r);
     396    return r;
     397}
     398
     399inline DdNode * AutoMultiplexing::Or(DdNode * x, DdNode * y) {
     400    DdNode * r = Cudd_bddOr(mManager, x, y);
     401    Cudd_Ref(r);
     402    return r;
     403}
     404
     405inline DdNode * AutoMultiplexing::Xor(DdNode * x, DdNode * y) {
     406    DdNode * r = Cudd_bddXor(mManager, x, y);
     407    Cudd_Ref(r);
     408    return r;
     409}
     410
     411inline DdNode * AutoMultiplexing::Not(DdNode * x) {
     412    return Cudd_Not(x);
     413}
     414
     415inline DdNode * AutoMultiplexing::Ite(DdNode * x, DdNode * y, DdNode * z) {
     416    DdNode * r = Cudd_bddIte(mManager, x, y, z);
     417    Cudd_Ref(r);
     418    return r;
     419}
     420
     421inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * x) {
     422    int* cube;
     423    CUDD_VALUE_TYPE dummy;
     424    return Cudd_IsGenEmpty(Cudd_FirstCube(mManager, x, &cube, &dummy));
     425}
     426
     427inline void AutoMultiplexing::shutdown() {
     428    Cudd_Quit(mManager);
     429}
     430
    359431
    360432/** ------------------------------------------------------------------------------------------------------------- *
     
    391463        }
    392464    }
     465
     466    assert (!S.empty());
    393467
    394468    for ( ; remainingVerticies >= 3; --remainingVerticies) {
     
    411485    }
    412486
     487    raw_os_ostream out(std::cerr);
     488
     489    out << "\n\ndigraph G {\n";
     490
     491    const unsigned m = num_vertices(mConstraintGraph);
     492    const unsigned n = num_vertices(mMultiplexSetGraph);
     493
     494    for (unsigned i = 0; i != m; ++i) {
     495        out << "v" << i << " [shape=box,label=\"" << mAdvance[i]->getName()->to_string() << "\"];\n";
     496    }
     497    for (unsigned i = m; i != n; ++i) {
     498        out << "v" << i << " [shape=circle];\n";
     499    }
     500
     501    for (unsigned i = m; i != n; ++i) {
     502        graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
     503        for (std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph); ei != ei_end; ++ei) {
     504            out << "v" << i << " -> v" << target(*ei, mMultiplexSetGraph) << ";\n";
     505        }
     506    }
     507
     508    out << "}\n\n";
     509
     510
    413511    return canMultiplex;
    414512}
     
    438536    // from contracting one advance node edge with an adjacent vertex
    439537
     538    using Set = flat_set<IndependentSetGraph::vertex_descriptor>;
    440539    const unsigned m = num_vertices(mConstraintGraph);
    441     const unsigned n = num_vertices(mMultiplexSetGraph);
     540    const unsigned n = num_vertices(mMultiplexSetGraph) - m;
    442541
    443542    IndependentSetGraph G(n);
    444543
    445     // Record the "weight" of this independent set vertex
    446     for (IndependentSetGraph::vertex_descriptor i = m; i != n; ++i) {
    447         G[i] = out_degree(i, mMultiplexSetGraph);
    448     }
    449 
    450     // Make all vertices in G adjacent if they are mutually adjacent to a set vertex in S.
    451     for (MultiplexSetGraph::vertex_descriptor i = m; i != n; ++i) {
    452         graph_traits<MultiplexSetGraph>::in_edge_iterator ei, ei_end;
    453         std::tie(ei, ei_end) = in_edges(i, mMultiplexSetGraph);
    454         for (; ei != ei_end; ++ei) {
    455             for (auto ej = ei; ej != ei; ++ej) {
    456                 add_edge(source(*ei, mMultiplexSetGraph), source(*ej, mMultiplexSetGraph), G);
    457             }
    458         }
    459     }
     544    if (true) {
     545
     546        std::vector<Set> S(n);
     547        // Record the "weight" of this set vertex and compute the actual set
     548        for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) {
     549            G[i] = out_degree(i + m, mMultiplexSetGraph);
     550            Set & Si = S[i];
     551            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
     552            // What are the members of the i-th set? (i.e., the outgoing edges of the i-th set vertex)
     553            for (std::tie(ei, ei_end) = out_edges(i + m, mMultiplexSetGraph); ei != ei_end; ++ei) {
     554                Si.insert(target(*ei, mMultiplexSetGraph));
     555            }
     556        }
     557
     558        // Make all vertices in G adjacent if their sets intersect.
     559        for (unsigned i = 1; i != n; ++i) {
     560            const Set & Si = S[i];
     561            for (unsigned j = 0; j != i; ++j) {
     562                const Set & Sj = S[j];
     563                auto mi = Si.begin();
     564                const auto mi_end = Si.end();
     565                auto mj = Sj.begin();
     566                const auto mj_end = Sj.end();
     567                while (mi != mi_end && mj != mj_end) {
     568                    if (*mi < *mj) {
     569                        ++mi;
     570                    }
     571                    else if (*mj < *mi) {
     572                        ++mj;
     573                    }
     574                    else {
     575                        // they intersect; add an edge between them.
     576                        add_edge(i, j, G);
     577                        break;
     578                    }
     579                }
     580            }
     581        }
     582    }
     583
    460584    // Process the graph using the greedy method of "Approximation Algorithms for the Weighted Independent Set Problem" (2005)
    461     // (Note: look into minimum independent dominating set algorithms. It fits better with the log2 + subset relationship cost model.)
     585    // (Note: look into minimum independent dominating set algorithms. It fits better with the ceil log2 + subset cost model.)
    462586    std::vector<IndependentSetGraph::vertex_descriptor> S;
    463587    std::vector<bool> removed(n, false);
     
    480604            }
    481605        }
     606
    482607        if (S.empty()) {
    483608            break;
    484609        }
    485610        // Select u from S
    486         const auto u = S[S.size() == 1 ? 0 : RNGDistribution(0, S.size() - 1)(rng)];
     611        const auto i = S.begin() + RNGDistribution(0, S.size() - 1)(rng);
     612        const auto u = *i;
     613        S.erase(i);
     614
    487615        // Remove u and its adjacencies from G; clear the adjacent set vertices from the multiplex set graph. This will effectively
    488616        // choose the set refered to by u as one of our chosen independent sets and discard any other sets that contain one
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp

    r4582 r4583  
    55#include <slab_allocator.h>
    66#include <queue>
    7 #include <pablo/analysis/bdd/bdd.hpp>
    87#include <boost/graph/adjacency_list.hpp>
    98#include <boost/graph/adjacency_matrix.hpp>
     
    1413#include <stdint.h>
    1514
     15struct DdManager; // forward declare of the CUDD manager
     16struct DdNode;
     17
    1618namespace pablo {
    1719
    1820class AutoMultiplexing {
    1921
    20     using CharacterizationMap = boost::container::flat_map<const PabloAST *, bdd::BDD>;
     22    using CharacterizationMap = boost::container::flat_map<const PabloAST *, DdNode *>;
    2123    using ConstraintGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>;
    2224    using PathGraph = boost::adjacency_matrix<boost::undirectedS>;
     
    3941    static void optimize(const std::vector<Var *> & input, PabloBlock & entry);
    4042protected:
    41     bdd::Engine initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
    42     void characterize(bdd::Engine & engine, PabloBlock &entry);
     43    void initialize(const std::vector<Var *> & vars, const PabloBlock & entry);
     44    void characterize(PabloBlock & entry);   
    4345    void createMultiplexSetGraph();
    4446    bool generateMultiplexSets(RNG & rng);   
     
    4951    void topologicalSort(PabloBlock & entry) const;
    5052    void topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q, TopologicalSortMap & M, Statement * ip, Statement * first) const;
    51 
     53    inline AutoMultiplexing()
     54    : mPathGraph(0) {
     55    }
    5256private:
    53     AutoMultiplexing();
    54 
     57    bool isZero(DdNode * x) const;
     58    DdNode * And(DdNode * x, DdNode * y);
     59    DdNode * Or(DdNode * x, DdNode * y);
     60    DdNode * Xor(DdNode * x, DdNode * y);
     61    DdNode * Not(DdNode * x);
     62    DdNode * Ite(DdNode * x, DdNode * y, DdNode * z);
     63    bool noSatisfyingAssignment(DdNode * x);
     64    void shutdown();
     65private:
     66    DdManager *             mManager;
    5567    CharacterizationMap     mCharacterizationMap;
    5668    PathGraph               mPathGraph;
Note: See TracChangeset for help on using the changeset viewer.