985c988013553135af440ef8749a4cb51be899fd
[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
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   //Allocating in separate loop to have somewhat contiguous memory allocation
66   hopBytes=new double*[count];
67   for(int i=0;i<count;i++)
68   {
69     hopBytes[i]=new double[count+2];
70   }
71
72   dist=new double*[count];
73   for(int i=0;i<count;i++)
74   {
75     dist[i]=new double[count+1];
76   }
77
78   comm=new double*[count];
79   for(int i=0;i<count;i++)
80   {
81     comm[i]=new double[count];
82   }
83
84   commUA=new double[count];
85   pfree=new bool[count];
86   cfree=new bool[count];
87   assign=new int[count];
88 }
89
90
91 void TopoLB::computePartitions(CentralLB::LDStats *stats,int count,int *newmap)
92 {
93   int numobjs = stats->n_objs;
94         int i, j, m;
95
96   // allocate space for the computing data
97   double *objtime = new double[numobjs];
98   int *objwt = new int[numobjs];
99   int *origmap = new int[numobjs];
100   LDObjHandle *handles = new LDObjHandle[numobjs];
101   
102         for(i=0;i<numobjs;i++) {
103     objtime[i] = 0.0;
104     objwt[i] = 0;
105     origmap[i] = 0;
106   }
107
108   for (i=0; i<stats->n_objs; i++) {
109     LDObjData &odata = stats->objData[i];
110     if (!odata.migratable) 
111       CmiAbort("MetisLB doesnot dupport nonmigratable object.\n");
112     int frompe = stats->from_proc[i];
113     origmap[i] = frompe;
114     objtime[i] = odata.wallTime*stats->procs[frompe].pe_speed;
115     handles[i] = odata.handle;
116   }
117
118   // to convert the weights on vertices to integers
119   double max_objtime = objtime[0];
120   for(i=0; i<numobjs; i++) {
121     if(max_objtime < objtime[i])
122       max_objtime = objtime[i];
123   }
124         int maxobj=0;
125         int totalwt=0;
126   double ratio = 1000.0/max_objtime;
127   for(i=0; i<numobjs; i++) {
128       objwt[i] = (int)(objtime[i]*ratio);
129                         if(maxobj<objwt[i])
130                                 maxobj=objwt[i];
131                         totalwt+=objwt[i];
132   }
133         
134         //CkPrintf("\nmax obj wt :%d \n totalwt before :%d \n\n",maxobj,totalwt);
135         
136   int **comm = new int*[numobjs];
137   for (i=0; i<numobjs; i++) {
138     comm[i] = new int[numobjs];
139     for (j=0; j<numobjs; j++)  {
140       comm[i][j] = 0;
141     }
142   }
143
144   const int csz = stats->n_comm;
145   for(i=0; i<csz; i++) {
146       LDCommData &cdata = stats->commData[i];
147       //if(cdata.from_proc() || cdata.receiver.get_type() != LD_OBJ_MSG)
148         //continue;
149                         if(!cdata.from_proc() && cdata.receiver.get_type() == LD_OBJ_MSG){
150         int senderID = stats->getHash(cdata.sender);
151         int recverID = stats->getHash(cdata.receiver.get_destObj());
152         CmiAssert(senderID < numobjs);
153         CmiAssert(recverID < numobjs);
154         //comm[senderID][recverID] += (int)(cdata.messages*alpha + cdata.bytes*beta);
155         //comm[recverID][senderID] += (int)(cdata.messages*alpha + cdata.bytes*beta);
156                 //CkPrintf("in compute partitions...%d\n",comm[senderID][recverID]);
157                                 comm[senderID][recverID] += cdata.messages;
158         comm[recverID][senderID] += cdata.messages;
159
160                                 //Use bytes or messages -- do i include messages for objlist too...??
161                         }
162                         else if (cdata.receiver.get_type() == LD_OBJLIST_MSG) {
163                                 //CkPrintf("in objlist..\n");
164         int nobjs;
165         LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
166         int senderID = stats->getHash(cdata.sender);
167         for (j=0; j<nobjs; j++) {
168            int recverID = stats->getHash(objs[j]);
169            if((senderID == -1)||(recverID == -1))
170               if (_lb_args.migObjOnly()) continue;
171               else CkAbort("Error in search\n");
172            comm[senderID][recverID] += cdata.messages;
173            comm[recverID][senderID] += cdata.messages;
174         }
175                         }
176                 }
177
178 // ignore messages sent from an object to itself
179   for (i=0; i<numobjs; i++)
180     comm[i][i] = 0;
181
182   // construct the graph in CSR format
183   int *xadj = new int[numobjs+1];
184   int numedges = 0;
185   for(i=0;i<numobjs;i++) {
186     for(j=0;j<numobjs;j++) {
187       if(comm[i][j] != 0)
188         numedges++;
189     }
190   }
191   int *adjncy = new int[numedges];
192   int *edgewt = new int[numedges];
193         int factor = 10;
194   xadj[0] = 0;
195   int count4all = 0;
196   for (i=0; i<numobjs; i++) {
197     for (j=0; j<numobjs; j++) { 
198       if (comm[i][j] != 0) { 
199         adjncy[count4all] = j;
200         edgewt[count4all++] = comm[i][j]/factor;
201       }
202     }
203     xadj[i+1] = count4all;
204   }
205
206   /*if (_lb_args.debug() >= 2) {
207   CkPrintf("Pre-LDB Statistics step %d\n", step());
208   printStats(count, numobjs, objtime, comm, origmap);
209   }*/
210
211   int wgtflag = 3; // Weights both on vertices and edges
212   int numflag = 0; // C Style numbering
213   int options[5];
214   int edgecut;
215   int sameMapFlag = 1;
216
217         options[0] = 0;
218
219   if (count < 1) {
220     CkPrintf("error: Number of Pe less than 1!");
221   }
222   else if (count == 1) {
223         for(m=0;m<numobjs;m++) 
224                         newmap[i] = origmap[i];
225         sameMapFlag = 1;
226   }
227   else {
228         sameMapFlag = 0;
229                 /*
230         if (count > 8)
231                         METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt, 
232                             &wgtflag, &numflag, &count, options, 
233                             &edgecut, newmap);
234           else
235                         METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt, 
236                                  &wgtflag, &numflag, &count, options, 
237                                  &edgecut, newmap);
238                 */
239    //CkPrintf("before calling metis.\n");
240                 METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt,
241                                  &wgtflag, &numflag, &count, options,
242                                  &edgecut, newmap);
243          //CkPrintf("after calling Metis function.\n");
244   }
245          
246   /*if (_lb_args.debug() >= 2) {
247         CkPrintf("Post-LDB Statistics step %d\n", step());
248         printStats(count, numobjs, objtime, comm, newmap);
249   }*/
250
251   for(i=0;i<numobjs;i++)
252     delete[] comm[i];
253   delete[] comm;
254   delete[] objtime;
255   delete[] xadj;
256   delete[] adjncy;
257   delete[] objwt;
258   delete[] edgewt;
259
260         //CkPrintf("chking wts on each partition...\n");
261
262         /*int avg=0;
263         int *chkwt = new int[count];
264         for(i=0;i<count;i++)
265                 chkwt[i]=0;
266         //totalwt=0;
267         for(i=0;i<numobjs;i++){
268                 chkwt[newmap[i]] += objwt[i];
269                 avg += objwt[i];
270         }
271         
272         for(i=0;i<count;i++)
273                 CkPrintf("%d -- %d\n",i,chkwt[i]);
274         
275         //CkPrintf("totalwt after:%d avg is %d\n",avg,avg/count);
276 */
277   /*if(!sameMapFlag) {
278     for(i=0; i<numobjs; i++) {
279       if(origmap[i] != newmap[i]) {
280                                 CmiAssert(stats->from_proc[i] == origmap[i]);
281                                 ///Dont assign....wait........
282                                 stats->to_proc[i] =  newmap[i];
283                                 if (_lb_args.debug() >= 3)
284           CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),i,stats->from_proc[i],stats->to_proc[i]);
285       }
286     }
287   }*/
288
289   delete[] origmap;
290 }
291
292 void TopoLB::initDataStructures(CentralLB::LDStats *stats,int count,int *newmap)
293 {
294   //init dist
295   if(_lb_debug_on)
296     CkPrintf("Before initing dist\n");
297  
298   topo->get_pairwise_hop_count(dist);
299   for(int i=0;i<count;i++)
300   {
301     double totaldist=0;
302     for(int j=0;j<count;j++)
303     {
304       //dist[i][j]=topo->get_hop_count(i,j);
305       totaldist+=dist[i][j];
306     }
307     dist[i][count]=totaldist/(count-1);
308   }
309
310   //Init comm,commUA from stats
311   if(_lb_debug_on)
312     CkPrintf("Before initing comm\n");
313   for(int i=0;i<count;i++)
314   {
315     for(int j=0;j<count;j++)
316     {
317       comm[i][j]=0;
318     }
319     commUA[i]=0;
320   }
321   bool *multicastAdded=new bool[count];
322   for(int i=0;i<stats->n_comm;i++)
323   {
324     LDCommData &cdata=stats->commData[i];
325     if(!cdata.from_proc() && cdata.receiver.get_type() ==LD_OBJ_MSG)
326     {
327       int sender=stats->getHash(cdata.sender);
328       int receiver=stats->getHash(cdata.receiver.get_destObj());
329
330       CmiAssert(sender<stats->n_objs);
331       CmiAssert(receiver<stats->n_objs);
332
333       if(newmap[sender]==newmap[receiver])
334         continue;
335
336       int send_part=newmap[sender];
337       int recv_part=newmap[receiver];
338       comm[send_part][recv_part]+=cdata.bytes;
339       comm[recv_part][send_part]+=cdata.bytes;
340
341       commUA[send_part]+=cdata.bytes;
342       commUA[recv_part]+=cdata.bytes;
343     }
344     if(!cdata.from_proc() && cdata.receiver.get_type()==LD_OBJLIST_MSG)
345     {
346       int nobjs=0;
347       LDObjKey *receivers=cdata.receiver.get_destObjs(nobjs);
348       int sender=stats->getHash(cdata.sender);
349       int send_part=newmap[sender];
350       
351       CmiAssert(sender<stats->n_objs);
352
353       for(int i=0;i<count;i++)
354         multicastAdded[i]=false;
355       multicastAdded[send_part]=true;
356
357       for(int k=0;k<nobjs;k++)
358       {
359         int receiver=stats->getHash(receivers[k]);
360         CmiAssert ( receiver < stats->n_objs);
361
362         int recv_part=newmap[receiver];
363         if(!multicastAdded[recv_part])
364         {
365           comm[send_part][recv_part]+=cdata.bytes;
366           comm[recv_part][send_part]+=cdata.bytes;
367       
368           commUA[send_part]+=cdata.bytes;
369           commUA[recv_part]+=cdata.bytes;
370
371           multicastAdded[recv_part]=true;
372         }
373       }
374     }
375   }
376
377   /******Avg degree test *******/
378   total_comm=0;
379   if(_lb_debug2_on)
380   {
381     int avg_degree=0;
382     for(int i=0;i<count;i++)
383     {
384       double comm_i_total=0;
385       for(int j=0;j<count;j++)
386       {
387         //Just a test
388         //comm[i][j]=(rand()%10 ==0);
389         //comm[i][j]=(dist[i][j]>count/4);
390         avg_degree+=(comm[i][j]>0);
391         total_comm+=comm[i][j];
392         comm_i_total+=comm[i][j];
393       }
394       //Just a test
395       //commUA[i]=comm_i_total;
396     }
397     CkPrintf("Avg degree (%d nodes) : %d\n",count,avg_degree/count);
398   }
399   /***************************/
400
401   //Init hopBytes
402   //hopBytes[i][j]=hopBytes if partition i is placed at proc j
403   if(_lb_debug_on)
404     CkPrintf("Before initing hopBytes\n");
405   for(int i=0;i<count;i++)
406   {
407     int hbminIndex=0;
408     double hbtotal=0;
409     for(int j=0;j<count;j++)
410     {
411       //Initialize by (total comm of i)*(avg dist from j);
412       hopBytes[i][j]=commUA[i]*dist[j][count];
413       //Just a test
414       //hopBytes[i][j]=0;
415       hbtotal+=hopBytes[i][j];
416       if(hopBytes[i][hbminIndex]>hopBytes[i][j])
417         hbminIndex=j;
418     }
419     hopBytes[i][count]=hbminIndex;
420     hopBytes[i][count+1]=hbtotal/count;
421   }
422   
423   //Init pfree, cfree, assign
424   if(_lb_debug_on)
425     CkPrintf("Before initing pfree cfree assign\n");
426   for(int i=0;i<count;i++)
427   {
428     pfree[i]=true;
429     cfree[i]=true;
430     assign[i]=-1;
431   }
432 }
433
434 void TopoLB :: work(CentralLB::LDStats *stats,int count)
435 {
436   if (_lb_args.debug() >= 2) 
437   {
438     CkPrintf("In TopoLB Strategy...\n");
439   }
440   
441   /****Make sure that there is at least one available processor.***/
442   int proc;
443   for (proc = 0; proc < count; proc++) 
444   {
445     if (stats->procs[proc].available)  
446       break;
447   }
448         
449   if (proc == count) 
450   {
451     CmiAbort ("TopoLB: no available processors!");
452   }
453  
454   removeNonMigratable(stats,count);
455
456   if(_lb_debug_on)
457   {
458     CkPrintf("Num of procs: %d\n",count);
459     CkPrintf("Num of objs:  %d\n",stats->n_objs);
460   }
461
462   /**************Initialize Topology ****************************/
463   LBtopoFn topofn;
464   topofn = LBTopoLookup(_lbtopo);
465   if (topofn == NULL) 
466   {
467         char str[1024];
468     CmiPrintf("TopoLB> Fatal error: Unknown topology: %s. Choose from:\n", _lbtopo);
469     printoutTopo();
470     sprintf(str, "TopoLB> Fatal error: Unknown topology: %s", _lbtopo);
471     CmiAbort(str);
472   }
473   topo = topofn(count);
474
475   /*********** Compute Partitions *********************************/
476   if(_lb_debug_on)
477     CkPrintf("before computing partitions...\n");
478   
479   int *newmap = new int[stats->n_objs];
480   if(_make_new_grouping_)
481     computePartitions(stats,count,newmap);
482   else
483   {
484     for(int i=0;i<stats->n_objs;i++)
485     {
486       newmap[i]=stats->from_proc[i];
487     }
488   }
489   /***************** Fill Data Structures *************************/
490   if(_lb_debug_on)
491     CkPrintf("before allocating dataStructures...\n");
492   allocateDataStructures(count);
493   if(_lb_debug_on)
494     CkPrintf("before initizlizing dataStructures...\n");
495   initDataStructures(stats,count,newmap);
496
497   if(_lb_debug_on)
498     printDataStructures(count, stats->n_objs,newmap);
499   
500   /****************** Perform Mapping *****************************/
501
502   if(_lb_debug_on)
503     CkPrintf("before performing mapping...\n");
504
505   double *distnew=new double[count];
506   for(int i=0;i<count;i++)
507   {
508     //Assume i-1 partitions placed, 
509     //select and place the ith partition
510
511     //select the (c,p) pair
512     int part_index=-1;
513     int proc_index=-1;
514
515
516     double gainMax=-1;
517     for(int j=0;j<count;j++)
518     {
519       if(!cfree[j])
520         continue;
521       
522       int hb_j_minIndex=(int)hopBytes[j][count];
523       //CmiAssert(pfree[hb_j_minIndex]);
524       double gain=hopBytes[j][count+1]-hopBytes[j][hb_j_minIndex];
525
526       //CmiAssert(gain>=0);
527       //CmiAssert(gain>=EPSILON);
528       
529       if(_lb_debug_on)
530         CkPrintf("Gain is : %lf\n",gain);
531
532       if(gain>gainMax)
533       {
534         part_index=j;
535         proc_index=hb_j_minIndex;
536         gainMax=gain;
537       }
538     }
539     if(_lb_debug_on)
540         CkPrintf("GainMax is : %lf\n",gainMax);
541
542     CmiAssert(part_index!=-1);
543     CmiAssert(proc_index!=-1);
544
545     //Assign the selection
546     CmiAssert(assign[part_index]==-1);
547     CmiAssert(pfree[proc_index]);
548     assign[part_index]=proc_index;
549     
550     /*
551     if(i==0)
552     {
553       double  maxComm=-1;
554       int maxCommIndex=-1;
555       for(int l=0;l<count;l++)
556       {
557         if(commUA[l]>maxComm)
558         {
559           maxComm=commUA[l];
560           maxCommIndex=l;
561         }
562       }
563       CkPrintf("Max communicating : %d\n",maxCommIndex);
564       CkPrintf("First selection   : %d\n",part_index);
565     }
566     */
567
568     //CkPrintf("assign[%d]=%d\n",part_index,proc_index);
569     /*
570     if(_lb_debug2_on)
571     {
572       if(i%100 ==0)
573         CkPrintf("Assigned %d procs \n",i+1);
574     }
575     */
576     /*****Update Data Structures******************/
577     cfree[part_index]=false;
578     pfree[proc_index]=false;
579
580     //Dont need to update other data structures if this is last assignment
581     if(i == count-1)
582       continue;
583
584     int procs_left=count-i-1;
585
586     //Update hopBytes
587     
588     for(int j=0;j<count;j++)
589     {
590       if(procs_left>1)
591         distnew[j]=(dist[j][count]*procs_left -dist[j][proc_index]) / (procs_left-1);
592       else
593         distnew[j]=0;
594     }
595     for(int cpart=0;cpart<count;cpart++)
596     {
597       if(!cfree[cpart]) //No need to update for assigned partitions
598         continue;    
599
600       //double hbmin=INFTY;
601       double hbmin=-1;
602       double hbtotal=0;
603
604       double c1=commUA[cpart];
605       double c2=comm[cpart][part_index];
606
607       double h_updated=0;
608       int h_minindex=(int)hopBytes[cpart][count];
609
610       for(int proc=0;proc<count;proc++)
611       {
612         if(!pfree[proc]) // No need to update for assigned procs
613           continue;
614
615         /*
616         hopBytes[cpart][proc]-=commUA[cpart]*dist[proc][count];
617         hopBytes[cpart][proc]+=comm[cpart][part_index]*dist[proc][proc_index];
618         hopBytes[cpart][proc]+=(commUA[cpart]-comm[cpart][part_index])*distnew[proc];
619         */
620
621         hopBytes[cpart][proc]+=(c1-c2)*distnew[proc]+c2*dist[proc][proc_index]-c1*dist[proc][count];
622         //Just a test
623         //hopBytes[cpart][proc]+=c2*dist[proc][proc_index];
624         h_updated=hopBytes[cpart][proc];
625         
626         //CmiAssert((commUA[cpart]-comm[cpart][part_index]) >= EPSILON);
627         //CmiAssert(hopBytes[cpart][proc] >= EPSILON);
628         //CmiAssert(hopBytes[cpart][proc] >= EPSILON);
629
630         hbtotal+=h_updated;
631         if(hbmin==-1 || h_updated<hbmin)
632         {
633           hbmin=h_updated;
634           h_minindex=proc;
635         }
636       }
637       hopBytes[cpart][count]=h_minindex;
638       //CmiAssert(hbmin!=-1);
639       hopBytes[cpart][count+1]=hbtotal/(procs_left);
640     }
641
642     // d[j][count] is the average dist of proc j to unassigned procs
643     // Also update commUA[j]
644     for(int j=0;j<count;j++)
645     {
646       if(procs_left>1)
647         dist[j][count]=(dist[j][count]*procs_left -dist[j][proc_index]) / (procs_left-1);
648       else
649         dist[j][count]=0;
650       commUA[j]-=comm[j][part_index];
651     }
652   }
653
654   /******************  Fill out final composition Mapping **************************/
655
656   for(int i=0;i<stats->n_objs;i++)
657   {
658     stats->to_proc[i]= assign[newmap[i]];
659   }
660
661   if(_lb_debug2_on)
662   {
663     double hbval1=getHopBytes(stats,count,stats->from_proc);
664     CkPrintf(" Original   hopBytes : %lf  Avg comm hops: %lf\n", hbval1,hbval1/total_comm);
665     double hbval2=getHopBytes(stats,count,stats->to_proc);
666     CkPrintf(" Resulting  hopBytes : %lf  Avg comm hops: %lf\n", hbval2,hbval2/total_comm);
667     CkPrintf("Percentage gain %.2lf\n",(hbval1-hbval2)*100/hbval1);
668   }
669
670   freeDataStructures(count);
671   delete[] newmap;
672 }
673
674
675 void TopoLB::printDataStructures(int count,int n_objs,int *newmap)
676 {
677   /*
678   CkPrintf("Partition Results : \n");
679   for(int i=0;i<n_objs;i++)
680   {
681     CkPrintf("map[%d] = %d\n",i,newmap[i]);
682   }
683   */
684
685   CkPrintf("Dist : \n");
686   for(int i=0;i<count;i++)
687   {
688     for(int j=0;j<count+1;j++)
689     {
690       CkPrintf("%lf ",dist[i][j]);
691     }
692     CkPrintf("\n");
693   }
694   CkPrintf("HopBytes: \n");
695   for(int i=0;i<count;i++)
696   {
697     for(int j=0;j<count+2;j++)
698     {
699       CkPrintf("%lf ",hopBytes[i][j]);
700     }
701     CkPrintf("\n");
702   }
703 }
704 double TopoLB::getHopBytes(CentralLB::LDStats *stats,int count,CkVec<int>map)
705 {
706   double **comm1=new double*[count];
707   for(int i=0;i<count;i++)
708     comm1[i]=new double[count];
709
710   for(int i=0;i<count;i++)
711   {
712     for(int j=0;j<count;j++)
713     {
714       comm1[i][j]=0;
715     }
716   }
717
718   bool *multicastAdded=new bool[count];
719   for(int i=0;i<stats->n_comm;i++)
720   {
721     LDCommData &cdata=stats->commData[i];
722     if(!cdata.from_proc() && cdata.receiver.get_type() ==LD_OBJ_MSG)
723     {
724       int sender=stats->getHash(cdata.sender);
725       int receiver=stats->getHash(cdata.receiver.get_destObj());
726
727       CmiAssert(sender<stats->n_objs);
728       CmiAssert(receiver<stats->n_objs);
729
730       if(map[sender]==map[receiver])
731         continue;
732
733       int send_part=map[sender];
734       int recv_part=map[receiver];
735       comm1[send_part][recv_part]+=cdata.bytes;
736       comm1[recv_part][send_part]+=cdata.bytes;
737     }
738     if(!cdata.from_proc() && cdata.receiver.get_type()==LD_OBJLIST_MSG)
739     {
740       int nobjs=0;
741       LDObjKey *receivers=cdata.receiver.get_destObjs(nobjs);
742       int sender=stats->getHash(cdata.sender);
743       int send_part=map[sender];
744       
745       CmiAssert(sender<stats->n_objs);
746
747       for(int i=0;i<count;i++)
748         multicastAdded[i]=false;
749       multicastAdded[send_part]=true;
750
751       for(int k=0;k<nobjs;k++)
752       {
753         int receiver=stats->getHash(receivers[k]);
754         //CmiAssert ( (int)(receivers[k])< stats->n_objs);
755         CmiAssert ( receiver < stats->n_objs);
756
757         int recv_part=map[receiver];
758         if(!multicastAdded[recv_part])
759         {
760           comm1[send_part][recv_part]+=cdata.bytes;
761           comm1[recv_part][send_part]+=cdata.bytes;
762       
763           multicastAdded[recv_part]=true;
764         }
765       }
766     }
767   }
768   delete[] multicastAdded;
769
770   double totalHB=0;
771   int proc1,proc2;
772
773   for(int i=0;i<count;i++)
774   {
775     proc1=map[i];
776     for(int j=0;j<count;j++)
777     {
778       proc2=map[j];
779       //totalHB+=dist[proc1][proc2]*comm1[i][j];
780       totalHB+=dist[i][j]*comm1[i][j];
781     }
782   }
783   for(int i=0;i<count;i++)
784     delete[] comm1[i];
785   delete[] comm1;
786
787   return totalHB;
788 }
789
790
791 #include "TopoLB.def.h"