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