bb8e65439b94067eaa88fd8dd9d75860f73f942b
[charm.git] / src / ck-ldb / RefineTopoLB.C
1 /**************************************************************************
2 RefineTopoLB: 
3 This is a topology-aware load balancer.
4 Author: Tarun Agarwal (tarun)
5 Date: 04/27/2005
6 ***************************************************************************/
7 #include <math.h>
8 #include <stdlib.h>
9 #include "charm++.h"
10 #include "cklists.h"
11 #include "CentralLB.h"
12
13 #include "RefineTopoLB.decl.h"
14
15 #include "RefineTopoLB.h"
16
17 #define alpha PER_MESSAGE_SEND_OVERHEAD_DEFAULT  /*Startup time per message, seconds*/
18 #define beta PER_BYTE_SEND_OVERHEAD_DEFAULT     /*Long-message time per byte, seconds*/
19 #define DEG_THRES 0.50
20 #define EPSILON  -0.001
21
22 #define _lb_debug_on 0
23 #define _lb_debug2_on 0
24 #define _make_new_grouping_ 0
25 #define _USE_MAX_HOPBYTES_ 1
26
27 CreateLBFunc_Def(RefineTopoLB,"TopoLB: Balance objects based on the network topology")
28
29
30 RefineTopoLB::RefineTopoLB(const CkLBOptions &opt) : TopoLB (opt)
31 {
32   lbname = "RefineTopoLB";
33   if (CkMyPe () == 0) {
34     CkPrintf ("[%d] RefineTopoLB created\n",CkMyPe());
35   }
36 }
37
38 CmiBool RefineTopoLB::QueryBalanceNow (int _step)
39 {
40   return CmiTrue;
41 }
42
43 void RefineTopoLB :: work(CentralLB::LDStats *stats,int count)
44 {
45   int i, j;
46   if (_lb_args.debug() >= 2) 
47   {
48     CkPrintf("In TopoLB Strategy...\n");
49   }
50   
51   /****Make sure that there is at least one available processor.***/
52   int proc;
53   for (proc = 0; proc < count; proc++) 
54   {
55     if (stats->procs[proc].available)  
56       break;
57   }
58         
59   if (proc == count) 
60   {
61     CmiAbort ("TopoLB: no available processors!");
62   }
63  
64   removeNonMigratable(stats,count);
65
66   if(_lb_debug_on)
67   {
68     CkPrintf("Num of procs: %d\n",count);
69     CkPrintf("Num of objs:  %d\n",stats->n_objs);
70   }
71
72   /**************Initialize Topology ****************************/
73   LBtopoFn topofn;
74   topofn = LBTopoLookup(_lbtopo);
75   if (topofn == NULL) 
76   {
77         char str[1024];
78     CmiPrintf("TopoLB> Fatal error: Unknown topology: %s. Choose from:\n", _lbtopo);
79     printoutTopo();
80     sprintf(str, "TopoLB> Fatal error: Unknown topology: %s", _lbtopo);
81     CmiAbort(str);
82   }
83   topo = topofn(count);
84   /**************************************************************/
85   if(_lb_debug_on)
86     CkPrintf("before computing partitions...\n");
87   
88   int *newmap = new int[stats->n_objs];
89   if(_make_new_grouping_)
90     computePartitions(stats,count,newmap);
91   else
92   {
93     for(int i=0;i<stats->n_objs;i++)
94     {
95       newmap[i]=stats->from_proc[i];
96     }
97   }
98   /***************** Fill Data Structures *************************/
99   if(_lb_debug_on)
100     CkPrintf("before allocating dataStructures...\n");
101   allocateDataStructures(count);
102   if(_lb_debug_on)
103     CkPrintf("before initizlizing dataStructures...\n");
104   initDataStructures(stats,count,newmap);
105   if(_lb_debug_on)
106     CkPrintf("After initizlizing dataStructures...\n");
107
108   for(i=0;i<count;i++)
109     assign[i]=i;
110   
111
112
113   if(_lb_debug_on)
114     printDataStructures(count, stats->n_objs,newmap);
115   /***************** Perform RefineMent *************************/
116   bool *swapdone=new bool[count];
117   for(i=0;i<count;i++)
118     swapdone[i]=false;
119
120     
121   //double hbval=getHopBytes(stats,count,stats->from_proc);
122   //double hbval=getHopBytesNew(NULL,count);
123  // CkPrintf(" Before Mapping Original   hopBytes : %lf  Avg comm hops: %lf\n", hbval,hbval/total_comm);
124   //Perform ith swap
125   double totalGain=0;
126   for(i=0;i<count;i++)
127   {
128     //select the cpart which is most communicating and hasn't been moved yet
129     if(_USE_MAX_HOPBYTES_)
130     {
131       updateCommUA(count);
132     }
133     int cpart=-1;
134     double maxComm=-1;
135     for(j=0;j<count;j++)
136     {
137       if(swapdone[j]) continue;
138       if(commUA[j]>maxComm)
139       {
140         maxComm=commUA[j];
141         cpart=j;
142       }
143     }
144     CmiAssert(cpart!=-1);
145
146     //Next find a cpart for swap
147     int swapcpart=-1;
148     double gainMax=-1;
149     double gain=-1;;
150     //double orig_value=getHopBytesNew(assign,count);
151     for(j=0;j<count;j++)
152     {
153       if(j==cpart)
154         continue;
155
156       gain=findSwapGain(j,cpart,count);
157
158       //CkPrintf("%lf : %lf\n",gain,findSwapGain(j,cpart,count));
159       if(gain>gainMax && gain>0)
160       {
161         gainMax=gain;
162         swapcpart=j;
163       }
164     }
165     if(swapcpart==-1)
166     {
167       swapdone[cpart]=true;
168       continue;
169     }
170     totalGain+=gainMax;
171     CmiAssert(swapcpart!=-1);
172     
173     //Actually swap
174     int temp=assign[cpart];
175     assign[cpart]=assign[swapcpart];
176     assign[swapcpart]=temp;
177     swapdone[cpart]=true;
178   
179     //CkPrintf("Gain: %lf  Total_Gain: %lf HopBytes: %lf\n ",gainMax,totalGain,getHopBytesNew(stats,count,newmap));
180     //CkPrintf(" %lf  getHopBytesNew(stats,count,newmap);
181     //CkPrintf("Swap# %d:  %d and %d\n",i+1,cpart,swapcpart);
182   }
183   /******************* Assign mapping and print Stats*********/
184   for(i=0;i<stats->n_objs;i++)
185   {
186     stats->to_proc[i]= assign[newmap[i]];
187   }
188   if(_lb_debug2_on)
189   {
190     //double hbval=getHopBytes(stats,count,stats->from_proc);
191     double hbval1=getHopBytesNew(NULL,count);
192     CkPrintf(" Original   hopBytes : %lf  Avg comm hops: %lf\n", hbval1,hbval1/total_comm);
193     double hbval2=getHopBytesNew(assign,count);
194     CkPrintf(" Resulting  hopBytes : %lf  Avg comm hops: %lf\n", hbval2,hbval2/total_comm);
195     CkPrintf(" Percentage gain %.2lf\n",(hbval1-hbval2)*100/hbval1);
196     CkPrintf("\n");
197   }
198   freeDataStructures(count);
199   delete[] newmap;
200   delete[] swapdone;
201 }
202
203 double RefineTopoLB::findSwapGain(int cpart1, int cpart2,int count)
204 {
205   double oldvalue=0;
206   int proc1=assign[cpart1];
207   int proc2=assign[cpart2];
208   int proci=-1;
209
210   for(int i=0;i<count;i++)
211   {
212     proci=assign[i];
213     if(i!=cpart1 && i!=cpart2)
214     {
215       //oldvalue+=comm[cpart1][i]*(dist[proc1][proci]-dist[proc2][proci]);
216       //oldvalue+=comm[cpart2][i]*(dist[proc2][proci]-dist[proc1][proci]);
217       oldvalue+=(comm[cpart1][i]-comm[cpart2][i])*(dist[proc1][proci]-dist[proc2][proci]);
218       
219     }
220   }
221   return oldvalue;
222 }
223
224 double RefineTopoLB::getCpartHopBytes(int cpart, int proc, int count)
225 {
226   double totalHB=0;
227   for(int i=0;i<count;i++)
228   {
229     if(assign[i]==proc)
230     {
231       totalHB+=comm[cpart][i]*dist[proc][assign[cpart]];
232     }
233     else
234     {
235       totalHB+=comm[cpart][i]*dist[proc][assign[i]];
236     }
237   }
238   return totalHB;
239 }
240
241 /*
242 double RefineTopoLB::getInterMedHopBytes(int *assign_map,int count)
243 {
244   double totalHB=0;
245   int i,j;
246
247   if(assign_map)
248   {
249     for(i=0;i<count;i++)
250       for(j=0;j<count;j++)
251         totalHB+=comm[i][j]*dist[assign_map[i]][assign_map[j]];
252   }
253   else
254   {
255     for(i=0;i<count;i++)
256       for(j=0;j<count;j++)
257         totalHB+=comm[i][j]*dist[i][j];
258   }
259   return totalHB;
260 }
261 */
262
263 void RefineTopoLB::updateCommUA(int count)
264 {
265   int i,j;
266   for(i=0;i<count;i++)
267   {
268     commUA[i]=0;
269     for(j=0;j<count;j++)
270       commUA[i]+=comm[i][j]*dist[assign[i]][assign[j]];
271   }
272 }
273
274 #include "RefineTopoLB.def.h"