Since earlier refineKLB did not use all of K moves, I've added further (greedy, 2...
authorTarun Agarwal <tagarwal@uiuc.edu>
Wed, 18 May 2005 20:35:45 +0000 (20:35 +0000)
committerTarun Agarwal <tagarwal@uiuc.edu>
Wed, 18 May 2005 20:35:45 +0000 (20:35 +0000)
src/ck-ldb/RefineKLB.C
src/ck-ldb/RefineKLB.h
src/ck-ldb/RefinerApprox.C

index 99e2413888cb77e651488c2b84023f5196bc5fc3..cfe37e03c5dff0797a90f6db70a27c1b1b87bf4d 100644 (file)
@@ -15,6 +15,7 @@
 #include "cklists.h"
 
 #include "RefineKLB.h"
+//#include "heap.h"
 
 CreateLBFunc_Def(RefineKLB, "Move objects away from overloaded processor to reach average");
 
@@ -42,18 +43,42 @@ void RefineKLB::work(BaseLB::LDStats* stats, int count)
   // Get a new buffer to refine into
   int* to_procs = RefinerApprox::AllocProcs(count,stats);
 
-  RefinerApprox refiner(1.003);  // overload tolerance=1.05
+  RefinerApprox refiner(1.003);  // overload tolerance=1.003
 
   refiner.Refine(count,stats,from_procs,to_procs,_lb_args.percentMovesAllowed());
 
   // Save output
-  for(obj=0;obj<stats->n_objs;obj++) {
-      int pe = stats->from_proc[obj];
-      if (to_procs[obj] != pe) {
-       // CkPrintf("[%d] Obj %d migrating from %d to %d\n",
-       //       CkMyPe(),obj,pe,to_procs[obj]);
-       stats->to_proc[obj] = to_procs[obj];
+  int numMoves=0;
+  for(obj=0;obj<stats->n_objs;obj++) 
+  {
+    int pe = stats->from_proc[obj];
+    if (to_procs[obj] != pe) 
+    {
+      // CkPrintf("[%d] Obj %d migrating from %d to %d\n",
+      //        CkMyPe(),obj,pe,to_procs[obj]);
+      stats->to_proc[obj] = to_procs[obj];
+      numMoves++;
+    }
+  }
+  int maxMoves=(stats->n_objs)*(_lb_args.percentMovesAllowed());
+  int availableMoves=maxMoves-numMoves;
+
+  //Perform Additional Moves in Greedy Fashion
+  if(availableMoves>0)
+  {
+    int *to_procs2=new int[stats->n_objs];
+    performGreedyMoves(count,stats,to_procs,to_procs2,availableMoves);
+
+    int nmoves2=0;
+    for(obj=0;obj<stats->n_objs;obj++)
+    {
+      if(to_procs2[obj]!=to_procs[obj])
+      {
+        stats->to_proc[obj]=to_procs2[obj];
+        nmoves2++;
       }
+    }
+    delete[] to_procs2;
   }
 
   // Free the refine buffers
@@ -61,6 +86,97 @@ void RefineKLB::work(BaseLB::LDStats* stats, int count)
   RefinerApprox::FreeProcs(to_procs);
 };
 
+void RefineKLB::performGreedyMoves(int count, BaseLB::LDStats* stats,int *from_procs, int *to_procs, int numMoves)
+{
+  //Calculate load per proc and objs per proc
+  int *objPerProc=new int[count];
+  double *loadPerProc=new double[count];
+  int i;
+  for(i=0;i<count;i++)
+  {
+    objPerProc[i]=0;
+    loadPerProc[i]=stats->procs[i].bg_walltime;
+  }
+  for(i=0;i<stats->n_objs;i++)
+  {
+    to_procs[i]=from_procs[i];
+    objPerProc[from_procs[i]]++;
+    loadPerProc[from_procs[i]]+=(stats->objData[i]).wallTime;
+  }
+
+  //Create a MaxHeap to select most-loaded procs
+  maxHeap *procLoad=new maxHeap(count);
+  for(i=0;i<count;i++)
+  {
+    InfoRecord *rec=new InfoRecord();
+    rec->load=loadPerProc[i];
+    rec->Id=i;
+    procLoad->insert(rec);
+  }
+
+  //Create a MaxHeap(for every proc) for selecting heaviest computes from each proc
+  maxHeap **procObjs=new maxHeap*[count];
+  for(i=0;i<count;i++)
+  {
+    procObjs[i]=new maxHeap(objPerProc[i]);
+  }
+  for(i=0;i<stats->n_objs;i++)
+  {
+    if((stats->objData[i]).migratable == CmiFalse)
+      continue;
+    InfoRecord *rec=new InfoRecord();
+    rec->load=(stats->objData[i]).wallTime;
+    rec->Id=i;
+    procObjs[from_procs[i]]->insert(rec);
+  }
+
+  //Pick k'(=numMoves) computes one-by-one by picking largest computes from most -loaded procs;
+  //Place in unassignedHeap;
+  maxHeap *unassignedComputes=new maxHeap(numMoves);
+  for(i=0;i<numMoves;i++)
+  {
+    InfoRecord *maxProc=procLoad->deleteMax();
+    
+    InfoRecord *maxObj=procObjs[maxProc->Id]->deleteMax();
+    unassignedComputes->insert(maxObj);
+
+    maxProc->load-=maxObj->load;
+    loadPerProc[maxProc->Id]=maxProc->load;
+
+    procLoad->insert(maxProc);
+  }
+
+  //Assign one-by-one to least-loaded proc
+  minHeap *leastLoadedP=new minHeap(count);
+  for(i=0;i<count;i++)
+  {
+    leastLoadedP->insert(procLoad->deleteMax());
+  }
+
+  for(i=0;i<numMoves;i++)
+  {
+    InfoRecord *c=unassignedComputes->deleteMax();
+
+    InfoRecord *proc=leastLoadedP->deleteMin();
+    proc->load+=c->load;
+    leastLoadedP->insert(proc);
+
+    to_procs[c->Id]=proc->Id;
+    delete c;
+  }
+
+  //free up memory
+  delete[] objPerProc;
+  delete[] loadPerProc;
+  for(i=0;i<count;i++)
+  {
+    delete procObjs[i];
+  }
+  delete procObjs;
+  delete unassignedComputes;
+  delete leastLoadedP;
+}
+
 #include "RefineKLB.def.h"
 
 /*@}*/
index fca8bc23969e3b38a9f9de88218e537e80a3bbe8..99cf55599907e236064483aa1fd0fc92910acc6d 100644 (file)
 
 #include "CentralLB.h"
 #include "RefinerApprox.h"
-#include "RefineKLB.decl.h"
 
 class minheap;
 class maxheap;
+#include "RefineKLB.decl.h"
 
 #include "elements.h"
 #include "heap.h"
@@ -37,6 +37,7 @@ protected:
   double averageLoad;
 
   double overLoad;
+  void performGreedyMoves(int count, BaseLB::LDStats* stats,int *from_procs, int *to_procs, int numMoves);
 
 public:
   RefineKLB(const CkLBOptions &);
index 27c0eb4f3e0c058ab78d5184b59bcb0d299de342..ba379713a3049e71347845f35e6d45108afdf6a4 100644 (file)
@@ -85,33 +85,6 @@ void RefinerApprox::reinitAssignment()
     }
 }
 
