Ignore:
Timestamp:
Jun 2, 2015, 5:22:53 PM (4 years ago)
Author:
nmedfort
Message:

More multiplexing work.

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

Legend:

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

    r4586 r4587  
    279279SET(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS} -O3 -DNDEBUG")
    280280IF (${CMAKE_SYSTEM} MATCHES "Linux")
    281     SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g -fsanitize=address -fsanitize=undefined-trap")
     281    SET(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS} -g -fsanitize=alignment")
    282282ENDIF()
    283283
  • icGREP/icgrep-devel/icgrep/compiler.cpp

    r4583 r4587  
    162162        CodeSinking::optimize(main);
    163163    }
     164
     165
     166
    164167    #ifdef ENABLE_MULTIPLEXING
    165168        AutoMultiplexing::optimize(basisBits, main);
  • icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp

    r4586 r4587  
    1111#include <unordered_map>
    1212#include <boost/numeric/ublas/matrix.hpp>
     13#include <boost/circular_buffer.hpp>
    1314#include <include/simd-lib/builtins.hpp>
    1415// #include <pablo/expression_map.hpp>
     
    2223using namespace boost::container;
    2324using namespace boost::numeric::ublas;
    24 
    25 #define PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS
    2625
    2726namespace pablo {
     
    247246            }
    248247
    249             PabloAST * expr = stmt;
    250248            bool testContradiction = true;
    251249
     
    261259                    // an operand of a Statement. Instead it updates the Initial operand's value.
    262260                    testContradiction = false;
    263                     expr = stmt->getOperand(0);
    264261                case PabloAST::ClassTypeId::Or:
    265262                    bdd = Or(input[0], input[1]);
     
    318315                            if ((stmt->getOperand(1) == adv->getOperand(1)) && (!edge(k, i, mPathGraph).second)) {
    319316
     317                                // Test this with Cudd_bddIntersect(mManager, Ik, Ii);
    320318                                DdNode * const tmp = And(Ik, Ii); // do we need to simplify this to identify subsets?
    321319
     
    367365            }
    368366            if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) {
    369                 Cudd_RecursiveDeref(mManager, bdd);
     367                Cudd_RecursiveDeref(mManager, bdd);               
    370368                stmt = stmt->replaceWith(entry.createZeroes());
    371369            }
    372             else {
    373                 mCharacterizationMap[expr] = bdd;
     370            else {               
     371                mCharacterizationMap[stmt] = bdd;
    374372                stmt = stmt->getNextNode();
    375373            }
     
    736734}
    737735
    738 //#define FAST_LOG2(x) ((sizeof(unsigned long) * 8 - 1) - ScanReverseIntrinsic((unsigned long)(x)))
    739 
    740 //#define FAST_CEIL_LOG2(x) (FAST_LOG_2(x) + ((x & (x - 1) != 0) ? 1 : 0))
     736
     737static inline size_t smallest_multiplexed_set(const size_t x) {
     738    return std::log2<size_t>(x) + 1; // use a faster builtin function for this?
     739}
     740
    741741
    742742/** ------------------------------------------------------------------------------------------------------------- *
     
    744744 ** ------------------------------------------------------------------------------------------------------------- */
    745745void AutoMultiplexing::multiplexSelectedIndependentSets() const {
     746
     747    const unsigned f = num_vertices(mConstraintGraph);
     748    const unsigned l = num_vertices(mMultiplexSetGraph);
     749
     750    // Preallocate the structures based on the size of the largest multiplex set
     751    size_t max_n = 3;
     752    for (unsigned s = f; s != l; ++s) {
     753        max_n = std::max<unsigned>(max_n, out_degree(s, mMultiplexSetGraph));
     754    }
     755    const size_t max_m = smallest_multiplexed_set(max_n);
     756
     757    std::vector<MultiplexSetGraph::vertex_descriptor> I(max_n);
     758    std::vector<Advance *> V(max_n);
     759    std::vector<PabloAST *> muxed(max_m);
     760    circular_buffer<PabloAST *> Q(max_n);
    746761
    747762    // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set
    748763    // relationships of our independent sets.
    749764
    750     for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMultiplexSetGraph); s != e; ++s) {
    751         const unsigned n = out_degree(s, mMultiplexSetGraph);
     765    for (unsigned s = f; s != l; ++s) {
     766        const size_t n = out_degree(s, mMultiplexSetGraph);
    752767        if (n) {
    753768
    754             const unsigned m = static_cast<unsigned>(std::ceil(std::log2(n))); // use a faster builtin function for this.
    755 
    756             std::vector<MultiplexSetGraph::vertex_descriptor> I;
    757             I.reserve(n);
    758 
    759             //raw_os_ostream out(std::cerr);
    760 
    761             //out << "n=" << n << ",m=" << m << "\nM={";
     769            const size_t m = smallest_multiplexed_set(n);
    762770
    763771            graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;
    764772            std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph);
    765773            for (unsigned i = 0; i != n; ++ei, ++i) {
    766                 I.push_back(target(*ei, mMultiplexSetGraph));
     774                I[i] = target(*ei, mMultiplexSetGraph);
    767775                assert (I[i] < mAdvance.size());
    768776            }
    769777            std::sort(I.begin(), I.begin() + n);
    770778
    771             std::vector<Advance *> V;
    772             V.reserve(n);
    773779            for (unsigned i = 0; i != n; ++i) {
    774                 V.push_back(mAdvance[I[i]]);
    775                 //if (i) out << ',';
    776                 //out << V[i]->getName()->to_string();
    777             }
    778            // out << "}\n\n";
     780                V[i] = mAdvance[I[i]];
     781            }
    779782
    780783            PabloBlock * const pb = V[0]->getParent();
     
    790793            #endif
    791794
    792             std::vector<PabloAST *> O; O.reserve(m);
    793 
    794795            /// Perform n-to-m Multiplexing
    795             for (unsigned j = 0; j != m; ++j) {
    796 
    797                 std::queue<PabloAST *> D;
    798 
    799                 for (unsigned i = 1; i != n; ++i) {
    800                     if ((i & (1 << j)) != 0) {
    801                         D.push(V[i - 1]->getOperand(0));
    802                     }
    803                 }
     796            for (size_t j = 0; j != m; ++j) {
     797
     798                assert (Q.empty());
     799
     800                std::stringstream name;
     801
     802                name << "mux";
     803
     804                for (size_t i = 1; i <= n; ++i) {
     805                    if ((i & (static_cast<size_t>(1) << j)) != 0) {
     806                        assert (!Q.full());
     807                        PabloAST * tmp = V[i - 1]->getOperand(0); assert (tmp);
     808                        Q.push_back(tmp);
     809                        name << "_" << V[i - 1]->getName()->to_string();
     810                    }
     811                }
     812
     813                assert (Q.size() >= 1);
     814
    804815                Advance * const adv = V[j];
    805816                // TODO: figure out a way to determine whether we're creating a duplicate value below.
    806817                // The expression map findOrCall ought to work conceptually but the functors method
    807818                // doesn't really work anymore with the current API.
    808                 while (D.size() > 1) {
    809                     PabloAST * a1 = D.front(); D.pop();
    810                     PabloAST * a2 = D.front(); D.pop();
     819                while (Q.size() > 1) {
     820                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
     821                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
     822                    assert (!Q.full());
    811823                    pb->setInsertPoint(choose(a2, a1, adv));
    812                     D.push(pb->createOr(a1, a2));
    813                 }
    814                 assert (D.size() == 1);
    815 
    816                 PabloAST * mux = D.front(); D.pop();
    817                 #ifdef PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS
    818                 mux = pb->createAssign("mux", mux);
    819                 #endif
    820                 O.push_back(pb->createAdvance(mux, adv->getOperand(1)));
    821             }
     824                    PabloAST * tmp = pb->createOr(a1, a2); assert (tmp);
     825                    Q.push_back(tmp);
     826                }
     827                assert (Q.size() == 1);
     828
     829                PabloAST * mux = Q.front(); Q.pop_front(); assert (mux);
     830                muxed[j] = pb->createAdvance(mux, adv->getOperand(1), name.str());
     831            }
     832
    822833
    823834            /// Perform m-to-n Demultiplexing
    824835            // Now construct the demuxed values and replaces all the users of the original advances with them.
    825             for (unsigned i = 1; i <= n; ++i) {
    826 
    827                 std::queue<PabloAST *> T;
    828                 std::queue<PabloAST *> F;
     836            for (size_t i = 1; i <= n; ++i) {
    829837
    830838                Advance * const adv = V[i - 1];
    831839
    832                 assert (T.size() == 0 && F.size() == 0);
    833 
     840                assert (Q.empty());
     841                for (size_t j = 0; j != m; ++j) {
     842                    if ((i & (static_cast<size_t>(1) << j)) == 0) {
     843                        Q.push_back(muxed[j]);
     844                    }
     845                }
     846
     847                assert (Q.size() <= m);
     848                PabloAST * neg = nullptr;
     849                if (LLVM_LIKELY(Q.size() > 0)) {
     850                    while (Q.size() > 1) {
     851                        PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
     852                        PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
     853                        pb->setInsertPoint(choose(a2, a1, adv));
     854                        assert (!Q.full());
     855                        PabloAST * tmp = pb->createOr(a1, a2); assert (tmp);
     856                        Q.push_back(tmp);
     857                    }
     858                    assert (Q.size() == 1);
     859                    neg = pb->createNot(Q.front()); Q.pop_front(); assert (neg);
     860                }
     861
     862                assert (Q.empty());
    834863                for (unsigned j = 0; j != m; ++j) {
    835                     if ((i & (1 << j)) != 0) {
    836                         T.push(O[j]);
    837                     }
    838                     else {
    839                         F.push(O[j]);
    840                     }
    841                 }
    842 
    843                 // out << "i=" << i << ": |T|=" << T.size() << ",|F|=" << F.size() << "\n";
    844 
    845                 assert (T.size() > 0);
    846 
    847                 while (T.size() > 1) {
    848                     PabloAST * a1 = T.front(); T.pop();
    849                     PabloAST * a2 = T.front(); T.pop();
    850                     pb->setInsertPoint(choose(a2, a1, adv));
    851                     T.push(pb->createAnd(a1, a2));
    852                 }
    853 
    854                 assert (T.size() == 1);
    855 
    856                 PabloAST * demux = T.front(); T.pop();
    857 
    858                 if (LLVM_LIKELY(F.size() > 0)) {
    859                     while (F.size() > 1) {
    860                         PabloAST * a1 = F.front(); F.pop();
    861                         PabloAST * a2 = F.front(); F.pop();
    862                         pb->setInsertPoint(choose(a2, a1, adv));
    863                         F.push(pb->createOr(a1, a2));
    864                     }
    865                     assert (F.size() == 1);
    866                     PabloAST * const neg = F.front(); F.pop();
    867                     demux = pb->createAnd(demux, pb->createNot(neg));
    868                 }
    869                 #ifdef PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS
    870                 demux = pb->createAssign("demux", demux);
    871                 #endif
     864                    if ((i & (static_cast<unsigned>(1) << j)) != 0) {
     865                        assert (!Q.full());
     866                        Q.push_back(muxed[j]);
     867                    }
     868                }
     869
     870                assert (Q.size() <= m);
     871                assert (Q.size() >= 1);
     872
     873                while (Q.size() > (1 + ((neg == nullptr) ? 1 : 0))) {
     874                    PabloAST * a1 = Q.front(); Q.pop_front(); assert (a1);
     875                    PabloAST * a2 = Q.front(); Q.pop_front(); assert (a2);
     876
     877                    assert (!Q.full());
     878                    PabloAST * tmp = pb->createAnd(a1, a2); assert (tmp);
     879                    Q.push_back(tmp);
     880                }
     881
     882                PabloAST * a1 = Q.front(); Q.pop_front(); assert (demux);
     883                PabloAST * a2 = neg;
     884                if (LLVM_UNLIKELY(Q.size() == 2)) {
     885                    a2 = Q.front(); Q.pop_front(); assert (a2);
     886                }
     887                pb->setInsertPoint(choose(a2, a1, adv));
     888                PabloAST * demux = pb->createAnd(a1, a2, "demux_" + V[i - 1]->getName()->to_string());
     889
    872890                V[i - 1]->replaceWith(demux, false, true);
    873891            }
  • icGREP/icgrep-devel/icgrep/pablo/pablo_compiler.cpp

    r4586 r4587  
    10121012    const unsigned advanceEntries = cd.longAdvanceEntries(shift_amount);
    10131013    const unsigned bufsize = cd.longAdvanceBufferSize(shift_amount);
    1014     std::cerr << "shift_amount = " << shift_amount << " bufsize = " << bufsize << std::endl;
     1014
    10151015    Value * indexMask = b.getInt64(bufsize - 1);  // A mask to implement circular buffer indexing
    10161016    Value * advBaseIndex = b.getInt64(cd.longAdvanceCarryDataOffset(localIndex));
Note: See TracChangeset for help on using the changeset viewer.