Changeset 4571
 Timestamp:
 May 22, 2015, 5:09:26 PM (4 years ago)
 Location:
 icGREP/icgrepdevel/icgrep/pablo
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/analysis/bdd/bdd.hpp
r4569 r4571 111 111 } 112 112 113 inline int operator==(const bool term) const { 114 return term ? isFalse() : isTrue(); 113 inline BDD & operator=(const bool term) const { 114 mRoot = term ? 0 : 1; 115 return *this; 115 116 } 116 117 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.cpp
r4570 r4571 23 23 Engine eng = am.initialize(vars, block); 24 24 am.characterize(eng, block); 25 am.createMappingGraph(); 25 26 RNG rng(std::random_device()()); 26 27 am.generateMultiplexSets(rng); 27 28 am.approxMaxWeightIndependentSet(); 29 am.applySubsetConstraints(); 28 30 am.multiplexSelectedIndependentSets(); 29 31 } … … 194 196 std::stack<const Statement *> scope; 195 197 196 197 198 198 unsigned variables = 0; 199 199 200 200 // Scan through and collect all the advances, calls, scanthrus and matchstars ... 201 201 for (const Statement * stmt = entry.front(); ; ) { 202 for (; stmt; stmt = stmt>getNextNode()) {202 while ( stmt ) { 203 203 204 204 if (LLVM_UNLIKELY(isa<If>(stmt)  isa<While>(stmt))) { … … 234 234 case PabloAST::ClassTypeId::And: 235 235 bdd = engine.applyAnd(input[0], input[1]); 236 if (LLVM_UNLIKELY(engine.satOne(bdd).isFalse())) {237 bdd = BDD::Contradiction();238 // Look into making a "replaceAllUsesWithZero" method that can recursively apply239 // the implication of having a Zero output.240 stmt>replaceAllUsesWith(entry.createZeroes());241 stmt>eraseFromParent(true);242 }243 236 break; 244 237 case PabloAST::ClassTypeId::Or: … … 257 250 case PabloAST::ClassTypeId::ScanThru: 258 251 // It may be possible use "engine.applyNot(input[1])" for ScanThrus if we rule out the 259 // possibility of a contradition being calculated later. An example of this would be 260 // Â¬(ScanThru(c,m) âš m) but are there others that would be harder to predict? 252 // possibility of a contradition being erroneously calculated later. An example of this 253 // would be Â¬(ScanThru(c,m) âš m) but are there others that would be harder to predict? 254 case PabloAST::ClassTypeId::MatchStar: 255 if (LLVM_UNLIKELY(input[0] == false  input[1] == false)) { 256 bdd = false; 257 break; 258 } 261 259 case PabloAST::ClassTypeId::Call: 262 case PabloAST::ClassTypeId::MatchStar:263 260 bdd = engine.var(variables++); 264 261 break; 265 case PabloAST::ClassTypeId::Advance: { 262 case PabloAST::ClassTypeId::Advance: 263 if (LLVM_UNLIKELY(input[0] == false)) { 264 bdd = false; 265 } 266 else { 267 266 268 const BDD var = engine.var(variables++); 267 269 268 270 bdd = var; 269 271 270 // when we built the path graph, we constructed it in the same order; hense the row/column of272 // When we built the path graph, we constructed it in the same order; hense the row/column of 271 273 // the path graph is equivalent to the index. 272 274 … … 313 315 break; 314 316 } 315 mCharacterizationMap.insert(std::make_pair(stmt, bdd)); 317 if (LLVM_UNLIKELY(engine.satOne(bdd) == false)) { 318 stmt = stmt>replaceWith(entry.createZeroes()); 319 } 320 else { 321 mCharacterizationMap.insert(std::make_pair(stmt, bdd)); 322 stmt = stmt>getNextNode(); 323 } 316 324 } 317 325 … … 322 330 scope.pop(); 323 331 } 332 } 333 334 /**  * 335 * @brief createMappingGraph 336 **  */ 337 void AutoMultiplexing::createMappingGraph() { 338 mMappingGraph = MappingGraph(num_vertices(mConstraintGraph)); 324 339 } 325 340 … … 345 360 D[*vi] = d; 346 361 if (d == 0) { 347 S. insert(*vi);362 S.push_back(*vi); 348 363 } 349 364 } 350 365 351 366 for ( ; remainingVerticies >= 3; remainingVerticies) { 352 if (S.size() > 2) {367 if (S.size() >= 3) { 353 368 addMultiplexSet(S); 354 } 369 } 355 370 // Randomly choose a vertex in S and discard it. 371 assert (!S.empty()); 356 372 const auto i = S.begin() + RNGDistribution(0, S.size()  1)(rng); 357 373 const Vertex u = *i; … … 361 377 const Vertex v = target(*ei, mConstraintGraph); 362 378 if ((D[v]) == 0) { 363 S.insert(v); 364 } 365 } 366 } 379 S.push_back(v); 380 } 381 } 382 } 383 367 384 } 368 385 … … 371 388 * @param set an independent set 372 389 **  */ 373 void AutoMultiplexing::addMultiplexSet(const IndependentSet & set) { 374 375 376 } 377 378 379 AutoMultiplexing::AutoMultiplexing() 380 { 381 382 } 383 384 385 } 390 inline void AutoMultiplexing::addMultiplexSet(const IndependentSet & set) { 391 392 // 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 395 const auto v = add_vertex(mMappingGraph); 396 for (auto u : set) { 397 add_edge(u, v, mMappingGraph); 398 } 399 } 400 401 /**  * 402 * @brief approxMaxWeightIndependentSet 403 **  */ 404 void AutoMultiplexing::approxMaxWeightIndependentSet(RNG & rng) { 405 406 // Compute our independent set graph from our mapping graph; effectively it's the graph resulting 407 // from contracting one advance node edge with an adjacent vertex 408 409 const unsigned m = num_vertices(mConstraintGraph); 410 const unsigned n = num_vertices(mMappingGraph)  m; 411 412 IndependentSetGraph G(n); 413 414 // Record the "weight" of this independent set vertex 415 for (IndependentSetGraph::vertex_descriptor i = 0; i != n; ++i) { 416 G[i] = in_degree(m + i, mMappingGraph); 417 } 418 // Add in any edges based on the adjacencies in the mapping graph 419 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); 422 for (; ei != ei_end; ++ei) { 423 for (auto ej = ei; ej != ei; ++ej) { 424 add_edge(*ei  m, *ej  m, G); 425 } 426 } 427 } 428 // Process the graph using the greedy method of "Approximation Algorithms for the Weighted Independent Set Problem" (2005) 429 std::vector<IndependentSetGraph::vertex_descriptor> S; 430 std::vector<bool> removed(n, false); 431 for (;;) { 432 // Select the miminum weight vertex 433 graph_traits<IndependentSetGraph>::vertex_iterator vi, vi_end; 434 std::tie(vi, vi_end) = vertices(G); 435 unsigned W = std::numeric_limits<unsigned>::max(); 436 for (; vi != vi_end; ++vi) { 437 if (removed[*vi]) { 438 continue; 439 } 440 const unsigned w = G[*vi]; 441 if (w <= W) { 442 if (w < W) { 443 W = w; 444 S.clear(); 445 } 446 S.push_back(*vi); 447 } 448 } 449 if (S.empty()) { 450 break; 451 } 452 453 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 455 graph_traits<IndependentSetGraph>::adjacency_iterator ai, ai_end; 456 std::tie(ai, ai_end) = adjacent_vertices(u, G); 457 for (; ai != ai_end; ++ai) { 458 removed[*ai] = true; 459 clear_in_edges(m + *ai, mMappingGraph); 460 } 461 removed[u] = true; 462 } 463 } 464 465 /**  * 466 * @brief applySubsetConstraints 467 **  */ 468 void AutoMultiplexing::applySubsetConstraints() { 469 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 473 graph_traits<SubsetGraph>::edge_iterator ei, ei_end; 474 for (std::tie(ei, ei_end) = edges(mSubsetGraph); ei != ei_end; ++ei) { 475 const auto u = source(*ei, mSubsetGraph); 476 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) { 482 add_edge(u, v, mMappingGraph); 483 } 484 } 485 } 486 487 } 488 489 490 /**  * 491 * @brief multiplexSelectedIndependentSets 492 **  */ 493 void AutoMultiplexing::multiplexSelectedIndependentSets() { 494 495 496 497 } 498 499 } 
icGREP/icgrepdevel/icgrep/pablo/optimizers/pablo_automultiplexing.hpp
r4570 r4571 22 22 using PathGraph = boost::adjacency_matrix<boost::undirectedS>; 23 23 using SubsetGraph = boost::edge_list<std::pair<unsigned, unsigned>>; 24 using MappingGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::bidirectionalS>; 25 using IndependentSetGraph = boost::adjacency_list<boost::hash_setS, boost::vecS, boost::undirectedS, unsigned>; 24 26 using IndexMap = boost::container::flat_map<PabloAST *, unsigned>; 25 27 … … 29 31 using Vertex = ConstraintGraph::vertex_descriptor; 30 32 31 using IndependentSet = boost::container::flat_set<Vector>;33 using IndependentSet = std::vector<Vertex>; 32 34 33 35 public: … … 38 40 void generateMultiplexSets(RNG & rng); 39 41 void addMultiplexSet(const IndependentSet & set); 40 void approxMaxWeightIndependentSet(); 42 void approxMaxWeightIndependentSet(RNG & rng); 43 void applySubsetConstraints(); 41 44 void multiplexSelectedIndependentSets(); 42 45 … … 49 52 SubsetGraph mSubsetGraph; 50 53 IndexMap mIndexMap; 51 54 MappingGraph mMappingGraph; 52 55 }; 53 56
Note: See TracChangeset
for help on using the changeset viewer.