Changeset 4587 for icGREP/icgrepdevel/icgrep/pablo/optimizers
 Timestamp:
 Jun 2, 2015, 5:22:53 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4586 r4587 11 11 #include <unordered_map> 12 12 #include <boost/numeric/ublas/matrix.hpp> 13 #include <boost/circular_buffer.hpp> 13 14 #include <include/simdlib/builtins.hpp> 14 15 // #include <pablo/expression_map.hpp> … … 22 23 using namespace boost::container; 23 24 using namespace boost::numeric::ublas; 24 25 #define PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS26 25 27 26 namespace pablo { … … 247 246 } 248 247 249 PabloAST * expr = stmt;250 248 bool testContradiction = true; 251 249 … … 261 259 // an operand of a Statement. Instead it updates the Initial operand's value. 262 260 testContradiction = false; 263 expr = stmt>getOperand(0);264 261 case PabloAST::ClassTypeId::Or: 265 262 bdd = Or(input[0], input[1]); … … 318 315 if ((stmt>getOperand(1) == adv>getOperand(1)) && (!edge(k, i, mPathGraph).second)) { 319 316 317 // Test this with Cudd_bddIntersect(mManager, Ik, Ii); 320 318 DdNode * const tmp = And(Ik, Ii); // do we need to simplify this to identify subsets? 321 319 … … 367 365 } 368 366 if (LLVM_UNLIKELY(testContradiction && noSatisfyingAssignment(bdd))) { 369 Cudd_RecursiveDeref(mManager, bdd); 367 Cudd_RecursiveDeref(mManager, bdd); 370 368 stmt = stmt>replaceWith(entry.createZeroes()); 371 369 } 372 else { 373 mCharacterizationMap[ expr] = bdd;370 else { 371 mCharacterizationMap[stmt] = bdd; 374 372 stmt = stmt>getNextNode(); 375 373 } … … 736 734 } 737 735 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 737 static 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 741 741 742 742 /**  * … … 744 744 **  */ 745 745 void 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); 746 761 747 762 // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set 748 763 // relationships of our independent sets. 749 764 750 for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMultiplexSetGraph); s != e; ++s) {751 const unsignedn = out_degree(s, mMultiplexSetGraph);765 for (unsigned s = f; s != l; ++s) { 766 const size_t n = out_degree(s, mMultiplexSetGraph); 752 767 if (n) { 753 768 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); 762 770 763 771 graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end; 764 772 std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph); 765 773 for (unsigned i = 0; i != n; ++ei, ++i) { 766 I .push_back(target(*ei, mMultiplexSetGraph));774 I[i] = target(*ei, mMultiplexSetGraph); 767 775 assert (I[i] < mAdvance.size()); 768 776 } 769 777 std::sort(I.begin(), I.begin() + n); 770 778 771 std::vector<Advance *> V;772 V.reserve(n);773 779 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 } 779 782 780 783 PabloBlock * const pb = V[0]>getParent(); … … 790 793 #endif 791 794 792 std::vector<PabloAST *> O; O.reserve(m);793 794 795 /// Perform ntom 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 804 815 Advance * const adv = V[j]; 805 816 // TODO: figure out a way to determine whether we're creating a duplicate value below. 806 817 // The expression map findOrCall ought to work conceptually but the functors method 807 818 // 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()); 811 823 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 822 833 823 834 /// Perform mton Demultiplexing 824 835 // 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) { 829 837 830 838 Advance * const adv = V[i  1]; 831 839 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()); 834 863 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 872 890 V[i  1]>replaceWith(demux, false, true); 873 891 }
Note: See TracChangeset
for help on using the changeset viewer.