doc/charm++/quiesce.tex

   1 \section{Completion Detection}
   2
   3 Completion detection is a method for automatically detecting completion of a
   4 distributed process within an application. This functionality is helpful when
   5 the exact number of messages expected by individual objects is not known. In
   6 such cases, the process must achieve global consensus as to the number of
   7 messages produced and the number of messages consumed.  Completion is reached
   8 within a distributed process when the participating objects have produced and
   9 consumed an equal number of events globally. The number of global events that
  10 will be produced and consumed does not need to be known, just the number of
  11 producers is required.
  12
  13
  14 The completion detection feature is implemented in \charmpp{} as a
  15 module, and therefore is only included when ``{\tt -module completion}'' is
  16 specified when linking your application.
  17
  18 First, the detector should be constructed. This call would typically
  19 belong in application startup code (it initializes the group that
  20 keeps track of completion):
  21
  22 \begin{alltt}
  23 CProxy_CompletionDetector detector = CProxy_CompletionDetector::ckNew();
  24 \end{alltt}
  25
  26 When it is time to start completion detection, invoke the following method of the
  27 library on {\em all} branches of the completion detection group:
  28
  29 \begin{alltt}
  30 void start_detection(int num_producers,
  31                      CkCallback start,
  32                      CkCallback all_produced,
  33                      CkCallback finish,
  34                      int prio);
  35 \end{alltt}
  36
  37 The \verb|num_producers| parameter is the number of objects (chares)
  38 that will produce elements. So if every chare array element will produce one
  39 event, then it would be the size of the array.
  40
  41 The \verb|start| callback notifies your program that it is safe to
  42 begin producing and consuming (this state is reached when the module
  43 has finished its internal initialization).
  44
  45 The \verb|all_produced| callback notifies your program when the client has
  46 called \verb|done| with arguments summing to \verb|num_producers|.
  47
  48 The \verb|finish| callback is invoked when completion has been
  49 detected (all objects participating have produced and consumed an
  50 equal number of elements globally).
  51
  52 The \verb|prio| parameter is the priority with which the completion detector will run.
  53 This feature is still under development, but it should be set below the
  54 application's priority if possible.
  55
  56 For example, the call
  57
  58 \begin{alltt}
  59 detector.start_detection(10,
  60                          CkCallback(CkIndex_chare1::start_test(), thisProxy),
  61                          CkCallback(CkIndex_chare1::produced_test(), thisProxy),
  62                          CkCallback(CkIndex_chare1::finish_test(), thisProxy),
  63                          0);
  64 \end{alltt}
  65
  66 sets up completion detection for 10 producers. Once initialization is done, the callback
  67 associated with the {\tt start\_test} method will be invoked. Once all 10 producers have
  68 called \verb|done| on the completion detector, the {\tt produced\_test} method
  69 will be invoked. Furthermore, when the system detects completion, the callback associated
  70 with {\tt finish\_test} will be invoked. Finally, the priority given to the completion
  71 detection library is set to 0 in this case.
  72
  73 Once initialization is complete (the ``start'' callback is triggered),
  74 make the following call to the library:
  75
  76 \begin{alltt}
  77 void CompletionDetector::produce(int events_produced)
  78 void CompletionDetector::produce() // 1 by default
  79 \end{alltt}
  80
  81 For example, within the code for a chare array object, you might make the following call:
  82 \begin{alltt}
  83 detector.ckLocalBranch()->produce(4);
  84 \end{alltt}
  85
  86 Once all the ``events'' that this chare is going to produce have been sent out,
  87 make the following call:
  88
  89 \begin{alltt}
  90 void CompletionDetector::done(int producers_done)
  91 void CompletionDetector::done() // 1 by default
  92 \end{alltt}
  93
  94 \begin{alltt}
  95 detector.ckLocalBranch()->done();
  96 \end{alltt}
  97
  98 At the same time, objects can also consume produced elements, using the following calls:
  99
 100 \begin{alltt}
 101 void CompletionDetector::consume(int events_consumed)
 102 void CompletionDetector::consume() // 1 by default
 103 \end{alltt}
 104
 105 \begin{alltt}
 106 detector.ckLocalBranch()->consume();
 107 \end{alltt}
 108
 109 Note that an object may interleave calls to {\tt produce()} and {\tt consume()}, i.e.
 110 it could produce a few elements, consume a few, etc. When it is done producing its elements,
 111 it should call {\tt done()}, after which cannot {\tt produce()} any more elements. However,
 112 it can continue to {\tt consume()} elements even after calling {\tt done()}.
 113 When the library detects that, globally, the number of produced elements equals
 114 the number of consumed elements, and all producers have finished producing
 115 (i.e. called {\tt done()}), it will invoke the \verb|finish| callback.
 116 Thereafter, \verb|start_detection| can be called again to restart the process.
 117
 118 \section{Quiescence Detection}
 119 \label{sec:qd}
 120
 121 In \charmpp, \index{quiescence}quiescence is defined as the state in which no
 122 processor is executing an entry point, no messages are awaiting processing, and
 123 there are no messages in-flight.  \charmpp\ provides two facilities for
 124 detecting quiescence: \kw{CkStartQD} and \kw{CkWaitQD}.  \kw{CkStartQD}
 125 registers with the system a callback that is to be invoked the next time
 126 \index{quiescence}quiescence is detected. Note that if immediate messages are
 127 used, QD cannot be used.  \kw{CkStartQD} has two variants
 128 which expect the following arguments:
 129
 130 \begin{enumerate}
 131 \item
 132 A \uw{CkCallback} object. The syntax of this call looks like:
 133 \begin{alltt}
 134   CkStartQD(const CkCallback& cb);
 135 \end{alltt}
 136
 137 Upon quiescence detection, the specified callback is called with no parameters. Note that
 138 using this variant, you could have your program terminate after quiescence is detected, by
 139 supplying the above method with a CkExit callback (\S~\ref{sec:callbacks/creating}).
 140
 141 \item An index corresponding to the entry function that is to be called,
 142 and a handle to the chare on which that entry function should be called.  The
 143 syntax of this call looks like this:
 144
 145 \begin{alltt}
 146  CkStartQD(int Index,const CkChareID* chareID);
 147 \end{alltt}
 148
 149 To retrieve the corresponding index of a particular \index{entry method}entry
 150 method, you must use a static method contained within the
 151 (\kw{charmc}-generated) \uw{CkIndex} object corresponding to the
 152 \index{chare}chare containing that entry method.  The syntax of this call is as
 153 follows:
 154
 155 \begin{alltt}
 156 \kw{myIdx}=CkIndex_\uw{ChareClass}::\uw{entryMethod}(\uw{parameters});
 157 \end{alltt}
 158
 159 where \uw{ChareClass} is the \CC{} class of the chare containing
 160 the desired entry method, \uw{entryMethod} is the name of that entry method,
 161 and \uw{parameters} are the parameters taken by the method.
 162 These parameters are only used to resolve the proper \uw{entryMethod};
 163 they are otherwise ignored.
 164
 165 \end{enumerate}
 166
 167 \kw{CkWaitQD}, by contrast, does not register a callback.  Rather,
 168 \kw{CkWaitQD} {\em blocks} and does not return until \index{quiescence}quiescence is
 169 detected.  It takes no parameters and returns no value.  A call to
 170 \kw{CkWaitQD} simply looks like this:
 171
 172 \begin{alltt}
 173   CkWaitQD();
 174 \end{alltt}
 175
 176 Note that \kw{CkWaitQD} should only be called from a threaded
 177 \index{entry method}entry method because a call to \kw{CkWaitQD} suspends the
 178 current thread of execution ({\em cf.} \S~\ref{threaded}).
 179 %If it were called from outside a threaded entry
 180 %method it would suspend the main thread of execution of the processor from
 181 %which \kw{CkWaitQD} was called, and the entire program would come to a grinding
 182 %halt on that processor.
 183
 184 %\function{void CkExitAfterQuiescence()} \index{CkExitAfterQuiescence}
 185 %\desc{This call informs the Charm RTS that computation on all processors
 186 %should terminate as soon as the machine becomes completely idle--that is,
 187 %after all messages and entry methods are finished.  This is the state of
 188 %quiescence, as described further in Section~\ref{sec:qd}.
 189 %This routine returns immediately.}
 190