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