*** empty log message ***
[charm.git] / doc / convext / ldb.tex
1 \chapter{Load Balancing}
2
3 Converse provides the programmer with a number of Load Balancing
4 strategies in order to distribute work among the processors in the
5 system. The load balancing strategy to be used in the program can be
6 specified at the link time. \note{In future versions, we will
7 provide users with the ability to write their own load balancing
8 strategies. However, in this version, the choice is limited to certain
9 predefined load balancing strategies.} The following functions are provided
10 for interfacing a Converse program with the load balancing module.
11
12 \function{void CldNewSeedFromLocal(void *msg, void *ldb, void (*sendfn)(),int queueing, int priolen, int *prioptr)}
13 \index{CldNewSeedFromLocal}
14 \desc{Hand over the message \param{msg}, which is freshly generated by
15 the local processor, to the load balancing module. This load balancing
16 module may use the space provided by \param{ldb} to either send the
17 message off to other processors using \param{sendfn()}, or may decide
18 to enqueue it locally using the queuing strategy \param{queueing} and
19 priority specifiers \param{priolen} and \param{prioptr}.}
20
21 \function{void CldNewSeedFromNet(void *msg, void *ldb, void (*sendfn)(),int queueing, int priolen, int *prioptr)}
22 \index{CldNewSeedFromNet}
23 \desc{Hand over the message \param{msg}, which is received from
24 network, to the load balancing module. This load balancing
25 module may use the space provided by \param{ldb} to either send the
26 message off to other processors using \param{sendfn()}, or may decide
27 to enqueue it locally using the queuing strategy \param{queueing} and
28 priority specifiers \param{priolen} and \param{prioptr}.}
29
30
31 The rationale behind this interface is as follows: A typical load
32 balancing strategy can have different behaviors based on whether the
33 message (\param{msg}) specifying work to be done is freshly generated
34 by the local processor or has arrived from the network after one or
35 more hops from the generating processor to local processor.
36 \note{Message \param{msg} must have its handler field set before it is
37 handed over to the load balancing module.} If the work is freshly
38 issued, one hands it over to the load balancing module using function
39 \param{CldNewSeedFromLocal()} otherwise calls
40 \param{CldNewSeedFromNet()}. Each load balancing strategy may have
41 different use of the parameter \param{ldb}. Some of the currently
42 implemented language specific load balancing strategies use this area
43 in the message for sending the load information on local processor
44 piggy-backed onto the message periodically; some of them may not need
45 this area at all. \note{The only ldb strategy available to Converse
46 users currently, i.e. random, does not use this area and the user could
47 specify \param{void * (0))} there.}
48
49 Some of the parallel languages or libraries built on top of Converse
50 may have the message packing mechanisms which have to be called before
51 any message crosses address boundaries. Therefore the load balancing
52 module cannot use built-in functions such as \param{CmiAsyncSend()}
53 for sending the work off to another processor. For this reason, the
54 user needs to specify a function \param{sendfn()} which takes two
55 parameters:  \param{void *msgptr} and \param{int destPE}. Languages or
56 runtimes using packing can pack the message before sending it to
57 processor \param{destPE} in \param{sendfn()}. However, if the load
58 balancing module decides not to send \param{msg} to any other
59 processor, it may queue it to the processors local queue. For this
60 eventuality, one has to specify the queuing parameters in above calls.
61 They are:  \param{queuing}--a queuing strategy (see
62 \param{CsdEnqueueGeneral())}; \param{priolen}--length of the priority
63 field; and \param{prioptr}--pointer to the priority information. If the
64 user is not using priorities, \param{priolen} should be 0.
65
66 \internal{
67 \function{void CldFillLdb(int destPE, void *ldb)}
68 \index{CldFillLdb}
69 \desc{}
70
71 \function{CldStripLdb(void *ldb)}
72 \index{CldStripLdb}
73 \desc{}
74 }
75
76 %\internal{
77 %\function {void ClbInit(void)}
78 %Routine called at scheduler startup to allow the load balancer to
79 %register its own message handlers.
80 %}
81 %
82 %\function {void ClbEnqueue(Message *msg, FunctionPtr send\_func)}
83 %Function called by a handler to let the load balancer know about a
84 %``seed'' message. If the seed is to be processed locally, the
85 %load balancer will
86 %enqueue it in the scheduler's queue to be eventually executed.
87 %{\sf send\_func} specifies the function
88 %which should be used to send the seed to another processor
89 %if it is not to be processed locally.
90 %
91 %\function {void ClbEnqueuePrio(Message *msg, FunctionPtr send\_func,
92 %void *prio, int len)} 
93 %Same as {\sf ClbEnqueue()}, except that a priority {\sf prio} of length
94 %{\sf len} bytes is associated with the message.
95 %
96 %
97 %The most general load balancing scheme will have three opportunities
98 %to migrate load.  The first will be when {\sf ClbEnQueue()} is called.
99 %This routine will either immediately send the message elsewhere for
100 %processing, or enqueue it in a local data structure.  A token message
101 %will then be enqueued with the scheduler to reactivate the load
102 %balancing in order to execute the seed message at the appropriate
103 %time.  The second opportunity for load balancing occurs when the load
104 %balancing module receives a request from the load balancing module on
105 %another processor for some work.  When this occurs, a message will be
106 %delivered to the requesting node from the load balance queue, and the
107 %token message in the scheduler queue will be marked as invalid.  The
108 %third opportunity occurs when a token message is removed from the
109 %scheduler queue.  Control will return to the load balancing module,
110 %which could then choose to send seed messages to another host.
111