Galois: RandomKWayRefiner.h Source File

00001 
00024 #ifndef RANDOMKWAYREFINER_H_
00025 #define RANDOMKWAYREFINER_H_
00026 #include "MetisGraph.h"
00027 #include "GMetisConfig.h"
00028 #include "defs.h"
00029 
00030 class RandomKwayEdgeRefiner {
00031 
00032 public:
00033         RandomKwayEdgeRefiner(float* tpwgts, int nparts, float ubfactor, int npasses, int ffactor) {
00034                 this->tpwgts = tpwgts;
00035                 this->nparts = nparts;
00036                 this->ubfactor = ubfactor;
00037                 this->npasses = npasses;
00038                 this->ffactor = ffactor;
00039                 minwgts = new int[nparts];
00040                 maxwgts = new int[nparts];
00041                 itpwgts = new int[nparts];
00042         }
00043         ~RandomKwayEdgeRefiner(){
00044                 delete[] minwgts;
00045                 delete[] maxwgts;
00046                 delete[] itpwgts;
00047         }
00048         void refine(MetisGraph* metisGraph){
00049 
00050                 int tvwgt = 0;
00051                 for (int i = 0; i < nparts; i++) {
00052                         tvwgt += metisGraph->getPartWeight(i);
00053                 }
00054                 for (int i = 0; i < nparts; i++) {
00055                         itpwgts[i] = (int) (tpwgts[i] * tvwgt);
00056                         maxwgts[i] = (int) (tpwgts[i] * tvwgt * ubfactor);
00057                         minwgts[i] = (int) (tpwgts[i] * tvwgt * (1.0 / ubfactor));
00058                 }
00059 
00060                 for (int pass = 0; pass < npasses; pass++) {
00061                         int oldcut = metisGraph->getMinCut();
00062 
00063                         Galois::GReducible<PerCPUValue, mergeP> perCPUValues;
00064                         parallelRefine pr(metisGraph, this, &perCPUValues);
00065                         Galois::for_each<GaloisRuntime::WorkList::ChunkedLIFO<32, GNode> >(metisGraph->getBoundaryNodes()->begin(), metisGraph->getBoundaryNodes()->end(), pr, "RandomKWAYRefine");
00066                         metisGraph->incMinCut(perCPUValues.get().mincutInc);
00067                         GNodeSTLSet& changedNodes = perCPUValues.get().changedBndNodes;
00068                         for(GNodeSTLSet::iterator iter=changedNodes.begin();iter!=changedNodes.end();++iter){
00069                                 GNode changed = *iter;
00070                                 if(changed.getData().isBoundary()){
00071                                         metisGraph->getBoundaryNodes()->insert(changed);
00072                                 }else{
00073                                         metisGraph->getBoundaryNodes()->erase(changed);
00074                                 }
00075                         }
00076 //                      GGraph* graph = metisGraph->getGraph();
00077 //                      for (GGraph::active_iterator ii = graph->active_begin(), ee = graph->active_end(); ii != ee; ++ii) {
00078 //                              GNode node = *ii;
00079 //                              if(node.getData().isBoundary()){
00080 //                                      metisGraph->getBoundaryNodes()->insert(node);
00081 //                              }else{
00082 //                                      metisGraph->getBoundaryNodes()->erase(node);
00083 //                              }
00084 //                      }
00085                         if (metisGraph->getMinCut() == oldcut) {
00086                                 break;
00087                         }
00088                 }
00089         }
00090 
00091 private:
00092 
00093   void refineOneNode(MetisGraph* metisGraph, GNode n,  Galois::GReducible<PerCPUValue, mergeP>* perCPUValues) {
00094                 GGraph* graph = metisGraph->getGraph();
00095                 MetisNode& nodeData = n.getData(Galois::CHECK_CONFLICT);
00096                 if (nodeData.getEdegree() >= nodeData.getIdegree()) {
00097                         int from = nodeData.getPartition();
00098                         //TODO
00099                         int from_weight=metisGraph->getPartWeight(from);
00100                         int vwgt = nodeData.getWeight();
00101                         if (nodeData.getIdegree() > 0 && from_weight - vwgt < minwgts[from])
00102                                 return;
00103                         int k = 0;
00104                         int to = 0;
00105                         long id = nodeData.getIdegree();
00106                         for (k = 0; k < nodeData.getNDegrees(); k++) {
00107                                 long gain = nodeData.getPartEd()[k] - id;
00108                                 if (gain < 0)
00109                                         continue;
00110                                 to = nodeData.getPartIndex()[k];
00111 
00112                                 if (metisGraph->getPartWeight(to) + vwgt <= maxwgts[to] + ffactor * gain && gain >= 0)
00113                                         break;
00114                         }
00115                         if (k == nodeData.getNDegrees())
00116                                 return;
00117                         for (int j = k + 1; j < nodeData.getNDegrees(); j++) {
00118                                 to = nodeData.getPartIndex()[j];
00119                                 int to_weight=metisGraph->getPartWeight(to);
00120                                 if ((nodeData.getPartEd()[j] > nodeData.getPartEd()[k] && to_weight + vwgt <= maxwgts[to])
00121                                                 || (nodeData.getPartEd()[j] == nodeData.getPartEd()[k]
00122                                                                                          && itpwgts[nodeData.getPartIndex()[k]] * to_weight < itpwgts[to]
00123                                                                                                                                                  * metisGraph->getPartWeight(nodeData.getPartIndex()[k])))
00124                                         k = j;
00125                         }
00126 
00127                         to = nodeData.getPartIndex()[k];
00128                         int to_weight=metisGraph->getPartWeight(to);
00129                         int j = 0;
00130                         if (nodeData.getPartEd()[k] - nodeData.getIdegree() > 0)
00131                                 j = 1;
00132                         else if (nodeData.getPartEd()[k] - nodeData.getIdegree() == 0) {
00133                                 if (from_weight >= maxwgts[from]
00134                                                            || itpwgts[from] * (to_weight + vwgt) < itpwgts[to] * from_weight)
00135                                         j = 1;
00136                         }
00137                         if (j == 0)
00138                                 return;
00139 
00140                         /*
00141                          * if we got here, we can now move the vertex from 'from' to 'to'
00142                          */
00143                         //dummy for cautious
00144 //                      if(!GaloisRuntime.getRuntime().useSerial()){
00145                         for (GGraph::neighbor_iterator jj = graph->neighbor_begin(n, Galois::CHECK_CONFLICT), eejj = graph->neighbor_end(n, Galois::CHECK_CONFLICT); jj != eejj; ++jj) {
00146                                 GNode neighbor = *jj;
00147 
00148                                 neighbor.getData(Galois::NONE);
00149                         }
00150 //                      }
00151 
00152 //                      metisGraph->incMinCut(-(nodeData.getPartEd()[k] - nodeData.getIdegree()));
00153                         perCPUValues->get().mincutInc+=-(nodeData.getPartEd()[k] - nodeData.getIdegree());
00154                         nodeData.setPartition(to);
00155                         metisGraph->incPartWeight(to, vwgt);
00156                         metisGraph->incPartWeight(from, -vwgt);
00157 
00158                         nodeData.setEdegree(nodeData.getEdegree() + nodeData.getIdegree() - nodeData.getPartEd()[k]);
00159                         int temp = nodeData.getIdegree();
00160                         nodeData.setIdegree(nodeData.getPartEd()[k]);
00161                         nodeData.getPartEd()[k] = temp;
00162 
00163                         if (nodeData.getPartEd()[k] == 0) {
00164                                 nodeData.setNDegrees(nodeData.getNDegrees() - 1);
00165                                 nodeData.getPartEd()[k] = nodeData.getPartEd()[nodeData.getNDegrees()];
00166                                 nodeData.getPartIndex()[k] = nodeData.getPartIndex()[nodeData.getNDegrees()];
00167                         } else {
00168                                 nodeData.getPartIndex()[k] = from;
00169                         }
00170 
00171                         if (nodeData.getEdegree() - nodeData.getIdegree() < 0){
00172 //                              metisGraph->unsetBoundaryNode(n);
00173                                 metisGraph->unMarkBoundaryNode(n);
00174 //                              perCPUValues->get().changedBndNodes.push_back(n);
00175                                 perCPUValues->get().changedBndNodes.insert(n);
00176                         }
00177 
00178                         /*
00179                          * update the degrees of adjacent vertices
00180                          */
00181                         for (GGraph::neighbor_iterator jj = graph->neighbor_begin(n, Galois::NONE), eejj = graph->neighbor_end(n, Galois::NONE); jj != eejj; ++jj) {
00182                                 GNode neighbor = *jj;
00183                                 MetisNode& neighborData = neighbor.getData(Galois::NONE);
00184                                 if (neighborData.getPartEd().size() == 0) {
00185                                         int numEdges = neighborData.getNumEdges();
00186 //                                      neighborData.partIndex = new int[numEdges];
00187 //                                      neighborData.partEd = new int[numEdges];
00188 //                                      cout<<"init"<<endl;
00189                                         neighborData.initPartEdAndIndex(numEdges);
00190                                 }
00191                                 int edgeWeight = graph->getEdgeData(n, jj, Galois::NONE);
00192                                 if (neighborData.getPartition() == from) {
00193                                         neighborData.setEdegree(neighborData.getEdegree() + edgeWeight);
00194                                         neighborData.setIdegree(neighborData.getIdegree() - edgeWeight);
00195                                         if (neighborData.getEdegree() - neighborData.getIdegree() >= 0 && !neighborData.isBoundary())
00196                                         {
00197 //                                              metisGraph->setBoundaryNode(neighbor);
00198                                                 metisGraph->markBoundaryNode(neighbor);
00199 //                                              perCPUValues->get().changedBndNodes.push_back(neighbor);
00200                                                 perCPUValues->get().changedBndNodes.insert(neighbor);
00201                                         }
00202                                 } else if (neighborData.getPartition() == to) {
00203                                         neighborData.setEdegree(neighborData.getEdegree() - edgeWeight);
00204                                         neighborData.setIdegree(neighborData.getIdegree() + edgeWeight);
00205                                         if (neighborData.getEdegree() - neighborData.getIdegree() < 0 && neighborData.isBoundary())
00206                                         {
00207 //                                              metisGraph->unsetBoundaryNode(neighbor);
00208                                                 metisGraph->unMarkBoundaryNode(neighbor);
00209 //                                              perCPUValues->get().changedBndNodes.push_back(neighbor);
00210                                                 perCPUValues->get().changedBndNodes.insert(neighbor);
00211                                         }
00212 
00213                                 }
00214                                 /*Remove contribution from the .ed of 'from' */
00215                                 if (neighborData.getPartition() != from) {
00216                                         for (int i = 0; i < neighborData.getNDegrees(); i++) {
00217                                                 if (neighborData.getPartIndex()[i] == from) {
00218                                                         if (neighborData.getPartEd()[i] == edgeWeight) {
00219                                                                 neighborData.setNDegrees(neighborData.getNDegrees() - 1);
00220                                                                 neighborData.getPartEd()[i] = neighborData.getPartEd()[neighborData.getNDegrees()];
00221                                                                 neighborData.getPartIndex()[i] = neighborData.getPartIndex()[neighborData.getNDegrees()];
00222                                                         } else {
00223                                                                 neighborData.getPartEd()[i] -= edgeWeight;
00224                                                         }
00225                                                         break;
00226                                                 }
00227                                         }
00228                                 }
00229                                 /*
00230                                  * add contribution to the .ed of 'to'
00231                                  */
00232                                 if (neighborData.getPartition() != to) {
00233                                         int i;
00234                                         for (i = 0; i < neighborData.getNDegrees(); i++) {
00235                                                 if (neighborData.getPartIndex()[i] == to) {
00236                                                         neighborData.getPartEd()[i] += edgeWeight;
00237                                                         break;
00238                                                 }
00239                                         }
00240                                         if (i == neighborData.getNDegrees()) {
00241                                                 int nd = neighborData.getNDegrees();
00242                                                 neighborData.getPartIndex()[nd] = to;
00243                                                 neighborData.getPartEd()[nd++] = edgeWeight;
00244                                                 neighborData.setNDegrees(nd);
00245                                         }
00246                                 }
00247                         }
00248                 }
00249 
00250         }
00251 
00252 
00253         struct parallelRefine {
00254                 MetisGraph* metisGraph;
00255                 RandomKwayEdgeRefiner* refiner;
00256           Galois::GReducible<PerCPUValue, mergeP>* perCPUValues;
00257           parallelRefine(MetisGraph* metisGraph, RandomKwayEdgeRefiner* refiner, Galois::GReducible<PerCPUValue, mergeP>* perCPUValues){
00258                         this->metisGraph = metisGraph;
00259                         this->refiner = refiner;
00260                         this->perCPUValues = perCPUValues;
00261                 }
00262                 template<typename Context>
00263                 void __attribute__((noinline)) operator()(GNode item, Context& lwl) {
00264 //                      if(perCPUValues->get().changedBndNodes.size() == 0){
00265 //                              perCPUValues->get().changedBndNodes.reserve(metisGraph->getNumOfBoundaryNodes());
00266 //                              cout<<"resize to "<<metisGraph->getNumOfBoundaryNodes()<<endl;
00267 //                      }
00268                   refiner->refineOneNode(metisGraph, item, perCPUValues);
00269                 }
00270         };
00271 
00272         float* tpwgts;
00273         float ubfactor;
00274         float npasses;
00275         int ffactor;
00276         int nparts;
00277         int* minwgts;
00278         int* maxwgts;
00279         int* itpwgts;
00280 };
00281 #endif /* RANDOMKWAYREFINER_H_ */