doc: Add serial to list of ci file reserved words
[charm.git] / src / ck-ldb / GridHybridSeedLB.C
1 /**************************************************************************
2 ** Greg Koenig (koenig@uiuc.edu)
3 ** June 14, 2007
4 **
5 ** This is GridHybridSeedLB.C
6 **
7 */
8
9 #include "GridHybridSeedLB.decl.h"
10
11 #include "GridHybridSeedLB.h"
12 #include "manager.h"
13
14 CreateLBFunc_Def (GridHybridSeedLB, "Grid load balancer that uses hybrid seed technique to optimize communication graph")
15
16
17
18 /**************************************************************************
19 **
20 */
21 GridHybridSeedLB::GridHybridSeedLB (const CkLBOptions &opt) : CentralLB (opt)
22 {
23   char *value;
24
25
26   lbname = (char *) "GridHybridSeedLB";
27
28   if (CkMyPe() == 0) {
29     CkPrintf ("[%d] GridHybridSeedLB created.\n", CkMyPe());
30   }
31
32   if (value = getenv ("CK_LDB_GRIDHYBRIDSEEDLB_MODE")) {
33     CK_LDB_GridHybridSeedLB_Mode = atoi (value);
34   } else {
35     CK_LDB_GridHybridSeedLB_Mode = CK_LDB_GRIDHYBRIDSEEDLB_MODE;
36   }
37
38   if (value = getenv ("CK_LDB_GRIDHYBRIDSEEDLB_BACKGROUND_LOAD")) {
39     CK_LDB_GridHybridSeedLB_Background_Load = atoi (value);
40   } else {
41     CK_LDB_GridHybridSeedLB_Background_Load = CK_LDB_GRIDHYBRIDSEEDLB_BACKGROUND_LOAD;
42   }
43
44   if (value = getenv ("CK_LDB_GRIDHYBRIDSEEDLB_LOAD_TOLERANCE")) {
45     CK_LDB_GridHybridSeedLB_Load_Tolerance = atof (value);
46   } else {
47     CK_LDB_GridHybridSeedLB_Load_Tolerance = CK_LDB_GRIDHYBRIDSEEDLB_LOAD_TOLERANCE;
48   }
49   
50   manager_init ();
51 }
52
53
54
55 /**************************************************************************
56 **
57 */
58 GridHybridSeedLB::GridHybridSeedLB (CkMigrateMessage *msg) : CentralLB (msg)
59 {
60   char *value;
61
62
63   lbname = (char *) "GridHybridSeedLB";
64
65   if (value = getenv ("CK_LDB_GRIDHYBRIDSEEDLB_MODE")) {
66     CK_LDB_GridHybridSeedLB_Mode = atoi (value);
67   } else {
68     CK_LDB_GridHybridSeedLB_Mode = CK_LDB_GRIDHYBRIDSEEDLB_MODE;
69   }
70
71   if (value = getenv ("CK_LDB_GRIDHYBRIDSEEDLB_BACKGROUND_LOAD")) {
72     CK_LDB_GridHybridSeedLB_Background_Load = atoi (value);
73   } else {
74     CK_LDB_GridHybridSeedLB_Background_Load = CK_LDB_GRIDHYBRIDSEEDLB_BACKGROUND_LOAD;
75   }
76
77   if (value = getenv ("CK_LDB_GRIDHYBRIDSEEDLB_LOAD_TOLERANCE")) {
78     CK_LDB_GridHybridSeedLB_Load_Tolerance = atof (value);
79   } else {
80     CK_LDB_GridHybridSeedLB_Load_Tolerance = CK_LDB_GRIDHYBRIDSEEDLB_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 GridHybridSeedLB::QueryBalanceNow (int step)
93 {
94   if (_lb_args.debug() > 2) {
95     CkPrintf ("[%d] GridHybridSeedLB 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 ** GridHybridSeedLB will assume a single-cluster computation and will
112 ** balance on the scaled processor load and number of LAN messages.
113 */
114 int GridHybridSeedLB::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 GridHybridSeedLB::Initialize_PE_Data (CentralLB::LDStats *stats)
129 {
130   int min_speed;
131
132
133   PE_Data = new PE_Data_T[Num_PEs];
134
135   min_speed = MAXINT;
136   for (int i = 0; i < Num_PEs; i++) {
137     (&PE_Data[i])->available      = stats->procs[i].available;
138     (&PE_Data[i])->cluster        = Get_Cluster (i);
139     (&PE_Data[i])->num_objs       = 0;
140     (&PE_Data[i])->num_lan_objs   = 0;
141     (&PE_Data[i])->num_lan_msgs   = 0;
142     (&PE_Data[i])->num_wan_objs   = 0;
143     (&PE_Data[i])->num_wan_msgs   = 0;
144     (&PE_Data[i])->relative_speed = 0.0;
145     (&PE_Data[i])->scaled_load    = 0.0;
146
147     if (stats->procs[i].pe_speed < min_speed) {
148       min_speed = stats->procs[i].pe_speed;
149     }
150   }
151
152   // Compute the relative PE speeds.
153   // Also add background CPU time to each PE's scaled load.
154   for (int i = 0; i < Num_PEs; i++) {
155     (&PE_Data[i])->relative_speed = (double) (stats->procs[i].pe_speed / min_speed);
156     if (CK_LDB_GridHybridSeedLB_Background_Load) {
157       (&PE_Data[i])->scaled_load += stats->procs[i].bg_walltime;
158     }
159   }
160 }
161
162
163
164 /**************************************************************************
165 **
166 */
167 int GridHybridSeedLB::Available_PE_Count ()
168 {
169   int available_pe_count;
170
171
172   available_pe_count = 0;
173   for (int i = 0; i < Num_PEs; i++) {
174     if ((&PE_Data[i])->available) {
175       available_pe_count += 1;
176     }
177   }
178
179   return (available_pe_count);
180 }
181
182
183
184 /**************************************************************************
185 **
186 */
187 int GridHybridSeedLB::Compute_Number_Of_Clusters ()
188 {
189   int max_cluster;
190
191
192   max_cluster = 0;
193   for (int i = 0; i < Num_PEs; i++) {
194     if ((&PE_Data[i])->cluster < 0) {
195       return (-1);
196     }
197
198     if ((&PE_Data[i])->cluster > max_cluster) {
199       max_cluster = (&PE_Data[i])->cluster;
200     }
201   }
202
203   return (max_cluster + 1);
204 }
205
206
207
208 /**************************************************************************
209 **
210 */
211 void GridHybridSeedLB::Initialize_Object_Data (CentralLB::LDStats *stats)
212 {
213   Object_Data = new Object_Data_T[Num_Objects];
214
215   for (int i = 0; i < Num_Objects; i++) {
216     (&Object_Data[i])->migratable      = (&stats->objData[i])->migratable;
217     (&Object_Data[i])->from_pe         = stats->from_proc[i];
218     (&Object_Data[i])->num_lan_msgs    = 0;
219     (&Object_Data[i])->num_wan_msgs    = 0;
220     (&Object_Data[i])->load            = (&stats->objData[i])->wallTime;
221     (&Object_Data[i])->secondary_index = -1;
222
223     if ((&Object_Data[i])->migratable) {
224       (&Object_Data[i])->to_pe = -1;
225       (&Object_Data[i])->cluster = -1;
226     } else {
227       (&Object_Data[i])->to_pe = (&Object_Data[i])->from_pe;
228       (&Object_Data[i])->cluster = Get_Cluster ((&Object_Data[i])->from_pe);
229       if (_lb_args.debug() > 1) {
230         CkPrintf ("[%d] GridHybridSeedLB identifies object %d as non-migratable.\n", CkMyPe(), i);
231       }
232     }
233   }
234 }
235
236
237
238 /**************************************************************************
239 **
240 */
241 int GridHybridSeedLB::Compute_Migratable_Object_Count ()
242 {
243   int count;
244
245
246   count = 0;
247
248   for (int i = 0; i < Num_Objects; i++) {
249     if ((&Object_Data[i])->migratable) {
250       count += 1;
251     }
252   }
253
254   return (count);
255 }
256
257
258
259 /**************************************************************************
260 **
261 */
262 void GridHybridSeedLB::Initialize_Cluster_Data ()
263 {
264   int cluster;
265   double min_total_cpu_power;
266
267
268   Cluster_Data = new Cluster_Data_T[Num_Clusters];
269
270   for (int i = 0; i < Num_Clusters; i++) {
271     (&Cluster_Data[i])->num_pes = 0;
272     (&Cluster_Data[i])->total_cpu_power = 0.0;
273     (&Cluster_Data[i])->scaled_cpu_power = 0.0;
274   }
275
276   // Compute the relative speed of each cluster.
277   for (int i = 0; i < Num_PEs; i++) {
278     cluster = (&PE_Data[i])->cluster;
279
280     (&Cluster_Data[cluster])->num_pes += 1;
281     (&Cluster_Data[cluster])->total_cpu_power += (&PE_Data[i])->relative_speed;
282   }
283
284   min_total_cpu_power = MAXDOUBLE;
285   for (int i = 0; i < Num_Clusters; i++) {
286     if ((&Cluster_Data[i])->total_cpu_power < min_total_cpu_power) {
287       min_total_cpu_power = (&Cluster_Data[i])->total_cpu_power;
288     }
289   }
290
291   for (int i = 0; i < Num_Clusters; i++) {
292     (&Cluster_Data[i])->scaled_cpu_power = (double) ((&Cluster_Data[i])->total_cpu_power / min_total_cpu_power);
293   }
294 }
295
296
297
298 /**************************************************************************
299 **
300 */
301 void GridHybridSeedLB::Initialize_Communication_Matrix (CentralLB::LDStats *stats)
302 {
303   LDCommData *com_data;
304   int send_object;
305   int recv_object;
306   int send_index;
307   int recv_index;
308   int num_objects;
309   LDObjKey *recv_objects;
310   int index;
311
312
313   Migratable_Objects = new int[Num_Migratable_Objects];
314
315   index = 0;
316   for (int i = 0; i < Num_Objects; i++) {
317     if ((&Object_Data[i])->migratable) {
318       (&Object_Data[i])->secondary_index = index;
319       Migratable_Objects[index] = i;
320       index += 1;
321     }
322   }
323
324   // Create Communication_Matrix[] to hold all object-to-object message counts.
325   Communication_Matrix = new int *[Num_Migratable_Objects];
326   for (int i = 0; i < Num_Migratable_Objects; i++) {
327     Communication_Matrix[i] = new int[Num_Migratable_Objects];
328     for (int j = 0; j < Num_Migratable_Objects; j++) {
329       Communication_Matrix[i][j] = 0;
330     }
331   }
332
333   for (int i = 0; i < stats->n_comm; i++) {
334     com_data = &(stats->commData[i]);
335     if ((!com_data->from_proc()) && (com_data->recv_type() == LD_OBJ_MSG)) {
336       send_object = stats->getHash (com_data->sender);
337       recv_object = stats->getHash (com_data->receiver.get_destObj());
338
339       if ((send_object < 0) || (send_object > Num_Objects) || (recv_object < 0) || (recv_object > Num_Objects)) {
340         continue;
341       }
342
343       if ((!(&Object_Data[send_object])->migratable) || (!(&Object_Data[recv_object])->migratable)) {
344         continue;
345       }
346
347       send_index = (&Object_Data[send_object])->secondary_index;
348       recv_index = (&Object_Data[recv_object])->secondary_index;
349
350       Communication_Matrix[send_index][recv_index] += com_data->messages;
351       Communication_Matrix[recv_index][send_index] += com_data->messages;
352     } else if (com_data->receiver.get_type() == LD_OBJLIST_MSG) {
353       send_object = stats->getHash (com_data->sender);
354
355       if ((send_object < 0) || (send_object > Num_Objects)) {
356         continue;
357       }
358
359       if (!(&Object_Data[send_object])->migratable) {
360         continue;
361       }
362
363       recv_objects = com_data->receiver.get_destObjs (num_objects);   // (num_objects is passed by reference)
364
365       for (int j = 0; j < num_objects; j++) {
366         recv_object = stats->getHash (recv_objects[j]);
367
368         if ((recv_object < 0) || (recv_object > Num_Objects)) {
369           continue;
370         }
371
372         if (!(&Object_Data[recv_object])->migratable) {
373           continue;
374         }
375
376         send_index = (&Object_Data[send_object])->secondary_index;
377         recv_index = (&Object_Data[recv_object])->secondary_index;
378
379         Communication_Matrix[send_index][recv_index] += com_data->messages;
380         Communication_Matrix[recv_index][send_index] += com_data->messages;
381       }
382     }
383   }
384
385   for (int i = 0; i < Num_Migratable_Objects; i++) {
386     Communication_Matrix[i][i] = 0;
387   }
388 }
389
390
391
392 /**************************************************************************
393 ** This takes objects and partitions them into clusters.
394 */
395 void GridHybridSeedLB::Partition_Objects_Into_Clusters (CentralLB::LDStats *stats)
396 {
397   int index;
398   int num_partitions;
399   int *partition_to_cluster_map;
400   int cluster;
401   int partition;
402   int partition_count;
403   int *vertex_weights;
404   int vertex;
405   int *xadj;
406   int num_edges;
407   int *adjncy;
408   int *edge_weights;
409   int count;
410   int weight_flag;
411   int numbering_flag;
412   int options[5];
413   int edgecut;
414   int *newmap;
415
416
417   if (Num_Clusters == 1) {
418     for (int i = 0; i < Num_Objects; i++) {
419       (&Object_Data[i])->cluster = 0;
420     }
421
422     return;
423   }
424
425   // Compute the number of partitions for Metis, based on the scaled CPU power for each cluster.
426   // Also create a partition-to-cluster mapping so the output of Metis can be mapped back to clusters.
427   num_partitions = 0;
428   for (int i = 0; i < Num_Clusters; i++) {
429     num_partitions += (int) ceil ((&Cluster_Data[i])->scaled_cpu_power);
430   }
431
432   partition_to_cluster_map = new int[num_partitions];
433
434   cluster = 0;
435   partition = 0;
436   while (partition < num_partitions) {
437     partition_count = (int) ceil ((&Cluster_Data[cluster])->scaled_cpu_power);
438
439     for (int i = partition; i < (partition + partition_count); i++) {
440       partition_to_cluster_map[i] = cluster;
441     }
442
443     partition += partition_count;
444     cluster += 1;
445   }
446
447   if ((CK_LDB_GridHybridSeedLB_Mode == 1) || (CK_LDB_GridHybridSeedLB_Mode == 3)) {
448     vertex_weights = new int[Num_Migratable_Objects];
449     vertex = 0;
450     for (int i = 0; i < Num_Objects; i++) {
451       if ((&Object_Data[i])->migratable) {
452         vertex_weights[vertex] = (int) ceil ((&Object_Data[i])->load * 10000);
453         vertex += 1;
454       }
455     }
456   }
457
458   // Construct a graph in CSR format for input to Metis.
459   xadj = new int[Num_Migratable_Objects + 1];
460   num_edges = 0;
461   for (int i = 0; i < Num_Migratable_Objects; i++) {
462     for (int j = 0; j < Num_Migratable_Objects; j++) {
463       if (Communication_Matrix[i][j] > 0) {
464         num_edges += 1;
465       }
466     }
467   }
468   adjncy = new int[num_edges];
469   edge_weights = new int[num_edges];
470   count = 0;
471   xadj[0] = 0;
472   for (int i = 0; i < Num_Migratable_Objects; i++) {
473     for (int j = 0; j < Num_Migratable_Objects; j++) {
474       if (Communication_Matrix[i][j] > 0) {
475         adjncy[count] = j;
476         edge_weights[count] = Communication_Matrix[i][j];
477         count += 1;
478       }
479     }
480     xadj[i+1] = count;
481   }
482
483   if ((CK_LDB_GridHybridSeedLB_Mode == 0) || (CK_LDB_GridHybridSeedLB_Mode == 2)) {
484     // Call Metis to partition the communication graph.
485     weight_flag = 1;      // weights on edges only
486     numbering_flag = 0;   // C style numbering (base 0)
487     options[0] = 0;
488     newmap = new int[Num_Migratable_Objects];
489
490     METIS_PartGraphRecursive (&Num_Migratable_Objects, xadj, adjncy, NULL, edge_weights, &weight_flag, &numbering_flag, &num_partitions, options, &edgecut, newmap);
491   } else if ((CK_LDB_GridHybridSeedLB_Mode == 1) || (CK_LDB_GridHybridSeedLB_Mode == 3)) {
492     // Call Metis to partition the communication graph.
493     weight_flag = 3;      // weights on both vertices and edges
494     numbering_flag = 0;   // C style numbering (base 0)
495     options[0] = 0;
496     newmap = new int[Num_Migratable_Objects];
497
498     METIS_PartGraphRecursive (&Num_Migratable_Objects, xadj, adjncy, vertex_weights, edge_weights, &weight_flag, &numbering_flag, &num_partitions, options, &edgecut, newmap);
499   } else {
500     if (_lb_args.debug() > 0) {
501       CkPrintf ("[%d] GridHybridSeedLB was told to use bad mode (%d).\n", CkMyPe(), CK_LDB_GridHybridSeedLB_Mode);
502     }
503   }
504
505   // Place the partitioned objects into their correct clusters.
506   for (int i = 0; i < Num_Migratable_Objects; i++) {
507     partition = newmap[i];
508     cluster = partition_to_cluster_map[partition];
509
510     index = Migratable_Objects[i];
511
512     (&Object_Data[index])->cluster = cluster;
513   }
514
515   // Free memory.
516   delete [] newmap;
517   delete [] edge_weights;
518   delete [] adjncy;
519   delete [] xadj;
520   if ((CK_LDB_GridHybridSeedLB_Mode == 1) || (CK_LDB_GridHybridSeedLB_Mode == 3)) {
521     delete [] vertex_weights;
522   }
523   delete [] partition_to_cluster_map;
524 }
525
526
527
528 /**************************************************************************
529 **
530 */
531 void GridHybridSeedLB::Examine_InterObject_Messages (CentralLB::LDStats *stats)
532 {
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 (int 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 (int 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 GridHybridSeedLB::Map_NonMigratable_Objects_To_PEs ()
596 {
597   for (int i = 0; i < Num_Objects; i++) {
598     if (!((&Object_Data[i])->migratable)) {
599       if (_lb_args.debug() > 1) {
600         CkPrintf ("[%d] GridHybridSeedLB identifies object %d as non-migratable.\n", CkMyPe(), i);
601       }
602
603       Assign_Object_To_PE (i, (&Object_Data[i])->from_pe);
604     }
605   }
606 }
607
608
609
610 /**************************************************************************
611 ** This method locates the maximum WAN object in terms of number of
612 ** messages that traverse a wide-area connection.  The search is
613 ** constrained to objects within the specified cluster that have not yet
614 ** been mapped (balanced) to a PE.
615 **
616 ** The method returns -1 if no matching object is found.
617 */
618 int GridHybridSeedLB::Find_Maximum_Object (int cluster)
619 {
620   int max_index;
621   double max_load;
622
623
624   max_index = -1;
625   max_load = -1.0;
626
627   for (int i = 0; i < Num_Objects; i++) {
628     if ((((&Object_Data[i])->cluster == cluster) && ((&Object_Data[i])->to_pe == -1)) && ((&Object_Data[i])->load > max_load)) {
629       max_index = i;
630       max_load = (&Object_Data[i])->load;
631     }
632   }
633
634   return (max_index);
635 }
636
637
638
639 /**************************************************************************
640 ** This method locates the maximum WAN object in terms of number of
641 ** messages that traverse a wide-area connection.  The search is
642 ** constrained to objects within the specified cluster that have not yet
643 ** been mapped (balanced) to a PE.
644 **
645 ** The method returns -1 if no matching object is found.
646 */
647 int GridHybridSeedLB::Find_Maximum_Border_Object (int cluster)
648 {
649   int max_index;
650   int max_load_index;
651   double max_load;
652   int max_wan_msgs_index;
653   int max_wan_msgs;
654   double load_tolerance;
655
656
657   max_index = -1;
658
659   max_load_index = -1;
660   max_load = -1.0;
661
662   max_wan_msgs_index = -1;
663   max_wan_msgs = -1;
664
665   for (int i = 0; i < Num_Objects; i++) {
666     if (((&Object_Data[i])->cluster == cluster) && ((&Object_Data[i])->to_pe == -1) && ((&Object_Data[i])->num_wan_msgs > 0)) {
667       if ((&Object_Data[i])->load > max_load) {
668         max_load_index = i;
669         max_load = (&Object_Data[i])->load;
670       }
671       if ((&Object_Data[i])->num_wan_msgs > max_wan_msgs) {
672         max_wan_msgs_index = i;
673         max_wan_msgs = (&Object_Data[i])->num_wan_msgs;
674       }
675     }
676   }
677
678   if (max_load_index < 0) {
679     return (max_load_index);
680   }
681
682   if ((&Object_Data[max_load_index])->num_wan_msgs >= (&Object_Data[max_wan_msgs_index])->num_wan_msgs) {
683     return (max_load_index);
684   }
685
686   if (CK_LDB_GridHybridSeedLB_Load_Tolerance <= 0.0) {
687     return (max_load_index);
688   }
689
690   load_tolerance = (&Object_Data[max_load_index])->load * CK_LDB_GridHybridSeedLB_Load_Tolerance;
691
692   max_index = max_load_index;
693
694   for (int i = 0; i < Num_Objects; i++) {
695     if (((&Object_Data[i])->cluster == cluster) && ((&Object_Data[i])->to_pe == -1) && ((&Object_Data[i])->num_wan_msgs > 0) && ((&Object_Data[i])->num_wan_msgs > (&Object_Data[max_index])->num_wan_msgs) && (fabs ((&Object_Data[max_load_index])->load - (&Object_Data[i])->load) <= load_tolerance)) {
696       max_index = i;
697     }
698   }
699
700   return (max_index);
701 }
702
703
704
705 /**************************************************************************
706 ** The method returns -1 if no matching object is found.
707 */
708 int GridHybridSeedLB::Find_Maximum_Object_From_Seeds (int pe)
709 {
710   int cluster;
711   int max_index;
712   int max_comm_events;
713   int max_load_index;
714   double max_load;
715   double load_tolerance;
716   int comm_events;
717
718
719   max_index = -1;
720
721   max_comm_events = 0;
722
723   max_load_index = -1;
724   max_load = -1.0;
725
726   cluster = (&PE_Data[pe])->cluster;
727
728   for (int i = 0; i < Num_Objects; i++) {
729     if (((&Object_Data[i])->cluster == cluster) && ((&Object_Data[i])->to_pe == -1) && ((&Object_Data[i])->load > max_load)) {
730       max_load_index = i;
731       max_load = (&Object_Data[i])->load;
732     }
733   }
734
735   if (max_load_index < 0) {
736     return (max_load_index);
737   }
738
739   if (CK_LDB_GridHybridSeedLB_Load_Tolerance <= 0.0) {
740     return (max_load_index);
741   }
742
743   load_tolerance = (&Object_Data[max_load_index])->load * CK_LDB_GridHybridSeedLB_Load_Tolerance;
744
745   max_index = max_load_index;
746
747   for (int i = 0; i < Num_Objects; i++) {
748     if ((&Object_Data[i])->to_pe == pe) {
749       for (int j = 0; j < Num_Objects; j++) {
750         if (((&Object_Data[j])->cluster == cluster) && ((&Object_Data[j])->to_pe == -1) && (fabs ((&Object_Data[max_load_index])->load - (&Object_Data[j])->load) <= load_tolerance)) {
751           comm_events = Compute_Communication_Events (i, j);
752           if (comm_events > max_comm_events) {
753             max_index = j;
754             max_comm_events = comm_events;
755           }
756         }
757       }
758     }
759   }
760
761   return (max_index);
762 }
763
764
765
766 /**************************************************************************
767 ** The method returns -1 if no matching object is found.
768 */
769 int GridHybridSeedLB::Find_Maximum_Border_Object_From_Seeds (int pe)
770 {
771   int cluster;
772   int max_index;
773   int max_comm_events;
774   int max_load_index;
775   double max_load;
776   double load_tolerance;
777   int comm_events;
778
779
780   max_index = -1;
781
782   max_comm_events = 0;
783
784   max_load_index = -1;
785   max_load = -1.0;
786
787   cluster = (&PE_Data[pe])->cluster;
788
789   for (int i = 0; i < Num_Objects; i++) {
790     if (((&Object_Data[i])->cluster == cluster) && ((&Object_Data[i])->to_pe == -1) && ((&Object_Data[i])->num_wan_msgs > 0) && ((&Object_Data[i])->load > max_load)) {
791       max_load_index = i;
792       max_load = (&Object_Data[i])->load;
793     }
794   }
795
796   if (max_load_index < 0) {
797     return (max_load_index);
798   }
799
800   if (CK_LDB_GridHybridSeedLB_Load_Tolerance <= 0.0) {
801     return (max_load_index);
802   }
803
804   load_tolerance = (&Object_Data[max_load_index])->load * CK_LDB_GridHybridSeedLB_Load_Tolerance;
805
806   max_index = max_load_index;
807
808   for (int i = 0; i < Num_Objects; i++) {
809     if ((&Object_Data[i])->to_pe == pe) {
810       for (int j = 0; j < Num_Objects; j++) {
811         if (((&Object_Data[j])->cluster == cluster) && ((&Object_Data[j])->to_pe == -1) && ((&Object_Data[j])->num_wan_msgs > 0) && (fabs ((&Object_Data[max_load_index])->load - (&Object_Data[j])->load) <= load_tolerance)) {
812           comm_events = Compute_Communication_Events (i, j);
813           if (comm_events > max_comm_events) {
814             max_index = j;
815             max_comm_events = comm_events;
816           }
817         }       
818       }
819     }
820   }
821
822   return (max_index);
823 }
824
825
826
827 /**************************************************************************
828 **
829 */
830 int GridHybridSeedLB::Compute_Communication_Events (int obj1, int obj2)
831 {
832   int send_index;
833   int recv_index;
834
835
836   send_index = (&Object_Data[obj1])->secondary_index;
837   recv_index = (&Object_Data[obj2])->secondary_index;
838
839   return (Communication_Matrix[send_index][recv_index]);
840 }
841
842
843
844 /**************************************************************************
845 ** This method locates the minimum WAN PE in terms of number of objects
846 ** that communicate with objects across a wide-area connection.  The search
847 ** is constrained to PEs within the specified cluster.
848 **
849 ** In the event of a "tie" (i.e., the number of WAN objects on a candidate
850 ** PE is equal to the minimum number of WAN objects discovered so far) the
851 ** tie is broken by considering the scaled CPU loads on the PEs.  The PE
852 ** with the smaller scaled load is the better candidate.  In the event of
853 ** a secondary tie, the secondary tie is broken by considering the number
854 ** of LAN objects on the two PEs.
855 **
856 ** The method returns -1 if no matching PE is found.
857 */
858 int GridHybridSeedLB::Find_Minimum_PE (int cluster)
859 {
860   if ((CK_LDB_GridHybridSeedLB_Mode == 0) || (CK_LDB_GridHybridSeedLB_Mode == 1)) {
861     int min_index;
862     int min_objs;
863
864
865     min_index = -1;
866     min_objs = MAXINT;
867
868     for (int i = 0; i < Num_PEs; i++) {
869       if (((&PE_Data[i])->available) && ((&PE_Data[i])->cluster == cluster)) {
870         if ((&PE_Data[i])->num_objs < min_objs) {
871           min_index = i;
872           min_objs = (&PE_Data[i])->num_objs;
873         } else if (((&PE_Data[i])->num_objs == min_objs) &&
874                    ((&PE_Data[i])->num_wan_objs < (&PE_Data[min_index])->num_wan_objs)) {
875           min_index = i;
876         } else if (((&PE_Data[i])->num_objs == min_objs) &&
877                    ((&PE_Data[i])->num_wan_objs == (&PE_Data[min_index])->num_wan_objs) &&
878                    ((&PE_Data[i])->num_wan_msgs < (&PE_Data[min_index])->num_wan_msgs)) {
879           min_index = i;
880         } else if (((&PE_Data[i])->num_objs == min_objs) &&
881                    ((&PE_Data[i])->num_wan_objs == (&PE_Data[min_index])->num_wan_objs) &&
882                    ((&PE_Data[i])->num_wan_msgs == (&PE_Data[min_index])->num_wan_msgs) &&
883                    ((&PE_Data[i])->scaled_load < (&PE_Data[min_index])->scaled_load)) {
884           min_index = i;
885         }
886       }
887     }
888
889     return (min_index);
890   } else if ((CK_LDB_GridHybridSeedLB_Mode == 2) || (CK_LDB_GridHybridSeedLB_Mode == 3)) {
891     int min_index;
892     int min_load_index;
893     double min_scaled_load;
894     int min_wan_msgs_index;
895     int min_wan_msgs;
896     double load_tolerance;
897
898
899     min_index = -1;
900
901     min_load_index = -1;
902     min_scaled_load = MAXDOUBLE;
903
904     min_wan_msgs_index = -1;
905     min_wan_msgs = MAXINT;
906
907     for (int i = 0; i < Num_PEs; i++) {
908       if (((&PE_Data[i])->available) && ((&PE_Data[i])->cluster == cluster)) {
909         if ((&PE_Data[i])->scaled_load < min_scaled_load) {
910           min_load_index = i;
911           min_scaled_load = (&PE_Data[i])->scaled_load;
912         }
913         if ((&PE_Data[i])->num_wan_msgs < min_wan_msgs) {
914           min_wan_msgs_index = i;
915           min_wan_msgs = (&PE_Data[i])->num_wan_msgs;
916         }
917       }
918     }
919
920     // If no PE at all was found, return a -1.
921     if (min_load_index < 0) {
922       return (min_load_index);
923     }
924
925     // If the number of WAN messages on the lightest loaded PE happens to match the minimum number
926     // of WAN messages overall, we win because this target PE is overall the minimum PE in terms
927     // of both load *and* WAN messages.
928     if ((&PE_Data[min_load_index])->num_wan_msgs <= (&PE_Data[min_wan_msgs_index])->num_wan_msgs) {
929       return (min_load_index);
930     }
931
932     // Otherwise, we now search for PEs that have loads +/- our tolerance.  If any PE has a load
933     // within our tolerance, check its number of WAN messages.  The one of these that has the
934     // fewest WAN messages is probably the best candidate for placing the next object onto.
935
936     load_tolerance = (&PE_Data[min_load_index])->scaled_load * CK_LDB_GridHybridSeedLB_Load_Tolerance;
937
938     min_index = min_load_index;
939
940     for (int i = 0; i < Num_PEs; i++) {
941       if (((&PE_Data[i])->available) && ((&PE_Data[i])->cluster == cluster)) {
942         if (i != min_load_index) {
943           if (fabs ((&PE_Data[i])->scaled_load - (&PE_Data[min_load_index])->scaled_load) <= load_tolerance) {
944             if ((&PE_Data[i])->num_wan_msgs < (&PE_Data[min_index])->num_wan_msgs) {
945               min_index = i;
946             }
947           }
948         }
949       }
950     }
951
952     return (min_index);
953   } else {
954     if (_lb_args.debug() > 0) {
955       CkPrintf ("[%d] GridHybridSeedLB was told to use bad mode (%d).\n", CkMyPe(), CK_LDB_GridHybridSeedLB_Mode);
956     }
957     return (-1);
958   }
959 }
960
961
962
963 /**************************************************************************
964 ** This method assigns target_object to target_pe.  The data structure
965 ** entry for target_pe is updated appropriately with measurements from
966 ** target_object.  This updated information is considered when placing
967 ** successive objects onto PEs.
968 */
969 void GridHybridSeedLB::Assign_Object_To_PE (int target_object, int target_pe)
970 {
971   (&Object_Data[target_object])->to_pe = target_pe;
972
973   (&PE_Data[target_pe])->num_objs += 1;
974
975   if ((&Object_Data[target_object])->num_lan_msgs > 0) {
976     (&PE_Data[target_pe])->num_lan_objs += 1;
977     (&PE_Data[target_pe])->num_lan_msgs += (&Object_Data[target_object])->num_lan_msgs;
978   }
979
980   if ((&Object_Data[target_object])->num_wan_msgs > 0) {
981     (&PE_Data[target_pe])->num_wan_objs += 1;
982     (&PE_Data[target_pe])->num_wan_msgs += (&Object_Data[target_object])->num_wan_msgs;
983   }
984
985   (&PE_Data[target_pe])->scaled_load += (&Object_Data[target_object])->load / (&PE_Data[target_pe])->relative_speed;
986 }
987
988
989
990 /**************************************************************************
991 ** The Charm++ load balancing framework invokes this method to cause the
992 ** load balancer to migrate objects to "better" PEs.
993 */
994 void GridHybridSeedLB::work (LDStats *stats)
995 {
996   int target_pe;
997   int target_object;
998
999
1000   if (_lb_args.debug() > 0) {
1001     CkPrintf ("[%d] GridHybridSeedLB is working (mode=%d, background load=%d, load tolerance=%f).\n", CkMyPe(), CK_LDB_GridHybridSeedLB_Mode, CK_LDB_GridHybridSeedLB_Background_Load, CK_LDB_GridHybridSeedLB_Load_Tolerance);
1002   }
1003
1004   // Since this load balancer looks at communications data, it must call stats->makeCommHash().
1005   stats->makeCommHash ();
1006
1007   // Initialize object variables for the number of PEs and number of objects.
1008   Num_PEs = stats->nprocs();
1009   Num_Objects = stats->n_objs;
1010
1011   if (_lb_args.debug() > 0) {
1012     CkPrintf ("[%d] GridHybridSeedLB is examining %d PEs and %d objects.\n", CkMyPe(), Num_PEs, Num_Objects);
1013   }
1014
1015   // Initialize the PE_Data[] data structure.
1016   Initialize_PE_Data (stats);
1017
1018   // If at least one available PE does not exist, return from load balancing.
1019   if (Available_PE_Count() < 1) {
1020     if (_lb_args.debug() > 0) {
1021       CkPrintf ("[%d] GridHybridSeedLB finds no available PEs -- no balancing done.\n", CkMyPe());
1022     }
1023
1024     delete [] PE_Data;
1025
1026     return;
1027   }
1028
1029   // Determine the number of clusters.
1030   // If any PE is not mapped to a cluster, return from load balancing.
1031   Num_Clusters = Compute_Number_Of_Clusters ();
1032   if (Num_Clusters < 1) {
1033     if (_lb_args.debug() > 0) {
1034       CkPrintf ("[%d] GridHybridSeedLB finds incomplete PE cluster map -- no balancing done.\n", CkMyPe());
1035     }
1036
1037     delete [] PE_Data;
1038
1039     return;
1040   }
1041
1042   if (_lb_args.debug() > 0) {
1043     CkPrintf ("[%d] GridHybridSeedLB finds %d clusters.\n", CkMyPe(), Num_Clusters);
1044   }
1045
1046   // Initialize the Object_Data[] data structure.
1047   Initialize_Object_Data (stats);
1048
1049   // Compute number of migratable objects.
1050   Num_Migratable_Objects = Compute_Migratable_Object_Count ();
1051
1052   // Initialize the Cluster_Data[] data structure.
1053   Initialize_Cluster_Data ();
1054
1055   // Initialize the Communication_Matrix[] data structure.
1056   Initialize_Communication_Matrix (stats);
1057
1058   // Partition objects into clusters.
1059   Partition_Objects_Into_Clusters (stats);
1060
1061   // Examine all object-to-object messages for intra-cluster and inter-cluster communications.
1062   Examine_InterObject_Messages (stats);
1063
1064   // Map non-migratable objects to PEs.
1065   Map_NonMigratable_Objects_To_PEs ();
1066
1067   // Map migratable objects to PEs in each cluster.
1068   for (int i = 0; i < Num_Clusters; i++) {
1069
1070     while (1) {
1071       target_pe = Find_Minimum_PE (i);
1072
1073       if ((&PE_Data[target_pe])->num_objs == 0) {
1074         target_object = Find_Maximum_Border_Object (i);
1075       } else {
1076         target_object = Find_Maximum_Border_Object_From_Seeds (target_pe);
1077         if (target_object == -1) {
1078           target_object = Find_Maximum_Border_Object (i);
1079         }
1080       }
1081
1082       if ((target_object == -1) || (target_pe == -1)) {
1083         break;
1084       }
1085
1086       Assign_Object_To_PE (target_object, target_pe);
1087     }
1088
1089     while (1) {
1090       target_pe = Find_Minimum_PE (i);
1091
1092       target_object = Find_Maximum_Object_From_Seeds (target_pe);
1093       if (target_object == -1) {
1094         target_object = Find_Maximum_Object (i);
1095       }
1096
1097       if ((target_object == -1) || (target_pe == -1)) {
1098         break;
1099       }
1100
1101       Assign_Object_To_PE (target_object, target_pe);
1102     }
1103   }
1104
1105   // Make the assignment of objects to PEs in the load balancer framework.
1106   for (int i = 0; i < Num_Objects; i++) {
1107     stats->to_proc[i] = (&Object_Data[i])->to_pe;
1108
1109     if (_lb_args.debug() > 2) {
1110       CkPrintf ("[%d] GridHybridSeedLB migrates object %d from PE %d to PE %d.\n", CkMyPe(), i, stats->from_proc[i], stats->to_proc[i]);
1111     } else if (_lb_args.debug() > 1) {
1112       if (stats->to_proc[i] != stats->from_proc[i]) {
1113         CkPrintf ("[%d] GridHybridSeedLB migrates object %d from PE %d to PE %d.\n", CkMyPe(), i, stats->from_proc[i], stats->to_proc[i]);
1114       }
1115     }
1116   }
1117
1118   // Free memory.
1119   delete [] Migratable_Objects;
1120   for (int i = 0; i < Num_Migratable_Objects; i++) {
1121     delete [] Communication_Matrix[i];
1122   }
1123   delete [] Communication_Matrix;
1124   delete [] Cluster_Data;
1125   delete [] Object_Data;
1126   delete [] PE_Data;
1127 }
1128
1129 #include "GridHybridSeedLB.def.h"