 Timestamp:
 Nov 24, 2015, 4:27:35 PM (4 years ago)
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

icGREP/icgrepdevel/icgrep/pablo/optimizers/distributivepass.cpp
r4878 r4880 2 2 3 3 #include <pablo/codegenstate.h> 4 #include <pablo/analysis/pabloverifier.hpp> 5 #include <pablo/optimizers/pablo_simplifier.hpp> 6 #include <boost/container/flat_set.hpp> 4 7 #include <boost/container/flat_map.hpp> 5 8 #include <boost/graph/adjacency_list.hpp> … … 10 13 namespace pablo { 11 14 12 using DistributionGraph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>;13 using DistributionMap = flat_map<PabloAST *, DistributionGraph::vertex_descriptor>;14 15 using VertexSet = std::vector<V ariadic *>;15 using Graph = adjacency_list<hash_setS, vecS, bidirectionalS, PabloAST *>; 16 using Vertex = Graph::vertex_descriptor; 17 using Map = flat_map<PabloAST *, Vertex>; 18 using VertexSet = std::vector<Vertex>; 16 19 using Biclique = std::pair<VertexSet, VertexSet>; 17 20 using BicliqueSet = std::vector<Biclique>; … … 24 27 * @brief getVertex 25 28 **  */ 26 static inline DistributionGraph::vertex_descriptor getVertex(const PabloAST * value, DistributionGraph & G, DistributionMap & M) {29 static inline Vertex getVertex(PabloAST * value, Graph & G, Map & M) { 27 30 const auto f = M.find(value); 28 31 if (f != M.end()) { … … 35 38 36 39 /**  * 37 * @brief enumerateBicliques40 * @brief generateDistributionGraph 38 41 * 39 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal 40 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in 41 * bipartition A and their adjacencies to be in B. 42 **  */ 43 template <class Graph> 44 static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) { 45 using IntersectionSets = std::set<VertexSet>; 46 47 IntersectionSets B1; 48 for (auto u : A) { 49 if (in_degree(u, G) > 0) { 50 VertexSet incomingAdjacencies; 51 incomingAdjacencies.reserve(in_degree(u, G)); 52 for (auto e : make_iterator_range(in_edges(u, G))) { 53 incomingAdjacencies.push_back(source(e, G)); 54 } 55 std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end()); 56 B1.insert(std::move(incomingAdjacencies)); 57 } 58 } 59 60 IntersectionSets B(B1); 61 62 IntersectionSets Bi; 63 64 VertexSet clique; 65 for (auto i = B1.begin(); i != B1.end(); ++i) { 66 for (auto j = i; ++j != B1.end(); ) { 67 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 68 if (clique.size() > 0) { 69 if (B.count(clique) == 0) { 70 Bi.insert(clique); 71 } 72 clique.clear(); 73 } 74 } 75 } 76 77 for (;;) { 78 if (Bi.empty()) { 79 break; 80 } 81 B.insert(Bi.begin(), Bi.end()); 82 IntersectionSets Bk; 83 for (auto i = B1.begin(); i != B1.end(); ++i) { 84 for (auto j = Bi.begin(); j != Bi.end(); ++j) { 85 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 86 if (clique.size() > 0) { 87 if (B.count(clique) == 0) { 88 Bk.insert(clique); 89 } 90 clique.clear(); 91 } 92 } 93 } 94 Bi.swap(Bk); 95 } 96 97 BicliqueSet cliques; 98 cliques.reserve(B.size()); 99 for (auto Bi = B.begin(); Bi != B.end(); ++Bi) { 100 VertexSet Ai(A); 101 for (const Vertex u : *Bi) { 102 VertexSet Aj; 103 Aj.reserve(out_degree(u, G)); 104 for (auto e : make_iterator_range(out_edges(u, G))) { 105 Aj.push_back(target(e, G)); 106 } 107 std::sort(Aj.begin(), Aj.end()); 108 VertexSet Ak; 109 Ak.reserve(std::min(Ai.size(), Aj.size())); 110 std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak)); 111 Ai.swap(Ak); 112 } 113 assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly 114 cliques.emplace_back(std::move(Ai), std::move(*Bi)); 115 } 116 return std::move(cliques); 42 * Generate a graph G describing the potential applications of the distributive law for the given block. 43 **  */ 44 VertexSet generateDistributionGraph(PabloBlock * block, Graph & G) { 45 Map M; 46 VertexSet distSet; 47 for (Statement * stmt : *block) { 48 if (isa<And>(stmt)  isa<Or>(stmt)) { 49 const TypeId outerTypeId = stmt>getClassTypeId(); 50 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And; 51 flat_set<PabloAST *> distributable; 52 for (PabloAST * const expr : *cast<Variadic>(stmt)) { 53 if (LLVM_UNLIKELY(expr>getClassTypeId() == innerTypeId)) { 54 bool safe = true; 55 for (PabloAST * const user : expr>users()) { 56 if (user>getClassTypeId() != outerTypeId) { 57 safe = false; 58 break; 59 } 60 } 61 if (safe) { 62 distributable.insert(expr); 63 } 64 } 65 } 66 if (LLVM_LIKELY(distributable.size() > 1)) { 67 flat_map<PabloAST *, bool> observedMoreThanOnce; 68 bool anyOpportunities = false; 69 for (const PabloAST * distOperation : distributable) { 70 for (PabloAST * const distVar : *cast<Variadic>(distOperation)) { 71 auto ob = observedMoreThanOnce.find(distVar); 72 if (ob == observedMoreThanOnce.end()) { 73 observedMoreThanOnce.emplace(distVar, false); 74 } else { 75 ob>second = true; 76 anyOpportunities = true; 77 } 78 } 79 } 80 if (anyOpportunities) { 81 for (const auto ob : observedMoreThanOnce) { 82 PabloAST * distVar = nullptr; 83 bool observedTwice = false; 84 std::tie(distVar, observedTwice) = ob; 85 if (observedTwice) { 86 const Vertex z = getVertex(stmt, G, M); 87 distSet.push_back(z); 88 for (PabloAST * const distOperation : distVar>users()) { 89 if (distributable.count(distOperation)) { 90 const Vertex y = getVertex(distOperation, G, M); 91 add_edge(getVertex(distVar, G, M), y, G); 92 add_edge(y, z, G); 93 } 94 } 95 } 96 } 97 } 98 } 99 } 100 } 101 return distSet; 117 102 } 118 103 … … 191 176 192 177 /**  * 178 * @brief enumerateBicliques 179 * 180 * Adaptation of the MICA algorithm as described in "Consensus algorithms for the generation of all maximal 181 * bicliques" by Alexe et. al. (2003). Note: this implementation considers all verticies in set A to be in 182 * bipartition A and their adjacencies to be in B. 183 **  */ 184 static BicliqueSet enumerateBicliques(const Graph & G, const VertexSet & A) { 185 using IntersectionSets = std::set<VertexSet>; 186 187 IntersectionSets B1; 188 for (auto u : A) { 189 if (in_degree(u, G) > 0) { 190 VertexSet incomingAdjacencies; 191 incomingAdjacencies.reserve(in_degree(u, G)); 192 for (auto e : make_iterator_range(in_edges(u, G))) { 193 incomingAdjacencies.push_back(source(e, G)); 194 } 195 std::sort(incomingAdjacencies.begin(), incomingAdjacencies.end()); 196 B1.insert(std::move(incomingAdjacencies)); 197 } 198 } 199 200 IntersectionSets B(B1); 201 202 IntersectionSets Bi; 203 204 VertexSet clique; 205 for (auto i = B1.begin(); i != B1.end(); ++i) { 206 for (auto j = i; ++j != B1.end(); ) { 207 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 208 if (clique.size() > 0) { 209 if (B.count(clique) == 0) { 210 Bi.insert(clique); 211 } 212 clique.clear(); 213 } 214 } 215 } 216 217 for (;;) { 218 if (Bi.empty()) { 219 break; 220 } 221 B.insert(Bi.begin(), Bi.end()); 222 IntersectionSets Bk; 223 for (auto i = B1.begin(); i != B1.end(); ++i) { 224 for (auto j = Bi.begin(); j != Bi.end(); ++j) { 225 std::set_intersection(i>begin(), i>end(), j>begin(), j>end(), std::back_inserter(clique)); 226 if (clique.size() > 0) { 227 if (B.count(clique) == 0) { 228 Bk.insert(clique); 229 } 230 clique.clear(); 231 } 232 } 233 } 234 Bi.swap(Bk); 235 } 236 237 BicliqueSet cliques; 238 cliques.reserve(B.size()); 239 for (auto Bi = B.begin(); Bi != B.end(); ++Bi) { 240 VertexSet Ai(A); 241 for (const Vertex u : *Bi) { 242 VertexSet Aj; 243 Aj.reserve(out_degree(u, G)); 244 for (auto e : make_iterator_range(out_edges(u, G))) { 245 Aj.push_back(target(e, G)); 246 } 247 std::sort(Aj.begin(), Aj.end()); 248 VertexSet Ak; 249 Ak.reserve(std::min(Ai.size(), Aj.size())); 250 std::set_intersection(Ai.begin(), Ai.end(), Aj.begin(), Aj.end(), std::back_inserter(Ak)); 251 Ai.swap(Ak); 252 } 253 assert (Ai.size() > 0); // cannot happen if this algorithm is working correctly 254 cliques.emplace_back(std::move(Ai), std::move(*Bi)); 255 } 256 return std::move(cliques); 257 } 258 259 /**  * 193 260 * @brief removeUnhelpfulBicliques 194 261 * … … 197 264 * there are not enough vertices in the biclique to make distribution profitable, eliminate the clique. 198 265 **  */ 199 static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, DistributionGraph & G) {266 static BicliqueSet && removeUnhelpfulBicliques(BicliqueSet && cliques, Graph & G) { 200 267 for (auto ci = cliques.begin(); ci != cliques.end(); ) { 201 268 const auto cardinalityA = std::get<0>(*ci).size(); … … 220 287 * @brief safeDistributionSets 221 288 **  */ 222 static DistributionSets safeDistributionSets(DistributionGraph & G) { 223 224 VertexSet sinks; 225 for (const auto u : make_iterator_range(vertices(G))) { 226 if (out_degree(u, G) == 0 && in_degree(u, G) != 0) { 227 sinks.push_back(u); 228 } 229 } 230 289 static DistributionSets safeDistributionSets(Graph & G, const VertexSet & distSet) { 231 290 DistributionSets T; 232 BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(G, sinks), G), 1);291 BicliqueSet lowerSet = independentCliqueSets<1>(removeUnhelpfulBicliques(enumerateBicliques(G, distSet), G), 1); 233 292 for (Biclique & lower : lowerSet) { 234 293 BicliqueSet upperSet = independentCliqueSets<0>(enumerateBicliques(G, std::get<1>(lower)), 2); … … 241 300 242 301 /**  * 243 * @brief generateDistributionGraph 244 * 245 * Generate a graph G describing the potential applications of the distributive law for the given block. 246 **  */ 247 void generateDistributionGraph(PabloBlock * block, DistributionGraph & G) { 248 DistributionMap M; 302 * @brief distribute 303 **  */ 304 inline bool DistributivePass::distribute(PabloBlock * const block) { 305 306 Graph G; 307 308 const VertexSet distSet = generateDistributionGraph(block, G); 309 310 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 311 if (LLVM_UNLIKELY(distSet.empty())) { 312 return false; 313 } 314 315 const DistributionSets distributionSets = safeDistributionSets(G, distSet); 316 317 if (LLVM_UNLIKELY(distributionSets.empty())) { 318 return false; 319 } 320 321 for (const DistributionSet & set : distributionSets) { 322 323 // Each distribution tuple consists of the sources, intermediary, and sink nodes. 324 const VertexSet & sources = std::get<0>(set); 325 const VertexSet & intermediary = std::get<1>(set); 326 const VertexSet & sinks = std::get<2>(set); 327 328 // Find the first sink and set the insert point immediately before that. 329 Variadic * innerOp = nullptr; 330 Variadic * outerOp = nullptr; 331 332 block>setInsertPoint(cast<Variadic>(G[sinks.front()])>getPrevNode()); 333 334 if (isa<And>(G[sinks.front()])) { 335 outerOp = block>createAnd(intermediary.size(), PabloBlock::createOnes()); 336 innerOp = block>createOr(sources.size() + 1, outerOp); 337 } else { 338 outerOp = block>createOr(intermediary.size(), PabloBlock::createZeroes()); 339 innerOp = block>createAnd(sources.size() + 1, outerOp); 340 } 341 342 unsigned i = 0; 343 for (const Vertex u : intermediary) { 344 for (const Vertex v : sinks) { 345 cast<Variadic>(G[v])>removeOperand(cast<Variadic>(G[u])); 346 } 347 outerOp>setOperand(i++, cast<Variadic>(G[u])); 348 } 349 350 i = 0; 351 for (const Vertex u : sources) { 352 for (const Vertex v : intermediary) { 353 cast<Variadic>(G[v])>removeOperand(G[u]); 354 } 355 innerOp>setOperand(i++, G[u]); 356 } 357 for (const Vertex u : sinks) { 358 cast<Variadic>(G[u])>addOperand(innerOp); 359 } 360 } 361 362 return true; 363 } 364 365 /**  * 366 * @brief process 367 **  */ 368 bool DistributivePass::process(PabloBlock * const block) { 369 bool modified = false; 249 370 for (Statement * stmt : *block) { 250 if (isa<And>(stmt)  isa<Or>(stmt)) { 251 const TypeId outerTypeId = stmt>getClassTypeId(); 252 const TypeId innerTypeId = (outerTypeId == TypeId::And) ? TypeId::Or : TypeId::And; 253 flat_set<Variadic *> distributable; 254 for (PabloAST * const expr : *cast<Variadic>(stmt)) { 255 if (LLVM_UNLIKELY(expr>getClassTypeId() == innerTypeId)) { 256 bool safe = true; 257 for (PabloAST * const user : expr>users()) { 258 if (user>getClassTypeId() != outerTypeId) { 259 safe = false; 260 break; 261 } 262 } 263 if (safe) { 264 distributable.insert(cast<Variadic>(expr)); 265 } 266 } 267 } 268 if (LLVM_LIKELY(distributable.size() > 1)) { 269 flat_map<PabloAST *, bool> observedMoreThanOnce; 270 bool anyOpportunities = false; 271 for (const Variadic * distOperation : distributable) { 272 for (PabloAST * const distVar : *distOperation) { 273 auto ob = observedMoreThanOnce.find(distVar); 274 if (ob == observedMoreThanOnce.end()) { 275 observedMoreThanOnce.emplace(distVar, false); 276 } else { 277 ob>second = true; 278 anyOpportunities = true; 279 } 280 } 281 } 282 if (anyOpportunities) { 283 for (const auto ob : observedMoreThanOnce) { 284 PabloAST * const distVar = nullptr; 285 bool observedTwice = false; 286 std::tie(distVar, observedTwice) = *ob; 287 if (observedTwice) { 288 for (PabloAST * const distOperation : distVar>users()) { 289 if (distributable.count(distOperation)) { 290 const Vertex y = getVertex(distOperation, G, M); 291 add_edge(y, getVertex(stmt, G, M), G); 292 add_edge(getVertex(distVar, G, M), y, G); 293 } 294 } 295 } 296 } 297 } 298 } 299 } 300 } 301 } 302 303 /**  * 304 * @brief redistributeAST 305 * 306 * Apply the distribution law to reduce computations whenever possible. 307 **  */ 308 void DistributivePass::redistributeAST(PabloBlock * block) const { 309 310 std::vector<Vertex> mapping(num_vertices(G) + 16); 311 std::iota(mapping.begin(), mapping.end(), 0); // 0,1,.....n 312 313 for (;;) { 314 315 DistributionGraph H; 316 317 generateDistributionGraph(block, H); 318 319 // If we found no potential opportunities then we cannot apply the distribution law to any part of G. 320 if (num_vertices(H) == 0) { 321 break; 322 } 323 324 const DistributionSets distributionSets = safeDistributionSets(block, H); 325 326 if (LLVM_UNLIKELY(distributionSets.empty())) { 327 break; 328 } 329 330 for (const DistributionSet & set : distributionSets) { 331 332 // Each distribution tuple consists of the sources, intermediary, and sink nodes. 333 const VertexSet & sources = std::get<0>(set); 334 const VertexSet & intermediary = std::get<1>(set); 335 const VertexSet & sinks = std::get<2>(set); 336 337 const TypeId outerTypeId = getType(G[mapping[H[sinks.front()]]]); 338 assert (outerTypeId == TypeId::And  outerTypeId == TypeId::Or); 339 const TypeId innerTypeId = (outerTypeId == TypeId::Or) ? TypeId::And : TypeId::Or; 340 341 // Update G to match the desired change 342 const Vertex x = addSummaryVertex(outerTypeId, G); 343 const Vertex y = addSummaryVertex(innerTypeId, G); 344 mapping.resize(num_vertices(G)); 345 mapping[x] = x; 346 mapping[y] = y; 347 348 for (const Vertex i : intermediary) { 349 const auto u = mapping[H[i]]; 350 assert (getType(G[u]) == innerTypeId); 351 for (const Vertex t : sinks) { 352 assert (getType(G[mapping[H[t]]]) == outerTypeId); 353 remove_edge(u, mapping[H[t]], G); 354 } 355 add_edge(nullptr, u, x, G); 356 } 357 358 for (const Vertex s : sources) { 359 const auto u = mapping[H[s]]; 360 for (const Vertex i : intermediary) { 361 remove_edge(u, mapping[H[i]], G); 362 } 363 add_edge(nullptr, u, y, G); 364 } 365 add_edge(nullptr, x, y, G); 366 367 for (const Vertex t : sinks) { 368 const auto v = mapping[H[t]]; 369 add_edge(getValue(G[v]), y, v, G); 370 } 371 372 summarizeGraph(G, mapping); 373 } 374 } 375 } 376 377 378 } 371 if (isa<If>(stmt)  isa<While>(stmt)) { 372 modified = process(isa<If>(stmt) ? cast<If>(stmt)>getBody() : cast<While>(stmt)>getBody()); 373 } 374 } 375 modified = distribute(block); 376 return modified; 377 } 378 379 /**  * 380 * @brief process 381 **  */ 382 bool DistributivePass::optimize(PabloFunction & function) { 383 const bool modified = DistributivePass::process(function.getEntryBlock()); 384 #ifndef NDEBUG 385 PabloVerifier::verify(function, "postdistribution"); 386 #endif 387 Simplifier::optimize(function); 388 return modified; 389 } 390 391 392 }
Note: See TracChangeset
for help on using the changeset viewer.