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