 Timestamp:
 Jun 2, 2015, 11:43:13 AM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4585 r4586 9 9 #include <unordered_set> 10 10 #include <boost/container/flat_set.hpp> 11 #include <unordered_map> 11 12 #include <boost/numeric/ublas/matrix.hpp> 12 13 #include <include/simdlib/builtins.hpp> … … 72 73 } 73 74 75 assert ("Run the Simplifer pass prior to this!" && (stmt>getNumUses() != 0  (isa<Assign>(stmt) ? !cast<Assign>(stmt)>superfluous() : false))); 76 74 77 switch (stmt>getClassTypeId()) { 75 case PabloAST::ClassTypeId::Advance: 78 case PabloAST::ClassTypeId::Advance: 76 79 mAdvance.push_back(const_cast<Advance*>(cast<Advance>(stmt))); 77 80 map.emplace(stmt, m++); … … 300 303 301 304 assert (mCharacterizationMap.count(stmt)); 302 DdNode * Ik = input[0];303 DdNode * Vk = bdd = mCharacterizationMap[stmt];305 DdNode * const Ik = input[0]; 306 DdNode * const Vk = bdd = mCharacterizationMap[stmt]; 304 307 const unsigned k = advances.size(); 305 308 … … 315 318 if ((stmt>getOperand(1) == adv>getOperand(1)) && (!edge(k, i, mPathGraph).second)) { 316 319 317 DdNode * tmp = And(Ik, Ii); // do we need to simplify this to identify subsets? 318 320 DdNode * const tmp = And(Ik, Ii); // do we need to simplify this to identify subsets? 321 322 if (Ik == tmp) { 323 // If Ik = C and C = Ii â© Ik then Ik (the input to the kth advance) is a *subset* of Ii (the input of the 324 // ith advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the 325 // multiplex set graph if Advance_i and Advance_k happen to be in the same mutually exclusive set. 326 mSubsetGraph.emplace_back(k, i); 327 constrained = false; 328 } 329 else if (Ii == tmp) { 330 mSubsetGraph.emplace_back(i, k); 331 constrained = false; 332 } 319 333 // Is there any satisfying truth assignment? If not, these streams are mutually exclusive. 320 if (noSatisfyingAssignment(tmp)) {334 else if (noSatisfyingAssignment(tmp)) { 321 335 322 336 assert (mCharacterizationMap.count(adv)); … … 326 340 bdd = And(bdd, Not(Vi)); 327 341 other = And(other, Not(Vk)); 328 // If these advances are not from the same scope, we cannot safely multiplex them even if 329 // they're mutually exclusive. 330 constrained = (stmt>getParent() != adv>getParent()); 331 } 332 else { // Test whether one of the inputs to these advances are a subset of the other 333 if (LLVM_UNLIKELY(Ik == tmp)) { 334 // If Ik = C and C = Ii â© Ik then Ik (the input to the kth advance) is a *subset* of Ii (the input of the 335 // ith advance). Record this in the subset graph with the arc (k,i). These edges will be moved into the 336 // multiplex set graph if Advance_i and Advance_k happen to be in the same mutually exclusive set. 337 mSubsetGraph.emplace_back(k, i); 338 constrained = false; 339 } 340 else if (LLVM_UNLIKELY(Ii == tmp)) { 341 mSubsetGraph.emplace_back(i, k); 342 constrained = false; 343 } 342 constrained = false; 344 343 } 345 344 … … 347 346 } 348 347 349 if (constrained) { 348 // Advances must be in the same scope or they cannot be safely multiplexed unless one is moved. 349 if (constrained  (stmt>getParent() != adv>getParent())) { 350 350 // We want the constraint graph to be acyclic; since the dependencies are already in topological order, 351 351 // adding an arc from a lesser to greater numbered vertex won't induce a cycle. … … 357 357 // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to 358 358 // eliminate the need for looking it up again. 359 advances.emplace_back( input[0], Vk);359 advances.emplace_back(Ik, Vk); 360 360 testContradiction = false; 361 361 } … … 421 421 422 422 inline bool AutoMultiplexing::noSatisfyingAssignment(DdNode * x) { 423 // TODO: since we're only interested in knowing whether there is no such cube, 424 // write an optimized function for that if one does not exist. 423 425 int* cube; 424 426 CUDD_VALUE_TYPE dummy; 425 return Cudd_IsGenEmpty(Cudd_FirstCube(mManager, x, &cube, &dummy)); 427 auto gen = Cudd_FirstCube(mManager, x, &cube, &dummy); 428 bool r = Cudd_IsGenEmpty(gen); 429 Cudd_GenFree(gen); 430 return r; 426 431 } 427 432 … … 429 434 Cudd_Quit(mManager); 430 435 } 431 432 436 433 437 /**  * … … 483 487 } 484 488 485 // raw_os_ostream out(std::cerr);486 487 // out << "\n\ndigraph G {\n";488 489 // const unsigned m = num_vertices(mConstraintGraph);490 // const unsigned n = num_vertices(mMultiplexSetGraph);491 492 // for (unsigned i = 0; i != m; ++i) {493 // out << "v" << i << " [shape=box,label=\"" << mAdvance[i]>getName()>to_string() << "\"];\n";494 // }495 // for (unsigned i = m; i != n; ++i) {496 // out << "v" << i << " [shape=circle];\n";497 // }498 499 // for (unsigned i = m; i != n; ++i) {500 // graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end;501 // for (std::tie(ei, ei_end) = out_edges(i, mMultiplexSetGraph); ei != ei_end; ++ei) {502 // out << "v" << i << " > v" << target(*ei, mMultiplexSetGraph) << ";\n";503 // }504 // }505 506 // out << "}\n\n";507 508 489 return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph); 509 490 } … … 511 492 /**  * 512 493 * @brief addMultiplexSet 513 * @param setan independent set494 * @param S an independent set 514 495 **  */ 515 496 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & S) { … … 519 500 520 501 // Question: should we enumerate the power set of S? 502 521 503 const auto v = add_vertex(mMultiplexSetGraph); 522 504 for (auto u : S) { 523 505 add_edge(v, u, mMultiplexSetGraph); 524 506 } 507 525 508 } 526 509 527 510 /**  * 528 511 * @brief approxMaxWeightIndependentSet 512 * @param RNG random number generator 529 513 **  */ 530 514 void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) { … … 538 522 IndependentSetGraph G(n); 539 523 540 for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) { 541 G[i] = out_degree(i + m, mMultiplexSetGraph); 524 std::unordered_map<MultiplexSetGraph::vertex_descriptor, IndependentSetGraph::vertex_descriptor> M; 525 MultiplexSetGraph::vertex_descriptor i = m; 526 graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end; 527 for (std::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi, ++i) { 528 M.emplace(i, *vi); 529 G[*vi] = std::make_pair(out_degree(i, mMultiplexSetGraph), i); 542 530 } 543 531 … … 547 535 // I.e., make all vertices in G adjacent if their corresponding sets intersect. 548 536 549 for ( unsignedi = 0; i != m; ++i) {537 for (i = 0; i != m; ++i) { 550 538 if (in_degree(i, mMultiplexSetGraph) > 1) { 551 539 graph_traits<MultiplexSetGraph>::in_edge_iterator ei_begin, ei_end; … … 554 542 for (auto ej = ei_begin; ej != ei; ++ej) { 555 543 // Note: ei and ej are incoming edges. The source is the set vertex, 556 // which must have a id >= m. 557 add_edge(source(*ei, mMultiplexSetGraph)  m, source(*ej, mMultiplexSetGraph)  m, G); 558 } 559 } 560 } 561 } 562 563 // Process the graph using the greedy method of "Approximation Algorithms for the Weighted Independent Set Problem" (2005) 544 add_edge(M[source(*ei, mMultiplexSetGraph)], M[source(*ej, mMultiplexSetGraph)], G); 545 } 546 } 547 } 548 } 549 550 // Using WMIN from "A note on greedy algorithms for the maximum weighted independent set problem" 564 551 // (Note: look into minimum independent dominating set algorithms. It fits better with the ceil log2 + subset cost model.) 565 std::vector<IndependentSetGraph::vertex_descriptor> S; 566 std::vector<bool> removed(n, false); 567 for (;;) { 568 // Let S be the set of verticies of miminal weight 569 graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end; 570 std::tie(vi, vi_end) = vertices(G); 571 unsigned W = std::numeric_limits<unsigned>::max(); 572 for (; vi != vi_end; ++vi) { 573 if (removed[*vi]) { 574 continue; 575 } 576 const unsigned w = G[*vi]; 577 if (w <= W) { 578 if (w < W) { 579 W = w; 580 S.clear(); 581 } 582 S.push_back(*vi); 583 } 584 } 585 586 if (S.empty()) { 587 break; 588 } 589 // Select u from S 590 const auto i = S.begin() + RNGDistribution(0, S.size()  1)(rng); 591 const auto u = *i; 592 S.erase(i); 593 // Remove u and its adjacencies from G; clear the adjacent set vertices from the multiplex set graph. This will effectively 594 // choose the set refered to by u as one of our chosen independent sets and discard any other sets that contain one 595 // of the vertices in the chosen set. 552 553 std::vector<IndependentSetGraph::vertex_descriptor> A; 554 555 while (num_vertices(G) > 0) { 556 557 // Select a vertex vi whose weight as greater than the average weight of its neighbours ... 558 559 auto i = RNGDistribution(0, num_vertices(G)  1)(rng); 560 for (std::tie(vi, vi_end) = vertices(G); i && vi != vi_end; ++vi, i); 561 562 const unsigned Vw = G[*vi].first * (degree(*vi, G) + 1); 563 564 unsigned Nw = 0; 596 565 graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end; 597 std::tie(ai, ai_end) = adjacent_vertices( u, G);566 std::tie(ai, ai_end) = adjacent_vertices(*vi, G); 598 567 for (; ai != ai_end; ++ai) { 599 removed[*ai] = true; 600 clear_out_edges(m + *ai, mMultiplexSetGraph); 601 } 602 removed[u] = true; 603 } 568 Nw += G[*ai].first; 569 } 570 571 // Then add it to our set and remove it and its neighbourhood from G 572 573 if (Nw <= Vw) { 574 A.reserve(degree(*vi, G) + 1); 575 // Note: by clearing the adjacent set vertices from the multiplex set graph, this will effectively 576 // choose the set refered to by vi as one of our chosen independent sets. 577 graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end; 578 A.push_back(*vi); 579 for (std::tie(ai, ai_end) = adjacent_vertices(*vi, G); ai != ai_end; ++ai) { 580 clear_out_edges(G[*ai].second, mMultiplexSetGraph); 581 A.push_back(*ai); 582 } 583 for (auto u : A) { 584 clear_vertex(u, G); 585 remove_vertex(u, G); 586 } 587 A.clear(); 588 } 589 590 591 } 592 593 #ifndef NDEBUG 594 for (unsigned i = 0; i != m; ++i) { 595 assert (in_degree(i, mMultiplexSetGraph) <= 1); 596 } 597 for (unsigned i = m; i != (m + n); ++i) { 598 assert (out_degree(i, mMultiplexSetGraph) == 0  out_degree(i, mMultiplexSetGraph) >= 3); 599 } 600 #endif 601 } 602 603 /**  * 604 * @brief choose 605 **  */ 606 607 inline Statement * choose(PabloAST * x, PabloAST * y, Statement * z) { 608 return isa<Statement>(x) ? cast<Statement>(x) : (isa<Statement>(y) ? cast<Statement>(y) : z); 604 609 } 605 610 … … 709 714 PabloAST * a1 = Q.front(); Q.pop(); 710 715 PabloAST * a2 = Q.front(); Q.pop(); 711 pb>setInsertPoint(c ast<Statement>(a2));716 pb>setInsertPoint(choose(a2, a1, adv)); 712 717 Q.push(pb>createOr(a1, a2)); 713 718 } … … 743 748 // relationships of our independent sets. 744 749 745 unsigned N = 3;746 for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMultiplexSetGraph); s != e; ++s) {747 N = std::max<unsigned>(N, out_degree(s, mMultiplexSetGraph));748 }749 750 std::vector<MultiplexSetGraph::vertex_descriptor> V(N);751 std::queue<PabloAST *> T;752 std::queue<PabloAST *> F;753 std::vector<SmallVector<PabloAST *, 4>> users(N);754 755 750 for (unsigned s = num_vertices(mConstraintGraph), e = num_vertices(mMultiplexSetGraph); s != e; ++s) { 756 751 const unsigned n = out_degree(s, mMultiplexSetGraph); … … 759 754 const unsigned m = static_cast<unsigned>(std::ceil(std::log2(n))); // use a faster builtin function for this. 760 755 761 assert (n < (1 << m)); 762 763 graph_traits<MultiplexSetGraph>::out_edge_iterator ei_begin, ei_end; 764 std::tie(ei_begin, ei_end) = out_edges(s, mMultiplexSetGraph); 765 for (auto ei = ei_begin; ei != ei_end; ++ei) { 766 V[std::distance(ei_begin, ei)] = target(*ei, mMultiplexSetGraph); 767 } 768 std::sort(V.begin(), V.begin() + n); 769 770 // raw_os_ostream out(std::cerr); 771 772 // out << "M={"; 773 // for (auto i = 0; i != n; ++i) { 774 // out << ' ' << mAdvance[V[i]]>getName()>to_string() << " (" << (ptrdiff_t)(mAdvance[V[i]]>getParent()) << ")"; 775 // } 776 // out << "}\n\n"; 777 778 PabloBlock * const pb = mAdvance[V[0]]>getParent(); 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={"; 762 763 graph_traits<MultiplexSetGraph>::out_edge_iterator ei, ei_end; 764 std::tie(ei, ei_end) = out_edges(s, mMultiplexSetGraph); 765 for (unsigned i = 0; i != n; ++ei, ++i) { 766 I.push_back(target(*ei, mMultiplexSetGraph)); 767 assert (I[i] < mAdvance.size()); 768 } 769 std::sort(I.begin(), I.begin() + n); 770 771 std::vector<Advance *> V; 772 V.reserve(n); 773 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"; 779 780 PabloBlock * const pb = V[0]>getParent(); 779 781 assert (pb); 780 782 781 783 // Sanity test to make sure every advance is in the same scope. 782 784 #ifndef NDEBUG 783 for ( autoi = 1; i != n; ++i) {784 assert ( V[i  1] < V[i]);785 assert (V[i ] < mAdvance.size());786 assert ( mAdvance[V[i]]>getParent() == pb);785 for (unsigned i = 1; i != n; ++i) { 786 assert (I[i  1] < I[i]); 787 assert (V[i  1] != V[i]); 788 assert (V[i]>getParent() == pb); 787 789 } 788 790 #endif 789 791 790 // Store the original users of our advances; we'll be modifying these extensively shortly. 791 for (unsigned i = 0; i != n; ++i) { 792 const Advance * const adv = mAdvance[V[i]]; 793 assert (users[i].empty()); 794 users[i].insert(users[i].begin(), adv>user_begin(), adv>user_end()) ; 795 } 792 std::vector<PabloAST *> O; O.reserve(m); 796 793 797 794 /// Perform ntom Multiplexing 798 795 for (unsigned j = 0; j != m; ++j) { 799 for (unsigned i = 1; i != (1 << m); ++i) { 796 797 std::queue<PabloAST *> D; 798 799 for (unsigned i = 1; i != n; ++i) { 800 800 if ((i & (1 << j)) != 0) { 801 T.push(mAdvance[V[i  1]]>getOperand(0));802 } 803 } 804 Advance * const adv = mAdvance[V[j]];801 D.push(V[i  1]>getOperand(0)); 802 } 803 } 804 Advance * const adv = V[j]; 805 805 // TODO: figure out a way to determine whether we're creating a duplicate value below. 806 806 // The expression map findOrCall ought to work conceptually but the functors method 807 807 // 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(); 811 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 } 822 823 /// Perform mton Demultiplexing 824 // 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; 829 830 Advance * const adv = V[i  1]; 831 832 assert (T.size() == 0 && F.size() == 0); 833 834 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 808 847 while (T.size() > 1) { 809 848 PabloAST * a1 = T.front(); T.pop(); 810 849 PabloAST * a2 = T.front(); T.pop(); 811 pb>setInsertPoint(cast<Statement>(a2)); 812 T.push(pb>createOr(a1, a2)); 813 } 814 assert (T.size() == 1); 815 816 PabloAST * mux = T.front(); T.pop(); 817 #ifdef PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS 818 mux = pb>createAssign("mux", mux); 819 #endif 820 821 adv>setOperand(0, mux); 822 } 823 824 /// Perform mton Demultiplexing 825 // Now construct the demuxed values and replaces all the users of the original advances with them. 826 for (unsigned i = 1; i <= n; ++i) { 827 828 assert (T.size() == 0 && F.size() == 0); 829 830 for (unsigned j = 0; j != m; ++j) { 831 if ((i & (1 << j)) != 0) { 832 T.push(mAdvance[V[j]]); 833 } 834 else { 835 F.push(mAdvance[V[j]]); 836 } 837 } 838 839 assert (T.size() > 0); 840 841 while (T.size() > 1) { 842 PabloAST * a1 = T.front(); T.pop(); 843 PabloAST * a2 = T.front(); T.pop(); 844 pb>setInsertPoint(cast<Statement>(a2)); 850 pb>setInsertPoint(choose(a2, a1, adv)); 845 851 T.push(pb>createAnd(a1, a2)); 846 852 } … … 852 858 if (LLVM_LIKELY(F.size() > 0)) { 853 859 while (F.size() > 1) { 854 PabloAST * a1 = T.front(); T.pop();855 PabloAST * a2 = T.front(); T.pop();856 pb>setInsertPoint(c ast<Statement>(a2));860 PabloAST * a1 = F.front(); F.pop(); 861 PabloAST * a2 = F.front(); F.pop(); 862 pb>setInsertPoint(choose(a2, a1, adv)); 857 863 F.push(pb>createOr(a1, a2)); 858 864 } 859 865 assert (F.size() == 1); 860 demux = pb>createAnd(demux, pb>createNot(F.front())); F.pop();861 }862 866 PabloAST * const neg = F.front(); F.pop(); 867 demux = pb>createAnd(demux, pb>createNot(neg)); 868 } 863 869 #ifdef PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS 864 870 demux = pb>createAssign("demux", demux); 865 871 #endif 866 867 Advance * const adv = mAdvance[V[i  1]]; 868 for (PabloAST * use : users[i  1]) { 869 cast<Statement>(use)>replaceUsesOfWith(adv, demux); 870 } 871 } 872 873 /// Clean up the unneeded advances ... 874 for (unsigned i = m; i != n; ++i) { 875 mAdvance[V[i]]>eraseFromParent(true); 876 } 877 for (unsigned i = 0; i != n; ++i) { 878 users[i].clear(); 879 } 880 872 V[i  1]>replaceWith(demux, false, true); 873 } 881 874 } 882 875 } … … 945 938 } 946 939 947 948 940 } // end of namespace pablo 949 941
Note: See TracChangeset
for help on using the changeset viewer.