d3197837cecac1e7d48df3fe67af7b2c72babb74
[charm.git] / src / ck-ldb / GridMetisLB.C
1 /**************************************************************************
2 ** Greg Koenig (koenig@uiuc.edu)
3 ** April 1, 2006
4 **
5 ** This is GridMetisLB.C
6 **
7 */
8
9 #include "GridMetisLB.decl.h"
10
11 #include "GridMetisLB.h"
12 #include "manager.h"
13
14 CreateLBFunc_Def (GridMetisLB, "Grid load balancer that uses Metis to optimize communication graph");
15
16
17
18 /**************************************************************************
19 **
20 */
21 GridMetisLB::GridMetisLB (const CkLBOptions &opt) : CentralLB (opt)
22 {
23   lbname = (char *) "GridMetisLB";
24
25   if (CkMyPe() == 0) {
26     CkPrintf ("[%d] GridMetisLB created.\n", CkMyPe());
27   }
28
29   manager_init ();
30 }
31
32
33
34 /**************************************************************************
35 **
36 */
37 GridMetisLB::GridMetisLB (CkMigrateMessage *msg) : CentralLB (msg)
38 {
39   lbname = (char *) "GridMetisLB";
40
41   manager_init ();
42 }
43
44
45
46 /**************************************************************************
47 ** The Charm++ load balancing framework invokes this method to determine
48 ** whether load balancing can be performed at a specified time.
49 */
50 CmiBool GridMetisLB::QueryBalanceNow (int step)
51 {
52   if (_lb_args.debug() > 2) {
53     CkPrintf ("[%d] GridMetisLB is balancing on step %d.\n", CkMyPe(), step);
54   }
55
56   return (CmiTrue);
57 }
58
59
60
61 /**************************************************************************
62 ** The vmi-linux machine layer incorporates the idea that PEs are located
63 ** within identifiable clusters.  This information can be supplied by the
64 ** user or can be probed automatically by the machine layer.  The exposed
65 ** API call CmiGetCluster() returns the integer cluster number for a
66 ** specified PE or -1 if the information is unknown.
67 **
68 ** For machine layers other than vmi-linux, simply return the constant 0.
69 ** GridCommLB will assume a single-cluster computation and will balance
70 ** on the scaled processor load and number of LAN messages.
71 */
72 int GridMetisLB::Get_Cluster (int pe)
73 {
74 #if CONVERSE_VERSION_VMI
75   return (CmiGetCluster (pe));
76 #else
77   return (0);
78 #endif
79 }
80
81
82
83 /**************************************************************************
84 **
85 */
86 void GridMetisLB::Initialize_PE_Data (CentralLB::LDStats *stats)
87 {
88   int min_speed;
89   int i;
90
91
92   PE_Data = new PE_Data_T[Num_PEs];
93
94   min_speed = MAXINT;
95   for (i = 0; i < Num_PEs; i++) {
96     (&PE_Data[i])->available      = stats->procs[i].available;
97     (&PE_Data[i])->cluster        = Get_Cluster (i);
98     (&PE_Data[i])->num_objs       = 0;
99     (&PE_Data[i])->relative_speed = 0.0;
100     (&PE_Data[i])->scaled_load    = 0.0;
101
102     if (stats->procs[i].pe_speed < min_speed) {
103       min_speed = stats->procs[i].pe_speed;
104     }
105   }
106
107   // Compute the relative PE speeds.
108   // Also add background CPU time to each PE's scaled load.
109   for (i = 0; i < Num_PEs; i++) {
110     (&PE_Data[i])->relative_speed = (double) (stats->procs[i].pe_speed / min_speed);
111     (&PE_Data[i])->scaled_load += stats->procs[i].bg_cputime;
112   }
113 }
114
115
116
117 /**************************************************************************
118 **
119 */
120 int GridMetisLB::Available_PE_Count ()
121 {
122   int available_pe_count;
123   int i;
124
125
126   available_pe_count = 0;
127   for (i = 0; i < Num_PEs; i++) {
128     if ((&PE_Data[i])->available) {
129       available_pe_count += 1;
130     }
131   }
132   return (available_pe_count);
133 }
134
135
136
137 /**************************************************************************
138 **
139 */
140 int GridMetisLB::Compute_Number_Of_Clusters ()
141 {
142   int max_cluster;
143   int i;
144
145
146   max_cluster = 0;
147   for (i = 0; i < Num_PEs; i++) {
148     if ((&PE_Data[i])->cluster < 0) {
149       return (-1);
150     }
151
152     if ((&PE_Data[i])->cluster > max_cluster) {
153       max_cluster = (&PE_Data[i])->cluster;
154     }
155   }
156   return (max_cluster + 1);
157 }
158
159
160
161 /**************************************************************************
162 **
163 */
164 void GridMetisLB::Initialize_Object_Data (CentralLB::LDStats *stats)
165 {
166   int i;
167
168
169   Object_Data = new Object_Data_T[Num_Objects];
170
171   for (i = 0; i < Num_Objects; i++) {
172     (&Object_Data[i])->migratable   = (&stats->objData[i])->migratable;
173     (&Object_Data[i])->cluster      = Get_Cluster (stats->from_proc[i]);
174     (&Object_Data[i])->from_pe      = stats->from_proc[i];
175     (&Object_Data[i])->load         = (&stats->objData[i])->wallTime;
176
177     if ((&Object_Data[i])->migratable) {
178       (&Object_Data[i])->to_pe = -1;
179     } else {
180       (&Object_Data[i])->to_pe = (&Object_Data[i])->from_pe;
181       (&PE_Data[(&Object_Data[i])->to_pe])->scaled_load += (&Object_Data[i])->load;
182       if (_lb_args.debug() > 1) {
183         CkPrintf ("[%d] GridMetisLB identifies object %d as non-migratable.\n", CkMyPe(), i);
184       }
185     }
186   }
187 }
188
189
190
191 /**************************************************************************
192 **
193 */
194 void GridMetisLB::Initialize_Cluster_Data ()
195 {
196   int cluster;
197   double min_total_cpu_power;
198   int i;
199
200
201   Cluster_Data = new Cluster_Data_T[Num_Clusters];
202
203   for (i = 0; i < Num_Clusters; i++) {
204     (&Cluster_Data[i])->num_pes = 0;
205     (&Cluster_Data[i])->total_cpu_power = 0.0;
206     (&Cluster_Data[i])->scaled_cpu_power = 0.0;
207   }
208
209   // Compute the relative speed of each cluster.
210   for (i = 0; i < Num_PEs; i++) {
211     cluster = (&PE_Data[i])->cluster;
212
213     (&Cluster_Data[cluster])->num_pes += 1;
214     (&Cluster_Data[cluster])->total_cpu_power += (&PE_Data[i])->relative_speed;
215   }
216
217   min_total_cpu_power = MAXDOUBLE;
218   for (i = 0; i < Num_Clusters; i++) {
219     if ((&Cluster_Data[i])->total_cpu_power < min_total_cpu_power) {
220       min_total_cpu_power = (&Cluster_Data[i])->total_cpu_power;
221     }
222   }
223
224   for (i = 0; i < Num_Clusters; i++) {
225     (&Cluster_Data[i])->scaled_cpu_power = (double) ((&Cluster_Data[i])->total_cpu_power / min_total_cpu_power);
226   }
227 }
228
229
230
231 /**************************************************************************
232 ** This takes objects and partitions them into clusters.
233 */
234 void GridMetisLB::Partition_Objects_Into_Clusters (CentralLB::LDStats *stats)
235 {
236   int num_migratable_objects;
237   int *migratable_objects;
238   int index;
239   int num_partitions;
240   int *partition_to_cluster_map;
241   int cluster;
242   int partition;
243   int partition_count;
244   int **communication_matrix;
245   LDCommData *com_data;
246   int send_object;
247   int recv_object;
248   int send_index;
249   int recv_index;
250   LDObjKey *recv_objects;
251   int num_objects;
252   int *xadj;
253   int num_edges;
254   int *adjncy;
255   int *edge_weights;
256   int count;
257   int weight_flag;
258   int numbering_flag;
259   int options[5];
260   int edgecut;
261   int *newmap;
262   int i;
263   int j;
264
265
266   if (Num_Clusters == 1) {
267     for (i = 0; i < Num_Objects; i++) {
268       (&Object_Data[i])->cluster = 0;
269     }
270
271     return;
272   }
273
274   // Count the number of migratable objects, which are the only candidates to give to Metis.
275   // (The non-migratable objects have been placed onto the correct destination PEs earlier.)
276   // After getting the count, create a migratable_objects[] array to keep track of them.
277   num_migratable_objects = 0;
278   for (i = 0; i < Num_Objects; i++) {
279     if ((&Object_Data[i])->migratable) {
280       num_migratable_objects += 1;
281     }
282   }
283
284   migratable_objects = new int[num_migratable_objects];
285
286   index = 0;
287   for (i = 0; i < Num_Objects; i++) {
288     if ((&Object_Data[i])->migratable) {
289       (&Object_Data[i])->secondary_index = index;
290       migratable_objects[index] = i;
291       index += 1;
292     }
293   }
294
295   // Compute the number of partitions for Metis, based on the scaled CPU power for each cluster.
296   // Also create a partition-to-cluster mapping so the output of Metis can be mapped back to clusters.
297   num_partitions = 0;
298   for (i = 0; i < Num_Clusters; i++) {
299     num_partitions += (int) ceil ((&Cluster_Data[i])->scaled_cpu_power);
300   }
301
302   partition_to_cluster_map = new int[num_partitions];
303
304   cluster = 0;
305   partition = 0;
306   while (partition < num_partitions) {
307     partition_count = (int) ceil ((&Cluster_Data[cluster])->scaled_cpu_power);
308
309     for (i = partition; i < (partition + partition_count); i++) {
310       partition_to_cluster_map[i] = cluster;
311     }
312
313     partition += partition_count;
314     cluster += 1;
315   }
316
317   // Create communication_matrix[] to hold all object-to-object message counts.
318   communication_matrix = new int *[num_migratable_objects];
319   for (i = 0; i < num_migratable_objects; i++) {
320     communication_matrix[i] = new int[num_migratable_objects];
321     for (j = 0; j < num_migratable_objects; j++) {
322       communication_matrix[i][j] = 0;
323     }
324   }
325
326   for (i = 0; i < stats->n_comm; i++) {
327     com_data = &(stats->commData[i]);
328     if ((!com_data->from_proc()) && (com_data->recv_type() == LD_OBJ_MSG)) {
329       send_object = stats->getHash (com_data->sender);
330       recv_object = stats->getHash (com_data->receiver.get_destObj());
331
332       if ((recv_object == -1) && (stats->complete_flag == 0)) {
333         continue;
334       }
335
336       if ((!(&Object_Data[send_object])->migratable) || (!(&Object_Data[recv_object])->migratable)) {
337         continue;
338       }
339
340       send_index = (&Object_Data[send_object])->secondary_index;
341       recv_index = (&Object_Data[recv_object])->secondary_index;
342
343       communication_matrix[send_index][recv_index] += com_data->messages;
344       communication_matrix[recv_index][send_index] += com_data->messages;
345     } else if (com_data->receiver.get_type() == LD_OBJLIST_MSG) {
346       send_object = stats->getHash (com_data->sender);
347
348       if (!(&Object_Data[send_object])->migratable) {
349         continue;
350       }
351
352       recv_objects = com_data->receiver.get_destObjs (num_objects);   // (num_objects is passed by reference)
353
354       for (j = 0; j < num_objects; j++) {
355         recv_object = stats->getHash (recv_objects[j]);
356
357         if (recv_object == -1) {
358           continue;
359         }
360
361         if (!(&Object_Data[recv_object])->migratable) {
362           continue;
363         }
364
365         send_index = (&Object_Data[send_object])->secondary_index;
366         recv_index = (&Object_Data[recv_object])->secondary_index;
367
368         communication_matrix[send_index][recv_index] += com_data->messages;
369         communication_matrix[recv_index][send_index] += com_data->messages;
370       }
371     }
372   }
373
374   for (i = 0; i < num_migratable_objects; i++) {
375     communication_matrix[i][i] = 0;
376   }
377
378   // Construct a graph in CSR format for input to Metis.
379   xadj = new int[num_migratable_objects + 1];
380   num_edges = 0;
381   for (i = 0; i < num_migratable_objects; i++) {
382     for (j = 0; j < num_migratable_objects; j++) {
383       if (communication_matrix[i][j] != 0) {
384         num_edges += 1;
385       }
386     }
387   }
388   adjncy = new int[num_edges];
389   edge_weights = new int[num_edges];
390   count = 0;
391   xadj[0] = 0;
392   for (i = 0; i < num_migratable_objects; i++) {
393     for (j = 0; j < num_migratable_objects; j++) {
394       if (communication_matrix[i][j] != 0) {
395         adjncy[count] = j;
396         edge_weights[count] = communication_matrix[i][j];
397         count += 1;
398       }
399     }
400     xadj[i+1] = count;
401   }
402
403   // Call Metis to partition the communication graph.
404   weight_flag = 1;      // weights on edges only
405   numbering_flag = 0;   // C style numbering (base 0)
406   options[0] = 0;
407   newmap = new int[num_migratable_objects];
408
409   METIS_PartGraphRecursive (&num_migratable_objects, xadj, adjncy, NULL, edge_weights, &weight_flag, &numbering_flag, &num_partitions, options,
410                             &edgecut, newmap);
411
412   // Place the partitioned objects into their correct clusters.
413   for (i = 0; i < num_migratable_objects; i++) {
414     partition = newmap[i];
415     cluster = partition_to_cluster_map[partition];
416
417     index = migratable_objects[i];
418
419     (&Object_Data[index])->cluster = cluster;
420   }
421
422   // Free memory.
423   delete [] newmap;
424   delete [] edge_weights;
425   delete [] adjncy;
426   delete [] xadj;
427   for (i = 0; i < num_migratable_objects; i++) {
428     delete [] communication_matrix[i];
429   }
430   delete [] communication_matrix;
431   delete [] partition_to_cluster_map;
432   delete [] migratable_objects;
433 }
434
435
436
437 /**************************************************************************
438 ** This takes objects in a cluster and partitions them onto PEs.
439 */
440 void GridMetisLB::Partition_ClusterObjects_Into_PEs (CentralLB::LDStats *stats, int cluster)
441 {
442   int num_migratable_cluster_objects;
443   int *migratable_cluster_objects;
444   int index;
445   int num_available_cluster_pes;
446   int num_partitions;
447   int *partition_to_pe_map;
448   int pe;
449   int partition;
450   int partition_count;
451   int *vertex_weights;
452   int vertex;
453   int **communication_matrix;
454   LDCommData *com_data;
455   int send_object;
456   int recv_object;
457   int send_index;
458   int recv_index;
459   LDObjKey *recv_objects;
460   int num_objects;
461   int *xadj;
462   int num_edges;
463   int *adjncy;
464   int *edge_weights;
465   int count;
466   int weight_flag;
467   int numbering_flag;
468   int options[5];
469   int edgecut;
470   int *newmap;
471   int i;
472   int j;
473
474
475   // Count the number of migratable objects within this cluster, which are the only candidates to give to Metis.
476   // (The non-migratable objects have been placed onto the correct destination PEs earlier.)
477   // After getting the count, create a migratable_cluster_objects[] array to keep track of them.
478   num_migratable_cluster_objects = 0;
479   for (i = 0; i < Num_Objects; i++) {
480     if (((&Object_Data[i])->migratable) && ((&Object_Data[i])->cluster == cluster)) {
481       num_migratable_cluster_objects += 1;
482     }
483   }
484
485   migratable_cluster_objects = new int[num_migratable_cluster_objects];
486
487   index = 0;
488   for (i = 0; i < Num_Objects; i++) {
489     if (((&Object_Data[i])->migratable) && ((&Object_Data[i])->cluster == cluster)) {
490       (&Object_Data[i])->secondary_index = index;
491       migratable_cluster_objects[index] = i;
492       index += 1;
493     }
494   }
495
496   // Count the number of available PEs in the cluster.
497   num_available_cluster_pes = 0;
498   for (i = 0; i < Num_PEs; i++) {
499     if (((&PE_Data[i])->available) && ((&PE_Data[i])->cluster == cluster)) {
500       num_available_cluster_pes += 1;
501     }
502   }
503
504   // Compute the number of partitions for Metis, based on the relative speed of each PE.
505   // Also create the partition-to-PE mapping so the output of Metis can be mapped back to PEs.
506   num_partitions = 0;
507   for (i = 0; i < Num_PEs; i++) {
508     if (((&PE_Data[i])->available) && ((&PE_Data[i])->cluster == cluster)) {
509       num_partitions += (int) ceil ((&PE_Data[i])->relative_speed);
510     }
511   }
512
513   partition_to_pe_map = new int[num_partitions];
514
515   pe = 0;
516   while (((!(&PE_Data[pe])->available) || ((&PE_Data[pe])->cluster != cluster)) && (pe < Num_PEs)) {
517     pe += 1;
518   }
519   if (pe >= Num_PEs) {
520     CmiAbort ("GridMetisLB: Error 1!\n");
521   }
522   partition = 0;
523   while (partition < num_partitions) {
524     partition_count = (int) ceil ((&PE_Data[pe])->relative_speed);
525
526     for (i = partition; i < (partition + partition_count); i++) {
527       partition_to_pe_map[i] = pe;
528     }
529
530     partition += partition_count;
531
532     pe += 1;
533     while (((!(&PE_Data[pe])->available) || ((&PE_Data[pe])->cluster != cluster)) && (pe < Num_PEs)) {
534       pe += 1;
535     }
536     if (pe > Num_PEs) {
537       CmiPrintf ("[%d] GridMetisLB: PE=%d, Num_PEs=%d\n", CmiMyPe(), pe, Num_PEs);
538     }
539   }
540
541   // Compute vertex weights for the objects.
542   vertex_weights = new int[num_migratable_cluster_objects];
543   vertex = 0;
544   for (i = 0; i < Num_Objects; i++) {
545     if ((&Object_Data[i])->migratable && ((&Object_Data[i])->cluster == cluster)) {
546       vertex_weights[vertex] = (int) ceil ((&Object_Data[i])->load * 10000);
547       vertex += 1;
548     }
549   }
550
551   // Create communication_matrix[] to hold all object-to-object message counts;
552   communication_matrix = new int *[num_migratable_cluster_objects];
553   for (i = 0; i < num_migratable_cluster_objects; i++) {
554     communication_matrix[i] = new int[num_migratable_cluster_objects];
555     for (j = 0; j < num_migratable_cluster_objects; j++) {
556       communication_matrix[i][j] = 0;
557     }
558   }
559
560   for (i = 0; i < stats->n_comm; i++) {
561     com_data = &(stats->commData[i]);
562     if ((!com_data->from_proc()) && (com_data->recv_type() == LD_OBJ_MSG)) {
563       send_object = stats->getHash (com_data->sender);
564       recv_object = stats->getHash (com_data->receiver.get_destObj());
565
566       if (recv_object == -1 && stats->complete_flag == 0) {
567         continue;
568       }
569
570       if ((!(&Object_Data[send_object])->migratable) || (!(&Object_Data[recv_object])->migratable)) {
571         continue;
572       }
573
574       if (((&Object_Data[send_object])->cluster != cluster) || ((&Object_Data[recv_object])->cluster != cluster)) {
575         continue;
576       }
577
578       send_index = (&Object_Data[send_object])->secondary_index;
579       recv_index = (&Object_Data[recv_object])->secondary_index;
580
581       communication_matrix[send_index][recv_index] += com_data->messages;
582       communication_matrix[recv_index][send_index] += com_data->messages;
583     } else if (com_data->receiver.get_type() == LD_OBJLIST_MSG) {
584       send_object = stats->getHash (com_data->sender);
585
586       if (!(&Object_Data[send_object])->migratable) {
587         continue;
588       }
589
590       if ((&Object_Data[send_object])->cluster != cluster) {
591         continue;
592       }
593
594       recv_objects = com_data->receiver.get_destObjs (num_objects);   // (num_objects is passed by reference)
595
596       for (j = 0; j < num_objects; j++) {
597         recv_object = stats->getHash (recv_objects[j]);
598
599         if (recv_object == -1) {
600           continue;
601         }
602
603         if (!(&Object_Data[recv_object])->migratable) {
604           continue;
605         }
606
607         if ((&Object_Data[recv_object])->cluster != cluster) {
608           continue;
609         }
610
611         send_index = (&Object_Data[send_object])->secondary_index;
612         recv_index = (&Object_Data[recv_object])->secondary_index;
613
614         communication_matrix[send_index][recv_index] += com_data->messages;
615         communication_matrix[recv_index][send_index] += com_data->messages;
616       }
617     }
618   }
619
620   for (i = 0; i < num_migratable_cluster_objects; i++) {
621     communication_matrix[i][i] = 0;
622   }
623
624   // Construct a graph in CSR format for input to Metis.
625   xadj = new int[num_migratable_cluster_objects + 1];
626   num_edges = 0;
627   for (i = 0; i < num_migratable_cluster_objects; i++) {
628     for (j = 0; j < num_migratable_cluster_objects; j++) {
629       if (communication_matrix[i][j] != 0) {
630         num_edges += 1;
631       }
632     }
633   }
634   adjncy = new int[num_edges];
635   edge_weights = new int[num_edges];
636   count = 0;
637   xadj[0] = 0;
638   for (i = 0; i < num_migratable_cluster_objects; i++) {
639     for (j = 0; j < num_migratable_cluster_objects; j++) {
640       if (communication_matrix[i][j] != 0) {
641         adjncy[count] = j;
642         edge_weights[count] = communication_matrix[i][j];
643         count += 1;
644       }
645     }
646     xadj[i+1] = count;
647   }
648
649   // Call Metis to partition the communication graph.
650   weight_flag = 3;      // weights on both vertices and edges
651   numbering_flag = 0;   // C style numbering (base 0)
652   options[0] = 0;
653   newmap = new int[num_migratable_cluster_objects];
654
655   CmiPrintf ("[%d] GridMetisLB partitioning %d objects in cluster %d into %d partitions\n", CmiMyPe(), num_migratable_cluster_objects, cluster, num_partitions);
656
657   METIS_PartGraphRecursive (&num_migratable_cluster_objects, xadj, adjncy, vertex_weights, edge_weights, &weight_flag, &numbering_flag, &num_partitions, options,
658                             &edgecut, newmap);
659
660   // Place the partitioned objects onto their correct PEs.
661   for (i = 0; i < num_migratable_cluster_objects; i++) {
662     partition = newmap[i];
663     pe = partition_to_pe_map[partition];
664
665     index = migratable_cluster_objects[i];
666
667     for (j = 0; j < Num_Objects; j++) {
668       if ((&Object_Data[j])->secondary_index == index) {
669         (&Object_Data[j])->to_pe = pe;
670         break;
671       }
672     }
673   }
674
675   // Free memory.
676   delete [] newmap;
677   delete [] edge_weights;
678   delete [] adjncy;
679   delete [] xadj;
680   for (i = 0; i < num_migratable_cluster_objects; i++) {
681     delete [] communication_matrix[i];
682   }
683   delete [] communication_matrix;
684   delete [] vertex_weights;
685   delete [] partition_to_pe_map;
686   delete [] migratable_cluster_objects;
687 }
688
689
690
691 /**************************************************************************
692 ** The Charm++ load balancing framework invokes this method to cause the
693 ** load balancer to migrate objects to "better" PEs.
694 */
695 void GridMetisLB::work (CentralLB::LDStats *stats, int count)
696 {
697   int i;
698
699
700   if (_lb_args.debug() > 0) {
701     CkPrintf ("[%d] GridMetisLB is working.\n", CkMyPe());
702   }
703
704   // Since this load balancer looks at communications data, it must call stats->makeCommHash().
705   stats->makeCommHash ();
706
707   // Initialize object variables for the number of PEs and number of objects.
708   Num_PEs = count;
709   Num_Objects = stats->n_objs;
710
711   if (_lb_args.debug() > 0) {
712     CkPrintf ("[%d] GridMetisLB is examining %d PEs and %d objects.\n", CkMyPe(), Num_PEs, Num_Objects);
713   }
714
715   // Initialize the PE_Data[] data structure.
716   Initialize_PE_Data (stats);
717
718   // If at least one available PE does not exist, return from load balancing.
719   if (Available_PE_Count() < 1) {
720     if (_lb_args.debug() > 0) {
721       CkPrintf ("[%d] GridMetisLB finds no available PEs -- no balancing done.\n", CkMyPe());
722     }
723
724     delete [] PE_Data;
725
726     return;
727   }
728
729   // Determine the number of clusters.
730   // If any PE is not mapped to a cluster, return from load balancing.
731   Num_Clusters = Compute_Number_Of_Clusters ();
732   if (Num_Clusters < 1) {
733     if (_lb_args.debug() > 0) {
734       CkPrintf ("[%d] GridMetisLB finds incomplete PE cluster map -- no balancing done.\n", CkMyPe());
735     }
736
737     delete [] PE_Data;
738
739     return;
740   }
741
742   if (_lb_args.debug() > 0) {
743     CkPrintf ("[%d] GridMetisLB finds %d clusters.\n", CkMyPe(), Num_Clusters);
744   }
745
746   // Initialize the Object_Data[] data structure.
747   Initialize_Object_Data (stats);
748
749   // Initialize the Cluster_Data[] data structure.
750   Initialize_Cluster_Data ();
751
752   Partition_Objects_Into_Clusters (stats);
753   for (i = 0; i < Num_Clusters; i++) {
754     Partition_ClusterObjects_Into_PEs (stats, i);
755   }
756
757   // Make the assignment of objects to PEs in the load balancer framework.
758   for (i = 0; i < Num_Objects; i++) {
759     stats->to_proc[i] = (&Object_Data[i])->to_pe;
760
761     if (_lb_args.debug() > 2) {
762       CkPrintf ("[%d] GridMetisLB migrates object %d from PE %d to PE %d.\n", CkMyPe(), i, stats->from_proc[i], stats->to_proc[i]);
763     } else if (_lb_args.debug() > 1) {
764       if (stats->to_proc[i] != stats->from_proc[i]) {
765         CkPrintf ("[%d] GridMetisLB migrates object %d from PE %d to PE %d.\n", CkMyPe(), i, stats->from_proc[i], stats->to_proc[i]);
766       }
767     }
768   }
769
770   // Free memory.
771   delete [] Cluster_Data;
772   delete [] Object_Data;
773   delete [] PE_Data;
774 }
775
776 #include "GridMetisLB.def.h"