doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / RefineKLB.C
1 /**
2  * \addtogroup CkLdb
3 */
4 /*@{*/
5
6 #include "elements.h"
7 #include "ckheap.h"
8 #include "RefineKLB.h"
9
10 #define _USE_APPROX_ALGO_ 1
11 #define _USE_RESIDUAL_MOVES_ 1
12 //#include "heap.h"
13
14 CreateLBFunc_Def(RefineKLB, "Move objects away from overloaded processor to reach average")
15
16 RefineKLB::RefineKLB(const CkLBOptions &opt): CentralLB(opt)
17 {
18   lbname = (char *)"RefineKLB";
19   if (CkMyPe() == 0)
20     CkPrintf("[%d] RefineKLB created\n",CkMyPe());
21 }
22
23 void RefineKLB::work(LDStats* stats)
24 {
25   int obj;
26   int n_pes = stats->nprocs();
27
28   //  CkPrintf("[%d] RefineKLB strategy\n",CkMyPe());
29
30   // RemoveNonMigratable(stats, n_pes);
31
32   // get original object mapping
33   int* from_procs = RefinerApprox::AllocProcs(n_pes, stats);
34   for(obj=0;obj<stats->n_objs;obj++)  {
35     int pe = stats->from_proc[obj];
36     from_procs[obj] = pe;
37   }
38
39   // Get a new buffer to refine into
40   int* to_procs = RefinerApprox::AllocProcs(n_pes, stats);
41
42   RefinerApprox refiner(1.003);  // overload tolerance=1.003
43
44   if(_lb_args.percentMovesAllowed()>0 && _USE_APPROX_ALGO_)
45   {
46     refiner.Refine(n_pes, stats, from_procs, to_procs, _lb_args.percentMovesAllowed());
47   }
48   else
49   {
50     for(obj=0;obj<stats->n_objs;obj++)  
51     {
52       to_procs[obj] = stats->from_proc[obj];
53     }
54   }
55
56   // Save output
57   int numMoves=0;
58   for(obj=0;obj<stats->n_objs;obj++) 
59   {
60     int pe = stats->from_proc[obj];
61     if (to_procs[obj] != pe) 
62     {
63       // CkPrintf("[%d] Obj %d migrating from %d to %d\n",
64       //         CkMyPe(),obj,pe,to_procs[obj]);
65       stats->to_proc[obj] = to_procs[obj];
66       numMoves++;
67     }
68   }
69   int maxMoves=0.01*(stats->n_objs)*(_lb_args.percentMovesAllowed());
70   int availableMoves=maxMoves-numMoves;
71
72   //Perform Additional Moves in Greedy Fashion
73   if(availableMoves>0 && _USE_RESIDUAL_MOVES_)
74   {
75     int *to_procs2=new int[stats->n_objs];
76     performGreedyMoves(n_pes, stats, to_procs, to_procs2, availableMoves);
77
78     int nmoves2=0;
79     for(obj=0;obj<stats->n_objs;obj++)
80     {
81       if(to_procs2[obj]!=to_procs[obj])
82       {
83         stats->to_proc[obj]=to_procs2[obj];
84         nmoves2++;
85       }
86     }
87     delete[] to_procs2;
88   }
89
90   // Free the refine buffers
91   RefinerApprox::FreeProcs(from_procs);
92   RefinerApprox::FreeProcs(to_procs);
93 }
94
95 void RefineKLB::performGreedyMoves(int count, BaseLB::LDStats* stats,int *from_procs, int *to_procs, int numMoves)
96 {
97   //Calculate load per proc and objs per proc
98   int *objPerProc=new int[count];
99   double *loadPerProc=new double[count];
100   int i;
101   for(i=0;i<count;i++)
102   {
103     objPerProc[i]=0;
104     loadPerProc[i]=stats->procs[i].bg_walltime;
105   }
106   for(i=0;i<stats->n_objs;i++)
107   {
108     to_procs[i]=from_procs[i];
109     objPerProc[from_procs[i]]++;
110     loadPerProc[from_procs[i]]+=(stats->objData[i]).wallTime;
111   }
112
113   //Create a MaxHeap to select most-loaded procs
114   maxHeap *procLoad=new maxHeap(count);
115   for(i=0;i<count;i++)
116   {
117     InfoRecord *rec=new InfoRecord();
118     rec->load=loadPerProc[i];
119     rec->Id=i;
120     procLoad->insert(rec);
121   }
122
123   //Create a MaxHeap(for every proc) for selecting heaviest computes from each proc
124   maxHeap **procObjs=new maxHeap*[count];
125   for(i=0;i<count;i++)
126   {
127     procObjs[i]=new maxHeap(objPerProc[i]);
128   }
129   for(i=0;i<stats->n_objs;i++)
130   {
131     if((stats->objData[i]).migratable == CmiFalse)
132       continue;
133     InfoRecord *rec=new InfoRecord();
134     rec->load=(stats->objData[i]).wallTime;
135     rec->Id=i;
136     procObjs[from_procs[i]]->insert(rec);
137   }
138
139   //Pick k'(=numMoves) computes one-by-one by picking largest computes from most -loaded procs;
140   //Place in unassignedHeap;
141   maxHeap *unassignedComputes=new maxHeap(numMoves);
142   for(i=0;i<numMoves;i++)
143   {
144     InfoRecord *maxProc=procLoad->deleteMax();
145     
146     InfoRecord *maxObj=procObjs[maxProc->Id]->deleteMax();
147     if(!maxObj)
148     {
149       procLoad->insert(maxProc);
150       break;
151     }
152     unassignedComputes->insert(maxObj);
153
154     maxProc->load-=maxObj->load;
155     loadPerProc[maxProc->Id]=maxProc->load;
156
157     procLoad->insert(maxProc);
158   }
159
160   //Assign one-by-one to least-loaded proc
161   minHeap *leastLoadedP=new minHeap(count);
162   for(i=0;i<count;i++)
163   {
164     leastLoadedP->insert(procLoad->deleteMax());
165   }
166
167   for(i=0;i<numMoves;i++)
168   {
169     InfoRecord *c=unassignedComputes->deleteMax();
170     if(!c)
171       break;
172
173     InfoRecord *proc=leastLoadedP->deleteMin();
174     proc->load+=c->load;
175     leastLoadedP->insert(proc);
176
177     to_procs[c->Id]=proc->Id;
178     delete c;
179   }
180
181   //free up memory
182   delete[] objPerProc;
183   delete[] loadPerProc;
184   for(i=0;i<count;i++)
185   {
186     delete procObjs[i];
187   }
188   delete procObjs;
189   delete unassignedComputes;
190   delete leastLoadedP;
191 }
192
193 #include "RefineKLB.def.h"
194
195 /*@}*/