Merge last phase of static array optimization branch
[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(topo) delete topo;
55 }
56
57 /*This routine partitions the task graph minimizing the communication and balancing the object load on all partitions*/
58 /*It uses METIS library to accomplish that*/
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   //Prepare compute loads for METIS library
78   for (i=0; i<stats->n_objs; i++) {
79     LDObjData &odata = stats->objData[i];
80     if (!odata.migratable) 
81       CmiAbort("MetisLB doesnot dupport nonmigratable object.\n");
82     int frompe = stats->from_proc[i];
83     origmap[i] = frompe;
84     objtime[i] = odata.wallTime*stats->procs[frompe].pe_speed;
85     handles[i] = odata.handle;
86   }
87
88   // to convert the weights on vertices to integers
89   double max_objtime = objtime[0];
90   for(i=0; i<numobjs; i++) {
91     if(max_objtime < objtime[i])
92       max_objtime = objtime[i];
93   }
94         int maxobj=0;
95         int totalwt=0;
96   double ratio = 1000.0/max_objtime;
97   for(i=0; i<numobjs; i++) {
98       objwt[i] = (int)(objtime[i]*ratio);
99                         if(maxobj<objwt[i])
100                                 maxobj=objwt[i];
101                         totalwt+=objwt[i];
102   }
103         
104   int **comm = new int*[numobjs];
105   for (i=0; i<numobjs; i++) {
106     comm[i] = new int[numobjs];
107     for (j=0; j<numobjs; j++)  {
108       comm[i][j] = 0;
109     }
110   }
111
112   //Prepare communication for METIS library
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] += cdata.messages;
124         comm[recverID][senderID] += cdata.messages;
125                                 //Use bytes or messages -- do i include messages for objlist too...??
126                         }
127                         else if (cdata.receiver.get_type() == LD_OBJLIST_MSG) {
128                                 //CkPrintf("in objlist..\n");
129         int nobjs;
130         LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
131         int senderID = stats->getHash(cdata.sender);
132         for (j=0; j<nobjs; j++) {
133            int recverID = stats->getHash(objs[j]);
134            if((senderID == -1)||(recverID == -1))
135               if (_lb_args.migObjOnly()) continue;
136               else CkAbort("Error in search\n");
137            comm[senderID][recverID] += cdata.messages;
138            comm[recverID][senderID] += cdata.messages;
139         }
140                         }
141                 }
142
143 // ignore messages sent from an object to itself
144   for (i=0; i<numobjs; i++)
145     comm[i][i] = 0;
146
147   // construct the graph in CSR format
148   int *xadj = new int[numobjs+1];
149   int numedges = 0;
150   for(i=0;i<numobjs;i++) {
151     for(j=0;j<numobjs;j++) {
152       if(comm[i][j] != 0)
153         numedges++;
154     }
155   }
156   int *adjncy = new int[numedges];
157   int *edgewt = new int[numedges];
158         int factor = 10;
159   xadj[0] = 0;
160   int count4all = 0;
161   for (i=0; i<numobjs; i++) {
162     for (j=0; j<numobjs; j++) { 
163       if (comm[i][j] != 0) { 
164         adjncy[count4all] = j;
165         edgewt[count4all++] = comm[i][j]/factor;
166       }
167     }
168     xadj[i+1] = count4all;
169   }
170
171   //Call METIS routine
172   int wgtflag = 3; // Weights both on vertices and edges
173   int numflag = 0; // C Style numbering
174   int options[5];
175   int edgecut;
176   int sameMapFlag = 1;
177
178         options[0] = 0;
179
180   if (count < 1) {
181     CkPrintf("error: Number of Pe less than 1!");
182   }
183   else if (count == 1) {
184         for(m=0;m<numobjs;m++) 
185                         newmap[i] = origmap[i];
186         sameMapFlag = 1;
187   }
188   else {
189         sameMapFlag = 0;
190                 /*
191         if (count > 8)
192                         METIS_PartGraphKway(&numobjs, xadj, adjncy, objwt, edgewt, 
193                             &wgtflag, &numflag, &count, options, 
194                             &edgecut, newmap);
195           else
196                         METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt, 
197                                  &wgtflag, &numflag, &count, options, 
198                                  &edgecut, newmap);
199                 */
200                 METIS_PartGraphRecursive(&numobjs, xadj, adjncy, objwt, edgewt,
201                                  &wgtflag, &numflag, &count, options,
202                                  &edgecut, newmap);
203   }
204          
205  
206   //Debugging code: Checking load on each partition
207   if(_lb_args.debug() >=2){
208           int total=0;
209           int *chkwt = new int[count];
210           for(i=0;i<count;i++)
211                   chkwt[i]=0;
212           for(i=0;i<numobjs;i++){
213                 chkwt[newmap[i]] += objwt[i];
214                   total += objwt[i];
215           }
216           for(i=0;i<count;i++)
217                   CkPrintf("%d -- %d\n",i,chkwt[i]);
218           CkPrintf("Totalwt of all partitions after call to METIS:%d, Avg is %d\n",total,total/count);
219   }
220
221   //Clean up all the variables allocated in this routine
222   for(i=0;i<numobjs;i++)
223     delete[] comm[i];
224   delete[] comm;
225   delete[] objtime;
226   delete[] xadj;
227   delete[] adjncy;
228   delete[] objwt;
229   delete[] edgewt;
230         delete[] handles;
231   delete[] origmap;
232
233 }
234
235 int TopoCentLB::findMaxObjs(int *map,int totalobjs,int count)
236 {
237         int *max_num = new int[count];
238         int i;
239         int maxobjs=0;
240         
241         for(i=0;i<count;i++)
242                 max_num[i]=0;
243                 
244         for(i=0;i<totalobjs;i++)
245                 max_num[map[i]]++;
246         
247         for(i=0;i<count;i++)
248                 if(max_num[i]>maxobjs)
249                         maxobjs = max_num[i];
250         
251         delete[] max_num;
252
253         return maxobjs;
254 }
255
256 void TopoCentLB::Heapify(HeapNode *heap, int node, int heapSize)
257 {
258   int left = 2*node+1;
259   int right = 2*node+2;
260   int xchange;
261         
262   if (left < heapSize && (heap[left].key > heap[node].key))
263     xchange = left;
264   else 
265                 xchange = node;
266   
267   if (right < heapSize && (heap[right].key > heap[xchange].key))
268     xchange = right;
269
270   if (xchange != node) {
271     HeapNode tmp;
272     tmp = heap[node];
273     heap[node] = heap[xchange];
274     heap[xchange] = tmp;
275                 heapMapping[heap[node].node]=node;
276                 heapMapping[heap[xchange].node]=xchange;
277     Heapify(heap,xchange,heapSize);
278   }    
279 }
280
281
282 TopoCentLB::HeapNode TopoCentLB::extractMax(HeapNode *heap,int *heapSize){
283
284         if(*heapSize < 1)
285                 CmiAbort("Empty Heap passed to extractMin!\n");
286
287         HeapNode max = heap[0];
288         heap[0] = heap[*heapSize-1];
289         heapMapping[heap[0].node]=0;
290         *heapSize = *heapSize - 1;
291         Heapify(heap,0,*heapSize);
292         return max;
293 }
294
295 void TopoCentLB::BuildHeap(HeapNode *heap,int heapSize){
296         for(int i=heapSize/2; i >= 0; i--)
297                 Heapify(heap,i,heapSize);
298 }
299
300 void TopoCentLB :: increaseKey(HeapNode *heap,int i,double wt){
301         int val;
302         if(wt != -1.00){
303                 #ifdef MAX_EDGE
304                         if(wt>heap[i].key)
305                                 heap[i].key = wt;
306                 #else
307                         heap[i].key += wt;
308                 #endif
309         }
310         int parent = (i-1)/2;
311         
312         if(heap[parent].key >= heap[i].key)
313                 return;
314         else {
315                 HeapNode tmp = heap[parent];
316                 heap[parent] = heap[i];
317                 heap[i] = tmp;
318                 heapMapping[heap[parent].node]=parent;
319                 heapMapping[heap[i].node]=i;
320                 increaseKey(heap,parent,-1.00);
321         }
322 }
323
324 /*This routine implements the algorithm used to produce the partition-processor mapping*/
325 /*The algorithm uses an idea similar to the standard MST algorithm*/
326 void TopoCentLB :: calculateMST(PartGraph *partgraph,LBTopology *topo,int *proc_mapping,int max_comm_part){
327
328         int *inHeap;
329         double *keys;
330         int count = partgraph->n_nodes;
331         int i=0,j=0;
332
333   //Arrays needed for keeping information
334         inHeap = new int[partgraph->n_nodes];
335         keys = new double[partgraph->n_nodes];
336
337         int *assigned_procs = new int[count];
338
339         hopCount = new double*[count];
340         for(i=0;i<count;i++){
341                 proc_mapping[i]=-1;
342                 assigned_procs[i]=0;
343                 hopCount[i] = new double[count];
344                 for(j=0;j<count;j++)
345                         hopCount[i][j] = 0;
346         }
347
348   //Call a topology routine to fill up hopCount
349         topo->get_pairwise_hop_count(hopCount);
350         
351   int max_neighbors = topo->max_neighbors();
352         
353         HeapNode *heap = new HeapNode[partgraph->n_nodes];
354         heapMapping = new int[partgraph->n_nodes];
355         
356         int heapSize = 0;
357
358         for(i=0;i<partgraph->n_nodes;i++){
359                 heap[i].key = 0.00;
360                 heap[i].node = i;
361                 keys[i] = 0.00;
362                 inHeap[i] = 1;
363                 heapMapping[i]=i;
364         }
365
366         //Assign the max comm partition first
367         heap[max_comm_part].key = 1.00;
368         
369         heapSize = partgraph->n_nodes;
370         BuildHeap(heap,heapSize);
371
372         int k=0,comm_cnt=0,m=0,n=0;
373         int *commParts = new int[partgraph->n_nodes];
374         
375         //srand(count);
376
377         while(heapSize > 0){
378
379     /****Phase1: Extracting appropriate partition from heap****/
380
381                 HeapNode max = extractMax(heap,&heapSize);
382                 inHeap[max.node] = 0;
383
384                 for(i=0;i<partgraph->n_nodes;i++){
385                         commParts[i]=-1;
386                         PartGraph::Edge wt = partgraph->edges[max.node][i];
387                         if(wt == 0)
388                                 continue;
389                         if(inHeap[i]){
390                         #ifdef MAX_EDGE
391                                 if(wt>keys[i])
392                                         keys[i]=wt;
393                         #else
394                                 keys[i] += wt;
395                         #endif
396         /*This part has been COMMENTED out for optimizing the code: we handle the updation using heapMapping*/
397         /*array instead of searching for node in the heap everytime*/
398
399                                 //Update in the heap too
400                                 //First, find where this node is..in the heap
401                                 /*for(j=0;j<heapSize;j++)
402                                         if(heap[j].node == i)
403                                                 break;
404                                 if(j==heapSize)
405                                         CmiAbort("Some error in heap...\n");*/
406                                 increaseKey(heap,heapMapping[i],wt);
407                         }
408                 }
409                  
410     /*Phase2: ASSIGNING partition to processor*/
411                 
412     //Special case
413                 if(heapSize == partgraph->n_nodes-1){ //Assign max comm partition to 0th proc in the topology
414                         proc_mapping[max.node]=0;
415                         assigned_procs[0]=1;
416                         continue;
417                 }
418                 
419                 m=0;
420                 n=0;
421                 comm_cnt=0;
422
423                 int pot_proc=-1;
424                 double min_cost=-1;
425                 int min_cost_index=-1;
426                 double cost=0;
427                 int p=0;
428                 //int q=0;
429
430                 for(k=0;k<partgraph->n_nodes;k++){
431                         if(!inHeap[k] && partgraph->edges[k][max.node]){
432                                 commParts[comm_cnt]=k;
433                                 comm_cnt++;
434                         }
435                 }
436
437     //Optimized the loop by commenting out the get_hop_count code and getting all the hop counts initially
438                 for(m=0;m<count;m++){
439                         if(!assigned_procs[m]){
440                                 cost=0;
441                                 for(p=0;p<comm_cnt;p++){
442                                         //if(!hopCount[proc_mapping[commParts[p]]][m])
443                                                 //hopCount[proc_mapping[commParts[p]]][m]=topo->get_hop_count(proc_mapping[commParts[p]],m);
444                                         cost += hopCount[proc_mapping[commParts[p]]][m]*partgraph->edges[commParts[p]][max.node];
445                                 }
446                                 if(min_cost==-1 || cost<min_cost){
447                                         min_cost=cost;
448                                         min_cost_index=m;
449                                 }
450                         }
451                 }
452
453                 proc_mapping[max.node]=min_cost_index;
454                 assigned_procs[min_cost_index]=1;
455         }
456
457         //clear up memory
458         delete[] inHeap;
459         delete[] keys;
460         delete[] assigned_procs;
461         delete[] heap;
462         delete[] commParts;
463 }
464
465
466 void TopoCentLB :: work(LDStats *stats)
467 {
468   int proc;
469   int obj;
470   int dest;
471   int i,j;
472   LDObjData *odata;
473   int n_pes = stats->nprocs();
474         
475   if (_lb_args.debug() >= 2) {
476     CkPrintf("In TopoCentLB Strategy...\n");
477   }
478   
479   // Make sure that there is at least one available processor.
480   for (proc = 0; proc < n_pes; proc++) {
481     if (stats->procs[proc].available) {
482       break;
483     }
484   }
485
486   if (proc == n_pes) {
487     CmiAbort ("TopoCentLB: no available processors!");
488   }
489
490   
491   removeNonMigratable(stats, n_pes);
492   int *newmap = new int[stats->n_objs];
493
494
495   if(make_mapping)
496     computePartitions(stats, n_pes, newmap);
497   else {
498     //mapping taken from previous algo
499     for(i=0;i<stats->n_objs;i++) {
500       newmap[i]=stats->from_proc[i];
501     }
502   }
503
504   //Debugging Code
505   if(_lb_args.debug() >=2){
506           CkPrintf("Map obtained from partitioning:\n");
507     for(i=0;i<stats->n_objs;i++)
508                   CkPrintf(" %d,%d ",i,newmap[i]);
509   }
510
511         int max_objs = findMaxObjs(newmap,stats->n_objs, n_pes);
512         
513         partgraph = new PartGraph(n_pes, max_objs);
514
515         //Fill up the partition graph - first fill the nodes and then, the edges
516
517         for(i=0;i<stats->n_objs;i++)
518         {
519                 PartGraph::Node* n = &partgraph->nodes[newmap[i]];
520                 n->obj_list[n->num_objs]=i;
521                 n->num_objs++;
522         }
523
524         int *addedComm=new int[n_pes];
525   
526   stats->makeCommHash();
527   
528         int max_comm_part=-1;
529         
530         double max_comm=0;
531
532   //Try putting random amount of communication on the partition graph edges to see if things work fine
533   //This also checks the running time of the algorithm since number of edges is high than in a practical scenario
534         #ifdef RAND_COMM
535         for(i = 0; i < n_pes; i++) {
536                 for(j = i+1; j < n_pes; j++) {
537                         int val;
538                         if(rand()%5==0)
539                                 val=0;
540                         else
541                                 val= rand()%1000;
542                                 
543                         partgraph->edges[i][j] = val;
544                         partgraph->edges[j][i] = val;
545                         
546                         partgraph->nodes[i].comm += val;
547                         partgraph->nodes[j].comm += val;
548                         
549                         if(partgraph->nodes[i].comm > max_comm){
550                                 max_comm = partgraph->nodes[i].comm;
551                                 max_comm_part = i;
552                         }
553                         if(partgraph->nodes[j].comm > max_comm){
554                                 max_comm = partgraph->nodes[j].comm;
555                                 max_comm_part = j;
556                         }
557                 }
558         }
559         #else
560   //Adding communication to the partition graph edges
561         for(i=0;i<stats->n_comm;i++)
562         {
563                 //DO I consider other comm too....i.e. to or from a processor
564                 LDCommData &cdata = stats->commData[i];
565                 if(!cdata.from_proc() && cdata.receiver.get_type() == LD_OBJ_MSG){
566         int senderID = stats->getHash(cdata.sender);
567         int recverID = stats->getHash(cdata.receiver.get_destObj());
568                         CmiAssert(senderID < stats->n_objs);
569                 CmiAssert(recverID < stats->n_objs);
570                 
571                         if(newmap[senderID]==newmap[recverID])
572                                 continue;
573         
574                         if(partgraph->edges[newmap[senderID]][newmap[recverID]] == 0){
575                                 partgraph->nodes[newmap[senderID]].degree++;
576                                 partgraph->nodes[newmap[recverID]].degree++;
577                         }
578                 
579                         partgraph->edges[newmap[senderID]][newmap[recverID]] += cdata.bytes;
580                         partgraph->edges[newmap[recverID]][newmap[senderID]] += cdata.bytes;
581                         
582                         partgraph->nodes[newmap[senderID]].comm += cdata.bytes;
583                         partgraph->nodes[newmap[recverID]].comm += cdata.bytes;
584
585       //Keeping track of maximum communiacting partition
586                         if(partgraph->nodes[newmap[senderID]].comm > max_comm){
587                                 max_comm = partgraph->nodes[newmap[senderID]].comm;
588                                 max_comm_part = newmap[senderID];
589                         }
590                         if(partgraph->nodes[newmap[recverID]].comm > max_comm){
591                                 max_comm = partgraph->nodes[newmap[recverID]].comm;
592                                 max_comm_part = newmap[recverID];
593                         }
594                 }
595                 else if(cdata.receiver.get_type() == LD_OBJLIST_MSG) {
596                         int nobjs;
597         LDObjKey *objs = cdata.receiver.get_destObjs(nobjs);
598       int senderID = stats->getHash(cdata.sender);
599                         for(j = 0; j < n_pes; j++)
600                                 addedComm[j]=0;
601                         for (j=0; j<nobjs; j++) {
602         int recverID = stats->getHash(objs[j]);
603         if((senderID == -1)||(recverID == -1))
604                 if (_lb_args.migObjOnly()) continue;
605                 else CkAbort("Error in search\n");
606                                         
607                                 if(newmap[senderID]==newmap[recverID])
608                                         continue;
609         
610                                 if(partgraph->edges[newmap[senderID]][newmap[recverID]] == 0){
611                                         partgraph->nodes[newmap[senderID]].degree++;
612                                         partgraph->nodes[newmap[recverID]].degree++;
613                                 }
614
615         //Communication added only once for a message sent to many objects on a single processor
616                                 if(!addedComm[newmap[recverID]]){
617                                         partgraph->edges[newmap[senderID]][newmap[recverID]] += cdata.bytes;
618                                         partgraph->edges[newmap[recverID]][newmap[senderID]] += cdata.bytes;
619         
620                                         partgraph->nodes[newmap[senderID]].comm += cdata.bytes;
621                                         partgraph->nodes[newmap[recverID]].comm += cdata.bytes;
622
623                                         if(partgraph->nodes[newmap[senderID]].comm > max_comm){
624                                                 max_comm = partgraph->nodes[newmap[senderID]].comm;
625                                                 max_comm_part = newmap[senderID];
626                                         }
627                                         if(partgraph->nodes[newmap[recverID]].comm > max_comm){
628                                                 max_comm = partgraph->nodes[newmap[recverID]].comm;
629                                                 max_comm_part = newmap[recverID];
630                                         }
631                                         //bytesComm[newmap[senderID]][newmap[recverID]] += cdata.bytes;
632                                         //bytesComm[newmap[recverID]][newmap[senderID]] += cdata.bytes;
633                                         addedComm[newmap[recverID]]=1;
634                                 }
635       }
636                 }
637
638         }
639         #endif
640         
641         int *proc_mapping = new int[n_pes];
642         
643         delete [] addedComm;
644                 
645         LBtopoFn topofn;
646         int max_neighbors=0;
647         int *neigh;
648         int num_neigh=0;
649
650   //Parsing the command line input for getting the processor topology
651         char *lbcopy = strdup(_lbtopo);
652   char *ptr = strchr(lbcopy, ':');
653   if (ptr!=NULL)
654     ptr = strtok(lbcopy, ":");
655         else
656                 ptr=lbcopy;
657
658         topofn = LBTopoLookup(ptr);
659   if (topofn == NULL) {
660     char str[1024];
661     CmiPrintf("TopoCentLB> Fatal error: Unknown topology: %s. Choose from:\n", ptr);
662     printoutTopo();
663     sprintf(str, "TopoCentLB> Fatal error: Unknown topology: %s", ptr);
664     CmiAbort(str);
665   }
666   
667         topo = topofn(n_pes);
668
669   //Call the core routine to produce the partition processor mapping
670         calculateMST(partgraph,topo,proc_mapping,max_comm_part);
671         //Returned partition graph is a Maximum Spanning Tree -- converted in above function itself
672
673   //Debugging code: Result of mapping partition graph onto processor graph
674         if (_lb_args.debug()>1) {
675           CkPrintf("Resultant mapping..(partition,processor)\n");
676           for(i = 0; i < n_pes; i++)
677                   CkPrintf("%d,%d\n",i,proc_mapping[i]);
678   }
679
680   //Store the result in the load balancing database
681         int pe;
682         PartGraph::Node* n;
683         for(i = 0; i < n_pes; i++){
684                 pe = proc_mapping[i];
685                 n = &partgraph->nodes[i];
686                 for(j=0;j<n->num_objs;j++){
687                         stats->to_proc[n->obj_list[j]] = pe;
688                         if (_lb_args.debug()>1) 
689         CkPrintf("[%d] Obj %d migrating from %d to %d\n", CkMyPe(),n->obj_list[j],stats->from_proc[n->obj_list[j]],pe);
690                 }
691         }
692
693         delete[] newmap;
694         delete[] proc_mapping;
695         //Delete hopCount
696         for(i = 0; i < n_pes; i++)
697                 delete[] hopCount[i];
698
699         delete[] hopCount;
700         delete[] heapMapping;
701         
702   delete partgraph;
703 }
704
705 #include "TopoCentLB.def.h"