added description of --with-lbtime-type=type option
[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{Writing a communication-aware load balancing strategy}
62
63 Charm++ programmers can choose an existing load balancing strategy from
64 Charm++'s built-in strategies(see ~\ref{lbStrategy}) for the best performance
65 based on the characteristics of their applications. However, they can also
66 choose to write their own load balancing strategies.
67
68 The Charm++ load balancing framework provides a simple scheme to incorporate
69 new load balancing strategies. The programmer needs to write their strategy for
70 load balancing based on a instrumented ProcArray and ObjGraph provided by the
71 load balancing framework. This strategy is to be incorporated within this
72 function:
73
74 \begin{alltt}
75 void FooLB::work(LDStats *stats) \{
76   /** ========================== INITIALIZATION ============================= */
77   ProcArray *parr = new ProcArray(stats);
78   ObjGraph *ogr = new ObjGraph(stats);
79
80   /** ============================= STRATEGY ================================ */
81   /// The strategy goes here
82   /// The strategy goes here
83   /// The strategy goes here
84   /// The strategy goes here
85   /// The strategy goes here
86
87   /** ============================== CLEANUP ================================ */
88   ogr->convertDecisions(stats);
89 \}
90 \end{alltt}
91
92 Figure~\ref{fig:ckgraph} explains the two data structures available to the
93 strategy: ProcArray and ObjGraph. Using these, the strategy should assign new
94 processors for objects it wants to be migrated through the setNewPe() method.
95
96 \begin{figure}[h]
97 \centering
98 \includegraphics[width=6.0in]{fig/ckgraph}
99 \caption{ProcArray and ObjGraph data structures to be used when writing a load
100 balancing strategy}
101 \label{fig:ckgraph}
102 \end{figure}
103
104 Incorporating this strategy into the Charm++ build framework is explained in
105 the next section.
106
107 \subsubsection{Adding a load balancer to Charm++}
108
109 Let us assume that we are writing a new centralized load balancer called FooLB.
110 The next few steps explain the addition of the load balancer to the Charm++
111 build system:
112
113 \begin{enumerate}
114 \item Create files named {\em FooLB.ci, FooLB.h and FooLB.C}. One can choose to
115 copy and rename the files GraphPartLB.* and rename the class name in those
116 files.
117
118 \item Implement the strategy in the {\em FooLB} class method --- {\bf
119 FooLB::work(LDStats* stats)} as described in the previous section.
120 %This method takes the load balancing database ({\em stats}) as an input, and
121 %output the new mapping of objects to processors in {\em stats->to\_proc}
122 %array.
123
124 \item Build charm for your platform (This will create the required links in the
125 tmp directory).
126
127 \item To compile the strategy files, first add {\em FooLB} in the ALL\_LDBS
128 list in charm/tmp/Makefile\_lb.sh. Also comment out the line containing
129 UNCOMMON\_LDBS in Makefile\_lb.sh.  If FooLB will require some libraries at
130 link time, you also need to create the dependency file called
131 libmoduleFooLB.dep. Run the script in charm/tmp, which creates the new Makefile
132 named ``Make.lb''.
133
134 \item Run ``make depends'' to update dependence rule of Charm++ files.  And run
135 ``make charm++'' to compile Charm++ which includes the new load balancing
136 strategy files.
137 \end{enumerate}
138
139
140 \subsubsection{Understand Load Balancing Database Data Structure}
141
142 \label{lbdatabase}
143
144 To write a load balancing strategy, one may want to know 
145 what information is measured during the runtime and how it is represented in
146 the load balancing database data structure?
147
148 There are mainly 3 categories of information: a) processor information including processor speed, background load; b) object information including per object
149 cpu/wallclock compute time and c) communication information .
150
151 The database data structure named {\kw LDStats} is defined in {\em CentralLB.h}:
152
153 \begin{verbatim}
154
155   struct ProcStats {  // per processor
156     LBRealType total_walltime;
157     LBRealType total_cputime;
158     LBRealType idletime;
159     LBRealType bg_walltime;
160     LBRealType bg_cputime;
161     int pe_speed;
162     double utilization;
163     CmiBool available;
164     int   n_objs;
165   }
166
167   struct LDStats { // load balancing database
168     ProcStats  *procs;
169     int count;
170
171     int   n_objs;
172     int   n_migrateobjs;
173     LDObjData* objData;
174
175     int   n_comm;
176     LDCommData* commData;
177
178     int  *from_proc, *to_proc;
179   }
180
181 \end{verbatim}
182
183 \begin{enumerate}
184 \item {\em LBRealType} is the data type for load balancer measured time. It is "double" by default. User can specify the type to float if wanted at Charm++ compile time. For example, ./build charm++ net-linux-x86\_64 {-}{-}with-lbtime-type=float;
185 \item {\em procs} array defines processor attributes and usage data for each
186 processor;
187 \item {\em objData} array records per object information, {\em LDObjData} is defined in {\em lbdb.h};
188 \item {\em commData} array records per communication information. {\em LDCommData} is defined in {\em lbdb.h}.
189 \end{enumerate}
190