Refactoring, printfs
[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 1
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   {
307     double totaldist=0;
308     for(int j=0;j<count;j++)
309     {
310       //dist[i][j]=topo->get_hop_count(i,j);
311       totaldist+=dist[i][j];
312     }
313     dist[i][count]=totaldist/(count-1);
314   }
315
316   //Init comm,commUA from stats
317   if(_lb_debug_on)
318     CkPrintf("Before initing comm\n");
319   for(i=0;i<count;i++)
320   {
321     for(int j=0;j<count;j++)
322     {
323       comm[i][j]=0;
324     }
325     commUA[i]=0;
326   }
327   bool *multicastAdded=new bool[count];
328   for(i=0;i<stats->n_comm;i++)
329   {
330     LDCommData &cdata=stats->commData[i];
331     if(!cdata.from_proc() && cdata.receiver.get_type() ==LD_OBJ_MSG)
332     {
333       int sender=stats->getHash(cdata.sender);
334       int receiver=stats->getHash(cdata.receiver.get_destObj());
335
336       CmiAssert(sender<stats->n_objs);
337       CmiAssert(receiver<stats->n_objs);
338
339       if(newmap[sender]==newmap[receiver])
340         continue;
341
342       int send_part=newmap[sender];
343       int recv_part=newmap[receiver];
344       comm[send_part][recv_part]+=cdata.bytes;
345       comm[recv_part][send_part]+=cdata.bytes;
346
347       commUA[send_part]+=cdata.bytes;
348       commUA[recv_part]+=cdata.bytes;
349     }
350     if(!cdata.from_proc() && cdata.receiver.get_type()==LD_OBJLIST_MSG)
351     {
352       int nobjs=0;
353       LDObjKey *receivers=cdata.receiver.get_destObjs(nobjs);
354       int sender=stats->getHash(cdata.sender);
355       int send_part=newmap[sender];
356       
357       CmiAssert(sender<stats->n_objs);
358
359       for(int i=0;i<count;i++)
360         multicastAdded[i]=false;
361       multicastAdded[send_part]=true;
362
363       for(int k=0;k<nobjs;k++)
364       {
365         int receiver=stats->getHash(receivers[k]);
366         CmiAssert ( receiver < stats->n_objs);
367
368         int recv_part=newmap[receiver];
369         if(!multicastAdded[recv_part])
370         {
371           comm[send_part][recv_part]+=cdata.bytes;
372           comm[recv_part][send_part]+=cdata.bytes;
373       
374           commUA[send_part]+=cdata.bytes;
375           commUA[recv_part]+=cdata.bytes;
376
377           multicastAdded[recv_part]=true;
378         }
379       }
380     }
381   }
382
383   /***************************/
384   //Just a test
385   /*
386   for(int i=0;i<count;i++)
387     commUA[0];
388   for(int i=0;i<count;i++)
389   {
390     for(int j=0;j<i;j++)
391     {
392       comm[j][i]=comm[i][j]= rand()%100;
393       commUA[i]+=comm[i][j];
394       commUA[j]+=comm[i][j];
395     }
396   }
397   */
398
399   /******Avg degree test *******/
400   total_comm=0;
401   if(_lb_debug2_on)
402   {
403     int avg_degree=0;
404     for(int i=0;i<count;i++)
405     {
406       double comm_i_total=0;
407       for(int j=0;j<count;j++)
408       {
409         avg_degree+=(comm[i][j]>0);
410         total_comm+=comm[i][j];
411         comm_i_total+=comm[i][j];
412       }
413     }
414      // CkPrintf("Avg degree (%d nodes) : %d\n",count,avg_degree/count);
415   }
416   /***************************/
417
418   //Init hopBytes
419   //hopBytes[i][j]=hopBytes if partition i is placed at proc j
420   if(_lb_debug_on)
421     CkPrintf("Before initing hopBytes\n");
422   for(i=0;i<count;i++)
423   {
424     int hbminIndex=0;
425     double hbtotal=0;
426     for(int j=0;j<count;j++)
427     {
428       //Initialize by (total comm of i)*(avg dist from j);
429       if(_DIJKSTRA_LIKE_)
430         hopBytes[i][j]=0;
431       else
432         hopBytes[i][j]=commUA[i]*dist[j][count];
433
434       hbtotal+=hopBytes[i][j];
435       if(hopBytes[i][hbminIndex]>hopBytes[i][j])
436         hbminIndex=j;
437     }
438     hopBytes[i][count]=hbminIndex;
439     hopBytes[i][count+1]=hbtotal/count;
440   }
441   
442   //Init pfree, cfree, assign
443   if(_lb_debug_on)
444     CkPrintf("Before initing pfree cfree assign\n");
445   for(i=0;i<count;i++)
446   {
447     pfree[i]=true;
448     cfree[i]=true;
449     assign[i]=-1;
450   }
451
452 }
453
454 void randomAssign(int count, int *perm)
455 {
456   for(int i=0;i<count;i++)
457     perm[i]=i;
458   for(int i=0;i<count;i++)
459   {
460     int randpos=i+rand()%(count-i);
461     int temp=perm[i];
462     perm[i]=perm[randpos];
463     perm[randpos]=temp;
464   }
465 }
466
467 void TopoLB::performMapping(int *newmap, int count)
468 {
469   int i,j;
470   if(_lb_debug_on)
471     CkPrintf("before performing mapping...\n");
472
473   double *distnew=new double[count];
474   for(i=0;i<count;i++)
475   {
476     //Assume i-1 partitions placed, 
477     //select and place the ith partition
478
479     //select the (c,p) pair
480     int part_index=-1;
481     int proc_index=-1;
482
483
484     double gainMax=-1;
485     for(j=0;j<count;j++)
486     {
487       if(!cfree[j])
488         continue;
489       
490       int hb_j_minIndex=(int)hopBytes[j][count];
491       //CmiAssert(pfree[hb_j_minIndex]);
492       double gain=hopBytes[j][count+1]-hopBytes[j][hb_j_minIndex];
493
494       //CmiAssert(gain>=0);
495       //CmiAssert(gain>=EPSILON);
496       
497       if(_lb_debug_on)
498         CkPrintf("Gain is : %lf\n",gain);
499
500       if(gain>gainMax)
501       {
502         part_index=j;
503         proc_index=hb_j_minIndex;
504         gainMax=gain;
505       }
506     }
507     if(_lb_debug_on)
508         CkPrintf("GainMax [%d] is : %lf\n",i,gainMax);
509
510     CmiAssert(part_index!=-1);
511     CmiAssert(proc_index!=-1);
512
513     //Assign the selection
514     CmiAssert(assign[part_index]==-1);
515     CmiAssert(pfree[proc_index]);
516     assign[part_index]=proc_index;
517     
518     /*
519     if(_lb_debug2_on)
520     {
521       if(i%100 ==0)
522         CkPrintf("Assigned %d procs \n",i+1);
523     }
524     */
525     
526     
527     /*****Update Data Structures******************/
528
529
530 #ifndef _FASTER_
531     cfree[part_index]=false;
532     pfree[proc_index]=false;
533
534     //Dont need to update other data structures if this is last assignment
535     if(i == count-1)
536       continue;
537
538     int procs_left=count-i-1;
539
540     //Update hopBytes
541     
542     for(j=0;j<count;j++)
543     {
544       if(procs_left>1)
545         distnew[j]=(dist[j][count]*procs_left -dist[j][proc_index]) / (procs_left-1);
546       else
547         distnew[j]=0;
548     }
549     for(int cpart=0;cpart<count;cpart++)
550     {
551       if(!cfree[cpart]) //No need to update for assigned partitions
552         continue;    
553
554       if(commUA[cpart]==0 && hopBytes[cpart][count]!=proc_index)
555       {
556         if(procs_left>0)
557           hopBytes[cpart][count+1]=(hopBytes[cpart][count+1]*(procs_left+1) - hopBytes[cpart][proc_index])/(procs_left);
558         continue;
559       }
560
561       //double hbmin=INFTY;
562       int h_min_index=-1;
563       double h_min=-1;
564       double h_total=0;
565
566       double c1=commUA[cpart];
567       double c2=comm[cpart][part_index];
568
569       double h_updated=0;
570
571       for(int proc=0;proc<count;proc++)
572       {
573         if(!pfree[proc]) // No need to update for assigned procs
574           continue;
575
576         hopBytes[cpart][proc]+=(c1-c2)*distnew[proc]+c2*dist[proc][proc_index]-c1*dist[proc][count];
577         h_updated=hopBytes[cpart][proc];
578         
579         //CmiAssert(hopBytes[cpart][proc] >= EPSILON);
580
581         h_total+=h_updated;
582         if( h_updated<h_min || h_min_index==-1 )
583         {
584           h_min=h_updated;
585           h_min_index=proc;
586         }
587       }
588       //CmiAssert(h_min_index!=-1);
589       hopBytes[cpart][count]=h_min_index;
590       hopBytes[cpart][count+1]=h_total/(procs_left);
591     }
592
593     // d[j][count] is the average dist of proc j to unassigned procs
594     // Also update commUA[j]
595     for(j=0;j<count;j++)
596     {
597       if(procs_left>1)
598         dist[j][count]=(dist[j][count]*procs_left -dist[j][proc_index]) / (procs_left-1);
599       else
600         dist[j][count]=0;
601       commUA[j]-=comm[j][part_index];
602     }
603
604 #else
605     cfree[part_index]=false;
606     pfree[proc_index]=false;
607
608     //Dont need to update other data structures if this is last assignment
609     if(i == count-1)
610       continue;
611
612     int procs_left=count-i-1;
613
614     //Update hopBytes
615     for(int cpart=0;cpart<count;cpart++)
616     {
617       //No need to update for assigned partitions
618       if(!cfree[cpart]) 
619         continue;    
620
621       //If cpart doesn't communicate with part_index, just need to update minimum and average hopBytes attainable for cpart
622       if(comm[cpart][part_index]==0) 
623       {
624         //change average
625         if(procs_left>0)
626           hopBytes[cpart][count+1]=(hopBytes[cpart][count+1]*(procs_left+1) - hopBytes[cpart][proc_index])/(procs_left);
627
628         //change minimum if needed
629         if(hopBytes[cpart][count]==proc_index)
630         {
631           int c_min=-1;
632           double c_min_val=-1;
633           for(int l=0;l<count;l++)
634           {
635             if(!pfree[l])
636               continue;
637             
638             if(c_min==-1 || hopBytes[cpart][l]<c_min_val)
639             {
640               c_min_val=hopBytes[cpart][l];
641               c_min=l;
642             }
643           }
644           CmiAssert(c_min!=-1);
645           hopBytes[cpart][count]=c_min;
646         }
647         continue;
648       }
649
650       // If reached here cpart communicates with the partition assigned in this step( part_index)
651       int h_min_index=-1;
652       double h_min=-1;
653       double h_total=0;
654
655       //double c1=commUA[cpart];
656       double c2=comm[cpart][part_index];
657
658       double h_updated=0;
659
660       for(int proc=0;proc<count;proc++)
661       {
662         if(!pfree[proc]) // No need to update for assigned procs
663           continue;
664
665         if(_DIJKSTRA_LIKE_)
666           hopBytes[cpart][proc]+=c2*(dist[proc][proc_index]);
667         else
668           hopBytes[cpart][proc]+=c2*(dist[proc][proc_index]-dist[proc][count]);
669         h_updated=hopBytes[cpart][proc];
670         
671         //CmiAssert(h_updated >= EPSILON);
672
673         h_total+=h_updated;
674         if(h_updated<h_min || h_min_index==-1 )
675         {
676           h_min=h_updated;
677           h_min_index=proc;
678         }
679       }
680       CmiAssert(h_min_index!=-1);
681       CmiAssert(pfree[h_min_index]);
682       hopBytes[cpart][count]=h_min_index;
683       hopBytes[cpart][count+1]=h_total/(procs_left);
684     }
685
686 #endif
687     
688   }
689   
690   /******************  Fill out final composition Mapping **************************/
691
692 }
693
694 void TopoLB :: work(CentralLB::LDStats *stats,int count)
695 {
696   int i, j;
697   if (_lb_args.debug() >= 2) 
698   {
699     CkPrintf("In TopoLB Strategy...\n");
700   }
701   
702   /****Make sure that there is at least one available processor.***/
703   int proc;
704   for (proc = 0; proc < count; proc++) 
705   {
706     if (stats->procs[proc].available)  
707       break;
708   }
709         
710   if (proc == count) 
711   {
712     CmiAbort ("TopoLB: no available processors!");
713   }
714  
715   removeNonMigratable(stats,count);
716
717   if(_lb_debug_on)
718   {
719     CkPrintf("Num of procs: %d\n",count);
720     CkPrintf("Num of objs:  %d\n",stats->n_objs);
721   }
722
723   /**************Initialize Topology ****************************/
724   LBtopoFn topofn;
725   topofn = LBTopoLookup(_lbtopo);
726   if (topofn == NULL) 
727   {
728         char str[1024];
729     CmiPrintf("TopoLB> Fatal error: Unknown topology: %s. Choose from:\n", _lbtopo);
730     printoutTopo();
731     sprintf(str, "TopoLB> Fatal error: Unknown topology: %s", _lbtopo);
732     CmiAbort(str);
733   }
734   topo = topofn(count);
735
736   /*********** Compute Partitions *********************************/
737   if(_lb_debug_on)
738     CkPrintf("before computing partitions...\n");
739   
740   int *newmap = new int[stats->n_objs];
741   if(_make_new_grouping_)
742     computePartitions(stats,count,newmap);
743   else
744   {
745     for(i=0;i<stats->n_objs;i++)
746     {
747       newmap[i]=stats->from_proc[i];
748     }
749   }
750   /***************** Fill Data Structures *************************/
751   if(_lb_debug_on)
752     CkPrintf("before allocating dataStructures...\n");
753
754   allocateDataStructures(count);
755
756   if(_lb_debug_on)
757     CkPrintf("before initizlizing dataStructures...\n");
758
759   initDataStructures(stats,count,newmap);
760
761   if(_lb_debug_on)
762     printDataStructures(count, stats->n_objs,newmap);
763   
764   /****************** Perform Mapping *****************************/
765
766   if(_lb_debug_on)
767     CkPrintf("before performing mapping...\n");
768   
769   performMapping(newmap,count);
770
771   for(i=0;i<stats->n_objs;i++)
772   {
773     stats->to_proc[i]= assign[newmap[i]];
774   }
775
776   if(_lb_debug2_on)
777   {
778     double hbval1=getHopBytesNew(NULL,count);
779     CkPrintf("\n");
780     CkPrintf(" Original hopBytes : %.1lf \n", hbval1);
781     CkPrintf(" Original Avg hops : %.1lf \n", hbval1/total_comm);
782     double hbval2=getHopBytesNew(assign,count);
783     //CkPrintf(" Resulting hopBytes : %.1lf \n", hbval2);
784     //CkPrintf(" Resulting Avg hops : %.1lf \n", hbval2/total_comm);
785     //CkPrintf(" Percentage gain %.2lf\n",(hbval1-hbval2)*100/hbval1);
786     //CkPrintf("\n");
787     
788     double total_hb_rand=0;
789     int nTrials=10;
790     for(int t=0;t<nTrials;t++)
791     {
792       randomAssign(count, assign);
793       double hbval3=getHopBytesNew(assign,count);
794       total_hb_rand+=hbval3;
795      //CkPrintf(" Random hopBytes : %.1lf \n", hbval3);
796      //CkPrintf(" Random Avg hops : %.1lf \n", hbval3/total_comm);
797     }
798     //CkPrintf("\n");
799     double hbval4=total_hb_rand/nTrials;
800     CkPrintf(" Average Random hopBytes : %.1lf \n", hbval4);
801     CkPrintf(" Average Random Avg hops : %.1lf \n", hbval4/total_comm);
802     CkPrintf(" Resulting hopBytes : %.1lf \n", hbval2);
803     CkPrintf(" Resulting Avg hops : %.1lf \n", hbval2/total_comm);
804     CkPrintf(" Percentage gain(TopoLB vs random) %.2lf\n",(hbval4-hbval2)*100/hbval4);
805     CkPrintf("\n");
806   }
807   freeDataStructures(count);
808   delete[] newmap;
809   return;
810 }
811
812
813 void TopoLB::printDataStructures(int count,int n_objs,int *newmap)
814 {
815   int i;
816   /*
817   CkPrintf("Partition Results : \n");
818   for(int i=0;i<n_objs;i++)
819   {
820     CkPrintf("map[%d] = %d\n",i,newmap[i]);
821   }
822   */
823
824   CkPrintf("Dist : \n");
825   for(i=0;i<count;i++)
826   {
827     for(int j=0;j<count+1;j++)
828     {
829       CkPrintf("%lf ",dist[i][j]);
830     }
831     CkPrintf("\n");
832   }
833   CkPrintf("HopBytes: \n");
834   for(i=0;i<count;i++)
835   {
836     for(int j=0;j<count+2;j++)
837     {
838       CkPrintf("%lf ",hopBytes[i][j]);
839     }
840     CkPrintf("\n");
841   }
842 }
843
844 double TopoLB::getHopBytesNew(int *assign_map, int count)
845 {
846   double totalHB=0;
847   int i,j;
848   if(assign_map==NULL)
849   {
850     for(i=0;i<count;i++)
851       for(j=0;j<count;j++)
852         totalHB+=dist[i][j]*comm[i][j];
853   }
854   else
855   {
856     for(i=0;i<count;i++)
857       for(j=0;j<count;j++)
858         totalHB+=dist[assign_map[i]][assign_map[j]]*comm[i][j];
859   }
860   return totalHB;
861 }
862
863 double TopoLB::getHopBytes(CentralLB::LDStats *stats,int count,CkVec<int>map)
864 {
865   int i;
866   double **comm1=new double*[count];
867   for(i=0;i<count;i++)
868     comm1[i]=new double[count];
869
870   for(i=0;i<count;i++)
871   {
872     for(int j=0;j<count;j++)
873     {
874       comm1[i][j]=0;
875     }
876   }
877
878   bool *multicastAdded=new bool[count];
879   for(i=0;i<stats->n_comm;i++)
880   {
881     LDCommData &cdata=stats->commData[i];
882     if(!cdata.from_proc() && cdata.receiver.get_type() ==LD_OBJ_MSG)
883     {
884       int sender=stats->getHash(cdata.sender);
885       int receiver=stats->getHash(cdata.receiver.get_destObj());
886
887       CmiAssert(sender<stats->n_objs);
888       CmiAssert(receiver<stats->n_objs);
889
890       if(map[sender]==map[receiver])
891         continue;
892
893       int send_part=map[sender];
894       int recv_part=map[receiver];
895       comm1[send_part][recv_part]+=cdata.bytes;
896       comm1[recv_part][send_part]+=cdata.bytes;
897     }
898     if(!cdata.from_proc() && cdata.receiver.get_type()==LD_OBJLIST_MSG)
899     {
900       int nobjs=0;
901       LDObjKey *receivers=cdata.receiver.get_destObjs(nobjs);
902       int sender=stats->getHash(cdata.sender);
903       int send_part=map[sender];
904       
905       CmiAssert(sender<stats->n_objs);
906
907       for(i=0;i<count;i++)
908         multicastAdded[i]=false;
909       multicastAdded[send_part]=true;
910
911       for(int k=0;k<nobjs;k++)
912       {
913         int receiver=stats->getHash(receivers[k]);
914         //CmiAssert ( (int)(receivers[k])< stats->n_objs);
915         CmiAssert ( receiver < stats->n_objs);
916
917         int recv_part=map[receiver];
918         if(!multicastAdded[recv_part])
919         {
920           comm1[send_part][recv_part]+=cdata.bytes;
921           comm1[recv_part][send_part]+=cdata.bytes;
922       
923           multicastAdded[recv_part]=true;
924         }
925       }
926     }
927   }
928   delete[] multicastAdded;
929
930   double totalHB=0;
931   int proc1,proc2;
932
933   for(i=0;i<count;i++)
934   {
935     proc1=map[i];
936     for(int j=0;j<count;j++)
937     {
938       proc2=map[j];
939       //totalHB+=dist[proc1][proc2]*comm1[i][j];
940       totalHB+=dist[i][j]*comm1[i][j];
941     }
942   }
943   for(i=0;i<count;i++)
944     delete[] comm1[i];
945   delete[] comm1;
946
947   return totalHB;
948 }
949
950 #include "TopoLB.def.h"