Changeset 4577 for icGREP/icgrepdevel/icgrep/pablo/optimizers
 Timestamp:
 May 24, 2015, 4:18:10 PM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo/optimizers
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4571 r4577 4 4 #include <llvm/ADT/DenseMap.h> 5 5 #include <llvm/ADT/DenseSet.h> 6 #include <llvm/ADT/BitVector.h> 6 7 #include <stack> 7 8 #include <queue> … … 10 11 #include <boost/container/flat_set.hpp> 11 12 #include <boost/numeric/ublas/matrix.hpp> 13 12 14 13 15 using namespace llvm; … … 67 69 switch (stmt>getClassTypeId()) { 68 70 case PabloAST::ClassTypeId::Advance: 69 m IndexMap.emplace(stmt, m);71 mAdvance.emplace(stmt, m); 70 72 map.emplace(stmt, ++m); 71 73 case PabloAST::ClassTypeId::Call: … … 105 107 if (isa<Advance>(stmt)) { 106 108 u = ++n; 107 assert (mIndexMap.count(stmt) != 0 && mIndexMap[stmt] == (u  1)); 109 mAdvance.push_back(cast<Advance>(stmt)); 110 assert (mAdvance.size() == n); 108 111 } 109 112 else { … … 195 198 std::vector<std::pair<Advance *, BDD>> advances; 196 199 std::stack<const Statement *> scope; 200 201 advances.reserve(mAdvance.size()); 197 202 198 203 unsigned variables = 0; … … 228 233 } 229 234 235 bool testContradiction = true; 236 230 237 switch (stmt>getClassTypeId()) { 231 238 case PabloAST::ClassTypeId::Assign: … … 258 265 } 259 266 case PabloAST::ClassTypeId::Call: 267 testContradiction = false; 260 268 bdd = engine.var(variables++); 261 269 break; … … 273 281 // the path graph is equivalent to the index. 274 282 283 const BDD A = input[0]; 275 284 const unsigned k = advances.size(); 276 285 277 assert ( mIndexMap.count(stmt) != 0 && mIndexMap[stmt] == k);286 assert (stmt == mAdvance[k  1]); 278 287 279 288 for (unsigned i = 0; i != k; ++i) { 280 289 281 290 Advance * adv; 282 BDD eq; 283 std::tie(adv, eq) = advances[i]; 291 BDD B; 292 std::tie(adv, B) = advances[i]; 293 294 bool mutuallyExclusive = false; 295 bool constrained = false; 284 296 285 297 // If these advances are "shifting" their values by the same amount and aren't transitively dependant ... 286 298 if ((stmt>getOperand(1) != adv>getOperand(1)) && !edge(k, i, mPathGraph).second) { 287 288 const BDD C = engine.applyAnd(input[0], eq); // do we need to simplify this to identify subsets? 299 const BDD C = engine.applyAnd(A, B); // do we need to simplify this to identify subsets? 289 300 // Is there any satisfying truth assignment? If not, these streams are mutually exclusive. 290 if (engine.satOne(C).isFalse()) { 291 auto f = mCharacterizationMap.find(adv); 292 // build up our BDD equation for the kth Advance 293 bdd = engine.applyAnd(bdd, engine.applyNot(f>second)); 294 // but only 295 f>second = engine.applyAnd(f>second, engine.applyNot(var)); 296 continue; 297 } 298 else if (LLVM_UNLIKELY(input[0] == C)) { 299 add_edge(k, i, mSubsetGraph); 300 continue; 301 } 302 else if (LLVM_UNLIKELY(eq == C)) { 303 add_edge(i, k, mSubsetGraph); 304 continue; 305 } 306 } 307 // We want the constraint graph to be acyclic; since the dependencies are already in topological order, 308 // adding an arc from a lesser to greater numbered vertex won't induce a cycle. 309 add_edge(i, k, mConstraintGraph); 310 // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to 311 // eliminate the need for looking it up again. 312 advances.emplace_back(cast<Advance>(stmt), input[0]); 301 mutuallyExclusive = (engine.satOne(C) == false); 302 303 constrained = !mutuallyExclusive  (stmt>getParent() != adv>getParent()) ; 304 } 305 306 if (mutuallyExclusive) { 307 auto f = mCharacterizationMap.find(adv); 308 // build up our BDD equation for the kth advance 309 bdd = engine.applyAnd(bdd, engine.applyNot(f>second)); 310 // but only mark the other advance as being mutually exclusive with the kth *variable* 311 f>second = engine.applyAnd(f>second, engine.applyNot(var)); 312 } 313 314 if (constrained) { 315 // We want the constraint graph to be acyclic; since the dependencies are already in topological order, 316 // adding an arc from a lesser to greater numbered vertex won't induce a cycle. 317 add_edge(i, k, mConstraintGraph); 318 } 319 else if (LLVM_UNLIKELY(A == C)) { 320 // If A = C and C = A â© B then A (the input to the kth advance) is a *subset* of B (the input 321 // of the ith advance). Record this in the subset graph with the arc (k,i). 322 add_edge(k, i, mSubsetGraph); 323 continue; 324 } 325 else if (LLVM_UNLIKELY(B == C)) { 326 add_edge(i, k, mSubsetGraph); 327 continue; 328 } 313 329 } 314 } 315 break; 316 } 317 if (LLVM_UNLIKELY(engine.satOne(bdd) == false)) { 330 331 // Append this advance to the list of known advances in this "basic block"; add on the input's BDD to 332 // eliminate the need for looking it up again. 333 advances.emplace_back(cast<Advance>(stmt), A); 334 335 testContradiction = false; 336 } 337 break; 338 } 339 if (LLVM_UNLIKELY(testContradiction && engine.satOne(bdd) == false)) { 318 340 stmt = stmt>replaceWith(entry.createZeroes()); 319 341 } … … 388 410 * @param set an independent set 389 411 **  */ 390 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & set) {412 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & S) { 391 413 392 414 // At this stage, the mapping graph is a directed bipartite graph that is used to show relationships between 393 // the advance vertices and a "set vertex" for each independent set we find from "generateMultiplexSets". 394 415 // the "set vertex" for each independent set and its members. We obtain these from "generateMultiplexSets". 416 417 // Question: should we enumerate the power set of S? 395 418 const auto v = add_vertex(mMappingGraph); 396 for (auto u : set) {397 add_edge( u, v, mMappingGraph);419 for (auto u : S) { 420 add_edge(v, u, mMappingGraph); 398 421 } 399 422 } … … 414 437 // Record the "weight" of this independent set vertex 415 438 for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) { 416 G[i] = in_degree(m + i, mMappingGraph);439 G[i] = out_degree(m + i, mMappingGraph); 417 440 } 418 441 // Add in any edges based on the adjacencies in the mapping graph 419 442 for (MappingGraph::vertex_descriptor i = 0; i != m; ++i) { 420 graph_traits<MappingGraph>:: out_edge_iterator ei, ei_end;421 std::tie(ei, ei_end) = out_edges(i, mMappingGraph);443 graph_traits<MappingGraph>::in_edge_iterator ei, ei_end; 444 std::tie(ei, ei_end) = in_edges(i, mMappingGraph); 422 445 for (; ei != ei_end; ++ei) { 423 446 for (auto ej = ei; ej != ei; ++ej) { … … 427 450 } 428 451 // Process the graph using the greedy method of "Approximation Algorithms for the Weighted Independent Set Problem" (2005) 452 // (Note: look into minimum independent dominating set algorithms. It fits better with the log2 + subset relationship cost model.) 429 453 std::vector<IndependentSetGraph::vertex_descriptor> S; 430 454 std::vector<bool> removed(n, false); 431 455 for (;;) { 432 // Select the miminum weight vertex456 // Let S be the set of verticies of miminal weight 433 457 graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end; 434 458 std::tie(vi, vi_end) = vertices(G); … … 450 474 break; 451 475 } 452 476 // Select u from S 453 477 const auto u = S[S.size() == 1 ? 0 : RNGDistribution(0, S.size()  1)(rng)]; 454 // Remove it and its adjacencies from G; clear the adjacent set vertices from the mapping graph 478 // Remove u and its adjacencies from G; clear the adjacent set vertices from the mapping graph. This will effectively 479 // choose the set refered to by u as one of our chosen independent sets and discard any other sets that contain one 480 // of the vertices in the chosen set. 455 481 graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end; 456 482 std::tie(ai, ai_end) = adjacent_vertices(u, G); 457 483 for (; ai != ai_end; ++ai) { 458 484 removed[*ai] = true; 459 clear_ in_edges(m + *ai, mMappingGraph);485 clear_out_edges(m + *ai, mMappingGraph); 460 486 } 461 487 removed[u] = true; … … 468 494 void AutoMultiplexing::applySubsetConstraints() { 469 495 470 // The mapping graph now contains edges denoting the set relationships of our independent sets. 471 // Add in any edges from our subset constraints to the Mapping Graph that are within the same set. 472 496 // When entering thus function, the mapping graph M is a bipartite DAG with edges denoting the set 497 // relationships of our independent sets. 498 const unsigned m = num_vertices(mConstraintGraph); 499 const unsigned n = num_vertices(mMappingGraph); 500 501 // Add in any edges from our subset constraints to M that are within the same set. 502 bool hasSubsetConstraint = false; 473 503 graph_traits<SubsetGraph>::edge_iterator ei, ei_end; 474 504 for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) { 475 505 const auto u = source(*ei, mSubsetGraph); 476 506 const auto v = target(*ei, mSubsetGraph); 477 graph_traits<MappingGraph>::out_edge_iterator ej, ej_end; 478 for (std::tie(ej, ej_end) = out_edges(u, mMappingGraph); ej != ej_end; ++ej) { 479 // If both the source and target of ei are adjacent to the same vertex, that vertex must be the 480 // "set vertex". Add the edge between the vertices. 481 if (edge(v, target(*ej, mMappingGraph)).second) { 507 graph_traits<MappingGraph>::in_edge_iterator ej, ej_end; 508 // If both the source and target of ei are adjacent to the same vertex, that vertex must be the 509 // "set vertex". Add the edge between the vertices. 510 for (std::tie(ej, ej_end) = in_edges(u, mMappingGraph); ej != ej_end; ++ej) { 511 auto w = target(*ej, mMappingGraph); 512 // Only check (v, w) if w is a "set vertex". 513 if (w >= (n  m) && edge(v, w).second) { 482 514 add_edge(u, v, mMappingGraph); 483 } 484 } 485 } 486 515 hasSubsetConstraint = true; 516 } 517 } 518 } 519 520 if (LLVM_UNLIKELY(hasSubsetConstraint)) { 521 // At this point, M is still a DAG but no longer bipartite. We're going to scan through the set vertices 522 // in M, and use a DFS to scan through M and eliminate any subset relationships in the AST. 523 // That way, "multiplexSelectedIndependentSets" only needs to consider muxing and demuxing of the streams. 524 525 std::vector<MappingGraph::vertex_descriptor> V; 526 std::stack<MappingGraph::vertex_descriptor> S; 527 std::queue<PabloAST *> Q; 528 BitVector D(n  m, 0); 529 530 for (auto i = m; i != n; ++i) { 531 graph_traits<MappingGraph>::out_edge_iterator ei, ei_end; 532 // For each member of a "set vertex" ... 533 std::tie(ei, ei_end) = out_edges(i, mMappingGraph); 534 for (; ei != ei_end; ++ei) { 535 const auto s = source(*ei, mMappingGraph); 536 if (out_degree(s, mMappingGraph) != 0) { 537 // First scan through the subgraph of vertices in M dominated by s and build up the set T, 538 // consisting of all sinks w.r.t. vertex s. 539 auto u = s; 540 for (;;) { 541 graph_traits<MappingGraph>::out_edge_iterator ej, ej_end; 542 for (std::tie(ej, ej_end) = out_edges(u, mMappingGraph); ej != ej_end; ++ej) { 543 auto v = target(*ej, mMappingGraph); 544 if (D.test(v)) { 545 continue; 546 } 547 D.set(v); 548 if (out_degree(v, mMappingGraph) == 0) { 549 V.push(v); 550 } 551 else { 552 S.push(v); 553 } 554 } 555 if (S.empty()) { 556 break; 557 } 558 u = S.top(); 559 S.pop(); 560 } 561 D.clear(); 562 // Now in order for these advances to be mutually exclusive, the input to A_s must be masked 563 // with the complement of each advance indicated by V. 564 565 Advance * adv = mAdvance[s]; 566 PabloBlock * pb = adv>getParent(); 567 568 for (auto i : V) { 569 Q.push(mAdvance[i]>getOperand(0)); 570 } 571 pb>setInsertPoint(adv>getPrevNode()); 572 while (Q.size() > 1) { 573 PabloAST * a1 = Q.front(); Q.pop(); 574 PabloAST * a2 = Q.front(); Q.pop(); 575 Q.push(pb>createOr(a1, a2)); 576 } 577 assert (Q.size() == 1); 578 579 PabloAST * const mask = pb>createNot(Q.front()); Q.pop(); 580 adv>setOperand(0, pb>createAnd(adv>getOperand(0), mask, "subset_in")); 581 582 // Similar to the above, we're going to OR together the result of each advance, 583 // including s. This will restore the advanced variable back to its original state. 584 585 // Gather the original users to this advance. We'll be manipulating it shortly. 586 Statement::Users U(adv>users()); 587 588 // Add s to V and sort the list; it'll be closer to being in topological order. 589 V.push_back(s); 590 std::sort(V.begin(), V.end()); 591 for (auto i : V) { 592 Q.push(mAdvance[i]); 593 } 594 while (Q.size() > 1) { 595 PabloAST * a1 = Q.front(); Q.pop(); 596 PabloAST * a2 = Q.front(); Q.pop(); 597 pb>setInsertPoint(cast<Statement>(a2)); 598 Q.push(pb>createOr(a1, a2)); 599 } 600 assert (Q.size() == 1); 601 PabloAST * const input = Q.front(); Q.pop(); 602 603 for (PabloAST * use : U) { 604 if (LLVM_LIKELY(isa<Statement>(use))) { 605 cast<Statement>(use)>replaceUsesOfWith(adv, input); 606 } 607 } 608 609 pb>setInsertPoint(pb>back()); 610 611 V.clear(); 612 613 } 614 } 615 } 616 } 487 617 } 488 618 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp
r4571 r4577 24 24 using MappingGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>; 25 25 using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS, unsigned>; 26 using IndexMap = boost::container::flat_map<PabloAST *, unsigned>;26 using Advances = std::vector<Advance *>; 27 27 28 28 using RNG = std::mt19937; … … 51 51 ConstraintGraph mConstraintGraph; 52 52 SubsetGraph mSubsetGraph; 53 IndexMap mIndexMap;53 Advances mAdvance; 54 54 MappingGraph mMappingGraph; 55 55 };
Note: See TracChangeset
for help on using the changeset viewer.