doc: Add serial to list of ci file reserved words
[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   options[0] = 0;
217
218   if (count < 1) {
219     CkPrintf("error: Number of Pe less than 1!");
220   }
221   else if (count == 1) {
222         for(m=0;m<numobjs;m++) 
223                         newmap[i] = origmap[i];
224   }
225   else {
226                 /*
227         if (count > 8)
228                         METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt, 
229                             &wgtflag, &numflag, &count, options, 
230                             &edgecut, newmap);
231           else
232                         METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt, 
233                                  &wgtflag, &numflag, &count, options, 
234                                  &edgecut, newmap);
235                 */
236    //CkPrintf("before calling metis.\n");
237                 METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt,
238                                  &wgtflag, &numflag, &count, options,
239                                  &edgecut, newmap);
240          //CkPrintf("after calling Metis function.\n");
241   }
242          
243   /*if (_lb_args.debug() >= 2) {
244         CkPrintf("Post-LDB Statistics step %d\n", step());
245         printStats(count, numobjs, objtime, comm, newmap);
246   }*/
247
248   for(i=0;i<numobjs;i++)
249     delete[] comm[i];
250   delete[] comm;
251   delete[] objtime;
252   delete[] xadj;
253   delete[] adjncy;
254   delete[] objwt;
255   delete[] edgewt;
256
257         //CkPrintf("chking wts on each partition...\n");
258
259         /*int avg=0;
260         int *chkwt = new int[count];
261         for(i=0;i<count;i++)
262                 chkwt[i]=0;
263         //totalwt=0;
264         for(i=0;i<numobjs;i++){
265                 chkwt[newmap[i]] += objwt[i];
266                 avg += objwt[i];
267         }
268         
269         for(i=0;i<count;i++)
270                 CkPrintf("%d -- %d\n",i,chkwt[i]);
271         
272         //CkPrintf("totalwt after:%d avg is %d\n",avg,avg/count);
273 */
274   /*if(!sameMapFlag) {
275     for(i=0; i<numobjs; i++) {
276       if(origmap[i] != newmap[i]) {
277                                 CmiAssert(stats->from_proc[i] == origmap[i]);
278                                 ///Dont assign....wait........
279                                 stats->to_proc[i] =  newmap[i];
280                                 if (_lb_args.debug() >= 3)
281           CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),i,stats->from_proc[i],stats->to_proc[i]);
282       }
283     }
284   }*/
285
286   delete[] origmap;
287 }
288
289 void TopoLB::initDataStructures(CentralLB::LDStats *stats,int count,int *newmap)
290 {
291   int i;
292   //init dist
293   if(_lb_debug_on)
294     CkPrintf("Before initing dist\n");
295  
296   topo->get_pairwise_hop_count(dist);
297   /*for(i=0;i<count;i++){
298    for(int j=0;j<count;j++)
299     CkPrintf("%.0lf ",dist[i][j]);
300    CkPrintf("\n");
301   }*/
302   for(i=0;i<count;i++)
303   {
304     double totaldist=0;
305     for(int j=0;j<count;j++)
306     {
307       //dist[i][j]=topo->get_hop_count(i,j);
308       totaldist+=dist[i][j];
309     }
310     dist[i][count]=totaldist/(count-1);
311   }
312
313   //Init comm,commUA from stats
314   stats->makeCommHash();
315   if(_lb_debug_on)
316     CkPrintf("Before initing comm\n");
317   for(i=0;i<count;i++)
318   {
319     for(int j=0;j<count;j++)
320     {
321       comm[i][j]=0;
322     }
323     commUA[i]=0;
324   }
325   bool *multicastAdded=new bool[count];
326   for(i=0;i<stats->n_comm;i++)
327   {
328     LDCommData &cdata=stats->commData[i];
329     if(!cdata.from_proc() && cdata.receiver.get_type() ==LD_OBJ_MSG)
330     {
331       int sender=stats->getHash(cdata.sender);
332       int receiver=stats->getHash(cdata.receiver.get_destObj());
333
334       CmiAssert(sender<stats->n_objs);
335       CmiAssert(receiver<stats->n_objs);
336
337       if(newmap[sender]==newmap[receiver])
338         continue;
339
340       int send_part=newmap[sender];
341       int recv_part=newmap[receiver];
342       comm[send_part][recv_part]+=cdata.bytes;
343       comm[recv_part][send_part]+=cdata.bytes;
344
345       commUA[send_part]+=cdata.bytes;
346       commUA[recv_part]+=cdata.bytes;
347     }
348     if(!cdata.from_proc() && cdata.receiver.get_type()==LD_OBJLIST_MSG)
349     {
350       int nobjs=0;
351       LDObjKey *receivers=cdata.receiver.get_destObjs(nobjs);
352       int sender=stats->getHash(cdata.sender);
353       int send_part=newmap[sender];
354       
355       CmiAssert(sender<stats->n_objs);
356
357       for(int i=0;i<count;i++)
358         multicastAdded[i]=false;
359       multicastAdded[send_part]=true;
360
361       for(int k=0;k<nobjs;k++)
362       {
363         int receiver=stats->getHash(receivers[k]);
364         CmiAssert ( receiver < stats->n_objs);
365
366         int recv_part=newmap[receiver];
367         if(!multicastAdded[recv_part])
368         {
369           comm[send_part][recv_part]+=cdata.bytes;
370           comm[recv_part][send_part]+=cdata.bytes;
371       
372           commUA[send_part]+=cdata.bytes;
373           commUA[recv_part]+=cdata.bytes;
374
375           multicastAdded[recv_part]=true;
376         }
377       }
378     }
379   }
380   /*****FIXED A MEMORY LEAK******/
381   delete[] multicastAdded;
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   int i;
457   for(i=0;i<count;i++)
458     perm[i]=i;
459   for(i=0;i<count;i++)
460   {
461     int randpos=i+rand()%(count-i);
462     int temp=perm[i];
463     perm[i]=perm[randpos];
464     perm[randpos]=temp;
465   }
466 }
467
468 void TopoLB::performMapping(int *newmap, int count)
469 {
470   int i,j;
471   if(_lb_debug_on)
472     CkPrintf("before performing mapping...\n");
473
474   double *distnew=new double[count];
475   for(i=0;i<count;i++)
476   {
477     //Assume i-1 partitions placed, 
478     //select and place the ith partition
479
480     //select the (c,p) pair
481     int part_index=-1;
482     int proc_index=-1;
483
484
485     double gainMax=-1;
486     for(j=0;j<count;j++)
487     {
488       if(!cfree[j])
489         continue;
490       
491       int hb_j_minIndex=(int)hopBytes[j][count];
492       //CmiAssert(pfree[hb_j_minIndex]);
493       double gain=hopBytes[j][count+1]-hopBytes[j][hb_j_minIndex];
494
495       //CmiAssert(gain>=0);
496       //CmiAssert(gain>=EPSILON);
497       
498       if(_lb_debug_on)
499         CkPrintf("Gain is : %lf\n",gain);
500
501       if(gain>gainMax)
502       {
503         part_index=j;
504         proc_index=hb_j_minIndex;
505         gainMax=gain;
506       }
507     }
508     if(_lb_debug_on)
509         CkPrintf("GainMax [%d] is : %lf\n",i,gainMax);
510
511     CmiAssert(part_index!=-1);
512     CmiAssert(proc_index!=-1);
513
514     //Assign the selection
515     CmiAssert(assign[part_index]==-1);
516     CmiAssert(pfree[proc_index]);
517     assign[part_index]=proc_index;
518     
519     /*
520     if(_lb_debug2_on)
521     {
522       if(i%100 ==0)
523         CkPrintf("Assigned %d procs \n",i+1);
524     }
525     */
526     
527     
528     /*****Update Data Structures******************/
529
530
531 #ifndef _FASTER_
532     cfree[part_index]=false;
533     pfree[proc_index]=false;
534
535     //Dont need to update other data structures if this is last assignment
536     if(i == count-1)
537       continue;
538
539     int procs_left=count-i-1;
540
541     //Update hopBytes
542     
543     for(j=0;j<count;j++)
544     {
545       if(procs_left>1)
546         distnew[j]=(dist[j][count]*procs_left -dist[j][proc_index]) / (procs_left-1);
547       else
548         distnew[j]=0;
549     }
550     for(int cpart=0;cpart<count;cpart++)
551     {
552       if(!cfree[cpart]) //No need to update for assigned partitions
553         continue;    
554
555       if(commUA[cpart]==0 && hopBytes[cpart][count]!=proc_index)
556       {
557         if(procs_left>0)
558           hopBytes[cpart][count+1]=(hopBytes[cpart][count+1]*(procs_left+1) - hopBytes[cpart][proc_index])/(procs_left);
559         continue;
560       }
561
562       //double hbmin=INFTY;
563       int h_min_index=-1;
564       double h_min=-1;
565       double h_total=0;
566
567       double c1=commUA[cpart];
568       double c2=comm[cpart][part_index];
569
570       double h_updated=0;
571
572       for(int proc=0;proc<count;proc++)
573       {
574         if(!pfree[proc]) // No need to update for assigned procs
575           continue;
576
577         hopBytes[cpart][proc]+=(c1-c2)*distnew[proc]+c2*dist[proc][proc_index]-c1*dist[proc][count];
578         h_updated=hopBytes[cpart][proc];
579         
580         //CmiAssert(hopBytes[cpart][proc] >= EPSILON);
581
582         h_total+=h_updated;
583         if( h_updated<h_min || h_min_index==-1 )
584         {
585           h_min=h_updated;
586           h_min_index=proc;
587         }
588       }
589       //CmiAssert(h_min_index!=-1);
590       hopBytes[cpart][count]=h_min_index;
591       hopBytes[cpart][count+1]=h_total/(procs_left);
592     }
593
594     // d[j][count] is the average dist of proc j to unassigned procs
595     // Also update commUA[j]
596     for(j=0;j<count;j++)
597     {
598       if(procs_left>1)
599         dist[j][count]=(dist[j][count]*procs_left -dist[j][proc_index]) / (procs_left-1);
600       else
601         dist[j][count]=0;
602       commUA[j]-=comm[j][part_index];
603     }
604
605 #else
606     cfree[part_index]=false;
607     pfree[proc_index]=false;
608
609     //Dont need to update other data structures if this is last assignment
610     if(i == count-1)
611       continue;
612
613     int procs_left=count-i-1;
614
615     //Update hopBytes
616     for(int cpart=0;cpart<count;cpart++)
617     {
618       //No need to update for assigned partitions
619       if(!cfree[cpart]) 
620         continue;    
621
622       //If cpart doesn't communicate with part_index, just need to update minimum and average hopBytes attainable for cpart
623       if(comm[cpart][part_index]==0) 
624       {
625         //change average
626         if(procs_left>0)
627           hopBytes[cpart][count+1]=(hopBytes[cpart][count+1]*(procs_left+1) - hopBytes[cpart][proc_index])/(procs_left);
628
629         //change minimum if needed
630         if(hopBytes[cpart][count]==proc_index)
631         {
632           int c_min=-1;
633           double c_min_val=-1;
634           for(int l=0;l<count;l++)
635           {
636             if(!pfree[l])
637               continue;
638             
639             if(c_min==-1 || hopBytes[cpart][l]<c_min_val)
640             {
641               c_min_val=hopBytes[cpart][l];
642               c_min=l;
643             }
644           }
645           CmiAssert(c_min!=-1);
646           hopBytes[cpart][count]=c_min;
647         }
648         continue;
649       }
650
651       // If reached here cpart communicates with the partition assigned in this step( part_index)
652       int h_min_index=-1;
653       double h_min=-1;
654       double h_total=0;
655
656       //double c1=commUA[cpart];
657       double c2=comm[cpart][part_index];
658
659       double h_updated=0;
660
661       for(int proc=0;proc<count;proc++)
662       {
663         if(!pfree[proc]) // No need to update for assigned procs
664           continue;
665
666         if(_DIJKSTRA_LIKE_)
667           hopBytes[cpart][proc]+=c2*(dist[proc][proc_index]);
668         else
669           hopBytes[cpart][proc]+=c2*(dist[proc][proc_index]-dist[proc][count]);
670         h_updated=hopBytes[cpart][proc];
671         
672         //CmiAssert(h_updated >= EPSILON);
673
674         h_total+=h_updated;
675         if(h_updated<h_min || h_min_index==-1 )
676         {
677           h_min=h_updated;
678           h_min_index=proc;
679         }
680       }
681       CmiAssert(h_min_index!=-1);
682       CmiAssert(pfree[h_min_index]);
683       hopBytes[cpart][count]=h_min_index;
684       hopBytes[cpart][count+1]=h_total/(procs_left);
685     }
686
687 #endif
688     
689   }
690  
691   /****FIXED a memory leak******/
692   delete [] distnew;
693   /******************  Fill out final composition Mapping **************************/
694
695 }
696
697 void TopoLB :: work(LDStats *stats)
698 {
699   int i;
700   int n_pes = stats->nprocs();
701
702   if (_lb_args.debug() >= 2) {
703     CkPrintf("In TopoLB Strategy...\n");
704   }
705   
706   /****Make sure that there is at least one available processor.***/
707   int proc;
708   for (proc = 0; proc < n_pes; proc++) {
709     if (stats->procs[proc].available)  
710       break;
711   }
712         
713   if (proc == n_pes) {
714     CmiAbort ("TopoLB: no available processors!");
715   }
716  
717   removeNonMigratable(stats, n_pes);
718
719   if(_lb_debug_on)
720   {
721     CkPrintf("Num of procs: %d\n", n_pes);
722     CkPrintf("Num of objs:  %d\n",stats->n_objs);
723   }
724
725   /**************Initialize Topology ****************************/
726   LBtopoFn topofn;
727   char *lbcopy = strdup(_lbtopo);
728   char *ptr = strchr(lbcopy, ':');
729   if (ptr!=NULL)
730     ptr = strtok(lbcopy, ":");
731         else
732                 ptr=lbcopy;
733
734   topofn = LBTopoLookup(ptr);
735   if (topofn == NULL) 
736   {
737         char str[1024];
738     CmiPrintf("TopoLB> Fatal error: Unknown topology: %s. Choose from:\n", _lbtopo);
739     printoutTopo();
740     sprintf(str, "TopoLB> Fatal error: Unknown topology: %s", _lbtopo);
741     CmiAbort(str);
742   }
743   topo = topofn(n_pes);
744
745   /*********** Compute Partitions *********************************/
746   if(_lb_debug_on)
747     CkPrintf("before computing partitions...\n");
748   
749   int *newmap = new int[stats->n_objs];
750   if(_make_new_grouping_)
751     computePartitions(stats, n_pes, newmap);
752   else
753   {
754     for(i=0;i<stats->n_objs;i++)
755     {
756       newmap[i]=stats->from_proc[i];
757     }
758   }
759   /***************** Fill Data Structures *************************/
760   if(_lb_debug_on)
761     CkPrintf("before allocating dataStructures...\n");
762
763   allocateDataStructures(n_pes);
764
765   if(_lb_debug_on)
766     CkPrintf("before initizlizing dataStructures...\n");
767
768   initDataStructures(stats, n_pes, newmap);
769
770   if(_lb_debug_on)
771     printDataStructures(n_pes, stats->n_objs, newmap);
772   
773   /****************** Perform Mapping *****************************/
774
775   if(_lb_debug_on)
776     CkPrintf("before performing mapping...\n");
777   
778   performMapping(newmap, n_pes);
779
780   for(i=0;i<stats->n_objs;i++)
781   {
782     stats->to_proc[i]= assign[newmap[i]];
783   }
784
785   if(_lb_debug2_on)
786   {
787     double hbval1=getHopBytesNew(NULL, n_pes);
788     CkPrintf("\n");
789     CkPrintf(" Original hopBytes : %.1lf \n", hbval1);
790     CkPrintf(" Original Avg hops : %.1lf \n", hbval1/total_comm);
791     double hbval2=getHopBytesNew(assign, n_pes);
792     //CkPrintf(" Resulting hopBytes : %.1lf \n", hbval2);
793     //CkPrintf(" Resulting Avg hops : %.1lf \n", hbval2/total_comm);
794     //CkPrintf(" Percentage gain %.2lf\n",(hbval1-hbval2)*100/hbval1);
795     //CkPrintf("\n");
796     
797     double total_hb_rand=0;
798     int nTrials=10;
799     for(int t=0;t<nTrials;t++)
800     {
801       randomAssign(n_pes, assign);
802       double hbval3=getHopBytesNew(assign, n_pes);
803       total_hb_rand+=hbval3;
804      //CkPrintf(" Random hopBytes : %.1lf \n", hbval3);
805      //CkPrintf(" Random Avg hops : %.1lf \n", hbval3/total_comm);
806     }
807     //CkPrintf("\n");
808     double hbval4=total_hb_rand/nTrials;
809     CkPrintf(" Average Random hopBytes : %.1lf \n", hbval4);
810     CkPrintf(" Average Random Avg hops : %.1lf \n", hbval4/total_comm);
811     CkPrintf(" Resulting hopBytes : %.1lf \n", hbval2);
812     CkPrintf(" Resulting Avg hops : %.1lf \n", hbval2/total_comm);
813     CkPrintf(" Percentage gain(TopoLB vs random) %.2lf\n",(hbval4-hbval2)*100/hbval4);
814     CkPrintf("\n");
815   }
816   freeDataStructures(n_pes);
817   delete[] newmap;
818   return;
819 }
820
821
822 void TopoLB::printDataStructures(int count,int n_objs,int *newmap)
823 {
824   int i;
825   /*
826   CkPrintf("Partition Results : \n");
827   for(int i=0;i<n_objs;i++)
828   {
829     CkPrintf("map[%d] = %d\n",i,newmap[i]);
830   }
831   */
832
833   CkPrintf("Dist : \n");
834   for(i=0;i<count;i++)
835   {
836     for(int j=0;j<count+1;j++)
837     {
838       CkPrintf("%lf ",dist[i][j]);
839     }
840     CkPrintf("\n");
841   }
842   CkPrintf("HopBytes: \n");
843   for(i=0;i<count;i++)
844   {
845     for(int j=0;j<count+2;j++)
846     {
847       CkPrintf("%lf ",hopBytes[i][j]);
848     }
849     CkPrintf("\n");
850   }
851 }
852
853 double TopoLB::getHopBytesNew(int *assign_map, int count)
854 {
855   double totalHB=0;
856   int i,j;
857   if(assign_map==NULL)
858   {
859     for(i=0;i<count;i++)
860       for(j=0;j<count;j++)
861         totalHB+=dist[i][j]*comm[i][j];
862   }
863   else
864   {
865     for(i=0;i<count;i++)
866       for(j=0;j<count;j++)
867         totalHB+=dist[assign_map[i]][assign_map[j]]*comm[i][j];
868   }
869   return totalHB;
870 }
871
872 double TopoLB::getHopBytes(CentralLB::LDStats *stats,int count,CkVec<int>map)
873 {
874   int i;
875   double **comm1=new double*[count];
876   for(i=0;i<count;i++)
877     comm1[i]=new double[count];
878
879   for(i=0;i<count;i++)
880   {
881     for(int j=0;j<count;j++)
882     {
883       comm1[i][j]=0;
884     }
885   }
886
887   bool *multicastAdded=new bool[count];
888   for(i=0;i<stats->n_comm;i++)
889   {
890     LDCommData &cdata=stats->commData[i];
891     if(!cdata.from_proc() && cdata.receiver.get_type() ==LD_OBJ_MSG)
892     {
893       int sender=stats->getHash(cdata.sender);
894       int receiver=stats->getHash(cdata.receiver.get_destObj());
895
896       CmiAssert(sender<stats->n_objs);
897       CmiAssert(receiver<stats->n_objs);
898
899       if(map[sender]==map[receiver])
900         continue;
901
902       int send_part=map[sender];
903       int recv_part=map[receiver];
904       comm1[send_part][recv_part]+=cdata.bytes;
905       comm1[recv_part][send_part]+=cdata.bytes;
906     }
907     if(!cdata.from_proc() && cdata.receiver.get_type()==LD_OBJLIST_MSG)
908     {
909       int nobjs=0;
910       LDObjKey *receivers=cdata.receiver.get_destObjs(nobjs);
911       int sender=stats->getHash(cdata.sender);
912       int send_part=map[sender];
913       
914       CmiAssert(sender<stats->n_objs);
915
916       for(i=0;i<count;i++)
917         multicastAdded[i]=false;
918       multicastAdded[send_part]=true;
919
920       for(int k=0;k<nobjs;k++)
921       {
922         int receiver=stats->getHash(receivers[k]);
923         //CmiAssert ( (int)(receivers[k])< stats->n_objs);
924         CmiAssert ( receiver < stats->n_objs);
925
926         int recv_part=map[receiver];
927         if(!multicastAdded[recv_part])
928         {
929           comm1[send_part][recv_part]+=cdata.bytes;
930           comm1[recv_part][send_part]+=cdata.bytes;
931       
932           multicastAdded[recv_part]=true;
933         }
934       }
935     }
936   }
937   delete[] multicastAdded;
938
939   double totalHB=0;
940
941   for(i=0;i<count;i++)
942   {
943     for(int j=0;j<count;j++)
944     {
945       totalHB+=dist[i][j]*comm1[i][j];
946     }
947   }
948   for(i=0;i<count;i++)
949     delete[] comm1[i];
950   delete[] comm1;
951
952   return totalHB;
953 }
954
955 #include "TopoLB.def.h"