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