These changes fix things that I have discovered about Grid load balancing.
[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       (&PE_Data[(&Object_Data[i])->to_pe])->scaled_load += (&Object_Data[i])->load / (&PE_Data[(&Object_Data[i])->to_pe])->relative_speed;
183       if (_lb_args.debug() > 1) {
184         CkPrintf ("[%d] GridMetisLB identifies object %d as non-migratable.\n", CkMyPe(), i);
185       }
186     }
187   }
188 }
189
190
191
192 /**************************************************************************
193 **
194 */
195 void GridMetisLB::Initialize_Cluster_Data ()
196 {
197   int cluster;
198   double min_total_cpu_power;
199   int i;
200
201
202   Cluster_Data = new Cluster_Data_T[Num_Clusters];
203
204   for (i = 0; i < Num_Clusters; i++) {
205     (&Cluster_Data[i])->num_pes = 0;
206     (&Cluster_Data[i])->total_cpu_power = 0.0;
207     (&Cluster_Data[i])->scaled_cpu_power = 0.0;
208   }
209
210   // Compute the relative speed of each cluster.
211   for (i = 0; i < Num_PEs; i++) {
212     cluster = (&PE_Data[i])->cluster;
213
214     (&Cluster_Data[cluster])->num_pes += 1;
215     (&Cluster_Data[cluster])->total_cpu_power += (&PE_Data[i])->relative_speed;
216   }
217
218   min_total_cpu_power = MAXDOUBLE;
219   for (i = 0; i < Num_Clusters; i++) {
220     if ((&Cluster_Data[i])->total_cpu_power < min_total_cpu_power) {
221       min_total_cpu_power = (&Cluster_Data[i])->total_cpu_power;
222     }
223   }
224
225   for (i = 0; i < Num_Clusters; i++) {
226     (&Cluster_Data[i])->scaled_cpu_power = (double) ((&Cluster_Data[i])->total_cpu_power / min_total_cpu_power);
227   }
228 }
229
230
231
232 /**************************************************************************
233 ** This takes objects and partitions them into clusters.
234 */
235 void GridMetisLB::Partition_Objects_Into_Clusters (CentralLB::LDStats *stats)
236 {
237   int num_migratable_objects;
238   int *migratable_objects;
239   int index;
240   int num_partitions;
241   int *partition_to_cluster_map;
242   int cluster;
243   int partition;
244   int partition_count;
245   int **communication_matrix;
246   LDCommData *com_data;
247   int send_object;
248   int recv_object;
249   int send_index;
250   int recv_index;
251   LDObjKey *recv_objects;
252   int num_objects;
253   int *xadj;
254   int num_edges;
255   int *adjncy;
256   int *edge_weights;
257   int count;
258   int weight_flag;
259   int numbering_flag;
260   int options[5];
261   int edgecut;
262   int *newmap;
263   int i;
264   int j;
265
266
267   if (Num_Clusters == 1) {
268     for (i = 0; i < Num_Objects; i++) {
269       (&Object_Data[i])->cluster = 0;
270     }
271
272     return;
273   }
274
275   // Count the number of migratable objects, which are the only candidates to give to Metis.
276   // (The non-migratable objects have been placed onto the correct destination PEs earlier.)
277   // After getting the count, create a migratable_objects[] array to keep track of them.
278   num_migratable_objects = 0;
279   for (i = 0; i < Num_Objects; i++) {
280     if ((&Object_Data[i])->migratable) {
281       num_migratable_objects += 1;
282     }
283   }
284
285   migratable_objects = new int[num_migratable_objects];
286
287   index = 0;
288   for (i = 0; i < Num_Objects; i++) {
289     if ((&Object_Data[i])->migratable) {
290       (&Object_Data[i])->secondary_index = index;
291       migratable_objects[index] = i;
292       index += 1;
293     }
294   }
295
296   // Compute the number of partitions for Metis, based on the scaled CPU power for each cluster.
297   // Also create a partition-to-cluster mapping so the output of Metis can be mapped back to clusters.
298   num_partitions = 0;
299   for (i = 0; i < Num_Clusters; i++) {
300     num_partitions += (int) ceil ((&Cluster_Data[i])->scaled_cpu_power);
301   }
302
303   partition_to_cluster_map = new int[num_partitions];
304
305   cluster = 0;
306   partition = 0;
307   while (partition < num_partitions) {
308     partition_count = (int) ceil ((&Cluster_Data[cluster])->scaled_cpu_power);
309
310     for (i = partition; i < (partition + partition_count); i++) {
311       partition_to_cluster_map[i] = cluster;
312     }
313
314     partition += partition_count;
315     cluster += 1;
316   }
317
318   // Create communication_matrix[] to hold all object-to-object message counts.
319   communication_matrix = new int *[num_migratable_objects];
320   for (i = 0; i < num_migratable_objects; i++) {
321     communication_matrix[i] = new int[num_migratable_objects];
322     for (j = 0; j < num_migratable_objects; j++) {
323       communication_matrix[i][j] = 0;
324     }
325   }
326
327   for (i = 0; i < stats->n_comm; i++) {
328     com_data = &(stats->commData[i]);
329     if ((!com_data->from_proc()) && (com_data->recv_type() == LD_OBJ_MSG)) {
330       send_object = stats->getHash (com_data->sender);
331       recv_object = stats->getHash (com_data->receiver.get_destObj());
332
333       //if ((recv_object == -1) && (stats->complete_flag == 0)) {
334       if ((send_object < 0) || (send_object > Num_Objects) || (recv_object < 0) || (recv_object > Num_Objects)) {
335         continue;
336       }
337
338       if ((!(&Object_Data[send_object])->migratable) || (!(&Object_Data[recv_object])->migratable)) {
339         continue;
340       }
341
342       send_index = (&Object_Data[send_object])->secondary_index;
343       recv_index = (&Object_Data[recv_object])->secondary_index;
344
345       communication_matrix[send_index][recv_index] += com_data->messages;
346       communication_matrix[recv_index][send_index] += com_data->messages;
347     } else if (com_data->receiver.get_type() == LD_OBJLIST_MSG) {
348       send_object = stats->getHash (com_data->sender);
349
350       if ((send_object < 0) || (send_object > Num_Objects)) {
351         continue;
352       }
353
354       if (!(&Object_Data[send_object])->migratable) {
355         continue;
356       }
357
358       recv_objects = com_data->receiver.get_destObjs (num_objects);   // (num_objects is passed by reference)
359
360       for (j = 0; j < num_objects; j++) {
361         recv_object = stats->getHash (recv_objects[j]);
362
363         //if (recv_object == -1) {
364         if ((recv_object < 0) || (recv_object > Num_Objects)) {
365           continue;
366         }
367
368         if (!(&Object_Data[recv_object])->migratable) {
369           continue;
370         }
371
372         send_index = (&Object_Data[send_object])->secondary_index;
373         recv_index = (&Object_Data[recv_object])->secondary_index;
374
375         communication_matrix[send_index][recv_index] += com_data->messages;
376         communication_matrix[recv_index][send_index] += com_data->messages;
377       }
378     }
379   }
380
381   for (i = 0; i < num_migratable_objects; i++) {
382     communication_matrix[i][i] = 0;
383   }
384
385   // Construct a graph in CSR format for input to Metis.
386   xadj = new int[num_migratable_objects + 1];
387   num_edges = 0;
388   for (i = 0; i < num_migratable_objects; i++) {
389     for (j = 0; j < num_migratable_objects; j++) {
390       if (communication_matrix[i][j] > 0) {
391         num_edges += 1;
392       }
393     }
394   }
395   adjncy = new int[num_edges];
396   edge_weights = new int[num_edges];
397   count = 0;
398   xadj[0] = 0;
399   for (i = 0; i < num_migratable_objects; i++) {
400     for (j = 0; j < num_migratable_objects; j++) {
401       if (communication_matrix[i][j] > 0) {
402         adjncy[count] = j;
403         edge_weights[count] = communication_matrix[i][j];
404         count += 1;
405       }
406     }
407     xadj[i+1] = count;
408   }
409
410   // Call Metis to partition the communication graph.
411   weight_flag = 1;      // weights on edges only
412   numbering_flag = 0;   // C style numbering (base 0)
413   options[0] = 0;
414   newmap = new int[num_migratable_objects];
415
416   METIS_PartGraphRecursive (&num_migratable_objects, xadj, adjncy, NULL, edge_weights, &weight_flag, &numbering_flag, &num_partitions, options, &edgecut, newmap);
417
418   // Place the partitioned objects into their correct clusters.
419   for (i = 0; i < num_migratable_objects; i++) {
420     partition = newmap[i];
421     cluster = partition_to_cluster_map[partition];
422
423     index = migratable_objects[i];
424
425     (&Object_Data[index])->cluster = cluster;
426   }
427
428   // Free memory.
429   delete [] newmap;
430   delete [] edge_weights;
431   delete [] adjncy;
432   delete [] xadj;
433   for (i = 0; i < num_migratable_objects; i++) {
434     delete [] communication_matrix[i];
435   }
436   delete [] communication_matrix;
437   delete [] partition_to_cluster_map;
438   delete [] migratable_objects;
439 }
440
441
442
443 /**************************************************************************
444 ** This takes objects in a cluster and partitions them onto PEs.
445 */
446 void GridMetisLB::Partition_ClusterObjects_Into_PEs (CentralLB::LDStats *stats, int cluster)
447 {
448   int num_migratable_cluster_objects;
449   int *migratable_cluster_objects;
450   int index;
451   int num_available_cluster_pes;
452   int num_partitions;
453   int *partition_to_pe_map;
454   int pe;
455   int partition;
456   int partition_count;
457   int *vertex_weights;
458   int vertex;
459   int **communication_matrix;
460   LDCommData *com_data;
461   int send_object;
462   int recv_object;
463   int send_index;
464   int recv_index;
465   LDObjKey *recv_objects;
466   int num_objects;
467   int *xadj;
468   int num_edges;
469   int *adjncy;
470   int *edge_weights;
471   int count;
472   int weight_flag;
473   int numbering_flag;
474   int options[5];
475   int edgecut;
476   int *newmap;
477   int i;
478   int j;
479
480
481   // Count the number of migratable objects within this cluster, which are the only candidates to give to Metis.
482   // (The non-migratable objects have been placed onto the correct destination PEs earlier.)
483   // After getting the count, create a migratable_cluster_objects[] array to keep track of them.
484   num_migratable_cluster_objects = 0;
485   for (i = 0; i < Num_Objects; i++) {
486     if (((&Object_Data[i])->migratable) && ((&Object_Data[i])->cluster == cluster)) {
487       num_migratable_cluster_objects += 1;
488     }
489   }
490
491   migratable_cluster_objects = new int[num_migratable_cluster_objects];
492
493   index = 0;
494   for (i = 0; i < Num_Objects; i++) {
495     if (((&Object_Data[i])->migratable) && ((&Object_Data[i])->cluster == cluster)) {
496       (&Object_Data[i])->secondary_index = index;
497       migratable_cluster_objects[index] = i;
498       index += 1;
499     }
500   }
501
502   // Count the number of available PEs in the cluster.
503   num_available_cluster_pes = 0;
504   for (i = 0; i < Num_PEs; i++) {
505     if (((&PE_Data[i])->available) && ((&PE_Data[i])->cluster == cluster)) {
506       num_available_cluster_pes += 1;
507     }
508   }
509
510   // Compute the number of partitions for Metis, based on the relative speed of each PE.
511   // Also create the partition-to-PE mapping so the output of Metis can be mapped back to PEs.
512   num_partitions = 0;
513   for (i = 0; i < Num_PEs; i++) {
514     if (((&PE_Data[i])->available) && ((&PE_Data[i])->cluster == cluster)) {
515       num_partitions += (int) ceil ((&PE_Data[i])->relative_speed);
516     }
517   }
518
519   partition_to_pe_map = new int[num_partitions];
520
521   pe = 0;
522   while (((!(&PE_Data[pe])->available) || ((&PE_Data[pe])->cluster != cluster)) && (pe < Num_PEs)) {
523     pe += 1;
524   }
525   if (pe >= Num_PEs) {
526     CmiAbort ("GridMetisLB: Error computing partition to PE map!\n");
527   }
528   partition = 0;
529   while (partition < num_partitions) {
530     partition_count = (int) ceil ((&PE_Data[pe])->relative_speed);
531
532     for (i = partition; i < (partition + partition_count); i++) {
533       partition_to_pe_map[i] = pe;
534     }
535
536     partition += partition_count;
537
538     pe += 1;
539     while (((!(&PE_Data[pe])->available) || ((&PE_Data[pe])->cluster != cluster)) && (pe < Num_PEs)) {
540       pe += 1;
541     }
542     if (pe >= Num_PEs) {
543       CmiAbort ("GridMetisLB: Error computing partition to PE map!\n");
544     }
545   }
546
547   // Compute vertex weights for the objects.
548   vertex_weights = new int[num_migratable_cluster_objects];
549   vertex = 0;
550   for (i = 0; i < Num_Objects; i++) {
551     if ((&Object_Data[i])->migratable && ((&Object_Data[i])->cluster == cluster)) {
552       vertex_weights[vertex] = (int) ceil ((&Object_Data[i])->load * 10000);
553       vertex += 1;
554     }
555   }
556
557   // Create communication_matrix[] to hold all object-to-object message counts;
558   communication_matrix = new int *[num_migratable_cluster_objects];
559   for (i = 0; i < num_migratable_cluster_objects; i++) {
560     communication_matrix[i] = new int[num_migratable_cluster_objects];
561     for (j = 0; j < num_migratable_cluster_objects; j++) {
562       communication_matrix[i][j] = 0;
563     }
564   }
565
566   for (i = 0; i < stats->n_comm; i++) {
567     com_data = &(stats->commData[i]);
568     if ((!com_data->from_proc()) && (com_data->recv_type() == LD_OBJ_MSG)) {
569       send_object = stats->getHash (com_data->sender);
570       recv_object = stats->getHash (com_data->receiver.get_destObj());
571
572       //if ((recv_object == -1) && (stats->complete_flag == 0)) {
573       if ((send_object < 0) || (send_object > Num_Objects) || (recv_object < 0) || (recv_object > Num_Objects)) {
574         continue;
575       }
576
577       if ((!(&Object_Data[send_object])->migratable) || (!(&Object_Data[recv_object])->migratable)) {
578         continue;
579       }
580
581       if (((&Object_Data[send_object])->cluster != cluster) || ((&Object_Data[recv_object])->cluster != cluster)) {
582         continue;
583       }
584
585       send_index = (&Object_Data[send_object])->secondary_index;
586       recv_index = (&Object_Data[recv_object])->secondary_index;
587
588       communication_matrix[send_index][recv_index] += com_data->messages;
589       communication_matrix[recv_index][send_index] += com_data->messages;
590     } else if (com_data->receiver.get_type() == LD_OBJLIST_MSG) {
591       send_object = stats->getHash (com_data->sender);
592
593       if ((send_object < 0) || (send_object > Num_Objects)) {
594         continue;
595       }
596
597       if (!(&Object_Data[send_object])->migratable) {
598         continue;
599       }
600
601       if ((&Object_Data[send_object])->cluster != cluster) {
602         continue;
603       }
604
605       recv_objects = com_data->receiver.get_destObjs (num_objects);   // (num_objects is passed by reference)
606
607       for (j = 0; j < num_objects; j++) {
608         recv_object = stats->getHash (recv_objects[j]);
609
610         //if (recv_object == -1) {
611         if ((recv_object < 0) || (recv_object > Num_Objects)) {
612           continue;
613         }
614
615         if (!(&Object_Data[recv_object])->migratable) {
616           continue;
617         }
618
619         if ((&Object_Data[recv_object])->cluster != cluster) {
620           continue;
621         }
622
623         send_index = (&Object_Data[send_object])->secondary_index;
624         recv_index = (&Object_Data[recv_object])->secondary_index;
625
626         communication_matrix[send_index][recv_index] += com_data->messages;
627         communication_matrix[recv_index][send_index] += com_data->messages;
628       }
629     }
630   }
631
632   for (i = 0; i < num_migratable_cluster_objects; i++) {
633     communication_matrix[i][i] = 0;
634   }
635
636   // Construct a graph in CSR format for input to Metis.
637   xadj = new int[num_migratable_cluster_objects + 1];
638   num_edges = 0;
639   for (i = 0; i < num_migratable_cluster_objects; i++) {
640     for (j = 0; j < num_migratable_cluster_objects; j++) {
641       if (communication_matrix[i][j] > 0) {
642         num_edges += 1;
643       }
644     }
645   }
646   adjncy = new int[num_edges];
647   edge_weights = new int[num_edges];
648   count = 0;
649   xadj[0] = 0;
650   for (i = 0; i < num_migratable_cluster_objects; i++) {
651     for (j = 0; j < num_migratable_cluster_objects; j++) {
652       if (communication_matrix[i][j] > 0) {
653         adjncy[count] = j;
654         edge_weights[count] = communication_matrix[i][j];
655         count += 1;
656       }
657     }
658     xadj[i+1] = count;
659   }
660
661   // Call Metis to partition the communication graph.
662   weight_flag = 3;      // weights on both vertices and edges
663   numbering_flag = 0;   // C style numbering (base 0)
664   options[0] = 0;
665   newmap = new int[num_migratable_cluster_objects];
666
667   CmiPrintf ("[%d] GridMetisLB partitioning %d objects in cluster %d into %d partitions\n", CmiMyPe(), num_migratable_cluster_objects, cluster, num_partitions);
668
669   METIS_PartGraphRecursive (&num_migratable_cluster_objects, xadj, adjncy, vertex_weights, edge_weights, &weight_flag, &numbering_flag, &num_partitions, options, &edgecut, newmap);
670
671   // Place the partitioned objects onto their correct PEs.
672   for (i = 0; i < num_migratable_cluster_objects; i++) {
673     partition = newmap[i];
674     pe = partition_to_pe_map[partition];
675
676     index = migratable_cluster_objects[i];
677
678     for (j = 0; j < Num_Objects; j++) {
679       if ((&Object_Data[j])->secondary_index == index) {
680         (&Object_Data[j])->to_pe = pe;
681         break;
682       }
683     }
684   }
685
686   // Free memory.
687   delete [] newmap;
688   delete [] edge_weights;
689   delete [] adjncy;
690   delete [] xadj;
691   for (i = 0; i < num_migratable_cluster_objects; i++) {
692     delete [] communication_matrix[i];
693   }
694   delete [] communication_matrix;
695   delete [] vertex_weights;
696   delete [] partition_to_pe_map;
697   delete [] migratable_cluster_objects;
698 }
699
700
701
702 /**************************************************************************
703 ** The Charm++ load balancing framework invokes this method to cause the
704 ** load balancer to migrate objects to "better" PEs.
705 */
706 void GridMetisLB::work (CentralLB::LDStats *stats, int count)
707 {
708   int i;
709
710
711   if (_lb_args.debug() > 0) {
712     CkPrintf ("[%d] GridMetisLB is working.\n", CkMyPe());
713   }
714
715   // Since this load balancer looks at communications data, it must call stats->makeCommHash().
716   stats->makeCommHash ();
717
718   // Initialize object variables for the number of PEs and number of objects.
719   Num_PEs = count;
720   Num_Objects = stats->n_objs;
721
722   if (_lb_args.debug() > 0) {
723     CkPrintf ("[%d] GridMetisLB is examining %d PEs and %d objects.\n", CkMyPe(), Num_PEs, Num_Objects);
724   }
725
726   // Initialize the PE_Data[] data structure.
727   Initialize_PE_Data (stats);
728
729   // If at least one available PE does not exist, return from load balancing.
730   if (Available_PE_Count() < 1) {
731     if (_lb_args.debug() > 0) {
732       CkPrintf ("[%d] GridMetisLB finds no available PEs -- no balancing done.\n", CkMyPe());
733     }
734
735     delete [] PE_Data;
736
737     return;
738   }
739
740   // Determine the number of clusters.
741   // If any PE is not mapped to a cluster, return from load balancing.
742   Num_Clusters = Compute_Number_Of_Clusters ();
743   if (Num_Clusters < 1) {
744     if (_lb_args.debug() > 0) {
745       CkPrintf ("[%d] GridMetisLB finds incomplete PE cluster map -- no balancing done.\n", CkMyPe());
746     }
747
748     delete [] PE_Data;
749
750     return;
751   }
752
753   if (_lb_args.debug() > 0) {
754     CkPrintf ("[%d] GridMetisLB finds %d clusters.\n", CkMyPe(), Num_Clusters);
755   }
756
757   // Initialize the Object_Data[] data structure.
758   Initialize_Object_Data (stats);
759
760   // Initialize the Cluster_Data[] data structure.
761   Initialize_Cluster_Data ();
762
763   Partition_Objects_Into_Clusters (stats);
764   for (i = 0; i < Num_Clusters; i++) {
765     Partition_ClusterObjects_Into_PEs (stats, i);
766   }
767
768   // Make the assignment of objects to PEs in the load balancer framework.
769   for (i = 0; i < Num_Objects; i++) {
770     stats->to_proc[i] = (&Object_Data[i])->to_pe;
771
772     if (_lb_args.debug() > 2) {
773       CkPrintf ("[%d] GridMetisLB migrates object %d from PE %d to PE %d.\n", CkMyPe(), i, stats->from_proc[i], stats->to_proc[i]);
774     } else if (_lb_args.debug() > 1) {
775       if (stats->to_proc[i] != stats->from_proc[i]) {
776         CkPrintf ("[%d] GridMetisLB migrates object %d from PE %d to PE %d.\n", CkMyPe(), i, stats->from_proc[i], stats->to_proc[i]);
777       }
778     }
779   }
780
781   // Free memory.
782   delete [] Cluster_Data;
783   delete [] Object_Data;
784   delete [] PE_Data;
785 }
786
787 #include "GridMetisLB.def.h"