A bunch of optimizations
[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       gain=findSwapGain(j,cpart,count);
147
148       //CkPrintf("%lf : %lf\n",gain,findSwapGain(j,cpart,count));
149       if(gain>gainMax && gain>0)
150       {
151         gainMax=gain;
152         swapcpart=j;
153       }
154     }
155     if(swapcpart==-1)
156     {
157       swapdone[cpart]=true;
158       continue;
159     }
160     totalGain+=gainMax;
161     CmiAssert(swapcpart!=-1);
162     
163     //Actually swap
164     int temp=assign[cpart];
165     assign[cpart]=assign[swapcpart];
166     assign[swapcpart]=temp;
167     swapdone[cpart]=true;
168   
169     //CkPrintf("Gain: %lf  Total_Gain: %lf HopBytes: %lf\n ",gainMax,totalGain,getInterMedHopBytes(stats,count,newmap));
170     //CkPrintf(" %lf  getInterMedHopBytes(stats,count,newmap);
171     //CkPrintf("Swap# %d:  %d and %d\n",i+1,cpart,swapcpart);
172   }
173   /******************* Assign mapping and print Stats*********/
174   for(int i=0;i<stats->n_objs;i++)
175   {
176     stats->to_proc[i]= assign[newmap[i]];
177   }
178   if(_lb_debug2_on)
179   {
180     double hbval=getHopBytes(stats,count,stats->from_proc);
181     CkPrintf(" Original   hopBytes : %lf  Avg comm hops: %lf\n", hbval,hbval/total_comm);
182   //  hbval=getHopBytes(stats,count,stats->to_proc);
183     //CkPrintf(" Resulting  hopBytes : %lf  Avg comm hops: %lf\n", hbval,hbval/total_comm);
184     hbval=getInterMedHopBytes(stats,count,newmap);
185     CkPrintf("Other Resulting  hopBytes : %lf  Avg comm hops: %lf\n", hbval,hbval/total_comm);
186   }
187   freeDataStructures(count);
188   delete[] newmap;
189   delete[] swapdone;
190 }
191
192 double RefineTopoLB::findSwapGain(int cpart1, int cpart2,int count)
193 {
194   double oldvalue=0;
195   int proc1=assign[cpart1];
196   int proc2=assign[cpart2];
197   int proci=-1;
198
199   for(int i=0;i<count;i++)
200   {
201     proci=assign[i];
202     if(i!=cpart1 && i!=cpart2)
203     {
204       //oldvalue+=comm[cpart1][i]*(dist[proc1][proci]-dist[proc2][proci]);
205       //oldvalue+=comm[cpart2][i]*(dist[proc2][proci]-dist[proc1][proci]);
206       oldvalue+=(comm[cpart1][i]-comm[cpart2][i])*(dist[proc1][proci]-dist[proc2][proci]);
207       
208     }
209   }
210   return oldvalue;
211 }
212
213 double RefineTopoLB::getCpartHopBytes(int cpart, int proc, int count)
214 {
215   double totalHB=0;
216   for(int i=0;i<count;i++)
217   {
218     if(assign[i]==proc)
219     {
220       totalHB+=comm[cpart][i]*dist[proc][assign[cpart]];
221     }
222     else
223     {
224       totalHB+=comm[cpart][i]*dist[proc][assign[i]];
225     }
226   }
227   return totalHB;
228 }
229
230 double RefineTopoLB::getInterMedHopBytes(CentralLB::LDStats *stats,int count, int *newmap)
231 {
232   double totalHB=0;
233
234   for(int i=0;i<count;i++)
235   {
236     for(int j=0;j<count;j++)
237     {
238       totalHB+=comm[i][j]*dist[assign[i]][assign[j]];
239     }
240   }
241   return totalHB;
242   /*
243   CkVec<int> obj_to_proc;
244   for(int i=0;i<stats->n_objs;i++)
245   {
246     obj_to_proc.push_back(assign[newmap[i]]);
247   }
248   return getHopBytes(stats,count,obj_to_proc);
249   */
250 }
251
252 #include "RefineTopoLB.def.h"