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