-/*
-void RefinerApprox::multirefine(int num_moves)
-{
-    computeAverage();
-    double avg=averageLoad;
-    double max=computeMax();
-
-    //Compute the thresholds for OPT that can effect moves
-    int numThresholds=numComputes+P;
-    double *threshold=new double[numThresholds];
-    
-    int i;
-    int nMoves;
-    for(i=0;i<numThresholds && nMoves>num_moves ;i++)
-    {
-       reinitAssignment();
-       nMoves=refine(threshold[i]);
-    }
-    if(nMoves>num_moves)
-    {
-       if(_lb_debug) CkPrintf("Mutirefine failed ");
-    }
-
-    delete [] threshold;
-}
-
-*/
 void RefinerApprox::multirefine(int num_moves)
 {
   computeAverage();
@@ -150,58 +123,6 @@ void RefinerApprox::multirefine(int num_moves)
   if(_lb_debug) CkPrintf("Refined within %d moves\n",numMoves);
   return;
 }
-/*
-int Refiner::multirefine()
-{
-  computeAverage();
-  double avg = averageLoad;
-  double max = computeMax();
-
-  const double overloadStep = 0.01;
-  const double overloadStart = 1.001;
-  double dCurOverload = max / avg;
-                                                                                
-  int minOverload = 0;
-  int maxOverload = (int)((dCurOverload - overloadStart)/overloadStep + 1);
-  double dMinOverload = minOverload * overloadStep + overloadStart;
-  double dMaxOverload = maxOverload * overloadStep + overloadStart;
-  int curOverload;
-  int refineDone = 0;
-  if (_lb_debug)
-    CmiPrintf("dMinOverload: %f dMaxOverload: %f\n", dMinOverload, dMaxOverload);
-                                                                                
-  overLoad = dMinOverload;
-  if (refine())
-    refineDone = 1;
-  else {
-    overLoad = dMaxOverload;
-    if (!refine()) {
-      CmiPrintf("ERROR: Could not refine at max overload\n");
-      refineDone = 1;
-    }
-  }
-                                                                                
-  // Scan up, until we find a refine that works
-  while (!refineDone) {
-    if (maxOverload - minOverload <= 1)
-      refineDone = 1;
-    else {
-      curOverload = (maxOverload + minOverload ) / 2;
-                                                                                
-      overLoad = curOverload * overloadStep + overloadStart;
-      if (_lb_debug)
-      CmiPrintf("Testing curOverload %d = %f [min,max]= %d, %d\n", curOverload, overLoad, minOverload, maxOverload);
-      if (refine())
-        maxOverload = curOverload;
-      else
-        minOverload = curOverload;
-    }
-  }
-  return 1;
-}
-*/
-
-/****************************************/
 
 Set * RefinerApprox::removeBiggestSmallComputes(int num,processorInfo * p,double opt)
 {