new LDStats. totally new interface for calling Strategy using LDStats.
authorGengbin Zheng <gzheng@illinois.edu>
Thu, 8 May 2003 07:16:51 +0000 (07:16 +0000)
committerGengbin Zheng <gzheng@illinois.edu>
Thu, 8 May 2003 07:16:51 +0000 (07:16 +0000)
clean up duplicate code in RandCentLB.C/RandRefLB.C and GreedyLB.C/GreedyRefLB.C.

23 files changed:
src/ck-ldb/BaseLB.h
src/ck-ldb/CentralLB.C
src/ck-ldb/CentralLB.h
src/ck-ldb/Comm1LB.C
src/ck-ldb/CommLB.C
src/ck-ldb/GreedyLB.C
src/ck-ldb/GreedyLB.h
src/ck-ldb/GreedyRefLB.C
src/ck-ldb/GreedyRefLB.h
src/ck-ldb/LBDatabase.C
src/ck-ldb/MetisLB.C
src/ck-ldb/ObjGraph.C
src/ck-ldb/ObjGraph.h
src/ck-ldb/OrbLB.C
src/ck-ldb/RandCentLB.C
src/ck-ldb/RandCentLB.h
src/ck-ldb/RandRefLB.C
src/ck-ldb/RandRefLB.h
src/ck-ldb/RecBisectBfLB.C
src/ck-ldb/RefineLB.C
src/ck-ldb/Refiner.C
src/ck-ldb/Refiner.h
src/ck-ldb/lbdb.h

index eae63386e5eb451f2109cf7856b12f12a6de62ba..acf2e229e1c927a0981c20220f9d4d395a7b3cef 100644 (file)
@@ -36,6 +36,7 @@ public:
 
 /// migration decision for an obj.
 struct MigrateInfo {  
+    int index;   // object index in objData array
     LDObjHandle obj;
     int from_pe;
     int to_pe;
index 51ebd7702942f4475691e19473cd06f5d9829533..2762012cd1ddd7d9ac1911ddc529838231ed1926 100644 (file)
@@ -22,12 +22,12 @@ char ** avail_vector_address;
 int * lb_ptr;
 int load_balancer_created;
 
+#define LB_DUMP_MSG       0
+
 #if CMK_LBDB_ON
 
 static void getPredictedLoad(CentralLB::LDStats* stats, int count, 
-                      LBMigrateMsg* msg, double *peLoads, double &, double &);
-static int FindPEAfterMigration(LDObjid& id, CentralLB::LDStats* stats, int count,
-                                                        LBMigrateMsg* msg, int bCheckStats);
+                          LBMigrateMsg *, double *peLoads, double &, double &);
 
 void CreateCentralLB()
 {
@@ -85,7 +85,9 @@ CentralLB::CentralLB()
   for(int i=0; i < CkNumPes(); i++)
     statsMsgsList[i] = 0;
 
-  statsDataList = new LDStats[CkNumPes()];
+  statsData = new LDStats;
+  statsData->procs = new ProcStats[CkNumPes()];
+
   myspeed = theLbdb->ProcessorSpeed();
   theLbdb->CollectStatsOn();
   migrates_completed = 0;
@@ -179,6 +181,33 @@ void CentralLB::Migrated(LDObjHandle h)
   }
 }
 
+// build data from buffered msg
+void CentralLB::buildStats()
+{
+    statsData->count = stats_msg_count;
+    statsData->objData = new LDObjData[statsData->n_objs];
+    statsData->from_proc = new int[statsData->n_objs];
+    statsData->to_proc = new int[statsData->n_objs];
+    statsData->commData = new LDCommData[statsData->n_comm];
+    int nobj = 0;
+    int ncom = 0;
+    for (int pe=0; pe<stats_msg_count; pe++) {
+       int i;
+       CLBStatsMsg *msg = statsMsgsList[pe];
+       for (i=0; i<msg->n_objs; i++) {
+         statsData->from_proc[nobj] = statsData->to_proc[nobj] = pe;
+        statsData->objData[nobj] = msg->objData[i];
+        nobj++;
+       }
+       for (i=0; i<msg->n_comm; i++) {
+        statsData->commData[ncom] = msg->commData[i];
+        ncom++;
+       }
+       delete msg;
+       statsMsgsList[pe]=0;
+    }
+}
+
 void CentralLB::ReceiveStats(CLBStatsMsg *m)
 {
   int proc;
@@ -199,26 +228,26 @@ void CentralLB::ReceiveStats(CLBStatsMsg *m)
             pe);
   } else {
     statsMsgsList[pe] = m;
-    statsDataList[pe].total_walltime = m->total_walltime;
-    statsDataList[pe].total_cputime = m->total_cputime;
+    struct ProcStats &procStat = statsData->procs[pe];
+    procStat.total_walltime = m->total_walltime;
+    procStat.total_cputime = m->total_cputime;
     if (lb_ignoreBgLoad) {
-    statsDataList[pe].idletime = 0.0;
-    statsDataList[pe].bg_walltime = 0.0;
-    statsDataList[pe].bg_cputime = 0.0;
+    procStat.idletime = 0.0;
+    procStat.bg_walltime = 0.0;
+    procStat.bg_cputime = 0.0;
     }
     else {
-    statsDataList[pe].idletime = m->idletime;
-    statsDataList[pe].bg_walltime = m->bg_walltime;
-    statsDataList[pe].bg_cputime = m->bg_cputime;
+    procStat.idletime = m->idletime;
+    procStat.bg_walltime = m->bg_walltime;
+    procStat.bg_cputime = m->bg_cputime;
     }
-    statsDataList[pe].pe_speed = m->pe_speed;
-    statsDataList[pe].utilization = 1.0;
-    statsDataList[pe].available = CmiTrue;
-
-    statsDataList[pe].n_objs = m->n_objs;
-    statsDataList[pe].objData = m->objData;
-    statsDataList[pe].n_comm = m->n_comm;
-    statsDataList[pe].commData = m->commData;
+    procStat.pe_speed = m->pe_speed;
+    procStat.utilization = 1.0;
+    procStat.available = CmiTrue;
+    procStat.n_objs = m->n_objs;
+
+    statsData->n_objs += m->n_objs;
+    statsData->n_comm += m->n_comm;
     stats_msg_count++;
   }
 
@@ -227,15 +256,18 @@ void CentralLB::ReceiveStats(CLBStatsMsg *m)
 //    double strat_start_time = CmiWallTimer();
 
 //    CkPrintf("Before setting bitmap\n");
-    for(proc = 0; proc < clients; proc++)
-      statsDataList[proc].available = (CmiBool)avail_vector[proc];
+    // build data
+    buildStats();
 
     // if this is the step at which we need to dump the database
     simulation();
 
+    for(proc = 0; proc < clients; proc++)
+      statsData->procs[proc].available = (CmiBool)avail_vector[proc];
+
 //    CkPrintf("Before Calling Strategy\n");
 
-    LBMigrateMsg* migrateMsg = Strategy(statsDataList,clients);
+    LBMigrateMsg* migrateMsg = Strategy(statsDataclients);
 
 //    CkPrintf("returned successfully\n");
     int num_proc = CkNumPes();
@@ -253,25 +285,11 @@ void CentralLB::ReceiveStats(CLBStatsMsg *m)
 //  CkPrintf("calling recv migration\n");
     thisProxy.ReceiveMigration(migrateMsg);
 
-#if 0
-    {
-      char fname[1024];
-      static int phase = 0;
-      if (QueryDumpData()) {
-        sprintf(fname, "load%d", phase);
-       writeStatsMsgs(fname);
-      }
-      phase ++;
-    }
-#endif
-
     // Zero out data structures for next cycle
     // CkPrintf("zeroing out data\n");
-    for(int i=0; i < clients; i++) {
-      delete statsMsgsList[i];
-      statsMsgsList[i]=0;
-    }
+    statsData->clear();
     stats_msg_count=0;
+
     double strat_end_time = CmiWallTimer();
     //     CkPrintf("Strat elapsed time %f\n",strat_end_time-strat_start_time);
   }
@@ -290,29 +308,26 @@ static int isMigratable(LDObjData **objData, int *len, int count, const LDCommDa
   return 1;
 }
 
+#if 0
 // remove in the LDStats those objects that are non migratable
 void CentralLB::RemoveNonMigratable(LDStats* stats, int count)
 {
   int pe;
   LDObjData **nonmig = new LDObjData*[count];
   int   *lens = new int[count];
-  for (pe=0; pe<count; pe++) {
-    int n_objs = stats[pe].n_objs;
-    if (n_objs == 0) continue;
-    LDObjData *objData = stats[pe].objData; 
+  int n_objs = stats->n_objs;
+    LDObjStats *objStat = stats.objData[n]; 
     int l=-1, h=n_objs;
     while (l<h) {
-      while (objData[l+1].migratable && l<h) l++;
-      while (h>0 && !objData[h-1].migratable && l<h) h--;
+      while (objStat[l+1].data.migratable && l<h) l++;
+      while (h>0 && !objStat[h-1].data.migratable && l<h) h--;
       if (h-l>2) {
-        LDObjData tmp = objData[l+1];
-        objData[l+1] = objData[h-1];
-        objData[h-1] = tmp;
+        LDObjStats tmp = objStat[l+1];
+        objStat[l+1] = objStat[h-1];
+        objStat[h-1] = tmp;
       }
-      else 
-        break;
     }
-    stats[pe].n_objs = h;
+    stats->n_objs = h;
     if (n_objs != h) CmiPrintf("Removed %d nonmigratable on pe:%d n_objs:%d migratable:%d\n", n_objs-h, pe, n_objs, h);
     nonmig[pe] = objData+stats[pe].n_objs;
     lens[pe] = n_objs-stats[pe].n_objs;
@@ -322,7 +337,6 @@ void CentralLB::RemoveNonMigratable(LDStats* stats, int count)
       stats[pe].bg_walltime += objData[j].wallTime;
       stats[pe].bg_cputime += objData[j].cpuTime;
     }
-  }
 
   // modify comm data
   for (pe=0; pe<count; pe++) {
@@ -348,6 +362,7 @@ void CentralLB::RemoveNonMigratable(LDStats* stats, int count)
   delete [] nonmig;
   delete [] lens;
 }
+#endif
 
 void CentralLB::ReceiveMigration(LBMigrateMsg *m)
 {
@@ -412,33 +427,43 @@ void CentralLB::ResumeClients()
   theLbdb->ResumeClients();
 }
 
