Added a new topology conscious LB called TopoCentLB
[charm.git] / src / ck-ldb / TopoCentLB.C
1 /**************************************************************************
2 ** Amit Sharma (asharma6@uiuc.edu)
3 ** November 23, 2004
4 **
5 ** This is a topology conscious load balancer.
6 ** It migrates objects to new processors based on the topology in which the processors are connected.
7 ****************************************************************************/
8
9 #include <math.h>
10 #include <stdlib.h>
11 #include "charm++.h"
12 #include "cklists.h"
13 #include "CentralLB.h"
14
15 #include "TopoCentLB.decl.h"
16
17 #include "TopoCentLB.h"
18
19 #define alpha PER_MESSAGE_SEND_OVERHEAD_DEFAULT  /*Startup time per message, seconds*/
20 #define beta PER_BYTE_SEND_OVERHEAD_DEFAULT     /*Long-message time per byte, seconds*/
21 #define DEG_THRES 0.50
22
23 //#define MAX_EDGE
24
25 CreateLBFunc_Def(TopoCentLB,"Balance objects based on the network topology");
26
27
28 /*static void lbinit (void)
29 {
30   LBRegisterBalancer ("TopoCentLB",
31                       CreateTopoCentLB,
32                       AllocateTopoCentLB,
33                       "Balance objects based on the network topology");
34 }*/
35
36
37 TopoCentLB::TopoCentLB(const CkLBOptions &opt) : CentralLB (opt)
38 {
39   lbname = "TopoCentLB";
40   if (CkMyPe () == 0) {
41     CkPrintf ("[%d] TopoCentLB created\n",CkMyPe());
42   }
43 }
44
45
46 CmiBool TopoCentLB::QueryBalanceNow (int _step)
47 {
48   return CmiTrue;
49 }
50
51
52 void TopoCentLB::computePartitions(CentralLB::LDStats *stats,int count,int *newmap)
53 {
54         
55   int numobjs = stats->n_objs;
56         int i, j, m;
57
58   // allocate space for the computing data
59   double *objtime = new double[numobjs];
60   int *objwt = new int[numobjs];
61   int *origmap = new int[numobjs];
62   LDObjHandle *handles = new LDObjHandle[numobjs];
63   
64         for(i=0;i<numobjs;i++) {
65     objtime[i] = 0.0;
66     objwt[i] = 0;
67     origmap[i] = 0;
68   }
69
70   for (i=0; i<stats->n_objs; i++) {
71     LDObjData &odata = stats->objData[i];
72     if (!odata.migratable) 
73       CmiAbort("MetisLB doesnot dupport nonmigratable object.\n");
74     int frompe = stats->from_proc[i];
75     origmap[i] = frompe;
76     objtime[i] = odata.wallTime*stats->procs[frompe].pe_speed;
77     handles[i] = odata.handle;
78   }
79
80   // to convert the weights on vertices to integers
81   double max_objtime = objtime[0];
82   for(i=0; i<numobjs; i++) {
83     if(max_objtime < objtime[i])
84       max_objtime = objtime[i];
85   }
86         int maxobj=0;
87         int totalwt=0;
88   double ratio = 1000.0/max_objtime;
89   for(i=0; i<numobjs; i++) {
90       objwt[i] = (int)(objtime[i]*ratio);
91                         if(maxobj<objwt[i])
92                                 maxobj=objwt[i];
93                         totalwt+=objwt[i];
94   }
95         
96         //CkPrintf("\nmax obj wt :%d \n totalwt before :%d \n\n",maxobj,totalwt);
97         
98   int **comm = new int*[numobjs];
99   for (i=0; i<numobjs; i++) {
100     comm[i] = new int[numobjs];
101     for (j=0; j<numobjs; j++)  {
102       comm[i][j] = 0;
103     }
104   }
105
106   const int csz = stats->n_comm;
107   for(i=0; i<csz; i++) {
108       LDCommData &cdata = stats->commData[i];
109       //if(cdata.from_proc() || cdata.receiver.get_type() != LD_OBJ_MSG)
110         //continue;
111                         if(!cdata.from_proc() && cdata.receiver.get_type() == LD_OBJ_MSG){
112         int senderID = stats->getHash(cdata.sender);
113         int recverID = stats->getHash(cdata.receiver.get_destObj());
114         CmiAssert(senderID < numobjs);
115         CmiAssert(recverID < numobjs);
116         //comm[senderID][recverID] += (int)(cdata.messages*alpha + cdata.bytes*beta);
117         //comm[recverID][senderID] += (int)(cdata.messages*alpha + cdata.bytes*beta);
118                 //CkPrintf("in compute partitions...%d\n",comm[senderID][recverID]);
119                                 comm[senderID][recverID] += cdata.messages;
120         comm[recverID][senderID] += cdata.messages;
121
122                                 //Use bytes or messages -- do i include messages for objlist too...??
123                         }
124                         else if (cdata.receiver.get_type() == LD_OBJLIST_MSG) {
125                                 //CkPrintf("in objlist..\n");
126         int nobjs;
127         LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
128         int senderID = stats->getHash(cdata.sender);
129         for (j=0; j<nobjs; j++) {
130            int recverID = stats->getHash(objs[j]);
131            if((senderID == -1)||(recverID == -1))
132               if (_lb_args.migObjOnly()) continue;
133               else CkAbort("Error in search\n");
134            comm[senderID][recverID] += cdata.messages;
135            comm[recverID][senderID] += cdata.messages;
136         }
137                         }
138                 }
139
140 // ignore messages sent from an object to itself
141   for (i=0; i<numobjs; i++)
142     comm[i][i] = 0;
143
144   // construct the graph in CSR format
145   int *xadj = new int[numobjs+1];
146   int numedges = 0;
147   for(i=0;i<numobjs;i++) {
148     for(j=0;j<numobjs;j++) {
149       if(comm[i][j] != 0)
150         numedges++;
151     }
152   }
153   int *adjncy = new int[numedges];
154   int *edgewt = new int[numedges];
155         int factor = 10;
156   xadj[0] = 0;
157   int count4all = 0;
158   for (i=0; i<numobjs; i++) {
159     for (j=0; j<numobjs; j++) { 
160       if (comm[i][j] != 0) { 
161         adjncy[count4all] = j;
162         edgewt[count4all++] = comm[i][j]/factor;
163       }
164     }
165     xadj[i+1] = count4all;
166   }
167
168   /*if (_lb_args.debug() >= 2) {
169   CkPrintf("Pre-LDB Statistics step %d\n", step());
170   printStats(count, numobjs, objtime, comm, origmap);
171   }*/
172
173   int wgtflag = 3; // Weights both on vertices and edges
174   int numflag = 0; // C Style numbering
175   int options[5];
176   int edgecut;
177   int sameMapFlag = 1;
178
179         options[0] = 0;
180
181   if (count < 1) {
182     CkPrintf("error: Number of Pe less than 1!");
183   }
184   else if (count == 1) {
185         for(m=0;m<numobjs;m++) 
186                         newmap[i] = origmap[i];
187         sameMapFlag = 1;
188   }
189   else {
190         sameMapFlag = 0;
191                 /*
192         if (count > 8)
193                         METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt, 
194                             &wgtflag, &numflag, &count, options, 
195                             &edgecut, newmap);
196           else
197                         METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt, 
198                                  &wgtflag, &numflag, &count, options, 
199                                  &edgecut, newmap);
200                 */
201    //CkPrintf("before calling metis.\n");
202                 METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt,
203                                  &wgtflag, &numflag, &count, options,
204                                  &edgecut, newmap);
205          //CkPrintf("after calling Metis function.\n");
206   }
207          
208   /*if (_lb_args.debug() >= 2) {
209         CkPrintf("Post-LDB Statistics step %d\n", step());
210         printStats(count, numobjs, objtime, comm, newmap);
211   }*/
212
213   for(i=0;i<numobjs;i++)
214     delete[] comm[i];
215   delete[] comm;
216   delete[] objtime;
217   delete[] xadj;
218   delete[] adjncy;
219   delete[] objwt;
220   delete[] edgewt;
221
222         //CkPrintf("chking wts on each partition...\n");
223
224         /*int avg=0;
225         int *chkwt = new int[count];
226         for(i=0;i<count;i++)
227                 chkwt[i]=0;
228         //totalwt=0;
229         for(i=0;i<numobjs;i++){
230                 chkwt[newmap[i]] += objwt[i];
231                 avg += objwt[i];
232                 
233         }
234         
235         
236         for(i=0;i<count;i++)
237                 CkPrintf("%d -- %d\n",i,chkwt[i]);
238         
239         //CkPrintf("totalwt after:%d avg is %d\n",avg,avg/count);
240 */
241   /*if(!sameMapFlag) {
242     for(i=0; i<numobjs; i++) {
243       if(origmap[i] != newmap[i]) {
244                                 CmiAssert(stats->from_proc[i] == origmap[i]);
245                                 ///Dont assign....wait........
246                                 stats->to_proc[i] =  newmap[i];
247                                 if (_lb_args.debug() >= 3)
248           CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),i,stats->from_proc[i],stats->to_proc[i]);
249       }
250     }
251   }*/
252
253   delete[] origmap;
254
255 }
256
257 int TopoCentLB::findMaxObjs(int *map,int totalobjs,int count)
258 {
259         int *max_num = new int[count];
260         int i;
261         int maxobjs=0;
262         
263         for(i=0;i<count;i++)
264                 max_num[i]=0;
265                 
266         for(i=0;i<totalobjs;i++)
267                 max_num[map[i]]++;
268         
269         for(i=0;i<count;i++)
270                 if(max_num[i]>maxobjs)
271                         maxobjs = max_num[i];
272         
273         delete[] max_num;
274
275         return maxobjs;
276 }
277
278 void TopoCentLB::Heapify(HeapNode *heap, int node, int heapSize)
279 {
280   int left = 2*node+1;
281   int right = 2*node+2;
282   int xchange;
283         
284   //heap[left].load > heap[node].load)
285   if (left < heapSize && (heap[left].key > heap[node].key))
286     xchange = left;
287   else 
288                 xchange = node;
289   //heap[right].load > heap[xchange].load) 
290   if (right < heapSize && (heap[right].key > heap[xchange].key))
291     xchange = right;
292
293   if (xchange != node) {
294     HeapNode tmp;
295     tmp = heap[node];
296     heap[node] = heap[xchange];
297     heap[xchange] = tmp;
298     Heapify(heap,xchange,heapSize);
299   }    
300 }
301
302
303 TopoCentLB::HeapNode TopoCentLB::extractMax(HeapNode *heap,int *heapSize){
304
305         if(*heapSize < 1)
306                 CmiAbort("Empty Heap passed to extractMin!\n");
307
308         HeapNode max = heap[0];
309         heap[0] = heap[*heapSize-1];
310         *heapSize = *heapSize - 1;
311         Heapify(heap,0,*heapSize);
312         return max;
313 }
314
315 void TopoCentLB::BuildHeap(HeapNode *heap,int heapSize){
316         for(int i=heapSize/2; i >= 0; i--)
317                 Heapify(heap,i,heapSize);
318 }
319
320 void TopoCentLB :: increaseKey(HeapNode *heap,int i,double wt){
321         
322         if(wt != -1.00){
323                 #ifdef MAX_EDGE
324                         //CkPrintf("me here...\n");
325                         if(wt>heap[i].key)
326                                 heap[i].key = wt;
327                 #else
328                         heap[i].key += wt;
329                 #endif
330         }
331         int parent = (i-1)/2;
332         
333         if(heap[parent].key >= heap[i].key)
334                 return;
335         else {
336                 HeapNode tmp = heap[parent];
337                 heap[parent] = heap[i];
338                 heap[i] = tmp;
339                 increaseKey(heap,parent,-1.00);
340         }
341         
342 }
343
344 void TopoCentLB :: calculateMST(PartGraph *partgraph,LBTopology *topo,int *proc_mapping,int max_comm_part){
345
346         //Edge **markedEdges;
347         //int *parent;
348         int *inHeap;
349         double *keys;
350         int count = partgraph->n_nodes;
351         int i=0,j=0;
352         
353         //parent = new int[partgraph->n_nodes];
354         inHeap = new int[partgraph->n_nodes];
355         keys = new double[partgraph->n_nodes];
356
357         int **hopCount;
358         int **topoGraph;
359         //int *topoDegree;
360         int *assigned_procs = new int[count];
361
362         hopCount = new int*[count];
363         for(i=0;i<count;i++){
364                 proc_mapping[i]=-1;
365                 assigned_procs[i]=0;
366                 hopCount[i] = new int[count];
367                 for(j=0;j<count;j++)
368                         hopCount[i][j] = 0;
369         }
370
371         int max_neighbors = topo->max_neighbors();
372         
373         //topoDegree = new int[count];
374         topoGraph = new int*[count];
375         for(i=0;i<count;i++){
376                 //topoDegree[i] = 0;
377                 topoGraph[i] = new int[max_neighbors+1];
378                 for(j=0;j<=max_neighbors;j++)
379                         topoGraph[i][j]=0;
380         }
381         
382         int *neigh = new int[max_neighbors];
383         int max_degree=0;
384         int num_neigh=0;
385         for(i=0;i<count;i++){
386                 topo->neighbors(i,neigh,num_neigh);
387                 //topoDegree[i] = num_neigh;
388                 if(num_neigh > max_degree)
389                         max_degree = num_neigh;
390                 for(j=0;j<num_neigh;j++)
391                         topoGraph[i][j]=neigh[j];
392                 topoGraph[i][j]=-1;
393         }
394         //Topology graph constructed
395         delete [] neigh;
396
397         //markedEdges = new Edge*[partmst->n_nodes];
398         /*for(int i=0;i<partmst->n_nodes;i++){
399                 parent[i] = -1;
400                 inHeap[i] = 1;
401         markedEdges[i] = new Edge[partmst->n_nodes];
402     for(int j=0;j<partmst->n_nodes;j++)
403         markedEdges[i][j] = 0;
404   }*/
405         
406         HeapNode *heap = new HeapNode[partgraph->n_nodes];
407         int heapSize = 0;
408
409         for(i=0;i<partgraph->n_nodes;i++){
410                 heap[i].key = 0.00;
411                 heap[i].node = i;
412                 keys[i] = 0.00;
413                 //parent[i] = -1;
414                 inHeap[i] = 1;
415                 
416                 /*if(i==0){ //Take 0 as root
417                         heap[0].key = 1.00;
418                         keys[0] = 0;
419                 }*/
420         }
421
422         //Assign the max comm partition first
423         heap[max_comm_part].key = 1.00;
424         
425         //CkPrintf("in calculate MST..\n");
426         heapSize = partgraph->n_nodes;
427         BuildHeap(heap,heapSize);
428
429         int k=0,comm_cnt=0,m=0,n=0;
430         int *commParts = new int[partgraph->n_nodes];
431         
432         srand(count);
433
434         while(heapSize > 0){
435                 HeapNode max = extractMax(heap,&heapSize);
436                 //CkPrintf("in the extracting loop..\n");
437                 inHeap[max.node] = 0;
438
439                 //CkPrintf("extracted part..%d with weight :%.1f\n",max.node,max.key);
440                 
441                 for(i=0;i<partgraph->n_nodes;i++){
442                         commParts[i]=-1;
443                         PartGraph::Edge wt = partgraph->edges[max.node][i];
444                         if(wt == 0)
445                                 continue;
446                         if(inHeap[i]){
447                                 //parent[i] = max.node;
448                         #ifdef MAX_EDGE
449                                 if(wt>keys[i])
450                                         keys[i]=wt;
451                         #else
452                                 keys[i] += wt;
453                         #endif
454                                 //Update in the heap too
455                                 //First, find where this node is..in the heap
456                                 for(j=0;j<heapSize;j++)
457                                         if(heap[j].node == i)
458                                                 break;
459                                 if(j==heapSize)
460                                         CmiAbort("Some error in heap...\n");
461                                 increaseKey(heap,j,wt);
462                         }
463                 }
464                 
465                 if(max.node==0){ //For now, assign max comm partition to 0th proc in the topology
466                         proc_mapping[max.node]=0;
467                         assigned_procs[0]=1;
468                         continue;
469                 }
470                 
471                 m=0;
472                 n=0;
473                 comm_cnt=0;
474                 for(k=0;k<partgraph->n_nodes;k++){
475                         if(!inHeap[k] && partgraph->edges[k][max.node]){
476                                 commParts[comm_cnt]=k;
477                                 comm_cnt++;
478                         }
479                 }
480                 int pot_proc=-1;
481                 double min_cost=-1;
482                 int min_cost_index=-1;
483                 double cost=0;
484                 int p=0;
485                 int q=0;
486                 int sec_pot_proc=-1;
487                 
488                 for(m=0;m<comm_cnt;m++){
489                         int pe=proc_mapping[commParts[m]];
490                         n=0;    
491                         //cost=0;
492                         //CkPrintf("\nnhs of %d ie. part %d are ",pe,commParts[m]);
493                         while(topoGraph[pe][n]!=-1){
494                                 pot_proc=topoGraph[pe][n];
495                                 //CkPrintf(" %d ",pot_proc);
496                                 if(assigned_procs[pot_proc]){
497                                         n++;
498                                         continue;
499                                 }
500                                 cost=0;
501                                 cost+=partgraph->edges[commParts[m]][max.node];
502                                 for(p=0;p<comm_cnt;p++){
503                                         if(p!=m){
504                                                 if(!hopCount[proc_mapping[commParts[p]]][pot_proc])
505                                                         hopCount[proc_mapping[commParts[p]]][pot_proc]=topo->get_hop_count(proc_mapping[commParts[p]],pot_proc);
506                                                 cost += hopCount[proc_mapping[commParts[p]]][pot_proc]*partgraph->edges[commParts[p]][max.node];
507                                                 //CkPrintf("hop count:%d\n",hopCount[proc_mapping[commParts[p]]][pot_proc]);
508                                         }
509                                 }
510                                 //CkPrintf("-cost=%.1f- ",cost);
511                                 if(min_cost==-1 || cost<min_cost){
512                                         min_cost=cost;
513                                         min_cost_index=pot_proc;
514                                 }
515
516                                 // look at 2-away neighbors too...
517                                 q=0;
518                                 while(topoGraph[pot_proc][q]!=-1){
519                                         sec_pot_proc=topoGraph[pot_proc][q];
520                                         //CkPrintf(" %d ",pot_proc);
521                                         if(assigned_procs[sec_pot_proc]){
522                                                 q++;
523                                                 continue;
524                                         }
525                                         cost=0;
526                                         cost+=2*partgraph->edges[commParts[m]][max.node];
527                                         for(p=0;p<comm_cnt;p++){
528                                                 if(p!=m){
529                                                         if(!hopCount[proc_mapping[commParts[p]]][sec_pot_proc])
530                                                                 hopCount[proc_mapping[commParts[p]]][sec_pot_proc]=topo->get_hop_count(proc_mapping[commParts[p]],sec_pot_proc);
531                                                         cost += hopCount[proc_mapping[commParts[p]]][sec_pot_proc]*partgraph->edges[commParts[p]][max.node];
532                                                         //CkPrintf("hop count:%d\n",hopCount[proc_mapping[commParts[p]]][pot_proc]);
533                                                 }
534                                         }
535                                         //CkPrintf("-cost=%.1f- ",cost);
536                                         if(min_cost==-1 || cost<min_cost){
537                                                 min_cost=cost;
538                                                 min_cost_index=sec_pot_proc;
539                                         }
540                                         q++;
541                                 }
542                                 n++;
543                         }
544                 }
545                 if(min_cost==-1){
546                         min_cost_index=-1;
547                         while(min_cost_index==-1){
548                                 min_cost_index = rand()%count;
549                                 if(assigned_procs[min_cost_index])
550                                         min_cost_index=-1;
551                         }
552                         //CmiAbort("No potential processor found\n");
553                         //CkPrintf("random proc:%d\n",min_cost_index);
554                 }
555                 //CkPrintf("\npart %d assigned to proc %d\n",max.node,min_cost_index);
556                 proc_mapping[max.node]=min_cost_index;
557                 assigned_procs[min_cost_index]=1;
558         }
559
560 }
561
562         //CkPrintf("just before end..\n");
563         //Retain only those edges which are in the MST
564         /*PartGraph::Edge **newEdges;
565         
566         newEdges = new PartGraph::Edge*[partmst->n_nodes];
567         for(int i=0;i<partmst->n_nodes;i++){
568                 newEdges[i] = new PartGraph::Edge[partmst->n_nodes];
569                 for(int j=0;j<partmst->n_nodes;j++)
570                         newEdges[i][j]=0;
571         }
572         
573         for(int i=0;i<partmst->n_nodes;i++){
574                 if(parent[i] != -1){
575                         newEdges[parent[i]][i] = partmst->edges[parent[i]][i];
576                         newEdges[i][parent[i]] = partmst->edges[i][parent[i]];
577                 }
578         }
579
580         //Convert the minimum spanning tree back to maximum spanning tree       
581         for(int i=0;i<partmst->n_nodes;i++)
582                 for(int j=0;j<partmst->n_nodes;j++)
583                         if(newEdges[i][j] != 0)
584                                 partmst->edges[i][j] = max_weight - newEdges[i][j];
585                         else
586                                 partmst->edges[i][j] = 0;
587         */
588
589
590 /*int TopoCentLB :: compare(const void *p,const void *q){
591         return (((PotList*)p)->size - ((PotList*)q)->size);
592 }
593 */
594 void TopoCentLB :: work(CentralLB::LDStats *stats,int count)
595 {
596   int proc;
597   int obj;
598   int dest;
599   int i,j;
600         LDObjData *odata;
601         
602         if (_lb_args.debug() >= 2) {
603     CkPrintf("In TopoCentLB Strategy...\n");
604   }
605         
606   // Make sure that there is at least one available processor.
607   for (proc = 0; proc < count; proc++) {
608     if (stats->procs[proc].available) {
609       break;
610     }
611   }
612         if (proc == count) {
613     CmiAbort ("TopoCentLB: no available processors!");
614   }
615  
616   removeNonMigratable(stats,count);
617
618         int *newmap = new int[stats->n_objs];
619
620         //CkPrintf("before computing partitions...\n");
621         
622         computePartitions(stats,count,newmap);
623         
624         /*CkPrintf("obj-proc mapping\n");
625         for(i=0;i<stats->n_objs;i++)
626                 CkPrintf(" %d,%d ",i,newmap[i]);
627         */
628         int max_objs = findMaxObjs(newmap,stats->n_objs,count);
629         
630         //Check to see if edgecut contains the reqd. no. of edges
631         
632         partgraph = new PartGraph(count,max_objs);
633
634         //Fill up the partition graph - first fill the nodes and then, the edges
635         //CkPrintf("after computing partitions...\n");
636
637
638         for(i=0;i<stats->n_objs;i++)
639         {
640                 PartGraph::Node* n = &partgraph->nodes[newmap[i]];
641                 //CkPrintf("num:%d\n",n->num_objs);
642                 n->obj_list[n->num_objs]=i;
643                 n->num_objs++;
644         }
645
646         int **bytesComm;
647         bytesComm = new int*[count];
648         for(i=0;i<count;i++){
649                 bytesComm[i] = new int[count];
650                 for(j=0;j<count;j++)
651                         bytesComm[i][j]=0;
652         }
653
654         //CkPrintf("num comm:%d\n",stats->n_comm);
655         int *addedComm=new int[count];
656
657         int max_comm_part=-1;
658         double max_comm=0;
659         
660         for(i=0;i<stats->n_comm;i++)
661         {
662                 //DO I consider other comm too....i.e. to or from a processor
663
664                 LDCommData &cdata = stats->commData[i];
665                 //if(cdata.from_proc() || cdata.receiver.get_type() != LD_OBJ_MSG)
666         //continue;
667                 if(!cdata.from_proc() && cdata.receiver.get_type() == LD_OBJ_MSG){
668         int senderID = stats->getHash(cdata.sender);
669         int recverID = stats->getHash(cdata.receiver.get_destObj());
670                         CmiAssert(senderID < stats->n_objs);
671                 CmiAssert(recverID < stats->n_objs);
672                 
673                         if(newmap[senderID]==newmap[recverID])
674                                 continue;
675         
676                         //CkPrintf("from %d to %d\n",newmap[senderID],newmap[recverID]);
677                         if(partgraph->edges[newmap[senderID]][newmap[recverID]] == 0){
678                                 partgraph->nodes[newmap[senderID]].degree++;
679                                 partgraph->nodes[newmap[recverID]].degree++;
680                         }
681                 
682                         partgraph->edges[newmap[senderID]][newmap[recverID]] += cdata.bytes;
683                         partgraph->edges[newmap[recverID]][newmap[senderID]] += cdata.bytes;
684                         
685                         partgraph->nodes[newmap[senderID]].comm += cdata.bytes;
686                         partgraph->nodes[newmap[recverID]].comm += cdata.bytes;
687                         
688                         if(partgraph->nodes[newmap[senderID]].comm > max_comm){
689                                 max_comm = partgraph->nodes[newmap[senderID]].comm;
690                                 max_comm_part = newmap[senderID];
691                         }
692                         if(partgraph->nodes[newmap[recverID]].comm > max_comm){
693                                 max_comm = partgraph->nodes[newmap[recverID]].comm;
694                                 max_comm_part = newmap[recverID];
695                         }
696
697                         //partgraph->edges[newmap[recverID]][newmap[senderID]] += 1000*(cdata.messages*alpha + cdata.bytes*beta);
698                         //bytesComm[newmap[senderID]][newmap[recverID]] += cdata.bytes;
699                         //bytesComm[newmap[recverID]][newmap[senderID]] += cdata.bytes;
700
701                 }
702                 else if(cdata.receiver.get_type() == LD_OBJLIST_MSG) {
703         //CkPrintf("\nin obj list cal...\n\n");
704                         int nobjs;
705         LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
706       int senderID = stats->getHash(cdata.sender);
707       //addedComm = new int[count];
708                         for(j=0;j<count;j++)
709                                 addedComm[j]=0;
710                         //CkPrintf("in obj list loop...\n");
711                         for (j=0; j<nobjs; j++) {
712         int recverID = stats->getHash(objs[j]);
713         if((senderID == -1)||(recverID == -1))
714                 if (_lb_args.migObjOnly()) continue;
715                 else CkAbort("Error in search\n");
716                                         
717                                 if(newmap[senderID]==newmap[recverID])
718                                         continue;
719         
720                                 //CkPrintf("from %d to %d\n",newmap[senderID],newmap[recverID]);
721                                 if(partgraph->edges[newmap[senderID]][newmap[recverID]] == 0){
722                                         //CkPrintf("sender:%d recver:%d\n",newmap[senderID],newmap[recverID]);
723                                         partgraph->nodes[newmap[senderID]].degree++;
724                                         partgraph->nodes[newmap[recverID]].degree++;
725                                 }
726                 
727                                 if(!addedComm[newmap[recverID]]){
728                                         partgraph->edges[newmap[senderID]][newmap[recverID]] += cdata.bytes;
729                                         partgraph->edges[newmap[recverID]][newmap[senderID]] += cdata.bytes;
730         
731                                         partgraph->nodes[newmap[senderID]].comm += cdata.bytes;
732                                         partgraph->nodes[newmap[recverID]].comm += cdata.bytes;
733
734                                         if(partgraph->nodes[newmap[senderID]].comm > max_comm){
735                                                 max_comm = partgraph->nodes[newmap[senderID]].comm;
736                                                 max_comm_part = newmap[senderID];
737                                         }
738                                         if(partgraph->nodes[newmap[recverID]].comm > max_comm){
739                                                 max_comm = partgraph->nodes[newmap[recverID]].comm;
740                                                 max_comm_part = newmap[recverID];
741                                         }
742
743                                         //bytesComm[newmap[senderID]][newmap[recverID]] += cdata.bytes;
744                                         //bytesComm[newmap[recverID]][newmap[senderID]] += cdata.bytes;
745                                         addedComm[newmap[recverID]]=1;
746                                 }
747       }
748                         //CkPrintf("outside loop..\n");
749         //delete [] addedComm;
750                 }
751
752         }
753         
754         int *proc_mapping = new int[count];
755         
756         delete [] addedComm;
757                 
758         LBtopoFn topofn;
759         int max_neighbors=0;
760         int *neigh;
761         int num_neigh=0;
762         
763         topofn = LBTopoLookup(_lbtopo);
764   if (topofn == NULL) {
765         char str[1024];
766     CmiPrintf("TopoCentLB> Fatal error: Unknown topology: %s. Choose from:\n", _lbtopo);
767     printoutTopo();
768     sprintf(str, "TopoCentLB> Fatal error: Unknown topology: %s", _lbtopo);
769     CmiAbort(str);
770   }
771   
772         topo = topofn(count);
773         
774         /*max_neighbors = topo->max_neighbors();
775         
776         topoDegree = new int[count];
777         for(i=0;i<count;i++){
778                 topoDegree[i] = 0;
779                 topoGraph[i] = new int[count];
780                 for(j=0;j<count;j++)
781                         topoGraph[i][j]=0;
782         }
783         
784         neigh = new int[max_neighbors];
785         int max_degree=0;
786         for(i=0;i<count;i++){
787                 topo->neighbors(i,neigh,num_neigh);
788                 topoDegree[i] = num_neigh;
789                 if(num_neigh > max_degree)
790                         max_degree = num_neigh;
791                 for(j=0;j<num_neigh;j++)
792                         topoGraph[i][neigh[j]]=1;
793         }
794         //Topology graph constructed
795         delete [] neigh;
796 */
797
798         calculateMST(partgraph,topo,proc_mapping,max_comm_part);
799         CkPrintf("after calculating MST...\n");
800         //Returned partition graph is a Maximum Spanning Tree -- converted in above function itself
801
802         /*for(i=0;i<count;i++)
803                 for(j=0;j<count;j++)
804                         if(partmst->edges[i][j]==0)
805                                 bytesComm[i][j]=0;*/
806         
807         //Construct the Topology Graph
808         
809         /*int max_part_degree = 0;
810         for(i=0;i<count;i++)
811                 if(partmst->nodes[i].degree > max_part_degree)
812                         max_part_degree = partmst->nodes[i].degree;
813         */
814         
815         /*CkPrintf("part,proc mapping..\n");
816         for(i=0;i<count;i++)
817                 CkPrintf("%d,%d len:%d\n",i,proc_mapping[i],(partgraph->nodes[i]).num_objs);
818                 */
819         int pe;
820         PartGraph::Node* n;
821         for(i=0;i<count;i++){
822                 pe = proc_mapping[i];
823                 //pe=i;
824                 n = &partgraph->nodes[i];
825                 //CkPrintf("here..%d,first object:%d\n",n->num_objs,n->obj_list[0]);
826                 for(j=0;j<n->num_objs;j++){
827                         stats->to_proc[n->obj_list[j]] = pe;
828                         //if(pe==507)
829                                 //CkPrintf(" %d,%d ",n->obj_list[j],pe);
830                         if (_lb_args.debug()>1) 
831         CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),n->obj_list[j],stats->from_proc[n->obj_list[j]],pe);
832                 }
833         }
834 }
835 #include "TopoCentLB.def.h"