 Timestamp:
 May 31, 2015, 11:19:37 AM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4583 r4585 16 16 #include <cudd.h> 17 17 #include <util.h> 18 #include <fstream>19 18 20 19 using namespace llvm; … … 22 21 using namespace boost::container; 23 22 using namespace boost::numeric::ublas; 23 24 #define PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS 24 25 25 26 namespace pablo { … … 453 454 std::vector<DegreeType> D(remainingVerticies); 454 455 455 bool canMultiplex = false;456 457 456 VertexIterator vi, vi_end; 458 457 for (std::tie(vi, vi_end) = vertices(mConstraintGraph); vi != vi_end; ++vi) { … … 469 468 if (S.size() >= 3) { 470 469 addMultiplexSet(S); 471 canMultiplex = true;472 470 } 473 471 // Randomly choose a vertex in S and discard it. … … 485 483 } 486 484 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 511 return canMultiplex; 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 return num_vertices(mMultiplexSetGraph) > num_vertices(mConstraintGraph); 512 509 } 513 510 … … 536 533 // from contracting one advance node edge with an adjacent vertex 537 534 538 using Set = flat_set<IndependentSetGraph::vertex_descriptor>;539 535 const unsigned m = num_vertices(mConstraintGraph); 540 536 const unsigned n = num_vertices(mMultiplexSetGraph)  m; … … 542 538 IndependentSetGraph G(n); 543 539 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 ith set? (i.e., the outgoing edges of the ith 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 } 540 for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) { 541 G[i] = out_degree(i + m, mMultiplexSetGraph); 542 } 543 544 // Let M be mMultiplexSetGraph. Each vertex in G corresponds to a set vertex in M. 545 // If an advance vertex in M (i.e., one of the first m vertices of M) is adjacent 546 // to two or more set vertices, add an edge between the corresponding vertices in G. 547 // I.e., make all vertices in G adjacent if their corresponding sets intersect. 548 549 for (unsigned i = 0; i != m; ++i) { 550 if (in_degree(i, mMultiplexSetGraph) > 1) { 551 graph_traits<MultiplexSetGraph>::in_edge_iterator ei_begin, ei_end; 552 std::tie(ei_begin, ei_end) = in_edges(i, mMultiplexSetGraph); 553 for (auto ei = ei_begin; ei != ei_end; ++ei) { 554 for (auto ej = ei_begin; ej != ei; ++ej) { 555 // 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); 579 558 } 580 559 } … … 608 587 break; 609 588 } 610 // Select u from S 589 // Select u from S 611 590 const auto i = S.begin() + RNGDistribution(0, S.size()  1)(rng); 612 591 const auto u = *i; 613 592 S.erase(i); 614 615 593 // Remove u and its adjacencies from G; clear the adjacent set vertices from the multiplex set graph. This will effectively 616 594 // choose the set refered to by u as one of our chosen independent sets and discard any other sets that contain one … … 702 680 PabloBlock * pb = adv>getParent(); 703 681 704 #define CHOOSE(A,B,C) (isa<Statement>(A) ? cast<Statement>(A) : (isa<Statement>(B) ? cast<Statement>(B) : C))705 706 682 for (auto i : V) { 707 683 Q.push(mAdvance[i]>getOperand(0)); … … 710 686 PabloAST * a1 = Q.front(); Q.pop(); 711 687 PabloAST * a2 = Q.front(); Q.pop(); 712 pb>setInsertPoint( CHOOSE(a2, a1, adv));688 pb>setInsertPoint(cast<Statement>(a2)); 713 689 Q.push(pb>createOr(a1, a2)); 714 690 } … … 733 709 PabloAST * a1 = Q.front(); Q.pop(); 734 710 PabloAST * a2 = Q.front(); Q.pop(); 735 pb>setInsertPoint( CHOOSE(a2, a1, adv));711 pb>setInsertPoint(cast<Statement>(a2)); 736 712 Q.push(pb>createOr(a1, a2)); 737 713 } … … 762 738 * @brief multiplexSelectedIndependentSets 763 739 **  */ 764 void AutoMultiplexing::multiplexSelectedIndependentSets() {740 void AutoMultiplexing::multiplexSelectedIndependentSets() const { 765 741 766 742 // When entering thus function, the multiplex set graph M is a DAG with edges denoting the set … … 783 759 const unsigned m = static_cast<unsigned>(std::ceil(std::log2(n))); // use a faster builtin function for this. 784 760 761 assert (n < (1 << m)); 762 785 763 graph_traits<MultiplexSetGraph>::out_edge_iterator ei_begin, ei_end; 786 764 std::tie(ei_begin, ei_end) = out_edges(s, mMultiplexSetGraph); … … 790 768 std::sort(V.begin(), V.begin() + n); 791 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 792 778 PabloBlock * const pb = mAdvance[V[0]]>getParent(); 779 assert (pb); 780 793 781 // Sanity test to make sure every advance is in the same scope. 794 782 #ifndef NDEBUG 795 783 for (auto i = 1; i != n; ++i) { 784 assert (V[i  1] < V[i]); 785 assert (V[i] < mAdvance.size()); 796 786 assert (mAdvance[V[i]]>getParent() == pb); 797 787 } 798 788 #endif 789 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 } 799 796 800 797 /// Perform ntom Multiplexing 801 798 for (unsigned j = 0; j != m; ++j) { 802 for (unsigned i = 0; i != (1 << m); ++i) {803 if (( (i + 1)& (1 << j)) != 0) {804 T.push(mAdvance[V[i ]]>getOperand(0));799 for (unsigned i = 1; i != (1 << m); ++i) { 800 if ((i & (1 << j)) != 0) { 801 T.push(mAdvance[V[i  1]]>getOperand(0)); 805 802 } 806 803 } … … 812 809 PabloAST * a1 = T.front(); T.pop(); 813 810 PabloAST * a2 = T.front(); T.pop(); 814 pb>setInsertPoint( CHOOSE(a2, a1, adv));811 pb>setInsertPoint(cast<Statement>(a2)); 815 812 T.push(pb>createOr(a1, a2)); 816 813 } 817 adv>setOperand(0, T.front()); T.pop(); 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); 818 822 } 819 823 820 824 /// Perform mton Demultiplexing 821 // Store the original users of our advances; we'll be modifying these extensively shortly.822 for (unsigned i = 0; i != n; ++i) {823 const Advance * const adv = mAdvance[V[i]];824 users[i].insert(users[i].begin(), adv>user_begin(), adv>user_end()) ;825 }826 827 825 // Now construct the demuxed values and replaces all the users of the original advances with them. 828 for (unsigned i = 0; i != n; ++i) { 829 Advance * adv = mAdvance[V[i]]; 826 for (unsigned i = 1; i <= n; ++i) { 827 828 assert (T.size() == 0 && F.size() == 0); 829 830 830 for (unsigned j = 0; j != m; ++j) { 831 if (( (i + 1)& (1 << j)) != 0) {831 if ((i & (1 << j)) != 0) { 832 832 T.push(mAdvance[V[j]]); 833 833 } … … 836 836 } 837 837 } 838 839 assert (T.size() > 0); 840 838 841 while (T.size() > 1) { 839 842 PabloAST * a1 = T.front(); T.pop(); 840 843 PabloAST * a2 = T.front(); T.pop(); 841 pb>setInsertPoint( CHOOSE(a2, a1, adv));844 pb>setInsertPoint(cast<Statement>(a2)); 842 845 T.push(pb>createAnd(a1, a2)); 843 846 } 847 844 848 assert (T.size() == 1); 845 849 846 while (F.size() > 1) { 847 PabloAST * a1 = T.front(); T.pop(); 848 PabloAST * a2 = T.front(); T.pop(); 849 pb>setInsertPoint(CHOOSE(a2, a1, adv)); 850 F.push(pb>createOr(a1, a2)); 851 } 852 assert (F.size() == 1); 853 854 PabloAST * const demux = pb>createAnd(T.front(), pb>createNot(F.front()), "demux"); T.pop(); F.pop(); 855 for (PabloAST * use : users[i]) { 850 PabloAST * demux = T.front(); T.pop(); 851 852 if (LLVM_LIKELY(F.size() > 0)) { 853 while (F.size() > 1) { 854 PabloAST * a1 = T.front(); T.pop(); 855 PabloAST * a2 = T.front(); T.pop(); 856 pb>setInsertPoint(cast<Statement>(a2)); 857 F.push(pb>createOr(a1, a2)); 858 } 859 assert (F.size() == 1); 860 demux = pb>createAnd(demux, pb>createNot(F.front())); F.pop(); 861 } 862 863 #ifdef PROVIDE_ASSIGNMENT_STATEMENTS_FOR_MUX_AND_DEMUX_STATEMENTS 864 demux = pb>createAssign("demux", demux); 865 #endif 866 867 Advance * const adv = mAdvance[V[i  1]]; 868 for (PabloAST * use : users[i  1]) { 856 869 cast<Statement>(use)>replaceUsesOfWith(adv, demux); 857 870 } … … 881 894 void AutoMultiplexing::topologicalSort(PabloBlock & entry) const { 882 895 883 TopologicalSortGraph G; 884 TopologicalSortQueue Q; 885 TopologicalSortMap map; 886 896 // Note: not a real topological sort. I expect the original order to be very close to the resulting one. 897 898 std::unordered_set<PabloAST *> encountered; 887 899 std::stack<Statement *> scope; 888 889 Statement * ip = nullptr; 890 Statement * first; 891 Statement * stmt; 892 893 for (first = stmt = entry.front(); ; ) { 900 for (Statement * stmt = entry.front(); ; ) { 894 901 895 902 while ( stmt ) { 903 904 bool moved = false; 905 906 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) { 907 PabloAST * const op = stmt>getOperand(i); 908 if (LLVM_LIKELY(isa<Statement>(op))) { 909 if (LLVM_UNLIKELY(encountered.count(op) == 0)) { 910 Statement * next = stmt>getNextNode(); 911 stmt>insertAfter(cast<Statement>(op)); 912 stmt = next; 913 moved = true; 914 break; 915 } 916 } 917 } 918 919 if (moved) { 920 continue; 921 } 922 923 encountered.insert(stmt); 924 896 925 if (LLVM_UNLIKELY(isa<If>(stmt)  isa<While>(stmt))) { 897 // Sort the current "basic block"898 topologicalSort(G, Q, map, ip, first);899 926 // Set the next statement to be the first statement of the inner scope and push the 900 927 // next statement of the current statement into the scope stack. 901 928 const PabloBlock & nested = isa<If>(stmt) ? cast<If>(stmt)>getBody() : cast<While>(stmt)>getBody(); 902 scope.push(stmt); 903 ip = nullptr; 904 first = stmt = nested.front(); 929 scope.push(stmt>getNextNode()); 930 stmt = nested.front(); 905 931 assert (stmt); 906 932 continue; 907 933 } 908 934 909 const auto u = add_vertex(stmt, G);910 for (unsigned i = 0; i != stmt>getNumOperands(); ++i) {911 auto f = map.find(stmt>getOperand(i));912 if (f == map.end()) {913 continue;914 }915 add_edge(f>second, u, G);916 }917 if (in_degree(u, G) == 0) {918 Q.push(u);919 }920 map.emplace(stmt, u);921 935 stmt = stmt>getNextNode(); 922 936 } 923 937 924 topologicalSort(G, Q, map, ip, first);925 938 if (scope.empty()) { 926 939 break; 927 940 } 928 ip= scope.top();941 stmt = scope.top(); 929 942 scope.pop(); 930 first = stmt = ip>getNextNode(); 931 } 932 933 } 934 935 void AutoMultiplexing::topologicalSort(TopologicalSortGraph & G, TopologicalSortQueue & Q, TopologicalSortMap & M, Statement * ip, Statement * first) const { 936 Statement * stmt = first; 937 while (!Q.empty()) { 938 const auto u = Q.front(); Q.pop(); 939 graph_traits<TopologicalSortGraph>::out_edge_iterator ei, ei_end; 940 for (std::tie(ei, ei_end) = out_edges(u, G); ei != ei_end; ++ei) { 941 const auto v = target(*ei, G); 942 if (in_degree(v, G) == 1) { 943 Q.push(v); 944 } 945 } 946 Statement * next = G[u]; 947 if (stmt != next) { 948 if (LLVM_UNLIKELY(ip == nullptr)) { 949 next>insertBefore(first); 950 } 951 else { 952 next>insertAfter(ip); 953 } 954 } 955 ip = next; 956 } 957 G.clear(); 958 M.clear(); 959 } 943 } 944 945 } 946 960 947 961 948 } // end of namespace pablo
Note: See TracChangeset
for help on using the changeset viewer.