+// default load balancing strategy
 LBMigrateMsg* CentralLB::Strategy(LDStats* stats,int count)
 {
-  for(int j=0; j < count; j++) {
-    int i;
-    LDObjData *odata = stats[j].objData;
-    const int osz = stats[j].n_objs;
+  work(stats, count);
+  return createMigrateMsg(stats, count);
+}
+
+void CentralLB::work(LDStats* stats,int count)
+{
+  int i;
+  for(int pe=0; pe < count; pe++) {
+    struct ProcStats &proc = stats->procs[pe];
 
     CkPrintf(
       "Proc %d Sp %d Total time (wall,cpu) = %f %f Idle = %f Bg = %f %f\n",
-      j,stats[j].pe_speed,stats[j].total_walltime,stats[j].total_cputime,
-      stats[j].idletime,stats[j].bg_walltime,stats[j].bg_cputime);
-    CkPrintf("------------- Object Data: PE %d: %d objects -------------\n",
-            j,osz);
+      pe,proc.pe_speed,proc.total_walltime,proc.total_cputime,
+      proc.idletime,proc.bg_walltime,proc.bg_cputime);
+  }
+
+  int osz = stats->n_objs;
+    CkPrintf("------------- Object Data: %d objects -------------\n",
+            stats->n_objs);
     for(i=0; i < osz; i++) {
+      LDObjData &odata = stats->objData[i];
       CkPrintf("Object %d\n",i);
-      CkPrintf("     id = %d\n",odata[i].id().id[0]);
-      CkPrintf("  OM id = %d\n",odata[i].omID().id);
-      CkPrintf("   Mig. = %d\n",odata[i].migratable);
-      CkPrintf("    CPU = %f\n",odata[i].cpuTime);
-      CkPrintf("   Wall = %f\n",odata[i].wallTime);
+      CkPrintf("     id = %d\n",odata.id().id[0]);
+      CkPrintf("  OM id = %d\n",odata.omID().id);
+      CkPrintf("   Mig. = %d\n",odata.migratable);
+      CkPrintf("    CPU = %f\n",odata.cpuTime);
+      CkPrintf("   Wall = %f\n",odata.wallTime);
     }
 
-    LDCommData *cdata = stats[j].commData;
-    const int csz = stats[j].n_comm;
+    const int csz = stats->n_comm;
 
-    CkPrintf("------------- Comm Data: PE %d: %d records -------------\n",
-            j,csz);
+    CkPrintf("------------- Comm Data: %d records -------------\n",
+            csz);
+    LDCommData *cdata = stats->commData;
     for(i=0; i < csz; i++) {
       CkPrintf("Link %d\n",i);
 
@@ -457,8 +482,10 @@ LBMigrateMsg* CentralLB::Strategy(LDStats* stats,int count)
       CkPrintf("     messages = %d\n",cdata[i].messages);
       CkPrintf("        bytes = %d\n",cdata[i].bytes);
     }
-  }
+}
 
