- Timestamp:
- Dec 2, 2015, 4:22:23 PM (3 years ago)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
icGREP/icgrep-devel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4885 r4888 20 20 using namespace boost::numeric::ublas; 21 21 22 //#define PRINT_DEBUG_OUTPUT22 #define PRINT_DEBUG_OUTPUT 23 23 24 24 #if !defined(NDEBUG) && !defined(PRINT_DEBUG_OUTPUT) … … 101 101 using TypeId = PabloAST::ClassTypeId; 102 102 103 bool AutoMultiplexing::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const bool independent) {103 bool MultiplexingPass::optimize(PabloFunction & function, const unsigned limit, const unsigned maxSelections, const unsigned windowSize, const bool independent) { 104 104 105 105 // std::random_device rd; … … 110 110 LOG("Seed: " << seed); 111 111 112 AutoMultiplexing am(limit, maxSelections);112 MultiplexingPass mp(limit, maxSelections, windowSize); 113 113 RECORD_TIMESTAMP(start_initialize); 114 const unsigned advances = am.initialize(function, independent);114 const unsigned advances = mp.initialize(function, independent); 115 115 RECORD_TIMESTAMP(end_initialize); 116 116 … … 124 124 125 125 RECORD_TIMESTAMP(start_characterize); 126 am.characterize(function.getEntryBlock());126 mp.characterize(function.getEntryBlock()); 127 127 RECORD_TIMESTAMP(end_characterize); 128 128 … … 137 137 138 138 RECORD_TIMESTAMP(start_create_multiplex_graph); 139 const bool multiplex = am.generateCandidateSets(rng);139 const bool multiplex = mp.generateCandidateSets(rng); 140 140 RECORD_TIMESTAMP(end_create_multiplex_graph); 141 141 LOG("GenerateCandidateSets: " << (end_create_multiplex_graph - start_create_multiplex_graph)); … … 144 144 145 145 RECORD_TIMESTAMP(start_select_multiplex_sets); 146 am.selectMultiplexSets(rng);146 mp.selectMultiplexSets(rng); 147 147 RECORD_TIMESTAMP(end_select_multiplex_sets); 148 148 LOG("SelectMultiplexSets: " << (end_select_multiplex_sets - start_select_multiplex_sets)); 149 149 150 150 RECORD_TIMESTAMP(start_subset_constraints); 151 am.applySubsetConstraints();151 mp.eliminateSubsetConstraints(); 152 152 RECORD_TIMESTAMP(end_subset_constraints); 153 153 LOG("ApplySubsetConstraints: " << (end_subset_constraints - start_subset_constraints)); 154 154 155 155 RECORD_TIMESTAMP(start_select_independent_sets); 156 am.multiplexSelectedIndependentSets(function);156 mp.multiplexSelectedIndependentSets(function); 157 157 RECORD_TIMESTAMP(end_select_independent_sets); 158 158 LOG("SelectedIndependentSets: " << (end_select_independent_sets - start_select_independent_sets)); 159 159 160 AutoMultiplexing::topologicalSort(function);160 MultiplexingPass::topologicalSort(function); 161 161 #ifndef NDEBUG 162 162 PabloVerifier::verify(function, "post-multiplexing"); … … 176 176 * the proper variable ordering. 177 177 ** ------------------------------------------------------------------------------------------------------------- */ 178 unsigned AutoMultiplexing::initialize(PabloFunction & function, const bool independent) { 179 180 flat_map<const PabloAST *, unsigned> map; 178 unsigned MultiplexingPass::initialize(PabloFunction & function, const bool independent) { 179 181 180 std::stack<Statement *> scope; 182 181 unsigned variableCount = 0; // number of statements that cannot always be categorized without generating a new variable … … 184 183 // Scan through and collect all the advances, calls, scanthrus and matchstars ... 185 184 unsigned statements = 0, advances = 0; 186 mResolvedScopes.emplace(function.getEntryBlock(), nullptr);187 185 for (Statement * stmt = function.getEntryBlock()->front(); ; ) { 188 186 while ( stmt ) { 189 187 ++statements; 190 188 if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { 191 // Set the next statement to be the first statement of the inner scope and push the192 // next statement of the current statement into the scope stack.193 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody();194 mResolvedScopes.emplace(nested, stmt);195 189 scope.push(stmt->getNextNode()); 190 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(); 196 191 stmt = nested->front(); 197 192 assert (stmt); 198 193 continue; 199 194 } 200 201 assert ("Run the Simplifer pass prior to this!" && (stmt->getNumUses() > 0));202 203 195 switch (stmt->getClassTypeId()) { 204 196 case TypeId::Advance: … … 226 218 } 227 219 228 // Create the transitive closure matrix of graph. From this we'll construct 229 // two graphs restricted to the relationships between advances. The first will 230 // be a path graph, which is used to bypass testing for mutual exclusivity of 231 // advances that cannot be multiplexed. The second is a transitive reduction 232 // of that graph, which forms the basis of our constraint graph when deciding 233 // which advances ought to be multiplexed. 234 235 matrix<bool> G(statements, advances, false); 236 for (unsigned i = 0; i != advances; ++i) { 237 G(i, i) = true; 238 } 239 240 unsigned n = advances; 241 unsigned m = 0; 242 243 for (const Statement * stmt = function.getEntryBlock()->front();;) { 244 while ( stmt ) { 245 246 unsigned u = 0; 247 if (isa<Advance>(stmt)) { 248 u = m++; 249 } else { 250 u = n++; 251 } 252 map.emplace(stmt, u); 253 254 for (unsigned i = 0; i != stmt->getNumOperands(); ++i) { 255 const PabloAST * const op = stmt->getOperand(i); 256 if (LLVM_LIKELY(isa<Statement>(op))) { 257 const unsigned v = map[op]; 258 for (unsigned w = 0; w != m; ++w) { 259 G(u, w) |= G(v, w); 260 } 261 } 262 } 263 if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { 264 // Set the next statement to be the first statement of the inner scope 265 // and push the next statement of the current statement into the stack. 266 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(); 267 scope.push(stmt->getNextNode()); 268 stmt = nested->front(); 269 assert (stmt); 270 continue; 271 } 272 stmt = stmt->getNextNode(); 273 } 274 if (scope.empty()) { 275 break; 276 } 277 stmt = scope.top(); 278 scope.pop(); 279 } 280 281 // Can I use the data in the matrix to indicate whether an Advance is dependent on a particular instruction and only 282 // for which there is still a use left of it? 283 284 // Record the path / base constraint graph after removing any reflexive-loops. 285 // Since G is a use-def graph and we want our constraint graph to be a def-use graph, 286 // reverse the edges as we're writing them to obtain the transposed graph. 287 288 mConstraintGraph = ConstraintGraph(advances); 220 initializeBaseConstraintGraph(function.getEntryBlock(), statements, advances); 221 289 222 mSubsetGraph = SubsetGraph(advances); 290 223 291 for (unsigned i = 0; i != advances; ++i) { 292 G(i, i) = false; 293 for (unsigned j = 0; j != advances; ++j) { 294 if (G(i, j)) { 295 add_edge(j, i, mConstraintGraph); 296 } 297 } 298 } 224 initializeAdvanceDepth(function.getEntryBlock(), advances); 299 225 300 226 // Initialize the BDD engine ... … … 334 260 335 261 /** ------------------------------------------------------------------------------------------------------------- * 262 * @brief initializeBaseConstraintGraph 263 ** ------------------------------------------------------------------------------------------------------------- */ 264 inline void MultiplexingPass::initializeBaseConstraintGraph(PabloBlock * const block, const unsigned statements, const unsigned advances) { 265 266 std::stack<Statement *> scope; 267 flat_map<const PabloAST *, unsigned> M; 268 M.reserve(statements); 269 matrix<bool> G(statements, advances, false); 270 for (unsigned i = 0; i != advances; ++i) { 271 G(i, i) = true; 272 } 273 274 unsigned n = advances; 275 unsigned k = 0; 276 for (const Statement * stmt = block->front();;) { 277 while ( stmt ) { 278 unsigned u = 0; 279 if (LLVM_UNLIKELY(isa<Advance>(stmt))) { 280 u = k++; 281 } else { 282 u = n++; 283 } 284 M.emplace(stmt, u); 285 for (unsigned i = 0; i != stmt->getNumOperands(); ++i) { 286 const PabloAST * const op = stmt->getOperand(i); 287 if (LLVM_LIKELY(isa<Statement>(op))) { 288 const unsigned v = M[op]; 289 for (unsigned w = 0; w != k; ++w) { 290 G(u, w) |= G(v, w); 291 } 292 } 293 } 294 if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { 295 scope.push(stmt->getNextNode()); 296 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(); 297 stmt = nested->front(); 298 assert (stmt); 299 continue; 300 } 301 stmt = stmt->getNextNode(); 302 } 303 if (scope.empty()) { 304 break; 305 } 306 stmt = scope.top(); 307 scope.pop(); 308 } 309 310 assert (k == advances); 311 312 // Compute the base constraint graph as the union of TRANSPOSE(G) without any reflective loops and the set of edges 313 // marking which advances are in differing scope blocks. 314 315 mConstraintGraph = ConstraintGraph(advances); 316 for (unsigned i = 0; i != advances; ++i) { 317 for (unsigned j = 0; j < i; ++j) { 318 if (G(i, j)) { 319 add_edge(j, i, mConstraintGraph); 320 } 321 } 322 for (unsigned j = i + 1; j < advances; ++j) { 323 if (G(i, j)) { 324 add_edge(j, i, mConstraintGraph); 325 } 326 } 327 } 328 329 } 330 331 /** ------------------------------------------------------------------------------------------------------------- * 332 * @brief initializeAdvanceDepth 333 ** ------------------------------------------------------------------------------------------------------------- */ 334 inline void MultiplexingPass::initializeAdvanceDepth(PabloBlock * const block, const unsigned advances) { 335 336 std::stack<Statement *> scope; 337 unsigned k = 0; 338 int maxDepth = 0; 339 const Advance * advance[advances]; 340 mAdvanceDepth.resize(advances, 0); 341 for (Statement * stmt = block->front(); ; ) { 342 while ( stmt ) { 343 if (LLVM_UNLIKELY(isa<If>(stmt) || isa<While>(stmt))) { 344 scope.push(stmt->getNextNode()); 345 const PabloBlock * const nested = isa<If>(stmt) ? cast<If>(stmt)->getBody() : cast<While>(stmt)->getBody(); 346 stmt = nested->front(); 347 assert (stmt); 348 continue; 349 } else if (LLVM_UNLIKELY(isa<Advance>(stmt))) { 350 int depth = 0; 351 advance[k] = cast<Advance>(stmt); 352 for (unsigned i = 0; i != k; ++i) { 353 if (edge(i, k, mConstraintGraph).second || (advance[i]->getParent() != advance[k]->getParent())) { 354 depth = std::max<int>(depth, mAdvanceDepth[i]); 355 } 356 } 357 mAdvanceDepth[k++] = ++depth; 358 maxDepth = std::max(maxDepth, depth); 359 } 360 stmt = stmt->getNextNode(); 361 } 362 if (scope.empty()) { 363 break; 364 } 365 stmt = scope.top(); 366 scope.pop(); 367 } 368 assert (k == advances); 369 370 LOG("Window Size / Max Depth: " << mWindowSize << " of " << maxDepth); 371 } 372 373 /** ------------------------------------------------------------------------------------------------------------- * 336 374 * @brief characterize 337 375 * @param vars the input vars for this program … … 339 377 * Scan through the program and iteratively compute the BDDs for each statement. 340 378 ** ------------------------------------------------------------------------------------------------------------- */ 341 void AutoMultiplexing::characterize(PabloBlock * const block) {379 void MultiplexingPass::characterize(PabloBlock * const block) { 342 380 for (Statement * stmt : *block) { 343 381 if (LLVM_UNLIKELY(isa<If>(stmt))) { … … 374 412 * @brief characterize 375 413 ** ------------------------------------------------------------------------------------------------------------- */ 376 inline BDD AutoMultiplexing::characterize(Statement * const stmt) {414 inline BDD MultiplexingPass::characterize(Statement * const stmt) { 377 415 BDD bdd = get(stmt->getOperand(0)); 378 416 switch (stmt->getClassTypeId()) { … … 402 440 break; 403 441 case TypeId::ScanThru: 404 // ScanThru(c, m) := (c + m) ⧠¬m. We can conservatively represent this statement using the BDD for ¬m --- provided405 // no derivative of this statement is negated in any fashion.442 // ScanThru(c, m) := (c + m) ⧠¬m. Thus we can conservatively represent this statement using the BDD 443 // for ¬m --- provided no derivative of this statement is negated in any fashion. 406 444 case TypeId::MatchStar: 407 445 case TypeId::Call: … … 418 456 * @brief characterize 419 457 ** ------------------------------------------------------------------------------------------------------------- */ 420 inline BDD AutoMultiplexing::characterize(Advance * const adv, const BDD Ik) { 421 458 inline BDD MultiplexingPass::characterize(Advance * const adv, const BDD Ik) { 422 459 const auto k = mAdvanceAttributes.size(); 423 460 std::vector<bool> unconstrained(k , false); 424 425 461 for (unsigned i = 0; i != k; ++i) { 426 // Have we already proven that these are unconstrained by the subset relationships? 462 // Are we interested in testing these streams to see whether they are mutually exclusive? 463 if (exceedsWindowSize(i, k)) continue; 464 // Have we already proven that they are unconstrained by their subset relationship? 427 465 if (unconstrained[i]) continue; 428 429 // If these advances are "shifting" their values by the same amount ...466 // If these Advances are mutually exclusive, in the same scope, transitively independent, and shift their 467 // values by the same amount, we can safely multiplex them. Otherwise mark the constraint in the graph. 430 468 const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]); 431 if ( independent(i, k) && adv->getOperand(1) == ithAdv->getOperand(1)) {469 if ((mTestConstrainedAdvances || independent(i, k)) && (ithAdv->getOperand(1) == adv->getOperand(1))) { 432 470 const BDD Ii = get(ithAdv->getOperand(0)); 433 471 const BDD IiIk = bdd_addref(bdd_and(Ii, Ik)); … … 468 506 } 469 507 470 const BDD Vk = bdd_addref(bdd_not(bdd_ithvar(mVariables++)));471 BDD Ck = bdd_one();508 BDD Ck = bdd_ithvar(mVariables++); 509 const BDD Nk = bdd_addref(bdd_not(Ck)); 472 510 for (unsigned i = 0; i != k; ++i) { 473 const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]);474 BDD & Ci = get(ithAdv);475 const BDD Vi = std::get<1>(mAdvanceAttributes[i]);476 511 if (unconstrained[i]) { 477 const BDD exclusionConstraint = bdd_addref(bdd_or(Vi, Vk)); 478 Ci = bdd_addref(bdd_and(Ci, exclusionConstraint)); 479 Ck = bdd_addref(bdd_and(Ck, exclusionConstraint)); 480 // If these Advances are mutually exclusive, in the same scope and transitively independent, 481 // we can safely multiplex them. Otherwise mark the constraint edge in the graph. 482 if (adv->getParent() == ithAdv->getParent()) { 512 const Advance * const ithAdv = std::get<0>(mAdvanceAttributes[i]); 513 const BDD Ni = std::get<1>(mAdvanceAttributes[i]); 514 515 BDD & Ci = get(ithAdv); 516 Ci = bdd_addref(bdd_and(Ci, Nk)); 517 Ck = bdd_addref(bdd_and(Ck, Ni)); 518 if ((!mTestConstrainedAdvances || independent(i, k)) && (adv->getParent() == ithAdv->getParent())) { 483 519 continue; 484 520 } … … 486 522 add_edge(i, k, mConstraintGraph); 487 523 } 488 489 mAdvanceAttributes.emplace_back(adv, Vk); 490 524 mAdvanceAttributes.emplace_back(adv, Nk); 491 525 return Ck; 492 526 } … … 495 529 * @brief independent 496 530 ** ------------------------------------------------------------------------------------------------------------- */ 497 inline bool AutoMultiplexing::independent(const ConstraintVertex i, const ConstraintVertex j) const {531 inline bool MultiplexingPass::independent(const ConstraintVertex i, const ConstraintVertex j) const { 498 532 assert (i < num_vertices(mConstraintGraph) && j < num_vertices(mConstraintGraph)); 499 533 return (mConstraintGraph.get_edge(i, j) == 0); … … 501 535 502 536 /** ------------------------------------------------------------------------------------------------------------- * 537 * @brief exceedsWindowSize 538 ** ------------------------------------------------------------------------------------------------------------- */ 539 inline bool MultiplexingPass::exceedsWindowSize(const ConstraintVertex i, const ConstraintVertex j) const { 540 assert (i < mAdvanceDepth.size() && j < mAdvanceDepth.size()); 541 return (std::abs<int>(mAdvanceDepth[i] - mAdvanceDepth[j]) > mWindowSize); 542 } 543 544 /** ------------------------------------------------------------------------------------------------------------- * 503 545 * @brief generateMultiplexSets 504 546 * @param RNG random number generator 505 547 ** ------------------------------------------------------------------------------------------------------------- */ 506 bool AutoMultiplexing::generateCandidateSets(RNG & rng) {548 bool MultiplexingPass::generateCandidateSets(RNG & rng) { 507 549 508 550 using degree_t = graph_traits<ConstraintGraph>::degree_size_type; … … 601 643 * @param S an independent set 602 644 ** ------------------------------------------------------------------------------------------------------------- */ 603 inline void AutoMultiplexing::addCandidateSet(const VertexVector & S, RNG & rng) {645 inline void MultiplexingPass::addCandidateSet(const VertexVector & S, RNG & rng) { 604 646 if (S.size() >= 3) { 605 if (S.size() <= m Limit) {647 if (S.size() <= mMultiplexingSetSizeLimit) { 606 648 const auto u = add_vertex(mMultiplexSetGraph); 607 649 for (const auto v : S) { … … 609 651 } 610 652 } else { 611 const auto max = choose(S.size(), m Limit);612 unsigned element[m Limit];613 if (LLVM_UNLIKELY(max <= mMax Selections)) {653 const auto max = choose(S.size(), mMultiplexingSetSizeLimit); 654 unsigned element[mMultiplexingSetSizeLimit]; 655 if (LLVM_UNLIKELY(max <= mMaxMultiplexingSetSelections)) { 614 656 for (unsigned i = 0; i != max; ++i) { 615 select(S.size(), m Limit, i, element);657 select(S.size(), mMultiplexingSetSizeLimit, i, element); 616 658 const auto u = add_vertex(mMultiplexSetGraph); 617 for (unsigned j = 0; j != m Limit; ++j) {659 for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) { 618 660 add_edge(u, S[element[j]], mMultiplexSetGraph); 619 661 } 620 662 } 621 663 } else { // take m random samples 622 for (unsigned i = 0; i != mMax Selections; ++i) {623 select(S.size(), m Limit, rng() % max, element);664 for (unsigned i = 0; i != mMaxMultiplexingSetSelections; ++i) { 665 select(S.size(), mMultiplexingSetSizeLimit, rng() % max, element); 624 666 const auto u = add_vertex(mMultiplexSetGraph); 625 for (unsigned j = 0; j != m Limit; ++j) {667 for (unsigned j = 0; j != mMultiplexingSetSizeLimit; ++j) { 626 668 add_edge(u, S[element[j]], mMultiplexSetGraph); 627 669 } … … 656 698 * two, labelled A and B, are disjoint and the third larger set, C, that consists of elements of A and B. 657 699 ** ------------------------------------------------------------------------------------------------------------- */ 658 void AutoMultiplexing::selectMultiplexSets(RNG &) {700 void MultiplexingPass::selectMultiplexSets(RNG &) { 659 701 660 702 using InEdgeIterator = graph_traits<MultiplexSetGraph>::in_edge_iterator; … … 750 792 751 793 /** ------------------------------------------------------------------------------------------------------------- * 752 * @brief applySubsetConstraints753 ** ------------------------------------------------------------------------------------------------------------- */ 754 void AutoMultiplexing::applySubsetConstraints() {794 * @brief eliminateSubsetConstraints 795 ** ------------------------------------------------------------------------------------------------------------- */ 796 void MultiplexingPass::eliminateSubsetConstraints() { 755 797 756 798 using SubsetEdgeIterator = graph_traits<SubsetGraph>::edge_iterator; … … 801 843 * @brief multiplexSelectedIndependentSets 802 844 ** ------------------------------------------------------------------------------------------------------------- */ 803 void AutoMultiplexing::multiplexSelectedIndependentSets(PabloFunction &) {845 void MultiplexingPass::multiplexSelectedIndependentSets(PabloFunction &) { 804 846 805 847 const unsigned first_set = num_vertices(mConstraintGraph); … … 911 953 * it's not necessarily the original ordering. 912 954 ** ------------------------------------------------------------------------------------------------------------- */ 913 void AutoMultiplexing::topologicalSort(PabloFunction & function) {955 void MultiplexingPass::topologicalSort(PabloFunction & function) { 914 956 // Note: not a real topological sort. I expect the original order to be very close to the resulting one. 915 957 std::unordered_set<const PabloAST *> encountered; … … 955 997 * @brief doTransitiveReductionOfSubsetGraph 956 998 ** ------------------------------------------------------------------------------------------------------------- */ 957 void AutoMultiplexing::doTransitiveReductionOfSubsetGraph() {999 void MultiplexingPass::doTransitiveReductionOfSubsetGraph() { 958 1000 std::vector<SubsetGraph::vertex_descriptor> Q; 959 1001 for (auto u : make_iterator_range(vertices(mSubsetGraph))) { … … 986 1028 * @brief get 987 1029 ** ------------------------------------------------------------------------------------------------------------- */ 988 inline BDD & AutoMultiplexing::get(const PabloAST * const expr) { 1030 inline BDD & MultiplexingPass::get(const PabloAST * const expr) { 1031 assert (expr); 989 1032 auto f = mCharacterization.find(expr); 990 1033 assert (f != mCharacterization.end());
Note: See TracChangeset
for help on using the changeset viewer.