f63718080eab9348174f51bbd0c025d5c762b602
[charm.git] / doc / charm++ / order.tex
1 \subsection{Delivery Order}
2
3 By default, \charmpp\ will process the messages you send in roughly
4 FIFO\index{message delivery order} order when they arrive at a PE.
5 For most programs, this behavior is fine.  However, for optimal
6 performance, some programs need more explicit control over the order
7 in which messages are processed. \charmpp\ allows you to adjust
8 delivery order on a per-message basis.
9
10 % Example general use cases here
11
12 \subsubsection{Queueing Strategies}
13 \label{queueing strategies}
14
15 The simplest call available to change the order in which messages
16 are processed is \kw{CkSetQueueing}.
17
18 \function{void CkSetQueueing(MsgType message, int queueingtype)}
19
20 where \uw{queueingtype} is one of the following constants:
21
22 \begin{alltt}
23   CK_QUEUEING_FIFO
24   CK_QUEUEING_LIFO
25   CK_QUEUEING_IFIFO
26   CK_QUEUEING_ILIFO
27   CK_QUEUEING_BFIFO
28   CK_QUEUEING_BLIFO
29   CK_QUEUEING_LFIFO
30   CK_QUEUEING_LLIFO
31 \end{alltt}
32
33 The first two options,  \kw{CK\_QUEUEING\_FIFO} and
34 \kw{CK\_QUEUEING\_LIFO}, are used as follows:
35
36 \begin{alltt}
37   MsgType *msg1 = new MsgType ;
38   CkSetQueueing(msg1, CK_QUEUEING_FIFO);
39
40   MsgType *msg2 = new MsgType ;
41   CkSetQueueing(msg2, CK_QUEUEING_LIFO);
42
43   CkEntryOptions opts1, opts2;
44   opts1.setQueueing(CK_QUEUEING_FIFO);
45   opts2.setQueueing(CK_QUEUEING_LIFO);
46
47   chare.entry_name(arg1, arg2, opts1);
48   chare.entry_name(arg1, arg2, opts2);
49 \end{alltt}
50
51 When message \kw{msg1} arrives at its destination, it will be pushed
52 onto the end of the message queue as usual.  However, when \kw{msg2}
53 arrives, it will be pushed onto the {\em front} of the message
54 queue. Similarly, the two parameter-marshalled calls to \kw{chare}
55 will be inserted at the end and beginning of the message queue,
56 respectively.
57
58 \subsubsection{Prioritized Execution}
59 \label{prioritized message passing}
60 \index{prioritized execution}
61 \index{prioritized message passing}
62 \index{priorities}
63
64 The basic FIFO and LIFO strategies are sufficient to approximate
65 parallel breadth-first and depth-first explorations of a problem
66 space, but they don't admit more fine-grained control. To provide that
67 degree of control, \charmpp\ also allows explicit prioritization of
68 messages.
69
70 The other six queueing strategies involve the use of
71 priorities\index{priorities}.  There are two kinds of priorities which
72 can be attached to a message: {\sl integer priorities}\index{integer
73   priorities} and {\sl bitvector priorities}\index{bitvector
74   priorities}. These correspond to the {\em I} and {\em B} queueing
75 strategies, respectively. In both cases, numerically lower priorities
76 will be dequeued and delivered before numerically greater
77 priorities. The FIFO and LIFO queueing strategies then control the
78 relative order in which messages of the same priority will be
79 delivered.
80
81 To attach a priority field to a
82 message, one needs to set aside space in the message's buffer while
83 allocating the message\index{message priority}.  To achieve this, the
84 size of the priority field\index{priority field} in bits should be
85 specified as a placement argument to the \kw{new} operator, as
86 described in Section \ref{memory allocation}.  Although the size of
87 the priority field is specified in bits, it is always padded to an
88 integral number of {\tt int}s.  A pointer to the priority part of the
89 message buffer can be obtained with this call:
90
91 \function{void *CkPriorityPtr(MsgType msg)}
92 \index{CkPriorityPtr}
93 \index{priority pointer}
94
95 Integer priorities are quite straightforward.  One allocates a message
96 with an extra integer parameter to ``new'' (see the first line of the
97 example below), which sets aside enough space (in bits) in the message
98 to hold the priority.  One then stores the priority in the message.
99 Finally, one informs the system that the message contains an integer
100 priority using \kw{CkSetQueueing}:
101
102 \begin{alltt}
103   MsgType *msg = new (8*sizeof(int)) MsgType;
104   *(int*)CkPriorityPtr(msg) = prio;
105   CkSetQueueing(msg, CK_QUEUEING_IFIFO);
106 \end{alltt}
107
108 Integer proiorities for parameter-marshalled messages can be achieved
109 through {\tt CkEntryOptions::setPriority()}:
110
111 \begin{alltt}
112   CkEntryOptions opts;
113   opts.setPriority(7);
114   chare.entry_name(arg1, arg2, opts);
115 \end{alltt}
116
117 Bitvector priorities are somewhat more complicated.  Bitvector
118 priorities are arbitrary-length bit-strings representing fixed-point
119 numbers in the range 0 to 1.  For example, the bit-string ``001001''
120 represents the number .001001\raisebox{-.5ex}{\scriptsize binary}.  As
121 with the simpler kind of priority, higher numbers represent lower
122 priorities.  Unlike the simpler kind of priority, bitvectors can be of
123 arbitrary length, therefore, the priority numbers they represent can
124 be of arbitrary precision.
125
126 Arbitrary-precision priorities\index{arbitrary-precision priorities}
127 are often useful in AI search-tree applications.  Suppose we have a
128 heuristic suggesting that tree node $N_1$ should be searched before
129 tree node $N_2$.  We therefore designate that node $N_1$ and its
130 descendants will use high priorities, and that node $N_2$ and its
131 descendants will use lower priorities.  We have effectively split the
132 range of possible priorities in two.  If several such heuristics fire
133 in sequence, we can easily split the priority range \index{priority
134 range splitting} in two enough times that no significant bits remain,
135 and the search begins to fail for lack of meaningful priorities to
136 assign.  The solution is to use arbitrary-precision priorities,
137 i.e. bitvector priorities.
138
139 To assign a bitvector priority, two methods are available.  The
140 first is to obtain a pointer to the priority field using  \kw{CkPriorityPtr},
141 and then manually set the bits using the bit-setting operations
142 inherent to C.  To achieve this, one must know the format
143 \index{bitvector format} of the
144 bitvector, which is as follows: the bitvector is represented as an
145 array of unsigned integers.  The most significant bit of the first
146 integer contains the first bit of the bitvector.  The remaining bits
147 of the first integer contain the next 31 bits of the bitvector.
148 Subsequent integers contain 32 bits each.  If the size of the
149 bitvector is not a multiple of 32, then the last integer contains 0
150 bits for padding in the least-significant bits of the integer.
151
152 The second way to assign priorities is only useful for those who are
153 using the priority range-splitting\index{priority range splitting}
154 described above.  The root of the tree is assigned the null
155 priority-string.  Each child is assigned its parent's priority with
156 some number of bits concatenated.  The net effect is that the entire
157 priority of a branch is within a small epsilon of the priority of its
158 root.
159
160 It is possible to utilize unprioritized messages, integer priorities,
161 and bitvector priorities in the same program.  The messages will be
162 processed in roughly the following order\index{multiple priority types}:
163
164 \begin{itemize}
165
166 \item Among messages enqueued with bitvector priorities, the
167 messages are dequeued according to their priority.  The
168 priority ``0000...'' is dequeued first, and ``1111...'' is
169 dequeued last.
170
171 \item Unprioritized messages are treated as if they had the
172 priority ``1000...'' (which is the ``middle'' priority, it
173 lies exactly halfway between ``0000...'' and ``1111...'').
174
175 \item Integer priorities are converted to bitvector priorities.  They
176 are normalized so that the integer priority of zero is converted to
177 ``1000...'' (the ``middle'' priority).  To be more specific, the
178 conversion is performed by adding 0x80000000 to the integer, and then
179 treating the resulting 32-bit quantity as a 32-bit bitvector priority.
180
181 \item Among messages with the same priority, messages are
182 dequeued in FIFO order or LIFO order, depending upon which
183 queuing strategy was used.
184
185 \end{itemize}
186
187 Additionally, {\sl long integer priorities} can be specified by the {\em L} strategy. 
188
189 A final reminder about prioritized execution: \charmpp\ processes
190 messages in {\it roughly} the order you specify; it never guarantees
191 that it will deliver the messages in {\it precisely} the
192 order\index{message delivery order} you specify. Thus, the correctness
193 of your program should never depend on the order in which the runtime
194 delivers messages. However, it makes a serious attempt to be
195 ``close'', so priorities can strongly affect the efficiency of your
196 program.
197
198 \subsubsection{Skipping the Queue}
199
200 Some operations that one might want to perform are sufficiently
201 latency-sensitive that they should never wait in line behind other
202 messages. The \charmpp\ runtime offers two attributes for entry
203 methods, {\kw expedited} and {\kw immediate}, to serve these
204 needs. For more information on these attributes, see
205 Section~\ref{attributes} and the example in {\tt
206   charm/pgms/charm++/megatest/immediatering.C}.