af07a3025e111f76d943b4679f599cee90090fea
[charm.git] / src / ck-ldb / RefineSwapLB.C
1 /** \file RefineSwapLB.C
2  *
3  *  Written by Gengbin Zheng
4  *  Updated by Abhinav Bhatele, 2010-12-09 to use ckgraph
5  *
6  *  Status:
7  *    -- Does not support pe_speed's currently
8  *    -- Does not support nonmigratable attribute
9  */
10
11 /**
12  * \addtogroup CkLdb
13 */
14 /*@{*/
15
16 #include "RefineSwapLB.h"
17 #include "ckgraph.h"
18 #include <algorithm>
19 #include <iostream>
20
21 using std::cout;
22 using std::endl;
23
24 CreateLBFunc_Def(RefineSwapLB, "always assign the heaviest obj onto lightest loaded processor.")
25
26 RefineSwapLB::RefineSwapLB(const CkLBOptions &opt): CentralLB(opt)
27 {
28   lbname = "RefineSwapLB";
29   if (CkMyPe()==0)
30     CkPrintf("[%d] RefineSwapLB created\n",CkMyPe());
31 }
32
33 CmiBool RefineSwapLB::QueryBalanceNow(int _step)
34 {
35   //  CkPrintf("[%d] Balancing on step %d\n",CkMyPe(),_step);
36   return CmiTrue;
37 }
38
39 class ProcLoadGreater {
40   public:
41     bool operator()(ProcInfo p1, ProcInfo p2) {
42       return (p1.getTotalLoad() > p2.getTotalLoad());
43     }
44 };
45
46 class ProcLoadGreaterIndex {
47  public: 
48   ProcLoadGreaterIndex(ProcArray * parr) : parr(parr) {}
49   bool operator()(int lhs, int rhs) {
50     return (parr->procs[lhs].getTotalLoad() < parr->procs[rhs].getTotalLoad());
51   }
52  private:
53   ProcArray *parr;
54 };
55
56 class ObjLoadGreater {
57   public:
58     bool operator()(Vertex v1, Vertex v2) {
59       return (v1.getVertexLoad() > v2.getVertexLoad());
60     }
61 };
62
63
64 void RefineSwapLB::work(LDStats* stats)
65 {
66   /** ========================== INITIALIZATION ============================= */
67   ProcArray *parr = new ProcArray(stats);       // Processor Array
68   ObjGraph *ogr = new ObjGraph(stats);          // Object Graph
69
70
71   /** ============================= STRATEGY ================================ */
72   //parr->resetTotalLoad();
73
74   if (_lb_args.debug()>1) 
75     CkPrintf("[%d] In RefineSwapLB strategy\n",CkMyPe());
76
77   int vert;
78   double avg_load = parr->getAverageLoad();
79   double threshold = avg_load * 0.01;
80   double lower_bound_load = avg_load - threshold;
81   double upper_bound_load = avg_load + threshold;
82   cout <<"Average load " << avg_load << endl;
83   
84   std::vector<int> min_pe_heap;
85   std::vector<int> max_pe_heap;
86
87   std::vector<int>* pe_obj = new std::vector<int>[parr->procs.size()];
88
89   // Construct max heap of overloaded processors and min heap of underloaded
90   // processors.
91   for (int i = 0; i < parr->procs.size(); i++) {
92     if (parr->procs[i].getTotalLoad() > upper_bound_load) {
93       max_pe_heap.push_back(i);
94     } else if (parr->procs[i].getTotalLoad() < lower_bound_load) {
95       min_pe_heap.push_back(i);
96     }
97   }
98
99   // Create a datastructure to store the objects in a processor
100   for (int i = 0; i < ogr->vertices.size(); i++) {
101     pe_obj[ogr->vertices[i].getCurrentPe()].push_back(i);
102   }
103
104   std::make_heap(max_pe_heap.begin(), max_pe_heap.end(), ProcLoadGreaterIndex(parr));
105
106   int best_p;
107   int best_obj;
108   int iter_location;
109   int obj_iter_location;
110   int min_pe_iter;
111   int min_weight_obj;
112   int min_iter_location;
113   while (max_pe_heap.size() != 0 && min_pe_heap.size() != 0) {
114     int ideal_transfer_pe = 0;
115     int p_index = max_pe_heap.front();
116     double best_size = 0.0;
117     double obj_wg_min = 100.0;
118     int allocated = false;
119     int obj_considered;
120     int pe_considered;
121     ProcInfo &pinfo = parr->procs[p_index];
122     std::pop_heap(max_pe_heap.begin(), max_pe_heap.end(),
123         ProcLoadGreaterIndex(parr));
124     max_pe_heap.pop_back();
125     cout << "Picked max pe " << p_index << " (" <<
126         parr->procs[p_index].getTotalLoad() << ")" << endl;
127
128     // Iterate over all the min pes and see which is the best object to
129     // transfer.
130     for (int j = 0; j < min_pe_heap.size(); j++) {
131       for (int i = 0; i < pe_obj[p_index].size(); i++) {
132         obj_considered = pe_obj[p_index][i];
133         pe_considered = min_pe_heap[j];
134
135         if (pe_obj[pe_considered].size() > pe_obj[ideal_transfer_pe].size()) {
136           ideal_transfer_pe = pe_considered;
137         }
138         if (ogr->vertices[obj_considered].getVertexLoad() < obj_wg_min) {
139           min_weight_obj = obj_considered;
140           min_iter_location = i;
141         }
142
143         if (parr->procs[pe_considered].getTotalLoad() + ogr->vertices[obj_considered].getVertexLoad() < (avg_load + threshold)) {
144           if (ogr->vertices[obj_considered].getVertexLoad() > best_size) {
145             best_obj = obj_considered;
146             best_size = ogr->vertices[obj_considered].getVertexLoad();
147             best_p = pe_considered;
148             iter_location = i;
149             min_pe_iter = j;
150             allocated = true;
151           }
152         }
153       }
154     }
155
156     if (allocated) {
157       // Set the new pe
158       ogr->vertices[best_obj].setNewPe(best_p);
159
160       // Remove from pe_obj
161       pe_obj[p_index].erase(pe_obj[p_index].begin() + iter_location);
162       pe_obj[best_p].push_back(best_obj);
163
164       // Update load of underloaded and overloaded
165       parr->procs[p_index].setTotalLoad(parr->procs[p_index].getTotalLoad() -
166           best_size);
167       parr->procs[best_p].setTotalLoad(parr->procs[best_p].getTotalLoad() +
168           best_size);
169
170       std::cout << " Moving obj " << best_obj << " (" << best_size << ") from " << p_index << " to " <<
171             best_p << " New load " << p_index << ":" << parr->procs[p_index].getTotalLoad()
172             << " " << best_p << ":" << parr->procs[best_p].getTotalLoad()<< std::endl; 
173
174       // Update the max heap and min list
175       if (parr->procs[p_index].getTotalLoad() > (avg_load + threshold)) {
176         // Reinsert
177         max_pe_heap.push_back(p_index);
178         std::push_heap(max_pe_heap.begin(), max_pe_heap.end(),
179             ProcLoadGreaterIndex(parr));
180       } else if (parr->procs[p_index].getTotalLoad() < (avg_load - threshold)) {
181         // Insert into the list of underloaded procs
182         min_pe_heap.push_back(p_index);
183       }
184
185       if (parr->procs[best_p].getTotalLoad() > (avg_load - threshold)) {
186         // Remove from list of underloaded procs
187         min_pe_heap.erase(min_pe_heap.begin() + min_pe_iter);
188       }
189     } else {
190       // Swap with something. 
191       // TODO:
192       cout << " Swapping needs to be done" << endl;
193       best_size = 0.0;
194       int temp_iter = -1;
195       for (int i = 0; i < pe_obj[ideal_transfer_pe].size(); i++) {
196         obj_considered = pe_obj[ideal_transfer_pe][i];
197         // Find the max weight obj from the ideal transfer pe.
198           if (ogr->vertices[obj_considered].getVertexLoad() > best_size &&
199               ogr->vertices[min_weight_obj].getVertexLoad() < ogr->vertices[obj_considered].getVertexLoad()) {
200             best_obj = obj_considered;
201             best_size = ogr->vertices[obj_considered].getVertexLoad();
202             temp_iter = i;
203           }
204       }
205           // Swap max weight obj from 
206
207       // Set the new pe
208       ogr->vertices[obj_considered].setNewPe(p_index);
209       ogr->vertices[min_weight_obj].setNewPe(ideal_transfer_pe);
210
211       // Remove from pe_obj
212       pe_obj[p_index].erase(pe_obj[p_index].begin() + min_iter_location);
213       pe_obj[ideal_transfer_pe].erase(pe_obj[ideal_transfer_pe].begin() + temp_iter);
214       pe_obj[p_index].push_back(obj_considered);
215       pe_obj[ideal_transfer_pe].push_back(min_weight_obj);
216
217       // Update load of underloaded and overloaded
218       parr->procs[p_index].setTotalLoad(parr->procs[p_index].getTotalLoad() +
219           ogr->vertices[obj_considered].getVertexLoad() - ogr->vertices[min_weight_obj].getVertexLoad());
220       parr->procs[ideal_transfer_pe].setTotalLoad(parr->procs[best_p].getTotalLoad() -
221           ogr->vertices[obj_considered].getVertexLoad() + ogr->vertices[min_weight_obj].getVertexLoad());
222
223       // Update the max heap and min list
224       if (parr->procs[p_index].getTotalLoad() > (avg_load + threshold)) {
225         // Reinsert
226         max_pe_heap.push_back(p_index);
227         std::push_heap(max_pe_heap.begin(), max_pe_heap.end(),
228             ProcLoadGreaterIndex(parr));
229       } else if (parr->procs[p_index].getTotalLoad() < (avg_load - threshold)) {
230         // Insert into the list of underloaded procs
231         min_pe_heap.push_back(p_index);
232       }
233
234       if (parr->procs[ideal_transfer_pe].getTotalLoad() > (avg_load + threshold)) {
235         // Reinsert
236         max_pe_heap.push_back(ideal_transfer_pe);
237         std::push_heap(max_pe_heap.begin(), max_pe_heap.end(),
238             ProcLoadGreaterIndex(parr));
239         min_pe_heap.erase(min_pe_heap.begin() + min_pe_iter);
240       } else if (parr->procs[ideal_transfer_pe].getTotalLoad() > (avg_load - threshold)) {
241         // Remove from list of underloaded procs
242         min_pe_heap.erase(min_pe_heap.begin() + min_pe_iter);
243       }
244
245        cout << "  Swapping " << obj_considered << " (" <<
246        ogr->vertices[obj_considered].getVertexLoad() << ") " <<  min_weight_obj
247        << "(" << ogr->vertices[min_weight_obj].getVertexLoad() << ")"
248        <<  " from " << ideal_transfer_pe << " (" <<
249        parr->procs[ideal_transfer_pe].getTotalLoad() <<
250        ") to " << p_index << " (" << parr->procs[p_index].getTotalLoad() << ")"<< endl; 
251     }
252   }
253
254   std::cout << "Overloaded Processor load"<< endl;
255   for (int i = 0; i < max_pe_heap.size(); i++) {
256     std::cout << max_pe_heap[i] << ": " << parr->procs[max_pe_heap[i]].getTotalLoad() << std::endl;
257   }
258
259   /** ============================== CLEANUP ================================ */
260   ogr->convertDecisions(stats);         // Send decisions back to LDStats
261   delete[] pe_obj;
262   delete parr;
263   delete ogr;
264 }
265
266 #include "RefineSwapLB.def.h"
267
268 /*@}*/
269