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