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