Galois: Coarsening.h Source File

00001 
00024 #ifndef COARSENING_H_
00025 #define COARSENING_H_
00026 #include "GMetisConfig.h"
00027 #include "HEM.h"
00028 #include "RM.h"
00029 #include <map>
00030 using namespace boost;
00031 using namespace std;
00032 #include <boost/unordered_map.hpp>
00033 //typedef unordered_map<int, int> IntIntMap;
00034 typedef map<int, int> IntIntMap;
00035 typedef vector<int> IntVec;
00036 #include <boost/lexical_cast.hpp>
00037 class Coarsener {
00038 public:
00039 
00040         Coarsener(bool userSerial, int coarsenTo, int maxVertexWeight) {
00041                 this->useSerial = userSerial;
00042                 this->coarsenTo = coarsenTo;
00043                 this->maxVertexWeight = maxVertexWeight;
00044         }
00045 
00046         int getCoarsenTo() {
00047                 return coarsenTo;
00048         }
00049 
00050         void createNodes(MetisGraph* coarseMetisGraph){
00051                 GGraph* coarseGraph = coarseMetisGraph->getGraph();
00052                 bool* visited = new bool[metisGraph->getNumNodes()];
00053                 arrayFill(visited, metisGraph->getNumNodes(), false);
00054                 int id = 0;
00055                 for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00056                         GNode node = *ii;
00057                         MetisNode nodeData = node.getData(Galois::NONE);
00058                         if(visited[nodeData.getNodeId()]) continue;
00059 
00060                         GNode match = metisGraph->getMatch(nodeData.getNodeId());
00061                         MetisNode matchNodeData = match.getData(Galois::NONE);
00062                         int weight = nodeData.getWeight();
00063                         if(match!=node){
00064                                 weight+=matchNodeData.getWeight();
00065                         }
00066                         GNode newNode = coarseGraph->createNode(MetisNode(id++, weight));
00067                         coarseGraph->addNode(newNode, nodeData.getNumEdges()+matchNodeData.getNumEdges(), Galois::NONE);
00068                         metisGraph->setCoarseGraphMap(nodeData.getNodeId(), newNode);
00069                         if(match!=node){
00070                                 metisGraph->setCoarseGraphMap(matchNodeData.getNodeId(), newNode);
00071                         }
00072                         visited[matchNodeData.getNodeId()] = true;
00073                 }
00074                 coarseMetisGraph->setNumNodes(id);
00075                 delete[] visited;
00076         }
00077 
00078         MetisGraph* coarsen(MetisGraph* metisGraph) {
00079                 bool notFirstTime = false; // use when the graph have all weights equal
00080                 bool* visited = new bool[metisGraph->getNumNodes()];
00081                 int level = 0;
00082                 do {
00083                         metisGraph->initMatches();
00084                         metisGraph->initCoarseGraphMap();
00085                         MetisGraph* coarseMetisGraph = new MetisGraph();
00086                         GGraph* coarser = new GGraph();
00087 
00088                         coarseMetisGraph->setGraph(coarser);
00089                         this->graph = metisGraph->getGraph();
00090                         this->metisGraph = metisGraph;
00091                         if (useSerial) {
00092                                 notFirstTime = serialMatch(notFirstTime, coarser);
00093                                 createNodes(coarseMetisGraph);
00094 
00095                                 // assigning id to coarseGraph
00096                                 int id = 0;
00097                                 for (GGraph::active_iterator ii = coarser->active_begin(), ee = coarser->active_end(); ii != ee; ++ii) {
00098                                         GNode node = *ii;
00099                                         node.getData().setNodeId(id++);
00100                                 }
00101                                 coarseMetisGraph->setNumNodes(id);
00102                                 serialCreateCoarserGraph(coarseMetisGraph, visited);
00103                         } else {
00104 //                              Galois::Timer t1;
00105 //                              t1.start();
00106                                 notFirstTime = parallelMatch(notFirstTime, coarser, level);
00107 //                              t1.stop();
00108 //                              cout<<"matchTime::"<<t1.get()<<endl;
00109 
00110                                 // assigning id to coarseGraph
00111                                 createNodes(coarseMetisGraph);
00112 
00113 //                              int id = 0;
00114 //                              for (GGraph::active_iterator ii = coarser->active_begin(), ee = coarser->active_end(); ii != ee; ++ii) {
00115 //                                      GNode node = *ii;
00116 //                                      node.getData().setNodeId(id++);
00117 //                              }
00118 //                              coarseMetisGraph->setNumNodes(id);
00119 
00120                                 parallelCreateCoarserGraph(coarseMetisGraph, visited, level++);
00121 
00122 //                              coarseMetisGraph->getMaxAdjSum();
00123                         }
00124                         int numEdges = 0;
00125                         for (GGraph::active_iterator ii = coarser->active_begin(), ee = coarser->active_end(); ii != ee; ++ii) {
00126                                 numEdges += graph->neighborsSize(*ii, Galois::NONE);
00127                         }
00128                         metisGraph->releaseMatches();
00129                         coarseMetisGraph->setNumEdges(numEdges / 2);
00130                         coarseMetisGraph->setFinerGraph(metisGraph);
00131                         metisGraph = coarseMetisGraph;
00132 
00133                 } while (isDone(metisGraph));
00134                 delete[] visited;
00135                 return metisGraph;
00136         }
00137 private:
00138         bool serialMatch(bool notFirstTime, GGraph* coarser) {
00139                 if (notFirstTime) {
00140                         HEMMatcher matcher(metisGraph, coarser, maxVertexWeight);
00141 
00142                         for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00143                                 GNode node = *ii;
00144                                 matcher.match(node);
00145                         }
00146                 } else {
00147                         RMMatcher matcher(metisGraph, coarser, maxVertexWeight);
00148                         for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00149                                 GNode node = *ii;
00150                                 matcher.match(node);
00151                         }
00152                         notFirstTime = true;
00153                 }
00154                 return notFirstTime;
00155         }
00156 
00157         template<typename MatchingPolicy>
00158         struct parallelMatchNodes {
00159                 GGraph* coarser;
00160                 MatchingPolicy matcher;
00161                 MetisGraph* metisGraph;
00162                 int maxVertexWeight;
00163                 parallelMatchNodes(MetisGraph* metisGraph, GGraph* coarser, int maxVertexWeight):matcher(metisGraph, coarser, maxVertexWeight){
00164                         this->metisGraph = metisGraph;
00165                         this->coarser = coarser;
00166                         this->maxVertexWeight = maxVertexWeight;
00167                 }
00168                 template<typename Context>
00169                 void __attribute__((noinline)) operator()(GNode item, Context& lwl) {
00170                         matcher.match(item);
00171                 }
00172         };
00173 
00174         bool parallelMatch(bool notFirstTime, GGraph* coarser, int level){
00175 
00176                 if (notFirstTime) {
00177                         parallelMatchNodes<HEMMatcher> pHEM(metisGraph, coarser, maxVertexWeight);
00178                         Galois::for_each<GaloisRuntime::WorkList::ChunkedLIFO<64, GNode> >(graph->active_begin(), graph->active_end(), pHEM, "HEM_Match");
00179 //                      vector<GNode> v(graph->active_begin(), graph->active_end());
00180 //                      std::random_shuffle( v.begin(), v.end() );
00181 //                      Galois::for_each<GaloisRuntime::WorkList::ChunkedFIFO<32, GNode> >(v.begin(), v.end(), pHEM);
00182                 } else {
00183                         parallelMatchNodes<RMMatcher> pRM(metisGraph, coarser, maxVertexWeight);
00184 //                      vector<GNode> v(graph->active_begin(), graph->active_end());
00185 //                      std::random_shuffle( v.begin(), v.end() );
00186 //                      Galois::for_each<GaloisRuntime::WorkList::ChunkedFIFO<32, GNode> >(v.begin(), v.end(), pRM);
00187                         Galois::for_each<GaloisRuntime::WorkList::ChunkedLIFO<64, GNode> >(graph->active_begin(), graph->active_end(), pRM, "RM_Match");
00188                         notFirstTime = true;
00189                 }
00190                 return notFirstTime;
00191         }
00192 
00196         bool isDone(MetisGraph* metisGraph) {
00197                 int size = metisGraph->getNumNodes();//graph->size();
00198 //              cout<<metisGraph->getNumNodes()<<"|"<<metisGraph->getNumEdges()<<"<---"<<metisGraph->getFinerGraph()->getNumNodes()<<"|"<<metisGraph->getNumEdges()<<endl;
00199                 return size > coarsenTo && size < COARSEN_FRACTION * metisGraph->getFinerGraph()->getNumNodes()//->getGraph()->size()
00200                                 && metisGraph->getNumEdges() > size / 2;
00201         }
00202 
00203         void addNeighbors(int nodeId, GNode node, GGraph* graph, MetisGraph* coarseMetisGraph, IntVec& lmap) {
00204                 //int nodeId = node.getData(Galois::NONE).getNodeId();
00205                 GNode matched = metisGraph->getMatch(nodeId);//.getMatch();
00206                 GNode nodeMapTo = metisGraph->getCoarseGraphMap(nodeId);//node.getData(Galois::NONE).getMapTo();
00207                 MetisNode& nodeMapToData = nodeMapTo.getData(Galois::NONE);
00208                 GGraph* coarseGraph = coarseMetisGraph->getGraph();
00209                 for (GGraph::neighbor_iterator jj = graph->neighbor_begin(node, Galois::NONE), eejj = graph->neighbor_end(node, Galois::NONE); jj != eejj; ++jj) {
00210                         GNode neighbor = *jj;
00211                         if (neighbor == matched) {
00212                                 continue;
00213                         }
00214                         int edgeWeight = graph->getEdgeData(node, jj, Galois::NONE);
00215                         GNode neighborMapTo = metisGraph->getCoarseGraphMap(neighbor.getData(Galois::NONE).getNodeId());//neighbor.getData(Galois::NONE).getMapTo();
00216                         int neighMapToId = neighborMapTo.getData(Galois::NONE).getNodeId();
00217 //                      int& weight = lmap[neighMapToId];
00218                         int pos = -1;
00219                         for(int i=lmap.size()-1;i>=0;i--){
00220                                 if(lmap[i]  == neighMapToId){
00221                                         pos = i;
00222                                 }
00223                         }
00224                         if(pos == -1){
00225                                 coarseGraph->addEdge(nodeMapTo, neighborMapTo, edgeWeight, Galois::NONE);
00226                                 coarseMetisGraph->incNumEdges();
00227                                 nodeMapToData.incNumEdges();
00228                                 nodeMapToData.addEdgeWeight(edgeWeight);
00229                                 lmap.push_back(neighMapToId);
00230                         } else {
00231                                 coarseGraph->getEdgeData(nodeMapTo, neighborMapTo, Galois::NONE) += edgeWeight;
00232                                 nodeMapToData.addEdgeWeight(edgeWeight);
00233                         }
00234 
00235 
00236 //                      weight += edgeWeight;
00237 //                      coarseGraph->addEdge(nodeMapTo, neighborMapTo, weight, Galois::NONE);
00238 //                      coarseMetisGraph->incNumEdges();
00239 //                      nodeMapToData.incNumEdges();
00240 //                      nodeMapToData.addEdgeWeight(edgeWeight);
00241 
00242 //                      if (lmap.find(neighMapToId)==lmap.end()) {
00243 //                              coarseGraph->addEdge(nodeMapTo, neighborMapTo, edgeWeight, Galois::NONE);
00244 //                              coarseMetisGraph->incNumEdges();
00245 //                              MetisNode& nodeMapToData = nodeMapTo.getData(Galois::NONE);
00246 //                              nodeMapToData.incNumEdges();
00247 //                              nodeMapToData.addEdgeWeight(edgeWeight);
00248 //                              lmap[neighMapToId] = edgeWeight;
00249 //                      } else {
00250 //                              int newEdgeWeight = lmap[neighMapToId];
00251 //                              lmap[neighMapToId] = edgeWeight + newEdgeWeight;
00252 //                              coarseGraph->getEdgeData(nodeMapTo, neighborMapTo, Galois::NONE) += edgeWeight;
00253 //                              nodeMapTo.getData(Galois::NONE).addEdgeWeight(edgeWeight);
00254 //                      }
00255                 }
00256         }
00257 
00258         void addNeighbors(int nodeId, GNode node, GGraph* graph, MetisGraph* coarseMetisGraph) {
00259                 //int nodeId = node.getData(Galois::NONE).getNodeId();
00260                 GNode matched = metisGraph->getMatch(nodeId);//.getMatch();
00261                 GNode nodeMapTo = metisGraph->getCoarseGraphMap(nodeId);//node.getData(Galois::NONE).getMapTo();
00262                 MetisNode& nodeMapToData = nodeMapTo.getData(Galois::NONE);
00263                 GGraph* coarseGraph = coarseMetisGraph->getGraph();
00264                 for (GGraph::neighbor_iterator jj = graph->neighbor_begin(node, Galois::NONE), eejj = graph->neighbor_end(node, Galois::NONE); jj != eejj; ++jj) {
00265                         GNode neighbor = *jj;
00266                         if (neighbor == matched) {
00267                                 continue;
00268                         }
00269                         int edgeWeight = graph->getEdgeData(node, jj, Galois::NONE);
00270                         GNode neighborMapTo = metisGraph->getCoarseGraphMap(neighbor.getData(Galois::NONE).getNodeId());//neighbor.getData(Galois::NONE).getMapTo();
00271 //                      int neighMapToId = neighborMapTo.getData(Galois::NONE).getNodeId();
00272                         int& weight = coarseGraph->getOrCreateEdge(nodeMapTo, neighborMapTo, Galois::NONE);
00273 //                      int& weight = coarseGraph->getEdgeData(nodeMapTo, neighborMapTo, Galois::NONE);
00274 
00275                         if(weight == 0){
00276                                 weight = edgeWeight;
00277                                 nodeMapToData.incNumEdges();
00278 //                              coarseMetisGraph->incNumEdges();
00279                         }else{
00280                                 weight += edgeWeight;
00281                         }
00282                         nodeMapToData.addEdgeWeight(edgeWeight);
00283                 }
00284 //              cout<<"neighborSize:"<<coarseGraph->neighborsSize(nodeMapTo)<<endl;
00285         }
00286 
00287         void addNeighbors(int nodeId, GNode node, GGraph* graph, MetisGraph* coarseMetisGraph, IntIntMap& lmap) {
00288                         //int nodeId = node.getData(Galois::NONE).getNodeId();
00289                         GNode matched = metisGraph->getMatch(nodeId);//.getMatch();
00290                         GNode nodeMapTo = metisGraph->getCoarseGraphMap(nodeId);//node.getData(Galois::NONE).getMapTo();
00291                         MetisNode& nodeMapToData = nodeMapTo.getData(Galois::NONE);
00292                         GGraph* coarseGraph = coarseMetisGraph->getGraph();
00293                         for (GGraph::neighbor_iterator jj = graph->neighbor_begin(node, Galois::NONE), eejj = graph->neighbor_end(node, Galois::NONE); jj != eejj; ++jj) {
00294                                 GNode neighbor = *jj;
00295                                 if (neighbor == matched) {
00296                                         continue;
00297                                 }
00298                                 int edgeWeight = graph->getEdgeData(node, jj, Galois::NONE);
00299                                 GNode neighborMapTo = metisGraph->getCoarseGraphMap(neighbor.getData(Galois::NONE).getNodeId());//neighbor.getData(Galois::NONE).getMapTo();
00300 //                              int neighMapToId = neighborMapTo.getData(Galois::NONE).getNodeId();
00301 //                              int& weight = lmap[neighMapToId];
00302 //                              weight += edgeWeight;
00303 //                              coarseGraph->addEdge(nodeMapTo, neighborMapTo, weight, Galois::Graph::NONE);
00304                                 int& weight = coarseGraph->getOrCreateEdge(nodeMapTo, neighborMapTo, 0, Galois::NONE);
00305                                 assert(weight>=0);
00306                                 if(weight == 0){
00307                                         weight = edgeWeight;
00308                                         nodeMapToData.incNumEdges();
00309 //                                      coarseMetisGraph->incNumEdges();
00310                                 }else{
00311                                         weight += edgeWeight;
00312                                 }
00313                                 assert(weight>=0);
00314                                 nodeMapToData.addEdgeWeight(edgeWeight);
00315                                 assert(nodeMapToData.getAdjWgtSum()>=0);
00316 //                              if (lmap.find(neighMapToId)==lmap.end()) {
00317 //                                      coarseGraph->addEdge(nodeMapTo, neighborMapTo, edgeWeight, Galois::NONE);
00318 //                                      coarseMetisGraph->incNumEdges();
00319 //                                      MetisNode& nodeMapToData = nodeMapTo.getData(Galois::NONE);
00320 //                                      nodeMapToData.incNumEdges();
00321 //                                      nodeMapToData.addEdgeWeight(edgeWeight);
00322 //                                      lmap[neighMapToId] = edgeWeight;
00323 //                              } else {
00324 //                                      int newEdgeWeight = lmap[neighMapToId];
00325 //                                      lmap[neighMapToId] = edgeWeight + newEdgeWeight;
00326 //                                      coarseGraph->getEdgeData(nodeMapTo, neighborMapTo, Galois::NONE) += edgeWeight;
00327 //                                      nodeMapTo.getData(Galois::NONE).addEdgeWeight(edgeWeight);
00328 //                              }
00329                         }
00330         }
00331 
00332         void addEdges(int nodeId, GNode node, bool* visited, MetisGraph* coarseMetisGraph) {
00333 //              MetisNode& nodeData = node.getData(Galois::NONE);
00334 //              int nodeId = nodeData.getNodeId();
00335                 if (visited[nodeId])
00336                         return;
00337 //              lmap.clear();
00338                 GNode matched = metisGraph->getMatch(nodeId);
00339                 addNeighbors(nodeId, node, graph, coarseMetisGraph);
00340                 if (matched != node) {
00341                         //matched.map(new buildNeighborClosure(graph, coarseMetisGraph, matched, node, lmap), matched);
00342                         MetisNode& matchedData = matched.getData(Galois::NONE);
00343                         addNeighbors(matchedData.getNodeId(), matched, graph, coarseMetisGraph);
00344                         visited[matchedData.getNodeId()] = true;
00345                 }
00346                 //cout<<"nodeID:___"<<graph->neighborsSize(node,Galois::NONE)<<"|"<<graph->neighborsSize(matched,Galois::NONE)<<endl;
00347 //              cout<<"maxNeighborSize:"<<maxNeighborSize<<endl;
00348 //              if(maxNeighborSize>100){
00349 //                      IntIntMap lmap;
00350 //
00351 //                      addNeighbors(nodeId, node, graph, coarseMetisGraph, lmap);
00352 //                      if (matched != node) {
00353 //                              //matched.map(new buildNeighborClosure(graph, coarseMetisGraph, matched, node, lmap), matched);
00354 //                              MetisNode& matchedData = matched.getData(Galois::NONE);
00355 //                              addNeighbors(matchedData.getNodeId(), matched, graph, coarseMetisGraph, lmap);
00356 //                              visited[matchedData.getNodeId()] = true;
00357 //                      }
00358 //              }else{
00359 //                      IntVec lmap;
00360 //                      lmap.reserve(50);
00361 //                      addNeighbors(nodeId, node, graph, coarseMetisGraph, lmap);
00362 //                      if (matched != node) {
00363 //                              //matched.map(new buildNeighborClosure(graph, coarseMetisGraph, matched, node, lmap), matched);
00364 //                              MetisNode& matchedData = matched.getData(Galois::NONE);
00365 //                              addNeighbors(matchedData.getNodeId(), matched, graph, coarseMetisGraph, lmap);
00366 //                              visited[matchedData.getNodeId()] = true;
00367 //
00368 //              }
00369 //              }
00370         }
00371 
00372         void serialCreateCoarserGraph(MetisGraph* coarseMetisGraph, bool* visited) {
00373 //              cache_line_storage<bool>* visited = new cache_line_storage<bool>[metisGraph->getNumNodes()];
00374                 arrayFill(visited, metisGraph->getNumNodes(),false);
00375 //              for(int i=0;i<metisGraph->getNumNodes();i++){
00376 //                      visited[i] = false;
00377 //              }
00378 
00379                 for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00380                         GNode node = *ii;
00381                         addEdges(node.getData(Galois::NONE).getNodeId(), node, visited, coarseMetisGraph);
00382                 }
00383 //              delete[] visited;
00384         }
00385 
00386         struct parallelAddingEdges {
00387                 MetisGraph* coarseMetisGraph;
00388 //              cache_line_storage<bool>* visited;
00389                 bool* visited;
00390                 MetisGraph* metisGraph;
00391                 GGraph* graph;
00392                 Coarsener* coarsener;
00393                 parallelAddingEdges(MetisGraph* metisGraph, MetisGraph* coarseMetisGraph, Coarsener* coarsener, bool* visited){
00394                         this->coarseMetisGraph = coarseMetisGraph;
00395                         graph = metisGraph->getGraph();
00396                         this->visited = visited;//new bool[graph->size()];
00397 //                      arrayFill(visited, metisGraph->getNumNodes(),false);
00398                         for(int i=0;i<metisGraph->getNumNodes();i++){
00399                                 visited[i] = false;
00400                         }
00401                         this->metisGraph= metisGraph;
00402                         this->coarsener = coarsener;
00403                 }
00404                 //               ~parallelAddingEdges(){
00406                 //               }
00407                 template<typename Context>
00408                 void __attribute__((noinline)) operator()(GNode item, Context& lwl) {
00409                         MetisNode& nodeData = item.getData(Galois::NONE);
00410                         metisGraph->getCoarseGraphMap(nodeData.getNodeId()).getData(Galois::CHECK_CONFLICT);
00411                         coarsener->addEdges(nodeData.getNodeId(), item, visited, coarseMetisGraph);
00412                 }
00413         };
00414 
00415         void parallelCreateCoarserGraph(MetisGraph* coarseMetisGraph, bool* visited, int level){
00416 //              cache_line_storage<bool>* visited = new cache_line_storage<bool>[metisGraph->getNumNodes()];
00417 //              Galois::Timer t2;
00418 //              t2.start();
00419                 parallelAddingEdges pae(metisGraph, coarseMetisGraph, this, visited);
00420                 Galois::for_each<GaloisRuntime::WorkList::ChunkedLIFO<32, GNode> >(graph->active_begin(), graph->active_end(), pae, "AddNeighbors");
00421 //              t2.stop();
00422 //              cout<<"createTime::"<<t2.get()<<endl;
00423         }
00424 
00425 public:
00426         static const double COARSEN_FRACTION = 0.90;
00427 private:
00428         int coarsenTo;
00429         int maxVertexWeight;
00430         bool useSerial;
00431         GGraph* graph;
00432         MetisGraph* metisGraph;
00433 };
00434 #endif /* COARSENING_H_ */