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