48a3593dd7835ee7047f960fe7b0af4634890c7a
[charm.git] / src / ck-ldb / TopoLB.C
1 /**************************************************************************
2 TopoLB: 
3 This is a topology-aware load balancer.
4  * First groups the objects into $p$ groups.
5  * places object-groups onto processors one-by-one
6  * Next object group to be placed is the one that gains maximum if placed now. It is placed at the processor that minimizes hop-bytes for it.
7  
8 Author: Tarun Agarwal (tarun)
9 Date: 04/19/2005
10 ***************************************************************************/
11 #include <math.h>
12 #include <stdlib.h>
13 #include "charm++.h"
14 #include "cklists.h"
15 #include "CentralLB.h"
16
17 #include "TopoLB.decl.h"
18
19 #include "TopoLB.h"
20
21 #define alpha PER_MESSAGE_SEND_OVERHEAD_DEFAULT  /*Startup time per message, seconds*/
22 #define beta PER_BYTE_SEND_OVERHEAD_DEFAULT     /*Long-message time per byte, seconds*/
23 #define DEG_THRES 0.50
24 #define EPSILON  -0.001
25
26 #define _lb_debug_on 0
27 #define _lb_debug2_on 0
28 #define _make_new_grouping_ 0
29 #define _FASTER_
30 #define _DIJKSTRA_LIKE_ 0
31 #define _INIT_FROM_FILE  
32
33
34 CreateLBFunc_Def(TopoLB,"TopoLB: Balance objects based on the network topology")
35
36
37 TopoLB::TopoLB(const CkLBOptions &opt) : CentralLB (opt)
38 {
39   lbname = "TopoLB";
40   if (CkMyPe () == 0) {
41     CkPrintf ("[%d] TopoLB created\n",CkMyPe());
42   }
43 }
44
45 CmiBool TopoLB::QueryBalanceNow (int _step)
46 {
47   return CmiTrue;
48 }
49
50 void TopoLB::freeDataStructures(int count)
51 {
52   for(int i=0;i<count;i++)
53   {
54     delete[] hopBytes[i];
55     delete[] dist[i];
56     delete[] comm[i];
57   }
58   delete[] comm;
59   delete[] hopBytes;
60   delete[] dist;
61   delete[] pfree;
62   delete[] cfree;
63   delete[] commUA;
64   delete[] assign;
65 }
66
67 void TopoLB::allocateDataStructures(int count )
68 {
69   int i;
70   //Allocating in separate loop to have somewhat contiguous memory allocation
71   hopBytes=new double*[count];
72   for(i=0;i<count;i++)
73   {
74     hopBytes[i]=new double[count+2];
75   }
76
77   dist=new double*[count];
78   for(i=0;i<count;i++)
79   {
80     dist[i]=new double[count+1];
81   }
82
83   comm=new double*[count];
84   for(i=0;i<count;i++)
85   {
86     comm[i]=new double[count];
87   }
88
89   commUA=new double[count];
90   pfree=new bool[count];
91   cfree=new bool[count];
92   assign=new int[count];
93 }
94
95
96 void TopoLB::computePartitions(CentralLB::LDStats *stats,int count,int *newmap)
97 {
98   int numobjs = stats->n_objs;
99         int i, j, m;
100
101   // allocate space for the computing data
102   double *objtime = new double[numobjs];
103   int *objwt = new int[numobjs];
104   int *origmap = new int[numobjs];
105   LDObjHandle *handles = new LDObjHandle[numobjs];
106   
107         for(i=0;i<numobjs;i++) {
108     objtime[i] = 0.0;
109     objwt[i] = 0;
110     origmap[i] = 0;
111   }
112
113   for (i=0; i<stats->n_objs; i++) {
114     LDObjData &odata = stats->objData[i];
115     if (!odata.migratable) 
116       CmiAbort("MetisLB doesnot dupport nonmigratable object.\n");
117     int frompe = stats->from_proc[i];
118     origmap[i] = frompe;
119     objtime[i] = odata.wallTime*stats->procs[frompe].pe_speed;
120     handles[i] = odata.handle;
121   }
122
123   // to convert the weights on vertices to integers
124   double max_objtime = objtime[0];
125   for(i=0; i<numobjs; i++) {
126     if(max_objtime < objtime[i])
127       max_objtime = objtime[i];
128   }
129         int maxobj=0;
130         int totalwt=0;
131   double ratio = 1000.0/max_objtime;
132   for(i=0; i<numobjs; i++) {
133       objwt[i] = (int)(objtime[i]*ratio);
134                         if(maxobj<objwt[i])
135                                 maxobj=objwt[i];
136                         totalwt+=objwt[i];
137   }
138         
139         //CkPrintf("\nmax obj wt :%d \n totalwt before :%d \n\n",maxobj,totalwt);
140         
141   int **comm = new int*[numobjs];
142   for (i=0; i<numobjs; i++) {
143     comm[i] = new int[numobjs];
144     for (j=0; j<numobjs; j++)  {
145       comm[i][j] = 0;
146     }
147   }
148
149   const int csz = stats->n_comm;
150   for(i=0; i<csz; i++) {
151       LDCommData &cdata = stats->commData[i];
152       //if(cdata.from_proc() || cdata.receiver.get_type() != LD_OBJ_MSG)
153         //continue;
154                         if(!cdata.from_proc() && cdata.receiver.get_type() == LD_OBJ_MSG){
155         int senderID = stats->getHash(cdata.sender);
156         int recverID = stats->getHash(cdata.receiver.get_destObj());
157         CmiAssert(senderID < numobjs);
158         CmiAssert(recverID < numobjs);
159         //comm[senderID][recverID] += (int)(cdata.messages*alpha + cdata.bytes*beta);
160         //comm[recverID][senderID] += (int)(cdata.messages*alpha + cdata.bytes*beta);
161                 //CkPrintf("in compute partitions...%d\n",comm[senderID][recverID]);
162                                 comm[senderID][recverID] += cdata.messages;
163         comm[recverID][senderID] += cdata.messages;
164
165                                 //Use bytes or messages -- do i include messages for objlist too...??
166                         }
167                         else if (cdata.receiver.get_type() == LD_OBJLIST_MSG) {
168                                 //CkPrintf("in objlist..\n");
169         int nobjs;
170         LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
171         int senderID = stats->getHash(cdata.sender);
172         for (j=0; j<nobjs; j++) {
173            int recverID = stats->getHash(objs[j]);
174            if((senderID == -1)||(recverID == -1))
175               if (_lb_args.migObjOnly()) continue;
176               else CkAbort("Error in search\n");
177            comm[senderID][recverID] += cdata.messages;
178            comm[recverID][senderID] += cdata.messages;
179         }
180                         }
181                 }
182
183 // ignore messages sent from an object to itself
184   for (i=0; i<numobjs; i++)
185     comm[i][i] = 0;
186
187   // construct the graph in CSR format
188   int *xadj = new int[numobjs+1];
189   int numedges = 0;
190   for(i=0;i<numobjs;i++) {
191     for(j=0;j<numobjs;j++) {
192       if(comm[i][j] != 0)
193         numedges++;
194     }
195   }
196   int *adjncy = new int[numedges];
197   int *edgewt = new int[numedges];
198         int factor = 10;
199   xadj[0] = 0;
200   int count4all = 0;
201   for (i=0; i<numobjs; i++) {
202     for (j=0; j<numobjs; j++) { 
203       if (comm[i][j] != 0) { 
204         adjncy[count4all] = j;
205         edgewt[count4all++] = comm[i][j]/factor;
206       }
207     }
208     xadj[i+1] = count4all;
209   }
210
211   /*if (_lb_args.debug() >= 2) {
212   CkPrintf("Pre-LDB Statistics step %d\n", step());
213   printStats(count, numobjs, objtime, comm, origmap);
214   }*/
215
216   int wgtflag = 3; // Weights both on vertices and edges
217   int numflag = 0; // C Style numbering
218   int options[5];
219   int edgecut;
220   int sameMapFlag = 1;
221
222         options[0] = 0;
223
224   if (count < 1) {
225     CkPrintf("error: Number of Pe less than 1!");
226   }
227   else if (count == 1) {
228         for(m=0;m<numobjs;m++) 
229                         newmap[i] = origmap[i];
230         sameMapFlag = 1;
231   }
232   else {
233         sameMapFlag = 0;
234                 /*
235         if (count > 8)
236                         METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt, 
237                             &wgtflag, &numflag, &count, options, 
238                             &edgecut, newmap);
239           else
240                         METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt, 
241                                  &wgtflag, &numflag, &count, options, 
242                                  &edgecut, newmap);
243                 */
244    //CkPrintf("before calling metis.\n");
245                 METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt,
246                                  &wgtflag, &numflag, &count, options,
247                                  &edgecut, newmap);
248          //CkPrintf("after calling Metis function.\n");
249   }
250          
251   /*if (_lb_args.debug() >= 2) {
252         CkPrintf("Post-LDB Statistics step %d\n", step());
253         printStats(count, numobjs, objtime, comm, newmap);
254   }*/
255
256   for(i=0;i<numobjs;i++)
257     delete[] comm[i];
258   delete[] comm;
259   delete[] objtime;
260   delete[] xadj;
261   delete[] adjncy;
262   delete[] objwt;
263   delete[] edgewt;
264
265         //CkPrintf("chking wts on each partition...\n");
266
267         /*int avg=0;
268         int *chkwt = new int[count];
269         for(i=0;i<count;i++)
270                 chkwt[i]=0;
271         //totalwt=0;
272         for(i=0;i<numobjs;i++){
273                 chkwt[newmap[i]] += objwt[i];
274                 avg += objwt[i];
275         }
276         
277         for(i=0;i<count;i++)
278                 CkPrintf("%d -- %d\n",i,chkwt[i]);
279         
280         //CkPrintf("totalwt after:%d avg is %d\n",avg,avg/count);
281 */
282   /*if(!sameMapFlag) {
283     for(i=0; i<numobjs; i++) {
284       if(origmap[i] != newmap[i]) {
285                                 CmiAssert(stats->from_proc[i] == origmap[i]);
286                                 ///Dont assign....wait........
287                                 stats->to_proc[i] =  newmap[i];
288                                 if (_lb_args.debug() >= 3)
289           CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),i,stats->from_proc[i],stats->to_proc[i]);
290       }
291     }
292   }*/
293
294   delete[] origmap;
295 }
296
297 void TopoLB::initDataStructures(CentralLB::LDStats *stats,int count,int *newmap)
298 {
299   int i;
300   //init dist
301   if(_lb_debug_on)
302     CkPrintf("Before initing dist\n");
303  
304   topo->get_pairwise_hop_count(dist);
305   /*for(i=0;i<count;i++){
306    for(int j=0;j<count;j++)
307     CkPrintf("%.0lf ",dist[i][j]);
308    CkPrintf("\n");
309   }*/
310   for(i=0;i<count;i++)
311   {
312     double totaldist=0;
313     for(int j=0;j<count;j++)
314     {
315       //dist[i][j]=topo->get_hop_count(i,j);
316       totaldist+=dist[i][j];
317     }
318     dist[i][count]=totaldist/(count-1);
319   }
320
321   //Init comm,commUA from stats
322   stats->makeCommHash();
323   if(_lb_debug_on)
324     CkPrintf("Before initing comm\n");
325   for(i=0;i<count;i++)
326   {
327     for(int j=0;j<count;j++)
328     {
329       comm[i][j]=0;
330     }
331     commUA[i]=0;
332   }
333   bool *multicastAdded=new bool[count];
334   for(i=0;i<stats->n_comm;i++)
335   {
336     LDCommData &cdata=stats->commData[i];
337     if(!cdata.from_proc() && cdata.receiver.get_type() ==LD_OBJ_MSG)
338     {
339       int sender=stats->getHash(cdata.sender);
340       int receiver=stats->getHash(cdata.receiver.get_destObj());
341
342       CmiAssert(sender<stats->n_objs);
343       CmiAssert(receiver<stats->n_objs);
344
345       if(newmap[sender]==newmap[receiver])
346         continue;
347
348       int send_part=newmap[sender];
349       int recv_part=newmap[receiver];
350       comm[send_part][recv_part]+=cdata.bytes;
351       comm[recv_part][send_part]+=cdata.bytes;
352
353       commUA[send_part]+=cdata.bytes;
354       commUA[recv_part]+=cdata.bytes;
355     }
356     if(!cdata.from_proc() && cdata.receiver.get_type()==LD_OBJLIST_MSG)
357     {
358       int nobjs=0;
359       LDObjKey *receivers=cdata.receiver.get_destObjs(nobjs);
360       int sender=stats->getHash(cdata.sender);
361       int send_part=newmap[sender];
362       
363       CmiAssert(sender<stats->n_objs);
364
365       for(int i=0;i<count;i++)
366         multicastAdded[i]=false;
367       multicastAdded[send_part]=true;
368
369       for(int k=0;k<nobjs;k++)
370       {
371         int receiver=stats->getHash(receivers[k]);
372         CmiAssert ( receiver < stats->n_objs);
373
374         int recv_part=newmap[receiver];
375         if(!multicastAdded[recv_part])
376         {
377           comm[send_part][recv_part]+=cdata.bytes;
378           comm[recv_part][send_part]+=cdata.bytes;
379       
380           commUA[send_part]+=cdata.bytes;
381           commUA[recv_part]+=cdata.bytes;
382
383           multicastAdded[recv_part]=true;
384         }
385       }
386     }
387   }
388   /*****FIXED A MEMORY LEAK******/
389   delete[] multicastAdded;
390
391   /***************************/
392   //Just a test
393   /*
394   for(int i=0;i<count;i++)
395     commUA[0];
396   for(int i=0;i<count;i++)
397   {
398     for(int j=0;j<i;j++)
399     {
400       comm[j][i]=comm[i][j]= rand()%100;
401       commUA[i]+=comm[i][j];
402       commUA[j]+=comm[i][j];
403     }
404   }
405   */
406
407   /******Avg degree test *******/
408   total_comm=0;
409   if(_lb_debug2_on)
410   {
411     int avg_degree=0;
412     for(int i=0;i<count;i++)
413     {
414       double comm_i_total=0;
415       for(int j=0;j<count;j++)
416       {
417         avg_degree+=(comm[i][j]>0);
418         total_comm+=comm[i][j];
419         comm_i_total+=comm[i][j];
420       }
421     }
422      // CkPrintf("Avg degree (%d nodes) : %d\n",count,avg_degree/count);
423   }
424   /***************************/
425
426   //Init hopBytes
427   //hopBytes[i][j]=hopBytes if partition i is placed at proc j
428   if(_lb_debug_on)
429     CkPrintf("Before initing hopBytes\n");
430   for(i=0;i<count;i++)
431   {
432     int hbminIndex=0;
433     double hbtotal=0;
434     for(int j=0;j<count;j++)
435     {
436       //Initialize by (total comm of i)*(avg dist from j);
437       if(_DIJKSTRA_LIKE_)
438         hopBytes[i][j]=0;
439       else
440         hopBytes[i][j]=commUA[i]*dist[j][count];
441
442       hbtotal+=hopBytes[i][j];
443       if(hopBytes[i][hbminIndex]>hopBytes[i][j])
444         hbminIndex=j;
445     }
446     hopBytes[i][count]=hbminIndex;
447     hopBytes[i][count+1]=hbtotal/count;
448   }
449   
450   //Init pfree, cfree, assign
451   if(_lb_debug_on)
452     CkPrintf("Before initing pfree cfree assign\n");
453   for(i=0;i<count;i++)
454   {
455     pfree[i]=true;
456     cfree[i]=true;
457     assign[i]=-1;
458   }
459
460 }
461
462 void randomAssign(int count, int *perm)
463 {
464   int i;
465   for(i=0;i<count;i++)
466     perm[i]=i;
467   for(i=0;i<count;i++)
468   {
469     int randpos=i+rand()%(count-i);
470     int temp=perm[i];
471     perm[i]=perm[randpos];
472     perm[randpos]=temp;
473   }
474 }
475
476 void TopoLB::performMapping(int *newmap, int count)
477 {
478   int i,j;
479   if(_lb_debug_on)
480     CkPrintf("before performing mapping...\n");
481
482   double *distnew=new double[count];
483   for(i=0;i<count;i++)
484   {
485     //Assume i-1 partitions placed, 
486     //select and place the ith partition
487
488     //select the (c,p) pair
489     int part_index=-1;
490     int proc_index=-1;
491
492
493     double gainMax=-1;
494     for(j=0;j<count;j++)
495     {
496       if(!cfree[j])
497         continue;
498       
499       int hb_j_minIndex=(int)hopBytes[j][count];
500       //CmiAssert(pfree[hb_j_minIndex]);
501       double gain=hopBytes[j][count+1]-hopBytes[j][hb_j_minIndex];
502
503       //CmiAssert(gain>=0);
504       //CmiAssert(gain>=EPSILON);
505       
506       if(_lb_debug_on)
507         CkPrintf("Gain is : %lf\n",gain);
508
509       if(gain>gainMax)
510       {
511         part_index=j;
512         proc_index=hb_j_minIndex;
513         gainMax=gain;
514       }
515     }
516     if(_lb_debug_on)
517         CkPrintf("GainMax [%d] is : %lf\n",i,gainMax);
518
519     CmiAssert(part_index!=-1);
520     CmiAssert(proc_index!=-1);
521
522     //Assign the selection
523     CmiAssert(assign[part_index]==-1);
524     CmiAssert(pfree[proc_index]);
525     assign[part_index]=proc_index;
526     
527     /*
528     if(_lb_debug2_on)
529     {
530       if(i%100 ==0)
531         CkPrintf("Assigned %d procs \n",i+1);
532     }
533     */
534     
535     
536     /*****Update Data Structures******************/
537
538
539 #ifndef _FASTER_
540     cfree[part_index]=false;
541     pfree[proc_index]=false;
542
543     //Dont need to update other data structures if this is last assignment
544     if(i == count-1)
545       continue;
546
547     int procs_left=count-i-1;
548
549     //Update hopBytes
550     
551     for(j=0;j<count;j++)
552     {
553       if(procs_left>1)
554         distnew[j]=(dist[j][count]*procs_left -dist[j][proc_index]) / (procs_left-1);
555       else
556         distnew[j]=0;
557     }
558     for(int cpart=0;cpart<count;cpart++)
559     {
560       if(!cfree[cpart]) //No need to update for assigned partitions
561         continue;    
562
563       if(commUA[cpart]==0 && hopBytes[cpart][count]!=proc_index)
564       {
565         if(procs_left>0)
566           hopBytes[cpart][count+1]=(hopBytes[cpart][count+1]*(procs_left+1) - hopBytes[cpart][proc_index])/(procs_left);
567         continue;
568       }
569
570       //double hbmin=INFTY;
571       int h_min_index=-1;
572       double h_min=-1;
573       double h_total=0;
574
575       double c1=commUA[cpart];
576       double c2=comm[cpart][part_index];
577
578       double h_updated=0;
579
580       for(int proc=0;proc<count;proc++)
581       {
582         if(!pfree[proc]) // No need to update for assigned procs
583           continue;
584
585         hopBytes[cpart][proc]+=(c1-c2)*distnew[proc]+c2*dist[proc][proc_index]-c1*dist[proc][count];
586         h_updated=hopBytes[cpart][proc];
587         
588         //CmiAssert(hopBytes[cpart][proc] >= EPSILON);
589
590         h_total+=h_updated;
591         if( h_updated<h_min || h_min_index==-1 )
592         {
593           h_min=h_updated;
594           h_min_index=proc;
595         }
596       }
597       //CmiAssert(h_min_index!=-1);
598       hopBytes[cpart][count]=h_min_index;
599       hopBytes[cpart][count+1]=h_total/(procs_left);
600     }
601
602     // d[j][count] is the average dist of proc j to unassigned procs
603     // Also update commUA[j]
604     for(j=0;j<count;j++)
605     {
606       if(procs_left>1)
607         dist[j][count]=(dist[j][count]*procs_left -dist[j][proc_index]) / (procs_left-1);
608       else
609         dist[j][count]=0;
610       commUA[j]-=comm[j][part_index];
611     }
612
613 #else
614     cfree[part_index]=false;
615     pfree[proc_index]=false;
616
617     //Dont need to update other data structures if this is last assignment
618     if(i == count-1)
619       continue;
620
621     int procs_left=count-i-1;
622
623     //Update hopBytes
624     for(int cpart=0;cpart<count;cpart++)
625     {
626       //No need to update for assigned partitions
627       if(!cfree[cpart]) 
628         continue;    
629
630       //If cpart doesn't communicate with part_index, just need to update minimum and average hopBytes attainable for cpart
631       if(comm[cpart][part_index]==0) 
632       {
633         //change average
634         if(procs_left>0)
635           hopBytes[cpart][count+1]=(hopBytes[cpart][count+1]*(procs_left+1) - hopBytes[cpart][proc_index])/(procs_left);
636
637         //change minimum if needed
638         if(hopBytes[cpart][count]==proc_index)
639         {
640           int c_min=-1;
641           double c_min_val=-1;
642           for(int l=0;l<count;l++)
643           {
644             if(!pfree[l])
645               continue;
646             
647             if(c_min==-1 || hopBytes[cpart][l]<c_min_val)
648             {
649               c_min_val=hopBytes[cpart][l];
650               c_min=l;
651             }
652           }
653           CmiAssert(c_min!=-1);
654           hopBytes[cpart][count]=c_min;
655         }
656         continue;
657       }
658
659       // If reached here cpart communicates with the partition assigned in this step( part_index)
660       int h_min_index=-1;
661       double h_min=-1;
662       double h_total=0;
663
664       //double c1=commUA[cpart];
665       double c2=comm[cpart][part_index];
666
667       double h_updated=0;
668
669       for(int proc=0;proc<count;proc++)
670       {
671         if(!pfree[proc]) // No need to update for assigned procs
672           continue;
673
674         if(_DIJKSTRA_LIKE_)
675           hopBytes[cpart][proc]+=c2*(dist[proc][proc_index]);
676         else
677           hopBytes[cpart][proc]+=c2*(dist[proc][proc_index]-dist[proc][count]);
678         h_updated=hopBytes[cpart][proc];
679         
680         //CmiAssert(h_updated >= EPSILON);
681
682         h_total+=h_updated;
683         if(h_updated<h_min || h_min_index==-1 )
684         {
685           h_min=h_updated;
686           h_min_index=proc;
687         }
688       }
689       CmiAssert(h_min_index!=-1);
690       CmiAssert(pfree[h_min_index]);
691       hopBytes[cpart][count]=h_min_index;
692       hopBytes[cpart][count+1]=h_total/(procs_left);
693     }
694
695 #endif
696     
697   }
698  
699   /****FIXED a memory leak******/
700   delete [] distnew;
701   /******************  Fill out final composition Mapping **************************/
702
703 }
704
705 void TopoLB :: work(CentralLB::LDStats *stats,int count)
706 {
707   int i, j;
708   if (_lb_args.debug() >= 2) 
709   {
710     CkPrintf("In TopoLB Strategy...\n");
711   }
712   
713   /****Make sure that there is at least one available processor.***/
714   int proc;
715   for (proc = 0; proc < count; proc++) 
716   {
717     if (stats->procs[proc].available)  
718       break;
719   }
720         
721   if (proc == count) 
722   {
723     CmiAbort ("TopoLB: no available processors!");
724   }
725  
726   removeNonMigratable(stats,count);
727
728   if(_lb_debug_on)
729   {
730     CkPrintf("Num of procs: %d\n",count);
731     CkPrintf("Num of objs:  %d\n",stats->n_objs);
732   }
733
734   /**************Initialize Topology ****************************/
735   LBtopoFn topofn;
736   char *lbcopy = strdup(_lbtopo);
737   char *ptr = strchr(lbcopy, ':');
738   if (ptr!=NULL)
739     ptr = strtok(lbcopy, ":");
740         else
741                 ptr=lbcopy;
742
743   topofn = LBTopoLookup(ptr);
744   if (topofn == NULL) 
745   {
746         char str[1024];
747     CmiPrintf("TopoLB> Fatal error: Unknown topology: %s. Choose from:\n", _lbtopo);
748     printoutTopo();
749     sprintf(str, "TopoLB> Fatal error: Unknown topology: %s", _lbtopo);
750     CmiAbort(str);
751   }
752   topo = topofn(count);
753
754   /*********** Compute Partitions *********************************/
755   if(_lb_debug_on)
756     CkPrintf("before computing partitions...\n");
757   
758   int *newmap = new int[stats->n_objs];
759   if(_make_new_grouping_)
760     computePartitions(stats,count,newmap);
761   else
762   {
763     for(i=0;i<stats->n_objs;i++)
764     {
765       newmap[i]=stats->from_proc[i];
766     }
767   }
768   /***************** Fill Data Structures *************************/
769   if(_lb_debug_on)
770     CkPrintf("before allocating dataStructures...\n");
771
772   allocateDataStructures(count);
773
774   if(_lb_debug_on)
775     CkPrintf("before initizlizing dataStructures...\n");
776
777   initDataStructures(stats,count,newmap);
778
779   if(_lb_debug_on)
780     printDataStructures(count, stats->n_objs,newmap);
781   
782   /****************** Perform Mapping *****************************/
783
784   if(_lb_debug_on)
785     CkPrintf("before performing mapping...\n");
786   
787   performMapping(newmap,count);
788
789   for(i=0;i<stats->n_objs;i++)
790   {
791     stats->to_proc[i]= assign[newmap[i]];
792   }
793
794   if(_lb_debug2_on)
795   {
796     double hbval1=getHopBytesNew(NULL,count);
797     CkPrintf("\n");
798     CkPrintf(" Original hopBytes : %.1lf \n", hbval1);
799     CkPrintf(" Original Avg hops : %.1lf \n", hbval1/total_comm);
800     double hbval2=getHopBytesNew(assign,count);
801     //CkPrintf(" Resulting hopBytes : %.1lf \n", hbval2);
802     //CkPrintf(" Resulting Avg hops : %.1lf \n", hbval2/total_comm);
803     //CkPrintf(" Percentage gain %.2lf\n",(hbval1-hbval2)*100/hbval1);
804     //CkPrintf("\n");
805     
806     double total_hb_rand=0;
807     int nTrials=10;
808     for(int t=0;t<nTrials;t++)
809     {
810       randomAssign(count, assign);
811       double hbval3=getHopBytesNew(assign,count);
812       total_hb_rand+=hbval3;
813      //CkPrintf(" Random hopBytes : %.1lf \n", hbval3);
814      //CkPrintf(" Random Avg hops : %.1lf \n", hbval3/total_comm);
815     }
816     //CkPrintf("\n");
817     double hbval4=total_hb_rand/nTrials;
818     CkPrintf(" Average Random hopBytes : %.1lf \n", hbval4);
819     CkPrintf(" Average Random Avg hops : %.1lf \n", hbval4/total_comm);
820     CkPrintf(" Resulting hopBytes : %.1lf \n", hbval2);
821     CkPrintf(" Resulting Avg hops : %.1lf \n", hbval2/total_comm);
822     CkPrintf(" Percentage gain(TopoLB vs random) %.2lf\n",(hbval4-hbval2)*100/hbval4);
823     CkPrintf("\n");
824   }
825   freeDataStructures(count);
826   delete[] newmap;
827   return;
828 }
829
830
831 void TopoLB::printDataStructures(int count,int n_objs,int *newmap)
832 {
833   int i;
834   /*
835   CkPrintf("Partition Results : \n");
836   for(int i=0;i<n_objs;i++)
837   {
838     CkPrintf("map[%d] = %d\n",i,newmap[i]);
839   }
840   */
841
842   CkPrintf("Dist : \n");
843   for(i=0;i<count;i++)
844   {
845     for(int j=0;j<count+1;j++)
846     {
847       CkPrintf("%lf ",dist[i][j]);
848     }
849     CkPrintf("\n");
850   }
851   CkPrintf("HopBytes: \n");
852   for(i=0;i<count;i++)
853   {
854     for(int j=0;j<count+2;j++)
855     {
856       CkPrintf("%lf ",hopBytes[i][j]);
857     }
858     CkPrintf("\n");
859   }
860 }
861
862 double TopoLB::getHopBytesNew(int *assign_map, int count)
863 {
864   double totalHB=0;
865   int i,j;
866   if(assign_map==NULL)
867   {
868     for(i=0;i<count;i++)
869       for(j=0;j<count;j++)
870         totalHB+=dist[i][j]*comm[i][j];
871   }
872   else
873   {
874     for(i=0;i<count;i++)
875       for(j=0;j<count;j++)
876         totalHB+=dist[assign_map[i]][assign_map[j]]*comm[i][j];
877   }
878   return totalHB;
879 }
880
881 double TopoLB::getHopBytes(CentralLB::LDStats *stats,int count,CkVec<int>map)
882 {
883   int i;
884   double **comm1=new double*[count];
885   for(i=0;i<count;i++)
886     comm1[i]=new double[count];
887
888   for(i=0;i<count;i++)
889   {
890     for(int j=0;j<count;j++)
891     {
892       comm1[i][j]=0;
893     }
894   }
895
896   bool *multicastAdded=new bool[count];
897   for(i=0;i<stats->n_comm;i++)
898   {
899     LDCommData &cdata=stats->commData[i];
900     if(!cdata.from_proc() && cdata.receiver.get_type() ==LD_OBJ_MSG)
901     {
902       int sender=stats->getHash(cdata.sender);
903       int receiver=stats->getHash(cdata.receiver.get_destObj());
904
905       CmiAssert(sender<stats->n_objs);
906       CmiAssert(receiver<stats->n_objs);
907
908       if(map[sender]==map[receiver])
909         continue;
910
911       int send_part=map[sender];
912       int recv_part=map[receiver];
913       comm1[send_part][recv_part]+=cdata.bytes;
914       comm1[recv_part][send_part]+=cdata.bytes;
915     }
916     if(!cdata.from_proc() && cdata.receiver.get_type()==LD_OBJLIST_MSG)
917     {
918       int nobjs=0;
919       LDObjKey *receivers=cdata.receiver.get_destObjs(nobjs);
920       int sender=stats->getHash(cdata.sender);
921       int send_part=map[sender];
922       
923       CmiAssert(sender<stats->n_objs);
924
925       for(i=0;i<count;i++)
926         multicastAdded[i]=false;
927       multicastAdded[send_part]=true;
928
929       for(int k=0;k<nobjs;k++)
930       {
931         int receiver=stats->getHash(receivers[k]);
932         //CmiAssert ( (int)(receivers[k])< stats->n_objs);
933         CmiAssert ( receiver < stats->n_objs);
934
935         int recv_part=map[receiver];
936         if(!multicastAdded[recv_part])
937         {
938           comm1[send_part][recv_part]+=cdata.bytes;
939           comm1[recv_part][send_part]+=cdata.bytes;
940       
941           multicastAdded[recv_part]=true;
942         }
943       }
944     }
945   }
946   delete[] multicastAdded;
947
948   double totalHB=0;
949   int proc1,proc2;
950
951   for(i=0;i<count;i++)
952   {
953     proc1=map[i];
954     for(int j=0;j<count;j++)
955     {
956       proc2=map[j];
957       //totalHB+=dist[proc1][proc2]*comm1[i][j];
958       totalHB+=dist[i][j]*comm1[i][j];
959     }
960   }
961   for(i=0;i<count;i++)
962     delete[] comm1[i];
963   delete[] comm1;
964
965   return totalHB;
966 }
967
968 #include "TopoLB.def.h"