Added ability to process processor speed, processor availablilty,
authorSameer Paranjpye <paranjpy@uiuc.edu>
Tue, 1 Feb 2000 18:27:22 +0000 (18:27 +0000)
committerSameer Paranjpye <paranjpy@uiuc.edu>
Tue, 1 Feb 2000 18:27:22 +0000 (18:27 +0000)
non-migratable objects and background load to HeapCentLB.

src/ck-ldb/HeapCentLB.C
src/ck-ldb/HeapCentLB.h

index 13545953c2e6e986fd39de20287a20498ba2bb09..907f56886c09636f2f52618f94292c51a41bafc2 100644 (file)
@@ -29,82 +29,119 @@ void HeapCentLB::Heapify(HeapData *heap, int node, int heapSize)
 {
        int left = 2*node+1;
        int right = 2*node+2;
-       int largest;
+       int smallest;
 
-       if (left <= heapSize && heap[left].cpuTime < heap[node].cpuTime)
-               largest = left;
-       else largest = node;
+       if (left <= heapSize && heap[left].load > heap[node].load)
+               smallest = left;
+       else smallest = node;
        
-       if (right <= heapSize && heap[right].cpuTime < heap[largest].cpuTime
-               largest = right;
+       if (right <= heapSize && heap[right].load > heap[smallest].load
+               smallest = right;
 
-       if (largest != node) {
+       if (smallest != node) {
                HeapData obj;
                obj = heap[node];
-               heap[node] = heap[largest];
-               heap[largest] = obj;
-               Heapify(heap, largest, heapSize);
-       }
-               
+               heap[node] = heap[smallest];
+               heap[smallest] = obj;
+               Heapify(heap, smallest, heapSize);
+       }               
 }
 
 
-CLBMigrateMsg* HeapCentLB::Strategy(CentralLB::LDStats* stats, int count)
+//Inserts object into appropriate sorted position in the object array
+void HeapCentLB::InsertObject(HeapData *data, int index)
 {
-  int pe,obj;
-  //  CkPrintf("[%d] HeapCentLB strategy\n",CkMyPe());
+       HeapData key = data[index];
+       
+       for(int i = index-1; i >= 0 && objData[i].load < key.load; i--)
+               objData[i+1] = objData[i];
+       objData[i+1] = key;
+}
 
-  CkVector migrateInfo;
+HeapData* HeapCentLB::BuildObjectArray(CentralLB::LDStats* stats, 
+                                                                                                                                                        int count, int *objCount)
+{
+       HeapData *objData;
+
+       *objCount = 0;
+       for (int pe = 0; pe < count; pe++)
+               for (int obj = 0; obj < stats[pe].n_objs; obj++)
+                       if (stats[pe].objData[obj].migratable == CmiTrue) *objCount++; 
+
+       objData  = new HeapData[*objCount];
+       *objCount = 0; 
+       for(int pe=0; pe < count; pe++)
+               for(int 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;
+                               InsertObject(objData, *objCount++);
+                       }
+
+       return objData;
+}
 
-  int totalObjs = 0;
-  HeapData *cpuData = new HeapData[count];
-  HeapData *objData;
+HeapData* HeapCentLB::BuildCpuArray(CentralLB::LDStats* stats, 
+                                                                                                                                               int count, int *peCount)
+{
+       HeapData           *data;
+       CentralLB::LDStats *peData;
+       
+       *peCount = 0;
+       for (int pe = 0; pe < count; pe++)
+               if (stats[pe].available == CmiTrue) *peCount++;
 
-  for (pe=0; pe < count; pe++) {
-    totalObjs += stats[pe].n_objs;
-    cpuData[pe].cpuTime = 0.;
-    cpuData[pe].pe = cpuData[pe].id = pe;
-  }
+       data = new HeapData[*peCount];
+       
+       *peCount = 0;
+       for (int pe=0; pe < count; pe++) {
+               data[*peCount].load = 0.0;
+               peData = &(stats[pe]);
+
+               for (int obj = 0; obj < peData->n_objs; obj++) 
+                       if (peData->objData[obj].migratable == CmiFalse) 
+                               data[*peCount].load -= 
+                                       peData->objData[obj].wallTime * peData->pe_speed;
+                               
+               if (peData->available == CmiTrue) {
+                       data[*peCount].load += 
+                               (peData->total_walltime - peData->bg_walltime) * peData->pe_speed;
+                       data[*peCount].pe = data[*peCount].id = pe;
+                       InsertObject(data, *peCount);
+                       *peCount++;
+               }
+       }
+       
+       return data;
+}
 
-  objData = new HeapData[totalObjs];
-  int objCount = 0;
-  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);
+CLBMigrateMsg* HeapCentLB::Strategy(CentralLB::LDStats* stats, int count)
+{
+       CkVector migrateInfo;
+  int      obj, heapSize, objCount;
+  HeapData *cpuData = BuildCpuArray(stats, count, &heapSize);
+  HeapData *objData = BuildObjectArray(stats, count, &objCount);
 
-    for(obj=0; obj < stats[pe].n_objs; obj++, objCount++) {
-      objData[objCount].cpuTime = stats[pe].objData[obj].cpuTime;
-      objData[objCount].pe = pe;
-      objData[objCount].id = obj;
-    }
-  }
+  //  CkPrintf("[%d] HeapCentLB strategy\n",CkMyPe());
 
-  for (obj=1; obj < totalObjs; obj++) {
-    HeapData key = objData[obj];
-    int i = obj-1;
-    while (i >=0 && objData[i].cpuTime < key.cpuTime) {
-      objData[i+1] = objData[i];
-      i--;
-    }
-    objData[i+1] = key;
-  }
-  
-  int heapSize = count-1;
-  HeapData minCpu;     
-  for (obj=0; obj < totalObjs; obj++) {
-    // Operation of extracting the minimum(the least loaded processor)
+  heapSize--;
+  HeapData maxCpu;     
+  for (obj=0; obj < objCount; obj++) {
+    // Operation of extracting the the least loaded processor
     // from the heap
-    minCpu = cpuData[0];
+    maxCpu = cpuData[0];
     cpuData[0] = cpuData[heapSize];
     heapSize--;
     Heapify(cpuData, 0, heapSize);             
 
     // Increment the time of the least loaded processor by the cpuTime of
     // the `heaviest' object
-    minCpu.cpuTime += objData[obj].cpuTime;
+    maxCpu.load -= objData[obj].load;
 
     //Insert object into migration queue if necessary
-    const int dest = minCpu.pe;
+    const int dest = maxCpu.pe;
     const int pe   = objData[obj].pe;
     const int id   = objData[obj].id;
     if (dest != pe) {
@@ -116,15 +153,17 @@ CLBMigrateMsg* HeapCentLB::Strategy(CentralLB::LDStats* stats, int count)
       migrateMe->to_pe = dest;
       migrateInfo.push_back((void*)migrateMe);
     }
+
     //Insert the least loaded processor with load updated back into the heap
     heapSize++;
     int location = heapSize;
-    while (location>0 && cpuData[(location-1)/2].cpuTime > minCpu.cpuTime) {
+    while (location>0 && cpuData[(location-1)/2].load < maxCpu.load) {
       cpuData[location] = cpuData[(location-1)/2];
       location = (location-1)/2;
     }
-    cpuData[location] = minCpu;
+    cpuData[location] = maxCpu;
   }
+
   int migrate_count=migrateInfo.size();
   CkPrintf("HeapCentLB migrating %d elements\n",migrate_count);
   CLBMigrateMsg* msg = new(&migrate_count,1) CLBMigrateMsg;
@@ -139,3 +178,9 @@ CLBMigrateMsg* HeapCentLB::Strategy(CentralLB::LDStats* stats, int count)
 };
 
 #endif
+
+
+
+
+
+
index 784d88d2dbc096952c43db97b414e3d3e3f07573..20087ee8007959b5182c5ab4ccd4edbcb110b33f 100644 (file)
@@ -9,16 +9,19 @@ void CreateHeapCentLB();
 class HeapCentLB : public CentralLB {
 
 struct HeapData {
-       float cpuTime;
-       int   pe;
-       int   id;
+       double load;
+       int    pe;
+       int    id;
 };
 
 public:
   HeapCentLB();
 private:
-  void    Heapify(HeapData *, int, int);
-  CmiBool QueryBalanceNow(int step);
+  void           Heapify(HeapData *, int, int);
+  void           InsertObject(HeapData *, int);
+  HeapData*      BuildCpuArray(CentralLB::LDStats*, int, int *);      
+  HeapData*      BuildObjectArray(CentralLB::LDStats*, int, int *);      
+  CmiBool        QueryBalanceNow(int step);
   CLBMigrateMsg* Strategy(CentralLB::LDStats* stats, int count);
 };