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