Removed all STL template code from load balancer. Too bad STL doesn't work
[charm.git] / src / ck-ldb / HeapCentLB.C
1 #include <charm++.h>
2
3 #if CMK_LBDB_ON
4
5 #include "CkLists.h"
6 #include "HeapCentLB.h"
7 #include "HeapCentLB.def.h"
8
9 void CreateHeapCentLB()
10 {
11   CkPrintf("[%d] creating HeapCentLB %d\n",CkMyPe(),loadbalancer);
12   loadbalancer = CProxy_HeapCentLB::ckNew();
13   CkPrintf("[%d] created HeapCentLB %d\n",CkMyPe(),loadbalancer);
14 }
15
16 HeapCentLB::HeapCentLB()
17 {
18   CkPrintf("[%d] HeapCentLB created\n",CkMyPe());
19 }
20
21 CmiBool HeapCentLB::QueryBalanceNow(int _step)
22 {
23   CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
24   return CmiTrue;
25 }
26
27 void HeapCentLB::Heapify(HeapData *heap, int node, int heapSize)
28 {
29         int left = 2*node+1;
30         int right = 2*node+2;
31         int largest;
32
33         if (left <= heapSize && heap[left].cpuTime < heap[node].cpuTime)
34                 largest = left;
35         else largest = node;
36         
37         if (right <= heapSize && heap[right].cpuTime < heap[largest].cpuTime) 
38                 largest = right;
39
40         if (largest != node) {
41                 HeapData obj;
42                 obj = heap[node];
43                 heap[node] = heap[largest];
44                 heap[largest] = obj;
45                 Heapify(heap, largest, heapSize);
46         }
47                 
48 }
49
50
51 CLBMigrateMsg* HeapCentLB::Strategy(CentralLB::LDStats* stats, int count)
52 {
53   int pe,obj;
54   CkPrintf("[%d] HeapCentLB strategy\n",CkMyPe());
55
56   CkVector migrateInfo;
57
58   int totalObjs = 0;
59   HeapData *cpuData = new HeapData[count];
60   HeapData *objData;
61
62   for (pe=0; pe < count; pe++) {
63     totalObjs += stats[pe].n_objs;
64     cpuData[pe].cpuTime = 0.;
65     cpuData[pe].pe = cpuData[pe].id = pe;
66   }
67
68   objData = new HeapData[totalObjs];
69   int objCount = 0;
70   for(pe=0; pe < count; pe++) {
71     CkPrintf("[%d] PE %d : %d Objects : %d Communication\n",
72              CkMyPe(),pe,stats[pe].n_objs,stats[pe].n_comm);
73
74     for(obj=0; obj < stats[pe].n_objs; obj++, objCount++) {
75       objData[objCount].cpuTime = stats[pe].objData[obj].cpuTime;
76       objData[objCount].pe = pe;
77       objData[objCount].id = obj;
78     }
79   }
80
81   for (obj=1; obj < totalObjs; obj++) {
82     HeapData key = objData[obj];
83     int i = obj-1;
84     while (i >=0 && objData[i].cpuTime < key.cpuTime) {
85       objData[i+1] = objData[i];
86       i--;
87     }
88     objData[i+1] = key;
89   }
90   
91   int heapSize = count-1;
92   HeapData minCpu;      
93   for (obj=0; obj < totalObjs; obj++) {
94     // Operation of extracting the minimum(the least loaded processor)
95     // from the heap
96     minCpu = cpuData[0];
97     cpuData[0] = cpuData[heapSize];
98     heapSize--;
99     Heapify(cpuData, 0, heapSize);              
100
101     // Increment the time of the least loaded processor by the cpuTime of
102     // the `heaviest' object
103     minCpu.cpuTime += objData[obj].cpuTime;
104
105     //Insert object into migration queue if necessary
106     const int dest = minCpu.pe;
107     const int pe   = objData[obj].pe;
108     const int id   = objData[obj].id;
109     if (dest != pe) {
110       CkPrintf("[%d] Obj %d migrating from %d to %d\n",
111                CkMyPe(),obj,pe,dest);
112       MigrateInfo *migrateMe = new MigrateInfo;
113       migrateMe->obj = stats[pe].objData[id].handle;
114       migrateMe->from_pe = pe;
115       migrateMe->to_pe = dest;
116       migrateInfo.push_back((void*)migrateMe);
117     }
118     //Insert the least loaded processor with load updated back into the heap
119     heapSize++;
120     int location = heapSize;
121     while (location>0 && cpuData[(location-1)/2].cpuTime > minCpu.cpuTime) {
122       cpuData[location] = cpuData[(location-1)/2];
123       location = (location-1)/2;
124     }
125     cpuData[location] = minCpu;
126   }
127   int migrate_count=migrateInfo.size();
128   CLBMigrateMsg* msg = new(&migrate_count,1) CLBMigrateMsg;
129   msg->n_moves = migrate_count;
130   for(int i=0; i < migrate_count; i++) {
131     MigrateInfo* item = (MigrateInfo*) migrateInfo[i];
132     msg->moves[i] = *item;
133     delete item;
134     migrateInfo[i] = 0;
135   }
136   return msg;
137 };
138
139 #endif