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