b6849950c6c597f53459f02f04aef8ac990c5cad
[charm.git] / doc / charm++ / advancedlb.tex
1
2 \subsection{Advanced Load Balancing}
3
4 \label{advancedlb}
5
6 \subsubsection{Control CPU Load Statistics}
7
8 Charm++ programmers can control CPU load data in the load balancing database
9 before a load balancing phase is started (which is the time when load balancing
10 database is collected and used by load balancing strategies).
11
12 In an array element, the following function can be invoked to overwrite the 
13 CPU load that is measured by load balancing framework.
14
15 \begin{alltt}
16    double newTiming;
17    setObjTime(newTiming);
18 \end{alltt}
19
20 {\em setObjTime()} is defined as a method of class {\em CkMigratable}, which is
21 the superclass of all array elements.
22
23 The users can also retrieve the current timing that the load balancing runtime
24 has measured for the current array element. 
25  
26 \begin{alltt} 
27    double measuredTiming; 
28    measuredTiming = getObjTime(); 
29 \end{alltt}
30
31 This is useful when the users want to derive a new CPU load based on the 
32 existing one.
33
34 \subsubsection{Model-based Load Balancing}
35
36 Charm++ programmers can also choose to feed load balancer with their own CPU
37 timing of each Chare based on certain computational model of the applications.
38
39 To do so, first turn off automatic CPU load measurement completely
40 by setting:
41
42 \begin{alltt}
43    usesAutoMeasure = CmiFalse;
44 \end{alltt}
45
46 in array element's constructor.
47
48 Then the users need to implement the following function to the chare array
49 classes:
50
51 \begin{alltt}
52    virtual void CkMigratable::UserSetLBLoad();      // defined in base class
53 \end{alltt}
54
55 This function served as a callback that is called on each chare object when
56 {\em AtSync()} is called and ready to do load balancing. The implementation of
57 {\em UserSetLBLoad()} is simply to set the current chare object's CPU load to
58 load balancer framework. {\em setObjTime()} described above can be used for
59 this.
60
61 \subsubsection{Write a Measurement-based Object Migration Strategy}
62 \label{writelb}
63
64 Charm++ programmers can pick load balancing strategy from Charm++'s built-in
65 strategies(see ~\ref{lbStrategy}) for the best performance based on the 
66 characteristics of their applications, they can also choose to write their 
67 own load balancing strategies.
68
69 Charm++ load balancing framework provides a simple scheme to incorporate new 
70 load balancing strategies. To write a new load balancing strategy
71 involves the following steps (We use an example of writing a centralized
72 load balancer {\em fooLB} to illustrate the steps).
73
74 \begin{enumerate}
75 \item Create files named {\em fooLB.ci, fooLB.h and fooLB.C}. One can choose to
76 copy and rename the files RotateLB.* and rename the class name in those files.
77
78 \item Implement the {\em fooLB} class method --- {\bf fooLB::work(LDStats*
79 stats)} This method takes the load balancing database ({\em stats}) as an
80 input, and output the new mapping of objects to processors in {\em
81 stats->to\_proc} array.
82
83 \item Build charm for your platform (This will create the required links in the tmp directory).
84
85 \item To compile the strategy files, first add {\em fooLB} into the load
86 balancer list in charm/tmp/Makefile\_lb.sh. If fooLB will require some
87 libraries at link time, you also need to create the dependency file called
88 libmodulefooLB.dep. Run the script in charm/tmp, which creates the new Makefile
89 named ``Make.lb''.
90
91 \item Run ``make depends'' to update dependence rule of Charm++ files.  And run
92 ``make charm++'' to compile Charm++ which includes the new load balancing
93 strategy files.
94 \end{enumerate}
95
96
97 \subsubsection{Understand Load Balancing Database Data Structure}
98
99 \label{lbdatabase}
100
101 To write a load balancing strategy, one may want to know 
102 what information is measured during the runtime and how it is represented in
103 the load balancing database data structure?
104
105 There are mainly 3 categories of information: a) processor information including processor speed, background load; b) object information including per object
106 cpu/wallclock compute time and c) communication information .
107
108 The database data structure named {\kw LDStats} is defined in {\em CentralLB.h}:
109
110 \begin{verbatim}
111
112   struct ProcStats {  // per processor
113     double total_walltime;
114     double total_cputime;
115     double idletime;
116     double bg_walltime;
117     double bg_cputime;
118     int pe_speed;
119     double utilization;
120     CmiBool available;
121     int   n_objs;
122   }
123
124   struct LDStats { // load balancing database
125     ProcStats  *procs;
126     int count;
127
128     int   n_objs;
129     int   n_migrateobjs;
130     LDObjData* objData;
131
132     int   n_comm;
133     LDCommData* commData;
134
135     int  *from_proc, *to_proc;
136   }
137
138 \end{verbatim}
139
140 \begin{enumerate}
141 \item {\em procs} array defines processor attributes and usage data for each
142 processor;
143 \item {\em objData} array records per object information, {\em LDObjData} is defined in {\em lbdb.h};
144 \item {\em commData} array records per communication information. {\em LDCommData} is defined in {\em lbdb.h}.
145 \end{enumerate}
146