Minor fixes.
[charm.git] / doc / cldb / HowToLB.tex
1 \documentclass[11pt]{article}
2
3 \newif\ifpdf
4 \ifx\pdfoutput\undefined
5   \pdffalse
6 \else
7   \pdfoutput=1
8   \pdftrue
9 \fi
10
11 \ifpdf
12   \pdfcompresslevel=9
13   \usepackage[pdftex,colorlinks=true,plainpages=false]{hyperref}
14 \else
15 \fi
16
17 \pagestyle{headings}
18 %\setlength{\textwidth}{6.5in}
19 %\setlength{\textheight}{9in}
20 %\setlength{\parindent}{0in}
21 %\setlength{\topmargin}{-.5in}
22 %\parskip 0.1in
23
24
25 %
26 % Constants
27 %
28 %\newcommand{\version}{4.5}             %%% The current version number
29 %\newcommand{\prevversion}{4.3} %%% The previous version number
30
31 %
32 % Commands
33 %
34 \newcommand{\zap}[1]{ }
35 \newcommand{\fcmd}{\bf}         %%% Font for Charm commands
36 \newcommand{\fparm}{\it\sf}     %%% Font for parameters to Charm commands
37 \newcommand{\fexec}{\bf}        %%% Font for compile/execute cmds/options
38 \newcommand{\atitle}[1]{{\it #1}}
39 \newcommand{\keyword}[1]{{\textbf{#1}}}
40 \newcommand{\userword}[1]{{\fparm \textsc{#1}}}
41 \newcommand{\constraint}[1]{Note: {\it #1}}
42 \newcommand{\note}[1]{Note: {\it #1}}
43
44 \title{How To Write A Converse Load Balancer}
45 \author{Terry L. Wilmarth}
46
47 \begin{document}
48
49 \maketitle
50
51 \section{Introduction}
52
53 This manual details how to write your own load balancer in Converse.
54 A Converse load balancer can be used by any Converse program, but also
55 serves as the balancer of Charm++ chare creation messages.
56 Specifically, to use a load balancer, you would pass messages to
57 CldEnqueue rather than directly to the scheduler.  This is the default
58 behavior with chare creation message in Charm++.  Thus, the primary
59 provision of a new load balancer is an implementation of the
60 CldEnqueue function.
61
62 \section{Existing Load Balancers and Provided Utilities}
63
64 Throughout this manual, we will occasionally refer to the source code
65 of two provided load balancers, the random initial placement load balancer
66 ({\tt cldb.rand.c}) and the graph-based load balancer ({\tt
67 cldb.graph.c}).  The functioning of these balancers will be described
68 in detail later.
69
70 In addition, a special utility is provided that allows us to add and
71 remove load-balanced messages from the scheduler's queue.  The source
72 code for this is available in {\tt cldb.c}.  The usage of this utility
73 will also be described here in detail.
74
75 \section{A Sample Load Balancer}
76
77 This manual steps through the design of a load balancer using an
78 example which we will call HELP!  The HELP! load balancer has each processor
79 periodically send half of its load to its neighbor in a ring.
80 Specifically, for N processors, processor K will send approximately half of
81 its load to (K+1)\%N, every 100 milliseconds (this is an example only;
82 we leave the genius approaches up to you).
83
84 \section{CldEnqueue}
85
86 The prototype for the {\bf CldEnqueue} function is as follows:
87
88 {\tt void {\bf CldEnqueue}(int pe, void *msg, int infofn);}
89
90 Here, {\tt pe} is the intended destination of the {\tt msg}.  It may
91 take on the values of:
92
93 \begin{itemize}
94 \item Any particular processor number - the message must be sent to
95 that processor
96 \item {\tt CLD\_ANYWHERE} - the message can be placed on any processor
97 \item {\tt CLD\_BROADCAST} - the message must be sent to all processors
98 excluding the local processor
99 \item {\tt CLD\_BROADCAST\_ALL} - the message must be sent to all processors
100 including the local processor
101 \end{itemize}
102
103 {\bf CldEnqueue} must handle all of these possibilities.  The only
104 case in which the load balancer should get control of a mesage is when
105 {\tt pe = CLD\_ANYWHERE}.  All other messages must be sent off to their
106 intended destinations and passed on to the scheduler as if they never
107 came in contact with the load balancer. 
108
109 The integer parameter {\tt infofn} is a handler index for a
110 user-provided function that supplies CldEnqueue with information about
111 the message {\tt msg}.  We will describe this in more detail later.
112
113 Thus, an implementation of the {\bf CldEnqueue} function might have
114 the following structure:
115
116 \begin{verbatim}
117 void CldEnqueue(int pe, void *msg, int infofn)
118 {
119   ...
120   if (pe == CLD_ANYWHERE)
121     /* These messages can be load balanced */
122   else if (pe == CmiMyPe())
123     /* Enqueue the message in the scheduler locally */
124   else if (pe==CLD_BROADCAST) 
125     /* Broadcast to all but self */
126   else if (pe==CLD_BROADCAST_ALL)
127     /* Broadcast to all plus self */
128   else /* Specific processor number was specified */
129     /* Send to specific processor */
130 }
131 \end{verbatim}
132
133 In order to fill in the code above, we need to know more about the
134 message before we can send it off to a scheduler's queue, either
135 locally or remotely.  For this, we have the info function.  The
136 prototype of an info function must be as follows:
137
138 \noindent{\tt void ifn(void *msg, CldPackFn *pfn, int *len, int
139 *queueing, int *priobits, unsigned int **prioptr);}
140
141 Thus, to use the info function, we need to get the actual function via
142 the handler index provided to {\bf CldEnqueue}.  Typically, {\bf
143 CldEnqueue} would contain the following declarations:
144
145 \begin{verbatim}
146   int len, queueing, priobits; 
147   unsigned int *prioptr;
148   CldPackFn pfn;
149   CldInfoFn ifn = (CldInfoFn)CmiHandlerToFunction(infofn);
150 \end{verbatim}
151
152 \noindent Subsequently, a call to {\tt ifn} would look like this:
153
154 \begin{verbatim}
155   ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
156 \end{verbatim}
157
158 The info function extracts information from the message about its size,
159 queuing strategy and priority, and also a pack function, which will be
160 used when we need to send the message elsewhere.  For now, consider
161 the case where the message is to be locally enqueued:
162
163 \begin{verbatim}
164   ...
165   else if (pe == CmiMyPe())
166     {
167       ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
168       CsdEnqueueGeneral(msg, queueing, priobits, prioptr);
169     }
170   ...
171 \end{verbatim}
172
173 Thus, we see the info function is used to extract info from the
174 message that is necessary to pass on to {\bf CsdEnqueueGeneral}.
175
176 In order to send the message to a remote destination and enqueue it in
177 the scheduler, we need to pack it up with a special pack function so
178 that it has room for extra handler information and a reference to the
179 info function.  Therefore, before we handle the last three cases of
180 {\bf CldEnqueue}, we have a little extra work to do:
181
182 \begin{verbatim}
183   ...
184   else
185     {
186       ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
187       if (pfn) {
188         pfn(&msg);
189         ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
190       }
191       CldSwitchHandler(msg, CpvAccess(CldHandlerIndex));
192       CmiSetInfo(msg,infofn);
193       ...
194 \end{verbatim}
195
196 Calling the info function once gets the pack function we need, if
197 there is one.  We then call the pack function which rearranges the
198 message leaving space for the info function, which we will need to
199 call on the message when it is received at its destination, and also
200 room for the extra handler that will be used on the receiving side to
201 do the actual enqueuing.  {\bf CldSwitchHandler} is used to set this extra
202 handler, and the receiving side must restore the original handler.
203
204 In the above code, we call the info function again because some of the
205 values may have changed in the packing process.  
206
207 Finally, we handle our last few cases:
208
209 \begin{verbatim}
210   ...
211       if (pe==CLD_BROADCAST) 
212         CmiSyncBroadcastAndFree(len, msg);
213       else if (pe==CLD_BROADCAST_ALL)
214         CmiSyncBroadcastAllAndFree(len, msg);
215       else CmiSyncSendAndFree(pe, len, msg);
216     }
217 }
218 \end{verbatim}
219
220 \section{Other Functions}
221
222 A CldHandler function is necessary to receive messages forwarded by
223 CldEnqueue:
224
225 \begin{verbatim}
226 CpvDeclare(int, CldHandlerIndex);
227
228 void CldHandler(void *msg)
229 {
230   CldInfoFn ifn; CldPackFn pfn;
231   int len, queueing, priobits; unsigned int *prioptr;
232   
233   CmiGrabBuffer((void **)&msg);
234   CldRestoreHandler(msg);
235   ifn = (CldInfoFn)CmiHandlerToFunction(CmiGetInfo(msg));
236   ifn(msg, &pfn, &len, &queueing, &priobits, &prioptr);
237   CsdEnqueueGeneral(msg, queueing, priobits, prioptr);
238 }
239 \end{verbatim}
240
241 Note that the {\bf CldHandler} properly restores the message's original
242 handler using {\bf CldRestoreHandler}, and calls the info function to obtain
243 the proper parameters to pass on to the scheduler.
244
245 Also required is a CldModuleInit function:
246
247 \begin{verbatim}
248 void CldModuleInit()
249 {
250   CpvInitialize(int, CldHandlerIndex);
251   CpvAccess(CldHandlerIndex) = CmiRegisterHandler(CldHandler);
252   CldModuleGeneralInit();
253
254   /* call other init processes here */
255   CldGraphModuleInit();
256 }
257 \end{verbatim}
258
259 Here's an example of an additional init function:
260
261 \begin{verbatim}
262 void CldGraphModuleInit()
263 {
264   CpvInitialize(int, CldRelocatedMessages);
265   CpvInitialize(int, CldLoadBalanceMessages);
266   CpvInitialize(int, CldMessageChunks);
267
268   CpvAccess(CldRelocatedMessages) = CpvAccess(CldLoadBalanceMessages) = 
269     CpvAccess(CldMessageChunks) = 0;
270
271   CldBalance();
272 }
273 \end{verbatim}
274
275 You may want to provide the three status variables, which get
276 initialized in your own module init function (called CldGraphModuleInit
277 above).  These can be used to keep track of what your LB is doing (see usage
278 in cldb.graph.c and itc++queens program).
279
280 \begin{verbatim}
281 CpvDeclare(int, CldRelocatedMessages);
282 CpvDeclare(int, CldLoadBalanceMessages);
283 CpvDeclare(int, CldMessageChunks);
284 \end{verbatim}
285
286 A method for queueing balanceable messages is provided in cldb.c.  That file
287 contains instructions for its use, and examples of its use can be found in
288 cldb.graph.c.  Its primary function is to provide a way to retrieve messages
289 from the scheduler queue that have not yet been processed, so that they may be
290 moved to another processor.
291
292
293 \section{The HELP! Load Balancer}
294
295 The HELP! Load Balancer is available in
296 charm/src/Common/conv-ldb/cldb.test.c.  To try out your own load balancer you
297 can use this filename and SUPER\_INSTALL will compile it and you can link it
298 into your Charm++ programs with -balance test.  (To add your own new balancers
299 permanently and give them another name other than "test" you will need to
300 change the Makefile used by SUPER\_INSTALL. Don't worry about this for now.)
301 The cldb.test.c provides a good starting point for new load balancers.
302
303 Look at the code for the HELP! balancer, starting with the {\bf CldEnqueue}
304 function.  This is almost exactly as described earlier.  One exception is the
305 handling of a few extra cases: specifically if we are running the program on
306 only one processor, we don't want to do any load balancing.  The other obvious
307 difference is in the first case: how do we handle messages that can be load
308 balanced?  Rather than enqueuing the message directly with the scheduler, we
309 make use of the token queue.  This means that messages can later be removed
310 for relocation.  {\bf CldPutToken} adds the message to the token queue on the
311 local processor.
312
313 Now look two functions up from {\bf CldEnqueue}.  We have an additional
314 handler besides the {\bf CldHandler}: the {\bf CldBalanceHandler}.  The
315 purpose of this special handler is to receive messages that can be still be
316 relocated again in the future.  Just like the first case of {\bf CldEnqueue}
317 uses {\bf CldPutToken} to keep the message retrievable, {\bf
318 CldBalanceHandler} does the same with relocatable messages it receives.
319
320 Next we look at our initialization functions to see how the process gets
321 started.  The {\bf CldModuleInit} function gets called by the common Converse
322 initialization code, and in turn, it calls our {\bf CldHelpModuleInit}.  This
323 function starts off the periodic load distribution process by making a call to
324 {\bf CldDistributeTokens}.  This function computes an approximation of half of
325 its total load ({\bf CsdLength}()), and if that amount exceeds the number of
326 movable messages ({\bf CldCountTokens}()), we attempt to move all of the
327 movable messages.  To do this, we pass this number of messages to move and the
328 number of the PE to move them to, to the {\bf CldMultipleSend} function.
329
330 {\bf CldMultipleSend} is generally useful for any load balancer that sends
331 multiple messages to one processor.  It takes parameters {\sl pe} and {\sl
332 numToMove}, and handles the packing and transmission of as many messages up to
333 {\sl numToMove} as it can find, to the processor {\sl pe}.  If the number
334 and/or size of the messages sent is very large, {\bf CldMultipleSend} will
335 transmit them in reasonably sized parcels.
336
337 That's all there is to the HELP! balancer.  Make the test version of
338 itc++queens and try it out.
339
340 \end{document}