RecBipartLB: ldb strategy using recursive bipartition
authorAbhinav S Bhatele <bhatele@illinois.edu>
Thu, 10 Feb 2011 18:48:22 +0000 (12:48 -0600)
committerAbhinav S Bhatele <bhatele@illinois.edu>
Thu, 10 Feb 2011 18:48:22 +0000 (12:48 -0600)
code written by Swapnil Ghike (ghike2@illinois.edu)

src/ck-ldb/CommonLBs.ci
src/ck-ldb/EveryLB.ci
src/ck-ldb/Make.lb
src/ck-ldb/Makefile_lb.sh
src/ck-ldb/RecBipartLB.C [new file with mode: 0644]
src/ck-ldb/RecBipartLB.ci [new file with mode: 0644]
src/ck-ldb/RecBipartLB.h [new file with mode: 0644]
src/scripts/Make.cidepends
src/scripts/Make.depends

index f999195c214134ce324bb0fa4c9a35ca71911de9..238e5d7005bbf311fba8cab25f9af84b4ca8a61d 100644 (file)
@@ -12,6 +12,7 @@ module CommonLBs {
   extern module OrbLB;
   extern module PhasebyArrayLB;
   extern module RandCentLB;
+  extern module RecBipartLB;
   extern module RefineLB;
   extern module RefineCommLB;
   extern module RotateLB;
index 4dbb408d588ad6daccff6f886940c49511583e77..3defdd416ccf4ce1d874a03ae5cf47afcef18c6d 100644 (file)
@@ -12,6 +12,7 @@ module EveryLB {
   extern module OrbLB;
   extern module PhasebyArrayLB;
   extern module RandCentLB;
+  extern module RecBipartLB;
   extern module RefineLB;
   extern module RefineCommLB;
   extern module RotateLB;
index 2dd3e30d483957c8f8c312e7734128f9887cc995..2700749f0ac5bbc7a3b826f163fd4047a1f0b0d1 100644 (file)
@@ -1,7 +1,7 @@
 # Automatically generated by script Makefile_lb.sh
 #  by uid=21543(bhatele) gid=80(kale) groups=80(kale),400(ppladmin)
 #  at panache
-#  on Tue Feb 8 14:32:51 CST 2011
+#  on Thu Feb 10 12:38:39 CST 2011
 ALL_LDBS=\
    $(L)/libmoduleBlockLB.a \
    $(L)/libmoduleCommLB.a \
@@ -14,6 +14,7 @@ ALL_LDBS=\
    $(L)/libmoduleOrbLB.a \
    $(L)/libmodulePhasebyArrayLB.a \
    $(L)/libmoduleRandCentLB.a \
+   $(L)/libmoduleRecBipartLB.a \
    $(L)/libmoduleRefineLB.a \
    $(L)/libmoduleRefineCommLB.a \
    $(L)/libmoduleRotateLB.a \
@@ -101,6 +102,12 @@ $(L)/libmoduleRandCentLB.a: RandCentLB.o
 LBHEADERS += RandCentLB.h RandCentLB.decl.h
 
 
+$(L)/libmoduleRecBipartLB.a: RecBipartLB.o 
+       $(CHARMC) -o $(L)/libmoduleRecBipartLB.a RecBipartLB.o 
+       
+LBHEADERS += RecBipartLB.h RecBipartLB.decl.h
+
+
 $(L)/libmoduleRefineLB.a: RefineLB.o 
        $(CHARMC) -o $(L)/libmoduleRefineLB.a RefineLB.o 
        
@@ -222,6 +229,7 @@ ALL_LB_OBJS=EveryLB.o \
     OrbLB.o \
     PhasebyArrayLB.o \
     RandCentLB.o \
+    RecBipartLB.o \
     RefineLB.o \
     RefineCommLB.o \
     RotateLB.o \
@@ -254,6 +262,7 @@ EVERYLB_DEPS=EveryLB.o \
     OrbLB.o \
     PhasebyArrayLB.o \
     RandCentLB.o \
+    RecBipartLB.o \
     RefineLB.o \
     RefineCommLB.o \
     RotateLB.o \
@@ -286,6 +295,7 @@ COMMONLBS_DEPS=CommonLBs.o \
     OrbLB.o \
     PhasebyArrayLB.o \
     RandCentLB.o \
+    RecBipartLB.o \
     RefineLB.o \
     RefineCommLB.o \
     RotateLB.o \
index 315b40c2424e63cae22a8c426dc7d385badd5416..10347b0ec3ea759cbd46ed26913499b85bc3d9d9 100755 (executable)
@@ -1,6 +1,6 @@
 #!/bin/sh
 UNCOMMON_LDBS="MetisLB ScotchLB TeamLB"
-COMMON_LDBS="BlockLB CommLB DummyLB GreedyAgentLB GreedyCommLB GreedyLB NeighborCommLB NeighborLB OrbLB PhasebyArrayLB RandCentLB RefineLB RefineCommLB RotateLB"
+COMMON_LDBS="BlockLB CommLB DummyLB GreedyAgentLB GreedyCommLB GreedyLB NeighborCommLB NeighborLB OrbLB PhasebyArrayLB RandCentLB RecBipartLB RefineLB RefineCommLB RotateLB"
 OTHER_LDBS="ComboCentLB GraphPartLB GraphBFTLB GridCommLB GridCommRefineLB GridHybridLB GridHybridSeedLB GridMetisLB HbmLB HybridLB RefineKLB RefineTopoLB TopoCentLB TopoLB WSLB"
 ALL_LDBS="$COMMON_LDBS $OTHER_LDBS"
 
diff --git a/src/ck-ldb/RecBipartLB.C b/src/ck-ldb/RecBipartLB.C
new file mode 100644 (file)
index 0000000..a14f585
--- /dev/null
@@ -0,0 +1,651 @@
+/** \file RecBipartLB.C
+ *  Author: Swapnil Ghike
+ *  Date Created: 
+ *  E-mail: ghike2@illinois.edu
+ *
+ *  This strategy does a recursive bipartition of the object graph and the
+ *  processor graph. The objects are divided based on the loads in case of odd
+ *  number of processors. Recursive bi-partitioning is done by a breadth-first
+ *  traversal until you have the required load in one group.
+ *
+ * 
+ *  At each recursive biparititioning, the boundaries are refined to minimize
+ *  the edge cut. Vertices are moved across the boundary to see if the edge cut
+ *  reduces while trying to maintain proportionate load in both partitions.
+ */
+
+/**
+ *  \addtogroup CkLdb
+ */
+
+/*@{*/
+using namespace std;
+
+#include <limits.h>
+#include <math.h>
+#include <queue>
+#include <vector>
+#include "ckgraph.h"
+#include "RecBipartLB.h"
+
+void RecursiveBiPart(ObjGraph *, vector<Vertex *> & ,int, int);
+void adjustqueues(ObjGraph *, BQueue *, BQueue *, vector<Vertex *> &, vector<Vertex *> &,int *, int);
+void adjustgain(ObjGraph *,vector<Vertex *> &,BQueue *);
+void RefineBoundary(ObjGraph *, vector<Vertex *> &, vector<Vertex *> &,BQueue *, BQueue *, int, int, int, double, double, double);
+int modifypartitions(ObjGraph *,vector<Vertex *> &, vector<Vertex *> &, BQueue *, BQueue *, int, int);
+void swapQ1toQ2(ObjGraph *, BQueue *, BQueue *, int);
+Vertex * removeinSwap(ObjGraph *,BQueue *, BQueue *, int);
+Vertex * removePtr(vector<Vertex *> &,int);
+
+int level;
+double TOTALLOAD;
+vector<Vertex_helper *> vhelpers;
+int numparts, peno;
+ProcArray *parray;
+
+CreateLBFunc_Def(RecBipartLB, "Algorithm for load balacing based on recursive bipartitioning of object graph")
+
+//removes from BQueue but not from boundaryline
+void BQueue::removeToSwap(Vertex *vert)
+{
+  int i;
+  int v=vert->getVertexId();
+  for(i=0;i<q.size();i++)
+  {
+    if(q[i]==v)
+    {
+      //boundaryline and edgestopart1, edgestopart2 are left as they were since this vertex only swaps boundarylines
+      q[i]=q.back();
+      q.pop_back();
+      return;
+    }
+  }
+}
+
+//completely removes from the BQueue as well as from both boundarylines
+void BQueue::removeComplete(Vertex *vert)
+{       
+  int i;
+  int v=vert->getVertexId();
+  for(i=0;i<q.size();i++)
+  {
+    if(q[i]==v)
+    {
+      vhelpers[v]->setBoundaryline(false);
+      vhelpers[v]->setEdgestopart1(0);
+      vhelpers[v]->setEdgestopart2(0);
+      q[i]=q.back();
+      q.pop_back();
+      return;
+    }
+  }
+}
+
+void BQueue::push(Vertex *vert)
+{
+  int v=vert->getVertexId();
+  q.push_back(v);
+  vhelpers[v]->setBoundaryline(true);
+}
+
+
+RecBipartLB::RecBipartLB(const CkLBOptions &opt) : CentralLB(opt) {
+  lbname = "RecBipartLB";
+  if(CkMyPe() == 0)
+    CkPrintf("RecBipartLB created\n");
+}
+
+CmiBool RecBipartLB::QueryBalanceNow(int _step) {
+  return CmiTrue;
+}
+
+void RecBipartLB::work(LDStats *stats) {
+  vector<Vertex *> ptrvector;
+  /** ========================== INITIALIZATION ============================= */
+  ProcArray *parr = new ProcArray(stats);      // Processor Array
+  ObjGraph *ogr = new ObjGraph(stats);         // Object Graph
+
+
+  /** ============================= STRATEGY ================================ */
+  level=0;
+  peno=0;
+  TOTALLOAD=0;
+  numparts=CkNumPes();
+  parray=parr;
+
+  double avgLoad = parr->getAverageLoad();
+  int numPes = parr->procs.size();
+
+  parr->resetTotalLoad();
+  for(int i=0;i<ogr->vertices.size();i++)
+  {
+    Vertex_helper *helper = new Vertex_helper();
+    vhelpers.push_back(helper);
+    ptrvector.push_back((Vertex *)&(ogr->vertices[i]));
+
+  }
+
+  RecursiveBiPart(ogr,ptrvector,1,numparts);
+
+  /** ============================== CLEANUP ================================ */
+  ogr->convertDecisions(stats);                // Send decisions back to LDStats
+}
+
+/* Function that performs Recursive bipartitioning of the object graph.*/
+void RecursiveBiPart(ObjGraph *ogr, vector<Vertex *> &pvertices, int parent, int nump)
+{
+  //if the number of processors that this call has to deal with is 1, dont recurse any further
+  if(nump==1)
+  {
+    parray->procs[peno].setTotalLoad(0);
+    for(int i=0;i<pvertices.size();i++)
+    {
+      pvertices[i]->setNewPe(peno);
+      parray->procs[peno].setTotalLoad(parray->procs[peno].getTotalLoad() + pvertices[i]->getVertexLoad());
+    }
+    peno++;
+
+    return;
+  }
+
+  int numerator=nump/2;
+  double ratio = ((double)numerator/nump);//(ratio=floor of nump/2 divided by nump) This is equal to half if nump is even
+
+  //if you have only one vertex in the parent partition, just map it to the appropriate processor
+  if(pvertices.size()==1)
+  {
+    level++;   
+    RecursiveBiPart(ogr,pvertices,2*parent-1,numerator);//nump =6 =>numerator =3, nump =7=>numertaor =3
+    level--;
+    return;
+  }
+
+  //child partitions
+  vector<Vertex *> partition1;
+  vector<Vertex *> partition2;
+  bool *taken=(bool *)malloc(vhelpers.size()*sizeof(bool));
+
+  for(int i=0;i<vhelpers.size();i++)
+    taken[i]=false;
+  int start = pvertices[0]->getVertexId();
+  int nextPe = 0, count=0, n=0;
+  double loadseen=0;
+  double pload=0;
+  bool getout=false;
+  std::queue<int> que2;
+  std::queue<int> que1;
+  int KLFMruns=pvertices.size()/5;
+
+  //initialize from the parent partition
+  for(int i=0;i<pvertices.size();i++){
+    int id=pvertices[i]->getVertexId();
+    vhelpers[id]->setPartition(2*parent);
+    vhelpers[id]->setMarked(false);
+    vhelpers[id]->setBoundaryline(false);
+    vhelpers[id]->setEdgestopart2(0);
+    vhelpers[id]->setEdgestopart1(0);
+    vhelpers[id]->setLevel(level);
+    pload+=ogr->vertices[id].getVertexLoad();
+  }
+
+  // start at vertex with id 0
+  que2.push(start);
+  vhelpers[start]->setMarked(true);
+
+  int i, nbr, lastforced=0;
+  int visitcount=0;
+
+  bool swap=true;
+  int ei=-1;
+  // breadth first traversal
+  while(!que2.empty() && !getout) {
+    int n = que2.front();
+    que2.pop();
+    count++;
+
+    Vertex *v=(Vertex *)&(ogr->vertices[n]);
+    loadseen+=v->getVertexLoad();
+
+    vhelpers[v->getVertexId()]->setPartition(2*parent-1);//vertices in que2 are in the other partition
+
+    partition1.push_back(v);
+    taken[v->getVertexId()]=true;
+
+    //this case is useful if the last remaining vertex is way too large/heavy
+    if(count==pvertices.size()-1)
+      break;
+
+    //visit neighbors of a vertex
+    while(1) {
+      ei++;
+      if(swap==true && ei==v->sendToList.size())
+      { swap=false; ei=0;}
+
+      if(swap==false && ei==v->recvFromList.size())
+      {swap=true; ei=-1;  break;}
+
+      if(swap)
+       nbr = v->sendToList[ei].getNeighborId();
+      else
+       nbr=v->recvFromList[ei].getNeighborId();
+
+      Vertex_helper *u=(vhelpers[nbr]);
+      visitcount++;
+
+      //not all neighbos of v belong to the parent partition
+      if((u->getMarked()==false) && (u->getPartition()==2*parent) && (u->getLevel()==level)){
+       que2.push(nbr);
+       u->setMarked(true);
+
+      }//end of if
+    }//end of while(1)loop
+
+    //if you have visited enough vertices, stop Breadth First traversal
+    if(loadseen>=(ratio*pload))//if nump is even, ratio=1/2, if nump is odd say 7, ratio = 3/7. 1st rec call will have nump =3 and second nump = 4
+    {
+      getout=true;
+    }
+    else{
+      //if the parent partition is disconnected (likely to happen down the recursion tree), force a vertex in BFS
+      if(que2.empty())
+      {
+       for(int i=lastforced;i<pvertices.size();i++)
+       {
+         Vertex *w=pvertices[i];
+         if(taken[w->getVertexId()]==false)
+         {
+           que2.push(w->getVertexId());
+           vhelpers[w->getVertexId()]->setMarked(true);
+           lastforced=i+1;
+           break;
+         }             
+       }
+      }
+    }
+  } // end of while loop
+
+
+  for(int i=0;i<pvertices.size();i++){
+    Vertex *v=pvertices[i];
+    if(taken[v->getVertexId()]==false)
+      partition2.push_back(v);
+  }
+
+  delete[] taken;
+
+  int initialedgecut;
+
+  //Boundaries in respective child partitions, they are really vectors though the name says BQueue
+  BQueue *q1=new BQueue(1);
+  BQueue *q2=new BQueue(2);
+  int tempsize=que2.size();
+
+  for(i=0;i<tempsize;i++)
+  {
+    q2->push((Vertex *)&(ogr->vertices[que2.front()]));//also sets boundaryline=true for each vertex
+    que2.pop();
+  }
+  adjustqueues(ogr,q1,q2,partition1, partition2, &initialedgecut,parent);//adjusts initial queues and gains, edgecut
+
+  RefineBoundary(ogr,partition1,partition2,q1,q2,KLFMruns,initialedgecut,parent,loadseen,pload-loadseen,ratio);//iteratively modified queues and gains, edgecuts
+
+  //level must be incremented/decremented here
+  level++;
+  RecursiveBiPart(ogr,partition1,vhelpers[partition1[0]->getVertexId()]->getPartition(),numerator);//nump =6 =>numerator =3, nump =7=>numertaor =3
+  RecursiveBiPart(ogr,partition2,vhelpers[partition2[0]->getVertexId()]->getPartition(), nump-numerator);//nump=6=>nump-numerator=3, nump=7=>nump-numerator=4
+  level--;
+}
+
+//Fills in que1, que2 and adjusts their gains, calculates initial edgecut before KLFM
+void adjustqueues(ObjGraph *ogr, BQueue *que1, BQueue *que2, vector <Vertex *> &partition1, vector<Vertex *> &partition2, int *initialedgecut, int parent)
+{
+  int i,j,uid,wid;
+  bool swap=true;
+  int ei=-1;
+  Edge *edge;
+  int edgecut=0;
+  que2->setMingain(INT_MAX);
+  que2->setVertextoswap(-1);
+  que2->setSwapid(-1);
+
+  //This loop fills in que1 and adjusts gain of que2
+  for(i=0;i<que2->q.size();i++)//for each vertex v in que2
+  {
+    int vid=que2->q[i];
+    Vertex *v=((Vertex *)&(ogr->vertices[vid]));
+
+    while(1) {
+      ei++;
+      if(swap==true && ei==v->sendToList.size())
+      { swap=false; ei=0;}
+
+      if(swap==false && ei==v->recvFromList.size())
+      { swap=true; ei=-1; break;}
+
+      if(swap)
+      {
+       uid = v->sendToList[ei].getNeighborId();
+       edge=(Edge *)&(v->sendToList[ei]);
+      }
+      else
+      {
+       uid = v->recvFromList[ei].getNeighborId();
+       edge = (Edge *)&(v->recvFromList[ei]);
+      }
+
+      Vertex *u =(Vertex *)&(ogr->vertices[uid]);
+
+      if((vhelpers[uid]->getPartition())==(2*parent-1) && (vhelpers[uid]->getLevel())==level)//since v is on boundaryline2, its every neighbour in part1 is on boundaryline1
+      {
+       //if not already added to que1
+       if(vhelpers[uid]->getBoundaryline()==false)
+       {
+         que1->push(u);//also sets boundaryline=true
+       }
+
+       //calculate edgecut
+       edgecut+=edge->getNumBytes();
+       vhelpers[vid]->incEdgestopart1(edge->getNumBytes());//assuming it was initialized earlier to 0
+       vhelpers[uid]->incEdgestopart2(edge->getNumBytes());//assuming it was initialized earlier to 0
+      }
+      if(vhelpers[uid]->getPartition()==2*parent && vhelpers[uid]->getLevel()==level)
+      {
+       vhelpers[vid]->incEdgestopart2(edge->getNumBytes());
+      }
+    }//end of while(1) loop
+
+
+    //Edge counts are initialized while performing BFS
+    vhelpers[vid]->setGain(vhelpers[vid]->getEdgestopart2() - vhelpers[vid]->getEdgestopart1());
+    if(vhelpers[vid]->getGain() < que2->getMingain())//we want most negative gain
+    {
+      que2->setMingain(vhelpers[vid]->getGain());
+      que2->setVertextoswap(v->getVertexId());
+      que2->setSwapid(i);
+    }
+  }
+
+  for(i=0;i<que1->q.size();i++)
+  {
+    int uid=que1->q[i];
+    swap = true; ei=-1;
+    Vertex *u=(Vertex *)&(ogr->vertices[uid]);
+
+    while(1) {
+      ei++;
+      if(swap==true && ei==u->sendToList.size())
+      { swap=false; ei=0;}
+
+      if(swap==false && ei==u->recvFromList.size())
+      { swap=true; ei=-1; break;}
+
+      if(swap)
+      {
+       wid=u->sendToList[ei].getNeighborId();
+       edge = (Edge *)&(u->sendToList[ei]);
+      }
+      else
+      {
+       wid=u->recvFromList[ei].getNeighborId();
+       edge = (Edge *)&(u->recvFromList[ei]);
+      }
+
+      Vertex *w=(Vertex *)&(ogr->vertices[wid]);
+      if(vhelpers[wid]->getLevel()==level && vhelpers[wid]->getPartition()==(2*parent-1))
+       vhelpers[uid]->incEdgestopart1(edge->getNumBytes());
+    }
+
+  }    
+  *initialedgecut=edgecut;
+  //figure out which vertex to swap out of boundaryline1
+  //by this time we know edgestopart2 for every vertex in que1
+  adjustgain(ogr,partition1, que1);
+}
+
+//precondition - edgestopart1 and edgestopart2 must be known for every vertex in queue
+void adjustgain(ObjGraph *ogr,vector<Vertex *> &partition, BQueue *que)
+{
+  int i;
+  int bdry=que->getBoundary();
+  que->setMingain(INT_MAX);
+  que->setVertextoswap(-1);
+  que->setSwapid(-1);
+
+  for (i=0;i<que->q.size();i++)//for each vertex u in que
+  {
+    int uid=que->q[i];
+    Vertex *u =(Vertex *)&(ogr->vertices[uid]);
+
+    if(bdry==1)
+    {
+      vhelpers[uid]->setGain(vhelpers[uid]->getEdgestopart1() - vhelpers[uid]->getEdgestopart2());
+    }
+    else if(bdry==2)
+    {
+      vhelpers[uid]->setGain(vhelpers[uid]->getEdgestopart2() - vhelpers[uid]->getEdgestopart1());
+    }
+    if(vhelpers[uid]->getGain() < que->getMingain())//we want most negative gain
+    {  
+      que->setMingain(vhelpers[uid]->getGain());
+      que->setVertextoswap(u->getVertexId());
+      que->setSwapid(i);
+    }
+  }
+}
+
+// Fiduccia Mattheyses boundary refinement algorithm
+void RefineBoundary(ObjGraph *ogr,vector<Vertex *> &partition1, vector<Vertex *> &partition2, BQueue *que1, BQueue *que2, int runs, int initialedgecut, int parent, double part1load, double part2load, double ratio)
+{
+  int r=runs;
+  int t;
+  if(que1->q.size()<que2->q.size())
+    t=que1->q.size();
+  else t=que2->q.size();
+  if(t<r) r=t;
+  if(r==0) return;
+
+  int newedgecut=initialedgecut;
+
+  for(int i=0;i<r;i++)
+  {
+    if((part1load/(part1load+part2load))>ratio)
+    {
+      if(partition1.size()>1 && que1->q.size()>0)//because if part1 has only one vertex which is heavier than the whole part2, swapping it wouldnt make sense
+      {
+       double xfer=(ogr->vertices[que1->getVertextoswap()]).getVertexLoad();
+       part1load-=xfer;
+       part2load+=xfer;
+       newedgecut=modifypartitions(ogr, partition1, partition2, que1, que2, newedgecut, parent);//it also should adjust the new gains of both boundaries and the edgecut
+      }
+    }
+    else{
+      if(partition2.size()>1 && que2->q.size()>0)
+      {
+       double xfer=(ogr->vertices[que2->getVertextoswap()]).getVertexLoad();
+       part2load-=xfer;
+       part1load+=xfer;
+       newedgecut=modifypartitions(ogr, partition1, partition2, que2, que1, newedgecut, parent);//it also should adjust the new gains of both boundaries and the edgecut
+      }
+    }
+
+  }
+}
+
+
+int modifypartitions(ObjGraph *ogr,vector<Vertex *> &partition1, vector<Vertex *> &partition2, BQueue *q1, BQueue *q2,int ec, int parent)
+{
+  int newedgecut;
+  if(q1->getBoundary()==1)//we are swapping vertex out of boundaryline1
+  {
+    int e2=vhelpers[q1->getVertextoswap()]->getEdgestopart2();
+    int e1=vhelpers[q1->getVertextoswap()]->getEdgestopart1();
+    newedgecut=ec-(e2)+(e1);
+    vhelpers[q1->getVertextoswap()]->setPartition(2*parent);
+    Vertex *ptr=removePtr(partition1,q1->getVertextoswap());
+    partition2.push_back(ptr);
+
+  }
+  else if(q1->getBoundary()==2)//we are swapping vertex out of boundaryline2
+  {
+    int e1=vhelpers[q1->getVertextoswap()]->getEdgestopart1();
+    int e2=vhelpers[q1->getVertextoswap()]->getEdgestopart2();
+    newedgecut=ec-(e1)+(e2);
+    vhelpers[q1->getVertextoswap()]->setPartition(2*parent-1);
+    Vertex *ptr=removePtr(partition2,q1->getVertextoswap());
+    partition1.push_back(ptr);
+
+  }
+
+  swapQ1toQ2(ogr,q1,q2,parent);//avoid thrashing, same vertex cannot be swapped more than once in same call
+  adjustgain(ogr,partition1,q1);//not required for last run of KLFM
+  adjustgain(ogr,partition2,q2);       //not required for last run of KLFM
+  return newedgecut;
+}
+
+void swapQ1toQ2(ObjGraph *ogr, BQueue *q1, BQueue *q2, int parent)
+{
+  Vertex *vert=removeinSwap(ogr,q1,q2,parent);//remove vertex from q1
+  //removevert also removes or brings in new vertices in the queues, so the edgestopart1 and edgestopart2 are calculated for new vertices inside removevert
+  q2->push(vert);
+}
+
+Vertex * removeinSwap(ObjGraph *ogr,BQueue *q1, BQueue *q2, int parent)
+{
+  int i,j,ei=-1, uid, wid, einested=-1;
+  Edge *edge, *edgenested;
+  bool swap=true, swapnested=true;
+  Vertex *v=(Vertex *)&(ogr->vertices[q1->getVertextoswap()]);
+  //edge counts of v do not change
+  //Adjust edgecounts of neighbours, verify whether any additions or deletions happen to the boundarylines
+
+  while(1) {
+    ei++;
+    if(swap==true && ei==v->sendToList.size())
+    { swap=false; ei=0;}
+    if(swap==false && ei==v->recvFromList.size())
+    { swap=true; ei=-1; break;}
+    if(swap)
+    {
+      uid=v->sendToList[ei].getNeighborId();
+      edge=(Edge *)&(v->sendToList[ei]);
+    }
+    else
+    {
+      uid=v->recvFromList[ei].getNeighborId();
+      edge=(Edge *)&(v->recvFromList[ei]);
+    }
+
+    Vertex *u=(Vertex *)&(ogr->vertices[uid]);
+
+    if(q1->getBoundary()==1)//vertex being removed out of boundaryline1
+    {
+      if((vhelpers[uid]->getBoundaryline()==true) && vhelpers[uid]->getLevel()==level)//do for both partitions
+      {
+       vhelpers[uid]->incEdgestopart2(edge->getNumBytes());
+       vhelpers[uid]->decEdgestopart1(edge->getNumBytes());
+      }
+      else if(vhelpers[uid]->getPartition()==(2*parent-1) && vhelpers[uid]->getLevel()==level && vhelpers[uid]->getBoundaryline()==false)
+       //nbr u of v which was in part1, but not in boundaryline1, is now introduced to boundaryline1
+      {
+       //new to boundaryline1, hence calculate edgestopart2
+       vhelpers[uid]->setEdgestopart2(edge->getNumBytes());
+       vhelpers[uid]->setEdgestopart1(0);
+
+       while(1) {
+         einested++;
+         if(swapnested==true && einested==u->sendToList.size())
+         { swapnested=false; einested=0;}
+         if(swapnested==false && einested==u->recvFromList.size())
+         { swapnested=true; einested=-1; break;}
+         if(swapnested)
+         {
+           wid=u->sendToList[einested].getNeighborId();
+           edgenested=(Edge *)&(u->sendToList[einested]);
+         }
+         else
+         {
+           wid=u->recvFromList[einested].getNeighborId();
+           edgenested = (Edge *)&(u->recvFromList[einested]);
+         }
+         Vertex *w=(Vertex *)&(ogr->vertices[wid]);
+         if(vhelpers[wid]->getLevel()==level && vhelpers[wid]->getPartition()==(2*parent-1))
+           vhelpers[uid]->incEdgestopart1(edgenested->getNumBytes());
+       }
+       q1->push(u);//also sets boundaryline=true
+      }
+      if(vhelpers[uid]->getPartition()==2*parent && vhelpers[uid]->getLevel()==level && vhelpers[uid]->getBoundaryline()==true && vhelpers[uid]->getEdgestopart1()==0)
+       //vertex in part2, on boundaryline2, now not a part of boundaryline2
+      {
+       q2->removeComplete(u);//q1 is queue1, q2 is queue2//sets boundaryline=false
+      }
+    }
+    else if(q1->getBoundary()==2)//vertex being removed out of boundaryline2
+    {
+      if(vhelpers[uid]->getBoundaryline()==true && vhelpers[uid]->getLevel()==level)//do for both partitions
+      {
+       vhelpers[uid]->incEdgestopart1(edge->getNumBytes());
+       vhelpers[uid]->decEdgestopart2(edge->getNumBytes());
+      }
+      else if(vhelpers[uid]->getPartition()==2*parent && vhelpers[uid]->getLevel()==level && vhelpers[uid]->getBoundaryline()==false)
+       //vertex which was in part2, but not in boundaryline2, is now introduced to boundaryline2
+      {
+       //new to boundaryline2
+       vhelpers[uid]->setEdgestopart1(edge->getNumBytes());
+       vhelpers[uid]->setEdgestopart2(0);
+
+       while(1) {
+         einested++;
+         if(swapnested==true && einested==u->sendToList.size())
+         { swapnested=false; einested=0;}
+         if(swapnested==false && einested==u->recvFromList.size())
+         { swapnested=true; einested=-1; break;}
+         if(swapnested)
+         {
+           wid=u->sendToList[einested].getNeighborId();
+           edgenested = (Edge *)&(u->sendToList[einested]);
+         }
+         else
+         {
+           wid=u->recvFromList[einested].getNeighborId();
+           edgenested= (Edge *)&(u->recvFromList[einested]);
+         }
+
+         Vertex *w=(Vertex *)&(ogr->vertices[wid]);
+         if(vhelpers[wid]->getLevel()==level && vhelpers[wid]->getPartition()==(2*parent))
+           vhelpers[uid]->incEdgestopart2(edgenested->getNumBytes());
+       }
+
+       q1->push(u);//q1 is boundaryline2
+      }
+      if(vhelpers[uid]->getPartition()==(2*parent-1) && vhelpers[uid]->getLevel()==level && vhelpers[uid]->getBoundaryline()==true && vhelpers[uid]->getEdgestopart2()==0)
+       //vertex in part1, on boundaryline1, now not a part of boundaryline1
+      {
+       q2->removeComplete(u);//q1 is queue1, q2 is queue2
+      }
+    }
+  }
+
+  //remove vertex v from q1 to swap into q2
+  /*q1->removeToSwap(v); */
+  q1->removeComplete(v);       
+  return v;
+}
+
+Vertex * removePtr(vector<Vertex *> &vec,int id)
+{
+  int i;
+  for(i=0;i<vec.size();i++)
+  {
+    if(vec[i]->getVertexId()==id)
+    {
+      Vertex *ptr=vec[i];
+      vec[i]=vec.back();
+      vec.pop_back();
+      return ptr;
+    }
+  }
+  return NULL;
+}
+
+#include "RecBipartLB.def.h"
+/*@}*/
diff --git a/src/ck-ldb/RecBipartLB.ci b/src/ck-ldb/RecBipartLB.ci
new file mode 100644 (file)
index 0000000..61911a0
--- /dev/null
@@ -0,0 +1,8 @@
+module RecBipartLB {
+  extern module CentralLB;
+  initnode void lbinit (void);
+
+  group [migratable] RecBipartLB : CentralLB {
+    entry void RecBipartLB(const CkLBOptions &);
+  };
+};
diff --git a/src/ck-ldb/RecBipartLB.h b/src/ck-ldb/RecBipartLB.h
new file mode 100644 (file)
index 0000000..7de9fbe
--- /dev/null
@@ -0,0 +1,97 @@
+/** \file RecBipartLB.h
+ *  Author: Swapnil Ghike
+ *  Date Created:
+ *  E-mail:ghike2@illinois.edu
+ *
+ */
+
+/**
+ *  \addtogroup CkLdb
+ */
+
+/*@{*/
+
+#ifndef _RECBIPARTLB_H_
+#define _RECBIPARTLB_H_
+
+#include "CentralLB.h"
+#include "RecBipartLB.decl.h"
+
+/**
+ *  Class to contain additional data about the vertices in object graph
+ */
+class Vertex_helper {
+  public:
+    inline int getPartition(){ return partition; }
+    inline void setPartition(int p){partition=p; }
+    inline bool getMarked(){ return marked; }
+    inline void setMarked(bool v){ marked=v;}
+    inline bool getBoundaryline(){return boundaryline;}
+    inline void setBoundaryline(bool v){ boundaryline=v;}
+    inline int getEdgestopart1(){return edgestopart1;}
+    inline int getEdgestopart2(){return edgestopart2;}
+    inline void setEdgestopart1(int v){edgestopart1=v;}
+    inline void setEdgestopart2(int v){edgestopart2=v;}
+    inline void incEdgestopart1(int v){edgestopart1+=v ;}
+    inline void incEdgestopart2(int v){edgestopart2+=v;}
+    inline void decEdgestopart1(int v){edgestopart1-=v;}
+    inline void decEdgestopart2(int v){edgestopart2-=v;}
+    inline void setLevel(int l){level=l;}
+    inline int getLevel(){return level;}
+    inline int getGain(){return gain;}
+    inline void setGain(int v){gain=v;};
+
+  private:
+    int partition;      // partition to which this vertex currently belongs
+    bool marked;       // already marked or not
+    bool boundaryline;  //on boundaryline of a partition or not
+    int edgestopart1; //only for boundaryline vertices
+    int edgestopart2; //only for boundaryline vertices
+    int gain;          //gain if this vertex switched partitions
+    int level;
+};
+
+/**
+ *  Class to handle the boundaries of child partitions
+ */
+class BQueue {
+  public:
+    std::vector<int> q;
+
+    BQueue(short b){
+      forboundary=b;
+    }
+
+    inline int getMingain(){return mingain;}
+    inline void setMingain(int v){mingain=v;}
+    inline int getVertextoswap(){return vertextoswap;}
+    inline void setVertextoswap(int v){vertextoswap=v;}
+    inline int getSwapid(){return swapid;}
+    inline void setSwapid(int v){swapid=v;}
+    inline short getBoundary(){return forboundary;}
+    void push(Vertex *);
+    void removeComplete(Vertex *);
+    void removeToSwap(Vertex *);
+
+  private:
+    int mingain;
+    int vertextoswap;
+    int swapid;
+    short forboundary;
+};
+
+class RecBipartLB : public CentralLB {
+  public:
+    RecBipartLB(const CkLBOptions &opt);
+    RecBipartLB(CkMigrateMessage *m) : CentralLB (m) { };
+
+    void work(LDStats *stats);
+    void pup(PUP::er &p) { CentralLB::pup(p); }
+
+  private:
+    CmiBool QueryBalanceNow(int _step);
+};
+
+#endif /* _RECBIPARTLB_H_ */
+
+/*@}*/
index 3f63f331c62c1247c4b3247bc6cac4e0be7972ad..e0c4895c5b2d41cf856f3d05af600cef917f3183 100644 (file)
@@ -45,6 +45,7 @@ OrbLB.decl.h OrbLB.def.h: OrbLB.ci.stamp
 PathHistory.decl.h PathHistory.def.h: pathHistory.ci.stamp
 PhasebyArrayLB.decl.h PhasebyArrayLB.def.h: PhasebyArrayLB.ci.stamp
 RandCentLB.decl.h RandCentLB.def.h: RandCentLB.ci.stamp
+RecBipartLB.decl.h RecBipartLB.def.h: RecBipartLB.ci.stamp
 RecBisectBfLB.decl.h RecBisectBfLB.def.h: RecBisectBfLB.ci.stamp
 RefineCommLB.decl.h RefineCommLB.def.h: RefineCommLB.ci.stamp
 RefineKLB.decl.h RefineKLB.def.h: RefineKLB.ci.stamp
index 07521cf0ded3275edcf500e00b835d60b6868165..d124afb6fa0ad5d0a52edf4610c8fb2ca31ad244 100644 (file)
@@ -1438,11 +1438,11 @@ EveryLB.o: EveryLB.C LBDatabase.h lbdb.h converse.h conv-config.h \
  GreedyAgentLB.decl.h GreedyCommLB.decl.h GreedyLB.decl.h \
  NeighborCommLB.decl.h NborBaseLB.decl.h NeighborLBMsg.h \
  NeighborLB.decl.h OrbLB.decl.h PhasebyArrayLB.decl.h RandCentLB.decl.h \
- RefineLB.decl.h RefineCommLB.decl.h RotateLB.decl.h ComboCentLB.decl.h \
GraphPartLB.decl.h GraphBFTLB.decl.h GridCommLB.decl.h \
- GridCommRefineLB.decl.h GridHybridLB.decl.h GridHybridSeedLB.decl.h \
- GridMetisLB.decl.h HbmLB.decl.h HybridLBMsg.h HybridLB.decl.h \
- HybridBaseLB.decl.h RefineKLB.decl.h RefineTopoLB.decl.h \
+ RecBipartLB.decl.h RefineLB.decl.h RefineCommLB.decl.h RotateLB.decl.h \
ComboCentLB.decl.h GraphPartLB.decl.h GraphBFTLB.decl.h \
+ GridCommLB.decl.h GridCommRefineLB.decl.h GridHybridLB.decl.h \
+ GridHybridSeedLB.decl.h GridMetisLB.decl.h HbmLB.decl.h HybridLBMsg.h \
+ HybridLB.decl.h HybridBaseLB.decl.h RefineKLB.decl.h RefineTopoLB.decl.h \
  TopoCentLB.decl.h TopoLB.decl.h WSLB.decl.h EveryLB.def.h
        $(CHARMC) -c -I. EveryLB.C
 
@@ -1466,7 +1466,8 @@ CommonLBs.o: CommonLBs.C LBDatabase.h lbdb.h converse.h conv-config.h \
  GreedyAgentLB.decl.h GreedyCommLB.decl.h GreedyLB.decl.h \
  NeighborCommLB.decl.h NborBaseLB.decl.h NeighborLBMsg.h \
  NeighborLB.decl.h OrbLB.decl.h PhasebyArrayLB.decl.h RandCentLB.decl.h \
- RefineLB.decl.h RefineCommLB.decl.h RotateLB.decl.h CommonLBs.def.h
+ RecBipartLB.decl.h RefineLB.decl.h RefineCommLB.decl.h RotateLB.decl.h \
+ CommonLBs.def.h
        $(CHARMC) -c -I. CommonLBs.C
 
 BlockLB.o: BlockLB.C BlockLB.decl.h charm++.h charm.h converse.h \
@@ -1677,6 +1678,25 @@ RandCentLB.o: RandCentLB.C RandCentLB.h CentralLB.h BaseLB.h LBDatabase.h \
  RandCentLB.decl.h RandCentLB.def.h
        $(CHARMC) -c -I. RandCentLB.C
 
+RecBipartLB.o: RecBipartLB.C RecBipartLB.h CentralLB.h BaseLB.h \
+ LBDatabase.h lbdb.h converse.h conv-config.h conv-autoconfig.h \
+ conv-common.h conv-mach.h conv-mach-opt.h pup_c.h queueing.h conv-cpm.h \
+ conv-cpath.h conv-qd.h conv-random.h conv-lists.h conv-trace.h \
+ persistent.h debug-conv.h charm.h pup.h middle.h middle-conv.h \
+ LBDBManager.h cklists.h LBObj.h LBOM.h LBComm.h LBMachineUtil.h lbdb++.h \
+ LBDatabase.decl.h charm++.h ckbitvector.h ckstream.h init.h \
+ ckhashtable.h debug-charm.h simd.h CkMarshall.decl.h cksection.h \
+ ckcallback.h conv-ccs.h sockRoutines.h ccs-server.h ckobjQ.h \
+ ckreduction.h CkReduction.decl.h cknodegroupreduction.h \
+ CkArrayReductionMgr.decl.h ckmemcheckpoint.h CkMemCheckpoint.decl.h \
+ readonly.h ckarray.h cklocation.h CkLocation.decl.h CkArray.decl.h \
+ CkFutures.decl.h charisma.h charisma.decl.h tempo.h tempo.decl.h \
+ waitqd.h waitqd.decl.h sdag.h ckcheckpoint.h CkCheckpoint.decl.h \
+ ckevacuation.h ckarrayreductionmgr.h trace.h trace-bluegene.h envelope.h \
+ NullLB.decl.h BaseLB.decl.h CentralLB.decl.h CentralLBMsg.h \
+ RecBipartLB.decl.h ckgraph.h RecBipartLB.def.h
+       $(CHARMC) -c -I. RecBipartLB.C
+
 RefineLB.o: RefineLB.C elements.h converse.h conv-config.h \
  conv-autoconfig.h conv-common.h conv-mach.h conv-mach-opt.h pup_c.h \
  queueing.h conv-cpm.h conv-cpath.h conv-qd.h conv-random.h conv-lists.h \