+LBMigrateMsg * CentralLB::createMigrateMsg(LDStats* stats,int count)
+{
   int sizes=0;
   LBMigrateMsg* msg = new(&sizes,1) LBMigrateMsg;
   msg->n_moves = 0;
@@ -484,10 +511,10 @@ void CentralLB::simulation() {
     LBSimulation simResults(LBSimulation::simProcs);
 
     // now pass it to the strategy routine
-    LBMigrateMsg* migrateMsg = Strategy(statsDataList, LBSimulation::simProcs);
+    LBMigrateMsg* migrateMsg = Strategy(statsData, LBSimulation::simProcs);
 
     // now calculate the results of the load balancing simulation
-    FindSimResults(statsDataList, LBSimulation::simProcs, migrateMsg, &simResults);
+    FindSimResults(statsData, LBSimulation::simProcs, migrateMsg, &simResults);
 
     // now we have the simulation data, so print it and exit
     CmiPrintf("Charm++> LBSim: Simulation of one load balancing step done.\n");
@@ -518,11 +545,15 @@ void CentralLB::readStatsMsgs(const char* filename) {
   CmiPrintf("readStatsMsgs for %d pes starts ... \n", stats_msg_count);
   if (LBSimulation::simProcs == 0) LBSimulation::simProcs = stats_msg_count;
 
+#if LB_DUMP_MSG
   // now rebuild new structures
   int tableSize = stats_msg_count;
   if (tableSize < LBSimulation::simProcs) tableSize = LBSimulation::simProcs;
   statsMsgsList = new CLBStatsMsg*[stats_msg_count];
-  statsDataList = new LDStats[tableSize];
+  statsData->clear();
+
+  statsData->procs = new ProcStats[stats_msg_count];
+  statsData->count = stats_msg_count;
 
   for (i = 0; i < stats_msg_count; i++) {
     CLBStatsMsg* m = new CLBStatsMsg;
@@ -537,52 +568,48 @@ void CentralLB::readStatsMsgs(const char* filename) {
     m = (CLBStatsMsg *)EnvToUsr(env);
 
     statsMsgsList[i] = m;
-    statsDataList[i].total_walltime = m->total_walltime;
-    statsDataList[i].total_cputime = m->total_cputime;
-    statsDataList[i].idletime = m->idletime;
+    struct ProcStats &proc = statsData->procs[i];
+
+    proc.total_walltime = m->total_walltime;
+    proc.total_cputime = m->total_cputime;
+    proc.idletime = m->idletime;
 #if 0
-    statsDataList[i].bg_walltime = m->bg_walltime;
-    statsDataList[i].bg_cputime = m->bg_cputime;
+    proc.bg_walltime = m->bg_walltime;
+    proc.bg_cputime = m->bg_cputime;
 #else
-    statsDataList[i].bg_walltime = 0.;
-    statsDataList[i].bg_cputime = 0.;
-#endif
-    statsDataList[i].pe_speed = m->pe_speed;
-    statsDataList[i].utilization = 1.0;
-    statsDataList[i].available = CmiTrue;
-
-    statsDataList[i].n_objs = m->n_objs;
-    statsDataList[i].objData = m->objData;
-    statsDataList[i].n_comm = m->n_comm;
-    statsDataList[i].commData = m->commData;
-#if OLD_FORMAT_COMPATIBLE
-    statsDataList[i].objData = (LDObjData*)((char*)m+(size_t)m->objData);
-    statsDataList[i].commData = (LDCommData*)((char *)m+(size_t)m->commData);
+    proc.bg_walltime = 0.;
+    proc.bg_cputime = 0.;
 #endif
-//CmiPrintf("i:%d bg_walltime: %f total_walltime: %f objData: %d %p comm: %d %p\n", i, m->bg_walltime, m->total_walltime, m->n_objs, m->objData, m->n_comm, m->commData);
+    proc.pe_speed = m->pe_speed;
+    proc.utilization = 1.0;
+    proc.available = CmiTrue;
+    statsData->n_objs += m->n_objs;
+    statsData->n_comm += m->n_comm;
   }
 
-  CmiPrintf("Simulation for %d pes \n", LBSimulation::simProcs);
+  buildStats();
+
+//CmiPrintf("i:%d bg_walltime: %f total_walltime: %f objData: %d %p comm: %d %p\n", i, m->bg_walltime, m->total_walltime, m->n_objs, m->objData, m->n_comm, m->commData);
 
   if (stats_msg_count < LBSimulation::simProcs) {
     for (int i=stats_msg_count; i<LBSimulation::simProcs; i++) {
-      statsMsgsList[i] = NULL;
-      statsDataList[i].total_walltime = 0.0;
-      statsDataList[i].total_cputime = 0.0;
-      statsDataList[i].idletime = 0.0;
-      statsDataList[i].bg_walltime = 0.;
-      statsDataList[i].bg_cputime = 0.;
-      statsDataList[i].pe_speed = 1;
-      statsDataList[i].utilization = 1.0;
-      statsDataList[i].available = CmiTrue;
-
-      statsDataList[i].n_objs = 0;
-      statsDataList[i].objData = NULL;
-      statsDataList[i].n_comm = 0;
-      statsDataList[i].commData = NULL;
-      
+      struct ProcStats &proc = statsData->procs[i];
+      proc.total_walltime = 0.0;
+      proc.total_cputime = 0.0;
+      proc.idletime = 0.0;
+      proc.bg_walltime = 0.;
+      proc.bg_cputime = 0.;
+      proc.pe_speed = 1;
+      proc.utilization = 1.0;
+      proc.available = CmiTrue;
     }
   }
+#else
+    // LBSimulation::simProcs must be set
+  statsData->pup(p);
+#endif
+
+  CmiPrintf("Simulation for %d pes \n", LBSimulation::simProcs);
 
   // file f is closed in the destructor of PUP::fromDisk
   CmiPrintf("ReadStatsMsg from %s completed\n", filename);
@@ -598,6 +625,7 @@ void CentralLB::writeStatsMsgs(const char* filename) {
   PUP::toDisk p(f);
   p|stats_msg_count;
 
+#if LB_DUMP_MSG
   for (i = 0; i < stats_msg_count; i++) {
     CLBStatsMsg *m = statsMsgsList[i];
     envelope *env=UsrToEnv(m);
@@ -605,13 +633,18 @@ void CentralLB::writeStatsMsgs(const char* filename) {
     m = (CLBStatsMsg *)EnvToUsr(env);
     CkPupMessage(p, (void **)&m, 2);
   }
+#else
+  statsData->pup(p);
+#endif
 
   fclose(f);
 
   CmiPrintf("WriteStatsMsgs to %s succeed!\n", filename);
 }
 
-static void getPredictedLoad(CentralLB::LDStats* stats, int count, LBMigrateMsg* msg, double *peLoads, double &minObjLoad, double &maxObjLoad)
+static void getPredictedLoad(CentralLB::LDStats* stats, int count, 
+                             LBMigrateMsg *msg, double *peLoads, 
+                             double &minObjLoad, double &maxObjLoad)
 {
        int* msgSentCount = new int[count]; // # of messages sent by each PE
        int* msgRecvCount = new int[count]; // # of messages received by each PE
@@ -621,79 +654,58 @@ static void getPredictedLoad(CentralLB::LDStats* stats, int count, LBMigrateMsg*
 
        for(i = 0; i < count; i++)
          msgSentCount[i] = msgRecvCount[i] = byteSentCount[i] = byteRecvCount[i] = 0;
-        minObjLoad = 1.0e20;   // I suppose no object load beyond this
+        minObjLoad = 1.0e20;   // I suppose no object load is beyond this
        maxObjLoad = 0.0;
 
+       stats->makeCommHash();
+       // update to_proc according to migration msgs
+       for(int i = 0; i < msg->n_moves; i++) {
+         MigrateInfo &mInfo = msg->moves[i];
+         int idx = stats->getHash(mInfo.obj.objID(), mInfo.obj.omID());
+         CmiAssert(idx != -1);
+          stats->to_proc[idx] = mInfo.to_pe;
+       }
+
        for(pe = 0; pe < count; pe++)
        {
-         peLoads[pe] = stats[pe].bg_walltime;
+         peLoads[pe] = stats->procs[pe].bg_walltime;
+        }
 
-         for(int obj = 0; obj < stats[pe].n_objs; obj++)
-         {
-               double &oload = stats[pe].objData[obj].wallTime;
+       for(int obj = 0; obj < stats->n_objs; obj++)
+       {
+               int pe = stats->to_proc[obj];
+               double &oload = stats->objData[obj].wallTime;
                if (oload < minObjLoad) minObjLoad = oload;
                if (oload > maxObjLoad) maxObjLoad = oload;
                peLoads[pe] += oload;
-         }
        }
 
-       // now for each migration, substract the load of the migrating 
-        // object from the source pe and add it to the destination pe
-       for(int mig = 0; mig < msg->n_moves; mig++)
-       {
-               int from = msg->moves[mig].from_pe;
-               int to = msg->moves[mig].to_pe;
-               double wallTime;
-               int oidx, cidx;
-               
-               // find the cpu time for the object that is migrating
-               for(oidx = 0; oidx < stats[from].n_objs; oidx++)
-                       if(stats[from].objData[oidx].handle.id == msg->moves[mig].obj.id)
-                       {
-                               wallTime = stats[from].objData[oidx].wallTime;
-                               break;
-                       }
-               CkAssert(oidx != stats[from].n_objs);
-               peLoads[from] -= wallTime;
-               peLoads[to] += wallTime;
-       }
-       // handling of the communication overheads. Here, for each "link" in the communication statistics,
-       // find the sender and receiver PE and if they are not the same, add the costs, else don't add
-       for(pe = 0; pe < count; pe++)
-       {
-               // add the communication loads
-               LDCommData* cdata = stats[pe].commData;
-               const int csz = stats[pe].n_comm;
-
-               for(int cidx = 0; cidx < csz; cidx++)
-               {
-                       // find the sender and receiver PE for this "link"
-                       int senderPE, receiverPE;
-
-                       if(cdata[cidx].from_proc())
-                               senderPE = cdata[cidx].src_proc;
-                       else
-                       {
-                               // for sender, check just the migration messages
-                               senderPE = FindPEAfterMigration(cdata[cidx].sender, stats, count, msg, 0);
-                               if(senderPE == -1)
-                                       senderPE = pe;
-                       }
-
-                       if(cdata[cidx].to_proc())
-                               receiverPE = cdata[cidx].dest_proc;
-                       else
-                               receiverPE = FindPEAfterMigration(cdata[cidx].receiver, stats, count, msg, 1);
-
-                       if(senderPE != receiverPE)
-                       {
-                               msgSentCount[senderPE] += cdata[cidx].messages;
-                               byteSentCount[senderPE] += cdata[cidx].bytes;
-
-                               msgRecvCount[receiverPE] += cdata[cidx].messages;
-                               byteRecvCount[receiverPE] += cdata[cidx].bytes;
-                       }
-               }
+       // handling of the communication overheads. 
+        for (int cidx=0; cidx < stats->n_comm; cidx++) {
+         LDCommData& cdata = stats->commData[cidx];
+         int senderPE, receiverPE;
+         if(cdata.from_proc())
+           senderPE = cdata.src_proc;
+         else {
+           int idx = stats->getHash(cdata.sender, cdata.senderOM);
+           senderPE = stats->to_proc[idx];
+           CmiAssert(senderPE != -1);
+         }
+         if(cdata.to_proc())
+           receiverPE = cdata.dest_proc;
+         else {
+           int idx = stats->getHash(cdata.receiver, cdata.receiverOM);
+           receiverPE = stats->to_proc[idx];
+           CmiAssert(receiverPE != -1);
+         }
+         if(senderPE != receiverPE)
+         {
+               msgSentCount[senderPE] += cdata.messages;
+               byteSentCount[senderPE] += cdata.bytes;
+
+               msgRecvCount[receiverPE] += cdata.messages;
+               byteRecvCount[receiverPE] += cdata.bytes;
+         }
        }
 
        // now for each processor, add to its load the send and receive overheads
@@ -718,40 +730,95 @@ void CentralLB::FindSimResults(LDStats* stats, int count, LBMigrateMsg* msg, LBS
     // estimate the new loads of the processors. As a first approximation, this is the
     // get background load
     for(int pe = 0; pe < count; pe++)
-         simResults->bgLoads[pe] = stats[pe].bg_walltime;
+         simResults->bgLoads[pe] = stats->procs[pe].bg_walltime;
     // sum of the cpu times of the objects on that processor
-    getPredictedLoad(stats, count, msg, simResults->peLoads, simResults->minObjLoad, simResults->maxObjLoad);
+    getPredictedLoad(stats, count, msg, simResults->peLoads, 
+                    simResults->minObjLoad, simResults->maxObjLoad);
+}
+
+int CentralLB::useMem() { 
+  return CkNumPes() * (sizeof(CentralLB::LDStats)+sizeof(CLBStatsMsg *)) +
+                        sizeof(CentralLB);
+}
+
+void CentralLB::LDStats::makeCommHash() {
+  if (transTable) return;
+
+  transTable = new LDOId[n_objs];
+  for (int obj=0; obj < n_objs; obj++){
+      LDObjData &oData = objData[obj];
+      transTable[obj].mid.id = oData.omID().id;
+      transTable[obj].oid = oData.id();
+  }
+  int i;
+   
+  objHash = new int[n_objs];
+  for(i=0;i<n_objs;i++)
+        objHash[i] = -1;
+   
+  for(i=0;i<n_objs;i++){
+        LDObjid &oid = transTable[i].oid;
+        int hash = ((oid.id[0])|(oid.id[1])) % n_objs;
+        while(objHash[hash] != -1)
+            hash = (hash+1)%n_objs;
+        objHash[hash] = i;
+  }
+}
+
+void CentralLB::LDStats::deleteCommHash() {
+  if (objHash) delete [] objHash;
+  if (transTable) delete [] transTable;
 }
 
-// find the PE of an object after migration. The bCheckStats flag indicates whether the stats is to
-// be checked or not.
-static int FindPEAfterMigration(LDObjid& id, CentralLB::LDStats* stats, int count, LBMigrateMsg* msg, int bCheckStats)
+int CentralLB::LDStats::getHash(LDObjid oid, LDOMid mid)
 {
-       // first check in the migration messages
-       for(int i = 0; i < msg->n_moves; i++)
-               if(msg->moves[i].obj.id == id)
-                       return msg->moves[i].to_pe;
+    int hash = (oid.id[0] | oid.id[1]) % n_objs;
 
-       if(!bCheckStats)
-               return -1;
+    for(int id=0;id<n_objs;id++){
+        int index = (id+hash)%n_objs;
+        if (LDObjIDEqual(transTable[objHash[index]].oid, oid) &&
+            LDOMidEqual(transTable[objHash[index]].mid, mid))
+            return objHash[index];
+    }
+    //  CkPrintf("not found \n");
+    return -1;
+}
 
-       // not a migrating object, so find in the stats if requires
-       for(int pe = 0; pe < count; pe++)
-       {
-               CmiBool found = CmiFalse;
-               for(int obj = 0; obj < stats[pe].n_objs; obj++)
-                       if(stats[pe].objData[obj].handle.id == id)
-                               { found = CmiTrue; break;}
-               if(found)
-                       return pe;
-       }
-       CkAssert(0);
-       return -1;
+
+void CentralLB::LDStats::pup(PUP::er &p)
+{
+  int i;
+  p(count);  
+  p(n_objs);
+  p(n_comm);
+  if (p.isUnpacking()) {
+    int maxpe = count>LBSimulation::simProcs?count:LBSimulation::simProcs;
+    procs = new ProcStats[maxpe];
+    objData = new LDObjData[n_objs];
+    commData = new LDCommData[n_comm];
+    from_proc = new int[n_objs];
+    to_proc = new int[n_objs];
+    transTable = NULL;
+    objHash = NULL;
+  }
+#if 1
+  ProcStats dummy;             // ignore the background load
+  for (i=0; i<count; i++) p((char*)&dummy, sizeof(ProcStats));
+#else
+  for (i=0; i<count; i++) p((char*)&procs[i], sizeof(ProcStats));
+#endif
+  for (i=0; i<n_objs; i++) p((char*)&objData[i], sizeof(LDObjStats));
+  p(from_proc, n_objs);
+  p(to_proc, n_objs);
+  for (i=0; i<n_comm; i++) p((char*)&commData[i], sizeof(LDCommData));
+  if (p.isUnpacking())
+    count = LBSimulation::simProcs;
 }
 
-int CentralLB::useMem() { 
-  return CkNumPes() * (sizeof(CentralLB::LDStats)+sizeof(CLBStatsMsg *)) +
-                        sizeof(CentralLB);
+int CentralLB::LDStats::useMem() { 
+  return sizeof(LDStats) + sizeof(ProcStats)*count + 
+        (sizeof(LDObjData) + 2*sizeof(int)) * n_objs;
+        sizeof(LDCommData) * n_comm;
 }
 
 #endif
index 5ab905e5ad90eb5c3b0fcdcdb5f8d1ceef8bfc69..ab2fa4d12a3d909d2ec2d44e6ce459dc36d0deed 100644 (file)
@@ -64,7 +64,12 @@ public:
 
   void set_avail_vector(char *new_vector);
 
-  struct LDStats {  // Passed to Strategy
+   struct LDOId {
+     LDObjid oid;
+     LDOMid mid;
+   };
+
+  struct ProcStats {  // per processor data
     double total_walltime;
     double total_cputime;
     double idletime;
@@ -73,11 +78,42 @@ public:
     int pe_speed;
     double utilization;
     CmiBool available;
+    int   n_objs;
+    ProcStats(): total_walltime(0.0), total_cputime(0.0), idletime(0.0),
+                bg_walltime(0.0), bg_cputime(0.0), pe_speed(1),
+                utilization(1.0), available(1), n_objs(0) {}
+  };
+
+  struct LDStats {  // Passed to Strategy
+    struct ProcStats  *procs;
+    int count;
     
     int n_objs;
     LDObjData* objData;
+    int  *from_proc, *to_proc;
     int n_comm;
     LDCommData* commData;
+
+    LDOId *transTable;
+    int *objHash;
+
+    LDStats(): n_objs(0), n_comm(0) { objData = NULL; commData = NULL; 
+               from_proc = NULL; to_proc = NULL;
+               transTable = NULL; objHash = NULL; }
+      // build hash table
+    void makeCommHash();
+    void deleteCommHash();
+    int getHash(LDObjid oid, LDOMid mid);
+    void clear() {
+      n_objs = n_comm = 0;
+      delete [] objData;
+      delete [] commData;
+      delete [] from_proc;
+      delete [] to_proc;
+      deleteCommHash();
+    }
+    void pup(PUP::er &p);
+    int useMem();
   };
 
    LBMigrateMsg* callStrategy(LDStats* stats,int count){
@@ -96,18 +132,23 @@ protected:
   virtual CmiBool QueryBalanceNow(int) { return CmiTrue; };  
   virtual CmiBool QueryDumpData() { return CmiFalse; };  
   virtual LBMigrateMsg* Strategy(LDStats* stats,int count);
+  virtual void work(LDStats* stats,int count);
+  virtual LBMigrateMsg * createMigrateMsg(LDStats* stats,int count);
 
   void simulation();
   void FindSimResults(LDStats* stats, int count, LBMigrateMsg* msg, LBSimulation* simResults);
+#if 0
   void RemoveNonMigratable(LDStats* statsDataList, int count);
+#endif
+  void buildStats();
 
 private:  
 
   int mystep;
   int myspeed;
   int stats_msg_count;
-  CLBStatsMsg** statsMsgsList;
-  LDStats* statsDataList;
+  CLBStatsMsg **statsMsgsList;
+  LDStats *statsData;
   int migrates_completed;
   int migrates_expected;
   double start_lb_time;
index 99fc51526c9fecd3e8e81210fa4a1abfdf394d8e..16b45675dc337d6d3bc2ef4bf5c9764158f7c4b4 100644 (file)
@@ -186,43 +186,53 @@ LBMigrateMsg* Comm1LB::Strategy(CentralLB::LDStats* stats, int count)
 
   alloc_array = new alloc_struct *[count+1];
 
-  nobj =0;
-  for(pe=0; pe < count; pe++) 
-    for(obj=0; obj < stats[pe].n_objs; obj++) 
-      nobj++;
+  nobj = stats->n_objs;
   //  CkPrintf("OBJ: Before \n");
 
   ObjectHeap maxh(nobj+1);
-  nobj =0;
+  for(obj=0; obj < nobj; obj++) {
+      x = new ObjectRecord;
+      x->id = obj;
+      x->pos = obj;
+      x->load = stats->objData[obj].wallTime;
+      x->pe = stats->from_proc[obj];
+      maxh.insert(x);
+  }
+  for(pe=0; pe < count; pe++) {
+     mean_load += stats->procs[pe].total_walltime;
+  }
+  mean_load /= count;
+/*
   for(pe=0; pe < count; pe++) {
     load_pe = 0.0;
     for(obj=0; obj < stats[pe].n_objs; obj++) {
-      load_pe += stats[pe].objData[obj].wallTime;
+      load_pe += stats->objData[obj].data.wallTime;
       nobj++;
       x = new ObjectRecord;
       x->id = nobj -1;
       x->pos = obj;
-      x->load = stats[pe].objData[obj].wallTime;
+      x->load = stats->objData[obj].data.wallTime;
       x->pe = pe;
       maxh.insert(x);
     }
     mean_load += load_pe/count;
 //    CkPrintf("LOAD on %d = %5.3lf\n",pe,load_pe);
   }
+*/
 
   npe = count;
   translate = new obj_id[nobj];
   int objno=0;
 
-  for(pe=0; pe < count; pe++) 
-    for(obj=0; obj < stats[pe].n_objs; obj++){ 
-      translate[objno].mid.id = stats[pe].objData[obj].omID().id;
-      translate[objno].oid.id[0] = stats[pe].objData[obj].id().id[0];
-      translate[objno].oid.id[1] = stats[pe].objData[obj].id().id[1];
-      translate[objno].oid.id[2] = stats[pe].objData[obj].id().id[2];
-      translate[objno].oid.id[3] = stats[pe].objData[obj].id().id[3];
+  for(obj=0; obj < stats->n_objs; obj++){ 
+      LDObjData &oData = stats->objData[obj];
+      translate[objno].mid.id = oData.omID().id;
+      translate[objno].oid.id[0] = oData.id().id[0];
+      translate[objno].oid.id[1] = oData.id().id[1];
+      translate[objno].oid.id[2] = oData.id().id[2];
+      translate[objno].oid.id[3] = oData.id().id[3];
       objno++;
-    }
+  }
 
   make_hash();
 
@@ -235,16 +245,17 @@ LBMigrateMsg* Comm1LB::Strategy(CentralLB::LDStats* stats, int count)
 
   int xcoord=0,ycoord=0;
 
-  for(pe=0; pe < count; pe++) 
-    for(com =0; com< stats[pe].n_comm;com++)
-      if((!stats[pe].commData[com].from_proc())&&(!stats[pe].commData[com].to_proc())){
-       xcoord = search(stats[pe].commData[com].sender,stats[pe].commData[com].senderOM); 
-       ycoord = search(stats[pe].commData[com].receiver,stats[pe].commData[com].receiverOM);
+  for(com =0; com< stats->n_comm;com++) {
+      LDCommData &commData = stats->commData[com];
+      if((!commData.from_proc())&&(!commData.to_proc())){
+       xcoord = search(commData.sender, commData.senderOM); 
+       ycoord = search(commData.receiver, commData.receiverOM);
        if((xcoord == -1)||(ycoord == -1))
          if (lb_ignoreBgLoad) continue;
          else CkAbort("Error in search\n");
-       add_graph(xcoord,ycoord,stats[pe].commData[com].bytes, stats[pe].commData[com].messages);       
+       add_graph(xcoord,ycoord,commData.bytes, commData.messages);     
       }
+  }
   
   int id,maxid,spe=0,minpe=0,mpos;
   double temp_cost,min_cost;
@@ -255,11 +266,11 @@ LBMigrateMsg* Comm1LB::Strategy(CentralLB::LDStats* stats, int count)
   spe = x->pe;
   mpos = x->pos;
   
-  alloc(pe,maxid,stats[spe].objData[mpos].wallTime,0,0);
+  alloc(pe,maxid,stats->objData[mpos].wallTime,0,0);
   if(pe != spe){
     //      CkPrintf("**Moving from %d to %d\n",spe,pe);
     MigrateInfo* migrateMe = new MigrateInfo;
-    migrateMe->obj = stats[spe].objData[mpos].handle;
+    migrateMe->obj = stats->objData[mpos].handle;
     migrateMe->from_pe = spe;
     migrateMe->to_pe = pe;
     migrateInfo.insertAtEnd(migrateMe);
@@ -301,7 +312,7 @@ LBMigrateMsg* Comm1LB::Strategy(CentralLB::LDStats* stats, int count)
     if(minpe != spe){
       //      CkPrintf("**Moving from %d to %d\n",spe,minpe);
       MigrateInfo *migrateMe = new MigrateInfo;
-      migrateMe->obj = stats[spe].objData[mpos].handle;
+      migrateMe->obj = stats->objData[mpos].handle;
       migrateMe->from_pe = spe;
       migrateMe->to_pe = minpe;
       migrateInfo.insertAtEnd(migrateMe);
index 781a7f159c1649475d1bb2fcb50ea09b1a50be79..b38da769121e36742482a472c4ef1111175ae3fa 100644 (file)
@@ -161,7 +161,6 @@ void init(double **a, graph * object_graph, int l, int b){
 LBMigrateMsg* CommLB::Strategy(CentralLB::LDStats* stats, int count)
 {
     int pe,obj,com;
-    double load_pe=0.0;
     ObjectRecord *x;
     
     //  CkPrintf("[%d] CommLB strategy\n",CkMyPe());
@@ -170,45 +169,29 @@ LBMigrateMsg* CommLB::Strategy(CentralLB::LDStats* stats, int count)
     
     alloc_array = new double *[count+1];
     
-    nobj =0;
-    for(pe=0; pe < count; pe++) 
-       for(obj=0; obj < stats[pe].n_objs; obj++) 
-           nobj++;
+    nobj = stats->n_objs;
     
     ObjectHeap maxh(nobj+1);
-    nobj =0;
-    for(pe=0; pe < count; pe++) {
-       load_pe = 0.0;
-       for(obj=0; obj < stats[pe].n_objs; obj++) {
-           load_pe += stats[pe].objData[obj].wallTime;
-           nobj++;
+    for(obj=0; obj < stats->n_objs; obj++) {
+//         load_pe += stats[pe].objData[obj].wallTime;
            x = new ObjectRecord;
-           x->id = nobj -1;
+           x->id = obj;
            x->pos = obj;
-           x->load = stats[pe].objData[obj].wallTime;
-           x->pe = pe;
+           x->load = stats->objData[obj].wallTime;
+           x->pe = stats->from_proc[obj];
            maxh.insert(x);
-       }
-       //    CkPrintf("LOAD on %d = %5.3lf\n",pe,load_pe);
     }
 
     npe = count;
     translate = new obj_id[nobj];
     int objno=0;
 
-    for(pe=0; pe < count; pe++)
-       for(obj=0; obj < stats[pe].n_objs; obj++){
-           LDObjData &objData = stats[pe].objData[obj];
-           translate[objno].mid.id = objData.omID().id;
-           translate[objno].oid = objData.id();
-           #if 0
-           translate[objno].oid.id[0] = objData.id().id[0];
-           translate[objno].oid.id[1] = objData.id().id[1];
-           translate[objno].oid.id[2] = objData.id().id[2];
-           translate[objno].oid.id[3] = objData.id().id[3];
-           #endif
-           objno++;
-       }
+    for(obj=0; obj < stats->n_objs; obj++){
+      LDObjData &objData = stats->objData[obj];
+      translate[objno].mid.id = objData.omID().id;
+      translate[objno].oid = objData.id();
+      objno++;
+    }
 
     make_hash();
 
@@ -221,18 +204,17 @@ LBMigrateMsg* CommLB::Strategy(CentralLB::LDStats* stats, int count)
 
     int xcoord=0,ycoord=0;
 
-    for(pe=0; pe < count; pe++)
-       for(com =0; com< stats[pe].n_comm;com++) {
-           LDCommData &commData = stats[pe].commData[com];
-           if((!commData.from_proc())&&(!commData.to_proc())){
+    for(com =0; com< stats->n_comm;com++) {
+        LDCommData &commData = stats->commData[com];
+        if((!commData.from_proc())&&(!commData.to_proc())){
                xcoord = search(commData.sender, commData.senderOM);
                ycoord = search(commData.receiver, commData.receiverOM);
                if((xcoord == -1)||(ycoord == -1))
                    if (lb_ignoreBgLoad) continue;
                    else CkAbort("Error in search\n");
                add_graph(xcoord,ycoord,commData.bytes, commData.messages);
-           }
-        }
+        }
+    }
 
     int id,maxid,spe=0,minpe=0,mpos;
     double temp,total_time,min_temp;
@@ -241,7 +223,7 @@ LBMigrateMsg* CommLB::Strategy(CentralLB::LDStats* stats, int count)
        CkPrintf("avail for %d = %d\n",pe,stats[pe].available);
     */
     for(pe=0;pe < count;pe++)
-       if(stats[pe].available == 1)
+       if(stats->procs[pe].available == 1)
            break;
 
     int first_avail_pe = pe;
@@ -252,11 +234,11 @@ LBMigrateMsg* CommLB::Strategy(CentralLB::LDStats* stats, int count)
     mpos = x->pos;
     delete x;
     //  CkPrintf("before alloc firstpe = %d\n",pe);
-    alloc(pe,maxid,stats[spe].objData[mpos].wallTime);
+    alloc(pe,maxid,stats->objData[mpos].wallTime);
     if(pe != spe){
        //    CkPrintf("**Moving from %d to %d\n",spe,pe);
        MigrateInfo* migrateMe = new MigrateInfo;
-       migrateMe->obj = stats[spe].objData[mpos].handle;
+       migrateMe->obj = stats->objData[mpos].handle;
        migrateMe->from_pe = spe;
        migrateMe->to_pe = pe;
        migrateInfo.insertAtEnd(migrateMe);
@@ -275,7 +257,7 @@ LBMigrateMsg* CommLB::Strategy(CentralLB::LDStats* stats, int count)
        minpe = first_avail_pe;
        
        for(pe = first_avail_pe +1; pe < count; pe++){
-           if(stats[pe].available == 0)
+           if(stats->procs[pe].available == 0)
                continue;
            
            temp = compute_com(maxid,pe);
@@ -296,7 +278,7 @@ LBMigrateMsg* CommLB::Strategy(CentralLB::LDStats* stats, int count)
        if(minpe != spe){
            //      CkPrintf("**Moving from %d to %d\n",spe,minpe);
            MigrateInfo *migrateMe = new MigrateInfo;
-           migrateMe->obj = stats[spe].objData[mpos].handle;
+           migrateMe->obj = stats->objData[mpos].handle;
            migrateMe->from_pe = spe;
            migrateMe->to_pe = minpe;
            migrateInfo.insertAtEnd(migrateMe);
index a39cc25d4a705a364dc37a24acbe58707e9a58b0..0a801fb37581278d641de7b2aa8e3c2f3cde7792 100644 (file)
@@ -106,23 +106,22 @@ GreedyLB::BuildObjectArray(CentralLB::LDStats* stats,
 
   *objCount = 0;
   int pe, obj;
-  for (pe = 0; pe < count; pe++)
-    *objCount += stats[pe].n_objs;
+  *objCount += stats->n_objs;
 
 //for (obj = 0; obj < stats[pe].n_objs; obj++)
 //if (stats[pe].objData[obj].migratable == CmiTrue) (*objCount)++; 
 
   objData  = new HeapData[*objCount];
   *objCount = 0; 
-  for(pe=0; pe < count; pe++)
-       for(obj=0; obj < stats[pe].n_objs; obj++) {
+  for(obj=0; obj < stats->n_objs; obj++) {
 //      if (stats[pe].objData[obj].migratable == CmiTrue) {
+       int pe = stats->from_proc[obj];
         objData[*objCount].load = 
-          stats[pe].objData[obj].wallTime * stats[pe].pe_speed;
+          stats->objData[obj].wallTime * stats->procs[pe].pe_speed;
         objData[*objCount].pe = pe;
         objData[*objCount].id = obj;
         (*objCount)++;
-    }
+  }
   
   HeapSort(objData, *objCount-1, GT);
   return objData;
@@ -133,19 +132,19 @@ GreedyLB::BuildCpuArray(CentralLB::LDStats* stats,
                           int count, int *peCount)
 {
   HeapData           *data;
-  CentralLB::LDStats *peData;
+  CentralLB::ProcStats *peData;
   
   *peCount = 0;
   int pe;
   for (pe = 0; pe < count; pe++)
-    if (stats[pe].available == CmiTrue) (*peCount)++;
+    if (stats->procs[pe].available == CmiTrue) (*peCount)++;
 
   data = new HeapData[*peCount];
   
   *peCount = 0;
   for (pe=0; pe < count; pe++) {
     data[*peCount].load = 0.0;
-    peData = &(stats[pe]);
+    peData = &(stats->procs[pe]);
  
     if (peData->available == CmiTrue) 
        {
@@ -167,9 +166,8 @@ GreedyLB::BuildCpuArray(CentralLB::LDStats* stats,
   return data;
 }
 
-LBMigrateMsg* GreedyLB::Strategy(CentralLB::LDStats* stats, int count)
+void GreedyLB::work(CentralLB::LDStats* stats, int count)
 {
-  CkVec<MigrateInfo*> migrateInfo;
   int      obj, heapSize, objCount;
   HeapData *cpuData = BuildCpuArray(stats, count, &heapSize);
   HeapData *objData = BuildObjectArray(stats, count, &objCount);
@@ -195,13 +193,16 @@ LBMigrateMsg* GreedyLB::Strategy(CentralLB::LDStats* stats, int count)
     const int pe   = objData[obj].pe;
     const int id   = objData[obj].id;
     if (dest != pe) {
+      stats->to_proc[id] = dest;
       //      CkPrintf("[%d] Obj %d migrating from %d to %d\n",
       //         CkMyPe(),obj,pe,dest);
+/*
       MigrateInfo *migrateMe = new MigrateInfo;
-      migrateMe->obj = stats[pe].objData[id].handle;
+      migrateMe->obj = stats->objData[id].data.handle;
       migrateMe->from_pe = pe;
       migrateMe->to_pe = dest;
       migrateInfo.insertAtEnd(migrateMe);
+*/
     }
 
     //Insert the least loaded processor with load updated back into the heap
@@ -216,6 +217,25 @@ LBMigrateMsg* GreedyLB::Strategy(CentralLB::LDStats* stats, int count)
 
   delete [] cpuData;
   delete [] objData;
+}
+
+LBMigrateMsg * GreedyLB::createMigrateMsg(LDStats* stats,int count)
+{
+  CkVec<MigrateInfo*> migrateInfo;
+  for (int i=0; i<stats->n_objs; i++) {
+    LDObjData &objData = stats->objData[i];
+    int frompe = stats->from_proc[i];
+    int tope = stats->to_proc[i];
+    if (frompe != tope) {
+      //      CkPrintf("[%d] Obj %d migrating from %d to %d\n",
+      //         CkMyPe(),obj,pe,dest);
+      MigrateInfo *migrateMe = new MigrateInfo;
+      migrateMe->obj = objData.handle;
+      migrateMe->from_pe = frompe;
+      migrateMe->to_pe = tope;
+      migrateInfo.insertAtEnd(migrateMe);
+    }
+  }
 
   int migrate_count=migrateInfo.length();
   CkPrintf("GreedyLB migrating %d elements\n",migrate_count);
index 41da748cfc8aae437fa65e3d6ed7b9e1a17e64c0..560b936936ac20161de5a396ed9f3c6f9979c54d 100644 (file)
@@ -29,16 +29,17 @@ public:
 
   GreedyLB();
   GreedyLB(CkMigrateMessage *m):CentralLB(m) {}
+  void work(LDStats* stats,int count);
+  LBMigrateMsg * createMigrateMsg(LDStats* stats,int count);
 private:
        enum           HeapCmp {GT = '>', LT = '<'};
-    void           Heapify(HeapData*, int, int, HeapCmp);
+       void           Heapify(HeapData*, int, int, HeapCmp);
        void           HeapSort(HeapData*, int, HeapCmp);
        void           BuildHeap(HeapData*, int, HeapCmp);
        CmiBool        Compare(double, double, HeapCmp);
        HeapData*      BuildCpuArray(CentralLB::LDStats*, int, int *);      
        HeapData*      BuildObjectArray(CentralLB::LDStats*, int, int *);      
        CmiBool        QueryBalanceNow(int step);
-       LBMigrateMsg* Strategy(CentralLB::LDStats* stats, int count);
 };
 
 #endif /* _HEAPCENTLB_H_ */
index 6c338eeb4f3034b9d6f96a28cc02f49aaeb62a7b..7809f42cde0e9dbe05835d7a408719ad1a2368fd 100644 (file)
@@ -38,226 +38,48 @@ GreedyRefLB::GreedyRefLB()
     CkPrintf("[%d] GreedyRefLB created\n",CkMyPe());
 }
 
-CmiBool GreedyRefLB::QueryBalanceNow(int _step)
-{
-  //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
-  return CmiTrue;
-}
-
-CmiBool GreedyRefLB::Compare(double x, double y, GreedyCmp cmp)
-{
-  int test = ((cmp == GT) ? (x > y) : (x < y));
-  if (test) return CmiTrue;
-  else return CmiFalse;
-}
-
-
-void GreedyRefLB::Heapify(HeapData *heap, int node, int heapSize, GreedyCmp cmp)
-{
-  int left = 2*node+1;
-  int right = 2*node+2;
-  int xchange;
-
-  //heap[left].load > heap[node].load)
-  if (left <= heapSize && Compare(heap[left].load, heap[node].load, cmp))
-         xchange = left;
-  else xchange = node;
-  //heap[right].load > heap[xchange].load
-  if (right <= heapSize && Compare(heap[right].load, heap[xchange].load, cmp)) 
-    xchange = right;
-
-  if (xchange != node) {
-    HeapData obj;
-    obj = heap[node];
-    heap[node] = heap[xchange];
-    heap[xchange] = obj;
-    Heapify(heap, xchange, heapSize, cmp);
-  }    
-}
-
-void GreedyRefLB::BuildHeap(HeapData *data, int heapSize, GreedyCmp cmp)
-{
-       int i;
-       for(i=heapSize/2; i >= 0; i--)
-               Heapify(data, i, heapSize, cmp);
-}
-
-void GreedyRefLB::HeapSort(HeapData *data, int heapSize, GreedyCmp cmp)
-{
-       int i;
-       HeapData key;
-
-       BuildHeap(data, heapSize, cmp);
-       for (i=heapSize; i > 0; i--) {
-               key = data[0];
-               data[0] = data[i];
-               data[i] = key;
-               heapSize--;
-               Heapify(data, 0, heapSize, cmp);
-       }
-}
-
-GreedyRefLB::HeapData* 
-GreedyRefLB::BuildObjectArray(CentralLB::LDStats* stats, 
-                                                                       int count, int *objCount)
-{
-  HeapData *objData;
-
-  *objCount = 0;
-  int pe, obj;
-  for (pe = 0; pe < count; pe++)
-         *objCount += stats[pe].n_objs;
-    //for (obj = 0; obj < stats[pe].n_objs; obj++)
-      //if (stats[pe].objData[obj].migratable == CmiTrue) (*objCount)++; 
-
-  objData  = new HeapData[*objCount];
-  *objCount = 0; 
-  for(pe=0; pe < count; pe++)
-       for(obj=0; obj < stats[pe].n_objs; obj++) {
-      //if (stats[pe].objData[obj].migratable == CmiTrue) {
-        objData[*objCount].load = 
-          stats[pe].objData[obj].wallTime * stats[pe].pe_speed;
-        objData[*objCount].pe = pe;
-        objData[*objCount].id = obj;
-               (*objCount)++;
-    }
-  HeapSort(objData, *objCount-1, GT);
-  return objData;
-}
-
-GreedyRefLB::HeapData* 
-GreedyRefLB::BuildCpuArray(CentralLB::LDStats* stats, int count, int *peCount)
-{
-  HeapData           *data;
-  CentralLB::LDStats *peData;
-  
-  *peCount = 0;
-  int pe;
-  for (pe = 0; pe < count; pe++)
-    if (stats[pe].available == CmiTrue) (*peCount)++;
-
-  data = new HeapData[*peCount];
-  
-  *peCount = 0;
-  for (pe=0; pe < count; pe++) {
-    data[*peCount].load = 0.0;
-    peData = &(stats[pe]);
-
-    if (peData->available == CmiTrue) {
-
-       /*                       
-       for (obj = 0; obj < peData->n_objs; obj++) 
-                if (peData->objData[obj].migratable == CmiFalse) 
-                                data[*peCount].load -= 
-                                        peData->objData[obj].wallTime * peData->pe_speed;
-       */
-       
-        data[*peCount].load += peData->bg_walltime * peData->pe_speed;
-       //               (peData->total_walltime - peData->bg_walltime) * peData->pe_speed;
-        data[*peCount].pe = data[*peCount].id = pe;
-        (*peCount)++;
-       }
-  }
-  BuildHeap(data, *peCount-1, LT);
-  return data;
-}
-
-
 
 LBMigrateMsg* GreedyRefLB::Strategy(CentralLB::LDStats* stats, int count)
 {
   CkVec<MigrateInfo*> migrateInfo;
-  int      pe, obj, heapSize, objCount;
-  HeapData *cpuData = BuildCpuArray(stats, count, &heapSize);
-  HeapData *objData = BuildObjectArray(stats, count, &objCount);
-
-  //  CkPrintf("[%d] GreedyRefLB strategy\n",CkMyPe());
-
-  // Build the refine data structure, and use it for storing the info
-  // from the heap
-  int** from_procs = Refiner::AllocProcs(count, stats);
-  for(pe=0;pe<count;pe++)
-    for(obj=0;obj < stats[pe].n_objs; obj++)
-      from_procs[pe][obj] = 0;
+  int obj;
 
-  heapSize--;
-  HeapData minCpu;  
-  for (obj=0; obj < objCount; obj++) {
-    // Operation of extracting the the least loaded processor
-    // from the heap
-    minCpu = cpuData[0];
-    cpuData[0] = cpuData[heapSize];
-    heapSize--;
-    Heapify(cpuData, 0, heapSize, LT);    
+  work(stats, count);    // call GreedyLB first
 
-    // Increment the time of the least loaded processor by the cpuTime of
-    // the `heaviest' object
-    minCpu.load += objData[obj].load;
-
-    //Insert object into migration queue if necessary
-    const int dest = minCpu.pe;
-    const int pe   = objData[obj].pe;
-    const int id   = objData[obj].id;
-    from_procs[pe][id] = dest;
+  // Get a new buffer to refine into
+  int* from_procs = Refiner::AllocProcs(count, stats);
 
-    //Insert the least loaded processor with load updated back into the heap
-    heapSize++;
-    int location = heapSize;
-    while (location>0 && cpuData[(location-1)/2].load > minCpu.load) {
-      cpuData[location] = cpuData[(location-1)/2];
-      location = (location-1)/2;
-    }
-    cpuData[location] = minCpu;
-  }
+  for(obj=0;obj < stats->n_objs; obj++)
+      from_procs[obj] = stats->to_proc[obj];
 
-  int initial_migrates=0;
-  for(pe=0;pe < count; pe++) {
-    for(obj=0;obj<stats[pe].n_objs;obj++) {
-      if (from_procs[pe][obj] == -1)
-  CkPrintf("From_Proc was unassigned!\n");
-      if (from_procs[pe][obj] != pe)
-  initial_migrates++;
-    }
-  }
-  CkPrintf("Initially migrating %d objects\n",initial_migrates);
-
-  // Get a new buffer to refine into
-  int** to_procs = Refiner::AllocProcs(count,stats);
+  int* to_procs = Refiner::AllocProcs(count,stats);
 
   Refiner refiner(1.01);  // overload tolerance=1.05
-  
   refiner.Refine(count,stats,from_procs,to_procs);
 
-  // Report on the output
-  for(pe=0;pe < count; pe++) {
-    for(obj=0;obj<stats[pe].n_objs;obj++) {
-      if (from_procs[pe][obj] != to_procs[pe][obj]) {
-  CkPrintf("Refinement moved obj %d orig %d from %d to %d\n",
-     obj,pe,from_procs[pe][obj],to_procs[pe][obj]);
-      }
-    }
-  }
-
   // Save output
-  for(pe=0;pe < count; pe++) {
-    for(obj=0;obj<stats[pe].n_objs;obj++) {
-      if (from_procs[pe][obj] == -1)
-  CkPrintf("From_Proc was unassigned!\n");
-      if (to_procs[pe][obj] == -1)
-  CkPrintf("To_Proc was unassigned!\n");
+  for(obj=0;obj<stats->n_objs;obj++) {
+      int frompe = stats->from_proc[obj];
+
+      if (from_procs[obj] == -1) CkPrintf("From_Proc was unassigned!\n");
+      if (to_procs[obj] == -1) CkPrintf("To_Proc was unassigned!\n");
       
-      if (to_procs[pe][obj] != pe) {
+      if (to_procs[obj] != frompe) {
   //  CkPrintf("[%d] Obj %d migrating from %d to %d\n",
   //     CkMyPe(),obj,pe,to_procs[pe][obj]);
-  MigrateInfo *migrateMe = new MigrateInfo;
-  migrateMe->obj = stats[pe].objData[obj].handle;
-  migrateMe->from_pe = pe;
-  migrateMe->to_pe = to_procs[pe][obj];
-  migrateInfo.insertAtEnd(migrateMe);
+       CkPrintf("Refinement moved obj %d orig %d from %d to %d\n", obj,stats->from_proc[obj],from_procs[obj],to_procs[obj]);
+        MigrateInfo *migrateMe = new MigrateInfo;
+        migrateMe->obj = stats->objData[obj].handle;
+        migrateMe->from_pe = frompe;
+        migrateMe->to_pe = to_procs[obj];
+        migrateInfo.insertAtEnd(migrateMe);
       }
-    }
   }
 
+  // Free the refine buffers
+  Refiner::FreeProcs(from_procs);
+  Refiner::FreeProcs(to_procs);
+  
   int migrate_count=migrateInfo.length();
   CkPrintf("GreedyRefLB migrating %d elements\n",migrate_count);
   LBMigrateMsg* msg = new(&migrate_count,1) LBMigrateMsg;
@@ -269,12 +91,9 @@ LBMigrateMsg* GreedyRefLB::Strategy(CentralLB::LDStats* stats, int count)
     migrateInfo[i] = 0;
   }
 
-  // Free the refine buffers
-  Refiner::FreeProcs(from_procs);
-  Refiner::FreeProcs(to_procs);
-  
   return msg;
-};
+  
+}
 
 #endif
 
index cde107642a1a5c64f7fed88dd41e2c89e5ee3f06..6ae8456371577c6c80a7f5af74482f30221aefdd 100644 (file)
 #define _GREEDYREFLB_H_
 
 #include "CentralLB.h"
+#include "GreedyLB.h"
 #include "Refiner.h"
 #include "GreedyRefLB.decl.h"
 
 void CreateGreedyRefLB();
 
-class GreedyRefLB : public CentralLB {
-
-struct HeapData {
-       double load;
-       int   pe;
-       int   id;
-};
-
+class GreedyRefLB : public GreedyLB {
 public:
   GreedyRefLB();
-  GreedyRefLB(CkMigrateMessage *m):CentralLB(m) {}
+  GreedyRefLB(CkMigrateMessage *m):GreedyLB(m) {}
 private:
-       enum           GreedyCmp {GT = '>', LT = '<'};
-       CmiBool        Compare(double, double, GreedyCmp);
-    void           Heapify(HeapData *, int, int, GreedyCmp);
-       void           HeapSort(HeapData*, int, GreedyCmp);
-       void           BuildHeap(HeapData*, int, GreedyCmp);
-       HeapData*      BuildCpuArray(CentralLB::LDStats*, int, int *);      
-       HeapData*      BuildObjectArray(CentralLB::LDStats*, int, int *);      
-       CmiBool        QueryBalanceNow(int step);
-       LBMigrateMsg* Strategy(CentralLB::LDStats* stats, int count);
+  LBMigrateMsg* Strategy(CentralLB::LDStats* stats, int count);
 };
 
 #endif /* _GREEDYREFLB_H_ */
index 3b832cfb3469dec712549d4ee75e65cb182d206d..6ca2c1ffe4dcc2223c7bd87498c143cdd343767a 100644 (file)
@@ -177,6 +177,8 @@ void _loadbalancerInit()
       CmiPrintf("LB> Load balancer running in verbose mode.\n");
     if (lb_ignoreBgLoad)
       CmiPrintf("LB> Load balancer only balance migratable object.\n");
+    if (LBSimulation::doSimulation)
+      CmiPrintf("LB> Load balancer running in simulation mode.\n");
   }
 }
 
index 53d8bd3e970e55ba688d29ebb143f5377ec3a837..5060d6124eb74a32259edfc6cabaa654eb50f186 100644 (file)
@@ -116,9 +116,7 @@ LBMigrateMsg* MetisLB::Strategy(CentralLB::LDStats* stats, int count)
   int i, j, m;
   int option = 0;
   int numobjs = 0;
-  for (j=0; j < count; j++) {
-    numobjs += stats[j].n_objs;
-  }
+  numobjs = stats->n_objs;
 
   // allocate space for the computing data
   double *objtime = new double[numobjs];
@@ -132,19 +130,18 @@ LBMigrateMsg* MetisLB::Strategy(CentralLB::LDStats* stats, int count)
   }
 
   int k=0;
-  for (j=0; j<count; j++) {
-    for (i=0; i<stats[j].n_objs; i++) {
-      LDObjData *odata = stats[j].objData;
+  for (i=0; i<stats->n_objs; i++) {
+      LDObjData &odata = stats->objData[i];
       /*
       origmap[odata[i].id.id[0]] = j;
       cputime[odata[i].id.id[0]] = odata[i].cpuTime;
       handles[odata[i].id.id[0]] = odata[i].handle;
       */
-      origmap[k] = j;
-      objtime[k] = odata[i].wallTime*stats[j].pe_speed;
-      handles[k] = odata[i].handle;
+      int frompe = stats->from_proc[i];
+      origmap[k] = frompe;
+      objtime[k] = odata.wallTime*stats->procs[frompe].pe_speed;
+      handles[k] = odata.handle;
       k++;
-    }
   }
 
   // to convert the weights on vertices to integers
@@ -165,22 +162,21 @@ LBMigrateMsg* MetisLB::Strategy(CentralLB::LDStats* stats, int count)
     }
   }
 
-  for(j=0; j<count; j++) {
-    LDCommData *cdata = stats[j].commData;
-    const int csz = stats[j].n_comm;
-    for(i=0; i<csz; i++) {
-      if(cdata[i].from_proc() || cdata[i].to_proc())
+  const int csz = stats->n_comm;
+  for(i=0; i<csz; i++) {
+      LDCommData &cdata = stats->commData[i];
+      if(cdata.from_proc() || cdata.to_proc())
         continue;
       // FIXME!
       // senderID and recverID is not correct !!!
-      int senderID = cdata[i].sender.id[0];
-      int recverID = cdata[i].receiver.id[0];
+      int senderID = cdata.sender.id[0];
+      int recverID = cdata.receiver.id[0];
       CmiAssert(senderID < numobjs);
       CmiAssert(recverID < numobjs);
-      comm[senderID][recverID] += cdata[i].messages;
-      comm[recverID][senderID] += cdata[i].messages;
+      comm[senderID][recverID] += cdata.messages;
+      comm[recverID][senderID] += cdata.messages;
     }
-}
+
 // ignore messages sent from an object to itself
   for (i=0; i<numobjs; i++)
     comm[i][i] = 0;
@@ -260,21 +256,21 @@ LBMigrateMsg* MetisLB::Strategy(CentralLB::LDStats* stats, int count)
       // CkPrintf("after calling Metis functions.\n");
     }
     else if (WEIGHTED == option) {
-      float maxtotal_walltime = stats[0].total_walltime;
+      float maxtotal_walltime = stats->procs[0].total_walltime;
       for (m=1; m<count; m++) {
-       if (maxtotal_walltime < stats[m].total_walltime)
-         maxtotal_walltime = stats[m].total_walltime;
+       if (maxtotal_walltime < stats->procs[m].total_walltime)
+         maxtotal_walltime = stats->procs[m].total_walltime;
       }
       float totaltimeAllPe = 0.0;
       for (m=0; m<count; m++) {
-       totaltimeAllPe += stats[m].pe_speed * 
-         (maxtotal_walltime-stats[m].bg_walltime);
+       totaltimeAllPe += stats->procs[m].pe_speed * 
+         (maxtotal_walltime-stats->procs[m].bg_walltime);
       }
       // set up the different weights
       float *tpwgts = new float[count];
       for (m=0; m<count; m++) {
-       tpwgts[m] = stats[m].pe_speed * 
-         (maxtotal_walltime-stats[m].bg_walltime) / totaltimeAllPe;
+       tpwgts[m] = stats->procs[m].pe_speed * 
+         (maxtotal_walltime-stats->procs[m].bg_walltime) / totaltimeAllPe;
       }
       if (count > 8)
        METIS_WPartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt, 
index b26a20a7416c585c68ed65e3b956fe383fc9d23f..ae71de91b96fc9b9371ad7f27dedcb9f59aa0f47 100644 (file)
@@ -29,51 +29,46 @@ ObjGraph::ObjGraph(int count, CentralLB::LDStats* _stats)
   nodelist = 0;
   // Count up the edges and the nodes, and allocate storage for
   // them all at once.
-  n_objs = 0;
+  n_objs = stats->n_objs;
   n_edges = 0;
-  int pe;
-  for(pe=0; pe < count; pe++) {
-    n_objs += stats[pe].n_objs;
-    int index;
     // initialize node array
-    for(index = 0; index < stats[pe].n_comm; index++) {
-      const LDCommData newedgedata = stats[pe].commData[index];
+  int index;
+  for(int index = 0; index < stats->n_comm; index++) {
+      const LDCommData newedgedata = stats->commData[index];
 
       // If this isn't an object-to-object message, ignore it
       if (!newedgedata.from_proc() && !newedgedata.to_proc())
        n_edges++;
     }
-  }
   nodelist = new Node[n_objs];
   edgelist = new Edge[n_edges];
 
   // Now initialize the node and the edge arrays
   int cur_node = 0;
   int cur_edge = 0;
-  for(pe=0; pe < count; pe++) {
-    int index;
-    // initialize node array
-    for(index = 0; index < stats[pe].n_objs; index++) {
+  // initialize node array
+  for(index = 0; index < stats->n_objs; index++) {
+      LDObjData &odata = stats->objData[index];
       if(cur_node >= n_objs)
        CkPrintf("Error %d %d\n",cur_node,n_objs);
       Node* thisnode = nodelist + cur_node;
       thisnode->node_index = cur_node;
-      thisnode->proc = pe;
+      thisnode->proc = stats->from_proc[index];
       thisnode->index = index;
       thisnode->n_out = 0;
       thisnode->outEdge = 0;
       thisnode->n_in = 0;
       thisnode->inEdge = 0;
       cur_node++;
-      const int hashval = calc_hashval(stats[pe].objData[index].omID(),
-                                      stats[pe].objData[index].id());
+      const int hashval = calc_hashval(odata.omID(),
+                                      odata.id());
       thisnode->nxt_hash = node_table[hashval];
       node_table[hashval] = thisnode;
-    }
+  }
 
     // initialize edge array
-    for(index=0; index < stats[pe].n_comm; index++) {
-      const LDCommData newedgedata = stats[pe].commData[index];
+    for(index=0; index < stats->n_comm; index++) {
+      LDCommData &newedgedata = stats->commData[index];
 
       // If this isn't an object-to-object message, ignore it
       if (newedgedata.from_proc() || newedgedata.to_proc())
@@ -84,14 +79,12 @@ ObjGraph::ObjGraph(int count, CentralLB::LDStats* _stats)
 
       Edge* thisedge = edgelist + cur_edge;
       thisedge->edge_index = cur_edge;
-      thisedge->proc = pe;
       thisedge->index = index;
       thisedge->from_node = -1;
       thisedge->to_node = -1;
       thisedge->nxt_out = 0;
       thisedge->nxt_in = 0;
       cur_edge++;
-    }
   }
   if(cur_node != n_objs)
       CkPrintf("did not fill table %d %d\n",cur_node,n_objs);
@@ -102,9 +95,8 @@ ObjGraph::ObjGraph(int count, CentralLB::LDStats* _stats)
   // Now go through the comm lists
   for(cur_edge = 0; cur_edge < n_edges; cur_edge++) {
     Edge* newedge = edgelist + cur_edge;
-    int pe = newedge->proc;
     int index = newedge->index;
-    const LDCommData newedgedata = stats[pe].commData[index];
+    const LDCommData newedgedata = stats->commData[index];
 
     Node* from_node = find_node(newedgedata.senderOM,newedgedata.sender);
     if (from_node == 0) {
@@ -139,7 +131,7 @@ ObjGraph::~ObjGraph()
 }
 
 double ObjGraph::EdgeWeight(Edge* e) {
-  LDCommData commData = stats[e->proc].commData[e->index];
+  LDCommData commData = stats->commData[e->index];
   return commData.messages * alpha + commData.bytes * beta;
 }
 
@@ -160,9 +152,9 @@ ObjGraph::Node* ObjGraph::find_node(LDOMid edge_omid, LDObjid edge_id)
 
   while (from_node != 0) {
     const LDOMid omid =
-      stats[from_node->proc].objData[from_node->index].omID();
+      stats->objData[from_node->index].omID();
     const LDObjid objid =
-      stats[from_node->proc].objData[from_node->index].id();
+      stats->objData[from_node->index].id();
     //    CkPrintf("Comparing %d to %d\n",objid.id[0],edge_id.id[0]);
     if (LDOMidEqual(omid,edge_omid) && LDObjIDEqual(objid,edge_id) )
       break;
index 10ddb5770e73d00240f5a22efcb9369c5dd6f7aa..a7f3fe63ec56d41d0de2cbcafd1cab754097cfe4 100644 (file)
@@ -22,7 +22,6 @@ public:
     friend class ObjGraph;
   public:
     int edge_index;
-    int proc;
     int index;
     int from_node;
     int to_node;
@@ -62,7 +61,7 @@ public:
     const Node n = GraphNode(i);
     const int pe = n.proc;
     const int index = n.index;
-    return stats[pe].objData[index].wallTime;
+    return stats->objData[index].wallTime;
   };
 
   double EdgeWeight(Edge* e);
index 412f8688b616f11faecb8c628bf3c9996595b7bc..d7581d2f0989152427a50facace0084b1aa0e520 100644 (file)
@@ -267,8 +267,7 @@ LBMigrateMsg* OrbLB::Strategy(CentralLB::LDStats* stats, int count)
 
   P = count;
   // calculate total number of objects
-  nObjs = 0;
-  for (i=0; i<count; i++) nObjs += stats[i].n_objs;
+  nObjs = stats->n_objs;
 #ifdef DEBUG
   CmiPrintf("ORB: num objects:%d\n", nObjs);
 #endif
@@ -280,23 +279,20 @@ LBMigrateMsg* OrbLB::Strategy(CentralLB::LDStats* stats, int count)
   // v[0] = XDIR  v[1] = YDIR v[2] = ZDIR
   // vArray[XDIR] is an array holding the x vector for all computes
   int objIdx = 0;
-  for (i=0; i<count; i++) {
-    int osz = stats[i].n_objs;
-    LDObjData *odata = stats[i].objData;
-    for (j=0; j<osz; j++) {
-      computeLoad[objIdx].id = objIdx;
-      computeLoad[objIdx].v[XDIR] = odata[j].id().id[0];
-      computeLoad[objIdx].v[YDIR] = odata[j].id().id[1];
-      computeLoad[objIdx].v[ZDIR] = odata[j].id().id[2];
-      computeLoad[objIdx].load = odata[j].wallTime;
-      computeLoad[objIdx].refno = 0;
-      computeLoad[objIdx].partition = NULL;
-      for (int k=XDIR; k<=ZDIR; k++) {
+  for (i=0; i<nObjs; i++) {
+    LDObjData &odata = stats->objData[i];
+    computeLoad[objIdx].id = objIdx;
+    computeLoad[objIdx].v[XDIR] = odata.id().id[0];
+    computeLoad[objIdx].v[YDIR] = odata.id().id[1];
+    computeLoad[objIdx].v[ZDIR] = odata.id().id[2];
+    computeLoad[objIdx].load = odata.wallTime;
+    computeLoad[objIdx].refno = 0;
+    computeLoad[objIdx].partition = NULL;
+    for (int k=XDIR; k<=ZDIR; k++) {
         vArray[k][objIdx].id = objIdx;
         vArray[k][objIdx].v = computeLoad[objIdx].v[k];
-      }
-      objIdx ++;
     }
+    objIdx ++;
   }
 
   double t = CmiWallTimer();
@@ -376,19 +372,18 @@ LBMigrateMsg* OrbLB::Strategy(CentralLB::LDStats* stats, int count)
 
   // Save output
   objIdx = 0;
-  for(int pe=0;pe < count; pe++) {
-    for(int obj=0;obj<stats[pe].n_objs;obj++) {
-      if (pe != computeLoad[objIdx].partition->node) {
+  for(int obj=0;obj<stats->n_objs;obj++) {
+      int frompe = stats->from_proc[obj];
+      if (frompe != computeLoad[objIdx].partition->node) {
         //      CkPrintf("[%d] Obj %d migrating from %d to %d\n",
         //               CkMyPe(),obj,pe,to_procs[pe][obj]);
         MigrateInfo *migrateMe = new MigrateInfo;
-        migrateMe->obj = stats[pe].objData[obj].handle;
-        migrateMe->from_pe = pe;
+        migrateMe->obj = stats->objData[obj].handle;
+        migrateMe->from_pe = frompe;
         migrateMe->to_pe = computeLoad[objIdx].partition->node;
         migrateInfo.insertAtEnd(migrateMe);
       }
       objIdx ++;
-    }
   }
 
   int migrate_count=migrateInfo.length();
index e9a33bb8a64691d2f858a0ee5e838325edb57d9c..429c2e81ba005377b194a49e4aab64f1c9ed4ea2 100644 (file)
@@ -44,46 +44,19 @@ CmiBool RandCentLB::QueryBalanceNow(int _step)
   return CmiTrue;
 }
 
-LBMigrateMsg* RandCentLB::Strategy(CentralLB::LDStats* stats, int count)
+void RandCentLB::work(CentralLB::LDStats* stats, int count)
 {
-  //  CkPrintf("[%d] RandCentLB strategy\n",CkMyPe());
-
-  // remove non-migratable objects
-  RemoveNonMigratable(stats, count);
-
-  CkVec<MigrateInfo*> migrateInfo;
-
-  for(int pe=0; pe < count; pe++) {
-    //    CkPrintf("[%d] PE %d : %d Objects : %d Communication\n",
-    //      CkMyPe(),pe,stats[pe].n_objs,stats[pe].n_comm);
-    for(int obj=0; obj < stats[pe].n_objs; obj++) {
-      if (stats[pe].objData[obj].migratable) {
+  for(int obj=0; obj < stats->n_objs; obj++) {
+      LDObjData &odata = stats->objData[obj];
+      if (odata.migratable) {
        const int dest = (int)(CrnDrand()*(CkNumPes()-1) + 0.5);
-       if (dest != pe) {
-         //    CkPrintf("[%d] Obj %d migrating from %d to %d\n",
-         //             CkMyPe(),obj,pe,dest);
-         MigrateInfo* migrateMe = new MigrateInfo;
-         migrateMe->obj = stats[pe].objData[obj].handle;
-         migrateMe->from_pe = pe;
-         migrateMe->to_pe = dest;
-         migrateInfo.insertAtEnd(migrateMe);
-       }
+       if (dest != stats->from_proc[obj]) {
+         // CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),obj,odata.from_proc,dest);
+         stats->to_proc[obj] = dest;
+        }
       }
-    }
   }
-
-  int migrate_count=migrateInfo.length();
-  LBMigrateMsg* msg = new(&migrate_count,1) LBMigrateMsg;
-  msg->n_moves = migrate_count;
-  for(int i=0; i < migrate_count; i++) {
-    MigrateInfo* item = (MigrateInfo*)migrateInfo[i];
-    msg->moves[i] = *item;
-    delete item;
-    migrateInfo[i] = 0;
-  }
-
-  return msg;
-};
+}
 
 #endif
 
index 3ac2ddcc8cc60655e4109f4439f7b9f035e2d27e..6f445dc421d1e7eac2f6b2944399fda8e8f1690e 100644 (file)
@@ -22,9 +22,9 @@ class RandCentLB : public CentralLB {
 public:
   RandCentLB();
   RandCentLB(CkMigrateMessage *m):CentralLB(m) {}
+  void work(CentralLB::LDStats* stats, int count);
 private:
   CmiBool QueryBalanceNow(int step);
-  LBMigrateMsg* Strategy(CentralLB::LDStats* stats, int count);
 };
 
 #endif /* _RANDCENTLB_H_ */
index 2f8f35b5f78cc3f9aedf40d3ca07ccd3fc3c1915..a1a6f30c1084bafcc95c3b4d9131035bc55d4ccf 100644 (file)
@@ -40,59 +40,34 @@ RandRefLB::RandRefLB()
     CkPrintf("[%d] RandRefLB created\n",CkMyPe());
 }
 
-CmiBool RandRefLB::QueryBalanceNow(int _step)
-{
-  //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
-  return CmiTrue;
-}
-
-LBMigrateMsg* RandRefLB::Strategy(CentralLB::LDStats* stats, int count)
+void RandRefLB::work(CentralLB::LDStats* stats, int count)
 {
   //  CkPrintf("[%d] RandRefLB strategy\n",CkMyPe());
 
   CkVec<MigrateInfo*> migrateInfo;
-
-  int** from_procs = Refiner::AllocProcs(count,stats);
-  int pe;
   int obj;
-  for(pe=0; pe < count; pe++) {
-    //    CkPrintf("[%d] PE %d : %d Objects : %d Communication\n",
-    //      CkMyPe(),pe,stats[pe].n_objs,stats[pe].n_comm);
-    for(obj=0; obj < stats[pe].n_objs; obj++)
-      from_procs[pe][obj] = (int)(CrnDrand()*(CkNumPes()-1) + 0.5 );
-  }
-  int** to_procs = Refiner::AllocProcs(count,stats);
+
+  int* from_procs = Refiner::AllocProcs(count,stats);
+
+  for(obj=0; obj < stats->n_objs; obj++)
+      from_procs[obj] = (int)(CrnDrand()*(CkNumPes()-1) + 0.5 );
+
+  int* to_procs = Refiner::AllocProcs(count,stats);
+
   Refiner refiner(1.02);
   refiner.Refine(count,stats,from_procs,to_procs);
 
-  for(pe=0; pe < count; pe++) {
-    for(obj=0; obj < stats[pe].n_objs; obj++) {
-      if (to_procs[pe][obj] != pe) {
-       //      CkPrintf("[%d] Obj %d migrating from %d to %d\n",
-       //               CkMyPe(),obj,pe,dest);
-       MigrateInfo* migrateMe = new MigrateInfo;
-       migrateMe->obj = stats[pe].objData[obj].handle;
-       migrateMe->from_pe = pe;
-       migrateMe->to_pe = to_procs[pe][obj];
-       migrateInfo.insertAtEnd(migrateMe);
+  for(obj=0; obj < stats->n_objs; obj++) {
+      LDObjData &oData = stats->objData[obj];
+      if (stats->from_proc[obj] != to_procs[obj]) {
+       CkPrintf("[%d] Obj %d migrating from %d to %d\n",
+                        CkMyPe(),obj,stats->from_proc[obj],to_procs[obj]);
+        stats->to_proc[obj] = to_procs[obj];
       }
-    }
-  }
-
-  int migrate_count=migrateInfo.length();
-  LBMigrateMsg* msg = new(&migrate_count,1) LBMigrateMsg;
-  msg->n_moves = migrate_count;
-  for(int i=0; i < migrate_count; i++) {
-    MigrateInfo* item = (MigrateInfo*)migrateInfo[i];
-    msg->moves[i] = *item;
-    delete item;
-    migrateInfo[i] = 0;
   }
 
   Refiner::FreeProcs(from_procs);
   Refiner::FreeProcs(to_procs);
-
-  return msg;
 };
 
 #endif
index 91541cb1cc4cf6e9db3763ba0b55b125647bf0a9..992f2b9f2eaeb8f1778ec078b99995fc378ca9aa 100644 (file)
 #define _RANDREFLB_H_
 
 #include "CentralLB.h"
+#include "RandCentLB.h"
 #include "RandRefLB.decl.h"
 
 void CreateRandRefLB();
 
-class RandRefLB : public CentralLB {
+class RandRefLB : public RandCentLB {
 public:
   RandRefLB();
-  RandRefLB(CkMigrateMessage *m):CentralLB(m) {}
-private:
-  CmiBool QueryBalanceNow(int step);
-  LBMigrateMsg* Strategy(CentralLB::LDStats* stats, int count);
+  RandRefLB(CkMigrateMessage *m):RandCentLB(m) {}
+  void work(CentralLB::LDStats* stats, int count);
 };
 
 #endif /* _RANDCENTLB_H_ */
index 41b317e578a024c38c7ddf49ea544af8c1bb98ff..1829e0b13cdc9cf282af09993df4e622ec111491 100644 (file)
@@ -116,7 +116,7 @@ LBMigrateMsg* RecBisectBfLB::Strategy(CentralLB::LDStats* stats,
    
       if (n.proc != i) {
        MigrateInfo *migrateMe = new MigrateInfo;
-       migrateMe->obj = stats[n.proc].objData[n.index].handle;
+       migrateMe->obj = stats->objData[n.index].handle;
        migrateMe->from_pe = n.proc;
        migrateMe->to_pe = i;
        migrateInfo.insertAtEnd(migrateMe);
index ca4c1c7ddc70e1036f1a18aa701be928cebdc6b7..b3cec60eea787ea3d01fe943a2b94e64609c9f50 100644 (file)
@@ -49,42 +49,42 @@ LBMigrateMsg* RefineLB::Strategy(CentralLB::LDStats* stats, int count)
 
   //  CkPrintf("[%d] RefineLB strategy\n",CkMyPe());
 
-  // remove non-migratable objects
   // RemoveNonMigratable(stats, count);
 
   // get original object mapping
-  int** from_procs = Refiner::AllocProcs(count, stats);
-  for(pe=0;pe < count; pe++) 
-    for(obj=0;obj<stats[pe].n_objs;obj++) 
-       from_procs[pe][obj] = pe;
+  int* from_procs = Refiner::AllocProcs(count, stats);
+  for(obj=0;obj<stats->n_objs;obj++)  {
+    int pe = stats->from_proc[obj];
+    from_procs[obj] = pe;
+  }
 
   // Get a new buffer to refine into
-  int** to_procs = Refiner::AllocProcs(count,stats);
+  int* to_procs = Refiner::AllocProcs(count,stats);
 
-  Refiner refiner(1.01);  // overload tolerance=1.05
+  Refiner refiner(1.003);  // overload tolerance=1.05
 
   refiner.Refine(count,stats,from_procs,to_procs);
 
   CkVec<MigrateInfo*> migrateInfo;
 
   // Save output
-  for(pe=0;pe < count; pe++) {
-    for(obj=0;obj<stats[pe].n_objs;obj++) {
-      if (to_procs[pe][obj] != pe) {
-       //      CkPrintf("[%d] Obj %d migrating from %d to %d\n",
-       //               CkMyPe(),obj,pe,to_procs[pe][obj]);
+  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]);
        MigrateInfo *migrateMe = new MigrateInfo;
-       migrateMe->obj = stats[pe].objData[obj].handle;
+       migrateMe->obj = stats->objData[obj].handle;
        migrateMe->from_pe = pe;
-       migrateMe->to_pe = to_procs[pe][obj];
+       migrateMe->to_pe = to_procs[obj];
        migrateInfo.insertAtEnd(migrateMe);
-      }
     }
   }
 
   int migrate_count=migrateInfo.length();
   LBMigrateMsg* msg = new(&migrate_count,1) LBMigrateMsg;
   msg->n_moves = migrate_count;
+  if (lb_debug) CmiPrintf("RefineLB> migrating %d objects.\n", migrate_count);
   for(int i=0; i < migrate_count; i++) {
     MigrateInfo* item = (MigrateInfo*)migrateInfo[i];
     msg->moves[i] = *item;
index 60619615575d7db810cbbb4d13db8e8cf1b76d2b..63fff74a10ce0c2437e80be859115985f89c56f4 100644 (file)
 
 #include "Refiner.h"
 
-int** Refiner::AllocProcs(int count, CentralLB::LDStats* stats)
+int* Refiner::AllocProcs(int count, CentralLB::LDStats* stats)
 {
-  int** bufs = new int*[count];
-
-  int total_objs=0;
-  int i;
-  for(i=0; i<count; i++) 
-    total_objs += stats[i].n_objs;
-
-  bufs[0] = new int[total_objs];
-
-  int cur_obj = 0;
-  for(i=1; i<count;i++) {
-    cur_obj += stats[i-1].n_objs;
-    bufs[i] = bufs[0] + cur_obj;
-  }
-  return bufs;
+  return new int[stats->n_objs];
 }
 
-void Refiner::FreeProcs(int** bufs)
+void Refiner::FreeProcs(int* bufs)
 {
-  delete [] bufs[0];
   delete [] bufs;
 }
 
-void Refiner::create(int count, CentralLB::LDStats* stats, int** procs)
+void Refiner::create(int count, CentralLB::LDStats* stats, int* procs)
 {
-  int i,j;
+  int i;
 
   P = count;
 
   // now numComputes is all the computes: migratable and not.
   // afterwards, nonmigratable computes will be taken off
-  numComputes = 0;
-  for(j=0; j < P; j++) numComputes+= stats[j].n_objs;
+  numComputes = stats->n_objs;
   computes = new computeInfo[numComputes];
 
   processors = new processorInfo[count];
 
   int index = 0;
   numAvail = 0;
-  for(j=0; j < count; j++) {
-    processors[j].Id = j;
-    processors[j].backgroundLoad = stats[j].bg_cputime;
-    processors[j].load = processors[j].backgroundLoad;
-    processors[j].computeLoad = 0;
-    processors[j].computeSet = new Set();
-    processors[j].pe_speed = stats[j].pe_speed;
-    processors[j].utilization = stats[j].utilization;
-    processors[j].available = stats[j].available;
-    if (processors[j].available == CmiTrue) numAvail++;
-
-    LDObjData *odata = stats[j].objData;
-    const int osz = stats[j].n_objs;  
-    for(i=0; i < osz; i++) {
+  for(i=0; i < count; i++) {
+    processors[i].Id = i;
+    processors[i].backgroundLoad = stats->procs[i].bg_cputime;
+    processors[i].load = processors[i].backgroundLoad;
+    processors[i].computeLoad = 0;
+    processors[i].computeSet = new Set();
+    processors[i].pe_speed = stats->procs[i].pe_speed;
+    processors[i].utilization = stats->procs[i].utilization;
+    processors[i].available = stats->procs[i].available;
+    if (processors[i].available == CmiTrue) numAvail++;
+  }
+
+  LDObjData *odata = stats->objData;
+  for (i=0; i<stats->n_objs; i++)
+  {
         computes[index].id = odata[i].id();
         computes[index].handle = odata[i].handle;
         computes[index].load = odata[i].cpuTime;
-        computes[index].originalPE = j;
+        computes[index].originalPE = stats->from_proc[i];
         computes[index].originalIdx = i;
         computes[index].processor = -1;
-        computes[index].oldProcessor = procs[j][i];
+        computes[index].oldProcessor = procs[i];
         computes[index].migratable = odata[i].migratable;
         index ++;
 /*
@@ -98,7 +83,6 @@ void Refiner::create(int count, CentralLB::LDStats* stats, int** procs)
         numComputes --;
       }
 */
-    }
   }
 //  for (i=0; i < numComputes; i++)
 //      processors[computes[i].oldProcessor].computeLoad += computes[i].load;
@@ -289,7 +273,7 @@ int Refiner::refine()
 }
 
 void Refiner::Refine(int count, CentralLB::LDStats* stats, 
-                    int** cur_p, int** new_p)
+                    int* cur_p, int* new_p)
 {
   //  CkPrintf("[%d] Refiner strategy\n",CkMyPe());
 
@@ -312,7 +296,7 @@ void Refiner::Refine(int count, CentralLB::LDStats* stats,
     computeInfo *c = (computeInfo *)
       processors[pe].computeSet->iterator((Iterator *)&nextCompute);
     while(c) {
-      new_p[c->originalPE][c->originalIdx] = c->processor;
+      new_p[c->originalIdx] = c->processor;
 //       if (c->oldProcessor != c->processor)
 //             CkPrintf("Refiner::Refine: from %d to %d\n",
 //                      c->oldProcessor, c->processor);
index 575c6694176d9a02ea0dc874f74083a2a81d86d4..9bcf484643ef312b01f1f3330f58cd16c15b4756 100644 (file)
@@ -28,12 +28,12 @@ public:
   };
   ~Refiner() { delete [] computes; delete [] processors; };
 
-  static int** AllocProcs(int count, CentralLB::LDStats* stats);
-  static void FreeProcs(int** bufs);
-  void Refine(int count, CentralLB::LDStats* stats, int** cur_p, int** new_p);
+  static int* AllocProcs(int count, CentralLB::LDStats* stats);
+  static void FreeProcs(int* bufs);
+  void Refine(int count, CentralLB::LDStats* stats, int* cur_p, int* new_p);
 
 private:
-  void create(int count, CentralLB::LDStats* stats, int** cur_p);
+  void create(int count, CentralLB::LDStats* stats, int* cur_p);
   int refine();
   void assign(computeInfo *c, int p);
   void assign(computeInfo *c, processorInfo *p);
index 0afdb013153c6e70af9d14913d04ba5fa31c69a6..b9a1b6cc8f16263099b97725962c33214ec25d90 100644 (file)
@@ -80,6 +80,14 @@ typedef struct {
 #endif
 } LDObjData;
 
+/* used for load balancer */
+typedef struct {
+  int index;
+  LDObjData data;
+  int from_proc;
+  int to_proc;
+} LDObjStats;
+
 typedef struct {
   int src_proc;
   LDOMid senderOM;