Merge last phase of static array optimization branch
[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(LDStats *stats)
44 {
45   int i, j;
46   int n_pes = stats->nprocs();
47
48   if (_lb_args.debug() >= 2) {
49     CkPrintf("In TopoLB Strategy...\n");
50   }
51   
52   /****Make sure that there is at least one available processor.***/
53   int proc;
54   for (proc = 0; proc < n_pes; proc++) {
55     if (stats->procs[proc].available)  
56       break;
57   }
58         
59   if (proc == n_pes) {
60     CmiAbort ("TopoLB: no available processors!");
61   }
62  
63   removeNonMigratable(stats, n_pes);
64
65   if(_lb_debug_on) {
66     CkPrintf("Num of procs: %d\n", n_pes);
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(n_pes);
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, n_pes, 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(n_pes);
100   if(_lb_debug_on)
101     CkPrintf("before initizlizing dataStructures...\n");
102   initDataStructures(stats, n_pes, newmap);
103   if(_lb_debug_on)
104     CkPrintf("After initizlizing dataStructures...\n");
105
106   for(i = 0; i < n_pes; i++)
107     assign[i]=i;
108   
109
110
111   if(_lb_debug_on)
112     printDataStructures(n_pes, stats->n_objs,newmap);
113   /***************** Perform RefineMent *************************/
114   bool *swapdone=new bool[n_pes];
115   for(i = 0; i < n_pes; i++)
116     swapdone[i]=false;
117
118     
119   //double hbval=getHopBytes(stats, n_pes, stats->from_proc);
120   //double hbval=getHopBytesNew(NULL, n_pes);
121  // CkPrintf(" Before Mapping Original   hopBytes : %lf  Avg comm hops: %lf\n", hbval,hbval/total_comm);
122   //Perform ith swap
123   double totalGain=0;
124   for(i = 0; i < n_pes; i++)
125   {
126     //select the cpart which is most communicating and hasn't been moved yet
127     if(_USE_MAX_HOPBYTES_)
128     {
129       updateCommUA(n_pes);
130     }
131     int cpart=-1;
132     double maxComm=-1;
133     for(j = 0; j < n_pes; j++)
134     {
135       if(swapdone[j]) continue;
136       if(commUA[j]>maxComm)
137       {
138         maxComm=commUA[j];
139         cpart=j;
140       }
141     }
142     CmiAssert(cpart!=-1);
143
144     //Next find a cpart for swap
145     int swapcpart=-1;
146     double gainMax=-1;
147     double gain=-1;;
148     //double orig_value=getHopBytesNew(assign, n_pes);
149     for(j = 0; j < n_pes; j++)
150     {
151       if(j==cpart)
152         continue;
153
154       gain=findSwapGain(j, cpart, n_pes);
155
156       //CkPrintf("%lf : %lf\n",gain,findSwapGain(j, cpart, n_pes));
157       if(gain>gainMax && gain>0)
158       {
159         gainMax=gain;
160         swapcpart=j;
161       }
162     }
163     if(swapcpart==-1)
164     {
165       swapdone[cpart]=true;
166       continue;
167     }
168     totalGain+=gainMax;
169     CmiAssert(swapcpart!=-1);
170     
171     //Actually swap
172     int temp=assign[cpart];
173     assign[cpart]=assign[swapcpart];
174     assign[swapcpart]=temp;
175     swapdone[cpart]=true;
176   
177     //CkPrintf("Gain: %lf  Total_Gain: %lf HopBytes: %lf\n ",gainMax,totalGain,getHopBytesNew(stats, n_pes, newmap));
178     //CkPrintf(" %lf  getHopBytesNew(stats, n_pes, newmap);
179     //CkPrintf("Swap# %d:  %d and %d\n",i+1,cpart,swapcpart);
180   }
181   /******************* Assign mapping and print Stats*********/
182   for(i=0;i<stats->n_objs;i++)
183   {
184     stats->to_proc[i]= assign[newmap[i]];
185   }
186   if(_lb_debug2_on)
187   {
188     //double hbval=getHopBytes(stats, n_pes, stats->from_proc);
189     double hbval1=getHopBytesNew(NULL, n_pes);
190     CkPrintf(" Original   hopBytes : %lf  Avg comm hops: %lf\n", hbval1,hbval1/total_comm);
191     double hbval2=getHopBytesNew(assign, n_pes);
192     CkPrintf(" Resulting  hopBytes : %lf  Avg comm hops: %lf\n", hbval2,hbval2/total_comm);
193     CkPrintf(" Percentage gain %.2lf\n",(hbval1-hbval2)*100/hbval1);
194     CkPrintf("\n");
195   }
196   freeDataStructures(n_pes);
197   delete[] newmap;
198   delete[] swapdone;
199 }
200
201 double RefineTopoLB::findSwapGain(int cpart1, int cpart2, int n_pes)
202 {
203   double oldvalue=0;
204   int proc1=assign[cpart1];
205   int proc2=assign[cpart2];
206   int proci=-1;
207
208   for(int i = 0; i < n_pes; i++)
209   {
210     proci=assign[i];
211     if(i!=cpart1 && i!=cpart2)
212     {
213       //oldvalue+=comm[cpart1][i]*(dist[proc1][proci]-dist[proc2][proci]);
214       //oldvalue+=comm[cpart2][i]*(dist[proc2][proci]-dist[proc1][proci]);
215       oldvalue+=(comm[cpart1][i]-comm[cpart2][i])*(dist[proc1][proci]-dist[proc2][proci]);
216       
217     }
218   }
219   return oldvalue;
220 }
221
222 double RefineTopoLB::getCpartHopBytes(int cpart, int proc, int count)
223 {
224   double totalHB=0;
225   for(int i=0;i<count;i++)
226   {
227     if(assign[i]==proc)
228     {
229       totalHB+=comm[cpart][i]*dist[proc][assign[cpart]];
230     }
231     else
232     {
233       totalHB+=comm[cpart][i]*dist[proc][assign[i]];
234     }
235   }
236   return totalHB;
237 }
238
239 /*
240 double RefineTopoLB::getInterMedHopBytes(int *assign_map,int count)
241 {
242   double totalHB=0;
243   int i,j;
244
245   if(assign_map)
246   {
247     for(i=0;i<count;i++)
248       for(j=0;j<count;j++)
249         totalHB+=comm[i][j]*dist[assign_map[i]][assign_map[j]];
250   }
251   else
252   {
253     for(i=0;i<count;i++)
254       for(j=0;j<count;j++)
255         totalHB+=comm[i][j]*dist[i][j];
256   }
257   return totalHB;
258 }
259 */
260
261 void RefineTopoLB::updateCommUA(int count)
262 {
263   int i,j;
264   for(i=0;i<count;i++)
265   {
266     commUA[i]=0;
267     for(j=0;j<count;j++)
268       commUA[i]+=comm[i][j]*dist[assign[i]][assign[j]];
269   }
270 }
271
272 #include "RefineTopoLB.def.h"