Now these strategies use heapsort to construct the objetc array which is a
authorSameer Paranjpye <paranjpy@uiuc.edu>
Wed, 2 Feb 2000 05:12:18 +0000 (05:12 +0000)
committerSameer Paranjpye <paranjpy@uiuc.edu>
Wed, 2 Feb 2000 05:12:18 +0000 (05:12 +0000)
considerable saving in computation.

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

index d821ca6a7214b5d64003ef9799ec3e296e63d0d5..5bd1e5229fae6b148df322b8f74c140516ae8b3c 100644 (file)
@@ -47,16 +47,26 @@ void GreedyRefLB::Heapify(HeapData *heap, int node, int heapSize)
   }    
 }
 
+void GreedyRefLB::BuildHeap(HeapData *data, int heapSize)
+{
+       int i;
+       for(i=heapSize/2; i >= 0; i--)
+               Heapify(data, i, heapSize);
+}
 
-//Inserts object into appropriate sorted position in the object array
-void GreedyRefLB::InsertObject(HeapData *objData, int index)
+void GreedyRefLB::HeapSort(HeapData *data, int heapSize)
 {
-  HeapData key = objData[index];
-  
-  int i;
-  for(i = index-1; i >= 0 && objData[i].load < key.load; i--)
-    objData[i+1] = objData[i];
-  objData[i+1] = key;
+       int i;
+       HeapData key;
+
+       BuildHeap(data, heapSize);
+       for (i=heapSize; i > 0; i--) {
+               key = data[0];
+               data[0] = data[i];
+               data[i] = key;
+               heapSize--;
+               Heapify(data, 0, heapSize);
+       }
 }
 
 GreedyRefLB::HeapData* 
@@ -80,14 +90,15 @@ GreedyRefLB::BuildObjectArray(CentralLB::LDStats* stats,
           stats[pe].objData[obj].wallTime * stats[pe].pe_speed;
         objData[*objCount].pe = pe;
         objData[*objCount].id = obj;
-        InsertObject(objData, (*objCount)++);
+                               (*objCount)++;
       }
-
+       HeapSort(objData, *objCount-1);
   return objData;
 }
 
-GreedyRefLB::HeapData* GreedyRefLB::BuildCpuArray(CentralLB::LDStats* stats, 
-                                    int count, int *peCount)
+GreedyRefLB::HeapData* 
+GreedyRefLB::BuildCpuArray(CentralLB::LDStats* stats, 
+                                                                                                        int count, int *peCount)
 {
   HeapData           *data;
   CentralLB::LDStats *peData;
@@ -104,19 +115,19 @@ GreedyRefLB::HeapData* GreedyRefLB::BuildCpuArray(CentralLB::LDStats* stats,
     data[*peCount].load = 0.0;
     peData = &(stats[pe]);
 
-    for (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)++);
-    }
+                        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->total_walltime - peData->bg_walltime) * peData->pe_speed;
+                        data[*peCount].pe = data[*peCount].id = pe;
+                        (*peCount)++;
+                }
   }
-  
+  BuildHeap(data, *peCount-1);
   return data;
 }
 
index d09ce89256c0839404991fb69cb64576dd99e0ab..29a6060c1f5b8ee2bbe0d3283c4969b78940cff8 100644 (file)
@@ -19,7 +19,8 @@ public:
   GreedyRefLB();
 private:
   void           Heapify(HeapData *, int, int);
-  void           InsertObject(HeapData *, int);
+  void           HeapSort(HeapData*, int);
+       void           BuildHeap(HeapData*, int);
   HeapData*      BuildCpuArray(CentralLB::LDStats*, int, int *);      
   HeapData*      BuildObjectArray(CentralLB::LDStats*, int, int *);      
   CmiBool        QueryBalanceNow(int step);