3.12 Advanced Load Balancing

3.12.1 Control CPU Load Statistics

Charm++ programmers can control CPU load data in the load balancing database before a load balancing phase is started (which is the time when load balancing database is collected and used by load balancing strategies).

In an array element, the following function can be invoked to overwrite the CPU load that is measured by load balancing framework.

   double newTiming;
   setObjTime(newTiming);

setObjTime() is defined as a method of class CkMigratable, which is the superclass of all array elements.

The users can also retrieve the current timing that the load balancing runtime has measured for the current array element.

   double measuredTiming;
   measuredTiming = getObjTime();

This is useful when the users want to derive a new CPU load based on the existing one.

3.12.2 Model-based Load Balancing

Charm++ programmers can also choose to feed load balancer with their own CPU timing of each Chare based on certain computational model of the applications.

To do so, first turn off automatic CPU load measurement completely by setting:

   usesAutoMeasure = CmiFalse;

in array element's constructor.

Then the users need to implement the following function to the chare array classes:

   virtual void CkMigratable::UserSetLBLoad();      // defined in base class

This function served as a callback that is called on each chare object when AtSync() is called and ready to do load balancing. The implementation of UserSetLBLoad() is simply to set the current chare object's CPU load to load balancer framework. setObjTime() described above can be used for this.

3.12.3 Write a Measurement-based Object Migration Strategy

Charm++ programmers can pick load balancing strategy from Charm++'s built-in strategies(see 3.11.2) for the best performance based on the characteristics of their applications, they can also choose to write their own load balancing strategies.

Charm++ load balancing framework provides a simple scheme to incorporate new load balancing strategies. To write a new load balancing strategy involves the following steps (We use an example of writing a centralized load balancer fooLB to illustrate the steps).

1. Create files named fooLB.ci, fooLB.h and fooLB.C. One can choose to copy and rename the files RandCentLB (a random centralized load balancer) and rename the class name in those files.

2. Implement the fooLB class method -- fooLB::work(CentralLB::LDStats* stats, int count) This method takes the load balancing database (stats) as an input, and output the new mapping of objects to processors in stats->to_proc array.

3. To compile the strategy files, first add fooLB into the load balancer list in charm/tmp/Makefile_lb.sh. Run the script in charm/tmp, which creates the new Makefile named ``Make.lb''.

4. Run ``make depends'' to update dependence rule of Charm++ files. And run ``make charm++'' to compile Charm++ which includes the new load balancing strategy files.

3.12.4 Understand Load Balancing Database Data Structure

To write a load balancing strategy, one may want to know what information is measured during the runtime and how it is represented in the load balancing database data structure?

There are mainly 3 categories of information: a) processor information including processor speed, background load; b) object information including per object cpu/wallclock compute time and c) communication information .

The database data structure named LDStats is defined in CentralLB.h:

  struct ProcStats {  // per processor
    double total_walltime;
    double total_cputime;
    double idletime;
    double bg_walltime;
    double bg_cputime;
    int pe_speed;
    double utilization;
    CmiBool available;
    int   n_objs;
  }

  struct LDStats { // load balancing database
    ProcStats  *procs;
    int count;

    int   n_objs;
    int   n_migrateobjs;
    LDObjData* objData;

    int   n_comm;
    LDCommData* commData;

    int  *from_proc, *to_proc;
  }

1. procs array defines processor attributes and usage data for each processor;
2. objData array records per object information, LDObjData is defined in lbdb.h;
3. commData array records per communication information. LDCommData is defined in lbdb.h.