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